License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-11569
URL: http://drops.dagstuhl.de/opus/volltexte/2007/1156/
Go to the corresponding Portal


Conitzer, Vincent

Limited Verification of Identities to Induce False-Name-Proofness

pdf-format:
Document 1.pdf (189 KB)


Abstract

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 identi- fiers. 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.

BibTeX - Entry

@InProceedings{conitzer:DSP:2007:1156,
  author =	{Vincent Conitzer},
  title =	{Limited Verification of Identities to Induce False-Name-Proofness},
  booktitle =	{Computational Social Systems and the Internet},
  year =	{2007},
  editor =	{Peter Cramton and Rudolf M{\"u}ller and Eva Tardos and Moshe Tennenholtz },
  number =	{07271},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/1156},
  annote =	{Keywords: Mechanism design, social choice, false-name-proofness, verifying identities, combinatorial auctions}
}

Keywords: Mechanism design, social choice, false-name-proofness, verifying identities, combinatorial auctions
Seminar: 07271 - Computational Social Systems and the Internet
Issue Date: 2007
Date of publication: 02.10.2007


DROPS-Home | Fulltext Search | Imprint Published by LZI