| paper | d4-conf-atal-2017-0298 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 2 is a named conditional hardness result, but its query extracts one game of exactly \(2k\) individual players. In a population limit with fixed-size query, every positive-mass type eventually has ample supply, while vanishing rare types can still determine finite instances; the proposed fractional slots instead ask for a divisible team. That changes the unit of analysis, so no population-continuous question survives for this anchor that the paper would recognize.
fails bit b-changes — the continuum limit changes the question
The fixed \(2k\)-player demand does not scale with the queue, so positive-mass types become interchangeable in abundance and rare types disappear from the limiting distribution; the proposed fractional roster does not preserve the paper’s best-game query.
fatal: True
The proposed mirror covers only Theorem 2’s role-restricted queue query; it leaves Theorems 1, 3, 4, and 5 and the other results unaddressed. The opponent notes that batch or offline partitioning could be a more plausible mirror, but it was not an anchor in the proponent’s case.
The strongest anchor is Theorem 2, proved in Section 5. It says that for \(k\ge3\), assuming the 3SUM conjecture, a data structure for the role-restricted queueing problem must take \(n^{1-o(1)}\) time per insertion or \(n^{2-o(1)}\) time per query. The proof gives a stronger conditional form: if \((2k-2)\)SUM requires \(n^{c-o(1)}\) time, then insertion requires \(n^{c-1-o(1)}\) time or query requires \(n^{c-o(1)}\) time. The paper proves the reduction; the hardness assumption is imported.
A plausible high-multiplicity regime is a large matchmaking pool whose system uses a finite grid of skill ratings. A type is the pair \(t=(s_t,R_t)\): the rating used by the matchmaker and the set of roles the player accepts. These attributes determine everything the paper’s objective and feasibility rules use. With \(H\) rating values and \(k=5\), there are at most \(32H\) types, even if the queue contains far more players. This is a scenario about a particular rating regime, not a claim that every game queue has few types.
Here is the continuous question I would hand to a prover. Fix \(k\ge3\), \(p=q=1\), and \(\alpha=1\), all allowed choices in the paper’s model. The input is a finite support of types \(t=(s_t,R_t)\), with nonnegative rational masses \(a_t=N\mu_t\), where \(N\) is the queue’s total mass and \(\mu\) is its type distribution. The query chooses a fractional role-restricted game. Let \(x_{t,b,j}\ge0\) be the mass of type \(t\) assigned to team \(b\in\{A,B\}\), role \(j\in[k]\). Require \(x_{t,b,j}=0\) if \(j\notin R_t\), one unit of mass in every team-role slot,
\[
\sum_{t:j\in R_t}x_{t,b,j}=1 \quad\text{for every } b,j,
\]
and no type mass to be used twice,
\[
\sum_{b,j}x_{t,b,j}\le a_t \quad\text{for every }t.
\]
The total selected mass is \(2k\). Set
\[
\bar{s}(x)=\frac{1}{2k}\sum_{t,b,j}x_{t,b,j}s_t
\]
and minimize
\[
F(x)=
\left|\sum_{t,j}x_{t,A,j}s_t-\sum_{t,j}x_{t,B,j}s_t\right|
+\frac{1}{2k}\sum_{t,b,j}x_{t,b,j}|s_t-\bar{s}(x)|.
\]
The solution is an optimal allocation \(x\) and its value. Its dynamic version supports adding or removing rational mass at a type and answers this query after each update. The relevant parameters are \(k\), support size \(\tau\), and the binary input length \(L\).
This preserves the paper’s central question: find the best role-feasible game under its fairness and uniformity objective. The population is the continuous object. A mass unit is assigned to one team and one role; only the type-level amounts \(x_{t,b,j}\) can be fractional. In a real high-volume queue, this describes an aggregate game template. The authors could reasonably recognize it as the high-multiplicity relaxation of their query, though they would still need to accept a fractional template as the continuous analogue of selecting a playable roster.
I would expect the mass query to be Class A for fixed \(k\), with complexity polynomial in \(\tau\) and \(L\). The reduction behind Theorem 2 relies on selecting whole players whose skill values encode a KSUM witness. Fractional type masses can mix across role slots, so that exact selection witness may disappear. For \(p=q=1\), fixing the mean skill and the sign of the team-score difference makes the objective linear in \(x\); that suggests a parametric optimization over the role-assignment constraints. This is a route to investigate, not a tractability proof. In particular, the mean \(\bar{s}(x)\) depends on the chosen allocation, so the whole objective is not immediately an LP.
My weakest point is that a fractional game need not be a single roster that the service can put on the server. A rounding or batch-realization result would strengthen the application, and the exact mass problem might still be hard for reasons the 3SUM reduction does not capture. The open questions are whether the exact query is polynomial in \((\tau,L)\), whether type-mass updates can be maintained efficiently, and how the answer changes for other \(p,q,\alpha\). This mirror covers Theorem 2’s role-restricted queue query; it does not claim to mirror the paper’s offline partitioning or approximation results.
Theorem 2 is the right anchor, but its query is for one game of fixed size \(2k\). That makes the population limit unstable. If a type \(t=(s_t,R_t)\) has positive share \(\mu_t\), then in a queue of size \(N\) it has \(N\mu_t\) players. Once \(N\mu_t\ge 2k\), its exact abundance cannot affect whether it can supply a roster: any one game can use at most \(2k\) of them. In the large-population limit, the query depends on which types are present, not their proportions. Conversely, a rare type represented by one or two players can affect the best game while its share tends to zero and disappears from the limiting distribution. Those are precisely the players a distribution over the bulk may fail to record.
The proposed LP exposes the modeling problem. With slot demand fixed at one and capacities \(a_t=N\mu_t\), every positive-mass type eventually has more than enough capacity, so the mass constraints stop conveying the queue’s composition. If instead the unit of mass is normalized to population size, a slot of mass one represents a growing group of people, not one player in a fixed-size match. There is no scaling that both preserves the finite roster and makes its composition depend meaningfully on the limiting population proportions.
Allowing \(x_{t,b,j}\) to be fractional does not resolve that mismatch: a role slot filled partly by one type and partly by another is not a playable roster. It could stand for a lottery over rosters, but the objective is evaluated on the fractional mixture. Because it contains absolute values, that value need not equal the expected imbalance of a realized roster. Asking for a lottery with its own objective, or for a batch of games that realizes aggregate proportions, is a different question. The batch version is especially plausible, but it changes the unit of analysis from the paper’s best-game query to partitioning a population.
This is a real weakness in the case against the paper as a whole: the batch or offline partitioning results could admit a worthwhile continuous mirror. But for the analyst’s specific anchor, the obstacle is more basic than whether the 3SUM hardness survives: a fixed-size best-game query is driven by finite selections and rare types, while a population distribution records aggregate mass. I would reject this proposed mirror as a faithful continuization of Theorem 2, while conceding that the broader “no worthwhile mirror in any scenario” claim is not established.
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.