Algorithmic game theory

Algorithmic game theory is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments. 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. Algorithmic game theory is an area in the intersection of game theory and computer science, with the objective of understanding and design of 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. We can see Algorithmic Game Theory from two perspectives: 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. In 1999, the seminal paper of Nisan and Ronen drew the attention of the Theoretical Computer Science community to designing algorithms for selfish (strategic) users. As they claim in the abstract: This paper coined the term algorithmic mechanism design and was recognized by the 2012 Gödel Prize committee as one of 'three papers laying foundation of growth in Algorithmic Game Theory'. The other two papers cited in the 2012 Gödel Prize for fundamental contributions to Algorithmic Game Theory introduced and developed the concept of 'Price of Anarchy'. In their 1999 paper 'Worst-case Equilibria', Koutsoupias and Papadimitriou proposed a new measure of the degradation of system efficiency due to the selfish behavior of its agents: the ratio of between system efficiency at an optimal configuration, and its efficiency at the worst Nash equilibrium. (The term 'Price of Anarchy' only appeared a couple of years later.)