| paper | d4-conf-ijcai-2016-0370 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Corollary 3 is a computational result, but its proposed mirror does not preserve the paper's bracket or target. The mass recursion samples types independently at each leaf, while the paper assigns a fixed roster of players to one bracket; giving the target positive mass also changes the objective from a named player's win to a cohort's win. No other concrete population mirror is stated.
fails bit b-changes — the continuum limit changes the question
The recursion treats leaf type masses as independent sampling across editions, whereas the paper fixes one roster and assigns each player to one leaf; making the target a positive-mass type also replaces the named-player objective with a cohort objective.
fatal: True
The proposal targets Corollary 3's robust fixing decision; it does not separately mirror Theorem 2's fixed-draw approximation or Corollary 4's special-case algorithms.
The strongest mirror I believe is a type-aggregated robust tournament-fixing problem. Take a large competition whose entrants fall into \(\tau\) types, where a type specifies an entrant’s full matchup-probability profile. The population is \(\mu\), with \(\mu_t\) the fraction of entrants of type \(t\). A plausible regime is a tournament system drawing from many entrants in a few standardized cohorts—for example, competitors with the same division, rating band, and matchup record. The marked target can be a cohort whose members share a type.
Here is a precise mass version. Let \(M=2^n\) be the number of seed positions in a balanced bracket, let \(T\) be the finite type set, and let \(p_{tu}+p_{ut}=1\) be the nominal probability that type \(t\) beats type \(u\), with \(p_{tt}=1/2\). A mass draw is a matrix \(x_{\ell,t}\geq 0\), where \(\ell\) ranges over the bracket’s leaves, \(\sum_t x_{\ell,t}=1\) for every leaf, and \(\sum_\ell x_{\ell,t}=M\mu_t\). Interpret each leaf as a seed-position cohort across repeated editions of the tournament: in an edition, one entrant is drawn from each cohort according to its type proportions. Thus \(x\) allocates population mass among seed positions.
For each leaf, set its type distribution to \(x_{\ell,\cdot}\). At an internal node with child distributions \(y^L,y^R\), define the winner’s type distribution by
\[
y_t=\sum_{a,b\in T}y^L_a y^R_b\bigl(\mathbf{1}_{t=a}p_{ab}+\mathbf{1}_{t=b}p_{ba}\bigr).
\]
The root probability \(W(x,p)\) of type \(t^\star\) winning is the mirror’s objective. Perturb each type-pair probability by at most \(\epsilon\), preserving \(p_{tu}+p_{ut}=1\), and define
\[
D(x)=\limsup_{\epsilon\downarrow0}
\frac{W(x,p)-\inf_{p'\in\mathcal P(p,\epsilon)}W(x,p')}{\epsilon}.
\]
The continuous problem, Robust Mass Bracket Fixing, asks: given \(M,T,\mu,p,t^\star,q,s\), does a mass draw \(x\) exist with \(W(x,p)\geq q\) and \(D(x)\leq s\)? A solution is such an \(x\). The deterministic version sets \(p\) to a deterministic type matchup matrix and \(q=1\); the probabilistic version permits general \(p\) and \(q\).
My anchor is Corollary 3, proved in this paper. It states that RTFP and RPTFP are NP-complete. RTFP asks, for a deterministic comparison matrix, a distinguished player, and \(c\in\mathbb N\), whether there is a draw in which that player wins and whose first-order worst drop is at most \(c\epsilon\) for all sufficiently small \(\epsilon\). RPTFP asks, for a probabilistic comparison matrix, a distinguished player, and thresholds \(q,s\), whether a draw gives that player nominal winning probability at least \(q\) and first-order worst drop at most \(s\epsilon\). The paper proves the corollary here: hardness reduces from the previously established TFP hardness in [1], while membership uses the polynomial fixed-draw calculations. This is the strongest anchor because it concerns the paper’s central robustness question.
For the unrestricted mass problem, I expect hardness to transfer in its atomic regime. Give each original player its own type, set \(\mu_t=1/M\), use the original deterministic matchup matrix, set \(q=1\), and choose \(s=M\), which makes the robustness bound nonbinding. A feasible mass allocation with root target probability one can be decomposed into supported pure assignments; probability one requires every supported assignment to be a winning bracket, so a winning discrete draw can be recovered. Conversely, a discrete winning draw gives a feasible pure mass allocation. This is a hardness argument for the unrestricted family, not a claim that tight robustness thresholds or fixed-\(\tau\) cases remain hard. Those are further questions: does the mass version have integral optimal draws, and can fixed-\(\tau\) instances be solved in time polynomial in \(\tau\) and the input bit length?
The weakest point is that the paper’s draw places individually identified players into one bracket, while this mirror splits type mass across seed-position cohorts and asks whether the target type wins across the resulting population of editions. That is a real change in the object. It is most plausible when the application already has large, exchangeable cohorts and repeated brackets; a single tournament with one focal player is a strained fit. Still, the model preserves the balanced bracket, type-level pairwise matchups, seed placement, winning probability, and worst-case probability error. The population itself is the continuous object, so this is a credible mass analogue of robust draw fixing rather than continuity introduced through outcomes or noise alone.
Corollary 3 is a real computational anchor: RTFP and RPTFP are NP-complete. The difficulty is giving that result a nondegenerate population mirror while keeping the paper’s objective—the robust chance that one *distinguished player* wins.
The proposed mass bracket does not quite describe one tournament with a continuous population. Each leaf still needs one entrant. A fractional type assignment \(x_{\ell,t}\) therefore describes variation across editions: each edition samples a type for each seed position. The recursion for \(W(x,p)\) treats those leaf samples as independent, so an edition need not contain the fixed type counts represented by \(\mu\). Enforcing those counts instead requires a distribution over integral brackets; averaging assignments does not in general make the nonlinear winning probability equal to \(W(x,p)\). That repaired model is about randomizing brackets across editions, rather than choosing a draw for one given society.
The target creates a deeper problem. If the target’s identity is part of its type, as the paper’s objective requires, then it is a singleton type with mass \(1/M\), which vanishes as the field grows. If the identity mark is dropped to give the target type positive mass, the question changes to whether *some member of a cohort* wins. That may be a sensible question, but it is not RPTFP’s distinguished-player question. Treating the target as a tagged, zero-mass player preserves the objective more closely, but then a growing bracket gives that player \(\log M\) rounds and ultimately no finite terminal round. In the paper’s examples, the first-order robustness cost can grow with the number of crucial matches, so a limiting robustness bound may diverge too. Normalizing the cost or studying a survival rate could produce a new asymptotic problem, but those choices need their own justification.
A fixed positive-mass target cohort is the strongest repair: its chance of supplying the champion can remain meaningful even as the field grows. But that is a cohort-outcome objective, and its cleanest finite interpretation is again a bracket—or an ensemble of brackets—with actual entrants and integral leaf assignments. I cannot rule out that the authors would regard this extension as worthwhile. The negative case is therefore strongest against the proposed mirror and the faithful tagged-player version; it does not establish the universal claim that no worthwhile mirror exists.
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.