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.
from cs.AI updates on arXiv.org http://ift.tt/1MB08ux
via IFTTT
No comments:
Post a Comment