Algorithmic Game Theory - Extended Description

Research group: Algorithms, Combinatorics and Optimization (PNA1)

Research group: Algorithms, Combinatorics and Optimization (PNA1)

Many real-world applications are complex and distributed in nature and involve a multitude of interacting decision makers that attempt to achieve their own goals. A typical example are network applications arising in large-scale distributed information and communication systems such as the Internet. Other examples deal with problems concerned with traffic, transportation, logistics, auctions, etc.

In this research project, we study various aspects of such applications. Our goal is to gain a fundamental understanding of the implications of strategic interaction with a particular focus on computational and algorithmic issues. Our studies are interdisciplinary in flavor in that they combine methodologies and techniques from operations research, combinatorial optimization, complexity theory, logic, game theory and social choice theory.

Focal research points of the project are:

  1. Mechanism design
    • socially optimal mechanisms
    • cost sharing mechanisms
  2. Study of equilibria
    • equilibrium computation
    • inefficiency of equilibria
    • coordination mechanisms
  3. Reasoning in strategic games
    • strategy elimination procedures & interactive epistemology
    • altruistic player behavior
  4. Social networks

The group is involved in various national and international activities to advance the field of algorithmic game theory. We highlight a few activities below.

Members

Coordinators of this project
Krzysztof Apt and Guido Schäfer

Other members
Bart de Keijzer, Floor Sietsma, Sunil Simon

Former members

  • Amy Greenwald (01-01-2011 till 31-07-2011)
  • Vincent Conitzer (15-12-2010 till 15-05-2011)
  • Orestis Telelis (01-10-2009 till 30-06-2010)
  • Po-An Chen (CWI internship, summer 2010)
  • Arantza Estévez-Fernández (01-10-2006 till 31-08-2007)
  • Florian Horn (01-11-2008 till 31-08-2009)
  • Nathanaël Fijalkow (internship, summer 2009)
  • Nicole Immorlica (01-09-2007 till 31-08-2008)
  • Vangelis Markakis (01-01-2007 till 31-07-2008)
  • Renato Gomes (internship, summer 2008)
  • Georgios Piliouras (CWI internship, summer 2008)
  • Mahyar Salek (CWI internship, summer 2009) 
  • Andreas Witzel (01-05-2006 till 31-07-2009)
  • Dominik Wojtczak (01-01-2009 till 31-12-2009)
  • Jonathan Zvesper (01/01/2007 till 31-08-2009)

Below we give a short exposition of the research activities of PNA1 in algorithmic game theory.

1.  Mechanism design

The following quotation is a brilliant explanation of what mechanism design is about. It was published in The Economist on October 18, 2007 (Article Intelligent design) after it had been announced that three researchers got the Nobel Prize in Economic Sciences in 2007 for their work on mechanism design.

Mechanism design deals with the problem of "how to arrange our economic interactions so that, when everyone behaves in a self-interested manner, the result is something we all like."

Research at CWI focusses on different aspects of mechanism design.

Socially optimal mechanisms

In general, the proposed solutions require imposition of taxes, which leads to a lower social welfare (aggregated wealth). Research at CWI focusses on a study of various ways of minimizing taxes or on proving that this is not possible. In particular, we characterized auctions with unit demand that lead to the largest social welfare and showed that in the classical 'public project problem' the Vickrey-Clark-Groves (VCG) mechanism is socially optimal. Also, we proposed for both domains sequential mechanisms that lead to a higher social welfare.

Selected publications: [1] [2] [3].

Cost sharing mechanisms

Consider a situation in which several parties are interested in sharing the cost of a jointly utilized resource (or service). For example, companies might be interested in sharing the maintenance cost of a common network infrastructure, research institutes may want to share the cost of a super-computer to perform high-performance tasks, etc. How should one distribute the cost of the resource among the participating parties? This is the fundamental question that lies at the core of the studies on the design of cost sharing mechanisms. The goal is to design efficient mechanisms that ensure that it is in every participants' self-interest to truthfully reveal his valuation for using the resource.

We develop cost sharing mechanisms for several network design and scheduling problems. Our studies incorporate various issues of practical relevance such as cooperation among players, offline vs. online settings, realization of approximate budget balance and social cost efficiency, etc.

Selected publications: [4] [5] [6].

2.  Study of Equilibria

Equilibrium computation

The Nash equilibrium concept is the predominant solution concept for the prediction of outcomes of rational behavior in strategic games. In his seminal work, Nash (1950) proved that Nash equilibria (in mixed strategies) always exist in finite strategic games. It has been a major open problem for several decades whether a Nash equilibrium can be computed efficiently. This question has recently been settled by Chen, Deng and Teng (2009) by showing that even in two-player games the problem of computing a Nash equilibrium is PPAD-complete and thus unlikely to be solvable in polynomial time. In light of this negative result, researchers have tried to develop efficient algorithms for the computation of approximate Nash equilibria.

Researchers at CWI contributes to this topic in two-player games, repeated games and stochastic games.

Selected publications: [7] [8] [9].

Inefficiency of equilibria & Coordination mechanisms

It is well known that equilibria can be inefficient in the sense that they are suboptimal with respect to a socially desirable objective function. The Braess's paradox is a popular example illustrating this phenomenon in the context of a traffic application. It shows that selfish route choices of players can lead to equilibrium outcomes that are inferior (e.g., in terms of the total average travel time) to optimal routing schemes.

This observation triggers (at least) two natural questions:

  1. Can one quantify the inefficiency caused by selfish behavior?
  2. What are effective regulation means to reduce the inefficiency of equilibria?

Research at CWI addresses both questions.

Koutsoupias and Papadimitriou (1999) introduced the price of anarchy as a worst-case measure of the efficiency loss caused by selfish behavior. It is defined as the maximum ratio between the cost of a Nash equilibrium and the cost of an optimal solution (over all possible instances of the game). The price of anarchy has become the standard measure to assess the inefficiency of equilibria.

We quantify the inefficiency of equilibria for natural extensions of load balancing games. In our studies, we consider the more general strong equilibrium concept introduced by Auman (1960). Strong equilibria are outcomes that are stable with respect to arbitrary deviations of groups of players, i.e., no subset of the players can deviate such that every member of the group strictly benefits.

Selected publication: [10].

Coordination mechanisms can be seen as regulation means to reduce the inefficiency of equilibria. Motivated by the fact that such coordination mechanisms are becoming increasingly important in traffic applications, we study the effect of two kinds of coordination mechanisms in this context: (i) Stackelberg routing in which a central authority controls a fraction of the overall traffic. (ii) Imposing network tolls such that the selfish route choices lead to more favorable equilibrium outcomes.

Selected publications: [11] [12] [13].

3.  Reasoning in strategic games

Strategy elimination procedures & Interactive epistemology

The aim of this research is to predict and analyze choices of rational players. One of the directions, called "Interactive Epistemology", has been advocated in the late nineties by Aumann, winner of the Nobel Prize in Economic Sciences in 2005. It studies consequences of sharing knowledge and has links to logic, game theory and computer science.

Research at CWI focusses at the various strategy elimination procedures and interactive epistemology in games with arbitrary number of strategies.

Selected publications: [14] [15] [16].

Altruistic player behavior

Several game-theoretical studies reveal that rational player behavior is not always tantamount to assuming that players act selfishly. Instead, experiments show that in certain situations players' behavior may vary between altruistic, selfish and spiteful.

We study the impact of altruistic behavior in strategic games. Current research focusses on quantifying the inefficiency of equilibria in the presence of (partially) altruistic players.

Selected publications: [17] [18].

4.  Social networks

Social networks is a broad, interdisciplary area that deals with the nature and effects of social interaction. Examples include spread of certain events, disease, or information over the network. One line of research is concerned with various forms of communications and their effects upon the knowledge of the participants.

We currently study the diffusion process, e.g., adoption of the products by members of the network. Also we analyze knowledge-theoretic consequences of communication by email.

Selected publications: [19] [20].

Highlight Activities

The group is involved in various national and international activities to advance the field of algorithmic game theory. We highlight a few activities:

Key publications

[1] K.R. Apt, V. Conitzer, M. Guo and V. Markakis.
Welfare undominated Groves mechanisms.
In Proc. of the 4th Workshop on Internet & Network Economic (WINE '08), LNCS 5385, pp. 426-437, 2008.
[2] K.R. Apt, E. Markakis.
Sequential bidding in the Bailey-Cavallo mechanism.
In Proc. of the 5th Workshop on Internet & Network Economics (WINE '09), LNCS 5929, pp. 483-490, 2009.
[3] K.R. Apt, A. Estévez-Fernández.
Sequential pivotal mechanisms for public project problems.
In Proc. of the 2nd International Symposium on Algorithmic Game Theory (SAGT '09), LNCS 5814, pp. 85-96, 2009.
[4] J. Brenner and G. Schäfer.
Singleton acyclic mechanisms and their applications to scheduling problems.
In Proc. of the 1st International Symposium on Algorithmic Game Theory (SAGT '08), LNCS 4997, pp. 315-326, 2008.
[5] J. Brenner and G. Schäfer.
Generalized Incremental Mechanisms for Scheduling Games.
Manuscript (submitted), 2010.
[6] J. Brenner and G. Schäfer.
Online cooperative cost sharing.
In Proc. of the 7th International Conference on Algorithms and Complexity (CIAC '10), LNCS 6078, pp. 252-263, 2010.
[7] H. Bosse, J. Byrka, and E. Markakis.
New algorithms for approximate Nash equilibria in bimatrix games.
Theoretical Computer Science, 411(1), pp. 164-173, 2010.
[8] C. Borgs, J.T. Chayes, N. Immorlica, A. Kalai, V. S. Mirrokni, C.H. Papadimitriou.
The Myth of the Folk Theorem.
In Proc. of the 40th Annual ACM Symposium on Theory of Computing (STOC '08), pp. 365-372, 2008.
[9] M. Ummels and D. Wojtczak.
The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games.
In Proc. of the 36th Internatilonal Collogquium on Automata, Languages and Programming (ICALP '08), pp. 297-308, 2008.
[10] B. de Keijzer, G. Schäfer, and O. Telelis.
On the inefficiency of equilibria in linear bottleneck congestion games.
In Proc. of the 3rd International Symposium on Algorithmic Game Theory (SAGT '10), LNCS 6386, pp. 335-346, 2010.
[11] V. Bonifaci, T. Harks, and G. Schäfer.
Stackelberg routing in arbitrary networks.
Mathematics of Operations Research, 35(2), pp. 330-346, 2010.
[12] V. Bonifaci and M. Salek, and G. Schäfer.
Efficiency of restricted tolls in network routing games.
In Proc. of the 4th International Symposium on Algorithmic Game Theory (SAGT '11), 2011, to appear.
[13] T. Harks, G. Schäfer, and Martin Sieg.
The min-toll-booth problem: Complexity, algorithms and experimental findings.
In Proc. of the 7th Triennial Symposium on Transportation Analysis (TRISTAN '10), pp. 343-346, 2010.
[14] K.R. Apt.
Uniform proofs of order independence for various strategy elimination procedures.
Contributions to Theoretical Economics, 4(1), Article 5, 48 pages, 2004.
[15] K.R. Apt.
The many faces of rationalizability.
Topics in Theoretical Economics, 7(1), Article 1, 39 pages, 2007.
[16] K.R. Apt, J.A. Zvesper.
The role of monotonicity in the epistemic analysis of strategic games.
Games, 1(4), pp. 381-394, 2010.
[17] P.-A. Chen, B. de Keijzer, D. Kempe, G. Schäfer.
Robust price of anarchy for atomic games with altruistic players.
Manuscript (in preparation), 2011.
[18] K. Apt and G. Schäfer.
Selfishness level of a strategic game.
Manuscript (in preparation), 2011.
[19] K.R. Apt and V. Markakis.
Diffusion in Social Networks with Competing Products.
In Proc. of the 4th International Symposium on Algorithmic Game Theory (SAGT '11), 2011, to appear.
[20] F. Sietsma and K.R. Apt.
On email exchanges.
Manuscript (in preparation), 2011.