Prior-free multi-unit auctions with ordered bidders
<p>Prior-free auctions are robust auctions that assume no distribution over bidders’ valuations and provide worst-case (input-by-input) approximation guarantees. In contrast to previous work on this topic, we pursue good prior-free auctions with non-identical bidders.</p> <p>Prior...
| Hlavní autoři: | , , , , , |
|---|---|
| Médium: | Journal article |
| Jazyk: | English |
| Vydáno: |
Elsevier
2020
|
| _version_ | 1826290185625665536 |
|---|---|
| author | Bhattacharya, S Koutsoupias, E Kulkarni, J Leonardi, S Roughgarden, T Xu, X |
| author_facet | Bhattacharya, S Koutsoupias, E Kulkarni, J Leonardi, S Roughgarden, T Xu, X |
| author_sort | Bhattacharya, S |
| collection | OXFORD |
| description | <p>Prior-free auctions are robust auctions that assume no distribution over bidders’ valuations
and provide worst-case (input-by-input) approximation guarantees. In contrast to previous
work on this topic, we pursue good prior-free auctions with non-identical bidders.</p>
<p>Prior-free auctions can approximate meaningful benchmarks for non-identical bidders only
when sufficient qualitative information about the bidder asymmetry is publicly known. We
consider digital goods auctions where there is a total ordering of the bidders that is known
to the seller, where earlier bidders are in some sense thought to have higher valuations.
We use the framework of Hartline and Roughgarden (STOC’08) to define an appropriate
revenue benchmark: the maximum revenue that can be obtained from a bid vector using
prices that are nonincreasing in the bidder ordering and bounded above by the secondhighest bid. This monotone-price benchmark is always as large as the well-known fixed-price
benchmark F(2)
, so designing prior-free auctions with good approximation guarantees
is only harder. By design, an auction that approximates the monotone-price benchmark
satisfies a very strong guarantee: it is, in particular, simultaneously near-optimal for
essentially every Bayesian environment in which bidders’ valuation distributions have
nonincreasing monopoly prices, or in which the distribution of each bidder stochastically
dominates that of the next. Even when there is no distribution over bidders’ valuations,
such an auction still provides a quantifiable input-by-input performance guarantee.</p>
<p>In this paper, we design a simple O(1)-competitive prior-free auction for digital goods with
ordered bidders. We also extend the monotone-price benchmark and our O(1)-competitive
prior-free auction to multi-unit settings with limited supply.</p> |
| first_indexed | 2024-03-07T02:40:20Z |
| format | Journal article |
| id | oxford-uuid:aa381aba-2008-4d90-af59-8d93fb899c8e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T02:40:20Z |
| publishDate | 2020 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:aa381aba-2008-4d90-af59-8d93fb899c8e2022-03-27T03:13:42ZPrior-free multi-unit auctions with ordered biddersJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:aa381aba-2008-4d90-af59-8d93fb899c8eEnglishSymplectic ElementsElsevier2020Bhattacharya, SKoutsoupias, EKulkarni, JLeonardi, SRoughgarden, TXu, X<p>Prior-free auctions are robust auctions that assume no distribution over bidders’ valuations and provide worst-case (input-by-input) approximation guarantees. In contrast to previous work on this topic, we pursue good prior-free auctions with non-identical bidders.</p> <p>Prior-free auctions can approximate meaningful benchmarks for non-identical bidders only when sufficient qualitative information about the bidder asymmetry is publicly known. We consider digital goods auctions where there is a total ordering of the bidders that is known to the seller, where earlier bidders are in some sense thought to have higher valuations. We use the framework of Hartline and Roughgarden (STOC’08) to define an appropriate revenue benchmark: the maximum revenue that can be obtained from a bid vector using prices that are nonincreasing in the bidder ordering and bounded above by the secondhighest bid. This monotone-price benchmark is always as large as the well-known fixed-price benchmark F(2) , so designing prior-free auctions with good approximation guarantees is only harder. By design, an auction that approximates the monotone-price benchmark satisfies a very strong guarantee: it is, in particular, simultaneously near-optimal for essentially every Bayesian environment in which bidders’ valuation distributions have nonincreasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next. Even when there is no distribution over bidders’ valuations, such an auction still provides a quantifiable input-by-input performance guarantee.</p> <p>In this paper, we design a simple O(1)-competitive prior-free auction for digital goods with ordered bidders. We also extend the monotone-price benchmark and our O(1)-competitive prior-free auction to multi-unit settings with limited supply.</p> |
| spellingShingle | Bhattacharya, S Koutsoupias, E Kulkarni, J Leonardi, S Roughgarden, T Xu, X Prior-free multi-unit auctions with ordered bidders |
| title | Prior-free multi-unit auctions with ordered bidders |
| title_full | Prior-free multi-unit auctions with ordered bidders |
| title_fullStr | Prior-free multi-unit auctions with ordered bidders |
| title_full_unstemmed | Prior-free multi-unit auctions with ordered bidders |
| title_short | Prior-free multi-unit auctions with ordered bidders |
| title_sort | prior free multi unit auctions with ordered bidders |
| work_keys_str_mv | AT bhattacharyas priorfreemultiunitauctionswithorderedbidders AT koutsoupiase priorfreemultiunitauctionswithorderedbidders AT kulkarnij priorfreemultiunitauctionswithorderedbidders AT leonardis priorfreemultiunitauctionswithorderedbidders AT roughgardent priorfreemultiunitauctionswithorderedbidders AT xux priorfreemultiunitauctionswithorderedbidders |