Algorithmic game theory
Encyclopedia
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:
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:
Game theory studies equilibria (such as the Nash equilibrium
). An equilibrium is generally defined as a state in which no player has an incentive to change their strategy. Equilibria are found in several fields related to the Internet, for instance financial interactions and communication load-balancing. Game theory provides tools to analyze equilibria, and a common approach is then to ‘find the game’ – that is, to formalize specific Internet interactions as a game, and to derive the associated equilibria.
Rephrasing problems in terms of games allows the analysis of Internet-based interactions and the construction of mechanisms to meet specified demands. If equilibria can be shown to exist, a further question must be answered: can an equilibrium be found, and in reasonable time? This leads to the analysis of algorithms
for finding equilibria. Of special importance is the complexity class PPAD, which includes many problems in algorithmic game theory.
And the area counts with diverse practical applications:
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
and algorithm design
Algorithm design
Algorithm design is a specific method to create a mathematical process in solving problems. Applied algorithm design is algorithm engineering....
, 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 AnarchyPrice of anarchyThe Price of Anarchy is a concept in game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and...
, best-response dynamics ... - Design: design games that have both good game-theoretical and algorithmic properties. This area is called Algorithmic Mechanism DesignAlgorithmic mechanism designAlgorithmic mechanism design lies at the intersection of economic game theory and computer science.Noam Nisan and Amir Ronen, from the Hebrew University of Jerusalem, first coined "Algorithmic mechanism design" in a research paper published in 2001....
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:
The Internet as a catalyst
The Internet created a new economy – both as a foundation for exchange and commerce, and in its own right. The computational nature of the Internet allowed for the use of computational tools in this new emerging economy. On the other hand, the Internet itself is the outcome of actions of many. This was new to the classic, ‘top-down’ approach to computation that held till then. Thus, game theory is a natural way to view the Internet and interactions within it, both human and mechanical.Game theory studies equilibria (such as the Nash equilibrium
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
). An equilibrium is generally defined as a state in which no player has an incentive to change their strategy. Equilibria are found in several fields related to the Internet, for instance financial interactions and communication load-balancing. Game theory provides tools to analyze equilibria, and a common approach is then to ‘find the game’ – that is, to formalize specific Internet interactions as a game, and to derive the associated equilibria.
Rephrasing problems in terms of games allows the analysis of Internet-based interactions and the construction of mechanisms to meet specified demands. If equilibria can be shown to exist, a further question must be answered: can an equilibrium be found, and in reasonable time? This leads to the analysis of algorithms
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
for finding equilibria. Of special importance is the complexity class PPAD, which includes many problems in algorithmic game theory.
Areas of research
The main areas of research in algorithmic game theory include:- Algorithmic mechanism designAlgorithmic mechanism designAlgorithmic mechanism design lies at the intersection of economic game theory and computer science.Noam Nisan and Amir Ronen, from the Hebrew University of Jerusalem, first coined "Algorithmic mechanism design" in a research paper published in 2001....
- Inefficiency of equilibria (Price of AnarchyPrice of anarchyThe Price of Anarchy is a concept in game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and...
) - ComplexityComputational ComplexityComputational Complexity may refer to:*Computational complexity theory*Computational Complexity...
of finding equilibria - Market equilibrium
- Multi-agent systems
- Computational social choice
And the area counts with diverse practical applications:
- RoutingRoutingRouting is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...
- P2PPeer-to-peerPeer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...
systems - AdAuctions
See also
- Auction TheoryAuction theoryAuction theory is an applied branch of economics which deals with how people act in auction markets and researches the properties of auction markets. There are many possible designs for an auction and typical issues studied by auction theorists include the efficiency of a given auction design,...
- Mechanism designMechanism designMechanism design is a field in game theory studying solution concepts for a class of private information games...
- Multi-agent systemMulti-agent systemA multi-agent system is a system composed of multiple interacting intelligent agents. Multi-agent systems can be used to solve problems that are difficult or impossible for an individual agent or a monolithic system to solve...
- Voting in game theory
- Load balancing (computing)Load balancing (computing)Load balancing is a computer networking methodology to distribute workload across multiple computers or a computer cluster, network links, central processing units, disk drives, or other resources, to achieve optimal resource utilization, maximize throughput, minimize response time, and avoid...
External links
- gambit.sourceforge.net - a library of game theory software and tools for the construction and analysis of finite extensive and strategic games.
- gamut.stanford.edu - a suite of game generators designated for testing game-theoretic algorithms.