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. 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, etc.). 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 Elias Koutsoupias and Christos 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). Mathematical definition. Consider a game formula_1, defined by a set of players formula_2, strategy sets formula_3 for each player and utilities formula_4 (where formula_5 also called set of outcomes). We can define a measure of efficiency of each outcome which we call welfare function formula_6. Natural candidates include the sum of players utilities (utilitarian objective) formula_7 minimum utility (fairness or egalitarian objective) formula_8 ..., or any function that is meaningful for the particular game being analyzed and is desirable to be maximized . We can define a subset formula_9 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 'worst equilibrium' and the optimal 'centralized' solution: formula_10 If, instead of a 'welfare' which we want to 'maximize', the function measure efficiency is a 'cost function' formula_11 which we want to 'minimize' (e.g. delay in a network) we use (following the convention in approximation algorithms): formula_12 A related notion is that of the Price of Stability (PoS) which measures the ratio between the 'best equilibrium' and the  optimal 'centralized' solution: formula_13 or in the case of cost functions: formula_14 We know that formula_15 by the definition. It is expected that the loss in efficiency due to game-theoretical constraints is somewhere between 'PoS' and 'PoA'. Both the PoS and the PoA have been calculated for various types of games. Some examples are presented below. Prisoner's dilemma. Consider the 2x2 game called prisoner's dilemma, given by the following cost matrix: and let the cost function be formula_16 Now, the worst Nash Equilibrium would be when both players cooperate and the resulting cost is formula_17. However, the  highest social welfare occurs when both defect, in which case the cost is formula_18. Thus the PoA of this game will be formula_19. Since the game has a unique Nash equilibrium, the PoS is equal to the PoA and it is 5 too. Job scheduling. A more natural example is the one of job scheduling. There are formula_2 players and each of them has a job to run. They can choose one of formula_21 machines to run the job. The Price of Anarchy compares the situation where the selection of machines is guided/directed centrally to the situation where each  player chooses the machine that will make its job run fastest. Each machine has a speed formula_22 Each job has a weight formula_23 A player picks a machine to run his or her job on. So, the strategies of each player are formula_24 Define the "load" on machine formula_25 to be: The cost for player formula_27 is formula_28 i.e., the load of the machine they chose. We consider the egalitarian cost function formula_29, here called the "makespan." We consider two concepts of equilibrium: pure Nash and mixed Nash. It should be clear that mixed PoA ≥ pure PoA, because any  pure Nash equilibrium is also a mixed Nash equilibrium (this inequality can be strict: e.g. when formula_30, formula_31, formula_32, and formula_33, the mixed strategies formula_34 achieve an average makespan of 1.5, while any pure-strategy PoA in this setting is formula_35). First we need to argue that there exist pure Nash equilibria. Claim. For each job scheduling game, there exists at least one pure-strategy Nash equilibrium. Proof. We would like to take a socially optimal action profile formula_36. This would mean simply an action profile whose makespan is minimum. However, this will not be enough. There may be several  such action profiles leading to a variety of different loads distributions (all having the same maximum load). Among these, we further restrict ourselves to one that has a minimum second-largest load. Again, this results in a set of possible load distributions, and we repeat until the formula_21th-largest (i.e., smallest) load, where there can only be one distribution of loads (unique up to permutation). This would also be called the "lexicographic" smallest sorted load vector. We claim that this is a pure-strategy Nash equilibrium. Reasoning by contradiction, suppose that some player formula_27 could strictly improve by moving from  machine formula_25 to machine formula_40. This means that the increased load of machine formula_40 after the move is still smaller than the load of machine formula_25 before the move. As the load of machine formula_25 must decrease as a result of the move and no other machine is affected, this means that the new configuration is guaranteed to have reduced the formula_25th-largest (or higher ranked) load in the distribution. This, however, violates the assumed lexicographic minimality of formula_45. "Q.E.D." Claim. For each job scheduling game, the pure PoA is at most formula_21. Proof. It is easy to upper-bound  the welfare obtained at any mixed-strategy Nash equilibrium formula_47 by Consider, for clarity of exposition, any pure-strategy action profile formula_45: clearly Since the above holds for the social optimum as well, comparing the ratios formula_51 and formula_52 proves the claim. "Q.E.D" Selfish Routing. Braess's paradox. Consider a road network as shown in the adjacent diagram on which 4000 drivers wish to travel from point Start to End. The travel time in minutes on the Start–A road is the number of travelers (T) divided by 100, and on Start–B is a constant 45 minutes (likewise with  the roads across from them). If the dashed road does not exist (so the traffic network has 4 roads in total), the time needed to drive Start–A–End route with formula_45 drivers would be formula_54. The time needed to drive the Start–B–End route with formula_55 drivers would be formula_56. As there are 4000 drivers, the fact that formula_57 can be used to derive the fact that formula_58 when the system is at equilibrium. Therefore, each route takes formula_59 minutes. If either route took less time, it would not be a Nash equilibrium: a rational driver would switch  from the longer route to the shorter route. Now suppose the dashed line A–B is a road with an extremely short travel time of approximately 0 minutes. Suppose that the road is opened and one driver tries Start–A–B–End. To his surprise he finds that his time is formula_60 minutes, a saving of almost 25 minutes. Soon, more of the 4000 drivers are trying this new route. The time taken rises from 40.01 and keeps climbing. When the number of drivers trying the new route reaches 2500, with 1500 still in the Start–B–End route, their  time will be formula_61 minutes, which is no improvement over the original route. Meanwhile, those 1500 drivers have been slowed to formula_62 minutes, a 20-minute increase. They are obliged to switch to the new route via A too, so it now takes formula_63 minutes. Nobody has any incentive to travel A-End or Start-B because any driver trying them will take 85 minutes. Thus, the opening of the cross route triggers an irreversible change to it by everyone, costing everyone 80 minutes instead of the original 65. If every driver were to agree not to use the A –B path, or if that route were closed, every driver would benefit by a 15-minute reduction in travel time. Generalized routing problem. The routing problem introduced in the Braess's paradox can be generalized to many different flows traversing the same graph at the same time. Definition (Generalized flow). Let formula_64, formula_65 and formula_66 be as defined above, and suppose that we want to route the quantities formula_67 through each distinct pair of nodes in formula_68. A "flow" formula_69 is defined as an assignment formula_70 of a real, nonnegative number to each "path" formula_71 going from formula_72 to formula_73  formula_74, with the constraint that The flow traversing a specific edge of formula_76 is defined as For succinctness, we write formula_78 when formula_79 are clear from context. Definition (Nash-equilibrium flow). A flow formula_69 is a "Nash-equilibrium flow" iff formula_81 and formula_82 from formula_72 to formula_73 This definition is closely related to what we said about the support of mixed-strategy Nash equilibria in normal-form games. Definition (Conditional welfare of a flow). Let formula_69 and formula_87 be two flows in formula_76 associated with the same sets formula_89 and formula_90. In what follows, we will drop the subscript to  make the notation clearer. Assume to fix the latencies induced by formula_91 on the graph: the "conditional welfare" of formula_92 with respect to formula_91 is defined as Fact 1. Given a Nash-equilibrium flow formula_91 and any other flow formula_92, formula_97. Proof (By contradiction). Assume that formula_98. By definition, Since formula_91 and formula_92 are associated with the same sets formula_102, we know that Therefore, there must be a pair formula_104 and two paths formula_105 from formula_72 to formula_73 such that formula_108, formula_109, and In other words, the flow formula_92 can achieve a lower welfare than formula_91 only if there are  two paths from formula_72 to formula_73 having different costs, and if formula_92 reroutes some flow of formula_91 from the higher-cost path to the lower-cost path. This situation is clearly incompatible with the assumption that formula_91 is a Nash-equilibrium flow. "Q.E.D." Note that Fact 1 does not assume any particular structure on the set formula_65. Fact 2. Given any two real numbers formula_119 and formula_120, formula_121. Proof. This is another way to express the true inequality formula_122. "Q.E.D." Theorem. The pure PoA of any generalized routing problem formula_123 with linear latencies is formula_35. Proof. Note that this theorem  is equivalent to saying that for each Nash-equilibrium flow formula_91, formula_126, where formula_92 is any other flow. By definition, By using Fact 2, we have that since We can conclude that formula_135, and prove the thesis using Fact 1. "Q.E.D." Note that in the proof we have made extensive use of the assumption that the functions in formula_65 are linear. Actually, a more general fact holds. Theorem. Given a generalized routing problem with graph formula_76 and polynomial latency functions of degree formula_138 with nonnegative coefficients, the pure PoA is formula_139. Note that the PoA can grow with formula_138. Consider  the example shown in the following figure, where we assume unit flow: the Nash-equilibrium flows have social welfare 1; however, the best welfare is achieved when formula_141, in which case This quantity tends to zero when formula_138 tends to infinity.