Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 03291

Algorithmic Game Theory and the Internet

( Jul 13 – Jul 18, 2003 )

Please use the following short url to reference this page:



The seminar was devoted to the most important recent developments in the area of the Algorithmic Game Theory connected to the problems arising from, and motivated by, the Internet and other decentralized computer networks. The most defining characteristic of the Internet is that it was not designed by a single central entity, but emerged from the complex interaction of many economic agents, such as network operators, service providers, designers, users, etc., in varying degrees of collaboration and competition. The major questions that arise in that context are in analysis of its performance and in evaluation of its long term equilibria. They include all sorts of completely new questions that lie on the interface of the fields of networks, algorithms and game theory.

The focus of the workshop was on the following specific topics:

  • design of efficient algorithms for game theoretic problems connected to the Internet,
  • inherent complexity of game theoretic problems,
  • resource allocation and stability,
  • Nash equilibria,
  • market equilibria,
  • mechanism design,
  • economic aspects of the Internet,
  • combinatorial auctions and
  • cost allocations, network design.

Some new broadly applicable techniques have emerged recently in the above areas and the workshop has addressed those developments and new fundamental insights. The workshop has also addressed and formulated important open problems of the area and identified most challenging research directions for the future.

The 47 participants of the workshop came from various research areas connected to the main topic of the workshop. The 31 lectures delivered at the workshop covered wide body of recent research in the area. In addition, a special evening session was devoted to presentation of open problems.

The meeting was held in a very pleasant and stimulating atmosphere. Thanks to everyone who made it a very interesting and enjoyable event!


Monday, July 14th, 2003

09:00 - 09:10 Opening
Chair: Marek Karpinski
9:10 - 9:40 Nikhil R. Devanur (Georgia Institute of Technology)
Market Equilibrium: Algorithms for the Linear Case
9:40 - 10:10 Vijay Vazirani (Georgia Institute of Technology)
Market Equilibrium when Buyers have Spending Constraints
10:10 - 10:40 Steven Low (CalTech - Pasadena)
Duality and Stability Models of Internet Congestion Control
Chair: Vijay Vazirani
11:00 - 11:30 Daniel Lehmann (University of Jerusalem)
Equilibria in Exchange Economies
11:30 - 12:00 Rudolf Müller (Maastricht University)
On the Complexity of Auctions
Chair: Daniel Lehmann
15:00 - 15:30 Yoav Shoham (Stanford)
On the non-comparable paranoias of game theory and cryptography
15:30 - 16:00 Subhash Suri (University of California at Santa Barbara)
Nash Equilibrium Load Balancing
Chair: Mark Jerrum
16:30 - 17:00 Rahul Sami (Yale University)
Computation in a Distributed Information Market
17:00 - 17:30 Artur Czumaj (New Jersey Inst. of Technology)
Worst-Case Equilibria for Server Farms

Tuesday, July 15th, 2003

Chair: Martin Dyer
09:00 - 09:30 Christos Papadimitriou (Berkeley)
Nash Equilibria and Complexity
09:30 - 10:00 Milena Mihail (Georgia Institute of Technology)
Algorithmic Performance on Power Law Graphs
10:00 - 10:30 Elias Koutsoupias (University of California at Los Angeles)
Coordination Mechanisms
Chair: Michael Paterson
11:00 - 11:30 Rica Gonen (University of Jerusalem)
Incentive Compatible Multi-Unit Combinatorial Auctions
11:30 - 12:00 Piotr Krysta (MPI für Informatik)
Computing Equilibria for Congestion Games
Chair: Elias Koutsoupias
15:00 - 15:30 Jason Hartline
Profit Maximizing Envy-Free Auctions
15:30 - 16:00 Bernhard von Stengel (London School of Economics)
Hard-To-Solve Bimatrix Games
Chair: Leonard J. Schulman
16:30 - 17:00 Amitabh Sinha (CMU - Pittsburgh)
Min-max Payoffs of a Location Game
17:00 - 17:30 Aaron Archer (Cornell University)
Approximate Truthful Mechanisms fo a Combinatorial Auction

Wednesday July 16th, 2003

Chair: Noam Nisan
09:00 - 09:30 Eva Tardos (Cornell University)
Network Design Games
09:30 - 10:00 Amir Ronen (Technion - Haifa)
Optimal Auctions - A Theorectical Computer Science-based Approach
10:00 - 10:30 Tim Roughgarden (Cornell University)
Pricing Networks with Selfish Routing
Chair: Eva Tardos
11:30 - 12:00 Sven de Vries (TU München)
On Ascending Vickrey Auctions for Heterogeneous Objects
20:00 Evening Session
Chair: Vijay Vazirani

Thursday July 17th, 2003

Chair: Christos Papadimitriou
09:00 - 09:30 Noam Nisan (University of Jerusalem)
Characterization of truthful combinatorial auctions I :
Are there non-VCG mechanisms ?
09:30 - 10:00 Ahuva Mu'alem (University of Jerusalem)
Characterization of truthful combinatorial auctions II:
Truthfullnes, monotonicity, and IIA
10:00 - 10:30 Ron Lavi (University of Jerusalem)
Characterization of truthful combinatorial auctions III:
Proof of main theorem
Chair: Rica Gonen
11:00 - 11:30 Leonard J. Schulman (Caltech)
Router Congestion Control
11:30 - 12:00 Eric Friedman (Cornell University)
Fairness and Stability of Sharing Protocols for the Unlicensed Bands
Chair: Sven de Vries
15:00 - 15:30 Meir Bing (University of Jerusalem)
Representing Substitutes Valuation
15:30 - 16:00 Anupam Gupta (Carnegie Mellon University)
Approximation Algorithms via Cost Sharing

Friday July 18th, 2003

Chair: Miklos Santha
09:00 - 09:30 Michel de Rougemont (Universite Paris Sud)
Definable Strategies in Games
09:30 - 10:00 Petra Berenbrink (Simon Fraser University)
Utilitarian Resource Assignment

  • Aaron Archer (Cornell University, US)
  • Petra Berenbrink (Simon Fraser University - Burnaby, CA) [dblp]
  • Meir Bing (The Hebrew University of Jerusalem, IL)
  • Norbert Blum (Universität Bonn, DE)
  • Artur Czumaj (NJIT - Newark, US) [dblp]
  • Michel de Rougemont (Université Paris Sud, FR)
  • Sven de Vries (TU München, DE)
  • Nikhil Devanur Rangarajan (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Martin Dyer (University of Leeds, GB) [dblp]
  • Lisa K. Fleischer (IBM TJ Watson Research Center, US) [dblp]
  • Eric Friedman (Cornell University, US)
  • Rica Gonen (The Hebrew University of Jerusalem, IL)
  • Anupam Gupta (Carnegie Mellon University, US) [dblp]
  • Jason D. Hartline (Microsoft Corp. - Mountain View, US) [dblp]
  • Mathias Hauptmann (Universität Bonn, DE)
  • Mark R. Jerrum (University of Edinburgh, GB) [dblp]
  • Marek Karpinski (Universität Bonn, DE) [dblp]
  • Elias Koutsoupias (University of Athens, GR) [dblp]
  • Piotr Krysta (TU Dortmund, DE) [dblp]
  • Ron Lavi (Hebrew University - Jerusalem, IL) [dblp]
  • Daniel Lehmann (The Hebrew University of Jerusalem, IL) [dblp]
  • Steven Low (CalTech - Pasadena, US)
  • Milena Mihail (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Ahuva Mu'alem (Hebrew University - Jerusalem, IL)
  • Rudolf Müller (Maastricht University, NL) [dblp]
  • Yakov Nekrich (Universität Bonn, DE) [dblp]
  • Noam Nisan (The Hebrew University of Jerusalem, IL) [dblp]
  • Christos H. Papadimitriou (University of California - Berkeley, US) [dblp]
  • Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
  • Amir Ronen (Technion - Haifa, IL)
  • Tim Roughgarden (Stanford University, US) [dblp]
  • Rahul Sami (Yale University, US)
  • Miklos Santha (Université Paris Sud, FR) [dblp]
  • Leonard J. Schulman (Caltech - Pasadena, US) [dblp]
  • Yoav Shoham (Stanford University, US) [dblp]
  • Amitabh Sinha (Carnegie Mellon University, US)
  • Subhash Suri (University of California - Santa Barbara, US) [dblp]
  • Éva Tardos (Cornell University, US) [dblp]
  • Vijay V. Vazirani (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Berthold Vöcking (RWTH Aachen, DE) [dblp]
  • Bernhard von Stengel (London School of Economics, GB) [dblp]
  • Peter Wegner (Universität Bonn, DE)

  • Algorithmic Game Theory
  • Internet
  • Approximation Algorithms
  • Inherent Complexity
  • Resource Allocation
  • Stability
  • Nash Equilibria
  • Mechanism Design
  • Combinatorial Auctions
  • Cost Allocations
  • Cryptography
  • Congestion Fairness
  • Stability
  • Routing
  • Load Balancing
  • Network Design