Mathematical Definition
Consider a game, defined by a set of players, strategy sets for each player and utilities (where also called set of outcomes). We can define a measure of efficiency of each outcome which we call welfare function . Natural candidates include the sum of players utilities (utilitarian objective) minimum utility (fairness or egalitarian objective) ..., or any function that is meaningful for the particular game being analyzed and is desirable to be maximized.
We can define a subset 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:
Following the convention in approximation algorithms, if the function measure efficiency is, instead of a 'welfare' we want to 'maximize', a 'cost function' we want to 'minimize' (delay in a network, for example) we use:
A related notion is that of the Price of Stability (PoS) which measures the ratio between the 'best equilibrium' and the optimal 'centralized' solution:
or in the case of cost functions:
We know that by the definition. It is expected that the loss in efficiency due to game-theoretical constraints is somewhere between 'PoS' and 'PoA'.
Read more about this topic: Price Of Anarchy
Famous quotes containing the words mathematical and/or definition:
“The most distinct and beautiful statement of any truth must take at last the mathematical form.”
—Henry David Thoreau (1817–1862)
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)