Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009, Proceedings (Google eBook)

Front Cover
Marios Mavronicolas, Maria Papadoupoulou, Vicky G. Papadopoulou
Springer Science & Business Media, Sep 23, 2009 - Computers - 359 pages
0 Reviews
This volume contains the papers presented at the Second International Sym- sium on Algorithmic Game Theory (SAGT 2009), which was held on October 1820, 2009, in Paphos, Cyprus. This event followed the ?rst, very successful SAGT symposium, which took place in Paderborn, Germany, last year. The purpose of SAGT is to bring together researchers from computer s- ence, economics and mathematics to present and discuss originalresearchat the intersection of algorithms and game theory. It has been intended to cover all important areas such as solution concepts, game classes,computation of equil- riaandmarketequilibria,algorithmicmechanismdesign, automatedmechanism design,convergenceandlearningingames,complexityclassesingametheory,- gorithmicaspectsof?xed-pointtheorems,mechanisms,incentivesandcoalitions, cost-sharing algorithms, computational problems in economics, ?nance, decision theory and pricing, computational social choice, auction algorithms, price of - archyand its relatives, representationsof games and their complexity, economic aspects of distributed computing and the internet, congestion, routing and n- work design and formation games and game-theoretic approaches to networking problems. Approximately55submissionstoSAGT2009 werereceived.Eachsubmission was reviewed by at least three Program Committee members. The Program Committee decided to accept 29 papers. Out of these, a small number will be invited to a Special Issue of the Theory of Computing Systems journal with selected papers from SAGT 2009. The program of SAGT 2009 featured three invited talks from three outstanding researchers in algorithmic game theory: Elias Koutsoupias, Dov Monderer and Mihalis Yannakakis. We are very grateful toElias,DovandMihalisforjoiningusinPaphosandfortheirexcellentlectures.
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Monotonicity in Mechanism Design
1
Computational Aspects of Equilibria
2
A Modular Approach to Roberts Theorem
14
Characterizing Incentive Compatibility for Convex Valuations
24
Truthful Mechanisms for Selfish Routing and TwoParameter Agents
36
Partition Equilibrium
48
ManipulationOptimal Mechanisms
60
On the Planners Loss Due to Lack of Information in Bayesian Mechanism Design
72
Nash Dynamics in Constant Player and Bounded Jump Congestion Games
196
Price of Stability in Survivable Network Design
208
Games with CongestionAverse Utilities
220
A New Derandomization of Auctions
233
The Computational Complexity of Weak Saddles
238
Learning and Approximating the Optimal Strategy to Commit To
250
Doing Good with Spam Is Hard
263
On ProfitMaximizing Pricing for the Highway and Tollbooth Problems
275

Sequential Pivotal Mechanisms for Public Project Problems
85
Characterizing the Existence of Potential Functions in Weighted Congestion Games
97
FreeRiding and FreeLabor in Combinatorial Agency
109
The Cost of Stability in Coalitional Games
122
Nonclairvoyant Scheduling Games
135
Lower and Upper Bounds
147
Creating Better Matchings
159
Equilibria in Dynamic Selfish Routing
171
Stochastic Stability in Internet Router Congestion Games
183
On the Complexity of Iterated Weak Dominance in ConstantSum Games
287
Swap Bribery
299
Performances of OneRound Walks in Linear Congestion Games
311
Nash Equilibria and the Price of Anarchy for Flows over Time
323
Bayesian Auctions with Friends and Foes
335
On Equilibria for ADM Minimization Games
347
Author Index
359
Copyright

Common terms and phrases