Designing Collusion Resistant Mechanisms

Jason Hartline
Microsoft Research


Wednesday, February 2, 2005
4:45 - 5:45 PM
Terman Engineering Center, Room 453


Abstract:

We consider the problem of designing mechanisms with the incentive property that no coalition of agents can engage in a collusive strategy that results in an increase in the combined utility of the coalition. For single parameter agents, we give a characterization that essentially restricts such mechanisms to those that post a "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 generalized these results to give a methodology for designing collusion resistant mechanisms for single parameter agents. In addition, we give several results for a weaker incentive property from the literature known as *group strategyproofness*. This is joint work with Andrew Goldberg.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html