Despite its advantages, VCG has many shortcomings [1], including vulnerability to collusion [20]. Collusion and anti-competitive behavior occur in many domains, and many of its forms are illegal [20]. Avoiding collusion has been a key issue in huge auctions, such as the famous FCC auction [10]. A study of collusion in school milk contracts in Florida and Texas [22] considers first price auctions, and shows that the cartels can operate either by dividing the market or using side-payments. Our analysis is also based on side-payments, and [22] indicates such collusion occurs in practice, and is a major problem in real-world auctions.