Answer: Exactly polynomial-time computable in \(m,\tau,L\). All limits \(a_t\) exist as finite rational numbers; moreover, \(N\nu_N(t)\) is constant throughout the bridge-free tail.
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateis proved in Appendix 7. The proof says that the weight of a second-best response is opt + κ, and this must be optimal since all the weights are multiples of κ. For all other prime-edge-distributions there is a second-best response with weight less than opt + κ.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given fixed sites \(V\), a connected set of corridor types \(T\subseteq {V\choose 2}\), and positive rational masses \(\mu_t\) summing to \(1\), form \(G_N\) with \(N\mu_t\) parallel edges of type \(t\), for integers \(N\) making all multiplicities integral. In the spanning-connectivity game on \(G_N\), let \(\nu_N(e)\) be the nucleolus allocation to an edge of type \(t\). Do the limits \(a_t=\lim_{N\to\infty}N\nu_N(e)\) exist for every type, and can their exact values be computed in time polynomial in \(|V|,\tau,L\), where \(\tau=|T|\) and \(L\) is the mass encoding length?
Let \(V\) be a set of \(m\geq 3\) sites and let \(T\subseteq\binom{V}{2}\) satisfy that \((V,T)\) is connected.
A society is given by its support: the list of the \(\tau=|T|\) corridor types with positive masses \(\mu_t\), each encoded as a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total mass encoding length.
For each positive integer \(N\) with all \(N\mu_t\) integral, let \(G_N=(V,E_N)\) be the undirected, unweighted multigraph having \(N\mu_t\) distinct parallel edges of type \(t\).
The players are \(E_N\); a coalition \(S\subseteq E_N\) has value \(v_N(S)=1\) exactly when \((V,S)\) is connected, and otherwise has value zero. Allocations satisfy \(x_e\geq 0\) and \(\sum_{e\in E_N}x_e=1\).
Let \(\nu_N\) be the standard nucleolus of this game and let \(\nu_N(t)\) denote its common allocation to edges of type \(t\), which are interchangeable. Limits are along all admissible integers \(N\); equivalently, use the tail with \(N\mu_t\geq 2\) for every type, where \(G_N\) has no bridges.
Do all limits \(a_t=\lim_{N\to\infty}N\nu_N(t)\) exist as finite rational numbers, and, if so, is computing \((a_t)_{t\in T}\) exactly polynomial-time in \(m,\tau,L\), or is it NP-hard?
For explicitly represented connected graphs without bridges, the discrete nucleolus has a layer formula and is computable in time polynomial in the number of vertices and edges ([Aziz, Lachish, Paterson and Savani, 2009](https://arxiv.org/pdf/0909.5293v2)).
No result settling this precise mass-limit problem was located in the literature search.
All the limits exist, are finite rational numbers, and can be computed exactly in polynomial time in \(m,\tau,L\). In fact, \(N\nu_N(t)\) is already constant throughout the stated bridge-free tail.
The proof uses the cited discrete layer formula, but recovers its partition and order from a polytope with only \(\tau\) allocation variables. Thus no expanded multigraph needs to be constructed.
Write \(H=(V,T)\), and let \(\mathcal B\) be its family of spanning trees. For \(a\in\mathbb R_{\geq 0}^{T}\), define
\(w(a)=\min_{B\in\mathcal B}\sum_{t\in B}a_t.\)
Define the compact polytope
\(\Delta_\mu=\{a\in\mathbb R_{\geq 0}^{T}:\sum_{t\in T}\mu_ta_t=1\},\)
the number
\(c=\max_{a\in\Delta_\mu}w(a),\)
and its optimal face
\(P=\{a\in\Delta_\mu:\sum_{t\in B}a_t\geq c\text{ for every }B\in\mathcal B\}.\)
These definitions involve only the support and masses. Compactness follows from \(0\leq a_t\leq 1/\mu_t\). Moreover, \(a_t=1\) for every \(t\) is feasible and has \(w(a)=m-1\), so \(c>0\).
For a nonnegative allocation \(x\) on \(G_N\), every winning coalition contains a spanning tree. Consequently, its minimum winning-coalition allocation equals
\(M_N(x)=\min_{F\text{ spanning tree of }G_N}\sum_{e\in F}x_e.\)
Using the convention \(e_x(S)=v_N(S)-x(S)\), losing coalitions have nonpositive excess. Winning coalitions have maximum excess \(1-M_N(x)\), which is nonnegative. Hence the least core consists exactly of allocations maximizing \(M_N(x)\). Since \(m\geq 3\), every singleton has value zero, so the allocation domain in the question is precisely the usual imputation domain.
Let \(x\) maximize \(M_N\), and put
\(b_t=\min\{x_e:e\text{ has type }t\}.\)
A spanning tree contains at most one edge of any type. Conversely, each support spanning tree can be realized using a minimum-allocation copy of each of its types. Therefore
\(M_N(x)=\min_{B\in\mathcal B}\sum_{t\in B}b_t.\)
Give every copy of type \(t\) allocation \(b_t\), obtaining \(y\), and set \(s=\sum_e y_e\). Then \(y\leq x\), \(s\leq 1\), and \(M_N(y)=M_N(x)\).
The uniform allocation has minimum spanning-tree allocation \((m-1)/N>0\), so \(M_N(x)>0\) and \(s>0\). If any parallel copies have unequal allocations, then \(s<1\), and the normalized allocation \(y/s\) satisfies
\(M_N(y/s)=M_N(x)/s>M_N(x),\)
contradicting optimality. Thus every type receives a common per-edge allocation. \(\square\)
Now write that common allocation as \(x_e=a_t/N\). Normalization becomes
\(\sum_{e\in E_N}x_e=\sum_{t\in T}N\mu_t(a_t/N)=\sum_{t\in T}\mu_ta_t=1,\)
and
\(M_N(x)=w(a)/N.\)
It follows that, for every admissible \(N\), the entire least core is precisely
\(C_N=\{x:x_e=a_t/N\text{ for type }t,\ a\in P\},\)
and its maximum minimum spanning-tree allocation is \(c/N\).
The following combines Definition 7, Theorem 3, Definition 13, Theorem 5, and Proposition 6 of [Aziz, Lachish, Paterson and Savani](https://arxiv.org/pdf/0909.5293v2).
For a connected undirected unweighted multigraph with at least three vertices and no bridges, let \(C\) be its least core. Let \(D\) contain the edges assigned zero throughout \(C\). Partition the remaining edges by the equivalence relation
\(e\sim f\quad\Longleftrightarrow\quad x_e=x_f\text{ for every }x\in C.\)
These are the nondegenerate prime-partition blocks. There is a partial order on these blocks such that \(C\) consists exactly of normalized nonnegative vectors that vanish on \(D\), are constant on each block, and satisfy \(x_B\geq x_C\) whenever \(B\) precedes \(C\).
Let \(h(B)\) be the maximum number of blocks in a chain starting at \(B\), so sinks have height one. The nucleolus assigns
\(\nu(e)=\dfrac{h(B)}{\sum_C h(C)|C|}\quad(e\in B),\)
and zero on \(D\).
All hypotheses hold for the tail in the question: connectivity is inherited from \(H\), and when every type has at least two copies, removing any individual edge leaves its endpoints joined by another parallel edge. Thus \(G_N\) has no bridges.
Define
\(T_0=\{t\in T:a_t=0\text{ for every }a\in P\}.\)
On \(T\setminus T_0\), define
\(t\sim u\quad\Longleftrightarrow\quad a_t=a_u\text{ for every }a\in P.\)
Let \(\mathcal Q\) be the resulting set of classes. For \(B\in\mathcal Q\), write \(a_B\) for its common coordinate and
\(\mu(B)=\sum_{t\in B}\mu_t>0.\)
The correspondence between \(P\) and \(C_N\) shows that the degenerate edges of \(G_N\) are exactly the copies of types in \(T_0\), and its nondegenerate prime blocks are exactly the unions of copies of classes \(B\in\mathcal Q\). Their cardinalities are
\(|B_N|=N\mu(B).\)
In particular, the partition is independent of \(N\).
For distinct classes \(B,C\), define a relation using only \(P\):
\(B\succ C\quad\Longleftrightarrow\quad a_B\geq a_C\text{ for every }a\in P.\)
We next verify that this relation is exactly the reachability relation of the discrete theorem’s order.
If \(B\) precedes \(C\) along a chain, the theorem’s inequalities imply \(a_B\geq a_C\) throughout \(P\).
Conversely, suppose there is no chain from \(B\) to \(C\). Let \(U\) consist of \(C\) and all its ancestors in the discrete order. Then \(B\notin U\). Set
\(y_A=1\text{ for }A\in U,\qquad y_A=0\text{ for }A\notin U,\)
and set all coordinates in \(T_0\) to zero.
This vector satisfies every order inequality: if a child belongs to \(U\), its parent also belongs to \(U\). Normalize it by
\(a_t=\dfrac{y_{[t]}}{\sum_{A\in U}\mu(A)}\quad(t\notin T_0),\qquad a_t=0\quad(t\in T_0).\)
The denominator is positive. By the theorem’s exact characterization of the least core, this normalized vector belongs to \(P\). But it has \(a_B=0<a_C\), so \(B\succ C\) fails.
Thus \(\succ\) recovers the discrete reachability relation exactly. In particular, the order and its heights are independent of \(N\).
Define
\(h(B)=1+\max\{h(C):B\succ C\},\)
with the maximum of an empty set equal to zero. Set \(h_t=h([t])\) outside \(T_0\), and \(h_t=0\) on \(T_0\). There is at least one nondegenerate class because every point of \(P\) has weighted sum one. Hence
\(Z=\sum_{t\in T}\mu_th_t>0.\)
Applying the discrete layer formula gives, for every admissible \(N\) in the tail,
\(\nu_N(t)=\dfrac{h_t}{\sum_{B\in\mathcal Q}h(B)|B_N|} =\dfrac{h_t}{NZ}.\)
Consequently,
\(\boxed{a_t=\lim_{N\to\infty}N\nu_N(t)=\dfrac{h_t}{\sum_{u\in T}\mu_uh_u}.}\)
This proves exact constancy on the tail. Since the heights are integers and the masses are rational, every \(a_t\) is finite and rational.
It remains to compute \(P\), its universal equalities, and its universal order inequalities without expanding \(G_N\).
Compute \(c\) by the linear program
\(\max z,\)
subject to
\(a_t\geq 0,\qquad \sum_t\mu_ta_t=1,\qquad z\geq 0,\)
and
\(\sum_{t\in B}a_t\geq z\qquad(B\in\mathcal B).\)
Although there can be exponentially many tree constraints, they have a polynomial-time strong separation oracle. After checking the explicit constraints, compute a minimum spanning tree of \(H\) with edge weights \(a_t\). If its weight is below \(z\), its incidence vector supplies a violated constraint; otherwise all tree constraints hold.
The same oracle works for optimization over \(P\), replacing \(z\) by the computed value \(c\).
For completeness, the rational-polyhedron hypotheses needed for exact optimization are satisfied. Put \(\mu_{\min}=\min_t\mu_t\). Every feasible point obeys
\(0\leq a_t\leq 1/\mu_{\min},\qquad 0\leq z\leq (m-1)/\mu_{\min}.\)
These bounds have polynomial encoding length. Every constraint row has polynomial encoding length: tree coefficients are zero or one, and the remaining coefficients are the input masses. Cramer’s rule applied to a vertex-defining subsystem of at most \(\tau+1\) independent rows gives a polynomial bound on vertex encoding length, including the encoding length of \(c\). After fixing \(c\), the same bounds apply to \(P\).
Therefore the exact strong separation–optimization theorem for well-described rational polyhedra applies, including when the optimal face has lower dimension. It yields polynomial-time exact optimization for these LPs. See Grötschel, Lovász and Schrijver, [*Geometric Algorithms and Combinatorial Optimization*, the chapters on rational polyhedra](https://link.springer.com/book/10.1007/978-3-642-78240-4).
Perform the following exact optimizations over \(P\):
There are \(O(\tau^2)\) such LPs. All comparisons are exact rational comparisons. Compute the heights in the resulting acyclic order, then return \(h_t/Z\).
Finally, \(0\leq h_t\leq |\mathcal Q|\leq\tau\). If \(\mu_t=p_t/q_t\), a common denominator \(Q=\prod_tq_t\) has encoding length at most \(L\), and
\(Z=\dfrac{\sum_t h_tp_t(Q/q_t)}{Q}.\)
Thus the returned rational numbers also have polynomial encoding length.
The complete algorithm is polynomial in \(m,\tau,L\), and never constructs any \(G_N\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the assigned question: every limit exists and is a finite rational number, and the vector is exactly computable in polynomial time in \(m,\tau,L\). The stronger claim of exact constancy throughout the specified tail also follows. I found no major or minor mathematical issues.
1. The replication-independent polytope is well defined.
Connectivity of \(H\) ensures that its spanning-tree family is nonempty. Positivity of every mass makes \(\Delta_\mu\) bounded, and its defining constraints make it closed. The function \(w\) is continuous because it is the minimum of finitely many linear functions. Consequently, \(c\) is attained and \(P\) is nonempty and compact.
The test vector with every coordinate equal to one satisfies normalization and gives \(w(a)=m-1\). Thus the asserted positivity of \(c\) is correct.
2. The least-core reduction is correct.
Nonnegativity is essential here and is explicitly assumed: a winning coalition containing a spanning tree cannot have smaller allocation than that tree. Conversely, each spanning tree is itself winning. This verifies the equality defining \(M_N(x)\).
Losing coalitions have nonpositive excess under the stated convention. Since allocations sum to one, every spanning tree has allocation at most one, so \(1-M_N(x)\) is nonnegative. Therefore minimizing maximum excess is exactly maximizing \(M_N(x)\).
The identification of the allocation domain with the imputation domain is valid: with at least three vertices, a single edge cannot connect all vertices.
3. The lemma establishing equality within each type is rigorous.
Every multigraph spanning tree uses at most one copy of a corridor type. Its projection is a support spanning tree, and every support spanning tree can independently select a minimum-allocation copy of each type. Thus the displayed formula in terms of \(b_t\) is exact.
Replacing each allocation by its type minimum preserves \(M_N\) and weakly decreases total allocation. If any type has unequal copies, at least one decrease is strict, giving \(s<1\).
The uniform allocation establishes a strictly positive optimum. Hence \(s>0\), and normalization by \(s\) is legitimate. Homogeneity then gives the claimed strict improvement, contradicting optimality.
This argument establishes equality for every least-core allocation, rather than merely the existence of a symmetric optimum. Types with only one copy cause no exception.
The subsequent normalization and scaling identities are correct. They establish the full correspondence between \(C_N\) and \(P\), for every admissible \(N\).
4. The cited structural result is used correctly.
The universal-equality description of prime blocks matches Definition 7 and the discussion immediately preceding it. The order-inequality characterization is supplied by Theorem 3 and Corollary 2. Definition 13 gives the successive sink layers; Theorem 5 supplies their allocation formula, and Proposition 6 identifies that vector with the standard nucleolus. The prover’s combined statement accurately captures these results. [Full cited paper](https://arxiv.org/pdf/0909.5293).
The hypotheses are satisfied on the specified tail. The graph is connected, has at least three vertices, and has no bridges: every individual edge has another parallel copy joining its endpoints.
The excess sign convention causes no discrepancy. Reversing the sign and the corresponding lexicographic ordering preserves the standard nucleolus.
5. Recovery of the partition and order from \(P\) is valid.
The established correspondence transfers universal zeros and universal coordinate equalities exactly. Consequently, the identified type classes give the discrete nondegenerate blocks, with cardinalities \(N\mu(B)\). Neither the classes nor the degenerate types depend on \(N\).
The forward implication for order recovery follows by chaining the discrete inequalities.
For the converse, the chosen ancestor set \(U\) is nonempty and excludes \(B\) when there is no directed chain from \(B\) to \(C\). Its indicator satisfies every order inequality: membership of a child forces membership of its parent. The normalization denominator is strictly positive.
The discrete characterization therefore places the normalized vector in \(P\), where its coordinates strictly violate the proposed universal inequality. This proves the converse without assuming the relation being recovered.
Thus \(\succ\) is precisely strict reachability in the discrete acyclic order. Taking longest-chain heights over reachability gives the same heights as successive sink removal. The height recursion is therefore correct.
6. The limit formula follows exactly.
There is at least one nondegenerate class, because weighted normalization excludes the zero vector. Every such class has positive mass and positive height, giving \(Z>0\).
Substitution of the block cardinalities into the cited allocation formula yields exactly
\[
\nu_N(t)=\frac{h_t}{NZ}.
\]
Here and below, the displayed identity is the prover’s established scaling calculation.
Accordingly, \(N\nu_N(t)\) is constant on the specified tail. This proves convergence along all admissible integers: positivity of the masses ensures that every sufficiently large admissible integer belongs to that tail.
The resulting values \(h_t/Z\) are finite rational numbers. Degenerate types receive zero, as required.
7. The exact polynomial-time algorithm is justified.
The proposed oracle is a strong separation oracle. After the explicit constraints pass, a minimum spanning tree detects a violated tree inequality whenever one exists. Its incidence vector supplies the separating inequality with polynomial encoding length.
The optimization polytope is nonempty and bounded. The stated coordinate bounds are valid and have polynomial encoding length. Constraint encoding lengths are polynomial independently of the number of spanning trees.
The Cramer’s-rule argument correctly bounds vertex encoding lengths and hence the encoding length of \(c\). Fixing that rational value preserves polynomial constraint encoding length.
The invoked strong separation–optimization theorem applies to well-described rational polyhedra, including lower-dimensional ones. Thus the equality constraint and the possibly lower-dimensional optimal face do not invalidate exact optimization. This is the relevant scope of [Grötschel–Lovász–Schrijver, Theorem 6.4.9](https://www.zib.de/userpage/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf).
Each proposed optimization correctly tests its associated universal property:
The number of optimizations is \(O(\tau^2)\). Their objectives have polynomial encoding length, and exact rational comparisons suffice.
Finally, the height bound and common-denominator calculation correctly establish polynomial output encoding length. The algorithm’s complexity depends on the support representation and mass encoding, without constructing an expanded multigraph.
Required feedback: None. No missing lemma, failed hypothesis, or unsupported computational step prevents verification.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.