How Well Can Strategyproof Tournament Rules Resist Pairwise Manipulation?

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 $\alpha$ ($k$-SNM-$\alpha$), meaning that no coalition of size $k$ can fix the matches among themselves to increase their total winning probability by $\alpha$. Very recently, two new notions of non-manipulability were introduced. Multiplicative non-manipulability ($k$-MNM-$\delta$) is defined analogously, using the multiplicative factor instead. Non-manipulability for $\lambda$ ($k$-NM${}_{\lambda }$) characterizes the selfishness of a team, which restricts a coalition's gain to be less than $\lambda$ times the winning probability sacrificed by its members. In this work, we begin with a strict hierarchy among these three notions: NM${}_{\lambda }$ 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 $\lambda$. 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 $\lambda =11$ and comes within a factor of two of the lower bound $\lambda =1$.

23 Pages