Algorithmic game theory

This article is written like a personal reflection, personal essay, or argumentative essay that states a Wikipedia editor's personal feelings or presents an original argument about a topic. Please help improve it by rewriting it in an encyclopedic style. (August 2013) (Learn how and when to remove this message)

Algorithmic game theory (AGT) 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:

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

On top of the usual requirements in classical algorithm design (e.g., polynomial-time running time, good approximation ratio), the designer must also care about incentive constraints.