| paper | d4-conf-aldt-2009-0001 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: \(\mathrm{P}\), with running time \((\tau m L)^{O(1)}\) bit operations. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given rational masses \(\mu_t\) over finitely many opponent types, a finite score set \(S\), balanced baseline matchup profiles, and a distinguished target's baseline profile against each type, determine whether mass transfers \(x_{tu}(r,s)\) among type-pair games and \(z_t(r,s)\) in target-versus-type games obeying the paper's per-game manipulation restrictions admit a balanced realization in which the target's limiting score per opponent is at least the common per-capita score of every opponent type.
A finite-support mass-transfer feasibility problem: types carry rational population mass and coalition status; variables assign baseline outcome mass to final outcomes for each type pair and for the distinguished target's games; conservation, reciprocal scoring, per-game manipulation restrictions, and balanced realization constrain the transfers; the target must tie or exceed every opponent type's per-capita score.
The outcome-mass variables need a precise characterization of which transfers admit a balanced realization respecting each game's manipulation restrictions; this limits the proposed LP claim and its reach beyond the symmetric regime.
fatal: False
The mirror covers the constructive round-robin manipulation question anchored by Theorem 3 in a balanced type regime. It leaves the cup results, destructive manipulation, minimum-manipulation results, reseeding, and double-elimination results aside.
The strongest case is a mirror of the paper’s constructive manipulation result for round robins.
Lead mirror: Focal-Target Continuous Round-Robin Manipulation. Consider a very large round-robin league with \(N\) opponents grouped into \(\tau\) standardized matchup types, where \(N\gg\tau\). Each type \(t\) has mass \(\mu_t\), with \(\sum_t\mu_t=1\). A type includes the features the problem uses: its coalition status and its baseline matchup profile. A single named target team is tagged separately. It plays every opponent, so its score per opponent has a nonzero limit even though its share of the field tends to zero.
Let \(S\) be the explicit finite set of possible score pairs. For each type pair \(t,u\), give the baseline frequencies \(b_{tu}(r)\) of outcomes \(r\in S\); require reciprocal profiles when the order of the two types is reversed. The matchups are balanced: each team of a type receives the type-pair average against every other type. Give the target’s baseline matchup profile against each type as well.
A solution specifies fractions \(x_{tu}(r,s)\) of type-\(t\)-versus-type-\(u\) match mass that starts at baseline outcome \(r\) and ends at \(s\), and fractions \(z_t(r,s)\) for the target’s matches against type \(t\). Fractions must preserve the baseline mass and reciprocal scoring. Each outcome must obey the paper’s manipulation rule: no change if neither side is in the coalition; any \(s\in S\) if both are; and, if just one side is, that side cannot gain points while the other cannot lose points. Individual games still receive outcomes in \(S\); only the mass of games is divisible.
Write \(\sigma_w\) for the target’s per-opponent score, calculated from its matchup fractions, and \(\sigma_t\) for the per-capita score of type \(t\), calculated from its matchup fractions against all types. The question is whether feasible fractions exist such that \(\sigma_w\geq \sigma_t\) for every \(t\). A witness is the fractions themselves, or a balanced assignment of match outcomes realizing them. The target’s matches contribute to its own score; their contribution to any one opponent’s normalized score vanishes in the limit.
The anchor is Theorem 3, proved in this paper using the equivalence with winner determination and the dichotomy of Kern and Paulusma [7]. It says that deciding whether a constructive manipulation exists in a round robin is polynomial when the normalized scoring model is \(S=\{(i,n-i)\mid 0\leq i\leq n\}\), and NP-complete otherwise. Thus the paper itself states the full scoring-model boundary, while relying on [7] for the underlying winner-determination classification.
For this mirror, I expect tractability for every explicit finite \(S\). The variables \(x\) and \(z\), the mass-preservation constraints, the coalition restrictions, and the winner inequalities form a linear program of size polynomial in \(\tau\), \(|S|\), and the input bit length. The continuous question asks whether the discrete hardness in Theorem 3 dissolves when repeated type-pair matchups can be split across a continuum of games. This covers the paper’s constructive round-robin manipulation result; it makes no claim about its cup, destructive-manipulation, or minimum-number-of-manipulations results.
This is recognizable as their underlying problem because it retains round-robin score comparisons, a target, coalition-limited match changes, and the paper’s exact restriction on what a manipulator may do. It also has a plausible high-multiplicity regime: a massive league with many teams in a small number of standardized roster and matchup classes. The main uncertainty is the type-level regularity condition. The paper’s tournament graph permits arbitrary edge-by-edge outcomes; this mirror assumes a dense league whose matchup mass can be balanced so that teams of the same type share the same per-capita score. That is a real change in the instance regime, but it is precisely what makes a small number of types meaningful.
The soft spot is the same one: a referee could say that balancing opponents into type scores changes “this team wins” into a limit comparison against opponent classes. The tagged target preserves the named-team question, but its rivals are homogeneous in the limit. If arbitrary individual differences must remain relevant, types may proliferate to roughly \(N\), and this mirror loses its high-multiplicity force. The natural follow-up questions are whether discrete instances with many teams per type admit an additive approximation from this LP, and how much mass of games must be changed in the continuous analogue of the paper’s minimum-manipulation problem.
Theorem 3 is a real computational anchor, so the strongest objection is not that there is nothing to mirror. It is that the proposed LP may change the winner question it claims to preserve.
In a round robin, a team’s score is its row sum in the matchup graph, and the target must match or exceed the *largest individual row sum*. The LP instead compares the target with each opponent type’s average score. Those quantities need not agree. Among \(N\) teams with win–loss scoring, a regular tournament and a transitive tournament have the same aggregate count of match outcomes, but their highest scores are very different: roughly \(N/2\) wins versus \(N-1\). After normalization, that difference remains roughly \(1/2\) versus \(1\). Pair-type outcome frequencies alone do not determine whether the target wins.
This matters even though the mirror keeps a named target. The target’s score against the whole population can survive as a focal-agent quantity, while the comparison against its rivals still depends on the distribution of *individual* scores. Requiring a balanced assignment of outcomes repairs that gap only by restricting the instance or the permitted manipulations: the paper allows edge-by-edge changes, including changes that affect rivals unevenly. A type-pair LP does not show that every feasible aggregate transfer can be realized while keeping every rival below the target.
There is a stronger repair: represent the league’s matchup structure as a continuum of individual labels and compare the target’s score with the essential maximum of opponents’ row scores. But then the input is a matchup kernel, not a distribution over a small support of complete types. Encoding enough detail to preserve the individual comparisons can make the number of types grow with the number of teams; keeping a compressed kernel gives a different, potentially infinite-dimensional computational problem. That may itself be worth studying, but it is no longer the finite-support LP proposed for this anchor.
This objection does not establish the requested universal negative. A large, genuinely exchangeable league whose outcomes and feasible manipulations can be balanced across each team type is a plausible regime, and the focal-target construction could make its continuous winner question well posed. The honest conclusion is narrower: the proposed LP has not yet shown that it mirrors Theorem 3’s individual-winner question. I cannot honestly rule out a worthwhile continuous mirror in that symmetric regime.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.