2026-07-26T16:44:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2560 2024-03-06T11:09:13Z ddc:004 open_access

Nonmanipulable Selections from a Tournament Altman, Alon Procaccia, Ariel D. Tennenholtz, Moshe Tournament manipulation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alon Altman and Ariel D. Procaccia and Moshe Tennenholtz 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 10101, Computational Foundations of Social Choice (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.10101.5 urn:nbn:de:0030-drops-25607 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10101.5 eng https://creativecommons.org/licenses/by/4.0/legalcode