Algorithmic Game Theory

1. Front Matter

   PDF

2. Matching Theory

   1. Social Welfare in One-Sided Matchings: Random Priority and Beyond

      • Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Jie Zhang

      Pages 1-12

   2. Efficiency of Truthful and Symmetric Mechanisms in One-Sided Matching

      • Marek Adamczyk, Piotr Sankowski, Qiang Zhang

      Pages 13-24

   3. Stable Marriage with General Preferences

      • Linda Farczadi, Konstantinos Georgiou, Jochen Könemann

      Pages 25-36

3. Game Dynamics

   1. The Convergence Time for Selfish Bin Packing

      • György Dósa, Leah Epstein

      Pages 37-48

   2. Short Sequences of Improvement Moves Lead to Approximate Equilibria in Constraint Satisfaction Games

      • Ioannis Caragiannis, Angelo Fanelli, Nick Gravin

      Pages 49-60

   3. Paths to Stable Allocations

      • Ágnes Cseh, Martin Skutella

      Pages 61-73

   4. Self-stabilizing Uncoupled Dynamics

      • Aaron D. Jaggard, Neil Lutz, Michael Schapira, Rebecca N. Wright

      Pages 74-85

4. Games of Coordination

   1. Profit Sharing with Thresholds and Non-monotone Player Utilities

      • Elliot Anshelevich, John Postl

      Pages 86-97

   2. Shared Resource Management via Reward Schemes

      • Shahar Dobzinski, Amir Ronen

      Pages 98-109

   3. Budget-Restricted Utility Games with Ordered Strategic Decisions

      • Maximilian Drees, Sören Riechers, Alexander Skopalik

      Pages 110-121

5. Networks/Social Choice

   1. Influence Maximization in Switching-Selection Threshold Models

      • Dimitris Fotakis, Thodoris Lykouris, Evangelos Markakis, Svetlana Obraztsova

      Pages 122-133

   2. Network Cost-Sharing without Anonymity

      • Tim Roughgarden, Okke Schrijvers

      Pages 134-145

   3. Recognizing 1-Euclidean Preferences: An Alternative Approach

      • Edith Elkind, Piotr Faliszewski

      Pages 146-157

6. Markets and Auctions

   1. Clearing Markets via Bundles

      • Michal Feldman, Brendan Lucier

      Pages 158-169

   2. Walrasian Equilibrium with Few Buyers

      • Reshef Meir, Moshe Tennenholtz

      Pages 170-181

   3. Multimarket Oligopolies with Restricted Market Access

      • Tobias Harks, Max Klimm

      Pages 182-193

   4. Value of Targeting

      • Kshipra Bhawalkar, Patrick Hummel, Sergei Vassilvitskii

      Pages 194-205

7. Price of Anarchy

   1. Welfare Guarantees for Proportional Allocations

      • Ioannis Caragiannis, Alexandros A. Voudouris

      Pages 206-217

   2. Strong Price of Anarchy, Utility Games and Coalitional Dynamics

      • Yoram Bachrach, Vasilis Syrgkanis, Éva Tardos, Milan Vojnović

      Pages 218-230

This book constitutes the refereed proceedings of the 7th International Symposium on Algorithmic Game Theory, SAGT 2014, held in Haifa, Israel, in October 2014. The 24 full papers and 5 short papers presented were carefully reviewed and selected from 65 submissions. They cover various important aspects of algorithmic game theory, such as matching theory, game dynamics, games of coordination, networks and social choice, markets and auctions, price of anarchy, computational aspects of games, mechanism design and auctions.

• algorithmic mechanism design
• auctions
• better response strategy
• combinatorial auctions
• complexity of equilibria
• constraint satisfaction
• correlated market
• game dynamics
• greedy algorithms
• matroid optimization
• nash equilibria
• stabl matching
• support constraints

• Faculty of Industrial Engineering and Management, Technion Israel Institute of Technology, Israel

  Ron Lavi

Policies and ethics