Robustly Leveraging Collusion in Combinatorial Auctions

Because of its devastating effects in auctions and other mechanisms, collusion is prohibited andlegally prosecuted. Yet, colluders have always existed, and may continue to exist. We thus raise the followingquestion for mechanism design:What desiderata are achievable, and by what type of mechanisms, when any set of players who wish tocollude are free to do so without any restrictions on the way in which they cooperate and coordinate theiractions?In response to this question we put forward and exemplify the notion of a collusion-leveraging mechanism. Inessence, this is a mechanism aligning its desiderata with the incentives of all its players, including colluders, toa significant and mutually beneficial extent. Of course such mechanisms may exist only for suitable desiderata.In unrestricted combinatorial auctions, where classical mechanisms essentially guarantee 0 social welfare and 0revenue in the presence of just two colluders, we prove that it is possible for collusion-leveraging mechanisms toguarantee that the sum of social welfare and revenue is always high, even when all players are collusive.To guarantee better performance, collusion-leveraging mechanisms in essence “welcome" collusive players, ratherthan pretending they do not exist, raising a host of new questions at the intersection of cooperative and noncooperativegame theory.