Optimal Deterministic Clock Auctions and Beyond
summary
Presents concrete algorithms and tight guarantees: a deterministic water-filling clock auction that provably achieves a 4·log|O| approximation for any downward-closed feasibility constraint (matching the Ω(log n) lower bound from harmonic-style instances), plus a randomized hedging auction that alternates sampling and water-filling to break the logarithmic barrier on disjoint-maximal-set families, giving a min{log|O|, √(log K)} bound and demonstrating practical implementability with only revenue-oracle access.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:15Outline
- 2:41Sealed-Bid Auctions
- 4:19Clock Auctions - Milgrom and Segal EC 2014, JPE
- 5:45Clock Auction Properties Clock auctions have appealing properties making them a more practical solution
- 7:31Formal Setting
- 9:35Our Results
- 10:45Deterministic Lower Bound
- 18:04Beyond Determinism
- 19:26The Sampling Auction
- 21:24The Hedging Auction
- 22:45Conclusions and Open Questions