Algorithmic game theory studies the interaction of algorithms with strategic behavior. It asks both how hard equilibria are to compute and how mechanisms should be designed when participants choose actions to improve their own utility.
For example, a shortest-path algorithm optimizes travel time for one specified traveler, while a routing game asks what happens when many travelers each choose a route. A Nash equilibrium can have a larger total delay than a centrally chosen allocation. Quantifying that loss by a price of anarchy links incentives with computational optimization. The input representation, equilibrium concept and allowed running time must all be specified.
For a cost-minimization game with positive social optimum and a nonempty set of the specified Nash equilibria, the price of stability isIt measures the cost of requiring stability even when the best equilibrium can be selected. The equilibrium class, such as pure or mixed, and social-cost convention must be stated.
In a symmetric two-player game with actions , let each player's cost be one at , two at and three when the actions differ. Both coordinated choices are Nash equilibria; the best equilibrium has total cost two, matching the optimum, so the price of stability is one. The worst equilibrium instead costs four, giving price of anarchy two. The distinction matters when a designer can recommend an outcome but cannot force anyone to remain at an unstable one.[ref]
The Price of Stability for Network Design with Fair Cost Allocation by Elliot Anshelevich and others. Introduction, best equilibrium and stability interpretation
For a cost-minimization game, the price of anarchy is the ratio of the worst equilibrium social cost to the best feasible social cost:Here is the specified equilibrium set, the feasible profiles, and the chosen nonnegative social cost. The ratio requires a positive denominator; zero optimum costs and empty equilibrium sets need separate conventions. A payoff-maximization formulation uses the reciprocal orientation to keep a larger number meaning worse efficiency.
In the two-edge routing game with one unit of flow and latencies and one, the equilibrium costs one while the optimum costs , so the price of anarchy is . The best equilibrium instead defines the price of stability. Bounds depend on the equilibrium notion and the allowed game class; one example does not establish a universal bound for all games.
Articles by others on the same topic
Algorithmic game theory is an interdisciplinary field that combines concepts from computer science, game theory, and economics to study and design algorithms and computational systems that can solve problems related to strategic interactions among rational agents. The focus is on understanding how these agents make decisions, how to predict their behavior, and how to design mechanisms and systems that can lead to desirable outcomes.