| paper | d4-conf-atal-2016-0262 |
| 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 for every fixed \(k\ge2\); all limits exist, with running time \(O(\tau L^3+\tau^2L)=O(mL^3+m^2L)\) for \(m=\tau\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Fix \(k\), and take a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), and a symmetric matrix \(A\in\{0,1\}^{|T|\times |T|}\). Let \(D\) be a common denominator of the masses and form \(G_r\) with \(rD\mu_t\) vertices of type \(t\); distinct vertices of types \(t,u\) are adjacent exactly when \(A_{tu}=1\). For each vertex \(i\), set \(I_i(S)=|S\cap M^+(i)|\), where \(M^+(i)\) is its closed neighborhood, and use the paper’s value \(\nu(S,P)=|\{i:S\in\arg\max_{Q\in P} I_i(Q)\}|\) on partitions with at most \(k\) coalitions. Determine whether the \(k\)-coalitional Shapley payoff \(\Phi_t(r)\) of a vertex of each type \(t\) has a limit as \(r\to\infty\); when it does, compute each limit to accuracy \(\varepsilon\) and provide a certified \(R\) such that \(|\Phi_t(r)-\lim_{s\to\infty}\Phi_t(s)|\le\varepsilon\) for every \(r\ge R\).
A continuous society with type masses \(\mu_t\), where types encode complete roles in a dense block network through \(A\). The decision structure remains the paper’s partitions into at most \(k\) coalitions, the value remains the strongest-attacker count \(\nu\), and the output is each type’s limiting per-site \(k\)-coalitional Shapley payoff.
Convergence across pivotal influence ties is a substantial new result, and the complete block topology does not cover the paper’s Diplomacy geography; the proponent acknowledges the topology change and makes limit existence part of the question, but Theorem 4 settles neither issue.
fatal: False
The mirror covers Theorem 4 for the Network Control Game in replicated dense block networks. It leaves the paper’s axiomatizations, the Embedded MC-Nets complexity results, and its Diplomacy analysis outside the proposed limit question.
The strongest mirror I believe is narrow: the paper’s Theorem 4, proved in this paper, states that for the Network Control Game, the \(k\)-coalitional Shapley value can be computed in polynomial time when \(k\) is constant. The game’s value for a coalition is the number of network nodes for which it is among the strongest attackers. This is a good anchor because the population consists of the network nodes themselves, and the result computes the paper’s allocation rule for that population.
A plausible high-multiplicity setting is a large network of service areas or sites divided into a modest number of exposure roles. Sites in the same role have identical connections to every site in each role. There may be millions of sites but only \(\tau\) roles, with role \(t\) holding fraction \(\mu_t\) of the population. These are complete types for this model: the game uses only their role and network connections, and sites of one role are interchangeable.
Here is a concrete continuous problem. Fix \(k\), and let an instance consist of a finite type set \(T\), rational masses \(\mu_t>0\) summing to one, and a symmetric matrix \(A\in\{0,1\}^{\tau\times\tau}\). For each positive integer \(r\), form a finite network with \(rD\mu_t\) sites of type \(t\), where \(D\) is a common denominator of the masses. Put an edge between every pair of distinct sites of types \(t,u\) exactly when \(A_{tu}=1\). A coalition’s influence on site \(i\) is the number of its members adjacent to \(i\), plus one if it contains \(i\). The value of coalition \(S\) in a partition \(P\) into at most \(k\) coalitions is the number of sites for which \(S\) is among the coalitions with greatest influence.
Call the problem Replica-Limit Network Control Shapley: given \((T,\mu,A,k)\) and a rational accuracy \(\varepsilon>0\), compute the limiting \(k\)-coalitional Shapley payoff per site of each type, with a certified threshold \(R\) such that all replicas \(r\ge R\) are within \(\varepsilon\) of the reported limits. Symmetry makes each site of a given type receive the same payoff in every finite replica. Establishing that these limits exist for all such inputs—or characterizing the inputs where they fail to exist—is part of the question. The input describes the continuous society by type masses; the partitions into at most \(k\) coalitions are still the structures over which the Shapley value averages. This continuizes the population, not the coalition or outcome space.
I expect the fixed-\(k\), fixed-\(\tau\) version to be tractable. Theorem 4 supplies a polynomial algorithm in the explicit network size, while this mirror asks whether symmetry compresses that computation to the type counts and their rational masses. Whether the problem remains polynomial when \(\tau\) grows is a separate question; tie patterns between coalition influences could put complexity there. Useful follow-ups are the convergence rate, dependence on \(\tau\) and input bit length, and whether a certified continuous answer gives useful preprocessing for large finite networks.
The mirror is plausible because it keeps the same Network Control Game, strongest-attacker rule, and \(k\)-coalitional Shapley value. The paper’s authors could reasonably recognize it as their problem in a repeated, exchangeable network regime. Its scope is the Network Control result, not the paper’s other representation-specific results.
The weak point is the regime: complete role-to-role connectivity is a strong structural assumption, and the paper’s motivating Diplomacy board is a small, fixed graph with named provinces. A referee may regard the mirror as a model of large homogeneous networks, not as a continuation of the Diplomacy analysis itself. Still, the proposed sites are indistinguishable in every respect used by this game, and the continuous question retains the paper’s central computational object.
The one anchor they raise is real: Theorem 4 is a named polynomial-time result for computing the \(k\)-coalitional Shapley value. I would not base the negative case on missing computational content.
The strongest objection is that this value is driven by network neighborhoods, not just by a distribution over site roles. In the paper’s formula (8), a node’s payoff is a sum over its closed neighborhood, with each term determined by that neighbor’s closed-neighborhood size and \(k\). In a general sparse network, type masses do not say which sites are connected. Encoding each site’s full network role may make the number of types grow with the network, eliminating high multiplicity.
Replicating a fixed local network motif is the most natural way to restore many identical agents, but it makes the continuous limit degenerate here: the theorem’s formula depends only on local neighborhood data, which replication leaves unchanged. Each role’s payoff is therefore exactly the same at every replica size; the type masses add no new computational question.
The proposed block model avoids that degeneration, but only by making sites of a role uniformly adjacent to every site in selected roles. That creates a dense, highly symmetric interaction network, unlike the local geography motivating the paper. Its limit also needs to resolve pivotal ties in raw integer influence counts as populations grow. This is a coherent asymptotic problem, but it is an extension focused on dense block networks, not a faithful mirror of the paper’s topology-sensitive application.
That is the strongest case against the anchor, but it does not defeat the best version of the proponent’s mirror. A dense block network can be a sensible high-multiplicity regime, and its limiting Shapley computation preserves the paper’s game and allocation rule. I cannot honestly rule out that scenario; the negative case is weak at exactly that point.
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.