Christodoulou, George, Sgouritsa, Alkmini and Tang, Bo
(2015)
On the Efficiency of All-Pay Mechanisms.
.
This is the latest version of this item.
Text
allpay.pdf - Author Accepted Manuscript Download (496kB) |
|
Text
allpay.pdf - Author Accepted Manuscript Download (343kB) |
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 [Syrgkanis and Tardos STOC'13] 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 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 of social welfare, revenue and maximum bid.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Additional Information: | 26 pages, 2 figures, European Symposium on Algorithms(ESA) 2015 |
Uncontrolled Keywords: | cs.GT, cs.GT |
Subjects: | ?? QA75 ?? |
Depositing User: | Symplectic Admin |
Date Deposited: | 08 Jun 2016 09:43 |
Last Modified: | 19 Jan 2023 07:36 |
DOI: | 10.1007/978-3-662-48350-3_30 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3001549 |
Available Versions of this Item
-
On the Efficiency of All-Pay Mechanisms. (deposited 29 Jun 2015 07:46)
-
On the Efficiency of All-Pay Mechanisms. (deposited 20 Jul 2015 08:26)
- On the Efficiency of All-Pay Mechanisms. (deposited 08 Jun 2016 09:43) [Currently Displayed]
-
On the Efficiency of All-Pay Mechanisms. (deposited 20 Jul 2015 08:26)