| paper | d4-conf-atal-2014-0328 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\): exact optimization and the strict threshold decision are possible in \((\tau^4+L)^{O(1)}\) bit time. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 13
statement extracted from the paper’s text layer
Given a fixed weighted network whose edge roles \(a\) have endpoints and weights \(w_a\), and a population distribution \(\mu\) over those roles, maximize total team value over simple source-to-target paths \(r\). For each path let \(q(r)=\min_{a\in r}w_a\), and let \(x_r\ge 0\) be the mass of teams assigned to \(r\). Find an optimal \(x\) for \(\max \sum_r q(r)x_r\), subject to \(\sum_{r\ni a}x_r\le \mu_a\) for every role \(a\).
Types are edge roles \(a\) specified by endpoints and weight, with population mass \(\mu_a\); decision variables \(x_r\) are masses of teams assigned to paths; maximize \(\sum_r (\min_{a\in r}w_a)x_r\) subject to each role’s supply constraint \(\sum_{r\ni a}x_r\le\mu_a\).
Covers the decision question in Theorem 13 through the continuous optimal value; leaves the paper’s core, least-core, cost-of-stability, and approximation results unaddressed.
My lead mirror is Fractional WLG Coalition Structure, for the result in Theorem 13. The theorem is proved in this paper: given a WLG, deciding whether the value of its optimal coalition structure exceeds a specified threshold is NP-hard. Its proof reduces from the Disjoint Paths Problem, encoding prescribed source–target pairs with edges of distinct weights.
A plausible high-multiplicity setting is a large logistics market on a fixed network. Each agent is a supplier for one link role, specified by its endpoints and maximum load. Many suppliers may offer the same role under the same conditions. A team assembles suppliers along an \(s\)-to-\(t\) route; its value is the route’s weakest load limit. The society is a distribution \(\mu\) over link roles, with \(\mu_t\) the fraction of suppliers for role \(t\). The network and route choices stay discrete; the population and the mass of teams using each route are continuous. The regime is \(N\gg\tau\): many suppliers, but comparatively few distinct roles.
For a finite set \(T\) of roles and simple \(s\)-to-\(t\) paths \(\mathcal P\), write \(q(r)=\min_{t\in r}w_t\). The continuous problem is:
\[ \begin{aligned} \text{maximize}\quad & \sum_{r\in\mathcal P}q(r)x_r\\ \text{subject to}\quad & \sum_{r\ni t}x_r\le \mu_t &&\text{for each }t\in T,\\ &x_r\ge 0 &&\text{for each }r\in\mathcal P. \end{aligned} \]
Here \(x_r\) is the mass of teams per capita assigned to route \(r\). A solution is an optimal rational vector \(x\), or its optimal value; unused suppliers can remain in zero-value singleton coalitions. The objective is the original sum of team values, normalized by population size. In a finite instance with \(N\mu_t\) suppliers of each role, the corresponding variables are integer counts of teams; the continuous question relaxes those counts to masses. This preserves the paper’s team-formation objective and weak-link value while pooling only agents identical for the problem.
This is a credible tractability candidate, not just a softer question with different outcomes. The LP has exponentially many path variables, but its pricing problem is polynomial: given dual prices \(y_t\), find a route maximizing \(q(r)-\sum_{t\in r}y_t\). For each possible bottleneck threshold \(\alpha\in\{w_t:t\in T\}\), restrict to edges with \(w_t\ge\alpha\) and find a shortest \(s\)-to-\(t\) path under costs \(y_t\). Taking the best threshold solves pricing. Thus the LP is solvable in polynomial time in the graph size, \(\tau\), and the input bit length. It is also the natural high-multiplicity limit of replicated instances: for sufficiently divisible population sizes, a rational optimal route-mass vector can be realized by integral teams. I therefore expect this mirror to be Class A: tractable.
The mirror covers Theorem 13’s optimal coalition-structure decision problem, not the paper’s core, least-core, or cost-of-stability results. It also yields follow-up questions: how quickly can a finite replicated instance approach the LP value when its population size does not clear all denominators, and what approximation or rounding guarantees hold at finite multiplicity?
The weakest point is that Theorem 13’s reduction encodes network disjoint-path structure, so its hardness is not obviously caused only by a small population. The proposed mirror makes team counts divisible while preserving that network structure. That is a substantial, but standard, high-multiplicity co-modification: each actual supplier still joins an ordinary route team, while cohort-level team mass may be fractional. The case is strongest for markets with many interchangeable suppliers per fixed link role; it does not claim to capture every arbitrary WLG instance.
The strongest negative case is that this mirror depends on a narrow change to the paper’s agent model. In a WLG, agents are edges, and an edge’s endpoints and weight determine which coalitions can form a path. Those details must remain part of its type: merging agents from different edges would erase the network structure. In an ordinary simple graph, that leaves one agent per type, so the population is not high-multiplicity. To get many agents per type, the proposed logistics market must add many interchangeable suppliers for each fixed link role—effectively, parallel copies of the same edge. That is plausible for some markets, but it is a special regime, and its support grows with the network’s distinct roles.
The stronger version of the proposal survives that objection. For a fixed network with many interchangeable suppliers per role, route masses with per-role capacity constraints faithfully describe teams: each unit of route mass consumes one supplier of every role on that route. The path-packing LP is a sound continuous population model, and its pricing problem can be solved by checking the finitely many bottleneck weights and finding shortest paths. It also has a natural high-multiplicity interpretation. Calling this merely a fractional relaxation or a standard LP does not defeat it; tractability through continuous optimization is precisely the programme’s target.
So the negative case is weak. I can argue that the mirror applies only to markets where repeated suppliers of the same network role are credible, and that it leaves the graph’s combinatorial structure intact. But those are limits on its scope, not fundamental defects. Under the stated logistics regime, the anchor is a worthwhile continuous mirror, and I cannot honestly make the universal case that no scenario produces one.
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.