Learning in auctions: Regret is hard, envy is easy

• 成果类型: Article
• 署名作者: Daskalakis, Constantinos; Syrgkanis, Vasilis
• 署名单位: Massachusetts Institute of Technology (MIT); Microsoft
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2022.03.001
• 发表日期: 2022
• 页码: 308-343
• 关键词: No-regret learning; Simultaneous second price auctions; Combinatorial auction; Efficient learning; Convex rounding

摘要

A large line of recent work studies the welfare guarantees of simple and prevalent combinatorial auction formats, such as selling m items via simultaneous second price auctions (SiSPAs). These guarantees hold even when the auctions are repeatedly executed and the players use no-regret learning algorithms. Unfortunately, off-the-shelf no-regret algorithms for these auctions are computationally inefficient. We show that this obstacle is insurmountable: there are no polynomial-time no-regret algorithms for SiSPAs, unless RP & SUPE; NP, even when bidders are unit-demand. Our lower bound raises the question of how good outcomes polynomially-bounded bidders may discover in such auctions. We propose a novel concept of learning in auctions, termed no-envy learning , and show that it is both efficiently implementable and results in approximately optimal welfare, even when the bidders have valuations from the broad class of fractionally subadditive valuations, assuming demand oracle access to the valuations, or coverage valuations, even without demand oracles.(c) 2022 Elsevier Inc. All rights reserved.