Tournament rules improve resistance to strategic match fixing
How Well Can Strategyproof Tournament Rules Resist Pairwise Manipulation?
Computer Science and Game Theory
Summary
Some systems choose a winner based on pairwise matches between teams, but teams can sometimes change outcomes to improve their chances unfairly. The authors study how well different tournament rules prevent teams or small groups from manipulating results to their benefit. They show that a rule called Randomized Death Match limits the gain from such cheating to a certain factor and that their new rule, BlockBonusedWinStrengths, resists manipulation even better while still being fair. This helps design competitions where cheating offers less advantage, making outcomes more trustworthy.
tournament ruleCondorcet consistencymonotonicitymanipulation resistancecoalitionpairwise matchesstrategyproofnessRandomized Death MatchBlockBonusedWinStrengthsnon-manipulability measures
Authors
Ke Ding, Bo Li, Fangxiao Wang
Abstract
A tournament rule maps the outcomes of all pairwise matches among $n$ teams to a possibly randomized winner. Desirable rules should be Condorcet consistent and monotone, yet also resistant to manipulation among coalition. Prior work mostly measures such manipulation additively through $k$-strongly non-manipulable at $α$ ($k$-SNM-$α$), meaning that no coalition of size $k$ can fix the matches among themselves to increase their total winning probability by $α$. Very recently, two new notions of non-manipulability were introduced. Multiplicative non-manipulability ($k$-MNM-$δ$) is defined analogously, using the multiplicative factor instead. Non-manipulability for $λ$ ($k$-NM$_λ$) characterizes the selfishness of a team, which restricts a coalition's gain to be less than $λ$ times the winning probability sacrificed by its members. In this work, we begin with a strict hierarchy among these three notions: NM$_λ$ is stronger than MNM, which is then stronger than SNM. This motivates us to consider those two notions that are stronger but less studied: pairwise multiplicative non-manipulability and $2$-non-manipulability for $λ$. We show that Randomized Death Match is $2$-MNM-$3/2$ and optimally matches the lower bound. Then, we introduce the BlockBonusedWinStrengths rule, which is Condorcet consistent, monotone, and $2$-NM$_2$. This rule substantially improves the previous upper bound of $λ=11$ and comes within a factor of two of the lower bound $λ=1$.