Tilting at Windmills: The Economic Efficiency of Large Games

Speaker: Nicole Immorlica

Date: Tuesday, November 18, 2014

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Refreshments: 4:15 PM

Public: Yes

Location: G449 (Patil/Kiva)

Event Type:

Room Description:

Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan, MIT, CSAIL

Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Nicole Immorlica: Tilting at Windmills: The Economic Efficiency of Large Games

Abstract:

It is well-established that when participants in a system behave strategically, this can lead to sub-optimal outcomes in the worst case. But computer science applications typically exhibit conditions not present in these worst-case scenarios. Instead, they often feature a large number of participants who have a degree of uncertainty about the game they're playing. The goal of this talk is to develop an analytical framework for bounding the inefficiency of games under such conditions.

Our framework is based on a novel extension of smoothness, a standard technique for developing inefficiency, or price-of-anarchy, bounds in fixed games, to a sequence of games. We first define an approximate utility -- one that a delusional player might imagine he faces. We prove that this utility well-approximates the actual utility under realistic structural assumptions regarding market size and noise. We then show that this approximate utility is smooth with respect to the actual game.

We demonstrate the wide applicability of our framework through instantiations for several well-studied models, including simultaneous single-item auctions, greedy combinatorial auctions, and routing games. In all cases, we identify conditions under which the efficiency of large games is much better than that of worst-case instances.

Based on joint work with Michal Feldman, Brendan Lucier, Tim Roughgarden, and VasilisSyrkganis.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2014.

Created by Deborah Goodwin Email at Tuesday, July 29, 2014 at 11:36 AM.