Robustly Leveraging Collusion in Combinatorial Auctions
Because of its devastating effects in auctions and other mechanisms, collusion is prohibited and legally prosecuted. Yet, colluders have always existed, and may continue to exist. We thus raise the following question for mechanism design: What desiderata are achievable, and by what type of mechanisms, when any set of players who wish to collude are free to do so without any restrictions on the way in which they cooperate and coordinate their actions? In response to this question we put forward and exemplify the notion of a collusion-leveraging mechanism. In essence, this is a mechanism aligning its desiderata with the incentives of all its players, including colluders, to a 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 0 revenue in the presence of just two colluders, we prove that it is possible for collusion-leveraging mechanisms to guarantee 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, rather than pretending they do not exist, raising a host of new questions at the intersection of cooperative and noncooperative game theory.
mechanism design collusion leveraging player-knowledge benchmark and combinatorial auction
Jing Chen Silvio Micali Paul Valiant
CSAIL, MIT, Cambridge, MA 02139, USA Computer Science Division, UC Berkeley, Berkeley, CA 94720, USA
国际会议
The First Symposium on Innovations in Computer Science(2010 计算机科学创新研讨会 ICS 2010)
北京
英文
81-93
2010-01-05（万方平台首次上网日期，不代表论文的发表时间）