Skip to main content

Limited verification of identities to induce false-name-proofness

Publication ,  Conference
Conitzer, V
Published in: Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007
December 1, 2007

In open, anonymous environments such as the Internet, mechanism design is complicated by the fact that a single agent can participate in the mechanism under multiple identifiers. One way to address this is to design false-name-proof mechanisms, which choose the outcome in such a way that agents have no incentive to use more than one identifier. Unfortunately, there are inherent limitations on what can be achieved with false-name-proof mechanisms, and at least in some cases, these limitations are crippling. An alternative approach is to verify the identities of all agents. This imposes significant overhead and removes any benefits from anonymity. In this paper, we propose a middle ground. Based on the reported preferences, we check, for various subsets of the reports, whether the reports in the subset were all submitted by different agents. If they were not, then we discard some of them. We characterize when such a limited verification protocol induces false-name-proofness for a mechanism, that is, when the combination of the mechanism and the verification protocol gives the agents no incentive to use multiple identifiers. This characterization leads to various optimization problems for minimizing verification effort. We study how to solve these problems. Throughout, we use combinatorial auctions (using the Clarke mechanism) and majority voting as examples.

Duke Scholars

Published In

Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007

DOI

Publication Date

December 1, 2007

Start / End Page

102 / 111
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Conitzer, V. (2007). Limited verification of identities to induce false-name-proofness. In Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007 (pp. 102–111). https://doi.org/10.1145/1324249.1324265
Conitzer, V. “Limited verification of identities to induce false-name-proofness.” In Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007, 102–11, 2007. https://doi.org/10.1145/1324249.1324265.
Conitzer V. Limited verification of identities to induce false-name-proofness. In: Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007. 2007. p. 102–11.
Conitzer, V. “Limited verification of identities to induce false-name-proofness.” Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007, 2007, pp. 102–11. Scopus, doi:10.1145/1324249.1324265.
Conitzer V. Limited verification of identities to induce false-name-proofness. Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007. 2007. p. 102–111.

Published In

Proceedings of the 11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007

DOI

Publication Date

December 1, 2007

Start / End Page

102 / 111