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.4
URN: urn:nbn:de:0030-drops-11658
Go to the corresponding Portal

Conitzer, Vincent

Anonymity-Proof Voting Rules

07271.ConitzerVincent.Paper.1165.pdf (0.2 MB)


A (randomized, anonymous) voting rule maps any multiset of total orders of
(aka. votes over) a fixed set of alternatives to a probability distribution over these alternatives. A voting rule f is neutral if it treats all alternatives symmetrically. It satisfies participation if no voter ever benefits from not casting her vote. It is falsename-proof if no voter ever benefits from casting additional (potentially different)
votes. It is anonymity-proof if it satisfies participation and it is false-name-proof. We
show that the class of anonymity-proof neutral voting rules consists exactly of the
rules of the following form. With some probability kf in [0, 1], the rule chooses an
alternative at random. With probability 1-kf , the rule first draws a pair of alternatives
at random. If every vote prefers the same alternative between the two (and there
is at least one vote), then the rule chooses that alternative. Otherwise, the rule flips a
fair coin to decide between the two alternatives.

BibTeX - Entry

  author =	{Conitzer, Vincent},
  title =	{{Anonymity-Proof Voting Rules}},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--15},
  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 =		{},
  URN =		{urn:nbn:de:0030-drops-11658},
  doi =		{10.4230/DagSemProc.07271.4},
  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