View in EDS

Prior-free multi-unit auctions with ordered bidders.

Saved in:
Bibliographic Details
Title: Prior-free multi-unit auctions with ordered bidders.
Authors: Bhattacharya, Sayan1 (AUTHOR) S.Bhattacharya@warwick.ac.uk, Koutsoupias, Elias1,2 (AUTHOR) elias@cs.ox.ac.uk, Kulkarni, Janardhan1,3 (AUTHOR) Jakul@microsoft.com, Leonardi, Stefano1,4 (AUTHOR) leonardi@dis.uniroma1.it, Roughgarden, Tim1,5 (AUTHOR) tr@cs.columbia.edu, Xu, Xiaoming6 (AUTHOR) xiaomingnatexu@gmail.com
Source: Theoretical Computer Science. Dec2020, Vol. 846, p160-171. 12p.
Subjects: Auctions, Bidders, Linear orderings
Abstract: 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. 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 second-highest 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. 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. [ABSTRACT FROM AUTHOR]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract: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. 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 second-highest 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. 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. [ABSTRACT FROM AUTHOR]
ISSN:03043975
DOI:10.1016/j.tcs.2020.09.030