Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Honor Among Thieves — Collusion in Multi-Unit Auctions

Yoram Bachrach

Abstract

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.

Details

Publication typeInproceedings
Published inAAMAS 2010
> Publications > Honor Among Thieves — Collusion in Multi-Unit Auctions