License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07271.10
URN: urn:nbn:de:0030-drops-11569
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1156/
Go to the corresponding Portal

Conitzer, Vincent

Limited Verification of Identities to Induce False-Name-Proofness

pdf-format:
07271.ConitzerVincent.Paper.1156.pdf (0.2 MB)

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:DagSemProc.07271.10,
  author =	{Conitzer, Vincent},
  title =	{{Limited Verification of Identities to Induce False-Name-Proofness}},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7271},
  editor =	{Peter Cramton and Rudolf M\"{u}ller and Eva Tardos and Moshe Tennenholtz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1156},
  URN =		{urn:nbn:de:0030-drops-11569},
  doi =		{10.4230/DagSemProc.07271.10},
  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
Collection: 07271 - Computational Social Systems and the Internet
Issue Date: 2007
Date of publication: 02.10.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI