Algorithmic Game Theory
Algorithmic Game Theory: This volume contains the papers presented at the Second International Sym- sium on Algorithmic Game Theory (SAGT ), which was held on October , 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. Approximately55submissionstoSAGT 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 . The program of SAGT 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.