Pith. sign in

REVIEW 3 major objections 4 minor 33 references

Tournament Robustness via Redundancy

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A knockout tournament can be made so that the strongest player wins even if up to a third of the games on every path are rigged, at only polynomial size cost.

desk verdict A novel and clever robustness-via-redundancy construction, but the binary decoder is misdefined as written and the proof of Lemma 11 rests on it. read the letter →

arxiv 2506.03701 v1 pith:AA6NRLO2 submitted 2025-06-04 cs.DM

Klim Efremenko , Hendrik Molter , Meirav Zehavi This is my paper
classification cs.DM
keywords knockouttournamentsmanipulationrobustnesstournamentfixingbriberycommunicationprotocolsfeedbackchanneladversarialnoiseredundancy
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether a knockout tournament can be engineered so that the genuinely strongest player wins even when an adversary flips the outcome of some games. The authors answer yes: for any numbers of players $n$ and manipulations $k$, they construct a binary tournament tree in which each player is assigned to many leaves, and if at most $k$ games on every leaf-to-root path are manipulated, the strongest player still wins. The price is a polynomial increase in tournament size: the tree has height at most $\lceil 1.44 \log_2 n\rceil + 3k$, so tolerating a constant fraction of corrupted games per run costs only a polynomial blow-up. The construction needs no information about which player is strongest and works for every seeding and every winner function that has a strongest player. The key move is to translate a communication protocol with a feedback channel that corrects adversarial noise into the tournament tree, treating each manipulated game as a corrupted transmitted bit.

What carries the argument

The central object is the labeled tournament tree $T_{n,k}$, built by mirroring the feedback-channel communication protocol described in Section 3.2. Each vertex carries a label $(s, f(s), e(s))$: $s$ is the path string, $f$ is the cleanup map that removes the error marker $11$ at the front and the substring $011$ elsewhere, and $e$ counts the removals. The protocol's decoding rule, 'when the received message ends in 11, delete the last three bits,' becomes the tree's branching rule, so a manipulated game flips a bit of $s$ and the next few branches compensate for it. The proof engine is the prefix operation $p_\ell$ together with Observation 10, which describe how the required prefix of the strongest player's seed name shortens as manipulations are consumed; this carries the induction in Lemma 11.

What would settle it

Feed the string $01111$ through the decoding function $f$ exactly as defined in Section 4.3 (first remove a leading $11$, then remove every occurrence of $011$); the output is $11$, which contains consecutive ones, so the claim that $f$ always outputs strings without consecutive ones fails under that literal reading, and checking whether such a string is reachable in the constructed tree settles the proof.

Watch

Extended reading notes

Core claim

The central claim is Theorem 6: given integers $n$ and $k$, a binary tournament tree $T_{n,k}$ of height at most $\lceil 1.44 \log_2 n\rceil + 3k$ can be computed in $O(|T_{n,k}|)$ time such that for every set of $n$ players, every winner function with a strongest player $i_w$, and every seeding, if at most $k$ games on each leaf-to-root path are manipulated, then $i_w$ wins. Redundancy is achieved by letting many leaves share the same seed-position name. The proof labels every vertex with a triple $s \mid f(s) \mid e(s)$, where $s$ is the transmitted binary string along that path, $f$ deletes the error-indicating patterns $11$ (at the front) and $011$, and $e$ counts how many deletions were recognized. The invariant (Lemma 11) says that the strongest player wins any vertex if her seed name has the cleaned prefix $p_{k-e(s)-\ell}(f(s))$, given that at most $\ell$ games below that vertex were manipulated; induction then yields the theorem. A simpler ternary construction with an explicit error symbol reaches height $\log_2 n + 2k$ and is proved first as an illustration of the same idea.

Load-bearing premise

The construction inherits its guarantee from an unproved folklore communication protocol, and in the binary case the proof depends on the decoding function $f$ always outputting strings without consecutive ones with exactly the prefix behavior asserted in Observation 10.

Editorial extensions

If this is right

  • If the construction is correct, a knockout tournament can tolerate a constant fraction of rigged games on every leaf-to-root path while remaining only polynomially larger than a standard tournament.
  • For $k = \log_2 n$ the height is about $4.44\log_2 n$, so the tolerated manipulation fraction per path is about $1/4.44$, and as $k$ grows the fraction approaches $1/3$.
  • Corollary 12 shows the height can be pushed to $(1+\varepsilon)\log_2 n + g(\varepsilon^{-1})k$ by using longer runs of ones as error markers, so for constant $k$ the depth is arbitrarily close to an ordinary tournament's depth.
  • The guarantee holds uniformly over all winner functions and seedings, so the tournament organizer never needs to know pairwise strengths or the identity of the strongest player.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • We infer that the tournament tree is effectively a decoding circuit for a code whose codewords are leaf-to-root paths, which suggests that coding-theoretic lower bounds could be transferred into lower bounds on the height of any manipulation-proof tournament.
  • Replacing the feedback-channel protocol by other feedback-channel codes would change the trade-off between the coefficient of $\log_2 n$ and the coefficient of $k$ in the height bound beyond the smooth trade-off already noted in the paper.
  • If the strongest-player assumption is relaxed to a set of several equally strong players, the same redundancy should still force the winner to come from that set; the paper leaves this as an open question.
  • Because the construction never uses the identity of the strongest player, the robust tree is a fixed schedule that could be tested by simulation on small $n$ and $k$ against random manipulation patterns before deployment.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies knockout tournaments that remain correct when an adversary can flip the outcomes of up to k games on every leaf-to-root path, under the assumption that a strongest player exists but is not known to the designer. The authors propose to enlarge the tournament tree so that each player occupies several seed positions, and they build the tree from communication protocols with feedback that are robust to adversarial noise, specifically Berlekamp's protocol. The main formal results are a ternary tournament tree of height log n + 2k (Theorem 2) and a binary tournament tree of height at most ceil(1.44 log n) + 3k (Theorem 6), both computable in linear time; the binary construction is claimed to tolerate up to a 1/3 fraction of per-path manipulations at polynomial size. The proofs proceed by assigning to each tree vertex a label s|f(s)|e(s) that simulates Bob's decoding state and by proving invariants (Lemmas 5 and 11) that compare the strongest player's progress in the robust tree with his progress in a standard prefix tree. The ternary proof is self-contained and appears sound. The binary proof depends on a decoding function f that is supposed to output strings without consecutive ones, on Fibonacci counting of such strings, and on prefix operations p_l.

Significance. The paper introduces a genuinely new connection between tournament design and feedback-channel coding, and the ternary construction is elegant and appears correct. If Theorem 6 can be repaired, the result would be the first explicit tournament design tolerating a constant fraction (up to 1/3) of manipulations per path with only polynomial overhead, together with a clean trade-off between the constants in front of log n and k (Corollary 12). The constructions are explicit, run in linear time, and the main claims are falsifiable. The paper is also candid about open questions. However, as written the binary half has a load-bearing definitional problem that invalidates the proof of the main theorem; the paper is therefore not yet acceptable in its present form.

major comments (3)
  1. [§4.3, definition of f/e; Observation 10; Lemma 11] The static two-phase definition of f is not equivalent to the streaming decoder of §3.2, and under that definition the claim that seed names avoid consecutive ones is false. For example, with the literal definition, f(01111)=11: deleting the first 011 leaves 11, and no further 011 occurs. For r=2, k=1 this makes s=01111 a leaf with seed name 11; for r=3, k=1 the node s=011110 is a leaf with seed name 110. Both contain consecutive ones. Since Definition 2, Observation 10, and the proof of Lemma 11 assume f(s) has no consecutive ones and that appending a 1 to a string whose f-image ends in 1 increments e, the proof of Theorem 6 is not valid as written. The fix is to define f and e directly by the online rule of §3.2 (append the received bit; if the message now ends in 11, delete the last three bits, or all bits if fewer than three remain, and increment e), and to re-prove Observation 10 for that decoder.
  2. [§4.3, seed-position counting] The paper asserts that choosing r with F_{r+2} ≥ n guarantees sufficiently many seed position names, but no lemma shows that the leaves of T_{n,k} realize all, or even n distinct, strings of length r without consecutive ones. The construction produces leaves with other names: for k=1, s=1111 is a leaf whose seed name is ε, and under the current f some leaves receive names with consecutive ones (see previous comment). Theorem 6 requires n different seed positions and a bijective seeding σ, so the counting argument is load-bearing. A proof that every string of length r without consecutive ones occurs as f(s) for some leaf, or a replacement argument bounding |S_T|, is needed.
  3. [§4.3, Lemma 8] The proof of Lemma 8 contains a case analysis that is not correct for the stated f. The sentence 'if s ends with a one we have that e(s)=e(s1)-1' fails for s=011, where e(s)=e(s1)=1 under the literal definition, and the subsequent claim |f(s)|=|f(s1)|+1 or +2 also fails there. The potential function may still decrease by at least one in every step, but the proof needs to be redone, preferably after the streaming definition of f/e is adopted.
minor comments (4)
  1. [§3.2, decoding rule] The rule 'delete the last three bits from the message' is undefined when the current message has fewer than three bits; the paper should specify that the message becomes empty in that case, since this case is reachable (for example, after receiving 11).
  2. [Figure 6 caption] The caption says 'the function f removes occurrences of 001 from s', but the text defines the removed pattern as 011; the caption should be corrected.
  3. [Introduction and abstract] There are several typos: 'we are a given binary tournament tree' should be 'we are given a binary tournament tree', and the phrase 'larger than than' in §1.2 should be 'larger than'.
  4. [Observation 10] The proof of Observation 10 is dismissed as 'straightforwardly' following from the definition; given that the rest of the binary proof depends on this observation, the argument should be written out in full for the corrected decoder.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the construction is self-contained; the cited Berlekamp protocol and Fibonacci counts are external support, not load-bearing self-citations.

full rationale

I walked the derivation chain of Theorems 2 and 6. The tournament construction is defined directly from the inputs n and k: labels s | f(s) | e(s), children generated by appending symbols, and leaves labeled with seed names f(s). The robustness of the ternary case is proved in Lemma 5 by induction using the external invariant pk−e(s)−ℓ(f(s)); the binary case is proved in Lemma 11 using Definition 2 and Observation 10. No parameter is fitted to a target outcome, no prediction is renamed from an input, and no central premise is justified by a self-citation. The paper cites Berlekamp's communication protocol with feedback channel as folklore [2], but that is an external reference, not a self-citation, and the paper does not rely on the cited protocol's correctness in a way that reduces its own theorem to an assertion by the same authors. The Fibonacci counting fact is also standard external mathematics [8], used only to set the seed-name length r. The height bounds are derived from potential functions (Lemmas 4 and 8), not from the robustness claim. The possible issue raised in the skeptic note about the binary decoding function f producing consecutive ones for inputs like 01111 is a correctness concern about whether Observation 10 and Lemma 11 hold as written; it is not a circularity, because the theorem's conclusion is not equated with its assumptions by construction or by self-citation. The manuscript itself does not claim to derive the Berlekamp protocol, and the central tournament-robustness theorems are original constructions with inductive proofs. I therefore find no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The construction rests on the existence of a strongest player (an explicit modeling assumption), on the correctness of Berlekamp's feedback protocols (external, cited as folklore), and on standard Fibonacci counting. No parameters are fitted to data and no new entities are postulated. The main unproven load-bearing item is the exact behavior of the decoding function f in the binary case.

assumptions (4)
  • domain assumption There exists a strongest player iw who beats every other player in every match, and in every ternary match containing iw.
    Modeling assumption stated in Section 1.1 and formalized in Section 2.4. Without it, the robustness guarantee does not apply.
  • domain assumption The communication protocols with feedback (Sections 3.1 and 3.2) correctly decode the transmitted message when up to k symbols are corrupted, and Bob's decoding rule (delete last three bits on '11') has the properties used in the tournament translation.
    Cited as folklore from Berlekamp [2], not proven in the paper. Lemma 11 and Observation 10 rely on specific properties of f and e (e.g., that f(s) is always a string without consecutive ones) that are asserted but not fully established.
  • standard math The number of binary strings of length r without consecutive ones is F_{r+2} and F_{r+2} ≥ φ^r.
    Used in Section 4.3 to set r = ⌈1.44 log n⌉; cited to Gardner [8].
  • standard math Tribonacci growth ≈ 1.84^r for Corollary 12.
    Used for the trade-off with x=3; cited to Gardner [8].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tournament Robustness via Redundancy." pith.science (2026). https://pith.science/paper/AA6NRLO2

@misc{pith2026250603701,
  author       = {Pith},
  title        = {Pith review of: Tournament Robustness via Redundancy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AA6NRLO2}},
  note         = {Machine review of arXiv:2506.03701}
}
abstract

A knockout tournament is one of the most simple and popular forms of competition. Here, we are given a binary tournament tree where all leaves are labeled with seed position names. The players participating in the tournament are assigned to the seed positions. In each round, the two players assigned to leaves of the tournament tree with a common parent compete, and the winner is promoted to the parent. The last remaining player is the winner of the tournament. In this work, we study the problem of making knock-out tournaments robust against manipulation, where the form of manipulation we consider is changing the outcome of a game. We assume that our input is only the number of players that compete in the tournament, and the number of manipulations against which the tournament should be robust. Furthermore, we assume that there is a strongest player, that is, a player that beats any of the other players. However, the identity of this player is not part of the problem input. To ensure robustness against manipulation, we uncover an unexpected connection between the problem at hand and communication protocols that utilize a feedback channel, offering resilience against adversarial noise. We explore the trade-off between the size of the robust tournament tree and the degree of protection against manipulation. Specifically, we demonstrate that it is possible to tolerate up to a $1/3$ fraction of manipulations along each leaf-to-root path, at the cost of only a polynomial blow-up in the tournament size.

Figures

Figures reproduced from arXiv: 2506.03701 by the authors.

Figure 1
Figure 1. Illustration of the communication setting with feedback channel and adversarial noise. [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Flowchart of the protocol described in Section 3.1. Initially, the current bit is the first [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Visualization of a binary tree where the root is labeled with an empty string [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Visualization of the recursive construction of [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: Visualization of the recursive construction of [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Illustration of the tournament tree Tn,k in the binary case. Gray vertices visualize vertices with labels where the function f removes occurrences of 001 from s. • If |f(s)| < r, then the vertex has one child with label s0 | f(s0) | e(s0). • If |f(s)| < r or e(s) < k, …
Figure 7
Figure 7. Figure 7: Illustration of a tournament tree that uses seed position names without consecutive ones. [PITH_FULL_IMAGE:figures/full_fig_p017_7.png]
Figure 8
Figure 8. Figure 8: Illustration of the prefix tree for the seed position names used in Figure 7. [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    H. Aziz, S. Gaspers, S. Mackenzie, N. Mattei, P. Stursberg, and T. Walsh. Fixing balanced knockout and double elimination tournaments. Artificial Intelligence, 262:1–14, 2018. 2

    work page 2018

  2. [2]

    E. R. Berlekamp. Block coding with noiseless feedback. In Ph.D. thesis, Massachusetts Institute of Technology, 1964. URL https://api.semanticscholar.org/CorpusID:109356025. 4, 8

    work page 1964

  3. [3]

    Brandt and F

    F. Brandt and F. Fischer. Pagerank as a weak tournament solution. In Proceedings of the 3rd International Workshop on Web and Internet Economics (WINE) , pages 300–305. Springer,

    work page

  4. [4]

    Chaudhary, H

    J. Chaudhary, H. Molter, and M. Zehavi. How to make knockout tournaments more popular? In Proceedings of the 2024 AAAI Conference on Artificial Intelligence (AAAI) , volume 38, pages 9582–9589, 2024. 1

    work page 2024

  5. [5]

    Chaudhary, H

    J. Chaudhary, H. Molter, and M. Zehavi. Parameterized analysis of bribery in challenge the champ tournaments. In Proceedings of the 39th Annual AAAI Conference on Artificial Intelligence (AAAI) , page TBA, 2025. 2

    work page 2025

  6. [6]

    Tournament qualification, seeding and selection efficiency

    Connolly and Rendleman. Tournament qualification, seeding and selection efficiency. Technical Report 2011-96, Tuck School of Business , 2011. 1

    work page 2011

  7. [7]

    T. Feltes. Match fixing in western europe. In Match-fixing in international sports: Existing processes, law enforcement, and prevention strategies , pages 15–30. Springer, 2013. 2

    work page 2013

  8. [8]

    M. Gardner. The scientific American book of mathematical puzzles and diversions . Simon and Schuster, 1959. 17, 21

    work page 1959

Show all 33 references
  1. [9]

    Optimal seedings in elimination tournaments

    Groh, Moldovanu, Sela, and Sunde. Optimal seedings in elimination tournaments. Economic Theory, 49(1):59–80, 2012. 1

    2012

  2. [10]

    Gupta, S

    S. Gupta, S. Roy, S. Saurabh, and M. Zehavi. When rigging a tournament, let greediness blind you. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 275–281, 2018. 2

    2018

  3. [11]

    Gupta, S

    S. Gupta, S. Roy, S. Saurabh, and M. Zehavi. Winning a tournament by any means necessary. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) , pages 282–288, 2018. 2

    2018

  4. [12]

    Gupta, S

    S. Gupta, S. Saurabh, R. Sridharan, and M. Zehavi. On succinct encodings for the tourna- ment fixing problem. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI) , pages 322–328, 2019. 2

    2019

  5. [13]

    D. Hill. A critical mass of corruption: Why some football leagues have more match-fixing than others. International Journal of Sports Marketing and Sponsorship , 11(3):38–52, 2010. 2 22

    2010

  6. [14]

    Karchmer and A

    M. Karchmer and A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics , 3(2):255–265, 1990. 4

    1990

  7. [15]

    M. P. Kim and V. V. Williams. Fixing tournaments for kings, chokers, and more. InProceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI) , pages 561–567,

  8. [16]

    M. P. Kim, W. Suksompong, and V. V. Williams. Who can win a single-elimination tourna- ment? SIAM Journal on Discrete Mathematics , 31(3):1751–1764, 2017. 2

    2017

  9. [17]

    Konicki and V

    C. Konicki and V. V. Williams. Bribery in balanced knockout tournaments. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages 2066–2068, 2019. 2

    2019

  10. [18]

    J. F. Laslier. Tournament solutions and majority voting , volume 7. Springer, 1997. 1

    1997

  11. [19]

    A. E. Manoli and G. A. Antonopoulos. ‘the only game in town?’: football match-fixing in greece. Trends in organized crime, 18:196–211, 2015. 2

    2015

  12. [20]

    Mattei and T

    N. Mattei and T. Walsh. Empirical evaluation of real world tournaments. arXiv preprint arXiv:1608.01039, 2016. 2

    2016 arXiv

  13. [21]

    Mattei, J

    N. Mattei, J. Goldsmith, A. Klapper, and M. Mundhenk. On the complexity of bribery and manipulation in tournaments with uncertain information. Journal of Applied Logic , 13(4): 557–581, 2015. 2

    2015

  14. [22]

    Time out for match-fixers manipulating livestreams

    MediaNews. Time out for match-fixers manipulating livestreams. https://www.europol.europa.eu/media-press/newsroom/news/ time-out-for-match-fixers-manipulating-livestreams , 2020. 2

    2020

  15. [23]

    Top controversies of world cup 2023

    MediaNews. Top controversies of world cup 2023. https:// timesofindia.indiatimes.com/sports/cricket/icc-world-cup/news/ angelo-mathews-timed-out-to-pitch-switch-top-controversies/ /-of-world-cup-2023/articleshow/105326878.cms , 2023. 2

    2023

  16. [24]

    Most Talked-About Corruption Scandals in Sports History

    MediaNews. Most Talked-About Corruption Scandals in Sports History. https://247wallst.com/special-report/2023/09/07/ 17-most-talked-about-corruption-scandals-in-sports-history/ , 2023. 2

    2023

  17. [25]

    S. Rosen. Prizes and incentives in elimination tournaments, 1985. 1

    1985

  18. [26]

    Russell and T

    T. Russell and T. Walsh. Manipulating tournaments in cup and round robin competitions. In Proceedings of the 1st International Conference on Algorithmic Decision Theory (ADT), pages 26–37. Springer, 2009. 2

    2009

  19. [27]

    Stanton and V

    I. Stanton and V. V. Williams. The structure, efficacy, and manipulation of double-elimination tournaments. Journal of Quantitative Analysis in Sports , 9(4):319–335, 2013. 2

    2013

  20. [28]

    Suksompong

    W. Suksompong. Tournaments in computational social choice: Recent developments. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 4611–4618, 2021. 1 23

    2021

  21. [29]

    Toward a theory of the rent-seeking society

    Tullock. Toward a theory of the rent-seeking society. Texas A&M University Press , 1980. 1

    1980

  22. [30]

    T. Vu, A. Altman, and Y. Shoham. On the complexity of schedule control problems for knockout tournaments. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) , pages 225–232, 2009. 1, 2

    2009

  23. [31]

    V. V. Williams. Fixing a tournament. In Proceedings of the 2010 AAAI Conference on Artificial Intelligence (AAAI) , volume 24, pages 895–900, 2010. 2

    2010

  24. [32]

    V. V. Williams. Knockout Tournaments, page 453–474. Cambridge University Press, 2016. 1

    2016

  25. [33]

    M. Zehavi. Tournament fixing parameterized by feedback vertex set number is fpt. In Pro- ceedings of the 2023 AAAI Conference on Artificial Intelligence (AAAI) , volume 37, pages 5876–5883, 2023. 2 24

    2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.