Learning about Auctions
summary
Reconstructs bidder preferences and the allocator from only which bidders show up and who wins, with two concrete models and provable mistake bounds. For single-item pairwise arrivals the problem matches n log n lower/upper limits; for combinatorial single-minded bidders it learns the conflict graph and priority order with n^2 mistakes (optimal) via an online decision-list style update and edge deletions. Unit-demand with observed allocations reduces to an nm universe giving ~n m log m bounds or a faster hybrid using ellipsoid/separation oracle updates. For stochastic bids the Kaplan–Meier estimator recovers distributions above the observable threshold by setting reserve prices and using participatory samples.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 1:20Random observations
- 2:37Multiagent interactions
- 4:26Repeated auction in
- 6:03Re recoverable
- 7:04deterministic
- 21:15Unit Demand
- 29:34Bayesian Model
- 38:01Extended Models
related talks
27mEconometrics for Learning Agents
40mOnline Ad Allocation: Robust Optimization for Repeated Auctions
19mMarket Algorithms for Autobidding
32mLearning Reserve Prices in Second-Price Auctions
01h 07mMulti-Dimensional and Non-Linear Mechanism Design and Approximation I
01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
04mOn gradient-based methods for finding game-theoretic equilibria
29mIndividual Fairness in Advertising Auctions through Inverse Proportionality