## Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009, ProceedingsThis volume contains the papers presented at the Second International Sym- sium on Algorithmic Game Theory (SAGT 2009), which was held on October 18-20, 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 |

359 | |

### Other editions - View all

### Common terms and phrases

action aﬃne agents algorithm allocation approximation arcs assignment assume best response bidders coalition structure coalitional game consider cost functions decision problem deﬁned Deﬁnition denote deviation diﬀerent dominance dynamic edge exists FIFO ﬁnd ﬁnite ﬁrst ﬁxed point ﬂow game G game theory given graph Heidelberg incentive compatible Lemma linear linear program LNCS machine maximizing mixed strategy monotonicity Nash equilibrium Nash ﬂow node NP-complete NP-hard number of players one-round walk outcome paper path payment payoﬀ polynomial potential game price of anarchy price of stability problem Proc proﬁt proﬁtable proof prove pure Nash pure strategy random router routing games Sandholm satisﬁes selﬁsh routing sequence sequential Speciﬁcally stable matchings Stackelberg static ﬂow stochastic games strategy proﬁle subset swap bribery Theorem traﬃc truthful mechanism utility valuations vector voting weak saddle weighted congestion games WVGs