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