| paper | d4-conf-atal-2014-0060 |
| 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: All limits exist as sequence-independent rational numbers, and computing all of them exactly is polynomial-time solvable, in \(\mathrm{FP}\), with \(m=\tau\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Lemma 2
statement extracted from the paper’s text layer
Given a finite role set \(T\), a role graph \(H\), rational proportions \(\mu\), and an explicit rational polynomial \(g\) with \(g(0)=0\), form populations of \(N\) agents with \(N_t/N\to\mu_t\). Agents in the same role form a clique, and roles adjacent in \(H\) have all-to-all links. A connected coalition \(S\) has worth \(N g(x(S))\), where \(x_t(S)=|S\cap V_t|/N\); a disconnected coalition has the sum of its connected components’ worths. Compute the limit, as \(N\to\infty\), of each role’s per-agent Myerson value.
For each connected component \(K\) of \(H\), let \(x^K\) retain the coordinates in \(K\) and set the rest to zero, and define \(F_H(x)=\sum_{K\in\mathrm{cc}(H)}g(x^K)\). The target for role \(t\) is \(\psi_t=\int_0^1 \partial_{x_t}F_H(u\mu)\,du\); for the stated polynomial input, compute this rational vector exactly.
Role blocks make connectivity effectively determined by the role graph at positive mass, removing individual articulation points and the paper’s distinctive sparse-network centrality behavior.
fatal: False
The mirror covers limiting Myerson values for role-block graphs with smooth extensive polynomial worths. It leaves aside the paper’s arbitrary graph algorithms, its \(0\)-\(1\) connectivity games, and its terrorist-network sensitivity analysis.
The strongest named anchor I can honestly use is Lemma 2, proved in this paper: “DFSEnumeration examines edges \(2^{n-2}(n^2-n+4)-(n+1)\) times for an \(n\)-clique.” This is an exact algorithm-analysis result for the paper’s connected-induced-subgraph enumerator, which is then used in the Shapley and Myerson computations. It is not a named theorem that classifies either value computation as polynomial-time or hard; the paper’s broader runtime claims are unnumbered. I would anchor the mirror on this shared computational bottleneck, while being clear about that limitation.
My lead mirror is Block-Myerson Limit-Value Computation. An instance has a finite set \(T\) of agent roles, a graph \(H\) on those roles, a rational mass vector \(\mu\) with \(\sum_{t\in T}\mu_t=1\), and a rational polynomial \(g\) describing coalition worth per capita. A type is a role together with its communication links and worth parameters. Agents of a role are interchangeable: they have identical links to every role and identical effects on coalition worth.
For each population size \(N\), take \(N_t\) agents of role \(t\), with \(N_t/N\to\mu_t\). Agents within a role can communicate with one another, and agents in roles \(s,t\) can communicate whenever \(\{s,t\}\in E(H)\). For a coalition \(S\), write \(x_t(S)=|S\cap V_t|/N\). Its worth, when it is connected, is \(N g(x(S))\); disconnected coalitions receive the Myerson extension, the sum of their connected components’ worths. The task is to output, for every role \(t\), the limiting Myerson value per agent in that role as \(N\) grows. This is a payoff computation, not an optimization problem: the output is the vector of type-level value densities.
The continuum object is precise. For \(x\in[0,1]^T\), let \(x^K\) retain the coordinates in \(K\) and set the others to zero. Define \(F_H(x)=\sum_{K\in\mathrm{cc}(H)}g(x^K)\), where \(\mathrm{cc}(H)\) is the set of connected components of the role graph. The proposed output is \(\psi_t=\int_0^1 \partial_{x_t}F_H(u\mu)\,du\). A prover would establish that this is the limit of the finite Myerson values and give its exact bit complexity. For a rational sparse polynomial of explicitly bounded degree, the integral is rational and can be computed by differentiating and integrating each monomial, in time polynomial in the polynomial’s representation, \(|T|\), and the input bit length.
The regime is a large organization or consortium with many members in a small number of standardized roles and role-based communication channels. For example, there may be millions of members but only a few dozen role types. A role’s mass is its fraction of the population. The role graph preserves the paper’s communication restriction, while the block structure makes high multiplicity exact rather than approximate.
I expect this restricted problem to be Class A. In the finite instances, the enumerator visits connected subsets of individual agents; in the mirror, symmetry lets the computation work with role masses and an integral. The role graph and connected-component structure remain part of the problem, as does computing Myerson payoffs. This is a plausible continuous form of the authors’ question in an exchangeable-role regime, though it does not cover the paper’s arbitrary graph instances.
The weakest point is substantial: the paper’s motivating connectivity game assigns discrete \(0\)-\(1\) worths, and its centrality analysis can depend on a single articulation agent. My mirror instead uses population-scaled, smooth coalition worths and role cohorts large enough that no individual is a unique bridge. It therefore does not preserve the distinctive centrality of a lone broker. Lemma 2 supports the connection through the computation’s enumeration bottleneck, but it does not itself establish a complexity classification for this continuous problem. Further questions include how fast finite-population values converge, whether sparse non-block networks admit a comparable limit, and whether singular brokers can be represented without losing the high-multiplicity interpretation.
Lemma 2 is a genuine computational result: it gives an exact edge-inspection count for the DFS enumerator on an \(n\)-clique. Its reach is narrow, though. It does not classify the complexity of computing either value, and its parameter is the number of individually named vertices, not the support size of a population distribution. The count reflects enumerating exponentially many connected coalitions. A continuum mirror would need a new finite input and a new computation; the lemma itself gives little guidance about either.
The proposed role-block model makes that computation simple by changing the graph structure. With complete communication within roles and between adjacent roles, the graph is dense. At any positive fraction \(u\) of a random ordering, every supported role is occupied, so connectivity is determined by the fixed role graph \(H\); individual cut vertices disappear. For smooth extensive worths, the proposed output is a path integral of derivatives. That is a coherent limit-value problem, but it no longer mirrors the paper’s connected-subgraph enumeration bottleneck.
The formula also misses the paper’s basic connectivity game unless it is amended. Take connected \(H\) and \(g(x)=1\), with worth \(N\) for each nonempty connected coalition. The finite Myerson value is \(1\) per agent: the first agent in the ordering receives \(N\), with probability \(1/N\). Yet the proposed integral is zero because \(F_H(u\mu)\) is constant for every \(u>0\). A boundary contribution can repair this example, but that contribution records the first entrant, an event the smooth mass description erased. The unscaled \(0\)-\(1\) game instead gives vanishing value per agent, unless the output is changed to aggregate value by type.
A sparse-network limit could preserve more of the paper’s topology. In that setting, however, type masses alone do not determine who is connected to whom or which coalitions split apart. Encoding exact neighborhoods makes types proliferate with the population; using random links or a graph limit introduces a new model whose Myerson computation is not settled by Lemma 2. This is the strongest case against the anchor: the clean finite-type limit discards the paper’s topology, while preserving that topology demands substantially different input and algorithms.
I cannot honestly defend the universal claim that no worthwhile mirror exists. A reader could reasonably value the role-block limit problem, especially since the authors study Myerson values and the programme permits sensible co-modifications. The negative case is strongest as a claim that Lemma 2 does not establish that mirror’s relevance, and that preserving this paper’s distinctive computational challenge appears to require leaving the finite-type continuum 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.