Christodoulou, George, Sgouritsa, Alkmini and Tang, Bo
(2018)
On the Efficiency of All-Pay Mechanisms.
ALGORITHMICA, 80 (4).
pp. 1115-1145.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
2017-05-12T17:53:04Z.atom - Unspecified Download (22kB) |
|
Text
allpay.pdf - Author Accepted Manuscript Download (433kB) |
|
Text
2017-05-12T18:07:11Z.atom - Unspecified Download (22kB) |
|
Text
2017-05-12T18:46:11Z.atom - Unspecified Download (0B) |
|
Text
2017-05-12T19:47:11Z.atom - Unspecified Download (0B) |
|
Text
2017-05-12T20:46:12Z.atom - Unspecified Download (0B) |
|
Text
2017-05-12T21:46:21Z.atom - Unspecified Download (0B) |
|
Text
2017-05-12T22:47:44Z.atom - Unspecified Download (0B) |
|
Text
2017-05-12T23:54:24Z.atom - Unspecified Download (0B) |
|
Text
2017-05-13T01:49:07Z.atom - Unspecified Download (0B) |
|
Text
2017-05-13T02:47:36Z.atom - Unspecified Download (0B) |
|
Text
2017-05-13T03:47:41Z.atom - Unspecified Download (0B) |
|
Text
2017-05-13T05:12:03Z.atom - Unspecified Download (0B) |
|
Text
2017-05-13T05:47:51Z.atom - Unspecified Download (0B) |
|
Text
2017-05-13T06:46:38Z.atom - Unspecified Download (0B) |
|
Text
2017-05-13T07:47:06Z.atom - Unspecified Download (0B) |
|
Text
2017-05-13T08:47:54Z.atom - Unspecified Download (0B) |
|
Text
2017-05-13T09:46:43Z.atom - Unspecified Download (0B) |
Abstract
We study the inefficiency of mixed Nash 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 <i>m</i> all-pay auctions run in parallel, one for each good. For fractionally subadditive valuations, we strengthen the upper bound from 2 (Syrgkanis and Tardos in Proceedings of the 45th symposium on theory of computing (STOC '13), 2013) to 1.82 by proving some structural 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 mixed Nash equilibria in mechanisms used for multi-unit auctions. Finally, we analyze single-item all-pay auctions motivated by their connection to contests and show tight bounds on the price of anarchy with respect to social welfare, revenue and maximum bid.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Nash equilibrium, Price of anarchy, All-pay auction |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 15 May 2017 06:20 |
| Last Modified: | 08 Feb 2024 10:12 |
| DOI: | 10.1007/s00453-017-0296-2 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3007448 |
Dimensions
Dimensions
