When Bribes are Harmless: The Power and Limits of Collusion-Resilient Mechanism Design

Abstract

Collusion has long been the Achilles heel of mechanism design, as most results break down when participating agents can collude. The issue is more severe when monetary transfers (bribes) between agents are feasible, wherein it is known that truthful revelation and efficient allocation are incompatible. A natural relaxation that circumvents these impossibility results is that of coalitional dominance: replacing truthful revelation with the weaker requirement that all coalitions, whatever they may be, have dominant strategies. When a mechanism satisfies this property and is efficient, we call it collusion resilient. The goal of this paper is to characterize the power and limits of collusion resilient mechanisms.

On the positive side, in a general allocation setting, we demonstrate a new mechanism which is collusion-resilient for surplus-submodular settings – a large-class of problems which includes combinatorial auctions with gross substitutes valuations. We complement this mechanism with two impossibility results: (1) for combinatorial auctions with general submodular valuations, we show that no mechanism can be collusion-resilient, and (2) for the problem of collective decision making, we argue that any non-trivial approximation of welfare is impossible under coalitional dominance. Finally, we make a connection between collusion resilience and false-name-proofness, and show that our impossibility theorems strengthen existing results for false-name-proof mechanisms.