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 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.
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 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.
This result seems overly pessimistic: Therefore, it is common to analyze the PoA under a no overbidding assumption - no agent bids above his true valuation.
[2] Assuming strong-no-overbidding, any (mixed) Bayes-Nash equilibrium attains in expectation at least 1/2 the optimal welfare; hence the BPoA is at most 2.
[3] Under a strong-no-overbidding assumption: Case 4: General (monotone) buyers, first-price auctions, complete information:[4] Case 5: General buyers, 2nd-price auctions, complete information.
[7] With general valuations (that may have complementarities), the strong-no-overbidding assumption is too strong, since it prevents buyers from bidding high values on bundles of complementary items.
Under this weak-no-overbidding assumption: Case 6: General buyers, 1st-price auctions, incomplete information.
[4] For any common prior: Case 7: Subadditive buyers, incomplete information:[6] In a sequential auction,
When the buyers have full information (i.e., they know the sequence of auctions in advance), and a single item is sold in each round, a SPEPS always exists.
[9]: 872–874 The PoA of this SPEPS depends on the utility functions of the bidders, and on the type of auction used for each individual item.
The first five results below apply to agents with complete information (all agents know the valuations of all other agents): Case 1: Identical items, two buyers, 2nd-price auctions:[10][11] Case 2: additive buyers:[9] : 885 Case 3: unit demand buyers:[9] These results are surprising and they emphasize the importance of the design decision of using a first-price auction (rather than a second-price auction) in each round.
Moreover, the inefficient equilibria persist even under iterated elimination of weakly dominated strategies.
This implies linear inefficiency for many natural settings, including: Case 6: unit-demand buyers, incomplete information, 1st-price auctions:[13] The BPoA is at most 3.