Collusion-resistant mechanisms for single-parameter agents

Andrew V. Goldberg*, Jason D. Hartline

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

51 Scopus citations

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 strat-egyproofness.

Original languageEnglish (US)
Title of host publicationProceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Pages620-629
Number of pages10
StatePublished - Jul 1 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC
Period1/23/051/25/05

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Collusion-resistant mechanisms for single-parameter agents'. Together they form a unique fingerprint.

  • Cite this

    Goldberg, A. V., & Hartline, J. D. (2005). Collusion-resistant mechanisms for single-parameter agents. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 620-629)