Answer: —
Theorem 5.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose that agents have bi-valued cost functions and items are indivisible. Then, there exists an ex-ante truthful, ex-ante PO, ex-ante EF, and ex-post EF1 mechanism for chores. As a remark, it is known that the integral allocations returned by an ex-ante PO mechanism satisfy ex-post fractional PO, which is a stronger notion of ex-post PO [AFSV23]. Moreover, we skip the discussion on time complexity throughout as it is not our main concern, yet our mechanism can be implemented in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite chore classes \(O=\{o_1,\ldots,o_m\}\), complete bi-valued cost types \(T\), rational masses \(\mu\in\mathbb{Q}^{T}\), common \(p>q>0\), and rational per-capita supplies \(s_o\in[0,1]\), construct in time \(\operatorname{poly}(m,|T|,L)\) a truthful menu of lotteries \(P_r\) over integral bundles and a feasible joint coupling such that \(z_r(o)=\Pr_{B\sim P_r}[o\in B]\), \(\sum_t\mu_tz_t(o)=s_o\), truthfulness and ex-ante envy-freeness hold, the allocation is ex-ante Pareto optimal, and every realized integral assignment is EF1 almost everywhere.
Let \(O=\{o_1,\ldots,o_m\}\), with \(m\geq1\), be chore classes. Each agent may receive at most one chore from each class, so an integral bundle is \(B\subseteq O\). Types are additive cost vectors in \(D=\{p,q\}^{O}\), for common binary rationals \(p>q>0\); constant cost vectors are allowed.
A society is given by its support: the list \(T\subseteq D\) of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Supplies \(s_o\in[0,1]\) are binary rational masses; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
Represent the society by an atomless probability space \((A,\nu)\) with type regions \(A_t\) of measure \(\mu_t\). A menu assigns every report \(r\in D\) a lottery \(P_r\) over bundles, with marginals \(z_r(o)=\Pr_{B\sim P_r}[o\in B]\). Reports do not change the society, since individual agents have zero mass.
A feasible joint coupling is a random measurable assignment \(a\mapsto B_a\subseteq O\), giving almost every agent in \(A_t\) marginal law \(P_t\), such that every realization satisfies \(\nu\{a:o\in B_a\}=s_o\) for each \(o\). In particular, \(\sum_t\mu_tz_t(o)=s_o\).
Truthfulness requires \(c_t(z_t)\leq c_t(z_r)\) for every \(t\in T,r\in D\); ex-ante envy-freeness requires \(c_t(z_t)\leq c_t(z_u)\) for every \(t,u\in T\). Indifferences are permitted and these inequalities are weak.
Ex-ante Pareto optimality is relative to all measurable fractional assignments \(y_a\in[0,1]^O\) with \(\int_A y_a(o)\,d\nu(a)=s_o\): none may weakly lower almost every agent's expected cost and strictly lower it on a set of positive measure.
Every realized assignment must be EF1 for \(\nu\times\nu\)-almost every ordered pair of agents; removal is from the envious agent's bundle. Empty bundles impose no removal requirement.
Menus and couplings must have finite descriptions: allow succinct menus with polynomial-time evaluation on an \(m\)-coordinate report, and rational lotteries over sparse tables recording the mass of each type assigned each bundle, interpreted as anonymous couplings within type regions.
Can such menus and feasible joint couplings be constructed for every input in time \(\operatorname{poly}(m,\tau,L)\), or is this construction problem NP-hard?
For finite societies with common positive bi-valued costs, a polynomial-time randomized mechanism achieves ex-ante truthfulness, Pareto optimality, and envy-freeness, together with ex-post EF1. [Source](https://arxiv.org/html/2505.01629v2).
No result settling the atomless construction problem specified above was located.
The general construction problem remains unresolved here. I prove polynomial-time constructions for two additional regimes with arbitrary total supply:
I also prove a construction when the total deficit is at most one. These results allow heterogeneous types and constant cost vectors.
More precisely, define
$$
I=\{o:0<s_o<1\},
\qquad
F=\{o:s_o=1\},
\qquad
\mu_{\min}=\min_{t\in T}\mu_t.
$$
If $I$ is empty, assigning $F$ to everyone solves the problem. Otherwise, a construction exists in $\operatorname{poly}(m,\tau,L)$ time whenever at least one of the following holds:
$$
\sum_{o\in I}s_o\leq 1,
$$
$$
\sum_{o\in I}(1-s_o)\leq 1,
$$
$$
\max_{o\in I}s_o\leq\mu_{\min},
$$
$$
\max_{o\in I}(1-s_o)\leq\mu_{\min}.
$$
The proof produces one rational table with at most $\tau(m+1)$ positive cells. Its anonymous implementation satisfies exact supplies and EF1 in every realization.
The main new ingredient is a rounding lemma. In the direct construction, the preferred-chore count and total bundle size must be rounded together. This correlation is essential to the cross-type EF1 proof.
Temporarily consider a set $J$ of classes with supplies $v_o\in[0,1]$, and put
$$
R=\sum_{o\in J}v_o.
$$
Each supported index $t$ has costs $c_t(o)\in\{p,q\}$ on $J$. The proof permits identical restricted cost vectors at different indices.
We consider two interpretations:
$$ E_t=\{o\in J:c_t(o)=q\}. $$
$$ E_t=\{o\in J:c_t(o)=p\}. $$
The second interpretation will ultimately use supplies $v_o=1-s_o$.
If $R=0$, set $x_t=0$ for every $t$. Henceforth suppose $R>0$.
Consider the compact rational polytope of flows satisfying
$$
f_{t,o}\geq 0,
\qquad
f_{t,o}=0\quad\text{if }o\notin E_t,
$$
$$
\sum_t f_{t,o}\leq v_o,
\qquad
h_t=\frac{1}{\mu_t}\sum_o f_{t,o}\leq R.
$$
The vector $h$ records preferred amounts per agent. Choose a flow whose increasingly sorted vector of preferred amounts is lexicographically maximal. This is the leximin objective.
It can be computed with $O(\tau^2)$ rational linear programs:
At least one coordinate is fixed in each round. Otherwise, for every remaining coordinate there would be a feasible witness making it strictly greater than $\lambda$. Averaging these witnesses would make all remaining coordinates strictly greater than $\lambda$, contradicting optimality.
After the forced coordinates are fixed, the same averaging argument shows that all other coordinates can simultaneously exceed the current level. Thus the procedure successively determines the leximin levels.
Two structural properties follow.
Unused preferred supply. If $h_t<R$ and $o\in E_t$, then
$$
\sum_u f_{u,o}=v_o.
$$
Indeed, otherwise a small increase in $f_{t,o}$ would increase $h_t$ without decreasing any coordinate. This strictly improves the increasingly sorted vector.
Transfer property. If $h_t<h_u$ and $o\in E_t$, then
$$
f_{u,o}=0.
$$
If this flow were positive, transfer a sufficiently small mass from $u$ to $t$ on class $o$. Both preferred-edge restrictions remain satisfied. Choose the transfer small enough that the recipient’s new preferred amount remains below the donor’s new preferred amount. The smallest altered level increases, so the sorted vector improves lexicographically. This contradicts leximin optimality.
Define residual supplies and their total by
$$
r_o=v_o-\sum_t f_{t,o},
\qquad
\Delta=\sum_o r_o
=\sum_t\mu_t(R-h_t).
$$
If $\Delta>0$, set
$$
x_t(o)=\frac{f_{t,o}}{\mu_t}
+(R-h_t)\frac{r_o}{\Delta}.
$$
If $\Delta=0$, set $x_t(o)=f_{t,o}/\mu_t$. In this case every $h_t=R$, because the positive masses weight nonnegative deficits whose sum is zero.
In either case,
$$
\sum_o x_t(o)=R,
\qquad
\sum_t\mu_t x_t(o)=v_o.
$$
The unused-supply property implies that completion gives an unsaturated type only nonpreferred classes. Consequently,
$$
x_t(E_t)=h_t.
$$
For every unsaturated type $t$, meaning $h_t<R$, the following stronger support properties hold:
$$
h_u>h_t
\quad\Longrightarrow\quad
x_u(o)=0\ \text{for every }o\in E_t,
$$
and
$$
x_u(o)>0,\ o\in E_t
\quad\Longrightarrow\quad
o\in E_u.
$$
To verify these assertions, unused preferred supply gives $r_o=0$ on $E_t$. Thus any positive $x_u(o)$ there comes from $f_{u,o}$. The transfer property gives the first assertion, and the preferred-edge restriction gives the second.
The construction has not yet imposed the class caps $x_t(o)\leq1$. These caps hold automatically in either of the following situations:
$$
R\leq1,
\qquad\text{or}\qquad
v_o\leq\mu_{\min}\ \text{for every }o.
$$
For the first assertion, each nonnegative coordinate is bounded by its row sum $R$. For the second, supply conservation gives
$$
\mu_t x_t(o)\leq v_o\leq\mu_{\min}\leq\mu_t.
$$
All subsequent conclusions assume that the resulting $x$ satisfies the class caps.
For all $t,u$,
$$
x_u(E_t)\leq h_t.
$$
If $h_t=R$, this follows from $x_u(E_t)\leq\sum_o x_u(o)=R$.
If $h_t<R$, residual completion contributes nothing on $E_t$. When $h_u>h_t$, the transfer property makes $x_u(E_t)=0$. When $h_u\leq h_t$,
$$
x_u(E_t)
=\frac{1}{\mu_u}\sum_{o\in E_t}f_{u,o}
\leq\frac{1}{\mu_u}\sum_o f_{u,o}
=h_u
\leq h_t.
$$
For direct chores, therefore,
$$
c_t(x_t)=pR-(p-q)h_t
\leq pR-(p-q)x_u(E_t)
=c_t(x_u).
$$
For omitted chores viewed as goods,
$$
c_t(x_t)=qR+(p-q)h_t
\geq qR+(p-q)x_u(E_t)
=c_t(x_u).
$$
Thus the direct allocation is envy-free for chores, and the omission allocation is envy-free when omissions are valued as goods.
Let
$$
Z=\{t:h_t=R\}.
$$
For direct chores, define positive type weights
$$
w_t=
\begin{cases}
p/q,&t\in Z,\\
1,&t\notin Z,
\end{cases}
$$
and class coefficients
$$
\rho_o=
\begin{cases}
q,&o\in E_t\text{ for some }t\notin Z,\\
p,&\text{otherwise}.
\end{cases}
$$
For every type and class,
$$
w_t c_t(o)\geq\rho_o.
$$
Equality holds whenever $x_t(o)>0$:
Hence
$$
\sum_t\mu_t w_t c_t(x_t)=\sum_o\rho_o v_o.
$$
For every measurable fractional assignment $y_a\in[0,1]^J$ with the same supplies,
$$
\int_A w_{t(a)}c_{t(a)}(y_a)\,d\nu(a)
\geq
\sum_o\rho_o\int_A y_a(o)\,d\nu(a)
=
\sum_o\rho_o v_o.
$$
A weak cost improvement almost everywhere, strict on a positive-measure set, would strictly decrease this weighted integral. The weights are positive, and all costs are bounded and measurable. Such an improvement is therefore impossible.
For omissions viewed as goods, instead define
$$
w_t=
\begin{cases}
q/p,&t\in Z,\\
1,&t\notin Z,
\end{cases}
$$
and
$$
\rho_o=
\begin{cases}
p,&o\in E_t\text{ for some }t\notin Z,\\
q,&\text{otherwise}.
\end{cases}
$$
Now
$$
w_t c_t(o)\leq\rho_o,
$$
with equality on every positive allocation coordinate. The same recipient classification proves equality: preferred recipients are either unsaturated high-cost types or saturated high-cost types, and completion recipients are unsaturated low-cost types.
Consequently, the omission allocation maximizes
$$
\int_A w_{t(a)}c_{t(a)}(y_a)\,d\nu(a)
$$
over all measurable fractional assignments with supplies $v$. It is Pareto optimal for the interpretation in which a larger cost-weighted omission value is better.
The leximin computation has polynomial-size LPs with $O(m\tau)$ variables and polynomially many constraints.
The leximin levels have polynomial encoding length. To see this without relying on repeated denominator estimates, choose a permutation that orders the final $h$-coordinates. Add the corresponding ordering inequalities to the original rational flow polytope. Within this ordered polytope, the final $h$ is obtained by successive linear optimization of the ordered coordinates. The resulting nonempty optimal face contains a vertex of the ordered polytope with exactly these $h$-coordinates.
Cramer’s rule and determinant bounds for a rational matrix of polynomial order give polynomial encoding length for that vertex and hence for every leximin level. The final flow can then be chosen as a rational vertex with those levels fixed. The completion formula uses polynomially many rational operations, so $x$ also has polynomial encoding length.
There is also a useful additional cap test. Once $h$ is fixed, $\Delta$ is fixed and the completion formula is linear in $f$. An additional polynomial-size LP can choose a flow realizing this $h$ while imposing
$$
x_t(o)\leq1
$$
on every coordinate. If this LP succeeds, the constructions below apply even outside the four sufficient regimes stated in Section 1. Failure of this LP does not imply nonexistence of a solution to the original problem.
Assume now that $x_t(o)\in[0,1]$.
For each type, order its preferred classes first, followed by its other classes. Write that order as $o_1,\ldots,o_d$, where $d=|J|$, and define
$$
C_0=0,
\qquad
C_i=\sum_{j=1}^i x_t(o_j).
$$
For $U\in[0,1)$, include $o_i$ if the half-open interval
$$
[C_{i-1},C_i)
$$
contains a point of $U+\mathbb Z$.
Since its length is at most one, each interval contains at most one such point. Thus this construction gives a bundle rather than a multiset.
For uniform $U$, the inclusion probability of $o_i$ equals $x_t(o_i)$. Indeed,
$$
\int_0^1
\sum_{k\in\mathbb Z}
\mathbf 1_{[C_{i-1},C_i)}(U+k)\,dU
=C_i-C_{i-1}.
$$
Let
$$
k=\lfloor R\rfloor,\qquad \theta=R-k,
$$
and
$$
a_t=\lfloor h_t\rfloor,\qquad \beta_t=h_t-a_t.
$$
The total bundle size $n_t(U)$ and preferred count $\ell_t(U)$ satisfy
$$
n_t(U)=k+\mathbf 1_{\{U<\theta\}},
$$
$$
\ell_t(U)=a_t+\mathbf 1_{\{U<\beta_t\}}.
$$
These formulas follow by counting shifted lattice points in $[0,R)$ and its preferred initial segment $[0,h_t)$.
The bundle changes only at fractional parts of cumulative sums $C_i$. Hence the construction gives a rational lottery over at most $d+1$ bundles. Each positive lottery probability is the length of an interval between rational breakpoints.
The following correlation will be used for direct chores.
Correlated-count lemma. Suppose $h_t\geq h_u$. If a supported rounded bundle of $t$ has size $k+1$ and a supported rounded bundle of $u$ has size $k$, then
$$
\ell_t\geq\ell_u.
$$
If $\lfloor h_t\rfloor>\lfloor h_u\rfloor$, this follows from
$$
\ell_t\geq\lfloor h_t\rfloor
\geq\lfloor h_u\rfloor+1
\geq\ell_u.
$$
Otherwise their floors agree, and $\beta_t\geq\beta_u$. The only possible violation would have $\ell_t=a_t$ and $\ell_u=a_t+1$. For the larger bundle of $t$, these conditions require
$$
\beta_t\leq U_t<\theta,
$$
so $\beta_t<\theta$. For the smaller bundle of $u$, they require
$$
\theta\leq U_u<\beta_u,
$$
so $\theta<\beta_u$. This contradicts $\beta_t\geq\beta_u$.
This lemma compares any two supported bundles. It does not require the two agents to use the same rounding parameter.
Let $B$ be any supported rounded bundle of type $t$, and let $C$ be any supported rounded bundle of type $u$.
Their cardinalities differ by at most one.
If $B$ is nonempty and contains only $q$-cost chores for $t$, removing any one of them gives
$$
c_t(B)-q
=q(|B|-1)
\leq q|C|
\leq c_t(C).
$$
Suppose instead that $B$ contains a $p$-cost chore. Then $t$ is unsaturated, because a saturated type receives only preferred chores.
If $h_u>h_t$, the support property in Section 2.2 gives $C\cap E_t=\emptyset$. Therefore
$$
c_t(B)-p
\leq p(|B|-1)
\leq p|C|
=c_t(C).
$$
It remains to consider $h_u\leq h_t$. Put
$$
\ell_B=|B\cap E_t|,
\qquad
\ell_C=|C\cap E_u|.
$$
The support property gives $C\cap E_t\subseteq C\cap E_u$, so
$$
c_t(C)\geq p|C|-(p-q)\ell_C.
$$
Also,
$$
\ell_C-\ell_B
\leq\lceil h_u\rceil-\lfloor h_t\rfloor
\leq1.
$$
If $|B|\leq|C|$, then
$$
c_t(B)-p-c_t(C)
\leq
p(|B|-|C|-1)+(p-q)(\ell_C-\ell_B)
\leq-p+(p-q)
=-q<0.
$$
If $|B|=|C|+1$, the correlated-count lemma gives $\ell_B\geq\ell_C$. Hence
$$
c_t(B)-p-c_t(C)
\leq(p-q)(\ell_C-\ell_B)
\leq0.
$$
Thus every ordered pair of supported bundles satisfies chore EF1.
Now use supplies $v_o=1-s_o$ and preferred sets
$$
E_t=\{o:c_t(o)=p\}.
$$
Let $G_t$ be a rounded omission bundle, and assign the actual chore bundle
$$
B_t=J\setminus G_t.
$$
For any supported omission bundles $G_t,G_u$, write
$$
n_t=|G_t|,
\qquad
n_u=|G_u|,
\qquad
\ell_t=|G_t\cap E_t|.
$$
I first show
$$
|G_u\cap E_t|-\ell_t\leq1.
$$
If $t$ is saturated, every omitted class in $G_t$ is preferred, so $\ell_t=n_t$. Consequently,
$$
|G_u\cap E_t|-\ell_t
\leq n_u-n_t
\leq1.
$$
If $t$ is unsaturated and $h_u>h_t$, the support property gives $G_u\cap E_t=\emptyset$.
If $t$ is unsaturated and $h_u\leq h_t$, then
$$
G_u\cap E_t\subseteq G_u\cap E_u,
$$
and therefore
$$
|G_u\cap E_t|-\ell_t
\leq\lceil h_u\rceil-\lfloor h_t\rfloor
\leq1.
$$
Actual chore costs satisfy
$$
c_t(B_t)-c_t(B_u)
=c_t(G_u)-c_t(G_t).
$$
Using the cardinality and preferred-count bounds,
$$
c_t(G_u)-c_t(G_t)
=
q(n_u-n_t)
+(p-q)\bigl(|G_u\cap E_t|-\ell_t\bigr)
\leq q+(p-q)=p.
$$
If $B_t$ contains a $p$-cost chore, removing that chore eliminates its envy.
If $B_t$ is nonempty and contains only $q$-cost chores, then $G_t$ contains every class in $E_t$. Thus
$$
|G_u\cap E_t|-\ell_t\leq0,
$$
and the sharper bound is
$$
c_t(B_t)-c_t(B_u)\leq q(n_u-n_t)\leq q.
$$
Removing any chore from $B_t$ suffices. Empty bundles impose no requirement.
Therefore the complementary construction also makes every ordered pair of supported actual bundles EF1.
Its ex-ante properties follow exactly from the omission interpretation. Set
$$
z_t=\mathbf 1-x_t.
$$
Then
$$
\sum_t\mu_t z_t(o)=1-v_o=s_o.
$$
The omission envy inequalities give
$$
c_t(z_t)=c_t(J)-c_t(x_t)
\leq c_t(J)-c_t(x_u)
=c_t(z_u).
$$
For Pareto optimality, any feasible measurable chore assignment $y_a$ corresponds to the feasible omission assignment $\mathbf1-y_a$. A weak chore-cost decrease, strict on a positive-measure set, becomes a weak omission-value increase with the same strictness. Section 2.4 rules it out.
Let $P_t$ denote the rounded actual-bundle lottery from either construction. Define
$$
b_{t,B}=\mu_t P_t(B).
$$
These masses are rational and satisfy
$$
\sum_B b_{t,B}=\mu_t,
$$
$$
\sum_{t,B:o\in B}b_{t,B}=s_o.
$$
There are at most $\tau(|J|+1)$ positive cells. Section 4 proves EF1 for every ordered pair of positive cells, including pairs within a type.
For completeness, this table has the required anonymous coupling on any atomless society.
The atomless divisibility theorem states that, in an atomless finite measure space, every measurable set has a measurable subset of any prescribed measure between zero and its own measure. Each normalized type region
$$
(A_t,\nu(\,\cdot\,)/\mu_t)
$$
is an atomless probability space. Recursively halving its sets therefore gives a measurable coordinate $U_t:A_t\to[0,1)$ with uniform distribution: the successive binary partition choices supply its binary digits, and every dyadic interval has its prescribed measure.
Partition $[0,1)$ into intervals of lengths $P_t(B)$, labeled by bundles. For a uniform random $\Theta\in[0,1)$, give agent $a\in A_t$ the label containing
$$
(U_t(a)+\Theta)\bmod1.
$$
For each fixed $\Theta$, translation modulo one preserves every cell’s measure. Hence the table and all supplies are exact in every realization. For each fixed agent, the translated coordinate is uniform, giving marginal law $P_t$.
Every realized bundle belongs to a positive table cell apart from null sets, so the pairwise result of Section 4 gives EF1 for $\nu\times\nu$-almost every ordered pair in every realization.
For a supported report $r=t$, offer $P_t$. For an unsupported report, choose a supported lottery minimizing its reported expected cost:
$$
u(r)\in\arg\min_{u\in T}c_r(z_u),
$$
and offer $P_{u(r)}$.
Every report thus receives a supported lottery. Supported envy-freeness gives, for every truthful supported type $t$ and every report $r$,
$$
c_t(z_t)\leq c_t(z_r).
$$
This is precisely the requested truthfulness condition, since reports do not alter the society. Finding the chosen supported index requires $O(m\tau)$ rational arithmetic operations.
Classes with supply zero can be omitted. Classes in $F$ can be assigned to everyone.
Indeed, any feasible fractional comparison assignment satisfies
$$
y_a(o)=0\quad\text{almost everywhere if }s_o=0,
$$
and
$$
y_a(o)=1\quad\text{almost everywhere if }s_o=1.
$$
These conclusions follow from $0\leq y_a(o)\leq1$ and its prescribed integral. Thus fixed-class costs cancel in all ex-ante comparisons, and Pareto optimality on $I$ extends to the original instance.
Appending $F$ also preserves EF1. If a residual bundle is nonempty, use its EF1 removal and cancel the common $F$-cost from both sides. If it is empty, its full bundle is $F$, whose cost is at most that of $F$ plus any comparison residual bundle; removing any chore from $F$, when necessary, preserves the inequality.
Applying the direct construction on $I$ proves the first and third sufficient conditions in Section 1. Applying the complementary construction on $I$ proves the second and fourth.
Each construction uses $O(\tau^2)$ LPs with $O(m\tau)$ variables and polynomially many constraints. All rational data have polynomial encoding length in $m,\tau,L$.
Rounding all types requires $O(\tau m^2)$ rational arithmetic operations by sorting cumulative-sum breakpoints and evaluating the bundles between them. The table has at most $\tau(m+1)$ positive cells, with polynomial-bit probabilities and masses.
Hence construction time, output length, and menu-evaluation time are all polynomial in $m,\tau,L$.
Take four classes, two types of mass $1/2$, and supplies
$$
s_1=s_2=s_3=s_4=\frac25.
$$
Let the low-cost sets be
$$
E_t=\{o_1\},
\qquad
E_u=\{o_2,o_3\}.
$$
Thus total supply is $8/5>1$, while every class supply is at most $\mu_{\min}=1/2$.
The direct construction gives
$$
h_t=\frac45,
\qquad
h_u=\frac85,
$$
and marginals
$$
x_t=\left(\frac45,0,0,\frac45\right),
\qquad
x_u=\left(0,\frac45,\frac45,0\right).
$$
One resulting table is:
| Type | Bundle | Population mass |
|---|---|---:|
| $t$ | $\{o_1,o_4\}$ | $3/10$ |
| $t$ | $\{o_1\}$ | $1/10$ |
| $t$ | $\{o_4\}$ | $1/10$ |
| $u$ | $\{o_2,o_3\}$ | $3/10$ |
| $u$ | $\{o_2\}$ | $1/10$ |
| $u$ | $\{o_3\}$ | $1/10$ |
Each type has mass $1/2$, and each class has supply $2/5$. The preceding proofs establish truthfulness, ex-ante envy-freeness, Pareto optimality against the specified measurable benchmark, and realized EF1 for every $p>q>0$.
These results settle additional heterogeneous cases beyond total supply one. They do not establish universal feasibility or a general polynomial-time construction.
The unresolved inputs are those for which neither orientation yields a capped fractional allocation through the preferred-flow construction, and which fall outside the stated sufficient regimes. Failure of either cap LP only rejects that particular fractional construction.
The cited finite-society theorem provides the four guarantees for indivisible-item allocations, but it does not by itself resolve these capped atomless inputs. [Theorem 5.1](https://arxiv.org/html/2505.01629v2#S5)
A universal construction or a valid hardness reduction is still needed.
⟨structured verdict parsed — rendered above⟩
The output establishes substantive polynomial-time constructions in the stated sufficient regimes, subject to one minor clarification in the atomless implementation. I found no false central step in those constructions. It does not settle the general construction-versus-hardness question in USER_TASK, and it expressly acknowledges that limitation.
The appropriate overall status is partial. The incompleteness is a major issue relative to the assigned task, rather than a defect in the restricted-regime mathematical arguments.
The four conditions in Section 1 are sufficient conditions, not a characterization of all inputs. The direct construction is justified when
$$
\sum_{o\in I}s_o\leq1
\quad\text{or}\quad
\max_{o\in I}s_o\leq\mu_{\min},
$$
and the complementary construction is justified under the corresponding conditions for $1-s_o$.
The additional cap-feasibility LP can certify further instances. However, neither its universal feasibility nor an alternative construction for failures is established. No hardness reduction is supplied.
Major issue: the general question remains unanswered. This agrees with the prover’s own stated claim of partial progress.
Required additional work: a general construction with the requested running time, or a valid hardness reduction for the specified construction problem. Further clarification of the existing restricted constructions alone cannot close this gap.
The flow polytope is nonempty, since the zero flow is feasible, and compact: every flow coordinate is nonnegative and bounded by its class supply. Positive supported masses make every expression involving $1/\mu_t$ well-defined.
The proposed LP procedure correctly identifies forced coordinates at each level. The averaging argument establishes that at least one remaining coordinate must have maximum equal to the current common lower bound. Otherwise, averaging the finitely many witnesses would strictly improve every remaining coordinate simultaneously.
The same argument justifies proceeding to a strictly higher level for coordinates not fixed in that round. There are at most $\tau$ rounds and at most $\tau$ coordinate-maximization LPs per round, giving the claimed $O(\tau^2)$ bound.
Both structural properties follow from admissible improvements:
The normalization by unequal type masses changes the respective increases and decreases, but does not invalidate either argument.
The residual identity
$$
\Delta=R-\sum_t\mu_t h_t
=\sum_t\mu_t(R-h_t)
$$
uses $\sum_t\mu_t=1$ and is correct.
For $\Delta>0$, the completion formula gives the claimed row sums and weighted column sums. For $\Delta=0$, positivity of the masses and nonnegativity of the deficits imply $h_t=R$ for every supported type.
An unsaturated type receives no completion on its preferred classes because those classes have zero residual supply. A saturated type has zero completion altogether. Thus
$$
x_t(E_t)=h_t
$$
holds in both cases.
The stronger support properties also follow: on a preferred class of an unsaturated type, a positive allocation coordinate must come from preferred flow, and the transfer property excludes recipients with larger preferred amounts.
Both sufficient cap conditions are valid. Nonnegative coordinates are bounded by their row sum when $R\leq1$. Otherwise, supply conservation gives
$$
\mu_t x_t(o)\leq v_o,
$$
which proves the cap when $v_o\leq\mu_{\min}$.
The proof correctly restricts subsequent conclusions to capped allocations.
The cases $h_t=R$, $h_t<R$ with $h_u>h_t$, and $h_u\leq h_t$ exhaust all possibilities and establish
$$
x_u(E_t)\leq h_t.
$$
The direct cost identity
$$
c_t(x_u)=pR-(p-q)x_u(E_t)
$$
and the omission-value identity
$$
c_t(x_u)=qR+(p-q)x_u(E_t)
$$
have the correct signs for their respective preferred sets.
Consequently, direct envy-freeness and omission-value envy-freeness follow as written. Identical restricted cost vectors at different supported indices cause no problem.
For direct chores, the stated coefficient inequalities hold for every type and class. In particular, a saturated type has weighted cost at least $p$, whereas an unsaturated type has weighted cost either $q$ or $p$.
The equality-on-support classification is also valid:
These cases give exactly the stated coefficients.
The omission certificate reverses the inequalities correctly. Saturated types have weighted value at most $q$, and the same recipient classification establishes equality wherever allocation is positive.
The integral arguments apply to arbitrary measurable assignments, including assignments that vary within a type region. The weights are strictly positive, and costs are bounded and integrable. Therefore a weak improvement almost everywhere with strict improvement on a set of positive measure would contradict the respective weighted optimum.
This proves the requested Pareto property in the covered regimes, rather than merely Pareto optimality among type-constant assignments.
The ordered-polytope argument avoids assuming that repeated LP operations preserve a manageable denominator without justification. For a permutation ordering the final coordinates, successive coordinate optimizations select a face of a rational polytope whose original coefficients have polynomial encoding length. Such a face contains a vertex, and standard determinant bounds give polynomial encoding length for its coordinates.
Once the leximin levels are fixed, a vertex flow realizing them has polynomial encoding length as well. Computing the residuals and completion uses polynomially many rational operations.
The argument relies on standard polynomial-time exact rational linear programming. Its hypotheses are satisfied: the LPs have polynomial dimensions and polynomially encoded rational data.
For the additional cap test, fixing $h$ fixes $\Delta$. The completion expression is consequently linear in the remaining flow variables, including the separately handled case $\Delta=0$. The LP is therefore legitimate.
The disclaimer about infeasibility is essential and correct: failure rejects this construction, not the original problem.
The half-open interval convention ensures that an interval of length at most one contains at most one shifted lattice point, including when its length equals one. Each rounded outcome is therefore a bundle with no repeated class.
The integral calculation gives the correct inclusion marginals. The count formulas
$$
n_t(U)=\lfloor R\rfloor+\mathbf1_{\{U<R-\lfloor R\rfloor\}},
$$
$$
\ell_t(U)=\lfloor h_t\rfloor+
\mathbf1_{\{U<h_t-\lfloor h_t\rfloor\}}
$$
are correct, including integer values of $R$ and $h_t$.
Changes occur only at fractional parts of cumulative sums, giving at most $|J|+1$ positive-probability outcomes with rational probabilities.
The correlated-count lemma is valid. If the preferred-count floors differ, the integer bounds suffice. If they agree, a violation would require
$$
\beta_t<\theta<\beta_u,
$$
contradicting $\beta_t\geq\beta_u$.
Crucially, this argument compares independently selected supported bundles. It does not assume a common rounding parameter across agents.
Every nonempty bundle is covered.
For a bundle containing only preferred chores, the cardinality bound gives the claimed inequality after removing one chore.
If the bundle contains a $p$-cost chore, its type must be unsaturated. When $h_u>h_t$, the comparison bundle contains no class preferred by the envious type, and the displayed estimate is valid.
In the remaining case, the support inclusion and rounded-count bounds establish
$$
\ell_C-\ell_B\leq1.
$$
When the envious bundle is no larger, the resulting bound is $-q<0$. When it is larger by one chore, the correlated-count lemma gives the stronger inequality needed.
Removal is always from the envious agent’s bundle, as required. The proof covers pairs within a type as well as pairs between types.
The three cases for the preferred-omission difference are exhaustive and establish
$$
|G_u\cap E_t|-|G_t\cap E_t|\leq1.
$$
Together with the cardinality bound, this gives a chore-cost difference at most $p$. If the envious actual bundle contains a $p$-cost chore, the prescribed removal suffices.
If it contains only $q$-cost chores, its omission bundle contains every preferred class. The preferred-omission difference is then nonpositive, giving the sharper bound of $q$. Empty actual bundles are expressly exempted.
Complementation preserves the class caps and converts the omission supplies into the required chore supplies. The envy inequality and measurable Pareto comparison reverse in the correct direction.
The table masses are rational, have the asserted row sums, and reproduce every class supply. The bound of $\tau(|J|+1)$ positive cells follows from the per-type rounding support bound.
The atomless divisibility theorem is stated with the correct hypotheses, and every normalized positive-mass type region satisfies them. The translation construction preserves the table masses for every realization and gives the prescribed marginal lottery to agents. The supported-bundle EF1 result consequently applies to almost every ordered pair in every realization.
Minor issue: recursive binary subdivision directly describes a coordinate whose binary series can equal $1$ on the exceptional all-ones path. The text claims a literally $[0,1)$-valued coordinate without specifying the exceptional-path convention. The treatment of dyadic endpoints is likewise implicit.
Minimum clarification needed: specify the endpoint and exceptional-null-set conventions and confirm that the coordinate is measurable and has the stated uniform law.
This is a routine measure-theoretic clarification, not a new mathematical obstacle. The task permits sparse tables interpreted as anonymous couplings, so no computational encoding of the arbitrary underlying atomless space is required.
Every report is offered a supported lottery. Supported envy-freeness therefore implies truthfulness for every supported true type and every report in $D$. The argument correctly uses the fact that an individual report does not change the society.
Finding a minimizing supported lottery uses polynomially many rational cost comparisons; polynomial bit lengths have already been established. Constant cost vectors and indifferences require no extra restriction.
Zero-supply and unit-supply classes are fixed almost everywhere in every feasible fractional comparison. Their costs therefore cancel in ex-ante comparisons, and residual Pareto optimality extends to the full instance.
Appending the common bundle $F$ preserves EF1 by the stated cancellation argument. The empty residual-bundle case is also correctly handled. If $I$ is empty, the deterministic common bundle resolves the instance.
The LP count, rounding-operation bound, sparse-table size, and polynomial encoding bounds jointly justify construction and menu-evaluation time polynomial in $m,\tau,L$ for the covered instances.
In Section 6, each table row block sums to $1/2$, and every class has mass
$$
\frac{3}{10}+\frac{1}{10}=\frac25.
$$
Dividing by the type mass gives the displayed marginals. Their row sums are $8/5$, and their preferred amounts are $4/5$ and $8/5$, respectively.
The cited finite-society theorem does state the four guarantees for indivisible chores with common positive bi-valued costs, and its accompanying remark asserts polynomial implementation. It concerns finite allocations and supplies no stated extension to this atomless class-cap model. The prover correctly avoids treating it as a resolution of the remaining inputs. [Theorem 5.1 and accompanying remark](https://arxiv.org/html/2505.01629v2#S5)
The restricted constructions are genuine progress. The only local clarification identified is the null-set convention in the atomless implementation. The blocking deficiency for USER_TASK remains the absence of a general construction or hardness reduction.
⟨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.