To refer to this page use: http://arks.princeton.edu/ark:/88435/pr11v8v
 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