Loading AI tools
From Wikipedia, the free encyclopedia
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.[1] 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.
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,[2] 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:
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.
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:[2]
Case 2: fractionally subadditive buyers, 2nd-price auction, incomplete information.[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. This result does not depend on the common prior of the agents.
Case 3: subadditive buyers, 2nd-price auctions.[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. For example, if a buyer's valuation is $100 for a pair of shoes but $1 for each individual shoe, then the strong-no-overbidding assumption prevents him from bidding more than $1 on each shoe, so that he has little chances of winning the pair. Therefore, it is replaced with a weak-no-overbidding assumption, which means that the no-overbidding condition holds only for the bundle that the agent finally wins (i.e, the sum of bids of the buyer to his allocated bundle is at most his value for this specific bundle). 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, items are sold in consecutive auctions, one after the other. The common equilibrium type is subgame perfect equilibrium in pure strategies (SPEPS). 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.
Case 4: submodular buyers[9] (note that additive and unit-demand are special cases of submodular):
Case 5: additive+UD.[12] Suppose some bidders have additive valuations while others have unit-demand valuations. In a sequence of 1st-price auctions, the PoA might be at least , where m is the number of items and n is the number of bidders. 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.
See [14]
Studies on PoA in auctions have provided insights into other settings that are not related to auctions, such as network formation games [18]
[Partial table - contains only parallel auctions - should be completed]
Multi-auction | Single auction | Information | Valuations | Assumptions | PoA | Pos | Comments |
---|---|---|---|---|---|---|---|
Parallel | 2nd-price | complete | submodular | strong-no-overbidding | 2 | pure: 1 [always exists] | [2] |
Parallel | 2nd-price | Bayesian | XOS | strong-no-overbidding | 2 | [2] | |
Parallel | 2nd-price | complete | subadditive | strong-no-overbidding | 2 | [3] | |
Parallel | 2nd-price | Bayesian | subadditive | strong-no-overbidding | > 2, < 2 log(m) | [3] | |
Parallel | 1st-price | complete | monotone | None | pure: 1 [when exists] | Pure NE = WE. [4] | |
Parallel | 1st-price | complete | monotone | None | mixed: | [4] | |
Parallel | 1st-price | Bayesian | monotone | None | [4] | ||
Parallel | 2nd-price | complete | monotone | weak-no-overbidding | pure: 2 [when exists] | Pure NE = Conditional WE[7] | |
Parallel | 1st-price | Bayesian | subadditive | None | 2 | [6] | |
Parallel | 2nd-price | Bayesian | subadditive | weak/strong-no-overbidding | 4 | [6] |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.