The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.
In an auction, there are one or more items and one or more agents with different valuations for the items. The items have to be divided among the agents. It is desired that the social welfare - the sum of values of all agents - be as high as possible.
One approach to maximizing the social welfare is designing a truthful mechanism. In such a mechanism, each agent is incentivized to report his true valuations to the items. Then, the auctioneer can calculate and implement an allocation that maximizes the sum of values. An example to such a mechanism is the VCG auction.
In practice, however, it is not always feasible to use truthful mechanisms. The VCG mechanism, for example, might be too complicated for the participants to understand, might take too long for the auctioneer to compute, and might have other disadvantages. In practice, non-truthful mechanisms are often used, and it is interesting to calculate how much social welfare is lost by this non-truthfulness.
It is often assumed that, in a non-truthful auction, the participants play an equilibrium strategy, such as a Nash equilibrium. The price-of-anarchy of the auction is defined as the ratio between the optimal social welfare and the social welfare in the worst equilibrium:
A related notion is the Price of Stability (PoS) which measures the ratio between the optimal social welfare and the social welfare in the best equilibrium:
Obviously .
When there is complete information (each agent knows the valuations of all other agents), the common equilibrium type is Nash equilibrium - either pure or mixed. When there is incomplete information, the common equilibrium type is Bayes-Nash equilibrium. In the latter case, it is common to speak of the Bayesian price of anarchy, or BPoA.
Single-item auctions
In a first-price auction of a single item, a Nash equilibrium is always efficient, so the PoA and PoS are 1.
In a second-price auction, there is a Nash equilibrium in which the agents report truthfully; it is efficient, so the PoS is 1. However, the PoA is unbounded! For example, suppose there are two players: Alice values the item as a and Bob as b, with a>b.
There exists a "good" Nash equilibrium in which Alice bids a and Bob bids b; Alice receives the item and pays b. The social welfare is a, which is optimal.
However, there also exists a "bad" Nash equilibrium in which Alice bids 0 and Bob bids e.g. a+1; Bob receives the item and pays nothing. This is an equilibrium since Alice does not want to overbid Bob. The social welfare is b. Hence, the PoA is a/b, which is unbounded.
This result seems overly pessimistic: First, in a second-price auction, it is a weakly-dominant strategy for each agent to report his true valuation. If we assume that agents follow their dominant strategies, then the PoA is 1. Moreover, it is a dominated strategy for each agent to report any value above his true valuation. Therefore, it is common to analyze the PoA under a no overbidding assumption - no agent bids above his true valuation. Under this assumption, the PoA of a single-item auction is 1.
Parallel auctions
In a parallel (simultaneous) auction, items are sold at the same time to the same group of participants. In contrast to a combinatorial auction - in which the agents can bid on bundles of items, here the agents can only bid on individual items independently of the others. I.e, a strategy of an agent is a vector of bids, one bid per item. The PoA depends on the type of valuations of the buyers, and on the type of auction used for each individual item.
Case 1: submodular buyers, second-price auctions, complete information: There exists a pure Nash equilibrium with optimal social welfare. Hence, the PoS is 1. It is possible to calculate in polynomial time a pure Nash equilibrium with social welfare at least half the optimal. Hence, the price of "polynomial-time stability" is at most 2. The PoA is unbounded - as already shown by the single-item example above. However, under a strong-no-overbidding assumption (the sum of bids of any buyer to any bundle is at most the value of that bundle to the buyer), the PoA is at most 2. The latter result also holds when the buyers' valuations are fractionally subadditive.