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.|
|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|
|Pages:||305 - 322|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||ACM Conference on Economics and Computation|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.