* Faculty       * Staff       * Students & Alumni       * Committees       * Contact       * Institute Directory
* Undergraduate Program       * Graduate Program       * Courses       * Institute Catalog      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Colloquia       * Seminars       * News       * Events       * Institute Events      
* Overview       * Lab Manual       * Institute Computing      
No Menu Selected

* News


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