Condorcet-consistent and approximately strategyproof tournament rules

DOI10.4230/LIPICS.ITCS.2017.35MaRDI QIDQ4638087zbMATH OpenOpenAlexFDO

Authors Jon Schneider, Ariel Schvartzman, S. Matthew Weinberg

Publication date 3 May 2018

Full work available at URL https://arxiv.org/abs/1605.09733

zbMATH Keywords

Condorcet-consistentnon-manipulabilitystrategyproofnesstournament design

Mathematics Subject Classification ID

Social choice (91B14)

Abstract: We consider the manipulability of tournament rules for round-robin tournaments of $n$ competitors. Specifically, $n$ competitors are competing for a prize, and a tournament rule $r$ maps the result of all $$ pairwise matches (called a tournament, $T$) to a distribution over winners. Rule $r$ is Condorcet-consistent if whenever $i$ wins all $n-1$ of her matches, $r$ selects $i$ with probability $1$. We consider strategic manipulation of tournaments where player $j$ might throw their match to player $i$ in order to increase the likelihood that one of them wins the tournament. Regardless of the reason why $j$ chooses to do this, the potential for manipulation exists as long as $Pr[r(T)=i]$ increases by more than $Pr[r(T)=j]$ decreases. Unfortunately, it is known that every Condorcet-consistent rule is manipulable (Altman and Kleinberg). In this work, we address the question of how manipulable Condorcet-consistent rules must necessarily be - by trying to minimize the difference between the increase in $Pr[r(T)=i]$ and decrease in $Pr[r(T)=j]$ for any potential manipulating pair. We show that every Condorcet-consistent rule is in fact $1/3$-manipulable, and that selecting a winner according to a random single elimination bracket is not $alpha$-manipulable for any $alpha>1/3$. We also show that many previously studied tournament formats are all $1/2$-manipulable, and the popular class of Copeland rules (any rule that selects a player with the most wins) are all in fact $1$-manipulable, the worst possible. Finally, we consider extensions to match-fixing among sets of more than two players.

Recommendations

• Strategic manipulations in round-robin tournaments
• Manipulating Tournaments in Cup and Round Robin Competitions
• Can strategizing in round-robin subtournaments be avoided?
• Strategic manipulation in tournament games
• Knockout tournaments

Cites work

• Can strategizing in round-robin subtournaments be avoided?
• Choosing from a tournament
• Condorcet Social Choice Functions
• Covering sets and a new Condorcet choice correspondence
• Cyclic tournaments and cooperative majority voting: A solution
• Handbook of Computational Social Choice
• How hard is it to control an election?
• Manipulation of Schemes that Mix Voting with Chance
• Manipulation of Voting Schemes: A General Result
• Ranking the Participants in a Tournament
• Social Choice Scoring Functions
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• Tournament solutions and majority voting
• Who can win a single-elimination tournament?

Cited in

(14)

• Are serial Condorcet rules strategy-proof?
• Sophisticated voting rules: The case of two tournaments
• Manipulating Tournaments in Cup and Round Robin Competitions
• Can strategizing in round-robin subtournaments be avoided?
• Knockout tournaments
• Strategic manipulation in tournament games
• Who can win a single-elimination tournament?
• Strategic manipulations in round-robin tournaments
• Tight bounds on 3-team manipulations in randomized death match
• On incentive compatible competitive selection protocols
• Constant-approximate and constant-strategyproof two-facility location
• Toward fair and strategyproof tournament rules for tournaments with partially transferable utilities
• On approximately strategy-proof tournament rules for collusions of size at least three
• Approximately strategyproof tournament rules in the probabilistic setting

This page was built for publication: Condorcet-consistent and approximately strategyproof tournament rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638087)