Algorithmic Game Theory: First International Symposium, SAGT 2008, Paderborn, Germany, April 30 - May 2, 2008, Proceedings

Front Cover
Springer Science & Business Media, Apr 25, 2008 - Computers - 363 pages
ThisvolumecontainsthepaperspresentedattheFirstInternationalSymposium on Algorithmic Game Theory (SAGT 2008) held from April 30 to May 2 in Paderborn, Germany. The purpose of SAGT is to bring together researchers from computer science, economics and mathematics to present and discuss original research at the intersection of algorithms and game theory. It is intended to cover all important areas of algorithmic game theory, such as: solution concepts in game theory; game classes (e. g. , bimatrix, potential, Bayesian); exact and appro- mate computation of equilibria; convergence and learning in games; complexity classesingametheory;algorithmicaspectsof?xed-pointtheorems;mechanisms, incentives and coalitions; cost-sharing algorithms and analysis; computational aspects of market equilibria; computational problems in economics, ?nance, - cision theory and pricing; auction algorithms and analysis; price of anarchy and its relatives; representations of games and their complexity; economic aspects of distributed computing and the Internet; network formation on the Internet; congestion, routing and network design games; game-theoretic approaches to networking problems; Byzantine game theory. There were 60 submissions. Each submission was reviewed by three P- gramme Committee members. The committee decided to accept 28 papers. The programme also included three invited talks from outstanding researchers ChristosPapadimitriou,NobelMemorialPrizewinnerReinhardSeltenandPaul Spirakis. We would like to thank all the Programme Committee members and the external reviewers who assisted them in their work. The members of the Organizing Committee as well as the developer of the EasyChair conference system deserve our gratitude for their contributions throughout the preparations.
 

What people are saying - Write a review

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

Contents

The Influence of Link Restrictions on Random Selfish Routing
22
Convergence Time and Price of Anarchy
33
The Price of Anarchy on Uniformly Related Machines Revisited
46
Approximate Strong Equilibrium in Job Scheduling Games
58
Bertrand Competition in Networks
70
On the Approximability of Combinatorial Exchange Problems
83
WindowGames between TCP Flows
95
Price Variation in a Bipartite Exchange Network
109
Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity
206
The Price of Anarchy of a Network Creation Game with Exponential Payoff
218
A Hierarchical Model for Cooperative Games
230
Strategic Characterization of the Index of an Equilibrium
242
The Local and Global Price of Anarchy of Graphical Games
255
Approximate Nash Equilibria for Multiplayer Games
267
Subjective vs Objective Reality The Risk of Running Late
279
On the Hardness and Existence of QuasiStrict Equilibria
291

Fast Myopic and Concurrent
121
Frugal Routing on Wireless AdHoc Networks
133
Facets of the Fully Mixed Nash Equilibrium Conjecture
145
Sensitivity of Wardrop Equilibria
158
Prompt Mechanisms for Online Auctions
170
A Truthful Mechanism for Offline Ad Slot Scheduling
182
Alternatives to Truthfulness Are Hard to Recognize
194
The Price of Stochastic Anarchy
303
Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems
315
Is Shapley Cost Sharing Optimal?
327
Noncooperative Cost Sharing Games Via Subsidies
337
GroupStrategyproof Cost Sharing for Metric Fault Tolerant Facility Location
350
Author Index
362
Copyright

Other editions - View all

Common terms and phrases