The Independent Research Group "Algorithmic Game Theory" headed by Giorgos Christodoulou was part of the Cluster of Excellence from June 2010 until January 2011.
Algorithmic game theory has blossomed during the last ten years and now is a standalone field of theoretical computer science. Algorithmic game theory can be roughly categorized into three main topics.
The first topic is aimed at quantifying the impact of selfishness to the performance of systems, the second studies the design of algorithms in environments where part of the input is unknown and controlled by selfish entities, and the last topic considers computational issues of finding equilibria.
(In)efficiency of Equilibria
During the last decades, the rapid growth of the Internet and the World Wide Web led the computer science community to intensify its efforts to understand its most critical features. The Internet consists of a variety of autonomous computational entities with different and often conflicting interests. Noncooperative game theory has traditionally studied such situations (games) in which selfish agents with conflicting interests make decisions without regard to overall social welfare. The study of the Internet and the Web from this perspective is the subject of a relatively new scientific area that lies on the border between computer science and economics (in particular game theory).
The focus of this area is the modeling of a distributed system as a (non)cooperative game, where the actions taking place are strategic decisions of the selfish autonomous entities (agents, players) that constitute the network. Having such a model at hand, two main questions motivate our research: How much is the system’s performance affected due to the users’ selfish behavior? Can we modify the parameters of the system, so as to implicitly encourage the selfish agents to act in a way that benefits social welfare?
Algorithmic Mechanism Design
The design of algorithms and protocols for interconnected computer groups is a central field of computer science. The designer of such an algorithm or protocol usually makes the indirect assumption that the entities of the system will follow the rules of the protocol, with the exception of faulty or malicious ones. In large scale networks, like the Internet (when viewed as a platform for distributed computation), this assumption is not valid.
The distributed computational units that comprise the network belong to distinctly different economic organizations. Each one of the units has its own incentives and concerns. In addition, they frequently act (partially or completely) autonomously, and they exploit their autonomy in order to satisfy their interests. So, instead of following the rules of the system — that is, the protocol that the designer determined — they may manipulate it to turn it to their advantage.
Coordination Mechanisms
Together with Elias Koutsoupias and Akash Nanavati, in 2004 we proposed coordination mechanisms as an algorithmic framework to improve the price of anarchy. Our framework has frequently been adopted by subsequent papers. Instead of applying the classical approach of mechanism design, which uses monetary compensation to influence the players, we suggested the introduction of delays in achieving the objectives of the players. We designed mechanisms for specific network topologies, reducing the price of anarchy from a logarithmic factor down to a constant factor of the optimum.
Collaborations within the Cluster of Excellence
Our group works closely with Kurt Mehlhorn's Algorithms and Complexity Group at the MPIINF.

More specifically, together with Kurt Mehlhorn and Evangelia Pyrga, we have worked on coordination mechanisms for selfish routing games. Our objective is to design simple protocols that reduce the price of anarchy for singlecommodity networks.

Together with Khaled Elbassioni and Mahmoud Fouz, we have designed Incentive Compatible auctions for exhibitions.

Together with Annamaria Kovacs and Rob van Stee, we have worked on truthful mechanisms that approximate the natural fairness objective of maximizing the minimum load for related machines scheduling.
External Collaborations

Together with Annamaria Kovacs (University of Frankfurt), we consider the design of mechanisms for scheduling problems and combinatorial auctions under strategic settings where part of the input is secretly held by selfinterested agents. The natural properties that we study are incentive compatibility (each individual is motivated to report the truth) and envyfreeness (no agent is envious of the others).

Together with Elias Koutsoupias (University of Athens) and Paul Spirakis (University of Patras), we study the performance of approximate εNash equilibria for congestion games. We consider how much the price of anarchy (worstcase cost of an equilibrium/optimal cost) worsens and how much the price of stability (bestcase cost of an equilibrium/optimal cost) improves as a function of the approximation factor ε.

Together with Katrina Ligett (California Institute of Technology) and Evangelia Pyrga (Technical University of Munich), we have studied contention resolution under selfishness. We have designed a couple of strategyproof efficient protocols for some natural models.