Name
Abstract | ||
|---|---|---|
This work obtains truthful mechanisms that aim at maximizing both the revenue and the economic efficiency (social welfare) of unit-demand auctions. In a unit-demand auction a set of k items is auctioned to a set of n consumers, and although each consumer bids on all items, no consumer can purchase more than one item. We present a framework for devising polynomial-time randomized truthful mechanisms that are based on a new variant of the Vickrey-Clarke-Groves (VCG) mechanism. Instead of using reserve prices, this variant of VCG uses the number of objects that we wish to sell as a parameter. Our mechanisms differ in their selection of the number of items to be sold, and allow an interesting trade-off between revenue and economic efficiency, while improving upon the state-of-the-art results for the Unit-Demand Auctions problem (Guruswami et. al.[SODA 2005]). Our probabilistic results depend on what we call the competitiveness of the auction, i.e., the minimum number of items that need to be sold in order to obtain a certain fraction of the maximum efficiency. We denote by ${\mathcal T}$ the optimal efficiency achieved by the VCG mechanism. Our efficiency-oriented mechanism achieves $\Omega{(\mathcal T)}$ efficiency and $\Omega({\mathcal T}/ln(min\{k,n\})$ revenue with probability that grows with the competitiveness of the auction. We also show that no truthful mechanism can obtain an $\omega({\mathcal T}/ln(min\{k,n\})$ expected revenue on every set of bids. In fact, the revenue-oriented mechanism we present achieves $\Omega({\mathcal T}/ln(min\{k,n\})$ efficiency and $\Omega({\mathcal T}/ln(min\{k,n\})$ revenue, but the revenue can actually be much higher, even as large as $\Omega({\mathcal T})$ for some bid distributions. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11682462_23 | LATIN |
Keywords | Field | DocType |
social welfare,economic efficiency,polynomial time | Revenue,Discrete mathematics,Combinatorics,Combinatorial auction,Vickrey–Clarke–Groves auction,Common value auction,Omega,Time complexity,Maximum efficiency,Bidding,Mathematics | Conference |
Volume | ISSN | ISBN |
3887 | 0302-9743 | 3-540-32755-X |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Claudson F. Bornstein | 1 | 110 | 10.93 |
| Eduardo Sany Laber | 2 | 229 | 27.12 |
| Marcelo Mas | 3 | 0 | 0.34 |