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:
“What he loved so much in the plant morphological structure of the tree was that given a fixed mathematical basis, the final evolution was so incalculable.”
—D.H. (David Herbert)
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)