Campus Event Calendar

Event Entry

What and Who

Efficient Algorithms for Unknown Markets

Martin Hoefer
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience

Date, Time and Location

Thursday, 21 April 2016
45 Minutes
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.


Martin Hoefer
--email hidden
passcode not visible
logged in users only

Martin Hoefer, 03/23/2016 16:00
Martin Hoefer, 03/19/2016 08:49
Martin Hoefer, 03/18/2016 12:06 -- Created document.