Price of Anarchy of Practical Auctions Mechanism Design for Simple Auctions Éva Tardos, Cornell Joint work with Vasilis Syrgkanis Games and Quality of Solutions • Rational selfish action can lead to outcome bad for everyone Question: How to design Tragedy of the Commons games that avoid such tragedies Simple vs Optimal • Simple practical mechanism, that lead to good outcome. • optimal outcome is not practical • Traffic subject to congestion delays Congestion game =cost (delay) depends only on congestion on edges Simple vs Optimal • Simple practical mechanism, that lead to good outcome. • optimal outcome is not practical Also true in many other applications: • Need distributed protocol that routers can implement • Models a distributed process e.g. Bandwidth Sharing, Load Balancing, Games with good Price of Anarchy • Routing: • Cars or packets though the Internet • Bandwidth Sharing: • routers share limited bandwidth between processes • Facility Location: • Decide where to host certain Web applications • Load Balancing • Balancing load on servers (e.g. Web servers) • Network Design: • Independent service providers building the Internet Today Auction “Games” Basic Auction: single item Vickrey Auction $2 $5 $7 $3 $4 Pays $5 Player utility (cid:1874) (cid:3398) (cid:1868)  item value –price paid (cid:3036) (cid:3036) Vickrey Auction – Truthful (second price) - Efficient - Simple Extension VCG ( truthful and efficient), but not so simple Vickrey, Clarke, Groves Combinatorial Auctions Buyers have values for any subset S: v (S) i user utility v (S)- p  value –price paid i i Efficient assignment: max ∑ (cid:1874) (cid:1845)∗ (cid:3036) (cid:3036) (cid:3036) over partitions S* i • May be hard to compute • Needs central coordination Vickrey, Clarke, Groves Combinatorial Auctions Buyers have values for any subset S: v (S) i user utility v (S)- p  value –price paid i i Payment: welfare loss of others p =max  v (S )- ∑ (cid:1874) (cid:1845)∗ i ji j j (cid:3037) (cid:3037) ji Truthful! • Needs central coordination • pricing unintuitive Other games We will assume quasi-linear utility for money, value outcome x and price p has utility v (x)-p for user i. i Public projects Bandwidth Sharing Truthful Auctions and Composition? 2 • Second Price Auction 2 truthful and simple Two simultaneous second price auctions? No! How about sequentially? No!