首页|Learning in auctions: Regret is hard, envy is easy
Learning in auctions: Regret is hard, envy is easy
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
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.
No-regret learningSimultaneous second price auctionsCombinatorial auctionEfficient learningConvex roundingCOMBINATORIAL AUCTIONSRANDOMIZED MECHANISMSALGORITHMS
NSTL
Elsevier
