Honor Among Thieves “” Collusion in Multi-Unit Auctions

We consider collusion in multi-unit auctions where the allocation and payments are determined using the VCG mechanism. We show how collusion can increase the utility of the colluders, characterize the optimal collusion and show it can easily be computed in polynomial time. We then analyze the colluders’ coalition from a cooperative game theoretic perspective. We show that the collusion game is a convex game, so it always has a non-empty core, which contains the Shapley value. We show how to find core imputations and compute the Shapley value, and thus show that in this setting the colluders can always share the gain from their manipulation in a stable and fair way. This shows that this domain is extremely vulnerable to collusion.