GI-Dagstuhl-Seminar No. 04362:

Game-Theoretic Analyses of the Internet

Aug. 30 - Sep. 03, 2004, Schloß Dagstuhl

Organization: M. Bläser (ETH Zürich), P. Krysta, B. Vöcking (Univ. Dortmund), R. Reischuk (Univ. Lübeck)


The closing date for applications is March 31, 2004.

Notational conventions

About the seminar

The Internet is a platform for complex interaction between different entities like network operators, service providers, and users. Moreover, the network itself was not designed by a single person or instiution but emerged from the interaction of different entities. Different players compete with each other but also build coalitions. Todays rules and protocols for the interaction in the Internet assume to a large extend that the participants behave nicely and follow the protocols in a truthful manner in order to maximize the social benefit. The entities operating the Internet, however, are driven by economical interests, and many services that are free of costs today, like forwarding data packets, might not be for free in the future, since the incurred extra costs are not marginal. Under such conditions, selfishness may prevail, and it seems quite reasonable to assume that at least some entities rather try to manipulate and break the protocols for their own benefit.

The socio-economic aspects described above constitute an interesting challenge to derive and study new models for the Internet. In the past few years, this challenge has received a lot of attention among theoretical computer scientists. The applied tools and methods mostly come from Algorithm and Game Theory but more and more also from Micro Economics. An important field of research is the design of protocols (so-called mechanisms) that take the selfish behavior of the participants into account and "force" the participants to act truthfully. Other areas include the comparison of scenarios in which users act selfishly with globally optimal solutions. The goal of this seminar is to give a comprehensive overview of the most important results in the areas of selfish routing and mechanism design as well as to present other models, ideas and concepts from Game Theory and Micro Economics that might be relevant to studying the Internet.

Possible topics


The participants will be assigned a topic from the ones given above together with relevant literature on this topic and prepare an overview paper on the selected topic. During the seminar, this work is presented and discussed. It is planned to collect the papers in a seminar volume and publish it in an appropriate form.

The seminar is organized by

Time and Location

The seminar is organized as Dagstuhl-Seminar No. 04362, from August 30th to September 3rd, in the International Conference and Research Center for Computer Science at Schloss Dagstuhl. Dagstuhl lies about halfway between Saarbrücken and Trier. Registration fees will be 100 Euros, including accommodation and meals.

Application Modalities

No preliminary knowledge of the seminar topic is required. Participants are selected on the basis of a good general scientific qualification. Participants can apply by sending a short curriculum vitae and a letter of reference from a university professor.

Applications and questions should be sent by March 31st, 2004 to An application should contain a list of preferred areas (chosen from the list A,B,C,D above) ranked in order of preference, e.g., BCDA. The topics together with related literature will then be assigned by the organizing committee. The applicants will be notified about the decision of the organizing committee by the end of April, 2004.

About the GI/Dagstuhl research seminar series

Gesellschaft für Informatik (GI) (German Computer Society) has been organizing research seminars on current topics in computer science since 1997. They are primarily addressed to graduate students and recent PhDs that actively want to learn about new developments. Participants are selected on the basis of an application. The maximum number of participants is usually limited to 20. So far, there have been GI/Dagstuhl seminars on the following topics:


Schloss Dagstuhl Gesellschaft für Informatik
Piotr Krysta, October 10, 2003