Learning Simple Auctions
We present a general framework for proving polynomial sample complexity bounds for the problem of learning from samples the best auction in a class of "simple" auctions. Our framework captures all of the most prominent examples of "simple" auctions, including anonymous and non-anonymous item and bundle pricings, with either a single or multiple buyers. The technique we propose is to break the analysis of auctions into two natural pieces. First, one shows that the set of allocation rules have large amounts of structure; second, fixing an allocation on a sample, one shows that the set of auctions agreeing with this allocation on that sample have revenue functions with low dimensionality. Our results effectively imply that whenever it's possible to compute a near-optimal simple auction with a known prior, it is also possible to compute such an auction with an unknown prior (given a polynomial number of samples).
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Artificial Intelligence and Auction Design
Motivated by online advertising auctions, we study auction design in repeated auctions played by simple Artificial Intelligence algorithms (Q-learning). We find that first-price auctions with no additional feedback lead …
Q-LearningOn the Pseudo-Dimension of Nearly Optimal Auctions
This paper develops a general approach, rooted in statistical learning theory, to learning an approximately revenue-maximizing auction from data. We introduce t-level auctions to interpolate between simple auctions, such…
Learning TheoryApproximating Equilibria in Sequential Auctions with Incomplete Information and Multi-Unit Demand
In many large economic markets, goods are sold through sequential auctions. Such domains include eBay, online ad auctions, wireless spectrum auctions, and the Dutch flower auctions. Bidders in these domains face highly c…
Decision MakingContingent Fees in Order Flow Auctions
Many early order flow auction designs handle the payment for orders when they execute on the chain rather than when they are won in the auction. Payments in these auctions only take place when the orders are executed, cr…
Strategizing against No-Regret Learners in First-Price Auctions
We study repeated first-price auctions and general repeated Bayesian games between two players, where one player, the learner, employs a no-regret learning algorithm, and the other player, the optimizer, knowing the lear…