Abstract

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 manipula-tion. We say that a choice rule is monotonic if an alternative cannot get itself selected by losing on purpose, and 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 nonma-nipulable, and onto the set of alternatives, for any number of alternatives besides three.