Answer: —
Theorem 2 — class: algorithmic
Let \(H\) be a finite set of unit classes and let supported types \(t\) consist of a weak ranking over \(H\) and an endowed class \(e_t\), with rational masses \(\mu_t\). Set \(q_h=\sum_{t:e_t=h}\mu_t\). For an atomless population partitioned into these type cohorts, does there exist a uniform algorithm, polynomial in \(|H|\), \(\tau\), and the mass encoding length \(L\), that specifies a direct exchange rule with a measurable individual assignment \(\alpha(i)\in H\), represented compactly by its mass flows? Each individual must receive one whole unit, and each class must be assigned mass \(q_h\). The rule must be Pareto efficient and individually rational, select a core allocation whenever one exists, and admit no measurable positive-mass coalition whose members can all strictly improve by jointly misreporting or by reallocating their endowed units.
Let \(H\) be a nonempty finite set of unit classes, with \(m=|H|\). A society is given by its support: the list of \(\tau\) types \(t=(R_t,e_t)\) with positive binary-rational masses \(\mu_t\), where \(R_t\) is a complete, transitive weak ranking over \(H\), \(e_t\in H\), and \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Represent individuals by the Lebesgue probability space \(I=[0,1]\), partitioned into measurable cohorts \(I_t\) of masses \(\mu_t\). Each individual owns one whole unit of class \(e_t\); units within a class are interchangeable. Set \(q_h=\sum_{t:e_t=h}\mu_t\). Endowments are public and fixed; only rankings may be misreported, and there are no transfers.
An allocation is a measurable assignment \(\alpha:I\to H\) satisfying \(\lambda(\alpha^{-1}(h))=q_h\). Its flows are \(x_{th}=\lambda(I_t\cap\alpha^{-1}(h))\). A deterministic direct rule must specify these flows together with a fixed measurable realization convention using public individual labels, so individual outcomes remain identifiable across reports; labels cannot be reset after a deviation.
All welfare comparisons hold almost everywhere. Pareto improvement means weak improvement for almost everyone and strict improvement on a set of positive mass; individual rationality means receiving a class weakly preferred to one's endowment.
A coalition is any measurable \(C\subseteq I\) with \(\lambda(C)>0\), including a proper subset of a cohort. An endowed-unit reallocation \(\beta:C\to H\) must satisfy \(\lambda(C\cap\beta^{-1}(h))=\lambda(\{i\in C:e_i=h\})\) for every \(h\).
The weak core excludes such reallocations strictly improving almost every coalition member. The core excludes such reallocations weakly improving almost every member and strictly improving a positive-mass subset.
The rule must always be Pareto efficient, individually rational, weak-core selecting, and core selecting whenever the core is nonempty. It must also exclude every measurable coalition whose joint ranking misreports, leaving outsiders' reports fixed, strictly improve almost every member relative to truthful reporting under the same rule.
The rule is defined on all measurable ranking-report profiles, including profiles with irrational cohort masses; the computational bound concerns inputs with binary-rational support masses. Computational output consists of exact binary-rational flows and the specified realization convention.
Does a direct exchange rule satisfying all these requirements admit uniform evaluation in time polynomial in \(m\), \(\tau\), and \(L\), or is this rule-implementation problem \(\mathrm{NP}\)-hard?
For finite housing markets with weak rankings, polynomial-time rules simultaneously satisfy this property package. [Ahmad (2021)](https://orca.cardiff.ac.uk/id/eprint/157074/)
Continuum TTC has been defined for school choice with strict student preferences and school priorities; that model does not settle this endowed-unit problem with weak rankings and coalition requirements. [Leshno and Lo](https://www.columbia.edu/~iyl2104/Leshno%2CLo-SimpleTTC.pdf) No settlement of the exact problem above was located.
I interpret the question as asking whether there exists a uniformly polynomial-time rule satisfying the entire package.
The general question remains unresolved. The following results advance the incentive part of the problem:
The construction also specifies a unique flow selection for irrational masses, repairing the deterministic-selection gap identified in the verifier report.
Write $hP_tk$ for strict preference and $hI_tk$ for indifference. Ignore zero-supply classes: feasibility prevents their assignment on positive mass.
For a set $A$ of remaining positive-supply classes, the residual population is
$$
E_A=\{i\in I:e_i\in A\}.
$$
Its class supplies remain $q_h$ for $h\in A$. We do not renormalize its mass.
For every positive-mass type endowed in $A$, define
$$
T_t(A)=\{k\in A:kR_tg\text{ for every }g\in A\}.
$$
This set is nonempty because $A$ is finite and $R_t$ is complete and transitive.
Define the directed graph $D(A)$ on $A$ by including an edge
$$
e_t\longrightarrow k
$$
whenever $k\in T_t(A)$ and $\mu_t>0$. Every vertex has an outgoing edge, so $D(A)$ has a sink strongly connected component.
For a sink component $S$, consider the transportation system
$$
\begin{aligned}
y_{tk}&\geq 0,\\
\sum_{k\in S}y_{tk}&=\mu_t &&(e_t\in S),\\
\sum_{t:e_t\in S}y_{tk}&=q_k &&(k\in S),\\
y_{tk}&=0 &&(k\notin T_t(A)).
\end{aligned}
$$
Call $S$ feasible when this system has a solution.
Sink closure implies
$$
T_t(A)\subseteq S\qquad(e_t\in S).
$$
Thus a feasible component can allocate its own endowed supply so that every member receives a top class among all currently available classes.
Fix orders on classes and on all ranking–endowment types. For each feasible transportation system, select its lexicographically least flow vector, using a fixed order on its coordinates.
This selection exists and is unique, including for irrational masses: the feasible set is nonempty and compact, and successive coordinate minimizations leave nonempty compact sets, eventually fixing every coordinate.
Suppose a residual market on $A$ has a core allocation $\alpha$. If $S$ is a sink component of $D(A)$, then every individual endowed in $S$ receives a member of $T_t(A)$ almost everywhere.
Consequently, $S$ is feasible, its owners consume exactly its entire supply, and restricting $\alpha$ to $E_{A\setminus S}$ gives a core allocation of the remaining market.
Suppose instead that some type $t$ endowed in $S$ receives a class $h\notin T_t(A)$ on a positive-mass cell. Choose $k\in T_t(A)$. Then
$$
kP_th.
$$
Because $S$ is a sink, $k\in S$. Strong connectivity supplies a simple path from $k$ to $e_t$. Together with the edge $e_t\to k$, this produces a directed cycle; if $k=e_t$, use the loop.
Use the dissatisfied cell as the witness for the first edge. Every subsequent edge is witnessed by a positive-mass type whose top set contains that edge’s destination. Choose any positive allocation cell of that type. The destination is weakly preferred to the class received in that cell.
The source vertices of a simple cycle are distinct endowment classes. Hence the chosen witness cells are disjoint. Atomlessness permits selecting an equal positive mass $\varepsilon$ from each cell.
Give each selected subset the endowment class at the next cycle vertex. This balances the coalition’s endowed units class by class. All selected individuals weakly improve, and the first subset strictly improves. This contradicts core membership.
Thus all owners of $S$ receive top classes in $S$. Their total mass is
$$
\lambda(E_S)=\sum_{h\in S}q_h.
$$
They therefore exhaust the supply of $S$, and no outsider receives a class in $S$ on positive mass. Their allocation flows solve the transportation system.
The restriction to the remaining population is feasible. Any coalition blocking that restriction would also block $\alpha$, so the restriction belongs to the residual core. $\square$
Run the following procedure:
Crucially, an infeasible sink does not cause immediate termination when another feasible sink is available.
At most $m$ components are removed.
The original core is nonempty exactly when this procedure removes every class. Every allocation from a complete peeling run belongs to the core.
If a core allocation exists, Lemma 1 shows that every current sink component is feasible. It also shows that, after removing any selected component, the residual market still has a core allocation. Hence the procedure cannot stop before removing every class.
Conversely, suppose the procedure removes all classes, in the order
$$
S_1,\ldots,S_K.
$$
Let
$$
A_j=H_+\setminus\bigcup_{\ell<j}S_\ell,
$$
where $H_+$ is the set of positive-supply classes.
Suppose a coalition $C$ weakly improves through an endowed-unit reallocation $\beta$. Consider the first component represented in $C$ on positive mass. Earlier coalition endowments have zero mass, so coalition feasibility implies that $\beta$ assigns only classes available at that component’s removal.
Participating owners of $S_j$ already receive top classes in $A_j$. A weak improvement must give them another member of their top set, hence another class in $S_j$. They cannot strictly improve.
Their mass equals the coalition’s endowed supply from $S_j$. They exhaust that supply, so no remaining participant can receive a class in $S_j$. Remove these participants and repeat.
No positive-mass subset can strictly improve, contradicting core blocking. $\square$
In particular, if peeling stops with a nonempty residual market, that residual market has empty core.
If the core is nonempty, then for any two core allocations $\alpha$ and $\beta$,
$$
\alpha(i)I_i\beta(i)
$$
almost everywhere.
Apply Lemma 1 successively along a complete peeling run. Every individual endowed in $S_j$ must receive, under either allocation, a member of $T_t(A_j)$. All members of that set are indifferent for that individual. $\square$
This establishes uniqueness of welfare, rather than uniqueness of assigned classes or flows.
When peeling stops with a nonempty residual market, use the following fallback. Its incentive compatibility is not asserted.
Maintain residual type cohorts and their masses. Each positive residual type points to:
The resulting finite functional graph has a directed cycle. Choose one deterministically. If $\delta$ is the smallest residual mass on the cycle, select mass $\delta$ from each cycle cohort, give it the next cohort’s endowment class, and remove the selected individuals and their endowed units.
Each iteration exhausts at least one residual type. There are therefore at most $\tau$ iterations.
Every operation balances removed assignments and endowments class by class. Each selected individual receives a top available class; their own endowment class is available while they remain. The allocation $\alpha^0$ is consequently feasible and individually rational.
To verify weak-core membership, suppose a coalition strictly improves almost every member. Choose the earliest iteration whose selected individuals intersect the coalition in positive mass. Every positive-mass coalition endowment class was available at that iteration: earlier selected coalition members have zero mass. The selected participants already receive top available classes and therefore cannot strictly improve using coalition endowments. This is a contradiction.
Let
$$
B_{th}=I_t\cap(\alpha^0)^{-1}(h),
\qquad
x^0_{th}=\lambda(B_{th}).
$$
Choose integer utilities $u_t$ representing each ranking exactly, with values between $0$ and $m-1$.
Use variables $z_{thk}$ only for $kR_th$, subject to
$$
\begin{aligned}
z_{thk}&\geq 0,\\
\sum_k z_{thk}&=x^0_{th},\\
\sum_{t,h}z_{thk}&=q_k.
\end{aligned}
$$
Maximize
$$
\sum_{t,h,k}u_t(k)z_{thk},
$$
and choose the lexicographically least optimum.
Realize these variables by subdividing each actual cell $B_{th}$. The resulting allocation $\gamma$ weakly improves every individual relative to $\alpha^0$.
It remains individually rational. It also remains in the weak core: a coalition strictly improving upon $\gamma$ would, by transitivity, strictly improve upon $\alpha^0$.
For Pareto efficiency, suppose $\beta$ Pareto improves $\gamma$. It weakly improves $\alpha^0$ by transitivity, so its intersections with the cells $B_{th}$ define a feasible transportation solution. The utility integral increases strictly: every strict improvement raises the corresponding integer utility by at least one, and strict improvement occurs on positive mass. This contradicts optimality.
Thus the fallback satisfies feasibility, individual rationality, Pareto efficiency, and weak-core membership.
For any measurable set $B\subseteq I$, define
$$
F_B(s)=\lambda(B\cap[0,s]).
$$
This function is continuous, nondecreasing, and $1$-Lipschitz, with
$$
F_B(0)=0,\qquad F_B(1)=\lambda(B).
$$
Therefore, for every $z\in[0,\lambda(B)]$, a prefix cut selects exactly mass $z$. Choose the least cut point when $0<z<\lambda(B)$, and handle the two endpoints by selecting the empty set or all of $B$.
All cohort splitting uses this convention and the original public labels. Successive cuts realize the selected flow vectors. Changing a cohort by a null set changes its selected subsets only by null sets.
Define $F$ to be the rule that first peels every available feasible sink component and then, if necessary, applies the fallback to the terminal population.
The rule $F$ is individually rational, Pareto efficient, and weak-core selecting. It selects a core allocation whenever the core is nonempty.
Individual rationality follows from top assignments during peeling and from the fallback’s individual rationality.
For weak-core membership, a strictly blocking coalition intersecting a peeled component on positive mass has an earliest such component. Its participants there already receive top classes among all positive-mass coalition endowments and cannot strictly improve. A coalition lying entirely in the terminal population cannot block the fallback.
For Pareto efficiency, consider any putative Pareto improvement. Owners of the first peeled component receive top available classes, so weak improvement confines them to that component. Their mass exhausts its supply. No outsider can receive its classes, and these owners cannot strictly improve.
Remove them and repeat for each peeled component. The remaining allocation would Pareto improve the fallback, which is impossible.
If the core is nonempty, Lemma 2 gives a complete peeling run and proves core membership. $\square$
On rational inputs, choose a common denominator $D$ for the masses. Its binary length is $O(L)$: the product of the input denominators suffices. For dyadic inputs, take a common power of two.
There are at most $m$ peeling iterations and at most $m$ sink tests per iteration. Each feasibility test is a bipartite maximum-flow problem with $O(\tau+m)$ vertices and $O(\tau m)$ edges.
After scaling by $D$, transportation row and column totals are integers. The constraint matrix is totally unimodular: multiplying the column-sum rows by $-1$ turns it into a directed vertex–edge incidence matrix. Consequently, transportation vertices are integral after scaling.
Successive lexicographic optimization restricts to faces of the original transportation polytope. The final unique point is a vertex, so every selected flow is an integer multiple of $1/D$.
The fallback uses at most $\tau$ cycle operations and a transportation optimization with $O(\tau m^2)$ variables. Its row totals remain multiples of $1/D$. The same integrality argument applies.
Using polynomial-time rational linear programming, the objective optimization and polynomially many coordinate minimizations take time polynomial in $m$, $\tau$, and $L$. All returned flows have polynomial-length exact rational representations.
For arbitrary measurable report profiles, including irrational masses, there are still only finitely many positive ranking–endowment types. All operations remain defined through finite graphs, compact transportation sets, and measurable prefix cuts. No computational bound is claimed for irrational inputs.
The next lemma is the new ingredient needed for incentives.
Fix a report profile and residual market.
Here a sequence is maximal when it continues until no feasible sink remains.
Distinct sink strongly connected components are disjoint.
Suppose $S$ is available and another sink component $B$ is removed. For every type endowed in $S$,
$$
T_t(A)\subseteq S.
$$
Removing $B$ therefore leaves its top set unchanged:
$$
T_t(A\setminus B)=T_t(A).
$$
Hence the graph within $S$, its sink property, and its transportation system are unchanged. This proves persistence.
Each removal deletes at least one class. A maximal sequence cannot terminate while $S$ remains feasible, so it must eventually remove $S$.
If $S$ and $B$ are simultaneously available, removing either leaves the other’s transportation system unchanged. Their lexicographically selected flows are therefore unchanged. They act on disjoint endowed populations, so their fixed-label realizations also commute.
Finally, compare two maximal sequences. The first component of the first sequence is initially available in the second sequence. By persistence, the second sequence eventually removes it. Commuting it past preceding removals moves it to the front without changing assignments or the final residual market.
The two sequences now have the same first removal. Repeat on the remaining market. This induction proves the last assertion. $\square$
Although the implemented rule can use a fixed component order, its outcome does not depend on that order.
At a truthful profile, suppose $F$ peels components
$$
S_1,\ldots,S_K
$$
and leaves the terminal class set
$$
A_*=H_+\setminus\bigcup_{j=1}^KS_j.
$$
If a measurable coalition strictly improves almost every member through joint ranking misreports, then
$$
\lambda(C\setminus E_{A_*})=0.
$$
Moreover, its deviation can be analyzed entirely within the terminal population, using the same original labels and the same residual version of $F$.
First suppose the coalition intersects a peeled population on positive mass. Let $r$ be the least index with
$$
\lambda(C\cap E_{S_r})>0.
$$
For every $j<r$, coalition membership in $E_{S_j}$ has zero mass. Rankings of owners of those classes therefore remain unchanged almost everywhere.
At the deviating profile, $S_1$ is still a feasible sink component: its outgoing edges depend only on its owners’ unchanged rankings, its top sets remain inside $S_1$, and its transportation system is unchanged.
By Lemma 5, the deviating peeling sequence removes $S_1$, and that removal can be moved to the beginning without changing its outcome.
After removing $S_1$, the same argument applies to $S_2$. Continuing, the deviating sequence can be reordered to begin with
$$
S_1,\ldots,S_{r-1}.
$$
Each of these components consumes only its own supply.
Consequently, almost every individual outside those populations receives, after deviation, a class in
$$
A_r=H_+\setminus\bigcup_{j<r}S_j.
$$
This includes almost every coalition member.
But truthful participants in $E_{S_r}$ receive top classes in $A_r$. Their deviating assignments therefore cannot be strictly better. Since their intersection with $C$ has positive mass, the deviation cannot strictly improve almost every coalition member. This is a contradiction.
Thus the coalition must lie almost entirely in the terminal population.
In that case all truthful peeled populations have unchanged reports almost everywhere. The same commutation argument moves all their removals to the beginning of the deviating sequence. The remaining population, supplies, and public labels are exactly those of the truthful terminal market.
Lemma 5 makes the rest of the peeling outcome independent of removal order. The fallback depends only on the resulting residual profile and its existing labels. Therefore the residual outcome is exactly the outcome obtained by running the same construction on that terminal population. $\square$
If the truthful core is nonempty, no measurable coalition can strictly improve almost every member by joint ranking misreports under $F$.
Lemma 2 gives $A_*=\varnothing$. Theorem 6 would confine any profitable coalition to a null population, contrary to its required positive mass. $\square$
The deviating profile may have empty core. No assumption on its core is used.
For any rule selecting core allocations, a coalition cannot strictly improve almost every member when both the truthful and deviating profiles have nonempty cores.
Take a complete truthful peeling sequence and the first component meeting the coalition on positive mass.
For each preceding component, reports of its owners are unchanged almost everywhere. Lemma 1, applied successively to the deviating core allocation, forces those owners to consume their component’s supply. Thus coalition members cannot receive any earlier component’s classes.
The coalition’s participants in the first represented truthful component already receive top classes among the remaining classes. They cannot strictly improve. $\square$
The following example explains why handling deviations to empty-core profiles requires an additional argument.
Let
$$
H=\{a,b,c,d\}.
$$
There are four cohorts:
| Cohort | Mass | Endowment | Truthful ranking |
|---|---:|---|---|
| $U$ | $6/16$ | $a$ | $b\succ c\succ a\succ d$ |
| $V$ | $6/16$ | $b$ | $a\sim b\succ c\succ d$ |
| $W$ | $3/16$ | $c$ | $b\succ c\succ d\succ a$ |
| $Z$ | $1/16$ | $d$ | $c\succ d\succ a\succ b$ |
Initially, $\{a,b\}$ is a sink component. Its transportation system is feasible and forces
$$
U\longmapsto b,\qquad V\longmapsto a.
$$
After removing it, the available classes are $\{c,d\}$. Cohort $W$ ranks $c$ first, making $\{c\}$ a feasible sink. Finally, $Z$ receives $d$.
Thus
$$
\alpha(U)=b,\quad
\alpha(V)=a,\quad
\alpha(W)=c,\quad
\alpha(Z)=d
$$
belongs to the core by Lemma 2.
Let the coalition be all of $W$, and let it report
$$
b\succ d\succ c\succ a.
$$
The component $\{a,b\}$ is unchanged and remains forced in any putative core allocation.
After its removal, owners of $c$ demand $d$, while owners of $d$ demand $c$. The residual top graph is the strongly connected cycle
$$
c\longrightarrow d\longrightarrow c.
$$
Its transportation system would have to give class $d$ to all $3/16$ owners of $c$, although only $1/16$ of $d$ exists. It is infeasible. Lemma 1 therefore proves that the deviating profile has empty core.
At the deviating profile, consider $\gamma$ with flows
$$
\begin{aligned}
x_{Ub}&=3/16,&x_{Uc}&=3/16,\\
x_{Va}&=6/16,\\
x_{Wb}&=3/16,\\
x_{Zd}&=1/16.
\end{aligned}
$$
These flows preserve every class supply. They are individually rational under the reported rankings.
They also belong to the weak core. The only individuals capable of strict improvement are the members of $U$ receiving $c$ and the members of $Z$ receiving $d$. The former need $b$; the latter need $c$. A coalition consisting almost everywhere of such individuals owns only $a$ and $d$, so it cannot strictly improve almost every member.
For Pareto efficiency:
Hence no Pareto improvement exists.
Nevertheless, every member of $W$ receives $b$ under $\gamma$, strictly better in its true ranking than its truthful core assignment $c$.
This demonstrates that welfare compliance at the two profiles does not itself exclude the profitable misreport. The peeling rule $F$ prevents this particular outcome by assigning $\{a,b\}$ to their owners before using any fallback.
The construction has polynomial evaluation and all the required welfare properties. Its incentive proof covers every truthful profile with nonempty core and, more generally, confines any profitable coalition to its terminal residual market.
What remains is to prove the incentive requirement at truthful markets in which every sink component has an infeasible top-assignment transportation system, allowing deviations that may create feasible components.
These residual markets are substantive. For example, take three classes with supplies
$$
q_a=\frac12,\qquad q_b=q_c=\frac14,
$$
and homogeneous rankings within each endowment class whose top choices are
$$
a\longrightarrow b,\qquad
b\longrightarrow c,\qquad
c\longrightarrow a.
$$
The entire top graph is one sink component, and its transportation system is infeasible because owners of $a$ require mass $1/2$ of class $b$, whose supply is only $1/4$. No peeling occurs.
The finite-market theorem cited in the question supplies polynomial rules with the full finite-agent property package. [Ahmad’s Theorem 2](https://orca.cardiff.ac.uk/id/eprint/157074/1/Revised%20Draft%202.pdf) does not by itself provide the needed compressed implementation or fixed-label measurable-coalition proof for these residual markets.
No general incentive theorem for the fallback, hardness reduction, or impossibility proof has been established here. Therefore the requested polynomial-time-versus-$\mathrm{NP}$-hard classification remains open in this write-up.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial partial results, but it does not resolve the polynomial-time-versus-$\mathrm{NP}$-hard question in USER_TASK. Its own declaration that the general question remains unresolved is accurate.
The core characterization, welfare construction, and coalition-localization argument withstand scrutiny. The central outstanding requirement is incentive compatibility at truthful profiles with a nonempty terminal population. Polynomial evaluation of the proposed welfare rule does not establish polynomial implementation of a rule satisfying the entire package.
The definitions are consistent with the endowed-unit model.
Restricting the population to individuals endowed in $A$ preserves the supplies $q_h$ for $h\in A$ without renormalization. Ignoring zero-supply classes is legitimate for almost-everywhere comparisons and assignments.
Each vertex of $D(A)$ has an outgoing edge: a positive-supply class has a positive-mass endowed type, and that type has a nonempty top set. A finite directed graph with this property has a sink strongly connected component.
For a sink component $S$, the claimed containment
$$
T_t(A)\subseteq S
$$
for types endowed in $S$ follows directly from the graph’s edge definition and sink closure.
The transportation constraints express precisely the proposed internal top-class assignment. The feasible set is bounded by its row totals and closed. Successive coordinate minimizations therefore give a unique lexicographic minimum, including for irrational masses. No rationality assumption is needed for this existence argument.
Assessment: Correct.
The blocking argument is valid under the task’s definition of the core.
The loop case is also valid: the selected individuals can reclaim their own endowed class, which they strictly prefer to their current assignment.
The supply-exhaustion conclusion follows because all owners of $S$ consume classes in $S$, and their total mass equals its total supply. Restriction to the remaining population is consequently feasible, and any residual core blocker would also block the original allocation.
Assessment: Correct. This argument excludes weakly improving coalitions with a positive-mass strict improvement, as required for the core; it does not confuse this with weak-core blocking.
The forward direction of Lemma 2 correctly applies Lemma 1 after every removal. An existing residual core makes every current sink component feasible, so the procedure cannot terminate prematurely.
The converse correctly accounts for coalitions that include proper subsets of cohorts. At the first represented component, earlier coalition endowments have zero mass. Coalition feasibility therefore excludes earlier classes from its reallocation almost everywhere. Weak improvement confines participating owners of that component to its top sets, which lie within the component. Their consumption exhausts the coalition’s endowed supply from that component. Iterating this argument excludes a positive-mass strictly improving subset.
Because there are finitely many removed components, the iteration covers the coalition up to null sets.
Corollary 3 then follows: both core allocations assign each individual a class in the same residual top indifference class. It establishes individual welfare equivalence almost everywhere, without claiming uniqueness of flows or assigned classes.
Assessment: Correct.
The finite functional graph has a cycle, and each cycle operation removes at least one positive residual type. Thus the claimed bound of at most $\tau$ operations is valid.
Equal-mass cycle exchanges preserve supply even if distinct cycle types share an endowment class: the multiset of source endowments equals the multiset of assigned endowments.
Individual rationality follows because a remaining individual’s endowment class is still available. The earliest-iteration argument for weak-core membership is valid for arbitrary measurable coalitions, including fractions of selected cohorts.
The optimization is feasible because the initial allocation itself satisfies its constraints. Its variables record subdivisions of actual initial allocation cells, so the construction preserves individual weak improvement rather than merely improving aggregate type welfare.
The claims of individual rationality and weak-core preservation follow by transitivity. The Pareto-efficiency argument also holds: a purported Pareto improvement supplies a feasible solution to the stated optimization, and exact integer utilities yield a strictly larger integral when strict improvement occurs on positive mass.
Assessment: The welfare argument is correct. Incentive compatibility of this fallback is neither proved nor claimed.
Minor specification issue: The fallback says to choose a cycle deterministically and to choose integer utilities representing each ranking, but does not specify those choices. Different admissible utility representations can affect the selected allocation. To specify one actual direct rule, the write-up should fix these choices and their dependence on residual data.
The assertions about $F_B$ are correct. Its continuity and endpoint values ensure the required cuts exist. For an interior target mass, the set of cut points attaining that mass is nonempty and compact, so its least point exists.
Successive prefix cuts give measurable subdivisions. The convention uses the original public labels. Its null-set invariance is also correct: null changes to $B$ preserve its cumulative measure function and alter the selected subsets only by null sets.
The computational claim concerns flows and a specified symbolic realization convention. The argument does not establish polynomial computation of prefix-cut locations for arbitrary measurable cohorts, but USER_TASK does not require such locations as numerical output.
A minor total-definition omission remains: the construction ignores zero-mass types and exceptional null sets without specifying their assigned classes. Almost-everywhere properties survive this omission, but a literal map $\alpha:I\to H$ needs a convention on those individuals.
Assessment: Correct modulo this minor total-definition clarification.
The argument correctly combines peeled assignments with the fallback.
For weak-core selection, an earliest represented peeled component prevents strict improvement almost everywhere. A coalition entirely in the terminal population is excluded by the fallback’s weak-core property.
For Pareto efficiency, the successive supply-exhaustion argument confines any remaining improvement to the terminal population, contradicting fallback optimality. When peeling is complete, no positive-mass strict improvement remains possible.
Core selection on nonempty-core profiles follows from Lemma 2.
Assessment: Correct.
The arithmetic and size bounds are sound.
The nonnegative variables have finite row bounds, so the relevant optimization problems are bounded. Their rational coefficients and right-hand sides have polynomial encoding length. Polynomial-time rational linear programming therefore supports the claimed evaluation bound.
The final flows have denominator dividing $D$; for dyadic input masses, they are dyadic as well.
Assessment: Correct for the welfare rule constructed. It does not establish polynomial evaluation of a rule satisfying the unproved incentive requirement.
Persistence is valid. Removing a disjoint sink component does not remove any top class of an owner of $S$, so its top sets and internal graph remain unchanged. Its sink property prevents it from merging with outside vertices into a larger strongly connected component.
A maximal sequence must eventually remove a persistent feasible component, since it cannot terminate while that component remains available.
The simultaneous-removal claim is valid: the systems are unchanged, and the label realizations act on disjoint endowed populations.
The comparison of maximal sequences is also justified. While moving a persistent component past earlier removals, each adjacent swap concerns two components simultaneously available at that stage. Thus the preceding commutation claim applies.
Assessment: Correct.
The localization proof is valid.
Before the first truthful peeled population represented in the coalition, owner reports are unchanged almost everywhere. Each corresponding component therefore remains available and feasible after the earlier components have been removed. Lemma 5 permits placing these removals first in the deviating execution.
Their supplies are exhausted internally. Consequently, coalition members cannot obtain their classes on positive mass. Coalition members in the first represented truthful component already receive top classes among the remaining classes and cannot strictly improve.
This establishes the stated confinement to the terminal population. The residual-analysis assertion is valid under the intended reading that the fallback’s fixed choices depend only on residual data and inherited public labels; that dependence should be made explicit in the deterministic-choice clarification.
Corollary 7 follows when the terminal population is null. Corollary 8 correctly uses forced assignments in the deviating core instead of relying on the particular rule.
Assessment: Correct. The proof covers deviations from nonempty-core truthful profiles even when the deviating core is empty.
The example’s calculations are correct.
The truthful component $\{a,b\}$ forces the stated assignments because $U$ consumes all available $b$. The subsequent assignments to $W$ and $Z$ follow.
Under the misreport, the residual cycle requires $3/16$ of $d$ while only $1/16$ exists. The infeasibility and empty-core conclusion follow from the proved lemmas.
The proposed allocation preserves supplies:
$$
(q_a,q_b,q_c,q_d)=(6/16,6/16,3/16,1/16).
$$
Its individual-rationality, weak-core, and Pareto-efficiency arguments are valid under the reported rankings. All members of $W$ strictly prefer their resulting $b$ to their truthful assignment $c$.
The example demonstrates that the welfare properties at the two profiles alone do not exclude this profitable deviation. It does not demonstrate a manipulation of $F$, and the output correctly distinguishes these claims.
Assessment: Correct.
The description of [Ahmad’s Theorem 2](https://orca.cardiff.ac.uk/id/eprint/157074/1/Revised%20Draft%202.pdf) is accurate for finite housing markets. The output does not apply that theorem to the continuum construction. Its warning that the finite result alone supplies neither compressed evaluation nor the required measurable-coalition argument is justified.
The final three-class example correctly exhibits an infeasible sink transportation system.
Major outstanding issue: The proposed rule lacks the required incentive proof for truthful terminal markets. Theorem 6 localizes possible profitable deviations there but does not exclude them. No hardness reduction or impossibility proof supplies the alternative requested conclusion.
This is an acknowledged limitation rather than a false claim of completion.
USER_TASK.⟨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.