13. – 18. Juli 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)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team




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


Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.