July 13 – 18 , 2003, Dagstuhl Seminar 03291

Algorithmic Game Theory and the Internet


Marek Karpinski (Universität Bonn, DE)
Christos H. Papadimitriou (University of California – Berkeley, US)
Vijay V. Vazirani (Georgia Institute of Technology – Atlanta, US)

For support, please contact

Dagstuhl Service Team


List of Participants


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


  • 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


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.