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

by Kontogiannis, Spyros; Koutsoupias, Elias; Spirakis, Paul G.

• ISBN13: 9783642161698
• ISBN10: 3642161693
• Format: Paperback
• Copyright: 2010-11-15
• Publisher: Springer-Verlag New York Inc

Summary

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

When the Players are not Expectation Maximizers (Invited Talk)	p. 1
How Do You Like Your Equilibrium Selection Problems? Hard, or Very Hard? (Invited Talk)	p. 15
A Simplex-Like Algorithm for Fisher Markets	p. 18
Nash Equilibria in Fisher Market	p. 30
Partition Equilibrium Always Exists in Resource Selection Games	p. 42
Mixing Time and Stationary Expected Social Welfare of Logit Dynamics	p. 54
Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games	p. 66
On Nash-Equilibria of Approximation-Stable Games	p. 78
Improved Lower Bounds on the Price of Stability of Undirected Network Design Games	p. 90
On the Rate of Convergence of Fictitious Play	p. 102
On Learning Algorithms for Nash Equilibria	p. 114
On the Structure of Weakly Acyclic Games	p. 126
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium	p. 138
Responsive Lotteries	p. 150
On the Existence of Optimal Taxes for Network Congestion Games with Heterogeneous Users	p. 162
Computing Stable Outcomes in Hedonic Games	p. 174
A Perfect Price Discrimination Market Model with Production, and a (Rational) Convex Program for It	p. 186
The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements	p. 198
Complexity of Safe Strategic Voting	p. 210
Bottleneck Congestion Games with Logarithmic Price of Anarchy	p. 222
Single-Parameter Combinatorial Auctions with Partially Public Valuations	p. 234
On the Efficiency of Markets with Two-Sided Proportional Allocation Mechanisms	p. 246
Braess's Paradox for Flows over Time	p. 262
The Price of Anarchy in Network Creation Games Is (Mostly) Constant	p. 276
Truthful Fair Division	p. 288
No Regret Learning in Oligopolies: Cournot vs. Bertrand	p. 300
On the Complexity of Pareto-optimal Nash and Strong Equilibria	p. 312
2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties	p. 323
On the Inefficiency of Equilibria in Linear Bottleneck Congestion Games	p. 335
Minimal Subsidies in Expense Sharing Games	p. 347
Author Index	p. 359
Table of Contents provided by Ingram. All Rights Reserved.