Bandit Learning Boosts Procurement Auction Efficiency with Near-Optimal Regret
Harvard researchers design truthful auction mechanisms that learn product values from feedback, beating prior limits.
Yiling Chen, Shi Feng, and Sadie Zhao introduce two mechanisms for repeated contextual procurement auctions with bandit feedback. Their explore-then-commit mechanism achieves \(\widetilde O((ng)^{1/3}T^{2/3})\) regret. Their frozen-payment UCB mechanism offers a tradeoff: near-UCB tuning yields \(\widetilde O(\sqrt{ngT})\) welfare regret with \(\widetilde O(T^{3/4})\) incentive error; balanced tuning gives \(\widetilde O(T^{2/3})\) on both. Regret is measured as welfare loss relative to the full-information efficient allocation. They also prove a matching lower bound for the frozen-payment regret-incentive tradeoff.
- Explore-then-commit mechanism achieves regret O~((ng)^{1/3} T^{2/3}) with exact truthfulness.
- Frozen-payment UCB with near-UCB tuning yields O~(√(ngT)) welfare regret but O~(T^{3/4}) incentive error.
- Balanced tuning gives O~(T^{2/3}) on both regret and incentive error, proven optimal via lower bound.
Why It Matters
Enables platforms to run efficient, truthful procurement auctions without prior knowledge of product values.