Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Efficient Algorithms for Unknown Markets
Speaker:Martin Hoefer
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 21 April 2016
Duration:45 Minutes
Building:E1 4
This talk surveys our recent work on revealed preference problems in classic market models without information about the number of agents, their individual utilities and endowments. Here we only rely on queries that return aggregate demand for goods in order to, e.g., learn utility functions or compute a market equilibrium.

As a main result, we design a simple ascending-price algorithm to compute a (1+eps)-approx. equilibrium in exchange markets with weak gross substitute (WGS) property. It runs in time polynomial in market parameters and log(1/eps). This is the first efficient algorithm for this broad class of markets which is easy to implement and avoids heavy machinery such as the ellipsoid method. Moreover, we show how to extend our approach to obtain the first efficient algorithm for exact equilibria in markets with spending constraint utilities. Finally, we touch upon a novel descending-price technique that yields the first efficient algorithm for Fisher markets with budget-additive utilities.

Name(s):Martin Hoefer
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created by:Martin Hoefer, 03/18/2016 12:06 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Martin Hoefer, 03/23/2016 04:00 PM
  • Martin Hoefer, 03/19/2016 08:49 AM
  • Martin Hoefer, 03/18/2016 12:06 PM -- Created document.