Published in

Proceedings of the 13th ACM Conference on Electronic Commerce - EC '12

DOI: 10.1145/2229012.2229041

Links

Tools

Export citation

Search in Google Scholar

Efficiency of sequential english auctions with dynamic arrivals

Journal article published in 2012 by Olivier Compte, Ron Lavi, Ella Segev
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

We study a setting of online auctions with expiring/perishable items: $K$ items are sold sequentially, buyers arrive over time and have unit-demand. The goal is to maximize the social welfare (sum of winners' values). Most previously suggested mechanisms for this model are direct-revelation. In contrast, in real-life we usually see open mechanisms, most often a sequence of English auctions. We ask whether the previous optimal approximation bounds can be achieved using the more popular/realistic mechanism, or a small variant of it. We observe that a sequence of English auctions (the exact original format) does not guarantee any constant approximation, and describe two variants that bring back the approximation guarantee. In the first variant, the price ascent is stopped when the number of active bidders is equal to the number of remaining items. The winner is chosen from this set of active bidders using some tie-breaking rule. This yields a truthful deterministic 2-approximation. Moreover we show that this ratio is the best possible for any deterministic mechanism that must charge payments at the time of the sale. If the winner is chosen uniformly at random from the set of active bidders, the approximation ratio decreases to frac{e}{e-1} simeq 1.582 (the currently best approximation ratio for this problem). The second variant is to disqualify bidders that quit the auction when the number of active bidders is larger than the number of remaining items, i.e.~to disallow their participation in future auctions. Under the assumption that the true arrival times are observed by the auctioneer (i.e.~values are the only private information) this activity rule again ensures a 2-approximation of the social welfare when players play undominated strategies.