| paper | d4-conf-sigecom-2003-0023 |
| 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 exact core is always nonempty. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given an explicit finite routing-role graph, rational type masses \(\mu_t\), per-unit capacities \(c_t\), symmetric demand densities \(d_{tu}\), and allowed route templates, define \(V(z)\) as the maximum routed flow for a coalition with type masses \(0\le z_t\le\mu_t\), capacities \(c_tz_t\), and pair demands \(d_{tu}z_tz_u\) for distinct types and \(d_{tt}z_t^2/2\) within a type. Compute nonnegative per-unit payoffs \(p_t\) such that \(\sum_t\mu_tp_t=V(\mu)\) and \(\sum_tz_tp_t\ge V(z)\) for every coalition vector \(z\).
Agents are routing nodes grouped by complete routing role, with mass \(\mu_t\); a coalition selects any mass \(z_t\le\mu_t\). Capacities scale with mass, pair demands scale with the product of endpoint masses, and routes follow the finite role graph. The objective is a transferable core payoff per unit of mass. A dual certificate has the form \(p_t=c_tx_t+\frac12\sum_u d_{tu}\mu_u y_{tu}\), with route pricing given by shortest paths in an explicit graph.
The role-template model may fail to preserve topology-dependent path availability for every coalition unless it encodes enough detail to make the number of types approach the number of nodes; the proponent acknowledges this limitation for irregular networks.
fatal: False
Covers Theorem 3's transferable-payoff core allocation for replicated routing roles. It leaves Theorem 4's non-transferable result and Theorem 5's concave-utility extension outside the proposed mirror.
I would make the lead Continuum Typed Routing Core. The population consists of network nodes or autonomous systems, with type recording each node’s complete routing role: its capacity, traffic-demand profile, and place in a repeated route template. Mass \(\mu_t\) is the fraction of the population in role \(t\). A coalition may take any measurable share \(z_t\le\mu_t\) of each type. Its decision is how much flow to route along each admissible role path; its value is the maximum total flow. Transferable payments then assign each unit of mass a payoff \(p_t\).
A plausible regime is a large regional network made of many interchangeable access networks or points of presence in a small number of repeated roles. There might be thousands of participants but only tens of route roles, so \(n\gg\tau\). Capacities scale with mass, and pairwise demand is represented by a demand density: for distinct types \(t,u\), a coalition with masses \(z_t,z_u\) has aggregate demand \(d_{tu}z_tz_u\); within one type, it has \(d_{tt}z_t^2/2\). This is the high-multiplicity assumption made concrete: members of a type are interchangeable in every feature the routing game uses.
My anchor is Theorem 3, proved in this paper. It says that for every finite node-capacitated, demand-constrained multicommodity-flow game with transferable payoffs, the core is non-empty and a core allocation can be computed in polynomial time. The construction uses an optimal solution to the dual of the path-flow LP: node \(i\) receives \(p_i=c_ix_i+\frac12\sum_j d_{ij}y_{ij}\), where \(x_i\) and \(y_{ij}\) are the capacity and demand dual variables. The paper invokes polynomial solvability of the dual despite its path-indexed constraints. It contains no named hardness result, so this is its strongest computational anchor.
Precisely, the continuous problem takes a finite role graph, rational masses \(\mu_t\), per-mass capacities \(c_t\), symmetric demand densities \(d_{tu}\), and admissible route templates. For each \(z\in[0,\mu]\), let \(V(z)\) be the maximum total routed flow, subject to capacity \(c_tz_t\) at each role and the coalition’s type-pair demand limits. The task is to output nonnegative per-mass payoffs \(p_t\) satisfying
\[
\sum_t\mu_tp_t=V(\mu)
\quad\text{and}\quad
\sum_tz_tp_t\ge V(z)\quad\text{for every }z\in[0,\mu].
\]
That is a transferable core allocation for the continuum society; the solution is the payoff vector, with a grand-coalition optimal flow and dual prices as a certificate.
I expect this problem to be Class A, tractable, when the route template is explicit. The grand-coalition flow problem is an LP. Its optimal dual prices give the same kind of allocation as in Theorem 3: capacity prices are charged per unit of mass, and demand-price value is split between the two endpoint populations. For any smaller coalition, those grand-coalition demand-price payments dominate the dual value available to its reduced pairwise demands, while the capacity prices remain feasible. If routes are represented implicitly by a finite role graph, pricing a route is a shortest-path computation. The full question therefore retains the paper’s flow and coalition-stability structure, while making the player population continuous.
The weakest point is the role-homogeneity assumption. Topology matters: two nodes with the same capacity but different route access are not the same type. The mirror is convincing for replicated networks with a small number of genuinely interchangeable routing roles; in an irregular network, faithfully encoding route positions may make \(\tau\) nearly \(n\), leaving little high-multiplicity benefit. The demand-density scaling is also a model choice, though it is the natural way to preserve finite aggregate demand as the population becomes nonatomic. This mirror covers Theorem 3 only; it does not claim to cover the non-transferable result in Theorem 4 or the concave-utility extension in Theorem 5. The next questions would be whether the same certificate works for richer typed routing templates and whether a continuum non-transferable core can be computed.
Theorem 3 is a genuine computational anchor: it gives a polynomial-time algorithm for computing a core allocation. The fact that flows are divisible does not make this a continuous-population result.
The strongest objection is that the payoff of a coalition depends on its induced network, not just on the amounts of each node type it contains. The paper’s input includes a graph and a demand for each pair of nodes. Two societies with the same type masses, capacities, and pairwise demand totals can have different coalition values because their links differ. For example, a cycle and two disjoint cycles can have the same node counts and degrees, while coalitions in the connected network can route traffic between groups that cannot communicate in the disconnected one.
A type-level model can preserve those values only if it also preserves enough relational structure to determine every coalition’s available paths. For a general sparse network, that structure can require essentially the original links and pairwise demands; grouping by routing role then gives little compression. Replacing it with type-pair densities assumes homogeneous mixing. That can change which coalitions can route traffic and which nodes are pivotal. A richer graph limit may preserve more, but its input must still encode the correlations needed to answer coalition queries.
Exact replication is the strongest repair: a network built from many interchangeable access domains, with identical route roles and suitably uniform demand, can plausibly be represented by a small type graph and masses. That is coherent and the authors could recognize it as a version of their game. Its limitation is that the negative case cannot rule it out: this looks like a real high-multiplicity regime, rather than a mere fractional-outcome reformulation. So topology gives a serious objection to the paper’s general Internet-routing setting, but I cannot honestly claim it defeats every plausible mirror. The case against this anchor is weak on the universal burden.
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.