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

Altman, Alon ; Procaccia, Ariel D. ; Tennenholtz, Moshe

Nonmanipulable Selections from a Tournament

Document 1.pdf (142 KB)


A tournament is a binary dominance relation on a set of alternatives. Tournaments arise in many contexts that are relevant to AI, most notably in voting (as a method to aggregate the preferences of agents). There are many works that deal with choice rules that select a desirable alternative from a tournament, but very few of them deal directly with incentive issues, despite the fact that game-theoretic considerations are crucial with respect to systems populated by selfish agents. We deal with the problem of the manipulation of choice rules by considering two types of manipulation. We say that a choice rule is emph{monotonic} if an alternative cannot get itself selected by losing on purpose, and emph{pairwise nonmanipulable} if a pair of alternatives cannot make one of them the winner by reversing the outcome of the match between them. Our main result is a combinatorial construction of a choice rule that is monotonic, pairwise nonmanipulable, and onto the set of alternatives, for any number of alternatives besides three.

BibTeX - Entry

  author =	{Alon Altman and Ariel D. Procaccia and Moshe Tennenholtz},
  title =	{Nonmanipulable Selections from a Tournament},
  booktitle =	{Computational Foundations of Social Choice},
  year =	{2010},
  editor =	{Felix Brandt and Vincent Conitzer and Lane A. Hemaspaandra and Jean-Francois Laslier and William S. Zwicker},
  number =	{10101},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2560},
  annote =	{Keywords: Tournament, manipulation}

Keywords: Tournament, manipulation
Seminar: 10101 - Computational Foundations of Social Choice
Issue Date: 2010
Date of publication: 20.05.2010

DROPS-Home | Fulltext Search | Imprint Published by LZI