Sgouritsa, Alkmini, Tang, Bo and Christodoulou, Giorgos
(2015)
On the Efficiency of All-Pay Mechanisms.
In:
Proceedings of the 23rd European Symposium on Algorithms (ESA).
Springer.
ISBN UNSPECIFIED
There is a more recent version of this item available. |
Text
allpay.pdf - Accepted Version Download (496kB) |
Abstract
We study the inefficiency of mixed equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions where m all-pay auctions run in parallel, one for each good. For fractionally subadditive valuations, we strengthen the upper bound from 2 [22] to 1.82 by proving some struc- tural properties that characterize the mixed Nash equilibria of the game. Next, we design an all-pay mechanism with a randomized allocation rule for the multi-unit auction. We show that, for bidders with submodular valuations, the mechanism admits a unique, 75% efficient, pure Nash equilibrium. The efficiency of this mechanism outperforms all the known bounds on the price of anarchy of mechanisms used for multi-unit auc- tions. Finally, we analyze single-item all-pay auctions motivated by their connection to contests and show tight bounds on the price of anarchy of social welfare, revenue and maximum bid.
Item Type: | Book Section |
---|---|
Additional Information: | ## TULIP Type: Articles/Papers (Journal) ## |
Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
Depositing User: | Symplectic Admin |
Date Deposited: | 29 Jun 2015 07:46 |
Last Modified: | 31 Mar 2016 12:52 |
URI: | http://livrepository.liverpool.ac.uk/id/eprint/2014940 |
Available Versions of this Item
- On the Efficiency of All-Pay Mechanisms. (deposited 29 Jun 2015 07:46) [Currently Displayed]