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:
“It is by a mathematical point only that we are wise, as the sailor or the fugitive slave keeps the polestar in his eye; but that is sufficient guidance for all our life. We may not arrive at our port within a calculable period, but we would preserve the true course.”
—Henry David Thoreau (1817–1862)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)