How Well Can Strategyproof Tournament Rules Resist Pairwise Manipulation?

1 Introduction

• Tournament rules map pairwise match outcomes to winner probabilities and are judged by fairness, monotonicity, and resistance to coalitions changing their internal matches.Condorcet consistency selects an undefeated team with probability one when one exists; monotonicity means a team is not rewarded for throwing a game.Source: §1 · p. 1
• Earlier work left 2-MNM-7/2 against a lower bound of 3/2 and 2-NMλ upper and lower bounds of 11 and 1, respectively.Pennock et al. [12] provided the 2-MNM-7/2 rule and the first constant-λ rule, with λ = 11.Source: §1 · p. 2

1.1 Contribution

• Every k-NMλ rule implies k-MNM-(1 + λ), which implies k-SNM-λ/(1 + λ), but neither converse holds even for k = 2.This hierarchy shows that MNM and NMλ are more demanding than the additive SNM notion.Source: §1.1 · p. 2
• Randomized Death Match is Condorcet consistent, monotone, and 2-MNM-3/2 for every tournament, matching the optimal factor among Condorcet-consistent rules.The rule recursively selects a random pair of surviving teams and eliminates the loser of their recorded match.Source: §1.1 · p. 3
• BlockBonusedWinStrength is Condorcet consistent, monotone, and 2-NM2 for every tournament, with a tight λ = 2 guarantee.It combines geometric scores based on win counts with scores from defeated teams, then bonuses blockers to increase their winning probability.Source: §1.1 · p. 3

1.2 Related Work

• For pairwise collusion, several Condorcet-consistent, monotone rules are 2-SNM-1/3, with optimal additive constant 1/3; much less is known for coalitions of size k > 2.A Condorcet-consistent, monotone 3-SNM-1/2 rule and explicit k-SNM-α rules with α < 1 for every k were later constructed.Source: §1.2 · p. 3

• A randomized tournament rule maps each tournament to a probability distribution over the teams.Source: §2 · p. 4
• Condorcet consistency selects an undefeated team with probability one, while monotonicity prevents a team from benefiting by throwing a match.Source: §2 · p. 4
• k-SNM-α bounds a coalition’s gain in joint winning probability by an additive α when it fixes matches among its members.Source: §2 · pp. 4–5
• k-MNM-δ instead bounds that gain multiplicatively, while k-NMλ limits it relative to members’ sacrificed winning probabilities.Source: §2 · pp. 4–5
• A directed three-team cycle establishes Condorcet-consistent lower bounds of 1/3 for 2-SNM-α, 3/2 for 2-MNM-δ, and 1 for 2-NMλ.Reversing any edge makes a team a Condorcet winner.Source: §2 · p. 5, Figure 1 · p. 5

• k-NMλ implies k-MNM-(1 + λ), which implies k-SNM-λ/(1 + λ), without requiring Condorcet consistency or monotonicity.Source: §3 · p. 6
• The first conversion bounds manipulation using the coalition’s total sacrificed probability, which cannot exceed its initial joint winning probability.Source: §3 · p. 6
• The reverse implications fail even for monotone rules and coalitions of size two: an additive guarantee can permit gains from zero, unlike a multiplicative guarantee.Source: §3 · p. 6
• The Normalized Geometric Win Count Score rule is 2-MNM-7/2 but is not 2-NMλ for any λ = o(n).Source: §3 · p. 6
• These distinctions motivate designing rules with optimal pairwise multiplicative guarantees and smaller pairwise λ guarantees.Source: §3 · p. 6

• Randomized Death Match repeatedly selects a surviving pair uniformly at random, eliminates the loser, and selects the last remaining team.Source: §4 · p. 7
• The proof expresses coalition winning probability through possible first eliminations and uses induction to compare tournaments differing only in the coalition’s match.It handles the cases according to the number of losses of one coalition member.Source: §4 · pp. 7–8
• When that member has exactly one loss, deleting the unique team that defeats it restores a Condorcet winner and supplies the needed probability bound.Source: §4 · p. 8
• 2-MNM-3/2 is achieved by Randomized Death Match for every tournament, and 3/2 is optimal among Condorcet-consistent rules.The rule is also Condorcet consistent and monotone.Source: §4 · pp. 7–8

5 Non-Manipulability for λ = 2

• The rule starts from win-strength scores based on each team’s wins and the win counts of teams it defeats, then adds bonuses to blockers of almost-Condorcet winners.Almost-Condorcet winners have exactly one loss, and there are at most three; the bonus assignments depend on their number and blocker roles.Source: §5 · p. 9
• 2-NM2, Condorcet consistency, and monotonicity hold for BlockBonusedWinStrength on every tournament, and its 2-NM2 guarantee is tight.The proof combines the gain–loss bounds with separate well-definedness and monotonicity arguments.Source: §5 · pp. 9, 14
• Rule 2 normalizes scores into winning probabilities, and Lemma 6 establishes that it defines a probability distribution on every tournament.When a Condorcet winner exists, the rule assigns that team probability one; otherwise it normalizes the scores.Source: §5 · p. 9
• The manipulation proof compares the scaled loss of the team whose match is reversed with the other team’s scaled gain, first for unbonused scores and then for full scores.For unbonused scores, the target is G0 ≤ 3L0; changes in individual and total bonuses then adjust the full loss and gain.Source: §5 · pp. 10–12
• When bonuses change, the proof enumerates feasible transitions in almost-Condorcet winners and blocker roles, establishing G ≤ 3L when neither tournament has a Condorcet winner.If the reversal instead makes the gaining team a Condorcet winner, its probability becomes one and the bonuses support the required gain–loss bound.Source: §5 · pp. 12–13, Table 2 · p. 12
• Monotonicity follows by showing that a team’s winning probability does not increase when it loses the reversed match, including transitions where bonuses decrease its scaled loss.The proof treats Condorcet-winner cases separately and establishes the remaining transitions in Lemma 12.Source: §5 · pp. 13–14
• Rule 2 is not 2-NMλ for any λ < 2; as m → ∞, ti(Tm) → 1 + B and tj(Tm) → 3/2, while each team’s uniform share of the remaining probability mass tends to zero.Source: §5 · p. 14

6 Conclusion

• The Randomized Death Match rule is 2-MNM-3/2, the first known to match the universal lower bound; a novel rule satisfies 2-non-manipulability for λ = 2, improving the best-known upper bound of λ = 11.Source: §6 · p. 14
• The results leave open the gap between the 2-NM_λ guarantee at λ = 2 and the conjectured lower bound λ = 1.The authors also identify larger coalitions and tournaments where not every pair plays as directions for future study.Source: §6 · p. 14

AI Disclosure

• GPT 5.6 Sol assisted with parameter calculation, figure visualization, and typo checking, and materially affected Section 5.The authors state that they verified the correctness and originality of all content, including references.Source: AI Disclosure · p. 14

A Illustrations of the Bonus Transitions

• The diagrams mark the i-to-j outcome with a thicker arrow and highlight almost-Condorcet winners; accompanying tables give win counts and bonus transitions for displayed teams.A dash indicates an omitted annotation, and match outcomes not drawn are unspecified.Source: A Illustrations of the Bonus Transitions · p. 17
• In case (b), j enters H as the transition changes from 0 to 1; in case (c), i leaves H as it changes from 1 to 0.The case (d) illustration shows j replacing i in H while the transition remains 1 to 1.Source: Figure 5 · p. 17, Figure 6 · p. 17, Figure 7 · p. 17
• In cases (e1)–(e3), the transition is 1 to 2: j’s bonus changes from B to P, i’s from B to Q, or an old blocker ℓ outside {i, j} is involved.The figure descriptions distinguish the old-blocker case from the bonus changes.Source: Figure 8 · p. 17, Figure 9 · p. 17, Figure 10 · p. 17
• In cases (f1)–(f3), the transition is 2 to 1: i’s bonus changes from P to B, j as external blocker changes from Q to B, or blocker ℓ lies outside {i, j}.Source: Figure 11 · p. 18, Figure 12 · p. 18, Figure 13 · p. 18
• Case (h) changes from 2 to 3 with j’s bonus moving from Q to R, while case (i) changes from 3 to 2 with i’s bonus moving from R to Q.Source: Figure 17 · p. 18, Figure 18 · p. 18
• In cases (g1)–(g3), the transition remains 2 to 2: i’s bonus changes from P to Q, j’s from Q to P, or coalition members’ bonuses remain unchanged.Source: Figure 14 · p. 18, Figure 15 · p. 18, Figure 16 · p. 18

B.1 Well-Definedness

• Rule 2 defines a probability distribution on every tournament because its remaining probability mass is nonnegative, making every r_i(T) nonnegative.Source: §B.1 · p. 19
• For tournaments without a Condorcet winner, the proof bounds total unbonused win-strength scores using the win counts and losses of teams.It uses Landau’s characterization and discrete convexity to identify a maximizing sequence of win counts.Source: §B.1 · p. 19
• The proof adds the maximum total bonus to the bound on unbonused scores to obtain M, bounding Rule 2’s total assignment.The supplied passage gives the maximum total bonus as P + Q = 43/12; the resulting bound is used to show the residual mass is nonnegative.Source: §B.1 · p. 19

B.2 Properties for Small Tournaments

• When |H(T)| = 1 and |H(T′)| = 0, n = 4 is impossible, and n = 5 with v = 3 is impossible.These restrictions hold when neither tournament has a Condorcet winner.Source: §B.2 · p. 20
• When |H(T)| = 2 and |H(T′)| = 1, n ≥ 5.This restriction holds when neither tournament has a Condorcet winner.Source: §B.2 · p. 20
• In case (f2), n ≥ v + 3.This restriction holds when neither tournament has a Condorcet winner.Source: §B.2 · p. 20

B.3 No-Condorcet Cases under Bonus Transitions

• For every Table 2 case where neither tournament has a Condorcet winner, G ≤ 3L.For several cases, the proof shows that the bonus contribution is nonnegative or zero, while 3L0 − G0 > 0.Source: §B.3 · p. 20

B.4 Condorcet-Creation Cases

• When T has no Condorcet winner and j becomes one in T′, rj(T′) − rj(T) ≤ 3.Rule 2 gives rj(T′) = 1 and ri(T′) = 0, reducing the bound to 1 − rj(T) ≤ 3ri(T).Source: §B.4 · p. 22

B.5 Monotonicity under Bonus Transitions

• If neither T nor T′ has a Condorcet winner, every Table 2 transition satisfies ri(T) ≥ ri(T′).The proof checks the cases where bonuses may contribute negatively and shows that other transitions keep or increase L above L0.Source: §B.5 · p. 23
• Bonuses can reduce L only in cases (c), (f1)–(f3), (h), and (i); other transitions leave L at or above the positive baseline L0.The proof handles the potentially negative cases with separate bounds.Source: §B.5 · p. 23