Honor Among Thieves Collusion in Multi-Unit Auctions

Content Provider	Microsoft Research
Author	Bachrach, Yoram
Copyright Year	2010
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.
Language	English
Publisher	AAMAS 2010
Publisher Date	2010-01-01
Access Restriction	Open
Rights Holder	Microsoft Corporation
Subject Keyword	Economics computation
Content Type	Text
Resource Type	Proceeding