Price of anarchy

The Price of Anarchy (PoA) is a concept in economics and 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 many agents trying to go from some initial location to a destination. Let efficiency in this case mean the average time for an agent to reach the destination. In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time. In the 'decentralized' version, each agent chooses its own path. The Price of Anarchy measures the ratio between average travel time in the two cases. The Price of Anarchy (PoA) is a concept in economics and 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 many agents trying to go from some initial location to a destination. Let efficiency in this case mean the average time for an agent to reach the destination. In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time. In the 'decentralized' version, each agent chooses its own path. The Price of Anarchy measures the ratio between average travel time in the two cases. Usually the system is modeled as a game and the efficiency is some function of the outcomes (e.g. maximum delay in a network, congestion in a transportation system, social welfare in an auction, ...). Different concepts of equilibrium can be used to model the selfish behavior of the agents, among which the most common is the Nash equilibrium. Different flavors of Nash equilibrium lead to variations of the notion of Price of Anarchy as Pure Price of Anarchy (for deterministic equilibria), Mixed Price of Anarchy (for randomized equilibria), and Bayes-Nash Price of Anarchy (for games with incomplete information). Solution concepts other than Nash equilibrium lead to variations such as the Price of Sinking. The term Price of Anarchy was first used by Koutsoupias and Papadimitriou, but the idea of measuring inefficiency of equilibrium is older. The concept in its current form was designed to be the analogue of the 'approximation ratio' in an approximation algorithm or the 'competitive ratio' in an online algorithm. This is in the context of the current trend of analyzing games using algorithmic lenses (algorithmic game theory). Consider a game G = ( N , S , u ) {displaystyle G=(N,S,u)} , defined by a set of players N {displaystyle N} , strategy sets S i {displaystyle S_{i}} for each player and utilities u i : S → R {displaystyle u_{i}:S ightarrow mathbb {R} } (where S = S 1 × . . . × S n {displaystyle S=S_{1} imes ... imes S_{n}} also called set of outcomes). We can define a measure of efficiency of each outcome which we call welfare function W e l f : S → R {displaystyle Welf:S ightarrow mathbb {R} } . Natural candidates include the sum of players utilities (utilitarian objective) W e l f ( s ) = ∑ i ∈ N u i ( s ) , {displaystyle Welf(s)=sum _{iin N}u_{i}(s),} minimum utility (fairness or egalitarian objective) W e l f ( s ) = min i ∈ N u i ( s ) , {displaystyle Welf(s)=min _{iin N}u_{i}(s),} ..., or any function that is meaningful for the particular game being analyzed and is desirable to be maximized. We can define a subset E q u i l ⊆ S {displaystyle Equilsubseteq S} to be the set of strategies in equilibrium (for example, the set of Nash equilibria). The Price of Anarchy is then defined as the ratio between the optimal 'centralized' solution and the 'worst equilibrium': P o A = max s ∈ S W e l f ( s ) min s ∈ E q u i l W e l f ( s ) {displaystyle PoA={frac {max _{sin S}Welf(s)}{min _{sin Equil}Welf(s)}}} If, instead of a 'welfare' which we want to 'maximize', the function measure efficiency is a 'cost function' C o s t : S → R {displaystyle Cost:S ightarrow mathbb {R} } which we want to 'minimize' (e.g. delay in a network) we use (following the convention in approximation algorithms): P o A = max s ∈ E q u i l C o s t ( s ) min s ∈ S C o s t ( s ) {displaystyle PoA={frac {max _{sin Equil}Cost(s)}{min _{sin S}Cost(s)}}} A related notion is that of the Price of Stability (PoS) which measures the ratio between the 'best equilibrium' and the optimal 'centralized' solution: