Price of anarchy in auctions
Price of anarchy in auctions
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:
<math>PoA = \frac{\max_{s \in Allocations} Welf(s)}{\min_{s \in EquilibriumAllocations} Welf(s)}</math>
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:
<math>PoS = \frac{\max_{s \in Allocations} Welf(s)}{\max_{s \in EquilibriumAllocations} Welf(s)}</math>
Obviously <math>1\leq PoS \leq PoA \leq \infty</math>.
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, <math>m</math> items are sold at the same time to the same group of <math>n</math> 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**: Under a *strong-no-overbidding* assumption:
- With complete information, the welfare of every pure Nash equilibrium is at least 1/2 the optimum, so the PoA is at most 2.
- With incomplete information, there exist Bayes-Nash equilibria with welfare less than 1/2 the optimum, so the BPoA is more than 2.
- The BPoA is at most <math>2\log{m}</math>, where <math>m</math> is the number of items. This guarantee is also valid to coarse correlated equilibrium - and hence to the special cases of mixed Nash equilibrium and correlated-equilibrium.
- Both of the above upper bounds on the PoA degrade gracefully when the subadditivity and no-overbidding assumptions are relaxed. E.g.: if we assume that each player overbids by at most some constant factor, then the PoA grows by at most a constant factor.
- Case 4: General (monotone) buyers, first-price auctions, complete information**:
- The set of pure Nash equilibria of the game are exactly the Walrasian equilibria (price equilibria) of the market.
- Since such equilibria are socially-optimal (by the first welfare theorem), the PoA of pure Nash equilibria is 1. Unfortunately, such equilibria might not exist.
- A mixed Nash equilibrium always exists (when choosing the right tie-breaking rule). However, it is not necessarily socially-optimal. The PoA might be as high as <math>\Omega(\sqrt{m})</math>, and even the PoS might be as high as <math>\Omega(\sqrt{m}/\log{m})</math>.
- This result also extends to 2nd-price auctions, even with a weak-no-overbidding assumption. 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:
- The set of pure Nash equilibria of the game are exactly the conditional price-equilibria of the market.
- Since such equilibria are half-socially-optimal (attain at least half the maximum social welfare), the PoA of pure Nash equilibria is at most 2. Unfortunately, such equilibria might not exist.
- Case 6: General buyers, 1st-price auctions, incomplete information**.
- When the items are sold in first-price auctions, the BPoA is at most 2.
- When the items are sold in second-price auctions, the BPoA is at most 4. This is true both under the 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), and under the weak-no-overbidding assumption (the expected sum of the winning bids of any buyer is at most the expected winning value of that buyer).
Sequential auctions In a sequential-auction, <math>m</math> 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. * When at least one buyer has a concave valuation function (diminishing returns), the PoA is at most <math>1/(1-e) \approx 1.58</math>. * Numerical results show that, when there are many bidders with concave valuation functions, the efficiency loss decreases as the number of users increases.
- Case 2: additive buyers**:
- With second-price auctions, the PoA is unbounded – the welfare in a SPEPS might be arbitrarily small!
- Case 3: unit demand buyers**: 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 <math>\min(n,m)</math>, 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:
- buyers with gross substitute valuations,
- capacitated valuations,
- budget-additive valuations,
- additive valuations with hard budget constraints on the payments.
- Case 6: unit-demand buyers, incomplete information, 1st-price auctions**: The BPoA is at most 3.