Algorithmic game theory is the fertile marriage between the theory of algorithms and the theory of games, exploiting a powerful synergy between these two classical theories. On the one hand, game theory and solution concepts such as equilibrium and rationalizability give us the appropriate framework in which to understand, design, and analyze multi-agent protocols. On the other hand, the classical theory of algorithms provides the necessary tools for efficiently analyzing models of economics, such as games and markets. Deployed applications of this range from formal verification to designing airport security systems.

Current focus areas of CTIC within algorithmic game theory are:

• The development of rational cryptography. This topic aims at ensuring voluntary participation of rational agents in cryptographic protocols. In this area, the greatest challenge is to extend the applicability of the rational cryptographic analysis beyond the rudimentary applications to which they currently apply.
• The study of computational aspect of Shapley's stochastic games. The analysis of this model has rich and surprising applications in computer science, in particular within formal methods. The main open problem in this area is Condon's problem: to obtain a polynomial time algorithm for solving simple stochastic games.
• Connections between (computational) game theory and (computational) real algebraic geometry and symbolic-numerical computation.

The research within CTIC on algorithmic game theory is closely connected to research within the collocated Center for Research in the Foundations of Electronic Markets (CFEM).

Work Package Leaders: Peter Bro Miltersen, Professor from Aarhus University, Denmark, and Pinzhong Tang, Assistant Professor from Tsinghua University, China.