We consider the problem of designing mechanisms that maintain their incentive properties even in the presence of possible collusion among the agents when side payments are allowed. For single parameter agents, we give a characterization that essentially restricts such mechanisms to those that post an "take it or leave it" price to for each agent in advance. We then consider relaxing the incentive property to only hold with high probability. In this relaxed model, we are able to design approximate profit maximizing auctions and approximately efficient auctions. We also give a general framework for designing mechanisms for single parameter agents while maintaining incentive properties with high probability. In addition, we give several results for the case when side payments are disallowed.

PDF file

PostScript file

Publisher: ACM/SIAM

Details