Answer: —
Theorem 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe set PIR of individually rational Pareto optima is a polytope, hence the convex hull of its finitely many extreme points.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite state space \(S\) with rational probabilities, risks \(k\), types \(t\) with rational masses \(\mu_t>0\) summing to one, and nonnegative rational per-capita endowments \(e_t^k(s)\), determine the exact set of individually rational Pareto-optimal type-homogeneous allocations \(x_t^k(s)\geq 0\). Require \(\sum_t \mu_t x_t^k(s)=\sum_t \mu_t e_t^k(s)\) for each risk and state, and require \(x_t^k\succeq_{SSD}e_t^k\) for every type and risk; Pareto comparisons range over feasible type-homogeneous allocations, with strict improvement for at least one positive-mass type on at least one risk. Represent the resulting set by its extreme points and their convex hull.
Let \(S\) have \(m\geq1\) states with positive binary-rational probabilities \(p_s\) summing to one, and let there be \(r\geq1\) risks.
A society is given by its support: the list of the \(\tau\geq1\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Each type has nonnegative binary-rational per-capita endowments \(e_t^k(s)\); let \(L\) be the total input bit length.
A type-homogeneous allocation assigns a real per-capita amount \(x_t^k(s)\geq0\) to every member of type \(t\), with \(\sum_t\mu_t x_t^k(s)=\sum_t\mu_t e_t^k(s)\) for every risk \(k\) and state \(s\).
Use increasing-concave second-order stochastic dominance under the common state law. Strict dominance means weak dominance without reverse dominance. An allocation is individually rational when \(x_t^k\succeq_{SSD}e_t^k\) for every type and risk.
An allocation is Pareto optimal when no feasible type-homogeneous allocation \(y\) satisfies \(y_t^k\succeq_{SSD}x_t^k\) for every type and risk, with strict dominance for at least one pair. Let \(A\) be the set of individually rational Pareto-optimal allocations.
Can \(A\) be represented exactly by enumerating all its extreme points and taking their convex hull in total time polynomial in \(m,\tau,r,L,B\), where \(B\) is the total binary length of the vertex list, or would such an algorithm imply \(\mathrm{P}=\mathrm{NP}\)?
For finite lists of agents with rational state probabilities, the individually rational Pareto-optimal set is a nonempty polytope, hence the convex hull of finitely many extreme points; vertex enumeration is proposed without a polynomial-time bound. [Chateauneuf, Mostoufi and Vyncke](https://faculty-research.ipag.edu/wp-content/uploads/recherche/WP/IPAG_WP_2014_074.pdf).
The same structural result appears in a [later author version](https://theses.fr/2015PA010044/abes). No result settling the exact mass-version enumeration complexity was located.
The unrestricted complexity question remains unresolved here. I prove a stronger tractable case than the two-state result in the notes: output-polynomial enumeration is possible when either the support size or the number of distinct aggregate endowment levels is fixed.
For each risk, let
$$
d_k=\left|\left\{\sum_t\mu_t e_t^k(s):s\in S\right\}\right|,
\qquad D=\max_k d_k.
$$
The following bound holds for an exact enumeration algorithm:
$$
\operatorname{poly}(m,\tau,r,L)\,
(B+1)^{6\min\{\tau,D-1\}+4}.
$$
The polynomial factor has a fixed degree independent of $\tau$ and $D$. Thus the algorithm is output-polynomial for fixed $\tau$, or for fixed $D$, and in particular for fixed $m$. Its exponent does not settle the requested bound when both $\tau$ and $D$ vary.
The proof has two main ingredients:
$$ \min\{3\tau+1,\,2(d_k-1)\}. $$
I first establish the structural facts needed for these assertions directly in the support-and-mass model.
For a vector $Z=(Z_s)_{s\in S}$, define
$$
Q_Z(q)=
\min\left\{
\sum_s a_sZ_s:
0\leq a_s\leq p_s,\quad
\sum_s a_s=q
\right\},
\qquad 0\leq q\leq1.
$$
The minimum selects outcomes in increasing order, splitting the probability of the last selected state if necessary. Consequently, $Q_Z$ is continuous, piecewise linear, and convex, with
$$
Q_Z(0)=0,\qquad Q_Z(1)=\mathbb EZ.
$$
Under the increasing-concave convention,
$$
Z\succeq_{SSD}W
\quad\Longleftrightarrow\quad
Q_Z(q)\geq Q_W(q)
\quad\text{for every }q\in[0,1].
$$
To justify this characterization, put
$$
\phi_Z(h)=\mathbb E\min(Z,h).
$$
Selecting probability below a threshold gives the identities
$$
Q_Z(q)=
\sup_{h\in\mathbb R}
\bigl(\phi_Z(h)-(1-q)h\bigr),
$$
$$
\phi_Z(h)=
\inf_{q\in[0,1]}
\bigl(Q_Z(q)+(1-q)h\bigr).
$$
For the first identity, every admissible selection $a$ satisfies
$$
\sum_s a_sZ_s\geq
\phi_Z(h)-(1-q)h.
$$
Equality is obtained by choosing $h$ at the selection cutoff. For the second identity, the same inequality supplies one direction, and selecting exactly the probability strictly below $h$ supplies equality.
Thus comparison of all $Q$-values is equivalent to comparison of all $\phi$-values. Each function $z\mapsto\min(z,h)$ is increasing and concave, so increasing-concave dominance implies the latter comparison.
Conversely, interpolate any increasing concave utility on the finite union of the outcomes of $Z$ and $W$. On the relevant interval, its piecewise-linear interpolation is a constant plus a nonnegative multiple of $z$ and nonnegative multiples of functions $\min(z,h)$. Indeed, its final slope is nonnegative, and each downward change in slope supplies a nonnegative coefficient. Comparison of $\phi$-values, including expectations obtained by taking $h$ above all outcomes, therefore proves comparison for every such utility.
It follows that strict dominance is equivalent to weak quantile comparison with a strict inequality somewhere.
Two further facts will be used:
$$
Q_{cZ}(q)=cQ_Z(q)\qquad(c>0),
$$
and
$$
Q_{\sum_t c_tZ_t}(q)\geq
\sum_t c_tQ_{Z_t}(q)\qquad(c_t>0).
$$
The second inequality follows by minimizing a sum over the common selection set. Equality holds if every $Z_t$ is nondecreasing in one common state ordering, because one selection minimizes every summand.
Feasibility and dominance separate across risks. An allocation is Pareto optimal precisely when each risk component is Pareto optimal: an improvement of one component extends to an improvement of the entire allocation by retaining all other components, and any improvement of the entire allocation strictly improves some component.
Consider one risk, and write
$$
w(s)=\sum_t\mu_te_t(s),\qquad
z_t(s)=\mu_tx_t(s).
$$
Feasibility becomes
$$
\sum_tz_t(s)=w(s).
$$
Positive scaling preserves both weak and strict SSD, so this is a bijective reformulation of the mass model.
Call an allocation comonotone if
$$
(z_i(a)-z_i(b))(z_j(a)-z_j(b))\geq0
$$
for every pair of types and states.
Suppose comonotonicity fails. Choose types and states with
$$
z_i(a)>z_i(b),\qquad z_j(a)<z_j(b).
$$
Put $\lambda=p_a/p_b$ and choose
$$
0<\delta<
\frac{\min\{z_i(a)-z_i(b),\,z_j(b)-z_j(a)\}}{1+\lambda}.
$$
Replace the four entries by
$$
z'_i(a)=z_i(a)-\delta,\qquad
z'_i(b)=z_i(b)+\lambda\delta,
$$
$$
z'_j(a)=z_j(a)+\delta,\qquad
z'_j(b)=z_j(b)-\lambda\delta.
$$
This preserves statewise totals and each type’s expectation. For type $i$, the modified two-state vector equals
$$
(1-\theta_i)(z_i(a),z_i(b))+\theta_i(c_i,c_i),
$$
where
$$
c_i=\frac{p_az_i(a)+p_bz_i(b)}{p_a+p_b},
\qquad
\theta_i=
\frac{(1+\lambda)\delta}{z_i(a)-z_i(b)}
\in(0,1).
$$
For type $j$, the same representation holds with its conditional mean and
$$
\theta_j=
\frac{(1+\lambda)\delta}{z_j(b)-z_j(a)}
\in(0,1).
$$
Both modified pairs remain between their original endpoints, hence remain nonnegative. Concavity, followed by Jensen’s inequality at the conditional mean, proves weak improvement for every increasing concave utility. The improvement is strict for the strictly increasing, strictly concave utility $u(v)=-e^{-v}$. Thus both types strictly improve in SSD, disproving Pareto optimality.
For the converse, order states by increasing $w$. A comonotone allocation must be nondecreasing in this ordering. Otherwise, if $w(a)\leq w(b)$ but $z_i(a)>z_i(b)$, comonotonicity forces
$$
z_j(a)\geq z_j(b)
$$
for every other type, making the aggregate decrease strictly—a contradiction.
All types therefore have a common ordering, so
$$
Q_w(q)=\sum_tQ_{z_t}(q).
$$
If a feasible allocation $v$ dominates every $z_t$ and strictly dominates one, some $q_0$ satisfies
$$
Q_w(q_0)
\geq\sum_tQ_{v_t}(q_0)
>\sum_tQ_{z_t}(q_0)
=Q_w(q_0),
$$
a contradiction. This proves the proposition.
Moreover, when two states have equal aggregate endowments, every type receives equal allocations in those states: all typewise differences have the same weak sign and their sum is zero.
Let $C$ be the feasible individually rational set in the $z$-variables. It contains the scaled endowment allocation. Feasibility gives
$$
0\leq z_t(s)\leq w(s).
$$
The SSD threshold characterization makes $C$ closed, so $C$ is compact.
Minimize
$$
F(z)=\sum_t\mathbb E[z_t^2]
$$
over $C$. A crossing would permit the contraction constructed above, preserving individual rationality by transitivity of SSD. For each modified type, its conditional mean stays fixed and its conditional variance is multiplied by $(1-\theta_t)^2<1$. Hence $F$ strictly decreases, contradicting minimality.
The minimizer is comonotone and therefore Pareto optimal. Applying this argument independently to all risks proves
$$
A\neq\varnothing.
$$
Finally, every feasible individually rational allocation preserves each type’s expectation. SSD gives
$$
\mathbb Ex_t^k\geq\mathbb Ee_t^k.
$$
Feasibility implies
$$
\sum_t\mu_t
\bigl(\mathbb Ex_t^k-\mathbb Ee_t^k\bigr)=0.
$$
Every summand is nonnegative and every mass is positive; therefore
$$
\mathbb Ex_t^k=\mathbb Ee_t^k
\qquad\text{for every }t,k.
$$
Fix one risk. Let its distinct aggregate endowment levels be
$$
w_1<\cdots<w_d.
$$
Combine states having the same aggregate level, and define
$$
\pi_j=\sum_{\{s:w(s)=w_j\}}p_s,
\qquad
q_j=\sum_{\ell=1}^j\pi_\ell,
\qquad q_0=0.
$$
All $\pi_j$ are positive. Pareto-optimal allocations are constant within each combined group and nondecreasing across groups. Denote their compressed outcomes by $x_{tj}$.
Set
$$
h_t=\mathbb Ee_t,\qquad
c_{tj}=Q_{e_t}(q_j),
$$
and
$$
H_{tj}=\sum_{\ell=1}^j\pi_\ell x_{t\ell}.
$$
The endpoint values are
$$
H_{t0}=c_{t0}=0,\qquad H_{td}=c_{td}=h_t.
$$
For an aggregate-ordered allocation,
$$
x_t\succeq_{SSD}e_t
\quad\Longleftrightarrow\quad
H_{tj}\geq c_{tj}
\quad\text{for }j=1,\ldots,d-1.
$$
Necessity follows from quantile dominance at $q_j$.
For sufficiency, take $q\in[q_{j-1},q_j]$ and write
$$
\theta=\frac{q-q_{j-1}}{q_j-q_{j-1}}.
$$
The allocation’s integrated quantile is linear on this interval, whereas $Q_{e_t}$ is convex. Hence
$$
Q_{x_t}(q)
=(1-\theta)H_{t,j-1}+\theta H_{tj}
$$
$$
\geq
(1-\theta)c_{t,j-1}+\theta c_{tj}
\geq Q_{e_t}(q).
$$
The endpoint comparisons hold by the prescribed values at $0$ and $1$. This proves the lemma.
In particular, the endowment-specific knots used in the notes can be omitted.
Define
$$
W_j=\sum_{\ell=1}^j\pi_\ell w_\ell.
$$
The exact one-risk polytope is described by
$$
H_{tj}\geq c_{tj}
\qquad(1\leq j<d),
$$
$$
\frac{H_{t,j+1}-H_{tj}}{\pi_{j+1}}
-
\frac{H_{tj}-H_{t,j-1}}{\pi_j}
\geq0
\qquad(1\leq j<d),
$$
$$
\sum_t\mu_tH_{tj}=W_j
\qquad(1\leq j<d),
$$
together with the fixed endpoint values.
Indeed, recover outcomes by
$$
x_{tj}=\frac{H_{tj}-H_{t,j-1}}{\pi_j}.
$$
The second family makes these outcomes nondecreasing. The first outcome is nonnegative because
$$
H_{t1}\geq c_{t1}\geq0,
$$
so every outcome is nonnegative. Differencing the aggregate equations gives statewise feasibility. The final aggregate equation follows from
$$
\sum_t\mu_th_t=W_d.
$$
Conversely, every individually rational Pareto-optimal allocation satisfies all these constraints by Section 2 and the lemma. For $d=1$, the unique allocation is $x_{t1}=h_t$.
All constants are computable exactly in polynomial time: sort each endowment’s outcomes, evaluate its integrated quantile at the rational $q_j$, and perform rational arithmetic. No expansion of masses into lists of agents occurs.
This proves that $A$ is a nonempty rational polytope with a polynomial-size description.
Its vertices also have polynomial binary encoding length. At a vertex, the equality rows and active inequality rows span the ambient coordinate space; otherwise, a nonzero vector annihilating them would permit small feasible perturbations in both directions. A full-rank subsystem therefore determines the vertex. Clearing rational denominators and applying Cramer’s rule gives coordinates whose numerator and denominator lengths are polynomially bounded: a determinant of an $N$-dimensional integer matrix with entries of binary length at most $H$ has binary length at most
$$
O(NH+N\log N).
$$
Assume $d\geq2$ and put $n=d-1$. Introduce nonnegative variables
$$
u_{tj}=H_{tj}-c_{tj},
\qquad
v_{tj}=
\frac{H_{t,j+1}-H_{tj}}{\pi_{j+1}}
-
\frac{H_{tj}-H_{t,j-1}}{\pi_j}
$$
for $1\leq j\leq n$.
Set $u_{t0}=u_{td}=0$, and define
$$
g_{tj}=
\frac{c_{t,j+1}-c_{tj}}{\pi_{j+1}}
-
\frac{c_{tj}-c_{t,j-1}}{\pi_j},
$$
$$
b_j=W_j-\sum_t\mu_tc_{tj}.
$$
Convexity of $Q_{e_t}$ gives $g_{tj}\geq0$.
The constraints become
$$
\frac{u_{t,j-1}}{\pi_j}
-
\left(\frac1{\pi_j}+\frac1{\pi_{j+1}}\right)u_{tj}
+
\frac{u_{t,j+1}}{\pi_{j+1}}
-v_{tj}
=-g_{tj},
$$
$$
\sum_t\mu_tu_{tj}=b_j,
\qquad u_{tj}\geq0,\quad v_{tj}\geq0.
$$
Write this polytope as
$$
\mathcal P=\{z:Mz=a,\ z\geq0\},
$$
where $z$ comprises the $u$- and $v$-variables.
The transformation is an affine bijection: $H=c+u$, and $v$ is uniquely determined by $H$. It therefore preserves vertices.
Importantly, $\mathcal P$ is bounded. A convex $H$ with endpoints $0$ and $h_t$ satisfies
$$
c_{tj}\leq H_{tj}\leq q_jh_t.
$$
Thus $u$ is bounded, and $v$ is bounded because it is a fixed linear expression in $H$. Section 2 supplies nonemptiness.
For a subset $K$ of the columns of $M$, define
$$
\lambda(K)=
\operatorname{rank}(M_K)
+\operatorname{rank}(M_{\overline K})
-\operatorname{rank}(M).
$$
Equivalently,
$$
\lambda(K)=
\dim\bigl(
\operatorname{span}(M_K)
\cap
\operatorname{span}(M_{\overline K})
\bigr).
$$
A rooted binary column decomposition assigns columns to leaves. Its width is the maximum $\lambda(K)$ over column sets below its nodes.
We use the following elementary bound. If only $h$ rows contain nonzero entries on both sides of a column partition, then
$$
\lambda(K)\leq h.
$$
Indeed, every vector in the intersection of the two column spans is supported on those shared rows.
Call the local equation for $(t,j)$ row $R_{tj}$, and the aggregate equation for $j$ row $C_j$. A column $u_{tj}$ occurs only in
$$
R_{t,j-1},\ R_{tj},\ R_{t,j+1},\ C_j,
$$
with nonexistent endpoint rows omitted. A column $v_{tj}$ occurs only in $R_{tj}$.
Order columns in layers $j=1,\ldots,n$, placing all columns $u_{tj},v_{tj}$ of one layer consecutively.
Consider a prefix cut partway through layer $j$. A shared local row must have index
$$
j-1,\quad j,\quad\text{or }j+1.
$$
There are at most $3\tau$ such rows. Only aggregate row $C_j$ can be shared. Therefore every prefix cut satisfies
$$
\lambda(K)\leq3\tau+1.
$$
Construct a binary decomposition by repeatedly splitting the final column from the remaining prefix. Every non-leaf proper node is a prefix, and a singleton cut has $\lambda\leq1$. This gives width at most $3\tau+1$.
Instead, place all columns of each type consecutively.
At a prefix cut partway through one type, shared local rows belong only to that type, contributing at most $n$ rows. There are at most $n$ shared aggregate rows. Hence
$$
\lambda(K)\leq2n.
$$
The same prefix decomposition gives width at most $2n$. Choosing the better ordering yields a constructible decomposition of width
$$
k\leq\min\{3\tau+1,\,2(d-1)\}.
$$
These arguments allow redundant equations, zero constants, and degenerate polytopes.
The bounded-branch-width enumeration theorem of Reimers and Stougie applies to rational, bounded standard-form polytopes supplied with a column decomposition of bounded width. Its support-merging algorithm enumerates all vertices in total polynomial time for fixed width. A conservative version of its quantitative bound is
$$
\operatorname{poly}(\operatorname{size}(M,a))\,
(V+1)^{2k+2},
$$
where $V$ is the number of vertices. The polynomial work includes rational linear-programming and rank tests. See their [Theorems 5–6](https://arxiv.org/pdf/1404.5584).
All hypotheses have been verified here:
If preprocessing removes constant coordinates, the width bound persists. For any remaining column partition, the two new column spans are subspaces of the corresponding old spans, so their intersection dimension cannot increase. Removing constant coordinates is an affine bijection after retaining their values.
For one risk, the resulting bound is
$$
\operatorname{poly}(m,\tau,L)\,
(V+1)^{2\min\{3\tau+1,\,2(d-1)\}+2}.
$$
Since
$$
\min\{3\tau+1,\,2(d-1)\}
\leq3\min\{\tau,d-1\}+1,
$$
this is at most
$$
\operatorname{poly}(m,\tau,L)\,
(V+1)^{6\min\{\tau,d-1\}+4}.
$$
For multiple risks, their polytopes form a Cartesian product. A product point is extreme precisely when each component is extreme: a nontrivial decomposition in a factor gives one in the product, while a decomposition of a product of extreme points must be constant in every factor.
Enumerate each factor’s vertices, then output their Cartesian product. If the factor counts are $V_k$, all are positive, and
$$
V=\prod_kV_k,\qquad V_k\leq V.
$$
Moreover, $V\leq B$, because every listed vertex occupies at least one bit. Exact coordinate recovery and product formation take polynomial work per output vertex.
Consequently, the total running time is bounded by
$$
\operatorname{poly}(m,\tau,r,L)\,
(B+1)^{6\min\{\tau,D-1\}+4}.
$$
This proves output-polynomial enumeration for fixed support size, even with arbitrarily many states and arbitrary positive rational masses. It also proves output-polynomial enumeration for fixed numbers of aggregate levels, even with arbitrarily many supported types.
The established exponent depends on $\min\{\tau,D-1\}$. Thus this argument supplies no polynomial bound of fixed degree when both parameters vary.
Nor does it establish that the requested algorithm would imply $\mathrm P=\mathrm{NP}$. The society polytopes are bounded. The general-polyhedron hardness result cited in the notes explicitly leaves the bounded case open; see the [Khachiyan–Boros–Borys–Elbassioni–Gurvich abstract](https://archive.dimacs.rutgers.edu/archive/TechnicalReports/abstracts/2005/2005-21.html). Applying that hardness result to the present bounded class would require an additional reduction.
The unrestricted target therefore still needs either a uniform output-polynomial algorithm or a hardness reduction with the necessary output-length control.
⟨structured verdict parsed — rendered above⟩
Assessment: correct partial progress; the unrestricted task remains unresolved. The structural proof and the fixed-parameter enumeration result are sound. I found no false central step or substantive mathematical gap in those results.
The output explicitly acknowledges its limitation. Its failure to settle USER_TASK is a major scope issue, not a contradiction between its stated claim and its proof.
The definition of $Q_Z$ is correct for arbitrary positive state probabilities. Selecting the smallest outcomes first, with a possible fractional selection at the cutoff, establishes continuity, piecewise linearity, convexity, and the two endpoint values.
Both identities relating $Q_Z$ and $\phi_Z$ are correct. The selection inequality has the correct direction. Equality can be achieved at a cutoff, including at $q=0$ and $q=1$ by choosing a threshold outside the outcome range. For the reverse identity, selecting the states strictly below $h$ also handles outcomes equal to $h$ correctly.
The utility interpolation argument is valid: on the finite outcome range, an increasing concave piecewise-linear function has a nonnegative final slope and nonnegative downward slope changes. Its stated representation therefore establishes the converse dominance implication.
Consequently, weak SSD is equivalent to pointwise integrated-quantile comparison, and strict SSD is equivalent to weak comparison with a strict inequality somewhere.
Positive homogeneity and the inequality
$$
Q_{\sum_t c_tZ_t}(q)\geq\sum_t c_tQ_{Z_t}(q)
$$
are correct. Equality under a common ordering remains valid with tied outcomes because a common cutoff selection minimizes every summand.
Finding: verified.
Separation across risks follows directly from the pairwise dominance definition. Scaling by the positive masses is a bijection preserving feasibility and both weak and strict dominance.
The four-entry modification preserves statewise totals. It also preserves each modified type’s expectation because
$$
p_a\delta=p_b\lambda\delta.
$$
The displayed conditional-mean representations and both values of $\theta_t$ are correct. The bound on $\delta$ ensures that each contraction parameter lies strictly between zero and one. Each modified outcome remains between the original endpoints, establishing nonnegativity.
Concavity and conditional Jensen give weak improvement for every increasing concave utility. The original outcomes differ, so strict concavity of $u(v)=-e^{-v}$ gives strict improvement. This establishes strict SSD under the task’s definition, rather than merely an improvement for one utility.
If one type decreases between states whose aggregate endowments weakly increase, comonotonicity forces every other type’s difference to have the same weak sign. Their sum then contradicts the aggregate ordering.
Thus all types share the aggregate ordering. The resulting quantile equality, combined with quantile superadditivity for any proposed improvement, gives exactly the displayed contradiction.
The equal-aggregate-state conclusion also follows: any nonzero typewise difference would force a strict aggregate difference.
Finding: the equivalence between Pareto optimality and comonotonicity is verified, including aggregate ties and arbitrary positive rational masses.
The scaled endowment allocation belongs to the feasible individually rational set. Feasibility supplies coordinate bounds, and the dominance inequalities are closed conditions. Compactness and existence of a minimizer of $F$ therefore follow.
A crossing contraction preserves individual rationality by transitivity. Its conditional variance decreases strictly for both modified types, while their means remain fixed. Hence the objective decreases strictly, contradicting minimality. The resulting comonotone minimizer is Pareto optimal.
The expectation argument is also correct: every expectation gain is nonnegative, while their positively weighted sum is zero. Therefore each gain is zero.
Finding: nonemptiness and typewise expectation preservation are verified.
The compression by aggregate levels is justified by the preceding Pareto characterization.
The aggregate-knot lemma is correct in the stated context of the prescribed endpoints
$$
H_{t0}=0,\qquad H_{td}=h_t.
$$
On each aggregate interval, the allocation’s integrated quantile is affine, while the endowment’s integrated quantile lies below its endpoint chord. Checking aggregate knots therefore suffices; endowment-specific knots are unnecessary.
The proposed inequality system is exact:
For $d=1$, all Pareto-optimal outcomes are constant across states, and expectation preservation fixes their values to $h_t$. The previously established nonemptiness ensures this unique allocation belongs to the required set.
Sorting and rational arithmetic compute all constants in polynomial time and bit length. The active-row argument and determinant bound establish polynomial vertex encoding length. Recovering the original state coordinates preserves that bound.
Finding: the nonempty rational-polytope description is verified.
The substitution $H=c+u$ produces the displayed local equations with the correct signs. Convexity of the endowment integrated quantile gives $g_{tj}\geq0$.
The transformation is an affine bijection: $u$ determines $H$, and $H$ uniquely determines $v$. It therefore preserves vertices.
The boundedness argument is valid. Discrete convexity and the fixed endpoints imply
$$
H_{tj}\leq q_jh_t,
$$
while individual rationality supplies the lower bound. Thus $u$ is bounded, and the fixed affine expressions defining $v$ bound those variables as well.
Finding: the rational, nonempty, bounded standard-form formulation is verified.
The rank formula for $\lambda(K)$ equals the intersection dimension of the two column spans. Any vector in that intersection is supported only on rows used by both sides, so the shared-row bound is correct.
The column incidences are accurately listed.
For a cut within aggregate layer $j$, shared local rows can occur only at indices $j-1$, $j$, and $j+1$, and only $C_j$ can be a shared aggregate row. This gives $3\tau+1$.
For a cut within one type, only that type’s local rows can be shared, together with at most $n$ aggregate rows. This gives $2n$.
The prefix decomposition has the required binary structure. Its singleton cuts have intersection dimension at most one. Hence
$$
k\leq\min\{3\tau+1,\,2(d-1)\}
$$
is justified.
Deleting constant coordinates does not increase the width: each new partition can be extended to an old partition, and its column-span intersection is contained in the old intersection. Restricting and pruning the decomposition retains the bound.
Finding: both width estimates are verified.
The external citation supports the claimed application. Reimers and Stougie’s Theorem 5 bounds a merge by the vertex count raised to $2k+2$ for modules of interface dimension at most $k$; Proposition 6 gives polynomial-time tests, and Theorem 6 combines the merges. Thus the prover’s conservative bound is supported. The source’s width terminology has an indexing inconsistency, but the explicit merge bound suffices for the prover’s stated estimate. [Reimers–Stougie, Theorems 5–6](https://arxiv.org/pdf/1404.5584).
The hypotheses have been established: rational input, boundedness, nonemptiness, a supplied decomposition, and preservation of vertices. The polynomial number of decomposition nodes and polynomial-time tests supply a polynomial prefactor of fixed degree.
The exponent comparison
$$
2\min\{3\tau+1,\,2(d-1)\}+2
\leq6\min\{\tau,d-1\}+4
$$
is correct.
The Cartesian-product argument is also correct. Each factor is nonempty, so $V_k\leq V$. Together with $V\leq B$, this validates the final bound
$$
\operatorname{poly}(m,\tau,r,L)
(B+1)^{6\min\{\tau,D-1\}+4}.
$$
Finding: output-polynomial enumeration is established when $\tau$ is fixed or $D$ is fixed, including fixed $m$.
USER_TASKMajor issue — unresolved unrestricted enumeration complexity.
When both $\tau$ and $D$ vary, the displayed exponent varies with the input. This is not a bound polynomial in all the requested quantities with a fixed degree. It also does not prove that such a bound is impossible.
The output correctly declines to apply the general-polyhedron hardness result to this bounded class. The cited abstract explicitly leaves bounded polyhedra open. [Khachiyan–Boros–Borys–Elbassioni–Gurvich abstract](https://archive.dimacs.rutgers.edu/archive/TechnicalReports/abstracts/2005/2005-21.html).
Required additional result: either a uniform output-polynomial enumeration bound for these society polytopes, or a reduction establishing the requested implication to $\mathrm{P}=\mathrm{NP}$ with adequate output-length control. Expositional clarification alone cannot resolve this issue.
The valid restricted results warrant further investigation, but they do not adjudicate the unrestricted alternative posed by the 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.