When quoting this document, please refer to the following
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 =	{Vincent Conitzer},
  title =	{Anonymity-Proof Voting Rules},
  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 =		{},
  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