Algorithmic Game Theory

1. Front Matter

   PDF

2. Voting

   1. The Complexity of Fully Proportional Representation for Single-Crossing Electorates

      • Piotr Skowron, Lan Yu, Piotr Faliszewski, Edith Elkind

      Pages 1-12

   2. New Results on Equilibria in Strategic Candidacy

      • Jérome Lang, Nicolas Maudet, Maria Polukarov

      Pages 13-25

   3. Plurality Voting with Truth-Biased Agents

      • Svetlana Obraztsova, Evangelos Markakis, David R. M. Thompson

      Pages 26-37

   4. Reliability Weighted Voting Games

      • Yoram Bachrach, Nisarg Shah

      Pages 38-49

3. Price of Anarchy

   1. The Power of Mediation in an Extended El Farol Game

      • Dieter Mitsche, George Saad, Jared Saia

      Pages 50-61

   2. Friend of My Friend: Network Formation with Two-Hop Benefit

      • Elliot Anshelevich, Onkar Bhardwaj, Michael Usher

      Pages 62-73

   3. Load Rebalancing Games in Dynamic Systems with Migration Costs

      • Sofia Belikovetsky, Tami Tamir

      Pages 74-85

4. Congestion Games

   1. Stochastic Congestion Games with Risk-Averse Players

      • Haris Angelidakis, Dimitris Fotakis, Thanasis Lianeas

      Pages 86-97

   2. Congestion Games with Player-Specific Costs Revisited

      • Martin Gairing, Max Klimm

      Pages 98-109

   3. Using Reputation Instead of Tolls in Repeated Selfish Routing with Incomplete Information

      • Kun Hu, Jingjing Huang, George Karakostas

      Pages 110-121

5. Computational Aspects

   1. Anti-coordination Games and Stable Graph Colorings

      • Jeremy Kun, Brian Powers, Lev Reyzin

      Pages 122-133

   2. Approximating Multi Commodity Network Design on Graphs of Bounded Pathwidth and Bounded Degree

      • Kord Eickmeyer, Ken-ichi Kawarabayashi

      Pages 134-145

6. Alternative Solution Concepts

   1. Cooperative Equilibria in Iterated Social Dilemmas

      • Valerio Capraro, Matteo Venanzi, Maria Polukarov, Nicholas R. Jennings

      Pages 146-158

   2. Symmetries of Quasi-Values

      • Ales A. Kubena, Peter Franek

      Pages 159-170

   3. Dividing Connected Chores Fairly

      • Sandy Heydrich, Rob van Stee

      Pages 171-182

   4. On Popular Random Assignments

      • Haris Aziz, Felix Brandt, Paul Stursberg

      Pages 183-194

7. Social Networks

   1. Scheduling a Cascade with Opposing Influences

      • MohammadTaghi Hajiaghayi, Hamid Mahini, Anshul Sawant

      Pages 195-206

   2. Designing Budget-Balanced Best-Response Mechanisms for Network Coordination Games

      • Bruno Escoffier, Diodato Ferraioli, Laurent Gourvès, Stefano Moretti

      Pages 207-218

   3. Inefficiency of Games with Social Context

      • Aris Anagnostopoulos, Luca Becchetti, Bart de Keijzer, Guido Schäfer

      Pages 219-230

This book constitutes the proceedings of the 6th International Symposium on Algorithmic Game Theory, SAGT 2013, held in Aachen, Germany, in October 2013. The 25 papers presented in this volume were carefully reviewed and selected from 65 submissions. They cover various important aspects of algorithmic game theory, such as solution concepts in game theory, efficiency of equilibria and the price of anarchy, computational aspects of equilibria and game theoretical measures, repeated games and convergence of dynamics, evolution and learning in games, coordination and collective action, network games and graph-theoretic aspects of social networks, voting and social choice, as well as algorithmic mechanism design.

• advertisement auction
• influence maximization
• nash equilibria
• network robustness
• weighted voting game

• Department of Computer Science, RWTH Aachen University, Aachen, Germany

  Berthold Vöcking

Policies and ethics