Answer: Polynomial-time solvable for \(m=\tau=2\); a stable arrangement always exists and can be computed using at most one pool. All possible limiting local masses and type-average errors are characterized above.
Theorem 0.9 — class: algorithmic
Given rational masses \(\mu_s,\mu_\ell\) summing to one, sample counts \(n_s<n_\ell\), parameters \(\mu_e,\sigma^2\), and a population scale \(H\), compute a stable measurable partition of the two type masses into federation pools and local learners. For a type \(t\) in a pool whose other-client mass fractions are \(q_s,q_\ell\), use \(A(q)=n_s q_s+n_\ell q_\ell\), \(B(q)=n_s^2q_s+n_\ell^2q_\ell\), and expected error \(E_{t,H}(q)=\frac{\mu_e}{n_t+HA(q)}+\sigma^2\frac{HB(q)+H^2A(q)^2}{(n_t+HA(q))^2}\); stability rules out any positive-mass move that strictly improves the movers’ error and leaves destination incumbents weakly better off. Determine the high-multiplicity behavior as \(H\to\infty\).
A society is an atomless probability space given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Here \(m=\tau=2\), with types \(s,\ell\), masses \(\mu_s,\mu_\ell>0\), and \(\mu_s+\mu_\ell=1\).
Inputs are positive integers \(n_s<n_\ell\) and positive binary rationals \(\mu_e,\sigma^2,H\), with \(n_\ell>\mu_e/\sigma^2\). Let \(L\) be their total binary encoding length; state running times in \(m,\tau,L\) and any additional parameters.
An arrangement consists of finitely many disjoint measurable federation pools of positive mass and a residual set of local learners. It is represented by pool mass vectors \(x^j=(x_s^j,x_\ell^j)\) and local masses \(z_t\), satisfying \(z_t+\sum_jx_t^j=\mu_t\); exact coordinates may be real algebraic numbers.
For \(q=(q_s,q_\ell)\), set \(A(q)=n_sq_s+n_\ell q_\ell\), \(B(q)=n_s^2q_s+n_\ell^2q_\ell\), and \(E_{t,H}(q)=\frac{\mu_e}{n_t+HA(q)}+\sigma^2\frac{HB(q)+H^2A(q)^2}{(n_t+HA(q))^2}\). A type \(t\) member of pool \(j\) has error \(E_{t,H}(x^j)\): removing a single atomless member changes no mass. A local learner has error \(\mu_e/n_t\).
A deviation takes any positive-mass measurable set of movers, possibly from several sources, into one existing pool, into a newly formed pool, or into local learning. Recompute errors using the resulting pool masses. It is admissible when almost every mover strictly reduces error and almost every destination incumbent weakly reduces error; new pools and local learning have no destination incumbents. Source incumbents have no veto. An arrangement is stable if no admissible deviation exists.
Is finding a stable arrangement, or deciding that none exists, solvable in polynomial time, or is it NP-hard?
With all inputs except \(H\) fixed, what are the possible limiting local masses and type-average errors along stable arrangements as \(H\to\infty\)?
For finite agents with two sample counts and \(n_\ell>\mu_e/\sigma^2\), an individually stable arrangement exists and can be computed efficiently; this stability concerns single-agent deviations, and the constructed arrangement need not be core stable ([Donahue–Kleinberg](https://arxiv.org/html/2010.00753v3)).
No result settling the specified atomless problem with positive-mass deviations was identified in the literature search.
For the specified model with \(m=\tau=2\), a stable arrangement always exists and can be computed in polynomial time. The construction uses at most one federation pool, with coordinates of algebraic degree at most \(2\).
The limiting local masses and type-average errors can also be characterized completely.
Write
\(a=n_s\), \(b=n_\ell\), and \(r=\mu_e/\sigma^2\).
The hypotheses give \(0<a<b\) and \(r<b\).
For a pool of mass vector \(q\), introduce
\(x=Ha q_s\), \(y=Hb q_\ell\), \(W=x+y=HA(q)\), and \(V=ax+by=HB(q)\).
The society’s available quantities are
\(S=Ha\mu_s\) and \(T=Hb\mu_\ell\).
Divide all errors by the positive constant \(\sigma^2\). This preserves every strict or weak comparison. For sample count \(n\), normalized pool error is
\(\displaystyle f_n(x,y)=\frac{r(n+W)+V+W^2}{(n+W)^2},\)
and normalized local error is \(r/n\).
An identity useful below is
\(\displaystyle f_n(x,y)-\frac rn =\frac{n(V-rW)+(n-r)W^2}{n(n+W)^2}.\)
Here
\(V-rW=(a-r)x+(b-r)y\ge0\).
If \(a>r\), every member of every positive-mass pool has error strictly greater than its local error: in the preceding identity, \(n-r>0\) and \(W>0\). Any positive-mass group of such members can therefore deviate to local learning. Consequently, the all-local arrangement is the unique stable arrangement. It is stable because no mover can improve by entering any pool.
If \(a=r\), every pooled large-type learner still strictly prefers local learning, because \(b-r>0\). Thus a stable arrangement contains no pooled large-type mass. In a pure small-type pool, however, \(V=aW\), so \(f_s=1=r/a\).
It follows that, when \(a=r\), the stable arrangements are exactly those with all large-type learners local and an arbitrary division of small-type mass between local learning and finitely many pure small-type pools. Indeed, small-type learners cannot strictly improve from their common error \(1\), and large-type learners cannot improve from local learning by joining any pool.
In both cases, the algorithm may simply output the all-local arrangement.
For the rest of the construction, define the positive quantities
\(u=r-a\), \(v=b-r\), and \(d=b-a=u+v\).
The normalized errors simplify to
\(\displaystyle f_s(x,y)=1+\frac{u}{a+x+y}+\frac{dy}{(a+x+y)^2},\)
\(\displaystyle f_\ell(x,y)=1-\frac{v}{b+x+y}-\frac{dx}{(b+x+y)^2}.\)
The large type’s local error is \(r/b=1-v/b\). Direct multiplication by positive denominators gives
\[\displaystyle f_\ell(x,y)\le\frac rb \quad\Longleftrightarrow\quad v(x+y)(b+x+y)\le bd\,x. \tag{1}\]
We will put all small-type mass into one pool, choosing its large-type mass to minimize small-type error subject to large-type participation.
Consider every pool using available resources, so \(0\le x\le S\) and \(0\le y\le T\), subject to the additional condition \(f_\ell(x,y)\le r/b\) whenever \(y>0\).
Lemma. The minimum small-type error over these pools is attained by a pool with \(x=S\).
Proof. Let \(W=x+y\).
If \(W\le S\), then
\(\displaystyle f_s(x,y)\ge1+\frac{u}{a+W} \ge1+\frac{u}{a+S}=f_s(S,0).\)
If \(W>S\), replace the pool by \((S,W-S)\). This uses available resources because
\(0<W-S\le y\le T\). Its total \(W\) is unchanged. The error changes are exactly
\(\displaystyle f_s(S,W-S)=f_s(x,y)-\frac{d(S-x)}{(a+W)^2},\)
\(\displaystyle f_\ell(S,W-S)=f_\ell(x,y)-\frac{d(S-x)}{(b+W)^2}.\)
Both errors weakly decrease. In particular, large-type participation remains satisfied. Thus every admissible competitor is weakly worse for the small type than some feasible pool containing all small-type mass. This proves the lemma.
For fixed \(x=S\), large-type error strictly increases with \(y\):
\(\displaystyle \frac{\partial f_\ell(S,y)}{\partial y} =\frac{v}{(b+S+y)^2}+\frac{2dS}{(b+S+y)^3}>0.\)
Put \(M=bu/v\).
If \(S\ge M\), no positive \(y\) satisfies (1), since
\(vS(b+S)\ge bdS\) and increasing \(y\) strictly increases the left side. Set \(Y=0\).
If \(S<M\), define
\(\displaystyle R=\frac{-b+\sqrt{b^2+4bdS/v}}{2}, \qquad Y=\min\{T,R-S\}.\)
Here \(R>S\): the increasing function \(w\mapsto vw(b+w)\) takes a value below \(bdS\) at \(w=S\) and equals \(bdS\) at \(w=R\). By (1), the feasible values are exactly \(0\le y\le Y\).
Small-type error over this interval has derivative
\(\displaystyle \frac{\partial f_s(S,y)}{\partial y} =\frac{v(a+S)-(2u+v)y}{(a+S+y)^3}.\)
The numerator decreases strictly with \(y\). Hence the function increases and then decreases, and its minimum is at an endpoint.
Moreover,
\(\displaystyle f_s(S,y)-f_s(S,0) =\frac{y\bigl(v(a+S)-uy\bigr)} {(a+S)(a+S+y)^2}.\)
Define \(k=v(a+S)/u>0\), and choose
\(\displaystyle y_*= \begin{cases} Y,&Y\ge k,\\ 0,&Y<k. \end{cases}\)
Thus ties between the endpoints are resolved in favor of \(Y\).
The output is one pool and residual local masses:
\(\displaystyle q=\left(\mu_s,\frac{y_*}{Hb}\right), \qquad (z_s,z_\ell)=\left(0,\mu_\ell-\frac{y_*}{Hb}\right).\)
These coordinates are feasible because \(0\le y_*\le T\). They are measurably realizable: an atomless finite measure restricted to a measurable set of mass \(c\) admits a measurable subset of every prescribed mass in \([0,c]\). Each type set satisfies those hypotheses.
Let \(e_s=f_s(S,y_*)\). The comparison lemma and endpoint calculation establish:
Every pool using available resources and satisfying large-type participation whenever large-type mass is present has small-type error at least \(e_s\).
Also,
\(\displaystyle e_s\le f_s(S,0)=1+\frac{u}{a+S}<1+\frac ua=\frac ra.\)
We check every permitted destination.
Every small-type learner has error strictly below its local error. Every pooled large-type learner has error at most its local error by construction. Learners already local retain their error.
Thus no positive-mass deviation to local learning makes almost every mover strictly better off.
Suppose a proposed new pool contains positive small-type mass. Every small-type mover currently has error \(e_s\), so admissibility would require its new error to be strictly below \(e_s\).
If the pool also contains large-type movers, their current errors are all at most \(r/b\). Their strict improvement therefore requires the new large-type error to be strictly below \(r/b\). The new pool consequently belongs to the comparison class in Section 3.1, contradicting the minimum property of \(e_s\).
If the new pool contains only small-type mass, it also belongs to that comparison class, yielding the same contradiction.
Finally, a new pool containing only large-type mass \(y>0\) has
\(\displaystyle f_\ell(0,y)=1-\frac{v}{b+y}>1-\frac vb=\frac rb.\)
Its movers cannot improve from current errors at most \(r/b\). Hence no new-pool deviation is admissible.
All learners outside the constructed pool are local large-type learners. Any nontrivial incoming deviation therefore adds a positive quantity \(\delta\) of large-type mass.
If \(y_*>0\), the large-type residents’ error strictly increases, because \(f_\ell(S,y)\) strictly increases with \(y\). Their incumbent consent fails.
If \(y_*=0\), the construction chose the pure small-type pool because \(Y<k\). For incoming large-type movers to improve from local learning, their final mass \(\delta\) must satisfy large-type participation, and hence \(0<\delta\le Y<k\). The endpoint-difference identity then gives
\(\displaystyle f_s(S,\delta)>f_s(S,0).\)
The small-type incumbents therefore reject the deviation. If no such feasible positive \(\delta\) exists, the movers themselves cannot improve.
These arguments cover all destinations. The constructed arrangement is stable.
For \(m=\tau=2\), the construction takes \(O(L^2)\) bit operations using elementary integer arithmetic, with \(L\) understood as the full binary input length. If the stated \(L\) excludes the support masses, the bound is \(O((L+L_\mu)^2)\), where \(L_\mu\) is their combined encoding length.
To verify this bound, all intermediate rational quantities have \(O(L)\) bits, and only a constant number of arithmetic operations and comparisons are needed. Square roots need not be approximated.
In the branch \(S<M\), the decision \(Y\ge k\) is equivalent to the two rational comparisons
\(\displaystyle T\ge k, \qquad v(S+k)(b+S+k)\le bdS.\)
Similarly, \(Y=T\) is equivalent to
\(\displaystyle v(S+T)(b+S+T)\le bdS.\)
If a mixed pool is chosen and this last comparison holds, its coordinates are rational. Otherwise its large-type mass \(q_\ell\) is the unique root in \((0,\mu_\ell)\) of
\(\displaystyle P(X)=v(S+HbX)(b+S+HbX)-bdS.\)
After clearing denominators, this is an integer polynomial with \(O(L)\)-bit coefficients. Its constant coefficient is negative and its leading coefficient positive, so its two roots have opposite signs. The active branch gives \(P(\mu_\ell)>0\); consequently \((0,\mu_\ell)\) isolates its positive root.
The local mass \(\mu_\ell-q_\ell\) is likewise represented by \(P(\mu_\ell-X)\) with isolating interval \((0,\mu_\ell)\). The other root lies above \(\mu_\ell\).
Thus standard exact algebraic representations—square-free integer polynomials with rational isolating intervals—require only \(O(L)\) output bits. The algorithm outputs at most one pool and uses algebraic degree at most \(2\).
Therefore both the search problem and the existence decision problem are polynomial-time solvable. On every input satisfying the promises, the existence answer is affirmative.
Define the type-average error by
\(\displaystyle \overline E_t= \frac{z_t\,\mu_e/n_t+\sum_j x_t^jE_{t,H}(x^j)}{\mu_t}. \)
The following classification concerns arbitrary stable arrangements, not only the construction above.
First, every stable arrangement has \(z_s=0\). Otherwise a positive-mass set of local small-type learners could form a pure small-type pool, obtaining error strictly below \(r/a\).
Second, every pool containing positive large-type mass must satisfy \(f_\ell\le r/b\), because otherwise its large-type members could deviate to local learning. Equation (1), together with \(x\le W\), yields
\(\displaystyle vW(b+W)\le bd\,x\le bdW.\)
Since \(W>0\), this implies
\(\displaystyle W\le\frac{bu}{v}=M.\)
In particular, a pure large-type pool cannot occur in a stable arrangement.
Suppose now that \(S\ge M\). Consider the pure pool containing all small-type mass; its normalized error would be
\(\displaystyle e_0=1+\frac{u}{a+S}.\)
Any existing mixed pool has \(W\le M\le S\) and \(y>0\), so its small-type error satisfies
\(\displaystyle f_s(x,y)=1+\frac{u}{a+W}+\frac{dy}{(a+W)^2}>e_0.\)
Any pure small-type pool containing less than all small-type mass also has error strictly above \(e_0\).
Consequently, unless all small-type learners already occupy one pure pool, all small-type learners can jointly move into a new pure pool and strictly improve. Source incumbents have no veto, exactly as stipulated in the question.
Hence, for every
\(\displaystyle H\ge H_*= \frac{b(r-a)}{a\mu_s(b-r)},\)
the unique stable arrangement, up to null sets, is
\(\displaystyle q=(\mu_s,0), \qquad (z_s,z_\ell)=(0,\mu_\ell).\)
Its type-average errors are exactly
\(\displaystyle \overline E_s= \sigma^2+\frac{\mu_e/a-\sigma^2}{1+H\mu_s}, \qquad \overline E_\ell=\frac{\mu_e}{b}. \)
Thus every sequence of stable arrangements has these same limits as \(H\to\infty\).
Combining this result with Section 2 gives:
| Condition | Possible limiting local masses \((z_s,z_\ell)\) | Limiting type-average errors \((\overline E_s,\overline E_\ell)\) |
|---|---|---|
| \(n_s<\mu_e/\sigma^2\) | \((0,\mu_\ell)\) | \((\sigma^2,\mu_e/n_\ell)\) |
| \(n_s=\mu_e/\sigma^2\) | \((\lambda,\mu_\ell)\), any \(\lambda\in[0,\mu_s]\) | \((\sigma^2,\mu_e/n_\ell)\) |
| \(n_s>\mu_e/\sigma^2\) | \((\mu_s,\mu_\ell)\) | \((\mu_e/n_s,\mu_e/n_\ell)\) |
Every listed limit is attained. In the equality case, fix the desired local small-type mass \(\lambda\) and place the remaining small-type mass in a pure small-type pool; this arrangement is stable for every \(H\). Such sequences need not have convergent local masses, but all their subsequential limits lie in the displayed interval. Their type-average errors are constant.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The construction resolves the search and existence questions for the promised case \(m=\tau=2\). Its stability proof covers all permitted destinations, including deviations involving movers from several sources. The classification of limits applies to arbitrary stable arrangements.
No major or minor mathematical issues were found.
The substitutions \(a=n_s\), \(b=n_\ell\), and \(r=\mu_e/\sigma^2\) preserve the stated hypotheses: \(0<a<b\) and \(r<b\). Dividing errors by the positive constant \(\sigma^2\) preserves strict improvement and weak incumbent consent.
With \(x=Ha q_s\), \(y=Hb q_\ell\), \(W=x+y\), and \(V=ax+by\), the normalized error formula is correct:
\[ f_n(x,y)=\frac{r(n+W)+V+W^2}{(n+W)^2}. \]
The difference from local error is also correct:
\[ f_n(x,y)-\frac rn =\frac{n(V-rW)+(n-r)W^2}{n(n+W)^2}. \]
All denominators are positive, including for the zero vector used as a comparison point. A positive-mass pool has \(W>0\).
For \(a>r\), both types have \(n-r>0\), and \(V-rW\ge0\). The displayed difference is therefore strictly positive in every positive-mass pool. Any pool supplies a positive-mass group that strictly benefits from becoming local. Conversely, local learners cannot improve by forming a pool. The claimed uniqueness of the all-local arrangement follows.
For \(a=r\), every pooled large-type learner has error strictly above its local error. In a pure small-type pool, the small-type error equals \(1=r/a\). Mixed pools cannot give small-type learners error below \(1\), and no pool improves large-type learners upon local learning.
Thus the stated characterization—large types all local, small types divided arbitrarily between local learning and finitely many pure pools—is correct.
The definitions \(u=r-a\), \(v=b-r\), and \(d=b-a=u+v\) give positive quantities. Both simplified errors are correct:
\[ f_s(x,y)=1+\frac{u}{a+x+y}+\frac{dy}{(a+x+y)^2}, \]
\[ f_\ell(x,y)=1-\frac{v}{b+x+y}-\frac{dx}{(b+x+y)^2}. \]
The participation condition
\[ f_\ell(x,y)\le\frac rb \quad\Longleftrightarrow\quad v(x+y)(b+x+y)\le bd\,x \]
follows by multiplication by positive denominators, without changing the inequality direction.
The two cases cover every available resource vector.
The lemma therefore establishes the claimed global minimum property over its stated comparison class. It does not assume that the replacement pool itself can be reached by an admissible deviation; only a numerical comparison is needed.
The derivative of \(f_\ell(S,y)\) is strictly positive. The threshold \(M=bu/v\) is correct, including the boundary \(S=M\), where no positive \(y\) satisfies participation.
For \(S<M\), the stated \(R\) is the positive solution of \(vR(b+R)=bdS\), and \(R>S\). Consequently, the feasible interval is exactly \(0\le y\le Y\).
The derivative and endpoint-difference calculations for the small-type error are correct:
\[ \frac{\partial f_s(S,y)}{\partial y} =\frac{v(a+S)-(2u+v)y}{(a+S+y)^3}, \]
\[ f_s(S,y)-f_s(S,0) =\frac{y\bigl(v(a+S)-uy\bigr)} {(a+S)(a+S+y)^2}. \]
The derivative numerator decreases strictly, so an interior stationary point cannot be a minimum. The endpoint rule using \(k=v(a+S)/u\) correctly handles strict preference and equality.
The output masses are nonnegative and satisfy both conservation equations. The atomless divisibility property is stated precisely enough for its use: each measurable type set carries a finite atomless restricted measure, so the prescribed pool masses are realizable.
Finally,
\[ e_s\le f_s(S,0)<r/a \]
is valid because \(S>0\).
The proof checks every destination allowed by the task.
Local learning. Small types strictly prefer their constructed pool to local learning. Pooled large types weakly prefer it. Already-local learners obtain no strict improvement by remaining local.
A new pool. If it contains small-type movers, their strict improvement requires an error below \(e_s\). Any participating large-type movers have current error at most \(r/b\), so their strict improvement forces the proposed pool into the comparison class. The global minimum property rules out the deviation. Pure small-type proposals belong to that class as well.
A pure large-type proposal has error strictly above \(r/b\), so it cannot improve any available large-type movers.
This argument accommodates movers from several sources: it uses their type and current error bounds, without assuming a common source.
The existing pool. Every learner outside the constructed pool is a local large-type learner. Any incoming mass therefore increases \(y\).
The zero-feasibility case \(Y=0\) is also covered. There is no additional pool destination to inspect.
For the promised fixed values \(m=\tau=2\), the claimed \(O(L^2)\) bit-operation bound is justified.
The construction uses a constant number of rational arithmetic operations and comparisons. Every intermediate quantity has \(O(L)\) bits. The comparisons involving \(Y\) correctly eliminate the need to approximate a square root.
In the irrational-output branch, the polynomial
\[ P(X)=v(S+HbX)(b+S+HbX)-bdS \]
has \(O(L)\)-bit integer coefficients after clearing denominators. Its constant coefficient is negative and its leading coefficient positive, so its two roots are distinct and have opposite signs. The active branch supplies \(P(\mu_\ell)>0\), making \((0,\mu_\ell)\) a valid isolating interval for its positive root.
The transformed polynomial for the local mass likewise has exactly one root in that interval. Hence the degree bound, output-size bound, and exact representation claims stand.
The algorithm answers existence affirmatively on every promised input and returns a stable arrangement with at most one pool.
For \(a<r<b\), positive local small-type mass would admit a strictly improving pure small-type pool. Thus every stable arrangement has \(z_s=0\).
Any pool containing large-type mass must satisfy participation, since otherwise those learners can become local. Combining that inequality with \(x\le W\) correctly gives
\[ W\le M=\frac{bu}{v}. \]
This also excludes pure large-type pools.
When \(S\ge M\), each mixed pool gives its small-type members error strictly above \(e_0\), while every proper pure small-type pool does the same. Unless all small types already occupy one pure pool, all small types can therefore form a new pure pool and strictly improve. The absence of source-incumbent veto is used exactly as specified.
The threshold
\[ H_*=\frac{b(r-a)}{a\mu_s(b-r)} \]
is correct, including equality. Together with the earlier stability proof, this establishes eventual uniqueness.
The stated type-average error formula follows from the pure small-type pool error, and its limit is correct. The equality and strict-inequality regimes follow from the complete classifications in Section 2. Every listed limit is attained; the discussion correctly distinguishes possible limits from sequences whose local masses do not converge.
None. The argument establishes both the polynomial-time construction and the complete limiting classification for the promised input domain.
⟨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.