Learning in auctions: Regret is hard, envy is easy

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.