{"id":"abf3fcbc-29ec-4508-b4a2-5ce27cee03e1","arxiv_id":"2412.11799","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Adaptive coalition manipulation in knockout tournaments is hard for every level of the polynomial hierarchy, PSPACE-complete for unbalanced trees, and polynomial-time solvable for constant coalition size.","lead":"This paper introduces a model where a coalition of players in a knockout tournament can decide, round by round, which matches to throw after seeing who advanced. It proves that deciding whether this can make a favorite player win is computationally very hard, and that it becomes more tractable only when the coalition is small or the tournament is nearly deterministic.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The DP transition formula in §4.1 ignores the action of a coalition player who intentionally loses, making Lemma 14 false; on a 4-player instance it returns 0.2 while a legal throwing strategy gives e* probability 1.","rationale":"Read in good faith, the paper's central algorithmic claim is that adaptive coalition manipulation is tractable for small coalitions or small random game covers. That claim rises or falls with Lemma 14, which asserts the DP table M[i,S] equals the true optimal continuation probability. The transition formula in §4.1 is not a correct probability model of intentional losses: for a match between coalition players c1 and c2, the event 'c2 throws the match' should make c1 advance with probability 1, but the formula records c1's win probability p(c1,c2) and records nothing for c2's action because c2 is not in S*. The same defect applies when a throwing coalition player faces a non-coalition opponent, so the recurrence can severely underestimate the value of throwing. The 4-player instance is a minimal falsification: the DP outputs at most 1/5, while the legal strategy 'c2 throws' wins with probability 1. Consequently Theorems 15-17 and Corollary 18 lack a valid proof, and the PSPACE-containment half of Theorem 8 is also unsupported. I do not see a comparable flaw in the hardness reductions; the Section 3 lower bounds appear internally consistent. The reader's rationale flagged the same DP defect, so the verdict should remain REJECT; because the reader's named weakest assumption was instead about observability in the hardness reduction, I mark agreement as partial.","tokens_in":25807,"tokens_out":11425,"duration_ms":115202,"concrete_test":"Implement the DP of §4.1 and run it on the 4-player balanced instance with seed (c1,c2,e,d), C={c1,c2}, e*=e, p(c1,c2)=1/5, p(e,c1)=1, p(c2,e)=1. Compare the returned value with 1, the success probability of the explicit legal strategy in which c2 intentionally loses the first match and e* beats c1 in the final. If the DP returns less than 1 (it returns at most 1/5), Lemma 14 and Theorems 15-17 are falsified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 14 and the entire algorithmic section rest on the transition probability p(S,S',S*,c) defined in §4.1 as the product over players in S* of c(e)*p(e,s_{S,S'}(e)) for coalition winners and p(e,s_{S,S'}(e)) for non-coalition winners. This product includes a factor only for players who advance; a coalition player who intentionally loses (c(e)=0) is not in S* and contributes no factor. Therefore, when a coalition player throws a match, the probability that the opponent advances is recorded as p(opponent, loser) rather than 1. The expression is not even a probability distribution: the sum of p(S,S',S*,c) over next configurations S* is less than 1 whenever some coalition player intentionally loses. Consequently the induction in Lemma 14 is unsound. Concrete failure: take four players with C={c1,c2}, favorite e=e*, seed (c1,c2,e,d), p(c1,c2)=1/5, p(e,c1)=1, p(c2,e)=1, and arbitrary remaining probabilities. The DP returns at most 1/5, yet the legal strategy 'c2 throws the first match' lets c1 reach the final and e* beats c1, giving e* win probability 1. Hence Theorems 15-17 and Corollary 18 do not follow from the presented argument, and the PSPACE-containment half of Theorem 8 is also unproven. The PH and PSPACE hardness lower bounds in Section 3 are not affected by this flaw.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces an adaptive model of constructive coalition manipulation for probabilistic knockout tournaments, in which coalition players may decide, after each round, which matches to throw based on the current seeding. The authors claim (i) hardness for every class in the polynomial hierarchy for the balanced setting (ACCM-KT), (ii) PSPACE-completeness for an imbalanced generalization (ACCM-GKT), (iii) NP-hardness for best-response and non-adaptive variants, and (iv) algorithmic tractability: an n^{O(|C|)}-time algorithm for ACCM-GKT, an FPT algorithm for ACCM-KT parameterized by coalition size plus minimum random game cover, and polynomial-space containment for ACCM-GKT. The algorithmic results are obtained through a dynamic programming recurrence in Section 4.1.","tokens_in":1369,"tokens_out":1381,"duration_ms":55340,"significance":"If the results were correct, the paper would make a substantial contribution: it appears to be the first to introduce adaptiveness to coalition manipulation in knockout tournaments, and it resolves an open question on the NP-hardness of the non-adaptive CCM-KT problem. The hardness reductions are detailed and are not affected by the technical flaw found in the algorithmic section. However, the dynamic programming recurrence in Section 4.1 is unsound in a load-bearing way: it fails to account for the effect of a coalition player intentionally losing on the advancement probability of the opponent. Because the correctness of Theorems 15-17 and Corollary 18, as well as the PSPACE-containment half of Theorem 8, rests on this recurrence, a central pillar of the paper's positive results collapses.","major_comments":[{"comment":"The transition probability p(S,S',S*,c) is defined as a product over players in S* only, with factors c(e)*p(e, s_{S,S'}(e)) for coalition winners and p(e, s_{S,S'}(e)) for non-coalition winners. This omits the effect of a coalition player who intentionally loses (c(e)=0): when such a player throws a match, the opponent advances with probability 1, but the formula records the opponent's original winning probability p(opponent, e), which may be less than 1. Consequently, the sum of p(S,S',S*,c) over all next configurations S* is strictly less than 1 whenever some coalition player throws, so the expression is not a probability distribution and the induction in Lemma 14 is invalid. Concrete counterexample: take four players with C={c1,c2}, favorite e*, seed (c1,c2,e,d), p(c1,c2)=1/5, p(e,c1)=1, p(c2,e)=1, p(e,d)=1. The strategy 'c2 throws the first match' lets c1 reach the final and e* beats c1, giving e* win probability 1, but the DP in Section 4.1 returns at most 1/5. Thus Lemma 14 is false.","section":"Section 4.1, definition of p(S,S',S*,c) and Lemma 14"},{"comment":"Since Lemma 14 is false, the running-time analyses and correctness statements in Section 4.2 do not follow. In particular, Theorem 15 (XP for ACCM-GKT), Theorem 16 (FPT for ACCM-KT), and Corollary 18 (best-response computation) are unsupported. Moreover, Theorem 8 claims PSPACE-completeness for ACCM-GKT, but its containment in PSPACE is deferred to Theorem 17; with Theorem 17 unproven, only PSPACE-hardness is established. The hardness reductions in Section 3 are not affected by this flaw, but the positive results and the completeness claim in Theorem 8 are.","section":"Theorems 15, 16, 17 and Corollary 18; Theorem 8 containment"}],"minor_comments":[{"comment":"The definition of a random game cover has a typo: 'i ∈ X or j ∈ Y' should read 'i ∈ X or j ∈ X'.","section":"Section 2.6, Definition 1"},{"comment":"The strategy function ξ outputs zero or one, but the meaning of a zero when two coalition players face each other is not fully formalized; the constraint that not both can intentionally lose is stated only informally in the text.","section":"Section 2.1, strategy definition"},{"comment":"The 'ensurance player e' is named inconsistently with the favorite player e*; this can confuse the reader, though the intended meaning is clear from context.","section":"Proof of Theorem 12, New Clause Gadget"},{"comment":"The discussion that lowering winning probabilities arbitrarily is equivalent to choosing either the original probability or zero is reasonable, but it would benefit from a formal statement about the optimality of pure strategies in the adaptive setting, since the current argument is informal and only considers a single current game.","section":"Section 2.1, best response argument"}],"recommendation":"reject","confidential_remarks":"The technical flaw in Section 4.1 is decisive and directly invalidates the paper's main algorithmic claims. The hardness results appear sound and are valuable, but the paper as written does not support its central positive results. I recommend rejection, while noting that the DP transition could in principle be repaired by treating a throwing coalition player as contributing a factor of 1 to the opponent's advancement probability. If the authors fix this and re-prove the algorithmic statements, a revised submission would merit reconsideration."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The adaptive model is genuinely new and the lower bounds look like real progress. Adaptiveness is not in Russell–Walsh or Mattei et al., and the paper uses it to get PH-hardness for balanced tournaments, PSPACE-completeness for generalized trees, NP-hardness for the previously open non-adaptive CCM-KT, and W[1]-hardness. The reductions are detailed, use clean 0/1/1/2 probabilities, and the gadget arguments read coherently. The citation pattern is healthy: no fitted parameters, no circular derivation, and the authors' own prior work appears only as background. That is the part worth keeping.\n\nThe algorithmic half is not just weak, it is wrong as written. In Section 4.1 the transition probability p(S,S',S*,c) multiplies factors only for players who advance. When a coalition player intentionally loses, that player is not in S*, so the probability that the opponent advances is recorded as the opponent's natural win probability instead of 1. The sum of p(S,S',S*,c) over next configurations is then less than 1, so the expression is not even a probability distribution. Lemma 14 is false, and Theorems 15–17 and Corollary 18 do not follow. The PSPACE-containment half of Theorem 8, which depends on Theorem 17, is also unproven.\n\nThe stress-test counterexample is convincing and easy to check: four players, coalition {c1,c2}, seed (c1,c2,e,d), p(c1,c2)=1/5, p(e,c1)=1, p(c2,e)=1. The legal strategy where c2 throws the first match gives e* winning probability 1, while the DP returns at most 1/5. This is a load-bearing flaw, not a typo. My guess is it could be repaired by rewriting the transition to account for losing coalition players and their opponents' advancement, but that is a substantial change to the algorithm and its analysis. I also noticed the reversed-winner typo in the (⇐) direction of Theorem 3; that one is cosmetic and does not affect the reduction.\n\nWho should read this? People working on tournament manipulation or computational social choice will want the hardness results and the adaptive model even if the positive results are currently unsupported. I would not desk-reject it: the lower-bound contributions are significant enough to merit referee time, and the algorithmic defect is identifiable and possibly fixable. But the paper should not be accepted until the DP is corrected or the algorithmic claims are withdrawn. Send it to review with a clear request to fix Section 4.","headline":"Solid hardness results for adaptive coalition manipulation, but the DP recurrence is wrong and the algorithmic claims fall with it.","tokens_in":26641,"tokens_out":3015,"would_cite":true,"duration_ms":31374,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","68Q27"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces adaptive coalition manipulation in knockout tournaments and proves it hard for every class of the polynomial hierarchy, even when the required win probability is one.","keywords":["knockout tournaments","coalition manipulation","adaptive strategy","polynomial hierarchy","quantified Boolean formula","parameterized complexity","dynamic programming","random game cover"],"falsifier":"Run the Section 3.1 reduction on a small quantified Boolean formula with two quantifier alternations, enumerate all adaptive strategies for the resulting tournament, and check that the favorite's maximum winning probability is exactly one when the formula is true; any mismatch would refute the reduction, as would a polynomial-time algorithm for ACCM-KT at threshold one, which would collapse the polynomial hierarchy.","tokens_in":25582,"feed_emoji":"🏆","tokens_out":5810,"duration_ms":53971,"temperature":0.7,"pith_summary":"The paper introduces the first adaptive model of coalition manipulation in probabilistic knockout tournaments: coalition players decide which matches to throw after observing which players advanced to the current round. It establishes that deciding whether a designated favorite can win with probability at least a given threshold is computationally intractable in a very strong sense, namely hard for every class in the polynomial hierarchy for balanced tournaments and PSPACE-complete for imbalanced trees. If correct, this means adaptive manipulation has no polynomial-time algorithm and, for balanced tournaments, no polynomial-size certificate, in sharp contrast with the earlier non-adaptive model that lies in NP. The paper also provides algorithms, including polynomial time for constant coalition size and fixed-parameter tractability when the coalition size is combined with the size of a minimum random game cover.","feed_headline":"Adaptive match-throwing is hard for every PH level","feed_subtitle":"Even forcing a favorite to win with certainty has no polynomial-time algorithm unless polynomial hierarchy collapses.","key_machinery":"The load-bearing object is the adaptive strategy function, which maps a coalition player, a round number, and the observed seeding for that round to a throw-or-play decision. The hardness reductions build constant-sized selection gadgets, subtournaments where one coalition player can decide which of several non-coalition players wins, to encode existential choices, universal random advances, and clause satisfaction, arranged so that the number of quantifier alternations becomes the depth of the tournament. On the algorithmic side, the central mechanism is a dynamic program over the coalition skeleton, the subtree of the tournament tree containing the paths from the root to coalition players, which tracks valid configurations and sibling configurations and maximizes the favorite's winning probability round by round.","core_discovery":"The central claim is that adaptive constructive coalition manipulation in knockout tournaments is hard for every class in the polynomial hierarchy even when the threshold probability is one, and that the generalized version with imbalanced tournament trees is PSPACE-complete. The hardness arises from reductions from quantified Boolean formulas: constant-sized subtournaments act as gadgets in which a coalition player chooses which of several other players wins, while universal-variable gadgets advance randomly so that later existential gadgets can react to the assignment observed. The same constructions also resolve the NP-hardness of the non-adaptive variant, which had been open, and show that computing a best response for the first round is NP-hard.","pith_inferences":["If the observed-seeding assumption is what creates the alternating-quantifier structure, then a model in which the coalition must commit to a round's throws before seeing that round's seeding should collapse the hardness to NP; this is testable by rerunning the reduction without adaptive reaction.","The hardness transfers to budget-constrained manipulation, since coalition manipulation is the special case where throwing a game involving a coalition player costs one unit and all other manipulations are infinitely expensive.","The best-response formulation suggests an online protocol: compute the optimal first-round profile, play the round, observe the new seeding, and recompute, which gives the optimal continuation even though the full strategy has exponential description.","The jump from PH-hardness to PSPACE-completeness when moving from balanced to imbalanced trees indicates that the balanced-tree restriction is not a technical convenience but the boundary between two distinct hardness levels."],"forward_implications":["If ACCM-KT is hard for every class in the polynomial hierarchy, then adaptive coalition manipulation in balanced knockout tournaments has no polynomial-time algorithm and no polynomial-size witness under standard complexity assumptions.","The PSPACE-completeness of ACCM-GKT means that allowing imbalanced tournament trees makes the problem at least as hard as quantified Boolean formulas with polynomially many quantifier alternations.","The NP-hardness of the non-adaptive variant closes the open question left by the earlier model, showing that the non-adaptive problem is NP-complete given its previously known containment in NP.","The dynamic programming algorithms show that when the coalition is small, or when the coalition size is combined with the size of a minimum random game cover, the optimal strategy can be computed in polynomial or fixed-parameter tractable time.","The best-response variant can be solved in the same running-time bounds, so a coalition can re-optimize round by round as the seeding is revealed without writing down an exponentially large strategy."],"supporting_citations":[{"why":"It supplies the non-adaptive probabilistic model whose NP-containment is the baseline the paper contrasts with and whose NP-hardness the paper resolves.","marker":"[27]"},{"why":"It provides the deterministic setting and the polynomial-time algorithm that the paper treats as the base case when all games are deterministic.","marker":"[35]"},{"why":"It supplies the quantified Boolean formula framework and the definitions of the polynomial hierarchy and PSPACE used for the hardness reductions.","marker":"[2]"},{"why":"It supplies the W[1]-hardness of Multicolored Clique used for the parameterized hardness reduction for ACCM-GKT.","marker":"[13]"},{"why":"It supplies the NP-hardness of 3SAT used for the reductions showing BR-ACCM-KT and CCM-KT are NP-hard.","marker":"[20]"},{"why":"It supplies the standard parameterized complexity background and the fixed-parameter algorithm for vertex cover used to compute a minimum random game cover.","marker":"[8]"}],"fun_headline_variants":["Adaptive coalition throws make fixing knockouts PH-hard","Knockout rigging with adaptive coalitions is PH-hard","Even certain wins can't be fixed adaptively in knockouts","Match-throwing strategies: adaptive coalitions PH-hard","Coalition adaptivity in tournaments defies PH"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that coalition players observe the exact current seeding before each round and can coordinate freely on whether to throw; without this observation, the reductions' alternating-quantifier encoding would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive coalition throws make fixing knockouts PH-hard","Knockout rigging with adaptive coalitions is PH-hard","Even certain wins can't be fixed adaptively in knockouts","Match-throwing strategies: adaptive coalitions PH-hard","Coalition adaptivity in tournaments defies PH"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000957,"raw_usage":{"total_tokens":4058,"prompt_tokens":906,"completion_tokens":3152,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":3082}},"tokens_in":522,"tokens_out":3152,"duration_ms":26609,"temperature":1.0,"reasoning_tokens":3082,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:37:13.461531+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the Section 3.1 reduction on a small quantified Boolean formula with two quantifier alternations, enumerate all adaptive strategies for the resulting tournament, and check that the favorite's maximum winning probability is exactly one when the formula is true; any mismatch would refute the reduction, as would a polynomial-time algorithm for ACCM-KT at threshold one, which would collapse the polynomial hierarchy.","supporting_citations":[{"cited_title":"Mattei, J","cited_arxiv_id":null,"evidence_quote":"It supplies the non-adaptive probabilistic model whose NP-containment is the baseline the paper contrasts with and whose NP-hardness the paper resolves."},{"cited_title":"Russell and T","cited_arxiv_id":null,"evidence_quote":"It provides the deterministic setting and the polynomial-time algorithm that the paper treats as the base case when all games are deterministic."},{"cited_title":"Arora and B","cited_arxiv_id":null,"evidence_quote":"It supplies the quantified Boolean formula framework and the definitions of the polynomial hierarchy and PSPACE used for the hardness reductions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the W[1]-hardness of Multicolored Clique used for the parameterized hardness reduction for ACCM-GKT."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the NP-hardness of 3SAT used for the reductions showing BR-ACCM-KT and CCM-KT are NP-hard."},{"cited_title":"Cygan, F","cited_arxiv_id":null,"evidence_quote":"It supplies the standard parameterized complexity background and the fixed-parameter algorithm for vertex cover used to compute a minimum random game cover."}],"review_version":1}