| paper | d4-conf-ecai-2023-0097 |
| 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: Exact minimization is polynomial-time solvable in \(m=k\), \(\tau\), and \(L\), including computation of an exact rational optimal allocation. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given vehicle types \(r=1,\ldots,\tau\) with fleet masses \(\mu_r\), \(k\) charging stations, a fixed station-mass profile \(q_1,\ldots,q_k\) with \(\sum_j q_j=1\), and rational workload coefficients \(h_{rj}\), choose allocations \(x_{rj}\geq 0\) satisfying \(\sum_j x_{rj}=\mu_r\) and \(\sum_r x_{rj}=q_j\) to minimize the maximum station workload \(\max_j \sum_r h_{rj}x_{rj}\).
A society is a distribution \(\mu\) over recurring vehicle types, each defined by its charging-relevant attributes. The fixed configuration specifies the fraction \(q_j\) assigned to each station; \(x_{rj}\) is the mass of type \(r\) sent to station \(j\), and \(h_{rj}\) is its workload contribution there. Minimizing maximum workload is a linear program with an epigraph variable.
The LP optimizes over all type-mass allocations, while Theorem 3 bounds PISA's seeded candidate generation; the continuous question therefore does not mirror that theorem's precise computational workload.
fatal: False
The mirror covers fixed-profile SCSGA for the paper's electric-vehicle makespan objective; it does not cover PISA's candidate-generation bound itself, the general arbitrary coalition-value model, the second workload objective, or the empirical comparisons.
The strongest honest case is a mirror of one fixed subspace of SCSGA, in a high-multiplicity fleet setting.
My anchor is Theorem 3, proved in this paper. It claims that, for \(n\) agents and \(k\) tasks, PISA searches one subspace—one ordered profile of coalition sizes—in \(O(n^4 k^2)\) time. The proof counts \(O(k^2)\) pre-initial vectors, \(O(n^2)\) initial vectors per pre-initial vector, and \(O(n^2)\) permutations per initial vector. This is a bound for searching a single subspace, not a polynomial-time bound for the full SCSGA problem. The paper’s abstract calls SCSGA NP-complete, but that claim is not a numbered result; the introduction’s cited NP-completeness result concerns the related CSG problem.
A continuous counterpart of that subspace search is Type-Continuous Fixed-Configuration SCSGA. Consider a large fleet of electric vehicles with a small number \(\tau\) of recurring vehicle types—such as battery capacity and maximum charging power—and \(k\) stations treated as tasks. Type \(r\) has mass \(\mu_r\), the fraction of the fleet of that type. Fix a configuration \(q_1,\ldots,q_k\), where \(q_j\) is the fraction assigned to task \(j\), \(\sum_j q_j=1\). This fixes the total mass of each task’s coalition, just as a PISA subspace fixes its coalition sizes.
For each task \(j\), specify a rational, concave piecewise-linear welfare function on the type masses assigned to it:
\[
F_j(x)=\min_{a\in A_j}\left(b_{ja}+\sum_{r=1}^{\tau}w_{jar}x_r\right).
\]
The question is to find an allocation \(x_{rj}\geq 0\) maximizing \(\sum_j F_j(x_{\cdot j})\), subject to \(\sum_j x_{rj}=\mu_r\) for every type \(r\) and \(\sum_r x_{rj}=q_j\) for every task \(j\). A solution is the rational mass allocation and its welfare. These constraints make the action explicit: split each type’s mass among tasks while preserving both the fleet’s type proportions and the chosen coalition-size profile.
This is tractable for the stated valuation family: introduce a variable \(y_j\) for each task, constrain it below every affine piece of \(F_j\), and maximize \(\sum_j y_j\). That is a rational linear program, with size polynomial in \(\tau\), \(k\), the number of pieces, and the input bit length. The expected classification is Class A for this structured mirror. Further questions are whether the result extends beyond concave piecewise-linear valuations, and whether removing the fixed configuration preserves tractability.
The regime is plausible: a large fleet may contain thousands of vehicles but relatively few charging profiles, so agents of each type are interchangeable for the allocation model. The paper itself motivates SCSGA with electric vehicles and station-specific charging characteristics. Its workload objective also gives a natural additive special case, though the paper’s separate minimax workload criterion would require its own formulation.
The weak point is substantial: this mirror restricts the paper’s arbitrary coalition-value function to a concave, explicitly continued family, and fixes one coalition-size profile. Theorem 3 itself says nothing about the complexity of the full problem. I would present this as a credible continuous analogue of the particular subspace search PISA performs, not as evidence that general SCSGA becomes tractable.
The strongest objection is that the proposed LP does not mirror Theorem 3’s computational claim. That theorem bounds the work PISA performs on one fixed coalition-size configuration. In the paper’s general SCSGA model, configurations fix coalition sizes, while coalition values can depend arbitrarily on which agents are grouped together. The proposed LP replaces those values with concave piecewise-linear functions of type masses. Its polynomial runtime follows from that added structure; it does not explain the cost of PISA’s search.
There is also a problem with treating Theorem 3 as a bound for exhaustively searching a configuration. For \(k=2\) and the profile \([n/2,n/2]\), the configuration contains \(\binom{n}{n/2}\) coalition structures. PISA’s described seed generation and pairwise swaps produce only polynomially many candidates. The theorem’s bound therefore accounts for PISA’s generated candidates, not evaluation of the full subspace. A continuous question about an LP over type masses would concern a different operation.
The best version of the mirror would use the paper’s own electric-vehicle model: group vehicles into recurring types, fix station masses \(q_j\), and optimize the stated workload objectives over type-to-station mass allocations. That is a sensible high-multiplicity question, and the linear workload objectives give a well-defined LP. It still does not mirror Theorem 3’s permutation-search bound, but it does mirror a restricted SCSGA allocation problem the authors would likely recognize.
So the negative case can defeat the claimed connection to Theorem 3; it cannot honestly establish that no worthwhile continuous mirror exists. The EV mass-allocation version remains a credible mirror, and dismissing it because its LP is standard or easy would not meet the programme’s stated test.
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.