Algorithmic Game Theory

1. Front Matter

   PDF

2. A Classification of Weakly Acyclic Games

   • Krzysztof R. Apt, Sunil Simon

   Pages 1-12

3. Selfishness Level of Strategic Games

   • Krzysztof R. Apt, Guido Schäfer

   Pages 13-24

4. Mechanisms for Scheduling with Single-Bit Private Values

   • Vincenzo Auletta, George Christodoulou, Paolo Penna

   Pages 25-36

5. The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games

   • Vittorio Bilò, Marios Mavronicolas

   Pages 37-48

6. An Optimal Bound to Access the Core in TU-Games

   • Sylvain Béal, Eric Rémila, Philippe Solal

   Pages 49-60

7. Convergence of Ordered Improvement Paths in Generalized Congestion Games

   • K. Ruben Brokkelkamp, Mees J. de Vries

   Pages 61-71

8. Basic Network Creation Games with Communication Interests

   • Andreas Cord-Landwehr, Martina Hüllmann, Peter Kling, Alexander Setzer

   Pages 72-83

9. Common Knowledge and State-Dependent Equilibria

   • Nuh Aygun Dalkiran, Moshe Hoffman, Ramamohan Paturi, Daniel Ricketts, Andrea Vattani

   Pages 84-95

10. Approximating the Minmax Value of Three-Player Games within a Constant is as Hard as Detecting Planted Cliques

    • Kord Eickmeyer, Kristoffer Arnstfelt Hansen, Elad Verbin

    Pages 96-107

11. Approximate Well-Supported Nash Equilibria Below Two-Thirds

    • John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen

    Pages 108-119

12. Mechanisms and Impossibilities for Truthful, Envy-Free Allocations

    • Michal Feldman, John Lai

    Pages 120-131

13. Capacitated Network Design Games

    • Michal Feldman, Tom Ron

    Pages 132-143

14. Decentralized Dynamics for Finite Opinion Games

    • Diodato Ferraioli, Paul W. Goldberg, Carmine Ventre

    Pages 144-155

15. On the Hardness of Network Design for Bottleneck Routing Games

    • Dimitris Fotakis, Alexis C. Kaporis, Thanasis Lianeas, Paul G. Spirakis

    Pages 156-167

16. Ad Auctions with Data

    • Hu Fu, Patrick Jordan, Mohammad Mahdian, Uri Nadav, Inbal Talgam-Cohen, Sergei Vassilvitskii

    Pages 168-179

17. Commodity Auctions and Frugality Ratios

    • Paul W. Goldberg, Antony McCabe

    Pages 180-191

18. On the Communication Complexity of Approximate Nash Equilibria

    • Paul W. Goldberg, Arnoud Pastink

    Pages 192-203

19. Congestion Games with Capacitated Resources

    • Laurent Gourvès, Jérôme Monnot, Stefano Moretti, Nguyen Kim Thang

    Pages 204-215

20. Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances

    • Jochen Könemann, Kate Larson, David Steiner

    Pages 216-226

This book constitutes the refereed proceedings of the 5th International Symposium on Algorithmic Game Theory, SAGT 2012, held in Barcelona, Spain, in October 2012. The 22 revised full papers presented together with 2 invited lectures were carefully reviewed and selected from 65 submissions. The papers present original research at the intersection of Algorithms and Game Theory and address various current topics such as solution concepts in game theory; efficiency of equilibria and price of anarchy; complexity classes in game theory; computational aspects of equilibria; computational aspects of fixed-point theorems; repeated games; evolution and learning in games; convergence of dynamics; coalitions, coordination and collective action; reputation, recommendation and trust systems; graph-theoretic aspects of social networks; network games; cost-sharing algorithms and analysis; computing with incentives; algorithmic mechanism design; computational social choice; decision theory, and pricing; auction algorithms and analysis; economic aspects of distributed computing; internet economics and computational advertising.

• adwords
• economic theory
• network design
• potential function
• pure nash equilibrium

• Department de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, ALBCOM, Barcelona,, Spain

  Maria Serna

Policies and ethics