 Learning in auctions: Regret is hard, envy is easyConstantinos Daskalakis and Vasilis Syrgkanis Games and Economic Behavior, 2022, vol. 134, issue C, 308-343 Abstract: 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⊇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. Keywords: No-regret learning; Simultaneous second price auctions; Combinatorial auction; Efficient learning; Convex rounding (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:134:y:2022:i:c:p:308-343 DOI: 10.1016/j.geb.2022.03.001 Access Statistics for this article Games and Economic Behavior is currently edited by E. Kalai More articles in Games and Economic Behavior from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.