False-name-proof Mechanisms for Hiring a Team

Details False-name-proof Mechanisms for Hiring a Team False-name-proof Mechanisms for Hiring a Team

2011-06-13

arxiv.org/abs/1106.2378v1

Computer Science

Computer Science and Game Theory

23 pages, 3 figures, This paper is an extented version of "False-name-proof Mechanisms for Hiring a Team" in the Proceedings o

Scientific paper

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 case where each agent owns only one element in reality, but may pretend that this element is in fact a set of multiple elements. We prove that its frugality ratio is bounded by $2^n$, which, up to constants, matches a lower bound of $\Omega(2^n)$ for all false-name-proof mechanisms in this scenario. We then propose a second mechanism for the general case in which agents may own multiple elements. 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.

Affiliated with

Also associated with

No associations

Rating

False-name-proof Mechanisms for Hiring a Team does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with False-name-proof Mechanisms for Hiring a Team, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and False-name-proof Mechanisms for Hiring a Team will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-429139