Answer: —
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCR- and SCR-EXISTENCE FOR C are NP-hard if for all N and every collection of strict and mutual orderings (⩾i)i∈N in which each agent has at most 4 friends, there is a game ⟨N,(≽i)i∈N⟩∈C that is consistent on pairs, triangle- appreciating, monotone on triangles, {0-1}-toxic, weakly {1-1,2-2,3-3}-toxic, and intolerant in triangles with respect to (⩾i)i∈N.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\Theta\), rational masses \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\) summing to \(1\), and complete median-game profiles \(v_{\theta}(\eta)\), does there exist a finite-support measurable partition into coalition mass vectors \(z^1,\ldots,z^R\) and singleton mass \(s\), with \(\sum_r z^r+s=\mu\), such that no positive-mass coalition \(b\) strictly improves every participant (CR), or weakly improves all participants and strictly improves a positive mass (SCR)?
A society is atomless and given by its support: the list of \(\tau\geq1\) types \(\Theta\) with positive masses \(\mu_\theta\) encoded as binary rationals, where \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types. Each complete profile lists \(v_\theta(\eta)\in\mathbb Q\) for every \(\eta\in\Theta\); values may have either sign and ties are allowed. Let \(m=\tau\) be the profile dimension and \(L\) the total input bit length.
For a nonzero coalition vector \(z\in\mathbb R_{\geq0}^{\tau}\), put \(M(z)=\sum_\eta z_\eta\). Its weighted median interval for type \(\theta\) is \(I_\theta(z)=\{t\in\mathbb R:\sum_{\eta:v_\theta(\eta)<t}z_\eta\leq M(z)/2,\ \sum_{\eta:v_\theta(\eta)>t}z_\eta\leq M(z)/2\}\); its payoff is \(U_\theta(z)=(\min I_\theta(z)+\max I_\theta(z))/2\). Higher payoffs are preferred; singleton payoff is \(v_\theta(\theta)\).
An outcome consists of finitely many positive-mass measurable coalitions with vectors \(z^1,\ldots,z^R\), and residual mass \(s\) partitioned into individual singletons, satisfying \(\sum_{r=1}^Rz^r+s=\mu\). Types may split across coalitions; all outcome masses may be real, and \(R\geq0\) has no prescribed bound.
A deviation selects vectors \(0\leq d^r\leq z^r\) and \(0\leq d^0\leq s\), forming one coalition \(b=\sum_{r=0}^Rd^r\) with \(M(b)>0\). Write \(u_\theta^r=U_\theta(z^r)\) for \(r\geq1\) and \(u_\theta^0=v_\theta(\theta)\). It CR-blocks if \(U_\theta(b)>u_\theta^r\) whenever \(d_\theta^r>0\); it SCR-blocks if these inequalities are weak and the total selected mass experiencing a strict inequality is positive. An outcome is stable when it has no corresponding blocking deviation.
For each \(\alpha\in\{\mathrm{CR},\mathrm{SCR}\}\), is deciding whether an \(\alpha\)-stable outcome exists in \(\mathrm P\) or NP-hard, with running times measured in \(m,\tau,L\)?
Discrete median-game core and strict-core existence are NP-hard, even with nonnegative utilities ([Peters–Elkind, 2015](https://arxiv.org/html/1507.03474)). No result settling this exact atomless, finite-support decision problem was located.
The $\mathrm{CR}$ existence problem is in $\mathrm P$: every valid instance admits a $\mathrm{CR}$-stable outcome.
The general $\mathrm{SCR}$ classification remains unresolved here. The new results are:
$$
2^{O(\tau\log(\tau+1))}\operatorname{poly}(L),
$$
improving the bound in the notes.
$$ \sum_{\theta\in T}\mu_\theta>\frac12. $$
All arguments below apply to signed rational values and allow ties.
For a given outcome, define
$$
p_\theta
=
\min\{u_\theta^r:z_\theta^r>0,\ r\geq1\},
$$
including $u_\theta^0=v_\theta(\theta)$ when $s_\theta>0$. This is a minimum over a nonempty finite set, because $\mu_\theta>0$.
For a vector $w\geq0$, write
$$
\operatorname{supp}(w)=\{\theta:w_\theta>0\}.
$$
Multiplication by a positive scalar preserves every median interval. Hence
$$
U_\theta(\lambda w)=U_\theta(w)
\qquad(\lambda>0).
$$
Lemma 1. An outcome is $\mathrm{CR}$-blocked if and only if there exists a nonzero $w\geq0$ satisfying
$$
U_\theta(w)>p_\theta
\qquad
\text{for every }\theta\in\operatorname{supp}(w).
$$
It is $\mathrm{SCR}$-blocked if and only if there exists a nonzero $w\geq0$ satisfying
$$
U_\theta(w)\geq p_\theta
\qquad
\text{for every }\theta\in\operatorname{supp}(w),
$$
with strict inequality for at least one participating type.
Proof. For an actual deviation $b$, every selected origin of type $\theta$ has payoff at least $p_\theta$. Consequently, the deviation satisfies the displayed comparisons. Under $\mathrm{SCR}$, positive strictly improving selected mass implies a strict comparison for at least one participating type.
Conversely, suppose $w$ satisfies the relevant comparisons. For every $\theta$ in its support, choose an origin attaining $p_\theta$, and denote the available mass there by $a_\theta>0$. Since the support is finite, there exists $\lambda>0$ such that
$$
\lambda w_\theta\leq a_\theta
\qquad
\text{for every }\theta\in\operatorname{supp}(w).
$$
Select these masses from the chosen origins. Atomlessness permits selections of these prescribed sizes. Their aggregate vector is $\lambda w$, with the same payoffs as $w$. In the $\mathrm{SCR}$ case, a strictly improving type contributes strictly improving mass $\lambda w_\theta>0$. Thus this is a blocking deviation. $\square$
Two consequences will be used:
$$
p_\theta\geq v_\theta(\theta).
$$
Otherwise, a small pure-type coalition drawn from a minimum-payoff origin strictly improves all its participants.
For each type $\theta$, list the distinct values in its profile:
$$
a_{\theta,1}<\cdots<a_{\theta,k_\theta},
\qquad k_\theta\leq\tau.
$$
Define
$$
H_{\theta,j}(z)
=
\sum_{\eta:v_\theta(\eta)\leq a_{\theta,j}}z_\eta,
\qquad H_{\theta,0}(z)=0.
$$
For a nonzero $z$, the lower median endpoint is $a_{\theta,p}$ exactly when
$$
H_{\theta,p-1}(z)<\frac{M(z)}2\leq H_{\theta,p}(z).
$$
The upper endpoint is $a_{\theta,q}$ exactly when
$$
H_{\theta,q-1}(z)\leq\frac{M(z)}2<H_{\theta,q}(z).
$$
Indeed, the lower endpoint is the first profile value at which cumulative mass reaches half, while the upper endpoint is the first at which cumulative mass exceeds half. These descriptions also cover an interval between two supported values separated by an exactly balanced split.
It follows that every payoff belongs to
$$
D_\theta
=
\left\{
\frac{a_{\theta,p}+a_{\theta,q}}2:
1\leq p\leq q\leq k_\theta
\right\},
$$
where
$$
|D_\theta|\leq D:=\frac{\tau(\tau+1)}2.
$$
A signature specifies a nonempty support $S$ and both median endpoints for every type. There are at most
$$
K:=2^\tau D^\tau
=
2^{O(\tau\log(\tau+1))}
$$
candidate signatures.
Each signature defines a set $\mathcal C_j$ through homogeneous rational linear conditions:
Every nonempty $\mathcal C_j$ is closed under addition and positive scaling, and has a constant payoff vector $u^j$ and support $S_j$.
Nonemptiness is decidable by linear programming. Impose $M(z)=1$, replace every strict inequality $f(z)>0$ by
$$
f(z)\geq\delta,
$$
impose $0\leq\delta\leq1$, and maximize $\delta$. The signature is nonempty exactly when the optimum is positive: any feasible normalized vector has a positive minimum slack over its finitely many strict inequalities, and a positive optimum satisfies all of them.
Choose one normalized representative from each nonempty signature. Every possible coalition has the same support and payoffs as one of these representatives. By Lemma 1, this menu detects every blocking deviation.
We use the following form of Scarf’s lemma.
For a finite nonnegative matrix $A$ with no zero column, positive capacities $b$, and a strict ordering of the positive-entry columns in each row, there exists an extreme point of
$$
\{x\geq0:Ax\leq b\}
$$
that dominates every column. Domination of column $j$ in row $i$ means that $A_{ij}>0$, the row is saturated, and every positively used column incident with row $i$ is ranked at least as highly as $j$. This is [Lemma 1 of Biró–Csáji–Schlotter](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/LIPIcs.ICALP.2025.31/LIPIcs.ICALP.2025.31.pdf).
Apply the lemma with the normalized representatives as columns of $A$, and $b=\mu$. Include the pure-type columns $e_\theta$. In row $\theta$, order incident columns by $U_\theta$, breaking payoff ties arbitrarily.
All hypotheses hold: the matrix is finite and nonnegative, every column has total mass one, capacities are positive, and the row orderings are strict. Its feasible polytope is bounded, since
$$
\sum_jx_j
=
\sum_\theta(Ax)_\theta
\leq
\sum_\theta\mu_\theta
=
1.
$$
Let $x$ be supplied by the lemma. The pure-type column $e_\theta$ can be dominated only in row $\theta$. Thus every row is saturated:
$$
Ax=\mu.
$$
For each $x_j>0$, form a coalition with vector $x_j a^j$, where $a^j$ is its normalized representative. This finite outcome covers the society.
Consider any menu column $j$. Choose a row $\theta$ dominating it. Every used coalition containing type $\theta$ is ranked at least as highly as $j$, so
$$
p_\theta\geq U_\theta(a^j).
$$
Here $\theta\in\operatorname{supp}(a^j)$. Consequently, this composition cannot strictly improve all its participating types.
Lemma 1 and the finite-menu representation exclude every $\mathrm{CR}$-block.
Conclusion. Every valid instance has a $\mathrm{CR}$-stable outcome. Therefore the existence decision problem is in $\mathrm P$. This proof does not assert polynomial-time construction of an outcome.
Lemma 2. In an $\mathrm{SCR}$-stable outcome, every positive-mass portion of a type receives the same payoff.
Proof. Consider an existing coalition $z^r$. By definition,
$$
U_\theta(z^r)\geq p_\theta
\qquad
(\theta\in\operatorname{supp}(z^r)).
$$
If any inequality were strict, Lemma 1 would make this composition an $\mathrm{SCR}$-block after selecting a sufficiently small copy from minimum-payoff origins.
If a residual singleton portion received strictly more than its type’s minimum, a pure-type composition would block by the same argument. Hence every portion receives $p_\theta$. $\square$
Write the resulting uniform payoff vector as $q$. Such an outcome is stable exactly when there is no composition $w\neq0$ for which
$$
U_\theta(w)\geq q_\theta
\qquad
(\theta\in\operatorname{supp}(w)),
$$
with at least one strict inequality.
Every coordinate $q_\theta$ belongs to $D_\theta$.
The midpoint convention has a useful aggregation property.
Lemma 3. Fix any profile $v$. For nonzero vectors $x,y\geq0$,
$$
\min\{U_v(x),U_v(y)\}
\leq
U_v(x+y)
\leq
\max\{U_v(x),U_v(y)\}.
$$
Proof. First prove that, for every real $c$, the condition $U_v(z)\geq c$ is preserved under addition.
Partition the profile entries into
$$
A=\{\eta:v(\eta)<c\},
\qquad
B=\{\eta:v(\eta)\geq c\}.
$$
If $z(A)<M(z)/2$, both median endpoints are at least $c$, and therefore $U_v(z)\geq c$. If $z(A)>M(z)/2$, both endpoints are below $c$, and therefore $U_v(z)<c$.
When $z(A)=M(z)/2$, both parts have positive mass. Define
$$
\ell(z)=\max\{v(\eta):\eta\in A,\ z_\eta>0\},
$$
$$
h(z)=\min\{v(\eta):\eta\in B,\ z_\eta>0\}.
$$
The median interval is $[\ell(z),h(z)]$, so
$$
U_v(z)\geq c
\quad\Longleftrightarrow\quad
\ell(z)+h(z)\geq2c.
$$
Now suppose $U_v(x)\geq c$ and $U_v(y)\geq c$. Both have mass on $A$ at most half their total mass. If either inequality is strict, their sum also has less than half its mass on $A$, and hence satisfies the desired payoff bound.
Otherwise, both are exactly balanced. Then
$$
\ell(x+y)=\max\{\ell(x),\ell(y)\},
\qquad
h(x+y)=\min\{h(x),h(y)\}.
$$
Choose $t\in\{x,y\}$ attaining the latter minimum. We obtain
$$
\ell(x+y)+h(x+y)
\geq
\ell(t)+h(t)
\geq2c.
$$
Thus $U_v(x+y)\geq c$.
Negating the profile negates the payoff:
$$
U_{-v}(z)=-U_v(z),
$$
because its median interval is the reflection of the original interval. Applying the proved upper-level property to $-v$ shows that $U_v(z)\leq c$ is also preserved under addition.
Use these two properties with $c$ equal to the minimum and maximum of the two original payoffs. $\square$
Consequently, for a fixed support $S$ and prescribed payoffs $q_\theta$, the set
$$
\left\{
z:\operatorname{supp}(z)=S,\
U_\theta(z)=q_\theta\text{ for every }\theta\in S
\right\}
$$
is convex and closed under positive scaling.
These sets need not be topologically closed. For example, with values $0,1$, the vectors $(1,1+\varepsilon)$ have payoff $1$ for every $\varepsilon>0$, while their limit $(1,1)$ has payoff $1/2$. The next procedure therefore retains the strict inequalities.
This lemma is the source of the improved running time.
Suppose $\mathcal C_1,\ldots,\mathcal C_N$ are specified by homogeneous rational linear equalities, weak inequalities, and finitely many strict inequalities
$$
f_{j,\ell}(x)>0.
$$
Assume their vectors are nonnegative, and each description requires a nonempty support through positive-coordinate constraints.
We want to decide whether
$$
\mu=\sum_{j=1}^N x^j,
\qquad
x^j\in\mathcal C_j\cup\{0\}.
$$
The zero option means that the corresponding cone is unused.
Lemma 4. This covering question is decidable in time polynomial in the total size of these cone descriptions and the bit length of $\mu$.
Proof. Maintain a set $T$ of cones still permitted, initially all of them.
For this set, construct the closed linear feasibility system $P_T$ by requiring
$$
\sum_{j\in T}x^j=\mu,
\qquad x^j\geq0,
$$
and imposing every cone condition except that each strict inequality is relaxed to
$$
f_{j,\ell}(x^j)\geq0.
$$
If $P_T$ is infeasible, reject. This cannot discard a genuine covering, since every genuine covering satisfies the relaxation.
For each $j\in T$, solve a linear program over $P_T$ maximizing $\delta$, subject to
$$
0\leq\delta\leq1,
\qquad
f_{j,\ell}(x^j)\geq\delta
\quad\text{for all }\ell.
$$
Call $j$ activatable if its optimum is positive.
If a genuine covering uses cone $j$, its nonzero vector satisfies every strict inequality. Taking the minimum of these positive slacks and $1$ gives a feasible positive $\delta$. Therefore every nonactivatable cone must be unused in every genuine covering. Delete all such cones and repeat.
It remains to justify acceptance when every remaining cone is activatable. For each $j\in T$, choose a feasible witness $X^{(j)}$ in which every strict expression of component $j$ is positive. Average these $|T|$ witnesses.
The covering equation, all equalities, and all weak inequalities hold in the average. Fix $k\in T$. Every strict expression of its component is nonnegative in every witness and positive in witness $X^{(k)}$. It is therefore positive in the average. Thus the averaged component belongs to $\mathcal C_k$.
The average consequently supplies a genuine covering using all remaining cones.
Each nonterminal round deletes at least one cone, so there are at most $N$ deletion rounds. Each round uses at most $N+1$ linear programs. All their variables are bounded by the covering equation and nonnegativity, and the margin variable is bounded explicitly. Rational linear programming therefore gives the claimed polynomial-time procedure. $\square$
This proof also explains why merely testing the closed relaxation would be insufficient: it may cover $\mu$ using boundary vectors whose median signatures are incorrect.
Enumerate and test all median signatures from Section 2. Store the nonempty cones $\mathcal C_j$, their supports $S_j$, and their payoff vectors $u^j$.
Next enumerate
$$
q\in\prod_{\theta\in\Theta}D_\theta.
$$
For each candidate, perform the following steps.
First, check blocking. Reject $q$ if some nonempty signature satisfies
$$
u_\theta^j\geq q_\theta
\qquad(\theta\in S_j),
$$
with a strict inequality for at least one $\theta\in S_j$.
By Lemma 1, this test detects exactly the compositions that would block an outcome with uniform payoffs $q$.
Second, check attainability. Retain precisely the signatures satisfying
$$
u_\theta^j=q_\theta
\qquad(\theta\in S_j).
$$
Apply Lemma 4 to decide whether
$$
\mu=\sum_jx^j,
\qquad
x^j\in\mathcal C_j\cup\{0\},
$$
using only these retained signatures.
Accept if this covering exists.
An accepted covering gives finitely many coalitions, each paying $q_\theta$ to every participating type $\theta$. Since the first step excluded every blocking signature, Lemma 1 proves that this outcome is $\mathrm{SCR}$-stable.
Conversely, suppose an $\mathrm{SCR}$-stable outcome exists. Lemma 2 supplies a uniform payoff vector $q$, belonging to the enumerated product.
Replace each positive residual singleton mass by one pure-type coalition of the same mass. Its payoff is unchanged. Group coalitions having the same signature and add their vectors. Their sum remains in that signature cone: homogeneous equalities and weak inequalities are preserved, while every required strict expression remains positive.
This gives exactly a covering by retained cones. Its payoff vector passes the blocking test, so the algorithm accepts.
There are at most $D^\tau$ candidate payoff vectors and at most
$$
K=2^\tau D^\tau
$$
signatures. Constructing the menu requires $K$ linear programs of polynomial size in $(\tau,L)$.
For each payoff candidate, the blocking scan takes polynomial time in $(K,\tau,L)$. Lemma 4 also takes polynomial time in $(K,\tau,L)$: its linear programs have at most $\tau K+1$ variables and polynomially many constraints.
Thus the total running time is
$$
D^\tau\operatorname{poly}(K,\tau,L)
=
2^{O(\tau\log(\tau+1))}\operatorname{poly}(L).
$$
Since $m=\tau$, this gives an exact algorithm parameterized by the actual support size. It does not establish polynomial time when that size varies.
Assume there exists a nonempty set $T\subseteq\Theta$ such that, for every type $\theta$,
$$
\{\eta:v_\theta(\eta)=V_\theta\}=T,
\qquad
V_\theta:=\max_{\eta\in\Theta}v_\theta(\eta).
$$
The profiles may rank all nonmaximizing types differently.
Theorem 5. Under this assumption, an $\mathrm{SCR}$-stable outcome exists if and only if
$$
\mu(T):=\sum_{\theta\in T}\mu_\theta>\frac12.
$$
Proof.
First suppose a stable outcome exists, with uniform payoffs $q$.
For every $h\in T$, its singleton payoff is $V_h$. Individual rationality and the fact that no median payoff exceeds a profile maximum imply
$$
q_h=V_h.
$$
Now consider $i\notin T$. If $q_i<V_i$, choose any $h\in T$ and the composition
$$
w=e_i+2e_h.
$$
Type $h$ has a strict majority, so
$$
U_i(w)=v_i(h)=V_i,
\qquad
U_h(w)=v_h(h)=V_h=q_h.
$$
This weakly improves both participating types and strictly improves $i$. Lemma 1 gives an $\mathrm{SCR}$-block. Hence
$$
q_i=V_i
\qquad\text{for every }i.
$$
A nonzero coalition gives its participating types their profile maxima exactly when
$$
z(T)>\frac{M(z)}2.
$$
To verify this, if the inequality holds, more than half the mass is at the maximum value in every profile, so both median endpoints equal that maximum. If $z(T)<M(z)/2$, the upper endpoint is below the maximum. If equality holds, the upper endpoint is the maximum and the lower endpoint is strictly below it, so their midpoint is below the maximum.
Types outside $T$ cannot remain singletons, since their singleton payoffs are strictly below their maxima. Replace any residual singleton masses of types in $T$ by pure-type coalitions. All coalitions in the resulting finite covering satisfy
$$
z(T)>z(\Theta\setminus T).
$$
Summing these strict inequalities gives
$$
\mu(T)>\mu(\Theta\setminus T)=1-\mu(T),
$$
and therefore $\mu(T)>1/2$.
Conversely, if $\mu(T)>1/2$, the grand coalition gives every type its profile maximum. No deviation can strictly improve any selected mass, so it is $\mathrm{SCR}$-stable. $\square$
The hypothesis and the mass inequality can both be checked in polynomial time.
For a concrete no-instance, take two equally massive types with both profiles assigning value $0$ to the first type and $1$ to the second. Here $T$ contains only the second type and $\mu(T)=1/2$, so no $\mathrm{SCR}$-stable outcome exists.
The sharper algorithm is compatible with the previously established upper bound
$$
\mathrm{SCR}\text{-existence}\in\Sigma_2^p.
$$
For completeness, the witness arguments are given here.
Start from a stable outcome and replace singleton residuals by pure-type coalitions.
If more than $\tau$ coalition vectors remain, they are linearly dependent. Express their sum using positive coefficients. Move those coefficients along a nonzero linear dependence until one first becomes zero, keeping all coefficients nonnegative.
Such a dependence has coefficients of both signs: a nonzero nonnegative combination of nonzero nonnegative vectors cannot equal zero. Therefore this movement is possible and removes a coalition while preserving the covering vector.
Repeat until at most $\tau$ coalitions remain. Every retained vector is positively rescaled, so its payoff is unchanged. For $\mathrm{SCR}$, uniform payoffs are preserved; more generally, no type’s minimum decreases. Lemma 1 therefore preserves stability.
Fix the signatures of these at most $\tau$ coalition vectors. Their coordinates satisfy the covering equation and rational linear signature conditions.
Introduce a common margin $\delta$ for all strict inequalities, with $0\leq\delta\leq1$, and maximize it. The original real outcome supplies a positive feasible margin. Nonnegativity and the covering equation bound every coordinate, so this linear program has an optimal rational vertex with positive margin.
There are at most $\tau^2+1$ variables. Its coefficients have polynomial bit length in the original input. Clearing denominators and using Cramer’s rule with determinant bounds gives polynomial bit length for the vertex coordinates. The positive margin preserves every signature, hence all supports, payoffs, and blocking comparisons.
Thus a stable outcome, if one exists, has a polynomial-size rational certificate.
Likewise, any blocking composition can be normalized to total mass one. Fixing its signature and applying the same margin argument produces a rational blocking composition of polynomial bit length. Its blocking inequalities can be verified by exact rational arithmetic in polynomial time.
Consequently, one can guess a polynomial-size outcome and use an $\mathrm{NP}$ oracle to test whether a blocking composition exists. This establishes membership in $\Sigma_2^p$.
Open point. Neither this upper bound nor the improved exact algorithm proves a polynomial-time algorithm or NP-hardness for general $\mathrm{SCR}$-existence. The requested general classification remains open in this write-up.
⟨structured verdict parsed — rendered above⟩
The output gives a rigorous resolution of $\mathrm{CR}$-existence and valid partial results for $\mathrm{SCR}$-existence. I found no mathematical error in the supplied arguments. It does not resolve the requested general $\mathrm{SCR}$ classification, as it explicitly acknowledges.
Each $p_\theta$ exists because the outcome has finitely many coalition origins, at most one residual origin per type, and $\mu_\theta>0$.
Both directions of Lemma 1 are valid. An actual deviation improves relative to selected origins whose payoffs are at least $p_\theta$. Conversely, finite support permits a common positive scaling that fits the proposed composition into minimum-payoff origins. Atomlessness supplies the required selections.
The $\mathrm{SCR}$ strictness condition is handled correctly: a participating type with a strict comparison contributes positive selected mass. The conclusions about increasing minimum payoffs and individual rationality follow.
The different placements of strict inequalities in the lower- and upper-endpoint formulas are essential and correct. They cover exactly balanced splits and zero mass at intervening profile values.
Every payoff lies in $D_\theta$, and
$$
|D_\theta|\leq\frac{\tau(\tau+1)}2.
$$
Enumerating a support and an endpoint pair for every profile gives the stated signature bound. Infeasible endpoint combinations are harmless because nonemptiness is tested.
Signature conditions are homogeneous linear conditions. Addition and positive scaling preserve every strict condition as well as the weak conditions and equalities. Thus each nonempty signature has the stated constant support and payoff vector.
The normalized common-margin linear program correctly detects nonemptiness. Its feasible region is bounded, and positivity of the optimum is equivalent to simultaneous satisfaction of all strict inequalities.
The quoted domination statement matches Lemma 1 of the cited [Biró–Csáji–Schlotter paper](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/LIPIcs.ICALP.2025.31/LIPIcs.ICALP.2025.31.pdf). The source permits nonnegative capacities; the strictly positive capacities used here satisfy that hypothesis.
The matrix is finite and nonnegative, every column is nonzero, and arbitrary tie-breaking produces the required strict row orderings. The displayed normalization proves boundedness.
Including $e_\theta$ forces row $\theta$ to be saturated, since that column can only be dominated there. Therefore the selected columns cover $\mu$ exactly.
Domination guarantees that every used coalition incident with the chosen row has payoff at least that of the candidate column. Consequently, that participating type cannot strictly improve. The finite-signature representation and Lemma 1 then exclude every $\mathrm{CR}$ deviation.
The conclusion that every valid instance admits a $\mathrm{CR}$-stable outcome is established. This makes the existence decision problem polynomial-time without claiming polynomial-time construction.
An existing coalition weakly improves upon the minimum-payoff vector for all its participants. If any participant receives strictly more than its minimum, the same composition supplies an $\mathrm{SCR}$ block through Lemma 1.
The residual-singleton argument also works. Hence every positive-mass origin of a given type has the same payoff, and each coordinate of the uniform vector belongs to $D_\theta$.
The proof correctly separates mass below $c$ into the cases below, above, and exactly equal to half the total mass.
In the balanced case, both parts have positive mass, so $\ell(z)$ and $h(z)$ are defined. Under addition, the lower endpoint is the maximum of the two lower endpoints and the upper endpoint is the minimum of the two upper endpoints. Choosing the summand attaining the latter minimum justifies the displayed bound.
Reflection of the median interval under profile negation gives the corresponding sublevel-set property. These two properties prove Lemma 3 and the asserted convexity of fixed-payoff sets with fixed support.
The example showing failure of topological closedness is also correct.
Every genuine covering satisfies the relaxed system. If a cone is used in a genuine covering, all its strict expressions have positive slack, so its activation program has positive optimum. Deleting nonactivatable cones therefore cannot remove a genuine covering.
When all remaining cones are activatable, averaging their witnesses preserves the covering equation and every relaxed condition. For each component, every strict expression is nonnegative in all witnesses and positive in its own witness. Thus every required strict expression is positive in the average.
The procedure terminates after at most $N$ deletion rounds. Its linear programs have polynomial description size, with bounded component coordinates and bounded margin variable. Exact rational linear programming therefore supports the claimed polynomial running time.
The empty-set case causes no gap in this application: because $\mu$ has positive total mass, the covering equation with no remaining cones is infeasible and is rejected before averaging.
The blocking scan checks precisely the support-restricted weak comparisons and the required strict comparison. Values assigned to nonparticipating types do not affect this test.
The attainability scan correctly retains signatures paying the candidate $q$ to every participating type. Lemma 4 then decides whether those signatures cover the society.
Acceptance produces a uniform-payoff outcome without a blocking composition. Conversely, uniformity, replacement of residual singleton mass, and aggregation within each signature yield the required covering from every stable outcome.
The running-time calculation is valid:
$$
D^\tau\operatorname{poly}(K,\tau,L)
=
2^{O(\tau\log(\tau+1))}\operatorname{poly}(L).
$$
This is an exact parameterized bound, not a polynomial-time bound for variable $\tau$.
Individual rationality forces each type in $T$ to receive its profile maximum. The proposed composition $e_i+2e_h$ then establishes that every outside type must also receive its maximum in a stable outcome.
The characterization
$$
U_\theta(z)=V_\theta
\quad\Longleftrightarrow\quad
z(T)>\frac{M(z)}2
$$
is correct under the common-maximizer assumption. At equality, the lower endpoint is strictly below the maximum, so the midpoint is strictly below it.
Replacing residual singleton masses in $T$ and summing the strict majority inequalities over the finite covering gives $\mu(T)>1/2$. The converse follows because the grand coalition then gives everyone their maximum.
This includes $T=\Theta$ and $\tau=1$. The stated two-type no-instance is valid.
The linear-dependence elimination preserves the covering vector while deleting coalitions through nonnegative coefficients. Nonzero dependence coefficients must have both signs because all coalition vectors are nonzero and nonnegative.
Positive rescaling preserves signatures and payoffs. Removing origins cannot decrease any type’s minimum payoff, so stability is preserved.
Fixing at most $\tau$ signatures yields a bounded rational linear program with at most $\tau^2+1$ variables. The original real outcome supplies positive common slack. The rational-vertex and determinant argument therefore gives polynomial-bit rational outcome coordinates while preserving signatures.
The analogous normalized argument gives polynomial-bit blocking compositions. Exact rational verification of supports, median payoffs, and blocking comparisons is polynomial-time. The claimed membership
$$
\mathrm{SCR}\text{-existence}\in\Sigma_2^p
$$
follows.
General $\mathrm{SCR}$-existence is not classified as polynomial-time or NP-hard. The exact exponential algorithm, restricted polynomial-time classification, and $\Sigma_2^p$ upper bound do not settle that question.
This is an acknowledged limitation, not an invalid inference or internal inconsistency. No clarification of the existing proofs suffices to finish the assignment; a further general complexity result is required.
The established results are genuine progress. The overall status is partial because the task asks for both stability notions, and the general $\mathrm{SCR}$ case remains unresolved.
⟨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.