| paper | d4-conf-atal-2015-0280 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given a society μ over complete feature and cost types, with binary-rational masses summing to one, a marked target type of mass α and feature vector \(x^\star\), a budget \(B\), costs \(C\), and a rationally described allowed weight set \(W\), decide whether there is a common cohort update \(Δ ≥ 0\), with \(C · Δ ≤ B\), such that for every \(w ∈ W\), the mass whose score exceeds \(w · (x^\star+Δ)\) is less than a given threshold \(q\).
A distribution μ over complete entry types, each carrying a feature vector and any relevant costs; a marked cohort of mass α shares \(x^\star\) and makes a common per-member update Δ\). The objective is to minimize the worst-case mass strictly ranked ahead over \(w ∈ W\), subject to \(C · Δ ≤ B\).
The paper’s experiments concern roughly 102 colleges with likely unique feature profiles, and provide no evidence that exact high-multiplicity profiles occur in its applications; the proposed standardized-entry regime remains hypothetical.
fatal: False
The mirror covers Theorem 3’s minimax rank-threshold computation for a marked cohort and also admits Theorem 1’s agency weight choice as the zero-update case. It leaves the paper’s constrained agency MILP formulations, approximation heuristics, and USNews experiments outside the mirror.
The strongest lead is a continuous version of the paper’s agency manipulation problem. Take a ranking platform with many entries scored by the same \(n\) features. A type is an entry’s complete feature profile, plus any other information relevant to the problem. The society is a distribution \(\mu\) over those types, with rational masses summing to one. A plausible regime is a platform ranking millions of standardized or feature-binned listings: there may be millions of entries but only hundreds of distinct profiles. The target can be a cohort sharing one profile.
For a target type \(t^\star\), let \(x(t)\) be its feature vector and define its rank share under weights \(w\) as \(A_\mu(t^\star,w)=\sum_{t:w\cdot x(t)>w\cdot x(t^\star)}\mu_t\). This is the mass strictly ranked ahead, matching the paper’s strict tie convention. With uniform mass \(1/m\) per entry, the paper’s rank is \(1+mA_\mu\), so optimizing rank and optimizing rank share give the same answer.
Lead question — Continuous Cohort Agency Rank Manipulation. Given the supported types and their binary-rational masses, a designated target type, and valid weights \(W=\{w\in\mathbb R^n_{\ge0}:\sum_j w_j=1\}\), find a \(w\in W\) minimizing \(A_\mu\) (constructive manipulation) or maximizing it (destructive manipulation). The solution is the attaining weight vector. This directly preserves the paper’s decision variable, linear scores, and rank objective; only the count of entries ahead becomes their mass.
The anchor is Theorem 1, which states that computing the maximum constructive or destructive basic manipulation weights is NP-hard: for a fixed feature profile and distinguished agent, choosing valid weights to minimize or maximize that agent’s rank is NP-hard. The paper presents this as its result, but says the proof is deferred to a full version; it identifies a reduction from CLOSED HEMISPHERE [20]. The continuous problem inherits hardness by assigning each entry mass \(1/m\). Thus I expect hardness transfer, not continuum-specific hardness. This makes the mirror useful even if it does not dissolve this particular hardness: it asks whether weighted-mass versions, especially with small support, have a different complexity landscape.
A second, related mirror is credible for the paper’s agent-manipulation result. Consider a marked cohort of mass \(\alpha>0\), all with the same starting features \(x^\star\) and per-feature costs \(C\). A type includes the mark indicating eligibility for the intervention, so a background entry with the same score features need not be merged with the target cohort. The cohort makes a common per-member update \(\Delta\ge0\) with \(C\cdot\Delta\le B\). Shift its mass from its starting type to the updated type, giving \(\mu^\Delta\), and let \(R(\Delta,w)\) be the mass whose score under \(w\) is strictly above \(x^\star+\Delta\).
Continuous Minimax Cohort Rank Threshold. Given this population, budget and costs, a rationally described allowed weight set \(W\), and a rational threshold \(q\), decide whether \(\min_{\Delta:C\cdot\Delta\le B}\max_{w\in W}R(\Delta,w)<q\). The yes/no answer is the decision solution; an optimization version would return a minimizing update. It asks how much per-capita improvement a homogeneous cohort needs to guarantee a rank percentile against the agency’s worst allowed weights.
Its anchor is Theorem 3, which states that, given \(W\), the other agents’ feature profile \(P^{-}\), the feasible spending set \(\mathrm{Feasible}_B(c)\), and threshold \(T\), deciding whether the minimax value is smaller than \(T\) is coNP-complete. The paper derives this immediately from the \(B=0\) case. In the uniform discrete embedding, the minimax rank share is \((\text{minimax rank}-1)/m\), so the corresponding threshold is \(q=(T-1)/m\). The mass version is therefore at least coNP-hard by hardness transfer; I would not claim it is coNP-complete without separately proving membership for the weighted-mass input. A natural follow-up is whether hardness persists when \(\tau\ll m\), or when the target cohort’s mass is bounded away from zero.
The soft spot is the regime assumption. The paper’s USNews example has about 102 ranked colleges, and real feature measurements may be mostly unique; its experiments do not establish a high-multiplicity regime. The mirror becomes persuasive where features and, for cohort manipulation, costs are genuinely standardized or binned, so many entries really share a complete type. It also treats a cohort’s rank percentile rather than one named entity’s raw rank. I think the authors would recognize that as the same ranking question in population units, but the cohort interpretation and the move from measured profiles to repeated types are the parts a skeptical referee could reject.
The strongest case against is about yield, not whether the mirrors can be defined. The paper’s own setting has few ranked entities and real-valued feature vectors, so exact feature profiles will often be unique. Then the continuous society has \(\tau=m\): representing it by masses compresses nothing. Binning features to create repeated types would change score comparisons, while exact duplicates already tie under the paper’s rank definition. Its college experiments, with roughly 102 institutions, give little evidence that high multiplicity is the regime that matters here.
That objection reaches Theorem 1 only as a practical challenge. Its agency problem has a clean continuous-population form: for a target profile \(z\), minimize or maximize
\[
\mu\{x:w\cdot x>w\cdot z\}
\]
over valid weights \(w\). With equal masses, this is the paper’s number of entities strictly ahead, divided by the population size. A realistic platform with many standardized entries could make this a useful rank-share question. The paper’s finite, heterogeneous examples do not establish that regime, but they cannot rule it out.
Theorem 3 admits an even stronger mirror than the proposed cohort version. Keep the target as one tagged entity, and let \(\mu\) describe its competitors. Then its minimax rank share is
\[
\min_{\Delta:C\cdot\Delta\le B}\ \max_{w\in W}
\mu\{x:w\cdot x>w\cdot(z+\Delta)\}.
\]
The target need not carry positive population mass: its rank percentile is measured against the distribution of competitors. This preserves individual spending and avoids requiring a whole cohort to share one update. The theorem’s hardness already holds at \(B=0\), so it overlaps with the agency question; that makes it a less independent anchor, but not an invalid one. With positive budget, the tagged-target formulation still asks a coherent computational question.
So the negative case is that the paper offers weak evidence for a high-multiplicity application, and the two anchors may yield less distinct work than they first appear to. But I cannot honestly turn that into the requested claim that no scenario makes a worthwhile mirror. Standardized entries, or a target ranked against a large distribution of competitors, remain plausible regimes the authors could recognize. Both anchors survive their stronger formulations; the case against is weak.
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.