| paper | d4-conf-sigecom-2007-0041 |
| 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: Polynomial-time solvable; every valid instance admits a strong equilibrium. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3.4
statement extracted from the paper’s text layer
Given a directed series-parallel graph with common source \(s\), rational edge costs, and rational masses on finitely many sink types, does there exist a path-mass assignment with no positive-mass measurable coalition whose members can all reroute to strictly lower their costs?
Each type is a source–sink pair with mass \(\mu_t\); variables \(x_{t,P}\) assign that mass across available paths, and edge load is \(\ell_e=\sum_{t,P:e\in P}x_{t,P}\). A unit of mass using edge \(e\) pays \(c_e/\ell_e\), and a strong equilibrium is an assignment with no blocking measurable coalition.
The proposed mirror covers Theorems 3.4 and 3.5 for fair connection games; it leaves the general connection game results, nonexistence examples, and strong-price-of-anarchy bounds unaddressed.
The strongest honest case is an equilibrium-existence mirror for fair cost-sharing routing. One limitation first: this paper gives no named NP-hardness, polynomial-time, or parameterized-complexity result. Its named results concern equilibrium existence and efficiency. So this case rests on the paper’s structural existence theorems; it should not be presented as a mirror of a complexity classification.
A plausible high-multiplicity setting is recurring requests routed through a shared network: for example, many shipments from a hub to a modest number of destinations. A type is an origin–destination pair. Agents of a type have the same available paths and face the same edge costs and fair-sharing rule. The population has total mass \(1\), with mass \(\mu_t\) of each type \(t\); in the regime of interest, the number of requests \(N\) is much larger than the number of supported types \(\tau\).
Here is the continuous model. The input is a finite directed acyclic graph \(G=(V,E)\), rational edge costs \(c_e\ge 0\), and a finite-support distribution \(\mu\) over origin–destination types. For each type \(t\), let \(P\) range over its available paths, and let \(x_{t,P}\ge 0\) be the mass assigned to path \(P\), with \(\sum_P x_{t,P}=\mu_t\). The load on edge \(e\) is
\[
\ell_e=\sum_{t,P:e\in P}x_{t,P}.
\]
A member of type \(t\) using path \(P\) pays \(\sum_{e\in P} c_e/\ell_e\). This is a natural normalization: if \(N\) discrete agents have type proportions \(\mu\), their edge loads are \(N\ell_e\), so their discrete equal shares are \(c_e/(N\ell_e)\). Multiplying everyone’s costs by \(N\) leaves all deviation comparisons unchanged.
A coalition is any measurable positive mass of agents, selected from the current type–path cohorts, who may reroute together. It blocks an allocation if every deviator’s cost after the rerouting and the resulting load changes is strictly lower than before. A solution is a path-mass assignment \(x\) with no blocking coalition. There is no planner’s objective in the existence theorems I use; the natural aggregate social cost, \(\sum_{e:\ell_e>0}c_e\), is useful for later efficiency questions but is not optimized by these anchors.
My lead anchor is Theorem 3.4, proved in this paper: *every single-source fair connection game on a series-parallel graph possesses a strong equilibrium.* The game allows different sinks, but all players share a source; edge costs are split equally among users. The theorem’s proof is structural and inductive.
Its continuous counterpart is Continuous Single-Source Strong-Equilibrium Search on Series-Parallel Graphs. Given a directed series-parallel graph, a common source \(s\), rational edge costs, and rational masses on a finite set of sink types, determine whether a strong path-flow allocation exists and, if so, return one. The direct mirror claim is that every such instance has a solution. A further computational question is whether one can construct it efficiently in \(|V|\), \(|E|\), \(\tau\), and the input bit length. I expect this to be Class A: the original theorem’s graph decomposition may support a mass-based construction. The paper does not establish that extension or a polynomial running time.
A second, broader anchor is Theorem 3.5, also proved here: *every fair connection game on an extension-parallel graph possesses a strong equilibrium.* This covers multiple source–sink pairs. Its mirror is Continuous Strong-Equilibrium Search on Extension-Parallel Graphs: given such a graph and a rational distribution over finitely many origin–destination types, find a path-mass allocation with no blocking measurable coalition, or determine that none exists. I would also tentatively expect Class A, for the same structural reason, though with less confidence: the proof’s decomposition has to handle fractional populations of several commodities at once.
These are problems the authors should recognize as close to their questions. The agents still choose paths, edge costs are still shared fairly, and coalitions still coordinate deviations. The change is that population counts become masses and coalition members can move at arbitrary fractional granularity. That is a meaningful high-multiplicity version of their model, not a switch to fractional outcomes or a noise model.
The further questions are whether the continuous existence claims hold, whether returned equilibria can be represented exactly and constructed efficiently, and where the graph-topology boundary lies once demands are divisible. Hardness does not automatically transfer from a finite instance: in the mass model, agents of one type can split across paths and coalitions can move fractional amounts. Any embedding would need to address that change.
The mirror covers only Theorems 3.4 and 3.5: fair connection games on the stated graph classes. It does not claim a continuous result for general connection games or for the paper’s strong-price-of-anarchy bounds. Its weakest point is the strong-equilibrium definition itself. Allowing any positive mass to deviate changes the blocking condition, and the paper’s finite-player induction does not prove that an equilibrium survives this change. That gap is also the real research question: the scenario, action, cost-sharing rule, and coalition concept remain recognizable, while the theorem to be tested is clearly stated.
The strongest case against these anchors is a fit problem, not a claim that repeated demand is implausible. The paper has named results, but Theorems 3.4 and 3.5 establish existence from graph structure; they do not classify the complexity of a computational problem. In both cases the proposed mirror adds a search task: given masses and costs, construct an equilibrium. That is a possible research question, but it is not a continuous version of a complexity result the paper proves. The corresponding existence decision on the stated graph classes would simply ask whether the paper’s universal guarantee survives the change of model.
For Theorem 3.4, repeated requests from one source to a small set of destinations make a credible high-multiplicity regime. Still, the best version of the mirror—finding a path-mass allocation stable against every measurable blocking coalition—is chiefly a new nonatomic coalition-equilibrium problem. The finite theorem neither studies an algorithmic input-output task nor supplies a complexity benchmark for it. Expanding the question to classify graph topologies might produce a useful structural theorem, but that would extend the paper’s game-theoretic existence programme rather than fill the continuous computational-complexity gap ChoCo describes.
The same objection applies to Theorem 3.5 on extension-parallel graphs. Multiple origin–destination request types give it a plausible mass model, and an algorithm for constructing an equilibrium could be worth studying. But the paper’s result is again a topology-based existence guarantee, not a computational classification. Its continuous counterpart therefore becomes a new search or structural-classification problem, rather than a mirror of a discrete algorithmic result.
There is a real modeling question too, though I would not treat it as decisive. In the finite game, agents are indivisible and strong equilibrium rules out a blocking coalition of any size. In the mass model, a coalition can move an arbitrarily small fraction of a type’s traffic. That is a coherent limit concept, but the strict-blocking condition ranges over a different set of deviations; the finite theorem does not supply a two-way correspondence. The programme explicitly treats such a change as a potential co-modification, so it cannot by itself disqualify the mirror.
I cannot honestly sustain the universal claim that no scenario yields a worthwhile continuous mirror: the repeated-request setting is credible, and both proposed questions are well defined. The negative case is narrower: these anchors look like an adjacent equilibrium-existence project, not strong examples of the computational landscape ChoCo is intended to chart. That is a fit concern, not a convincing demonstration that the mirrors themselves lack value.
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.