False-name-proof mechanisms for hiring a team

Atsushi Iwasaki, David Kempe, Yasumasa Saito, Mahyar Salek, Makoto Yokoo

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

6 Citations (Scopus)


We study the problem of hiring a team of selfish agents to perform a task. Each agent is assumed to own one or more elements of a set system, and the auctioneer is trying to purchase a feasible solution by conducting an auction. Our goal is to design auctions that are truthful and false-name-proof, meaning that it is in the agents' best interest to reveal ownership of all elements (which may not be known to the auctioneer a priori) as well as their true incurred costs.We first propose and analyze a false-name-proof mechanism for the special cases where each agent owns only one element in reality. We prove that its frugality ratio is bounded by n2n, which nearly matches a lower bound of Ω(2n) for all false-name-proof mechanisms in this scenario. We then propose a second mechanism. It requires the auctioneer to choose a reserve cost a priori, and thus does not always purchase a solution. In return, it is false-name-proof even when agents own multiple elements. We experimentally evaluate the payment (as well as social surplus) of the second mechanism through simulation.

Original languageEnglish
Title of host publicationInternet and Network Economics - Third International Workshop, WINE 2007, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540771043
Publication statusPublished - 2007
Event3rd International Workshop on Internet and Network Economics, WINE 2007 - San Diego, CA, United States
Duration: Dec 12 2007Dec 14 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4858 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Workshop on Internet and Network Economics, WINE 2007
Country/TerritoryUnited States
CitySan Diego, CA

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'False-name-proof mechanisms for hiring a team'. Together they form a unique fingerprint.

Cite this