Algorithmic game theory

Algorithmic game theory is an area in the intersection of game theory and algorithm design, whose objective is to design algorithms in strategic environments. Typically, in Algorithmic Game Theory problems, the input to a given algorithm is distributed among many players who have a personal interest in the output. In those situations, the agents might not report the input truthfully because of their own personal interests. On top of the usual requirements in classical algorithm design, say polynomial-time running time, good approximation ratio, … the designer must also care about incentive constraints. We can see Algorithmic Game Theory from two perspectives:

• Analysis: look at the current implemented algorithms and analyze them using Game Theory tools: calculate and prove properties on their Nash equilibria, price of anarchy, best-response dynamics …
• Design: design games that have both good game-theoretical and algorithmic properties. This area is called algorithmic mechanism design.

The field was started when Nisan and Ronen in STOC’99 drew the attention of the Theoretical Computer Science community to designing algorithms for selfish (strategic) users. As they claim in the abstract:

“We consider algorithmic problems in a distributed setting where the participants cannot be assumed to follow the algorithm but rather their own self-interest. As such participants, termed agents, are capable of manipulating the algorithm, the algorithm designer should ensure in advance that the agents’ interests are best served by behaving correctly. Following notions from the field of mechanism design, we suggest a framework for studying such algorithms. In this model the algorithmic solution is adorned with payments to the participants and is termed a mechanism. The payments should be carefully chosen as to motivate all participants to act as the algorithm designer wishes. We apply the standard tools of mechanism design to algorithmic problems and in particular to the shortest path problem.”

See also

Game Theory

Material

• Gambit: Software Tools for Game Theory
• GAMUT a suite of game generators designated for testing game-theoretic algorithms.
• Stanford course: CS364A Fall 2013
• Éva Tardos’ Cornell course: CS684 Spring 2004
• Columbia course: COMS 6998-3

Papers

• Adkins, Robert. Algorithmic Game Theory. (2015). Random University Report

Books

• Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007), Algorithmic Game Theory, Cambridge, UK: Cambridge University Press.
• John von Neumann, Oskar Morgenstern (1944) Theory of Games and Economic Behavior. Princeton Univ. Press.
• Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. V. (2007). Algorithmic game theory. (Vol. 1). Cambridge: Cambridge University Press.