Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Collusion-Resistant Mechanisms for Single-Parameter Agents

Andrew Goldberg and Jason Hartline

Abstract

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.

Details

Publication typeTechReport
NumberMSR-TR-2004-40
Pages15
InstitutionMicrosoft Research
PublisherACM/SIAM
> Publications > Collusion-Resistant Mechanisms for Single-Parameter Agents