Ebook: Algorithmic Game Theory: 5th International Symposium, SAGT 2012, Barcelona, Spain, October 22-23, 2012. Proceedings

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.

---

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.

---

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.
Content:
Front Matter....Pages -
A Classification of Weakly Acyclic Games....Pages 1-12
Selfishness Level of Strategic Games....Pages 13-24
Mechanisms for Scheduling with Single-Bit Private Values....Pages 25-36
The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games....Pages 37-48
An Optimal Bound to Access the Core in TU-Games....Pages 49-60
Convergence of Ordered Improvement Paths in Generalized Congestion Games....Pages 61-71
Basic Network Creation Games with Communication Interests....Pages 72-83
Common Knowledge and State-Dependent Equilibria....Pages 84-95
Approximating the Minmax Value of Three-Player Games within a Constant is as Hard as Detecting Planted Cliques....Pages 96-107
Approximate Well-Supported Nash Equilibria Below Two-Thirds....Pages 108-119
Mechanisms and Impossibilities for Truthful, Envy-Free Allocations....Pages 120-131
Capacitated Network Design Games....Pages 132-143
Decentralized Dynamics for Finite Opinion Games....Pages 144-155
On the Hardness of Network Design for Bottleneck Routing Games....Pages 156-167
Ad Auctions with Data....Pages 168-179
Commodity Auctions and Frugality Ratios....Pages 180-191
On the Communication Complexity of Approximate Nash Equilibria....Pages 192-203
Congestion Games with Capacitated Resources....Pages 204-215
Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances....Pages 216-226
Uniform Price Auctions: Equilibria and Efficiency....Pages 227-238
Minimizing Expectation Plus Variance....Pages 239-250
A Theoretical Examination of Practical Game Playing: Lookahead Search....Pages 251-262
Back Matter....Pages -

---

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.
Content:
Front Matter....Pages -
A Classification of Weakly Acyclic Games....Pages 1-12
Selfishness Level of Strategic Games....Pages 13-24
Mechanisms for Scheduling with Single-Bit Private Values....Pages 25-36
The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games....Pages 37-48
An Optimal Bound to Access the Core in TU-Games....Pages 49-60
Convergence of Ordered Improvement Paths in Generalized Congestion Games....Pages 61-71
Basic Network Creation Games with Communication Interests....Pages 72-83
Common Knowledge and State-Dependent Equilibria....Pages 84-95
Approximating the Minmax Value of Three-Player Games within a Constant is as Hard as Detecting Planted Cliques....Pages 96-107
Approximate Well-Supported Nash Equilibria Below Two-Thirds....Pages 108-119
Mechanisms and Impossibilities for Truthful, Envy-Free Allocations....Pages 120-131
Capacitated Network Design Games....Pages 132-143
Decentralized Dynamics for Finite Opinion Games....Pages 144-155
On the Hardness of Network Design for Bottleneck Routing Games....Pages 156-167
Ad Auctions with Data....Pages 168-179
Commodity Auctions and Frugality Ratios....Pages 180-191
On the Communication Complexity of Approximate Nash Equilibria....Pages 192-203
Congestion Games with Capacitated Resources....Pages 204-215
Network Bargaining: Using Approximate Blocking Sets to Stabilize Unstable Instances....Pages 216-226
Uniform Price Auctions: Equilibria and Efficiency....Pages 227-238
Minimizing Expectation Plus Variance....Pages 239-250
A Theoretical Examination of Practical Game Playing: Lookahead Search....Pages 251-262
Back Matter....Pages -
....