Answer: \(\mathrm{P}\)
Theorem 1.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of deciding whether an allocation is equal to the nucleolus of an unweighted bipartite 3-matching game is NP-hard, even in graphs of maximum degree 7.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a bipartite type-compatibility graph \(H\), rational type masses \(\mu\), and a rational per-type allocation \(q\), form for each admissible integer \(d\) the finite simple \(3\)-matching game with \(d\mu_t\) agents of each type and an edge between every pair whose types are adjacent in \(H\). Let \(q^{(d)}\) be the per-type payoff vector in that game’s nucleolus. Decide whether \(\lim_{d\to\infty} q^{(d)}=q\), with \(d\) ranging over integers for which every \(d\mu_t\) is integral.
Input a finite simple bipartite compatibility graph \(H=(T,E)\). A society is given by its support: the list of its \(\tau=|T|\) types with positive masses \(\mu_t\), each a binary rational; \(\tau\) is the support size, not the number of possible types. Require \(\sum_{t\in T}\mu_t=1\). Also input a binary-rational candidate payoff vector \(q\in\mathbb{Q}^{T}\).
For every positive integer \(d\) with \(d\mu_t\in\mathbb{Z}\) for every type, create \(d\mu_t\) distinct agents of type \(t\). Join two agents exactly when their types are adjacent in \(H\); every edge has weight \(1\). Each agent has capacity \(3\), and each edge may be used at most once.
For every coalition \(S\), its worth \(\nu_d(S)\) is the maximum cardinality of an edge set in its induced graph having degree at most \(3\) at every agent. Take the standard nucleolus over imputations. Let \(q_t^{(d)}\) be the payoff to one agent of type \(t\), well-defined by symmetry, without rescaling by \(d\) or by the type population.
The decision problem accepts exactly when \(q^{(d)}\) converges coordinatewise to \(q\) along all admissible integers \(d\); failure to converge is a negative instance. Put \(m=|E|\), and let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this replication-limit nucleolus decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite unweighted simple bipartite games with capacity \(3\) at every agent, testing whether an allocation is the nucleolus is \(\mathrm{NP}\)-hard even at maximum degree \(7\). [Source](https://arxiv.org/abs/2105.07161v3)
No result settling this exact replication-limit decision problem was identified in the literature search.
The decision problem is in \(\mathrm{P}\). In fact, the per-agent nucleolus is eventually constant, rather than merely convergent.
Let \(D\) be the least common multiple of the denominators of the masses. I prove that every admissible replication satisfying \(d\mu_t\geq 3\) for every \(t\) has the same per-agent nucleolus. Consequently, stabilization holds for every admissible \(d\geq 3D\).
The algorithm uses one maximum-flow computation on the type graph and \(O(\tau(m+\tau))\) rational linear-programming calls. Its total running time is \((m+\tau+L)^{O(1)}\) bit operations.
Throughout, use the satisfaction convention
\(\sigma(S,x)=x(S)-\nu_d(S)\). The standard nucleolus lexicographically maximizes the coalition satisfactions sorted in nondecreasing order.
Choose a bipartition \(T=A\mathbin{\dot\cup}B\). Define the type-level optimization problem
\(\displaystyle M=\max\left\{\sum_{e\in E}f_e:\ f_e\geq 0,\quad \sum_{e\ni t}f_e\leq\mu_t\ \text{for every }t\in T\right\}.\)
Its dual is
\(\displaystyle M=\min\left\{\sum_{t\in T}\mu_t p_t:\ p_t\geq 0,\quad p_t+p_s\geq 1\ \text{for every }ts\in E\right\}.\)
The primal is feasible and bounded, and the dual is feasible, so strong linear-programming duality applies.
Fix an admissible \(d\), write \(n_t=d\mu_t\), and assume \(n_t\geq 3\) for every type. Let \(N_d\) denote the agent set.
Claim. \(\nu_d(N_d)=3dM\).
For the upper bound, any feasible simple \(3\)-matching induces type-edge counts \(z_{ts}\). The values \(f_{ts}=z_{ts}/(3d)\) satisfy the type-level constraints, since the agents of type \(t\) have total capacity \(3n_t\). Hence its cardinality is at most \(3dM\).
For the lower bound, take an optimal type-level solution \(f\). Give every agent edge between types \(t,s\) the fractional value
\(\displaystyle y_{ab}=\frac{3d f_{ts}}{n_t n_s}.\)
At an agent of type \(t\), the total incident value is
\(\displaystyle \sum_b y_{ab}=\frac{3}{\mu_t}\sum_{e\ni t}f_e\leq 3.\)
Moreover, \(f_{ts}\leq\min(\mu_t,\mu_s)\), so
\(\displaystyle y_{ab}\leq\frac{3}{\max(n_t,n_s)}\leq 1.\)
Thus this is a feasible fractional simple \(3\)-matching of value \(3dM\). The agent graph is bipartite. Its matching problem is a flow problem with source and sink capacities \(3\) and agent-edge capacities \(1\); all capacities are integers, so it has an integral optimal flow. This proves the claim. These integrality facts also follow from total unimodularity of bipartite incidence matrices with edge-bound rows added; see the [standard polyhedral formulation](https://theory.stanford.edu/~jvondrak/CS369P/lec3.pdf).
For a type-payoff vector \(x\), every agent of type \(t\) receives \(x_t\). Define
\(\displaystyle C=\left\{x\in\mathbb R^T:\ x_t\geq 0,\quad x_t+x_s\geq 3\ \text{for }ts\in E,\quad \sum_t\mu_t x_t=3M\right\}.\)
Claim. Whenever every \(n_t\geq 3\), \(C\) is exactly the set of symmetric core allocations.
For necessity, nonnegativity follows from singleton rationality, and the efficiency equation follows from Section 2. For any \(ts\in E\), select three agents of each type. They induce a \(K_{3,3}\), whose worth is \(9\). Its core constraint gives
\(\displaystyle 3x_t+3x_s\geq 9.\)
For sufficiency, take \(x\in C\), any coalition \(S\), and any feasible edge set \(F\) inside it. Since each selected edge has endpoint payoffs summing to at least \(3\),
\(\displaystyle |F|\leq\frac13\sum_{ab\in F}(x_{\operatorname{type}(a)}+x_{\operatorname{type}(b)})=\frac13\sum_{a\in S}\deg_F(a)x_{\operatorname{type}(a)}\leq\sum_{a\in S}x_{\operatorname{type}(a)}.\)
Maximizing over \(F\) proves every core inequality.
The dual characterization in Section 2 shows that \(C\) is nonempty. It is compact: every \(x\in C\) satisfies \(x_t\leq 3\). Otherwise, replacing a coordinate larger than \(3\) by \(3\) preserves all edge inequalities and strictly decreases the dual objective, because \(\mu_t>0\), contradicting optimality.
The nucleolus belongs to the core: any allocation outside the core has a negative coalition satisfaction, whereas every core allocation has only nonnegative satisfactions. It is also symmetric within each type, by uniqueness and invariance under permutations of agents of that type. Therefore, it suffices to lexicographically optimize coalition satisfactions over \(C\).
Introduce the following \(\tau+m\) affine functions:
\(\displaystyle b_t(x)=x_t\quad(t\in T),\qquad g_{ts}(x)=x_t+x_s-3\quad(ts\in E).\)
All are nonnegative on \(C\). The functions \(b_t\) are singleton satisfactions. The next claim supplies coalition witnesses for the variable functions \(g_{ts}\).
Fix an optimal type-level solution \(f\). For every \(x\in C\),
\(\displaystyle 0=\sum_t\left(\mu_t-\sum_{e\ni t}f_e\right)x_t+\sum_{ts\in E}f_{ts}g_{ts}(x).\)
Indeed, expanding the right-hand side gives \(\sum_t\mu_t x_t-3\sum_e f_e=3M-3M\). Every summand is nonnegative. Consequently:
For every compatibility edge, at least one endpoint is incident to a positive-flow edge. Otherwise both endpoint payoffs would vanish throughout the nonempty set \(C\), contradicting their edge inequality.
Now suppose \(g_{ts}\) is nonconstant on \(C\). Necessarily \(f_{ts}=0\). Orient its endpoints so that \(s\) has a positive-flow neighbor \(r\). Then \(r\neq t\), and
\(\displaystyle x_r+x_s=3\quad\text{throughout }C.\)
Select one agent of type \(t\), two of type \(r\), and three of type \(s\). Because \(t,r\) lie on the same side of the bipartition, this coalition induces a \(K_{3,3}\). Its worth is \(9\), and its satisfaction on \(C\) is
\(\displaystyle x_t+2x_r+3x_s-9=g_{ts}(x)+2g_{rs}(x)=g_{ts}(x).\)
The coalition is proper: it uses only one of the at least three agents of type \(t\).
Thus every basic function nonconstant on \(C\) is exactly the satisfaction of a proper coalition.
Fix any coalition \(S\). Let \(J\) be a maximum ordinary matching in its induced agent graph, and write \(r=|J|\). Let \(U\) be the agents unmatched by \(J\).
The induced graph is finite and bipartite, so König’s theorem gives a vertex cover of size \(r\). Any feasible \(3\)-matching has at most \(3r\) edges: every selected edge meets that cover, whose vertices each have capacity \(3\). Therefore
\(\displaystyle \delta_S=3r-\nu_d(S)\in\mathbb Z_{\geq 0}.\)
Partitioning the agents into ordinary matched pairs and unmatched agents yields the exact identity
\(\displaystyle \sigma(S,x)=\sum_{a\in U}b_{\operatorname{type}(a)}(x)+\sum_{ab\in J}g_{\operatorname{type}(a)\operatorname{type}(b)}(x)+\delta_S.\)
Hence every coalition satisfaction is a nonnegative integer combination of the basic functions, plus a nonnegative constant. The integer coefficients matter: every positive coefficient is at least \(1\).
Here is the lexicographic argument in full.
For a finite family of affine functions on a compact polytope, lexicographically maximizing their sorted values can be done recursively:
Removing constant functions preserves pairwise lexicographic comparisons: the same fixed multiset of values is removed from both sorted lists. Maximizing the minimum then fixes the first remaining lexicographic objective.
Compare this procedure for all proper-coalition satisfactions with the procedure for the basic family
\(\displaystyle \mathcal B=\{b_t:t\in T\}\cup\{g_{ts}:ts\in E\}.\)
Let \(F\subseteq C\) be any common current feasible set. If a coalition satisfaction is nonconstant on \(F\), its decomposition from Section 5 contains a basic function nonconstant on \(F\) with positive integer coefficient. Since every other term is nonnegative on \(C\), that coalition satisfaction is at least that basic function, pointwise on \(F\). Consequently,
\(\displaystyle \min_{\sigma(S,\cdot)\text{ nonconstant on }F}\sigma(S,x)\ \geq\ \min_{b\in\mathcal B\text{ nonconstant on }F}b(x).\)
Conversely, every basic function nonconstant on \(F\) is nonconstant on \(C\), and Sections 3–4 provide a proper coalition whose satisfaction equals it throughout \(C\). This proves the reverse inequality.
Thus the two minimum functions agree pointwise on \(F\). Their next optimizer sets coincide. Induction proves that both recursive procedures select the same final set.
Because \(\mathcal B\) contains every coordinate function \(x_t\), its final set is a singleton. Denote it by \(x^*(H,\mu)\). We have proved
\(\displaystyle q^{(d)}=x^*(H,\mu)\qquad\text{whenever }d\mu_t\geq 3\text{ for every }t.\)
The polytope and basic functions defining \(x^*\) contain no replication parameter. Therefore the replication sequence stabilizes.
Compute \(M\) by maximum flow in the type network: source-to-\(A\) capacities \(\mu_t\), \(A\)-to-\(B\) capacities \(1\) on compatibility edges, and \(B\)-to-sink capacities \(\mu_t\). The edge capacities \(1\) impose no additional restriction on the type-level primal, since \(f_{ts}\leq\min(\mu_t,\mu_s)\leq 1\).
Then form \(C\) and \(\mathcal B\). Starting with \(F=C\), perform the recursive procedure from Section 6. Constancy of a basic function on \(F\) is tested by minimizing and maximizing it with rational linear programming. For the nonconstant functions, solve
\(\displaystyle \max\lambda\quad\text{subject to }x\in F,\quad b(x)\geq\lambda\text{ for every currently nonconstant }b\in\mathcal B.\)
Restrict \(F\) by the resulting optimal lower bounds.
Each nonterminal stage reduces the affine dimension. To see this, let \(\lambda^*\) be its optimal value. At least one currently nonconstant basic function must equal \(\lambda^*\) throughout the optimizer set. Otherwise, for each function choose an optimizer where it exceeds \(\lambda^*\); averaging these finitely many optimizers makes every function exceed \(\lambda^*\), a contradiction. Thus at most \(\tau\) stages occur.
There are \(m+\tau\) basic functions. The procedure uses \(O(\tau(m+\tau))\) LP calls, each with at most \(\tau+1\) variables and \(O(m+\tau)\) constraints. Previous thresholds require only one retained lower bound per basic function.
For completeness, the intermediate rational numbers have polynomial bit length. Multiply the efficiency equation by \(D\). Its coefficients \(D\mu_t\) and right-hand side \(3DM\) are integers; integrality of the scaled type-flow network gives \(DM\in\mathbb Z\). Also, \(D\) has \(O(L)\) bits. Every other LP coefficient belongs to \(\{0,1,-1\}\).
A nonsingular basis determinant therefore has \(O(L+\tau\log(\tau+1))\) bits: at most one independent row contains the large efficiency coefficients. If the current right-hand sides have common denominator \(\Delta\), Cramer’s rule shows that the next optimal threshold has denominator dividing \(\Delta\) times such a determinant. Over at most \(\tau\) stages, denominator bit length is
\(\displaystyle O\bigl(\tau L+\tau^2\log(\tau+1)\bigr).\)
All basic-function values on \(C\) lie between \(0\) and \(3\), so numerator sizes are polynomial as well. Exact rational LP algorithms consequently give total running time \((m+\tau+L)^{O(1)}\) bit operations.
Finally, accept exactly when the computed rational vector \(x^*(H,\mu)\) equals the input \(q\).
Since every \(D\mu_t\) is a positive integer, every admissible \(d\geq 3D\) meets the stabilization condition. Thus nonconvergence never occurs on a valid input.
The cited [finite-game hardness theorem](https://arxiv.org/abs/2105.07161v3) concerns arbitrary finite agent graphs. The replication construction supplies the six-agent coalition witnesses in Section 4, which permit the polynomial reduction proved here.
⟨structured verdict parsed — rendered above⟩
Assessment: proved. The argument establishes eventual constancy of the per-agent nucleolus and an exact polynomial-time algorithm for the stated decision problem. I found no major or minor mathematical issues requiring repair.
The proof addresses the supplied replication model, including distinct agents, capacity \(3\), unit edge weights, and the restriction that each edge is used at most once.
The allocation coordinates remain per-agent payoffs throughout. In particular, the efficiency equation \(\sum_t\mu_t x_t=3M\) results from dividing the replicated efficiency equation by \(d\); it does not rescale the individual payoff \(x_t\).
The satisfaction convention has the correct sign: lexicographically maximizing satisfactions in nondecreasing order is equivalent to the usual nucleolus definition using excesses.
The primal and dual in Section 2 are correctly paired. The primal is nonempty and bounded, and the dual is feasible. Their optimal values are therefore equal and attained.
The upper-bound calculation is valid: type-edge counts divided by \(3d\) satisfy every type-capacity constraint.
For the lower bound, the fractional assignment respects both kinds of constraints:
Summing over all agent edges gives value \(3dM\). The agent graph is finite and bipartite, and the associated flow network has integer capacities. Integral maximum flow therefore supplies a feasible simple edge set attaining this value.
The optional total-unimodularity citation also supports the assertions used: the referenced notes state integrality for integer right-hand sides, total unimodularity of bipartite incidence matrices, and preservation under adjoining identity rows. [Referenced lecture notes](https://theory.stanford.edu/~jvondrak/CS369P/lec3.pdf)
Finding: The equality \(\nu_d(N_d)=3dM\) is established, including the edge-use restriction.
The necessity argument checks all defining constraints of \(C\):
The sufficiency calculation is correct. Nonnegative payoffs and the agent-degree bound justify its final inequality. It applies to every feasible edge set in every coalition, so taking the maximum establishes all core constraints.
Nonemptiness follows by multiplying an optimal dual solution by \(3\). The coordinate truncation argument correctly proves \(x_t\leq 3\): truncating such a coordinate preserves all edge constraints because the other coordinates are nonnegative, while strictly reducing the objective because \(\mu_t>0\). Closedness and boundedness then give compactness.
The reduction to symmetric core allocations is valid. A nonempty core excludes allocations with negative coalition satisfaction from nucleolus optimality. The standard uniqueness property applies to this finite game with a nonempty imputation set. Permutations within a type preserve the game, so uniqueness forces equal payoffs within each type.
Finding: Optimizing over \(C\) correctly captures the actual nucleolus, rather than merely a restricted allocation problem.
The complementary-slackness identity is algebraically correct. Every summand is nonnegative on \(C\), so the two stated consequences follow individually.
The assertion that every compatibility edge has an endpoint incident to positive flow is justified: otherwise both endpoint payoffs would be zero throughout nonempty \(C\), violating that edge’s inequality.
For a nonconstant \(g_{ts}\), the chosen positive-flow edge \(rs\) necessarily has \(r\neq t\). Bipartiteness places \(t\) and \(r\) on the same side. Consequently, the selected agents induce exactly \(K_{3,3}\), with worth \(9\).
The displayed satisfaction calculation is correct, and \(g_{rs}=0\) throughout \(C\). Thus the coalition satisfaction equals \(g_{ts}\) throughout \(C\), not merely at one allocation.
The coalition is proper because it selects only one agent of type \(t\), whose population is at least three. Singleton witnesses are also proper under the population assumption.
Finding: Every basic function nonconstant on \(C\) has the claimed proper-coalition witness.
König’s theorem is applied with its hypotheses satisfied: the coalition’s induced graph is finite and bipartite, and \(J\) is a maximum ordinary matching.
A vertex cover of size \(r\) bounds every feasible capacity-\(3\) edge set by \(3r\). Counting an edge twice when both endpoints belong to the cover cannot invalidate this upper bound. Hence \(\delta_S\) is a nonnegative integer.
The decomposition is exact. Matched pairs contribute their endpoint payoffs minus \(3\), unmatched agents contribute their payoffs, and the added constant restores the difference between \(3r\) and coalition worth.
Grouping repeated type functions produces nonnegative integer coefficients. Their integrality supplies the coefficient-at-least-one property used next.
Finding: The decomposition and its sign restrictions are established.
Removing functions constant on the current feasible set preserves lexicographic comparisons: both compared sorted lists lose the same fixed multiset, including its multiplicities.
Both directions of the minimum comparison are justified:
Thus the two procedures have identical minimum objectives on every common current set and retain identical complete optimizer sets. The argument does not require their full sorted lists to agree.
The dimension-reduction argument in Section 7 also validates finite termination. Once all basic functions are constant, the presence of every coordinate function forces the retained nonempty set to be a singleton.
Finding: The basic-family procedure selects the nucleolus. Eventual constancy follows because its polytope and functions are independent of \(d\).
The type-level flow network represents the primal correctly. Compatibility-edge capacity \(1\) is redundant because \(f_{ts}\leq\min(\mu_t,\mu_s)\leq 1\).
The LP implementation retains the complete optimizer set by imposing all optimal lower bounds. Testing constancy through exact minimum and maximum values is valid.
The averaging argument proves strict affine-dimension reduction at every nonterminal stage. Therefore the stated bound of at most \(\tau\) stages is valid.
With \(m+\tau\) basic functions, the claimed \(O(\tau(m+\tau))\) LP-call bound follows. Retaining only the strongest lower bound for each function keeps the number of constraints \(O(m+\tau)\).
The bit-complexity argument also checks out:
Exact rational LP therefore yields the claimed total running time \((m+\tau+L)^{O(1)}\). Exact comparison with the binary-rational input vector is also polynomial-time.
Finding: The algorithm establishes polynomial bit complexity, rather than only a polynomial number of arithmetic operations.
The stabilization threshold is correct: every \(D\mu_t\) is a positive integer, so every admissible \(d\geq 3D\) has all populations at least three.
Consequently, stabilization holds along all admissible integers beyond the threshold. No analysis of the finitely many smaller replications is needed for the limit decision.
Isolated types and disconnected graphs cause no failure. The edgeless case gives \(M=0\) and \(C=\{0\}\), so the procedure terminates immediately. The mass normalization excludes empty support.
The finite-game hardness result supplies no contradiction or necessary premise for this proof. Its stated scope concerns finite bipartite games; the present argument separately establishes the additional coalition structure available in sufficiently large replications. [Cited finite-game result](https://arxiv.org/abs/2105.07161v3)
No mathematical repair or additional clarification is needed. The prover’s claimed classification and stronger stabilization statement are supported by the write-up.
⟨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.