Learning in Auctions: Regret is Hard, Envy is Easy
  A line of recent work provides welfare guarantees of simple combinatorial
auction formats, such as selling m items via simultaneous second price auctions
(SiSPAs) (Christodoulou et al. 2008, Bhawalkar and Roughgarden 2011, Feldman et
al. 2013). These guarantees hold even when the auctions are repeatedly executed
and players use no-regret learning algorithms. Unfortunately, off-the-shelf
no-regret algorithms for these auctions are computationally inefficient as the
number of actions is exponential. We show that this obstacle is insurmountable:
there are no polynomial-time no-regret algorithms for SiSPAs, unless
RP$\supseteq$ NP, even when the bidders are unit-demand. Our lower bound raises
the question of how good outcomes polynomially-bounded bidders may discover in
such auctions.
  To answer this question, we propose a novel concept of learning in auctions,
termed "no-envy learning." This notion is founded upon Walrasian equilibrium,
and we show that it is both efficiently implementable and results in
approximately optimal welfare, even when the bidders have fractionally
subadditive (XOS) valuations (assuming demand oracles) or coverage valuations
(without demand oracles). No-envy learning outcomes are a relaxation of
no-regret outcomes, which maintain their approximate welfare optimality while
endowing them with computational tractability. Our results extend to other
auction formats that have been studied in the literature via the smoothness
paradigm.
  Our results for XOS valuations are enabled by a novel
Follow-The-Perturbed-Leader algorithm for settings where the number of experts
is infinite, and the payoff function of the learner is non-linear. This
algorithm has applications outside of auction settings, such as in security
games. Our result for coverage valuations is based on a novel use of convex
rounding schemes and a reduction to online convex optimization.
