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:
“An accurate charting of the American woman’s progress through history might look more like a corkscrew tilted slightly to one side, its loops inching closer to the line of freedom with the passage of time—but like a mathematical curve approaching infinity, never touching its goal. . . . Each time, the spiral turns her back just short of the finish line.”
—Susan Faludi (20th century)
“One definition of man is “an intelligence served by organs.””
—Ralph Waldo Emerson (1803–1882)