Algorithmic Game Theory: Third International Symposium, SAGT 2010, Athens, Greece, October 18-20, 2010. Proceedings

Amos Fiat, Christos Papadimitriou (auth.), Spyros Kontogiannis, Elias Koutsoupias, Paul G. Spirakis (eds.)3540793089, 9783540793083

This book constitutes the refereed proceedings of the Third International Symposium on Algorithmic Game Theory, SAGT 2010, held in Athens, Greece, in October 2010. The 28 revised full papers presented together with 2 invited lectures were carefully reviewed and selected from 61 submissions. The papers are intended to cover all important areas such as solution concepts, game classes, computation of equilibria and market equilibria, convergence and learning in games, complexity classes in game theory, algorithmic aspects of fixed-point theorems, mechanisms, incentives and coalitions, cost-sharing algorithms, computational problems in economics, finance, decision theory and pricing, computational social choice, auction algorithms, price of anarchy and its relatives, representations of games and their complexity, network formation on the internet, congestion, routing and network design and formation games, game-theoretic approaches to networking problems, and computational social choice.

---

Table of contents :
Front Matter….Pages –
When the Players Are Not Expectation Maximizers….Pages 1-14
How Do You Like Your Equilibrium Selection Problems? Hard, or Very Hard?….Pages 15-17
A Simplex-Like Algorithm for Fisher Markets….Pages 18-29
Nash Equilibria in Fisher Market….Pages 30-41
Partition Equilibrium Always Exists in Resource Selection Games….Pages 42-53
Mixing Time and Stationary Expected Social Welfare of Logit Dynamics….Pages 54-65
Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games….Pages 66-77
On Nash-Equilibria of Approximation-Stable Games….Pages 78-89
Improved Lower Bounds on the Price of Stability of Undirected Network Design Games….Pages 90-101
On the Rate of Convergence of Fictitious Play….Pages 102-113
On Learning Algorithms for Nash Equilibria….Pages 114-125
On the Structure of Weakly Acyclic Games….Pages 126-137
A Direct Reduction from k -Player to 2-Player Approximate Nash Equilibrium….Pages 138-149
Responsive Lotteries….Pages 150-161
On the Existence of Optimal Taxes for Network Congestion Games with Heterogeneous Users….Pages 162-173
Computing Stable Outcomes in Hedonic Games….Pages 174-185
A Perfect Price Discrimination Market Model with Production, and a (Rational) Convex Program for It….Pages 186-197
The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements….Pages 198-209
Complexity of Safe Strategic Voting….Pages 210-221
Bottleneck Congestion Games with Logarithmic Price of Anarchy….Pages 222-233
Single-Parameter Combinatorial Auctions with Partially Public Valuations….Pages 234-245
On the Efficiency of Markets with Two-Sided Proportional Allocation Mechanisms….Pages 246-261
Braess’s Paradox for Flows over Time….Pages 262-275
The Price of Anarchy in Network Creation Games Is (Mostly) Constant….Pages 276-287
Truthful Fair Division….Pages 288-299
No Regret Learning in Oligopolies: Cournot vs. Bertrand….Pages 300-311
On the Complexity of Pareto-optimal Nash and Strong Equilibria….Pages 312-322
2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties….Pages 323-334
On the Inefficiency of Equilibria in Linear Bottleneck Congestion Games….Pages 335-346
Minimal Subsidies in Expense Sharing Games….Pages 347-358
Back Matter….Pages –