Tilting at Windmills: The economic performance of markets in the wild
Speaker: Nicole Immorlica
Microsoft Research New England
November 25, 2014 - 4:00 p.m. to 5:00 p.m.
Location: CII (Low) 3051
Hosted By: Dr. Elliot Anshelevich (x6491)
Theoretical computer scientists often view the world through a lens of paranoia, focusing on bounding the worst-case performance of the systems they study. Economists instead prefer to assume the inputs are drawn from a well-behaved and commonly known distribution and study the resulting average-case performance of the system.
In this talk, we survey efforts aimed at a middle ground. We identify small realistic perturbations to economic settings that result in a good properties often even for worst-case inputs. We begin with a classic example of this phenomenon: in a canonical single-item market, if buyers' values are drawn from a ``nice'' (but unknown) distribution, then simple auctions have good revenue. We then discuss more complex multi-item markets, and identify noisy supply and demand conditions that guarantee good welfare. Finally, we mention extensions of these results to non-market games, including network routing, two-sided matching, and information aggregation in social networks.
In all cases, we identify conditions under which games perform much better than the corresponding worst-case instances, and often improve significantly as the market grows. Many of our results are based on a new analytical framework for bounding inefficiency of a sequence of games.
Based on joint works with Michal Feldman, Brendan Lucier, Mohammad Mahdian, Tim Roughgarden, Vasilis Syrkganis, and Matt Weinberg.
Last updated: August 21, 2014