| paper | d4-conf-atal-2021-0037 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the problem is in \(\mathrm{P}\), every valid input is feasible, and an explicit rational sequence is constructible in \(O\!\left(h^2(L+\tau\log(h+1))\right)\) bit operations. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given a finite support \(T\) of \(\tau\) operational types, rational masses \(\mu_t>0\) summing to \(1\), and a sequence length \(h\), construct finite mass partitions \(\Pi_1,\ldots,\Pi_h\). Each coalition is a nonzero vector \(q\in\mathbb{Q}_{\ge 0}^{\tau}\), and each \(\Pi_i\) must sum to \(\mu\). For every \(i<h\), require that each \(q'\in\Pi_{i+1}\) has a parent \(q\in\Pi_i\) with \(q'_t\le q_t\) for all \(t\), and that \(|\Pi_i|<|\Pi_{i+1}|\).
A continuum of interchangeable responders or equipment units represented by type masses \(\mu\). A coalition is a vector of type masses; the decisions are successive partitions refining one another. The objective is feasibility only, with no coalition-value objective.
The mirror covers Theorem 4.1’s feasibility guarantee for \(R_S\). It leaves out value maximization, the \(R_H\) and \(R_O\) cases, the modelling and expressiveness results, and the experiments.
The only computational anchor I would use is Theorem 4.1, proved in this paper. It says that for an SCFG \(G=\langle A,H,R\rangle\), where \(R\in\{R_H,R_S,R_O\}\), MC-Link eventually outputs a feasible coalition-structure sequence if one exists. Its running time is \(O(h^2n^3\alpha)\) and space is \(O(n^2+hn+\beta)\), where \(\alpha\) and \(\beta\) are the time and space costs of evaluating \(R\). I rely specifically on its \(R_S\) case: later coalition structures refine earlier ones, with the number of coalitions strictly increasing. Theorem 2.2 and Theorem 3.1 concern expressiveness and modelling, while the introduction’s coalition-generation hardness claim is cited from earlier work; I would not use those as computational anchors here.
My lead mirror is Continuous \(R_S\)-FCSS Construction. A plausible regime is a large disaster response operation drawing, say, tens of thousands of interchangeable responders and equipment units from a few dozen operational types. A type records every relevant feature—such as certification, equipment class, location, and availability—so members of one type have the same eligibility and valuation in each stage. The number of units is then much larger than the number of types. Mass represents a fraction of the eligible resource cohort; splitting mass means assigning members of a large interchangeable cohort to different groups, while each actual unit remains assigned as a whole.
Precisely, the input is a finite support \(T\) of \(\tau\) types, rational masses \(\mu_t>0\) with \(\sum_{t\in T}\mu_t=1\), and a finite sequence length \(h\). A coalition is a nonzero vector \(q\in\mathbb{Q}_{\ge 0}^{\tau}\) giving the mass of each type in that group. A coalition structure \(\Pi_i\) is a finite list of such vectors summing to \(\mu\). The question is to construct \(\Pi_1,\ldots,\Pi_h\) such that, for every \(i<h\), each coalition \(q'\in\Pi_{i+1}\) has a parent \(q\in\Pi_i\) with \(q'_t\le q_t\) for every type \(t\), and \(|\Pi_i|<|\Pi_{i+1}|\). A solution is the sequence of mass partitions, with parent assignments certifying refinement. This is a feasibility problem, so it has no payoff objective: Theorem 4.1 guarantees a feasible sequence, not an optimal one.
I expect this continuous construction problem to be tractable. Starting with the whole mass in one coalition, one can split any positive mass into two at each step, producing a rational witness for every finite \(h\). This is a direct mass version of the paper’s \(R_S\) feasibility condition, and the disaster-response hierarchy gives it a natural high-multiplicity interpretation. The continuous question is polynomial in the size of its output, with no bound tied to the number of individual units.
That easy construction is also the case’s weakest point. The theorem’s most interesting algorithmic setting is finding a useful sequence guided by coalition values; its stated guarantee is only that MC-Link finds a feasible seed. Once mass can be split freely, the seed-feasibility question loses much of the discrete challenge, and this mirror does not settle the paper’s central value-maximization problem or transfer any hardness. The natural next question is whether a continuous \(R_S\) version of maximizing \(\sum_i V_i(\Pi_i)\), under explicit assumptions on the type-level valuation functions, admits an exact or approximate algorithm. That is a stronger and more central mirror, but Theorem 4.1 alone does not establish its complexity.
The only anchor here is Theorem 4.1, and its \(R_S\) case is weaker than the proponent’s framing suggests. It guarantees a feasible sequence when one exists; feasibility does not depend on the characteristic functions. In the proposed mass model, start with the whole mass in one coalition and split a positive coalition in half at each stage. This gives a rational witness for any finite \(h\), with output size polynomial in \(h\) and \(\tau\). The construction works even with one type and does not use MC-Link’s value-guided choices. In the discrete theorem, strict growth in the number of coalitions imposes \(h\le n\); with divisible mass that bound disappears. Keeping indivisible units restores the bound, but then the feasibility question is a simple discrete refinement problem.
The more substantive mirror would optimize \(\sum_i V_i(\Pi_i)\) over feasible mass partitions, as MC-Link’s greedy improvements are meant to do. That requires a value function for fractional type-mass coalitions. The paper supplies arbitrary characteristic functions on subsets of named agents. Even if agents within each type are interchangeable, those values determine a function only on integer count vectors; they do not specify its values on fractional vectors. Different extensions can agree on every discrete coalition and yield different continuous optima. A compact, natural type-level production function could make a good new problem, especially for disaster response, but choosing and encoding that function adds the central computational structure rather than inheriting it from Theorem 4.1.
So the proponent’s stated feasibility mirror is well-posed but computationally empty, while the stronger optimization mirror is plausible only after adding assumptions the theorem does not establish. That is the strongest negative case I see. It remains limited: a disaster-response model with credible, compact valuations over resource mixtures could still be a worthwhile continuous mirror, and this argument cannot rule out such a model.
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.