Approximately Maximizing Efficiency and Revenue in Polyhedral Environments



Thanh Nguyen

Cornell University

Monday May 7, 2007
**3:40 PM - 4:00 PM**, 5130 Upson Hall



We consider a resource allocation game in polyhedral environments.

Polyhedral environments model a wide range of problems, including bandwidth sharing, some models of Adwords auctions and general resource allocation. We extend the fair sharing mechanism for such resource allocation games. We show that our mechanism simultaneously creates approximately efficient allocations and approximately maximizes revenue.

We also develop a new approach for analyzing games of these types. At the core of this approach is the relation between the condition for Nash equilibriums of the game and the dual of a certain linear program.

Joint work with Eva Tardos.