Answer: —
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateA categorical economy with additively separable and dichotomous preferences has nonempty weak core.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(\Theta\), rational masses \(\mu_\theta\), categories \(k\in\{1,\ldots,K\}\), finite goods \(O^k\), per-agent integral endowments \(e_{\theta,o}\), and acceptable sets \(G_\theta^k\), let \(v_\theta(B)=\sum_k \mathbf{1}[B\cap G_\theta^k\neq\emptyset]\) for integral bundles \(B\) containing at most one good per category, and let \(q_o=\sum_\theta\mu_\theta e_{\theta,o}\). Compute a mass allocation \(z_{\theta,B}\ge0\) with \(\sum_B z_{\theta,B}=\mu_\theta\) and \(\sum_{\theta,B:o\in B}z_{\theta,B}\le q_o\), such that no positive-mass selection \(0\le s_{\theta,B}\le z_{\theta,B}\) admits variables \(y_{\theta,B,B'}\ge0\) satisfying \(\sum_{B'}y_{\theta,B,B'}=s_{\theta,B}\), \(v_\theta(B')>v_\theta(B)\) whenever \(y_{\theta,B,B'}>0\), and \(\sum_{\theta,B,B':o\in B'}y_{\theta,B,B'}\le\sum_{\theta,B}s_{\theta,B}e_{\theta,o}\) for every good \(o\).
A society is given by its support: the list of \(\tau\geq1\) types \(\Theta\) with positive mass, each mass \(\mu_\theta\) a binary rational, with \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
Let \(O=\bigsqcup_{k=1}^{K}O^k\), where \(K\geq1\) and categories are finite and nonempty; write \(m=|O|\). Each type has explicitly listed acceptable sets \(G_\theta^k\subseteq O^k\) and binary-encoded endowments \(e_{\theta,o}\in\mathbb Z_{\geq0}\), with \(\sum_o e_{\theta,o}\geq1\). Set \(q_o=\sum_\theta\mu_\theta e_{\theta,o}>0\) for every good.
The allowable bundles are \(\mathcal B=\{B\subseteq O:|B\cap O^k|\leq1\text{ for every }k\}\), including the empty bundle. Utility is \(v_\theta(B)=\sum_{k=1}^{K}\mathbf1[B\cap G_\theta^k\neq\emptyset]\); equal utilities mean indifference. Endowments need not be allowable consumption bundles.
A mass allocation satisfies \(z_{\theta,B}\geq0\), \(\sum_{B\in\mathcal B}z_{\theta,B}=\mu_\theta\), and \(\sum_{\theta,B:o\in B}z_{\theta,B}\leq q_o\). Unused goods may be discarded.
It is in the weak core if there are no real selections \(0\leq s_{\theta,B}\leq z_{\theta,B}\) with \(\sum_{\theta,B}s_{\theta,B}>0\) and real transfers \(y_{\theta,B,B'}\geq0\), indexed by \(B,B'\in\mathcal B\), satisfying \(\sum_{B'}y_{\theta,B,B'}=s_{\theta,B}\), \(y_{\theta,B,B'}>0\Rightarrow v_\theta(B')>v_\theta(B)\), and \(\sum_{\theta,B,B':o\in B'}y_{\theta,B,B'}\leq\sum_{\theta,B}s_{\theta,B}e_{\theta,o}\) for every \(o\). Thus every participating member strictly improves using the coalition's original endowments.
Represent an exact output by listing its nonzero \(z_{\theta,B}\) as binary rationals and their bundles; all omitted entries are zero. Let \(L\) be the total input bit length.
Is computing a weak-core mass allocation, or determining that none exists, solvable in time polynomial in \(m,\tau,K,L\), or is this computational problem NP-hard?
For finite agents with distinct endowed objects, categorical additively separable dichotomous preferences guarantee a nonempty weak core; this is an existence result, not a polynomial-time bound ([Echenique–Goel–Lee](https://goelsumit.com/files/exchange_stable.pdf)).
Finite categorical economies with additive utilities also have a nonempty weak random core under expected-utility blocking, which differs from the bundle-contingent blocking defined here ([Echenique–Goel–Lee](https://goelsumit.com/files/exchange_stable.pdf)). No result settling this exact mass computation problem was located.
I do not settle the unrestricted complexity question. I prove two additional polynomial-time cases:
The first result follows from an exact characterization of weak-core stability by prices. I also reprove the existence and verification results needed for these arguments and complete the formal totality argument from the notes.
Write
$$
A_\theta=\bigcup_{k=1}^{K}G_\theta^k,
\qquad
n_\theta=\bigl|\{k:G_\theta^k\neq\emptyset\}\bigr|.
$$
An acceptable bundle for type $\theta$ is an allowable bundle contained in $A_\theta$. Its utility equals its cardinality, and the maximum attainable utility is $n_\theta$.
For a feasible allocation $z$, define
$$
a_\theta=\min\{v_\theta(B):z_{\theta,B}>0\}.
$$
This minimum exists because the bundle family is finite and $\mu_\theta>0$. In particular,
$$
0\leq a_\theta\leq n_\theta.
$$
For an integer vector $a$, define
$$
\mathcal C_\theta(a)
=
\{C\in\mathcal B:C\subseteq A_\theta,\ |C|=a_\theta+1\}.
$$
Lemma 1. A feasible allocation with minimum supported utilities $a$ is blocked if and only if there exist numbers $h_{\theta,C}\geq0$, indexed by $C\in\mathcal C_\theta(a)$, such that
$$
\sum_{\theta,C}h_{\theta,C}=1
$$
and
$$
\sum_{\theta,C:o\in C}h_{\theta,C}
\leq
\sum_{\theta,C}h_{\theta,C}e_{\theta,o}
\qquad(o\in O).
$$
Proof. Suppose a block exists. Every participating type-$\theta$ member starts with utility at least $a_\theta$. Because utilities are integers, every target bundle has utility at least $a_\theta+1$. Delete its unacceptable goods and retain exactly $a_\theta+1$ acceptable goods. This preserves allowability and decreases consumption.
Aggregate the resulting transfers by type and trimmed target bundle. Dividing by the positive total participating mass gives the required $h$.
Conversely, suppose such an $h$ exists. For each type, choose a bundle $B_\theta$ attaining its minimum supported utility, with
$$
z_{\theta,B_\theta}>0.
$$
Set
$$
t_\theta=\sum_C h_{\theta,C}.
$$
Choose $c>0$ small enough that
$$
ct_\theta\leq z_{\theta,B_\theta}
$$
for every type with $t_\theta>0$. This is possible because there are finitely many such types.
Select mass $ct_\theta$ from $B_\theta$ and transfer mass $ch_{\theta,C}$ to $C$. Every selected member improves from utility $a_\theta$ to $a_\theta+1$, and the resource inequalities follow by multiplying those for $h$ by $c$. Thus this is a block. $\square$
Consequently, stability depends only on the minimum supported utilities, not on the magnitudes of the positive allocation entries.
The following decomposition establishes the required equivalence between bundle distributions and good marginals.
Lemma 2. Fix a type $\theta$ and a nonnegative integer $r$. Suppose $t>0$ and nonnegative numbers $h_o$, for $o\in A_\theta$, satisfy
$$
\sum_{o\in A_\theta}h_o=rt,
\qquad
\sum_{o\in G_\theta^k}h_o\leq t
\qquad(k=1,\ldots,K).
$$
Then $h$ is the good-marginal vector of a distribution of total mass $t$ over acceptable bundles of cardinality $r$.
For rational $t,h$, such a distribution can be constructed in polynomial time, with at most $m+K+1$ positive entries and polynomially bounded rational encoding length.
Proof. Maintain residual mass $t$ and residual marginals $h$. Write
$$
H_k=\sum_{o\in G_\theta^k}h_o.
$$
Call a category tight if $H_k=t$.
There are at most $r$ tight categories: each contributes $t$ to the total $rt$. There are at least $r$ categories with positive residual marginals: each contributes at most $t$.
Choose exactly $r$ positive categories, including every tight category, and choose one good with positive residual mass from each chosen category. Let $v$ be this bundle’s incidence vector, and let $v_k$ indicate whether category $k$ was chosen.
Define
$$
\delta
=
\min\left(
\{t\}
\cup
\{h_o:v_o=1\}
\cup
\{t-H_k:v_k=0\}
\right).
$$
Every term is positive. Selected goods have positive mass, and every unselected category is slack.
Output mass $\delta$ on this bundle and replace
$$
h_o\leftarrow h_o-\delta v_o,
\qquad
t\leftarrow t-\delta.
$$
Nonnegativity remains valid. For a selected category,
$$
H_k-\delta\leq t-\delta.
$$
For an unselected category, the definition of $\delta$ gives
$$
H_k\leq t-\delta.
$$
The cardinality equation remains valid because
$$
\sum_o(h_o-\delta v_o)=rt-r\delta=r(t-\delta).
$$
Previously zero coordinates remain zero, and previously tight categories remain tight. If $\delta<t$, at least one previously positive coordinate becomes zero or one previously slack category becomes tight. Hence there are at most $m+K$ iterations with positive residual mass afterward, followed by at most one final iteration.
If the residual mass becomes zero, the cardinality equation and nonnegativity force all residual marginals to be zero. Thus the output has exactly the prescribed total mass and marginals.
For rational inputs, all operations are comparisons, minima, and subtraction. A common denominator for the initial entries remains a common denominator throughout. Residual entries stay bounded by their initial total mass, so their bit lengths remain polynomial. The choices and the number of iterations are polynomial. The case $r=0$ outputs the empty bundle with mass $t$. $\square$
For $a\in\prod_\theta\{0,\ldots,n_\theta\}$, let $F(a)$ be the following feasibility LP, with variables $w_{\theta,o}\geq0$ for acceptable goods:
$$
\sum_{o\in A_\theta}w_{\theta,o}=\mu_\theta a_\theta
\qquad(\theta\in\Theta),
$$
$$
\sum_{o\in G_\theta^k}w_{\theta,o}\leq\mu_\theta
\qquad(\theta\in\Theta,\ k=1,\ldots,K),
$$
$$
\sum_{\theta:o\in A_\theta}w_{\theta,o}\leq q_o
\qquad(o\in O).
$$
Proposition 3. The LP $F(a)$ is feasible if and only if there is a feasible allocation giving every type-$\theta$ member utility exactly $a_\theta$. Such an allocation can be constructed from a rational feasible solution in polynomial time.
Proof. Given the allocation, delete unacceptable goods and take its good marginals. The resulting variables satisfy $F(a)$.
Conversely, apply Lemma 2 to each type with total mass $\mu_\theta$ and cardinality $a_\theta$. Its bundle distribution has the specified marginals. The supply inequalities then establish feasibility. Rational linear programming produces a feasible solution of polynomial bit length, and Lemma 2 supplies the required exact output. $\square$
The feasible threshold vectors are downward closed. Indeed, if $b_\theta\leq a_\theta$ for every type and $F(a)$ is feasible, multiply type $\theta$’s marginals by $b_\theta/a_\theta$ when $a_\theta>0$. When $a_\theta=0$, its marginals are already zero. This gives a feasible solution of $F(b)$.
For blocking, put $r_\theta=a_\theta+1$. Let $H(a)$ have nonnegative variables $t_\theta$ and $f_{\theta,o}$, with constraints
$$
\sum_\theta t_\theta=1,
$$
$$
\sum_{o\in A_\theta}f_{\theta,o}=r_\theta t_\theta
\qquad(\theta\in\Theta),
$$
$$
\sum_{o\in G_\theta^k}f_{\theta,o}\leq t_\theta
\qquad(\theta\in\Theta,\ k=1,\ldots,K),
$$
$$
\sum_{\theta:o\in A_\theta}f_{\theta,o}
\leq
\sum_\theta t_\theta e_{\theta,o}
\qquad(o\in O).
$$
Proposition 4. An allocation with minimum supported utilities $a$ is in the weak core if and only if $H(a)$ is infeasible.
Proof. A normalized block from Lemma 1 gives a feasible solution by taking
$$
t_\theta=\sum_C h_{\theta,C},
\qquad
f_{\theta,o}=\sum_{C:o\in C}h_{\theta,C}.
$$
Conversely, apply Lemma 2 to every type with $t_\theta>0$. This decomposes its marginals into acceptable bundles of cardinality $a_\theta+1$, giving the numbers required by Lemma 1. If $t_\theta=0$, the cardinality equation and nonnegativity force all its marginals to be zero. $\square$
Both LPs have polynomially many variables and constraints, with polynomial coefficient bit lengths. Thus weak-core membership is decidable in polynomial time in the input and listed output lengths, including against real-valued blocks.
For $p\in\mathbb R_{\geq0}^{O}$, write
$$
p(C)=\sum_{o\in C}p_o,
\qquad
p(e_\theta)=\sum_o p_o e_{\theta,o}.
$$
Theorem 5. A feasible allocation with minimum supported utilities $a$ is in the weak core if and only if there exists a nonnegative price vector $p$, normalized by
$$
\sum_o p_o=1,
$$
such that
$$
p(C)>p(e_\theta)
\qquad
\bigl(\theta\in\Theta,\ C\in\mathcal C_\theta(a)\bigr).
$$
Whenever such prices exist, rational prices with polynomially bounded bit length exist.
Proof. For each improvement bundle, define its net-resource vector
$$
d_{\theta,C}=\mathbf1_C-e_\theta.
$$
Let $\mathcal D$ be the finite family of these vectors.
If the asserted prices exist, every vector in $\mathcal D$ has positive scalar product with $p$. Every convex combination therefore also has positive scalar product. But a normalized block would give a convex combination that is componentwise nonpositive. Its scalar product with $p\geq0$ would be nonpositive, a contradiction.
For the converse, assume there is no block. If $\mathcal D$ is empty, every normalized nonnegative price vector works. Otherwise, let
$$
T=\operatorname{conv}(\mathcal D),
\qquad
Q=\mathbb R_{\leq0}^{O}.
$$
Lemma 1 says exactly that $T\cap Q=\emptyset$.
Because $T$ is compact, choose $d^*\in T$ minimizing
$$
\sum_o\max\{d_o,0\}^2.
$$
Set
$$
u_o^*=\min\{d_o^*,0\},
\qquad
p_o=d_o^*-u_o^*=\max\{d_o^*,0\}.
$$
The pair $(d^*,u^*)$ minimizes the squared distance between $T$ and $Q$. Since the sets are disjoint, $p\neq0$.
For any $d\in T$ and $0\leq\varepsilon\leq1$, the point
$$
d^*+\varepsilon(d-d^*)
$$
belongs to $T$. Minimality therefore implies
$$
\left\|d^*+\varepsilon(d-d^*)-u^*\right\|^2
\geq
\|d^*-u^*\|^2.
$$
Taking the right derivative at $\varepsilon=0$ gives
$$
p\cdot(d-d^*)\geq0.
$$
Furthermore,
$$
p\cdot d^*=\|p\|^2>0.
$$
Consequently,
$$
p\cdot d\geq\|p\|^2>0
\qquad(d\in T).
$$
Normalize $p$ by its positive coordinate sum. This proves the price inequalities.
For the encoding claim, consider the finite LP
$$
p_o\geq0,\qquad \sum_o p_o=1,\qquad 0\leq\delta\leq1,
$$
$$
p\cdot d_{\theta,C}\geq\delta
\qquad(\theta,C).
$$
The preceding argument supplies a feasible point with $\delta>0$. The feasible region is compact, so maximizing $\delta$ has a vertex optimum with positive value.
There are $m+1$ variables. All coefficients are integers whose bit lengths are bounded by the input length, even though the number of rows can be exponential. A vertex is determined by $m+1$ independent tight rows. Cramer’s rule and Hadamard’s determinant bound therefore give polynomial bit lengths for its coordinates. $\square$
Define the largest affordable acceptable cardinality at prices $p$ by
$$
b_\theta(p)
=
\max\{|C|:C\subseteq A_\theta,\ C\in\mathcal B,\ p(C)\leq p(e_\theta)\}.
$$
The empty bundle guarantees that this maximum exists.
Corollary 6. A weak-core allocation exists if and only if there is a normalized nonnegative price vector $p$ such that $F(b(p))$ is feasible.
More precisely, every feasible allocation giving type $\theta$ utility exactly $b_\theta(p)$ is in the weak core.
Proof. By definition of $b_\theta(p)$, every acceptable bundle of cardinality $b_\theta(p)+1$ costs strictly more than $p(e_\theta)$. Theorem 5 proves the second assertion.
Conversely, take a weak-core allocation with minima $a$. Trimming each bundle to exactly $a_\theta$ acceptable goods proves that $F(a)$ is feasible. Choose prices from Theorem 5.
If $b_\theta(p)>a_\theta$, an affordable acceptable bundle has an acceptable subbundle of size $a_\theta+1$. Nonnegative prices make this subbundle affordable, contradicting Theorem 5. Thus
$$
b(p)\leq a
$$
componentwise. Downward closure of $F$ gives feasibility of $F(b(p))$. $\square$
For any specified rational $p$, the vector $b(p)$ is computable in polynomial time. For each nonempty acceptable category, take its cheapest acceptable good, sort these category prices, and find the longest prefix whose sum is at most $p(e_\theta)$. A cheapest acceptable bundle of cardinality $r$ uses precisely the $r$ cheapest categories.
Here is the finite theorem used, with its hypotheses stated explicitly:
A finite economy with distinct objects, pairwise disjoint nonempty endowments, categorical consumption, and additively separable dichotomous preferences has a nonempty weak core.
This is [Echenique–Goel–Lee, Theorem 1](https://goelsumit.com/files/exchange_stable.pdf). Their categorical model permits unrestricted endowments and discarding, and their weak core excludes coalitions in which every member strictly improves.
Theorem 7. Every valid instance in the question has a weak-core mass allocation.
Proof. Choose an integer $D>0$ clearing all mass denominators. For each positive integer $n$, put
$$
N_n=nD.
$$
Construct a finite economy with $N_n\mu_\theta$ agents of type $\theta$. Each owns $e_{\theta,o}$ distinct labeled copies of good $o$. Copies retain their original categories and acceptability.
Each agent has a nonempty endowment. All endowed copies are distinct and partition the object set. Each original good has
$$
N_nq_o>0
$$
copies, an integer. Thus every category is nonempty, and the finite theorem applies.
Choose a finite weak-core allocation. Retain at most one acceptable object per category for each agent and discard the rest. Utilities are preserved, so the modified allocation remains in the weak core: a block of the modified allocation would also block the original one.
Project copies to original good labels and divide agent counts by $N_n$. This gives a feasible mass allocation $z^{(n)}$.
The mass-allocation feasible set is compact: it is a closed bounded subset of the finite-dimensional space with coordinates $(\theta,B)$. Hence a subsequence converges to a feasible allocation $z^*$.
Suppose $z^*$ is blocked. Let $a$ be its minimum supported utilities and choose, for each participating type, a bundle $B_\theta$ with
$$
z^*_{\theta,B_\theta}>0,
\qquad
v_\theta(B_\theta)=a_\theta.
$$
By Lemma 1, its normalized blocking system is feasible. This is a finite rational polytope: its coefficients are integers and its nonnegative variables sum to one. It therefore has a rational feasible point.
Clearing denominators yields nonnegative integers $H_{\theta,C}$, not all zero, satisfying
$$
\sum_{\theta,C:o\in C}H_{\theta,C}
\leq
\sum_{\theta,C}H_{\theta,C}e_{\theta,o}
\qquad(o\in O).
$$
Put
$$
H_\theta=\sum_C H_{\theta,C}.
$$
Along the convergent subsequence, $z^{(n)}_{\theta,B_\theta}$ is eventually bounded below by a positive constant. Since $N_n$ tends to infinity, eventually
$$
N_nz^{(n)}_{\theta,B_\theta}\geq H_\theta
$$
for every participating type.
Select $H_\theta$ actual agents currently receiving projected bundle $B_\theta$. Give $H_{\theta,C}$ of them target bundle $C$. The integer resource inequalities ensure that enough distinct copies of each good occur in their original endowments to realize all targets.
Every selected agent improves from utility $a_\theta$ to $a_\theta+1$. This contradicts the finite allocation’s weak-core membership. Therefore $z^*$ is in the mass weak core. $\square$
Thus the “none exists” outcome never occurs on valid inputs. The remaining task is to compute an allocation.
Proposition 8. Every valid instance has a rational weak-core allocation with at most $\tau+m$ positive entries and polynomially bounded encoding length.
Proof. Take the allocation from Theorem 7 and its minima $a$. Trim every allocated bundle of type $\theta$ to exactly $a_\theta$ acceptable goods. This preserves feasibility and, by Lemma 1, stability.
Restrict the allocation LP to these acceptable cardinality-$a_\theta$ bundles. Add one supply slack for each good. The resulting nonempty bounded polytope has $\tau+m$ equality rows and a coefficient matrix with entries in $\{0,1\}$. A vertex therefore has at most $\tau+m$ positive allocation variables.
A common denominator for the masses also clears all supplies. Its bit length is polynomial in $L$, as are the cleared right-hand-side entries. Basic submatrices have order at most $\tau+m$. Hadamard’s inequality bounds their determinants, and Cramer’s rule gives polynomial numerator and denominator bit lengths.
Every positive bundle still gives its type utility exactly $a_\theta$, so the resulting allocation remains in the weak core. $\square$
Theorem 9. For every fixed $m$, a weak-core mass allocation can be computed in time polynomial in $\tau,K,L$.
Proof. Enumerate, for each type, all its acceptable allowable bundles. There are at most $2^m$ per type. For each pair $(\theta,C)$, define
$$
\ell_{\theta,C}(p)=p(C)-p(e_\theta).
$$
Let $N$ be the number of these forms, so
$$
N\leq\tau2^m.
$$
Their signs determine which acceptable bundles are affordable, and hence determine $b(p)$. It suffices to enumerate all realizable sign patterns on the price simplex
$$
\Delta=\left\{p\in\mathbb R_{\geq0}^{O}:\sum_o p_o=1\right\}.
$$
Process the forms successively. For each retained sign pattern, try extending it with a negative, zero, or positive sign for the next form.
A proposed pattern $\sigma$ is realizable on $\Delta$ precisely when the following rational LP has optimum $\varepsilon>0$:
$$
p\in\Delta,\qquad 0\leq\varepsilon\leq1,
$$
$$
\ell_j(p)\geq\varepsilon
\qquad\text{if }\sigma_j=1,
$$
$$
\ell_j(p)\leq-\varepsilon
\qquad\text{if }\sigma_j=-1,
$$
$$
\ell_j(p)=0
\qquad\text{if }\sigma_j=0.
$$
Indeed, a point realizing finitely many strict inequalities has a positive minimum strict margin. Conversely, positive $\varepsilon$ realizes the proposed signs. This also handles identically zero forms and equality cases.
Let
$$
d=m-1.
$$
The price simplex lies in the affine space
$$
\sum_o p_o=1,
$$
of dimension $d$. Consider the arrangement of the $N$ affine hyperplanes in that entire space, omitting forms whose zero sets are empty or the entire space.
The number of full-dimensional regions formed by $N$ hyperplanes in dimension $r$ is at most
$$
R_r(N)=\sum_{j=0}^{r}\binom Nj.
$$
To verify this bound, add hyperplanes successively. A new hyperplane splits at most as many existing regions as the induced arrangement has regions on that hyperplane. This gives the recurrence
$$
R_r(N)\leq R_r(N-1)+R_{r-1}(N-1),
$$
with the usual initial bounds $R_r(0)=1$ and $R_0(N)=1$, proving the displayed estimate by induction.
A nonempty sign cell of dimension $r$ has an affine hull determined by $d-r$ independent zero equations from the arrangement. There are at most
$$
\binom N{d-r}
$$
choices of such equations. Inside each resulting affine space, the possible cells are full-dimensional regions of the restricted arrangement, numbering at most $R_r(N)$.
Therefore the total number of realizable sign patterns is at most
$$
\sum_{r=0}^{d}\binom N{d-r}
\sum_{j=0}^{r}\binom Nj
\leq
(d+1)^2(N+1)^d.
$$
Intersecting with $\Delta$ cannot increase the number of sign patterns.
Thus the incremental enumeration performs polynomially many LP calls when $m$ is fixed. Each call has polynomial encoding length and returns a rational representative price vector of polynomial bit length.
For each final sign pattern, take its representative $p$, compute $b(p)$, and test $F(b(p))$. Whenever this LP is feasible, Proposition 3 constructs an exact allocation, and Corollary 6 proves its weak-core membership.
Theorem 7 and Corollary 6 guarantee that some sign pattern passes the test. A bound for this algorithm is
$$
\bigl(\tau2^m+1\bigr)^{O(m)}
\operatorname{poly}(m,\tau,K,L).
$$
For fixed $m$, this is polynomial. $\square$
This adds a polynomial case complementary to fixed support size. For completeness, fixed $\tau$ is also polynomial: enumerate the at most
$$
(K+1)^\tau
$$
threshold vectors, test $F(a)$ and $H(a)$, and construct an allocation when $F(a)$ is feasible and $H(a)$ is infeasible. Existence and trimming guarantee success.
Theorem 10. Suppose
$$
\sum_o e_{\theta,o}=1
\qquad(\theta\in\Theta).
$$
Then a weak-core allocation can be computed in polynomial time, with unrestricted $m,\tau,K$.
Proof. Construct a directed graph on types. Include an edge
$$
\theta\longrightarrow\phi
$$
if some good acceptable to $\theta$ is endowed to $\phi$. Self-loops are allowed.
Initially set the unserved mass to
$$
r_\theta=\mu_\theta.
$$
While the subgraph induced by types with $r_\theta>0$ has a directed cycle, choose a simple cycle
$$
\theta_1\longrightarrow\theta_2
\longrightarrow\cdots
\longrightarrow\theta_\ell
\longrightarrow\theta_1.
$$
For each edge, choose a witnessing good $o_i$, acceptable to $\theta_i$ and endowed to $\theta_{i+1}$, with cyclic indexing. Put
$$
\varepsilon=\min_i r_{\theta_i}.
$$
Allocate mass $\varepsilon$ of type $\theta_i$ the singleton $\{o_i\}$, and subtract $\varepsilon$ from every cycle type’s unserved mass. At termination, give all remaining mass the empty bundle.
Feasibility. Within a cycle, each demand is charged to one unit of the next type’s endowment. Each cycle type supplies exactly one demand. Thus cycle consumption is bounded coordinatewise by
$$
\varepsilon\sum_{i=1}^{\ell}e_{\theta_i,\cdot}.
$$
Across iterations, total mass charged to type $\theta$ is at most $\mu_\theta$. Total consumption is therefore bounded by $q$.
Complexity. Every iteration exhausts at least one type’s unserved mass, so there are at most $\tau$ iterations. Cycle detection is polynomial. Rational minima and subtraction preserve a common denominator for the input masses, giving polynomial bit lengths and output size.
Stability. Every served member receives utility one, and every unserved member receives utility zero.
Suppose a block exists. Let $S_0$ and $S_1$ be its participating masses currently receiving utilities zero and one, respectively. Every target for the first group contains at least one good; every target for the second group contains at least two goods. Therefore total target consumption, summed over all goods, is at least
$$
S_0+2S_1.
$$
Each participating member owns exactly one object, so the coalition’s total endowed quantity is
$$
S_0+S_1.
$$
Summing the resource inequalities gives
$$
S_0+2S_1\leq S_0+S_1.
$$
Hence $S_1=0$: only unserved members can participate.
Let $T$ be the types with positive participating mass. Each type in $T$ must receive a positive quantity of an acceptable good. The resource inequality for that good implies that some type in $T$ endows it. Thus every vertex of the graph induced by $T$ has an outgoing edge within $T$.
A finite directed graph with this property contains a directed cycle: follow outgoing edges until a vertex repeats. But $T$ is contained in the terminal unserved set, whose induced graph has no directed cycle. This contradiction proves stability. $\square$
The same cycle algorithm works for $K=1$ with arbitrary endowments. Its feasibility proof uses only that each witnessing endowment coordinate is at least one. For stability, served members then have maximum attainable utility and cannot participate; the remaining directed-cycle argument applies unchanged.
Propositions 4 and 8, together with Theorem 7, give a polynomially bounded total search formulation.
To make totality formal on every input string, define the relation as follows:
Validity is checkable in polynomial time. The explicitly listed sets and indices can be checked directly; rational masses, their sum, nonempty endowments, and positive supplies can be checked by exact arithmetic of polynomial bit length.
On valid inputs, output verification is polynomial by Proposition 4. Proposition 8 supplies a fixed polynomial witness-length bound, and Theorem 7 establishes totality. Thus this relation belongs to $\mathrm{TFNP}$, the class of polynomially bounded, polynomially verifiable total search relations.
There is a corresponding conditional restriction on one common meaning of NP-hardness. Suppose a polynomial-time reduction maps each SAT instance $\varphi$ to a valid economy $I_\varphi$, and a polynomial-time decoder correctly determines satisfiability from every valid weak-core output for $I_\varphi$.
Then an unsatisfiable formula has a polynomial certificate: a short weak-core output whose decoder returns “unsatisfiable.” Core membership and the decoder’s result are polynomially checkable. A satisfiable formula cannot have such a certificate, by decoder correctness. Consequently,
$$
\mathrm{UNSAT}\in\mathrm{NP},
$$
which implies
$$
\mathrm{NP}=\mathrm{coNP}.
$$
This is a conditional statement under the specified reduction convention. It does not settle the unrestricted search problem.
The general search is equivalently the task of finding prices $p$ for which
$$
F(b(p))
$$
is feasible. For specified prices, this condition is decidable in polynomial time. The unresolved step is finding suitable prices when both the number of goods and the support size vary.
The arrangement enumeration can genuinely encounter exponentially many affordable-threshold patterns. For example, take $n$ categories
$$
O^i=\{x_i,y_i\},
$$
and two types per category, each of mass $1/(2n)$. One owns $x_i$ and accepts only $y_i$; the other owns $y_i$ and accepts only $x_i$. Each independent comparison between $p_{x_i}$ and $p_{y_i}$ gives two different threshold pairs. Choosing these comparisons independently gives $2^n$ distinct threshold vectors.
This only limits the enumeration method. These particular instances are polynomial-time solvable by Theorem 10.
The proved results therefore provide an exact price certificate, polynomial computation for fixed $m$, and polynomial computation for arbitrary categories with one-object endowments. They establish neither an unrestricted polynomial-time algorithm nor an NP-hardness reduction.
⟨structured verdict parsed — rendered above⟩
Overall assessment: correct partial progress. The prover explicitly declines to settle the unrestricted complexity question. Its subsidiary mathematical arguments are sound: they establish existence, short rational outputs, polynomial verification, a price characterization, and several polynomial-time special cases. They establish neither a polynomial-time algorithm for unrestricted inputs nor NP-hardness.
I found no false central statement or mathematical gap in the proved subsidiary results. The remaining major issue is incompleteness relative to USER_TASK, rather than an error concealed in a claimed complete solution.
The definitions of $A_\theta$, $n_\theta$, and $a_\theta$ are consistent with the task.
An acceptable allowable bundle contains at most one good per category, so its cardinality equals its utility. Since $\mu_\theta>0$ and the bundle family is finite, the minimum defining $a_\theta$ exists.
Lemma 1 is correct in both directions.
If $a_\theta=n_\theta$, then $\mathcal C_\theta(a)$ is empty, correctly excluding that type from the normalized block.
The conclusion that stability depends only on minimum supported utilities is justified. Positive support magnitudes affect how far a block must be scaled down, but do not affect whether a positive scale exists.
Lemma 2 is correct. Its hypotheses imply that, while residual mass is positive, at most $r$ categories are tight and at least $r$ categories have positive marginals. The required selection of categories therefore exists.
Every term used to define $\delta$ is positive. After subtraction:
The termination argument is valid. Zero coordinates remain zero, and tight categories must remain selected and tight. Every nonfinal iteration creates a new zero coordinate or a new tight category. Thus the claimed bound of $m+K+1$ output entries holds.
The rational encoding argument also holds: subtraction preserves a common denominator, whose bit length is bounded by the sum of the initial denominator bit lengths. Residual quantities remain bounded. The separate treatment of $r=0$ handles the empty bundle correctly.
Proposition 3 is correct. Removing unacceptable goods preserves utility. Conversely, applying Lemma 2 separately to each type yields the required exact-cardinality distributions, and aggregate marginals enforce supply feasibility. Rational linear programming and the decomposition give polynomial output size and encoding length.
Downward closure is correct. Scaling a type’s marginals by $b_\theta/a_\theta$ preserves category inequalities and reduces resource use. The case $a_\theta=0$ is handled explicitly.
Proposition 4 is correct. Aggregating normalized bundle transfers gives $H(a)$. Its converse follows from Lemma 2 for positive $t_\theta$; zero $t_\theta$ forces zero marginals.
When $a_\theta=n_\theta$, summing the category inequalities makes positive $t_\theta$ impossible, as required.
The polynomial membership claim is justified. Both LPs have polynomial size and coefficient encoding length. For a listed rational allocation, feasibility and minimum supported utilities can also be checked in polynomial time. The LP equivalence addresses real-valued blocks, rather than merely rational blocks.
Theorem 5 is correct.
The forward implication uses the correct sign convention: a normalized block produces a convex combination of net-resource vectors that is componentwise nonpositive, contradicting strictly positive scalar products with nonnegative prices.
For the converse:
$$ p\cdot(d-d^*)\geq0. $$
$$ p\cdot d^*=\|p\|^2>0. $$
Normalization therefore produces all required strict inequalities. The empty-family case is handled correctly; a normalized price vector exists because $m\geq1$.
The polynomial rational encoding claim is also valid. The auxiliary LP has $m+1$ variables and a positive optimal margin. A vertex is determined by independent tight constraints, and determinant bounds depend on dimension and coefficient sizes, rather than on the potentially exponential number of rows.
Corollary 6 is correct. Its converse appropriately uses nonnegative prices to preserve affordability when passing to a subbundle. Downward closure then establishes feasibility of $F(b(p))$.
The computation of $b_\theta(p)$ is correct: an acceptable bundle of prescribed cardinality minimizes cost by choosing the cheapest acceptable good in each selected category and then selecting the cheapest categories. Zero prices, ties, and empty acceptable sets cause no failure.
The cited finite theorem has the required hypotheses. The source allows arbitrary endowments in its categorical model, permits unallocated objects, and defines weak-core blocking through strict improvement for every coalition member. Its Theorem 1 covers additively separable dichotomous preferences. [Echenique–Goel–Lee, model, categorical economy, and Theorem 1](https://goelsumit.com/files/exchange_stable.pdf).
Theorem 7 correctly transfers this existence result to the mass economy.
The contradiction at the limit is rigorous. A normalized block has a rational feasible point because its finite system has rational coefficients. Clearing denominators produces a fixed, nonzero integer blocking coalition specification.
Each required minimum-utility bundle has positive limiting mass, so sufficiently large replicated economies contain enough actual agents receiving it. The integer resource inequalities allow the target bundles to be realized with distinct copies from the selected agents’ original endowments. This contradicts finite weak-core membership.
The proof does not claim that constructing the replicated economies is polynomial time. Consequently, exponentially large replication is not a defect in this existence argument.
Proposition 8 is correct. Trimming preserves minima and stability. After adding supply slacks, a vertex has at most $\tau+m$ positive variables, hence at most that many positive allocation entries. The determinant argument supplies polynomial rational encoding length despite the exponential bundle family. Every retained allocation bundle has the original threshold utility, preserving stability.
Thus valid inputs always admit short exact rational outputs, and “none exists” never occurs.
Theorem 9 is correct.
The sign patterns determine affordability, including equality cases. The positive-margin LP correctly tests realizability; if there are no strict inequalities, its auxiliary margin can still be positive.
The arrangement count is valid:
Intersecting with the price simplex cannot introduce new sign patterns. Prefix enumeration therefore uses polynomially many LP calls for fixed $m$, including the boundary case $m=1$.
Testing $F(b(p))$ and applying Proposition 3 produces a core allocation when a pattern succeeds. Theorem 7 and Corollary 6 guarantee success.
The fixed-$\tau$ enumeration also follows from the established results: there are at most $(K+1)^\tau$ threshold vectors, and existence plus trimming guarantees an accepted vector.
Neither bound is polynomial in all unrestricted input parameters.
Theorem 10 is correct.
Under the one-object assumption, every type has exactly one endowed good. A cycle charges each singleton demand to the next type’s endowment, and each participating type supplies one demand. Cumulative charges remain bounded by its original mass.
Every iteration exhausts at least one active type. Cycle detection, rational arithmetic, and the resulting output therefore have polynomial complexity.
The stability argument correctly sums all resource inequalities:
$$
S_0+2S_1\leq S_0+S_1.
$$
This forces $S_1=0$, excluding all served participants.
Every participating unserved type must receive positive acceptable quantity. Its resource source includes a participating endowed type, producing an outgoing edge within the participating set. A finite graph with an outgoing edge at every vertex contains a directed cycle, contradicting termination.
The extension to $K=1$ with arbitrary endowments is also justified. A witnessing endowment coordinate is at least one, which suffices for feasibility. Served members have maximum utility and cannot strictly improve, so the terminal graph argument applies.
The $\mathrm{TFNP}$ formulation is correct. Invalid encodings can be recognized in polynomial time; valid encodings have polynomially bounded witnesses by Proposition 8; membership is polynomially verifiable by Proposition 4; and existence holds by Theorem 7.
The conditional hardness argument is correct under its explicitly stated convention. A decoder correct on every valid core output permits a short core output to certify unsatisfiability. Decoder correctness excludes such a certificate for satisfiable formulas. Hence the asserted reduction would imply
$$
\mathrm{NP}=\mathrm{coNP}.
$$
The prover appropriately does not extend this conclusion to unspecified notions of search-problem NP-hardness.
Major issue — the unrestricted classification remains open. The prover provides no polynomial-time search method when both $m$ and $\tau$ vary and no hardness reduction. This is expressly acknowledged and does not invalidate the partial results.
The exponential-pattern example is correct: independent strict comparisons between paired good prices produce $2^n$ distinct threshold vectors, with positive normalized prices available for every comparison choice. As the prover states, this limits that enumeration method; it supplies no hardness result.
Minimum actionable feedback: Retain the partial classification. Resolving USER_TASK requires either a general algorithm with a polynomial bound in $m,\tau,K,L$, or a hardness reduction with its search-reduction convention specified and proved. No merely expositional clarification would fill this remaining gap. No repairs to the subsidiary proofs are required.
⟨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.