| paper | d4-journals-geb-2024-0099 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: In \(\mathrm P\). Every valid input has a unique core vector, and exact algebraic charges are computable in time polynomial in \(\tau\) and \(L\). The proposed charges fail whenever \(b\leq u\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), waiting rates \(w_t>0\), and machine cost \(b\), let \(x_t\in[0,\mu_t]\) describe a coalition of mass \(\alpha=\sum_t x_t\). Sort its waiting rates in decreasing order as \(w_x(r)\), for \(r\in[0,\alpha]\), and define \(C(0)=0\) and \(C(x)=\min_{0<q\leq\alpha}\{bq+\int_0^\alpha (r/q)w_x(r)\,dr\}\). Decide whether there are type-level charges \(p_t\) with \(\sum_t\mu_t p_t=C(\mu)\) and \(\sum_t x_t p_t\leq C(x)\) for every coalition mass vector \(x\), and output such charges or certify that none exist. The direct analogue of Theorem 1(i) asks, in particular, whether \(p_t=\min(b+w_t,2w_t)\) is in the core when \(b\) is at most the upper weighted median waiting rate.
A fluid queueing cost game with waiting-cost types carrying mass, machine capacity \(q\), and type-level cost shares \(p_t\); coalitions choose submasses and the machine mass that minimizes their queueing cost.
The paper's completion times are integer periods, while the proposed fluid objective uses continuous completion time \(r/q\); the proponent does not derive this objective as a limit of the paper's scheduling costs.
fatal: False
The mirror covers the from-scratch queueing cost game and its core-feasibility question, including the low-machine-cost case of Theorem 1. It leaves the finite-instance core characterizations of Theorem 2 and the private and public requeueing results of Theorems 3–5 without a specified continuous mirror.
There is no qualifying computational anchor in this paper. Theorem 1 gives a cost allocation that is in the core under a machine-cost bound; Theorem 2 characterizes the core in two further cost ranges; Theorem 5 proves core non-emptiness for public requeueing with an efficient initial order and side payments. These are substantive results, but they establish game-theoretic existence and structure, not that a computational problem is in P, NP-hard, FPT, or similar. They are proved here, but I would not present them as computational anchors.
The strongest positive lead is a continuous version of the paper’s queueing game from scratch. Imagine a large vaccination or inspection service: jobs take the same time, but people fall into a small number \(\tau\) of urgency classes with distinct waiting-cost rates. Each type is a complete description for this model; its mass is the fraction of the population in that class. The population is large while \(\tau\) stays small, so class masses are the natural units for coalitions and cost sharing.
Here is a precise candidate problem. The input is a finite set of types \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), positive waiting rates \(w_t\), and a machine cost \(b\). For a coalition represented by masses \(x_t\in[0,\mu_t]\), let \(\alpha=\sum_t x_t\), and let \(w_x(r)\) be its waiting rates sorted from highest to lowest over cumulative mass \(r\in[0,\alpha]\). If it installs machine mass \(q\in(0,\alpha]\), its normalized cost is
\[ C(x)=\min_{0<q\leq\alpha}\left\{bq+\int_0^\alpha \frac{r}{q}w_x(r)\,dr\right\}, \qquad C(0)=0. \]
Here \(q\) is the number of machines per unit of total population. The integral is the limit of the queue’s waiting costs when ranks and machine counts are measured as population fractions; \(bq\) is the corresponding per-capita machine cost. Jobs are ordered by decreasing waiting rate, as in the paper.
Call this the continuous queueing cost-core problem: given \((T,\mu,w,b)\), decide whether there are type-level charges \(p_t\) satisfying
\[ \sum_{t\in T}\mu_t p_t=C(\mu) \quad\text{and}\quad \sum_{t\in T}x_t p_t\leq C(x) \quad\text{for every }x\in[0,\mu]. \]
A solution is such a charge vector, or a certificate that none exists. It mirrors the paper’s cost game: coalitions choose their queue and machine level, then ask whether the grand coalition’s costs can be shared so no coalition pays more than its standalone cost. It covers queueing from scratch, not the paper’s private or public requeueing games.
The closest result is Theorem 1(i), proved here: if \(b\leq w_{\lceil n/2\rceil}\), then the allocation \(y_i=\min(b+w_i,2w_i)\) is in the discrete game’s core. This suggests a restricted continuous question: when \(b\) is at most the median waiting rate, does \(p_t=\min(b+w_t,2w_t)\) give a core allocation? I would expect that restricted problem to be tractable if the continuous analogue of the theorem holds. But that claim needs a proof for every fractional coalition \(x\); the paper does not provide it. For the unrestricted continuous problem, I would not assign a class on this evidence. Its constraints range over all coalition-mass vectors, and the paper gives no complexity result for resolving them.
The high-multiplicity case is plausible: the queueing model already depends on agents through their waiting rates, and urgency classes in a large service population are a credible regime with \(N\gg\tau\). The authors could reasonably recognize this as a continuous extension of their cost game. The necessary scaling turns machine counts and coalition sizes into masses; the population remains the object being continuized. The further questions are whether the finite core formulas survive fractional coalitions, how to check all coalition constraints efficiently, and whether any discrete hardness has a continuous counterpart.
The weak point is decisive for ChoCo: even a convincing continuous model does not supply this paper with a named computational result to mirror. Also, allowing fractional machine mass and fractional coalitions changes the game, so the continuous question is a proposed extension rather than a limit identity established by the authors.
There is no computational result in this paper to mirror. Theorems 1 and 2 establish when the core is nonempty and describe core allocations; Theorem 5 establishes core nonemptiness for a public requeueing game under stated conditions. None classifies an algorithmic problem by complexity or presents an algorithmic bottleneck such as a pricing problem. The paper’s main optimization is choosing a queue and a number of machines, not analyzing the complexity of doing so. That makes the paper a poor fit for ChoCo’s stated task of charting the computational landscape.
The strongest proposed mirror, based on Theorem 1, is nevertheless a credible continuous game. Grouping people with the same waiting cost into types is natural, and the proposed scaling of machine counts and costs is coherent. Fractional coalitions also fit a population model. I would not reject it on grounds of identity, multiplicity, or a degenerate limit.
The gap is that the proposed computational problem is added after the fact. Theorem 1 gives a core allocation in a specified cost range; it does not ask how to decide core existence or compute allocations. One could extend the question to computing the core for all inputs, but that would be a new algorithmic question about a newly defined continuum game. The fractional coalition constraints and machine mass \(q\) are sensible modelling choices, yet they do not turn the paper’s existence theorem into a computational result it actually contains. The candidate is a plausible research direction, but a weak mirror of this paper under the programme’s computational remit.
The requeueing results offer a less direct route. An agent’s initial position affects their baseline cost and the savings they can obtain by moving. With a fixed number of machines, a type that records both waiting cost and initial queue position generally has little multiplicity. A fluid model could instead track a distribution over waiting costs and queue positions, but that would require building a new population-level requeueing model and specifying its coalition options. It is a possible extension, not a computational mirror supplied by Theorems 3–5.
So the negative case is strongest on fit: the paper studies cooperative-game existence and structure, rather than computational complexity. It is not strong enough to establish the universal claim that no worthwhile continuous mirror exists. The from-scratch queueing game remains a plausible continuous model; what is missing is a compelling connection from this paper’s theorems to the computational questions ChoCo is meant to classify.
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.