False-name-proof Mechanisms for Hiring a Team
| Autor: | Iwasaki, Atsushi, Kempe, David, Salek, Mahyar, Yokoo, Makoto |
|---|---|
| Rok vydání: | 2011 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 23 pages, 3 figures, This paper is an extented version of "False-name-proof Mechanisms for Hiring a Team" in the Proceedings of the Workshop on Internet and Network Economics, 2007 |
| Databáze: | arXiv |
| Externí odkaz: |
|