Ebook: Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009. Proceedings

This book constitutes the refereed proceedings of the Second International Symposium on Algorithmic Game Theory, SAGT 2009, held in Paphos, Cyprus, in October 2009.

The 29 revised full papes presented together with 3 invited lectures were carefully reviewed and selected from 55 submissions. The papers are intended to cover all important areas such as solution concepts, game classes, computation of equilibria and market equilibria, algorithmic mechanism design, automated mechanism design, 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, economic aspects of distributed computing and the internet, congestion, routing and network design and formation games and game-theoretic approaches to networking problems.

---

This book constitutes the refereed proceedings of the Second International Symposium on Algorithmic Game Theory, SAGT 2009, held in Paphos, Cyprus, in October 2009.

The 29 revised full papes presented together with 3 invited lectures were carefully reviewed and selected from 55 submissions. The papers are intended to cover all important areas such as solution concepts, game classes, computation of equilibria and market equilibria, algorithmic mechanism design, automated mechanism design, 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, economic aspects of distributed computing and the internet, congestion, routing and network design and formation games and game-theoretic approaches to networking problems.

---

This book constitutes the refereed proceedings of the Second International Symposium on Algorithmic Game Theory, SAGT 2009, held in Paphos, Cyprus, in October 2009.

The 29 revised full papes presented together with 3 invited lectures were carefully reviewed and selected from 55 submissions. The papers are intended to cover all important areas such as solution concepts, game classes, computation of equilibria and market equilibria, algorithmic mechanism design, automated mechanism design, 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, economic aspects of distributed computing and the internet, congestion, routing and network design and formation games and game-theoretic approaches to networking problems.

Content:
Front Matter....Pages -
Monotonicity in Mechanism Design....Pages 1-1
Computational Aspects of Equilibria....Pages 2-13
A Modular Approach to Roberts’ Theorem....Pages 14-23
Characterizing Incentive Compatibility for Convex Valuations....Pages 24-35
Truthful Mechanisms for Selfish Routing and Two-Parameter Agents....Pages 36-47
Partition Equilibrium....Pages 48-59
Better with Byzantine: Manipulation-Optimal Mechanisms....Pages 60-71
On the Planner’s Loss Due to Lack of Information in Bayesian Mechanism Design....Pages 72-84
Sequential Pivotal Mechanisms for Public Project Problems....Pages 85-96
Characterizing the Existence of Potential Functions in Weighted Congestion Games....Pages 97-108
Free-Riding and Free-Labor in Combinatorial Agency....Pages 109-121
The Cost of Stability in Coalitional Games....Pages 122-134
Non-clairvoyant Scheduling Games....Pages 135-146
The Balloon Popping Problem Revisited: Lower and Upper Bounds....Pages 147-158
Anarchy, Stability, and Utopia: Creating Better Matchings....Pages 159-170
Equilibria in Dynamic Selfish Routing....Pages 171-182
Stochastic Stability in Internet Router Congestion Games....Pages 183-195
Nash Dynamics in Constant Player and Bounded Jump Congestion Games....Pages 196-207
Price of Stability in Survivable Network Design....Pages 208-219
Games with Congestion-Averse Utilities....Pages 220-232
A New Derandomization of Auctions....Pages 233-237
The Computational Complexity of Weak Saddles....Pages 238-249
Learning and Approximating the Optimal Strategy to Commit To....Pages 250-262
Doing Good with Spam Is Hard....Pages 263-274
On Profit-Maximizing Pricing for the Highway and Tollbooth Problems....Pages 275-286
On the Complexity of Iterated Weak Dominance in Constant-Sum Games....Pages 287-298
Swap Bribery....Pages 299-310
Performances of One-Round Walks in Linear Congestion Games....Pages 311-322
Nash Equilibria and the Price of Anarchy for Flows over Time....Pages 323-334
Bayesian Auctions with Friends and Foes....Pages 335-346
On Equilibria for ADM Minimization Games....Pages 347-358
Back Matter....Pages -

---

This book constitutes the refereed proceedings of the Second International Symposium on Algorithmic Game Theory, SAGT 2009, held in Paphos, Cyprus, in October 2009.

The 29 revised full papes presented together with 3 invited lectures were carefully reviewed and selected from 55 submissions. The papers are intended to cover all important areas such as solution concepts, game classes, computation of equilibria and market equilibria, algorithmic mechanism design, automated mechanism design, 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, economic aspects of distributed computing and the internet, congestion, routing and network design and formation games and game-theoretic approaches to networking problems.

Content:
Front Matter....Pages -
Monotonicity in Mechanism Design....Pages 1-1
Computational Aspects of Equilibria....Pages 2-13
A Modular Approach to Roberts’ Theorem....Pages 14-23
Characterizing Incentive Compatibility for Convex Valuations....Pages 24-35
Truthful Mechanisms for Selfish Routing and Two-Parameter Agents....Pages 36-47
Partition Equilibrium....Pages 48-59
Better with Byzantine: Manipulation-Optimal Mechanisms....Pages 60-71
On the Planner’s Loss Due to Lack of Information in Bayesian Mechanism Design....Pages 72-84
Sequential Pivotal Mechanisms for Public Project Problems....Pages 85-96
Characterizing the Existence of Potential Functions in Weighted Congestion Games....Pages 97-108
Free-Riding and Free-Labor in Combinatorial Agency....Pages 109-121
The Cost of Stability in Coalitional Games....Pages 122-134
Non-clairvoyant Scheduling Games....Pages 135-146
The Balloon Popping Problem Revisited: Lower and Upper Bounds....Pages 147-158
Anarchy, Stability, and Utopia: Creating Better Matchings....Pages 159-170
Equilibria in Dynamic Selfish Routing....Pages 171-182
Stochastic Stability in Internet Router Congestion Games....Pages 183-195
Nash Dynamics in Constant Player and Bounded Jump Congestion Games....Pages 196-207
Price of Stability in Survivable Network Design....Pages 208-219
Games with Congestion-Averse Utilities....Pages 220-232
A New Derandomization of Auctions....Pages 233-237
The Computational Complexity of Weak Saddles....Pages 238-249
Learning and Approximating the Optimal Strategy to Commit To....Pages 250-262
Doing Good with Spam Is Hard....Pages 263-274
On Profit-Maximizing Pricing for the Highway and Tollbooth Problems....Pages 275-286
On the Complexity of Iterated Weak Dominance in Constant-Sum Games....Pages 287-298
Swap Bribery....Pages 299-310
Performances of One-Round Walks in Linear Congestion Games....Pages 311-322
Nash Equilibria and the Price of Anarchy for Flows over Time....Pages 323-334
Bayesian Auctions with Friends and Foes....Pages 335-346
On Equilibria for ADM Minimization Games....Pages 347-358
Back Matter....Pages -
....