Skip to main content

Simple Auctions with Simple Strategies

Author(s): Devanur, Nikhil; Morgenstern, Jamie; Syrgkanis, Vasilis; Weinberg, S Matthew

To refer to this page use:
Abstract: We introduce single-bid auctions as a new format for combinatorial auctions. In single-bid auctions, each bidder submits a single real-valued bid for the right to buy items at a fixed price. Contrary to other simple auction formats, such as simultaneous or sequential single-item auctions, bidders can implement no-regret learning strategies for single-bid auctions in polynomial time. Price of anarchy bounds for correlated equilibria concepts in single-bid auctions therefore have more bite than their counterparts for auctions and equilibria for which learning is not known to be computationally tractable (or worse, known to be computationally intractable [Cai and Papadimitriou 2014; Dobzinski et al. 2015] this end, we show that for any subadditive valuations the social welfare at equilibrium is an O(log m)-approximation to the optimal social welfare, where $m$ is the number of items. We also provide tighter approximation results for several subclasses. Our welfare guarantees hold for Nash equilibria and no-regret learning outcomes in both Bayesian and complete information settings via the smooth-mechanism framework. Of independent interest, our techniques show that in a combinatorial auction setting, efficiency guarantees of a mechanism via smoothness for a very restricted class of cardinality valuations extend, with a small degradation, to subadditive valuations, the largest complement-free class of valuations.
Publication Date: Jun-2015
Citation: Devanur, Nikhil, Jamie Morgenstern, Vasilis Syrgkanis, and S. Matthew Weinberg. "Simple Auctions with Simple Strategies." In ACM Conference on Economics and Computation (2015): pp. 305-322. doi:10.1145/2764468.2764484
DOI: 10.1145/2764468.2764484
Pages: 305 - 322
Type of Material: Conference Article
Journal/Proceeding Title: ACM Conference on Economics and Computation
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.