We show that there are no polynomial-time no-regret learning algorithms for simultaneous second price auctions (SiSPAs), unless $RP\supseteq NP$, even when the bidders are unit-demand. We prove this by establishing a specific result about SiSPAs and a generic statement about online learning. We complement this result by proposing a novel solution concept of learning in auctions, termed "no-envy learning". This notion is founded on Walrasian equilibrium, and we show that it is both efficiently computable and it results in approximate efficiency in SiSPAs, even for bidders from the broad class of XOS valuations (assuming demand oracle access to the valuations) or coverage valuations (even without demand oracles). Our result can be viewed as the first constant approximation for welfare maximization in combinatorial auctions with XOS valuations, where both the designer and the agents are computationally bounded. Our positive result for XOS valuations is based on a new class of Follow-The-Perturbed-Leader algorithms and an analysis framework for general online learning problems, which generalizes the existing framework of (Kalai and Vempala 2005) beyond linear utilities. Our results provide a positive counterpart to recent negative results on adversarial online learning via best-response oracles (Hazan and Korren 2015). We show that these results are of interest even outside auction settings, such as in security games of (Balcan et al. 2015). Our efficient learning result for coverage valuations is based on a novel use of convex rounding (Dughmi et al. 2011) and a reduction to online convex optimization.

本研究提出一种称为“无嫉妒学习”的拍卖学习概念，它是建立在 Walras 均衡基础上的，可有效实现且结果达到近似最优福利，即使投标人有分数次可减（XOS）估值或覆盖估值（无需具备要求），同时扩展到其他在文献中研究过的拍卖格式。

拍卖中的学习：遗憾很难，嫉妒很容易