Beyond Cake Cutting: Allocating Homogeneous Divisible Goods (aamas22-00027)

Given a finite type set \(T\) with rational masses \(\mu_t\), \(m\) homogeneous divisible goods with per-capita capacities \(b_k\), nondecreasing \(C\)-Lipschitz valuation oracles \(f_{t,k}:[0,1]\to\mathbb{R}_{\ge 0}\), and \(\epsilon>0\), where \(u_t(x)=\sum_k f_{t,k}(x_k)\), compute a finite-support lottery over measurable ex-post feasible allocation fields \(a\) satisfying \(\int a_k(p)\,dp\le b_k\) that is ex-ante envy-free between types and has no alternative feasible envy-free lottery \(L'\) with \(U_t(L')\ge(1+\epsilon)U_t(L)\) for every positive-mass type and strict inequality for one type.

A society is specified by its support: \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types.
Represent it by Lebesgue measure on \([0,1]\), partitioned into type intervals \(P_t\) of lengths \(\mu_t\). There are \(m\ge1\) homogeneous goods with binary-rational per-capita capacities \(0<b_k\le1\).
Each type has nondecreasing, \(C\)-Lipschitz valuations \(f_{t,k}:[0,1]\to\mathbb R_{\ge0}\), with \(f_{t,k}(0)=0\), \(\sum_k f_{t,k}(1)=1\), and \(u_t(x)=\sum_k f_{t,k}(x_k)\). The common bound \(C>0\) is supplied.
Access is through exact value queries at rational arguments, returning rational values. Let \(L\) bound the bit lengths of numerical input and oracle replies; count both queries and bit operations.
An allocation field is measurable \(a:[0,1]\to[0,1]^m\), and is feasible when \(\int_0^1a_k(p)\,dp\le b_k\) for every good. Unallocated goods are permitted.
For a lottery \(\mathcal L\) over feasible fields, define \(V_{t,s}(\mathcal L)=\mathbb E_{a\sim\mathcal L}[\mu_s^{-1}\int_{P_s}u_t(a(p))\,dp]\) and \(U_t(\mathcal L)=V_{t,t}(\mathcal L)\). Ex-ante envy-freeness means \(U_t(\mathcal L)\ge V_{t,s}(\mathcal L)\) for all types \(t,s\).
Given binary-rational \(0<\epsilon<1\), compute an ex-ante envy-free finite-support lottery, represented by rational probabilities and fields constant on finite rational interval partitions, for which no alternative feasible envy-free lottery \(\mathcal L'\) satisfies \(U_t(\mathcal L')\ge(1+\epsilon)U_t(\mathcal L)\) for every type, with at least one strict inequality. Alternatives may have arbitrary support and measurable fields.
Is this computation possible with query count and bit running time polynomial in \(m,\tau,L,C,1/\epsilon\), or is it NP-hard?
For \(n\) finite agents, an algorithm computes the analogous lottery in polynomial time using \(O(Cmn/\epsilon^2)\) value queries when \(\epsilon<1/(mn)\). [Caragiannis et al. (2022)](https://arxiv.org/html/2201.04662)
No result settling exactly this continuous problem was located.

Status: partial progress

I do not settle the general polynomial-time versus NP-hardness question.

I prove a quantitative refinement of the approach in the notes. Write
$$ \rho=\min_k b_k,\qquad H=\max\{1,\lceil C\rceil\}. $$
Suppose distinct valuation types are separated by at least $\Delta>0$, meaning that whenever two types have different valuation functions,
$$ \max_k\sup_{x\in[0,1]}|f_{t,k}(x)-f_{s,k}(x)|\ge\Delta. $$
Then the requested allocation can be computed using
$$ O\!\left(\frac{H m^2\tau^3}{\epsilon\rho\Delta^2}\right) $$
value queries, with bit running time polynomial in the corresponding grid size and coefficient bit lengths. In particular, this is a polynomial algorithm when $\rho$ and $\Delta$ have inverse-polynomial lower bounds.

The output can be a single deterministic field constant on at most
$$ m+\tau^2 $$
rational intervals. This bound is independent of the grid size.

These results do not establish the requested complexity bound: neither $1/\rho$ nor $1/\Delta$ is bounded polynomially by the given parameters. I also prove that, when all supported types have identical valuations, the requested polynomial bound holds without a lower bound on capacities.

All arguments below are self-contained. I do not use the [finite-agent theorem of Caragiannis et al., Section 5.2](https://arxiv.org/html/2201.04662#S5.SS2) to infer a complexity bound for the continuous problem.

1. Exact reduction to marginal distributions

For every recipient type $s$ and good $k$, let $q_{s,k}$ be a Borel probability measure on $[0,1]$. Define
$$ V_{t,s}(q)=\sum_k\int f_{t,k}(x)\,dq_{s,k}(x), \qquad U_t(q)=V_{t,t}(q). $$
The resource constraints are
$$ \sum_s\mu_s\int x\,dq_{s,k}(x)\le b_k \qquad(k=1,\ldots,m). $$

Proposition 1. These marginal systems achieve exactly the valuation matrices achievable by feasible lotteries. Every feasible marginal system is realizable by one deterministic measurable field.

Proof. Given a feasible lottery, sample its field and independently sample a person uniformly from $P_s$. Let $q_{s,k}$ be the resulting distribution of that person’s allocation of good $k$. Additivity gives the displayed formula for $V_{t,s}$. Moreover,
$$ \sum_s\mu_s\int x\,dq_{s,k}(x) = \mathbb E\!\left[\int_0^1a_k(p)\,dp\right] \le b_k. $$

Conversely, write $P_s=[\ell_s,\ell_s+\mu_s]$, ignoring endpoints of measure zero. Let $Q_{s,k}$ be a quantile function of $q_{s,k}$. Set
$$ a_k(p)=Q_{s,k}\!\left(\frac{p-\ell_s}{\mu_s}\right) \qquad(p\in P_s). $$
A quantile function is measurable and sends the uniform distribution on $[0,1]$ to its prescribed probability measure. Thus this field has every prescribed good marginal within every type. It preserves resource consumption and all valuation integrals, so it is feasible. The particular correlation introduced between goods is immaterial because utilities and resource constraints depend only on individual good marginals. ∎

Define population-weighted welfare by
$$ W(q)=\sum_t\mu_tU_t(q). $$
Monotonicity and endpoint normalization imply
$$ 0\le u_t(x)\le1, \qquad 0\le W(q)\le1. $$
An alternative satisfying
$$ U_t(q')\ge(1+\epsilon)U_t(q) $$
for every type necessarily satisfies
$$ W(q')\ge(1+\epsilon)W(q). $$
Consequently, a strict upper bound below $(1+\epsilon)W(q)$ on the welfare of all feasible envy-free alternatives suffices for the task.

2. Arbitrary alternatives admit small finite representations over real numbers

The following observation removes arbitrary support and arbitrary measurable fields from the existence question, although it does not give the rational representation required of the algorithm.

Proposition 2. Every feasible lottery has the same valuation matrix and resource consumption as a deterministic field constant on at most
$$ \tau\bigl(m(\tau+1)+1\bigr) $$
intervals. The amounts and interval endpoints in this proposition may be real.

Proof. Fix $s,k$ and consider the continuous curve
$$ F_k(x)=\bigl(x,f_{1,k}(x),\ldots,f_{\tau,k}(x)\bigr) \in\mathbb R^{\tau+1}. $$
Its image is compact.

We first justify the finite-dimensional convexity facts needed here. In dimension $D$, a finite convex combination involving more than $D+1$ points can be shortened. Indeed, those points are affinely dependent, so there are coefficients $c_i$, not all zero, satisfying
$$ \sum_i c_i=0,\qquad \sum_i c_i z_i=0. $$
Starting from positive combination coefficients $a_i$, subtract
$$ \theta c_i,\qquad \theta=\min_{c_i>0}\frac{a_i}{c_i}. $$
The new coefficients remain nonnegative, preserve their sum and the represented point, and at least one becomes zero. Repeating proves the bound $D+1$.

It follows that the convex hull of a compact set is compact: it is the continuous image of the compact space consisting of $D+1$ points of that set and their simplex of convex coefficients.

Now
$$ y=\int F_k(x)\,dq_{s,k}(x) $$
belongs to the convex hull of the curve. To verify this, suppose otherwise and let $z$ be a nearest point in that compact convex hull. With $w=y-z$, the nearest-point property gives
$$ w\cdot v\le w\cdot z<w\cdot y $$
for every point $v$ of the hull. Integrating this inequality over the curve contradicts the definition of $y$.

Therefore $y$ is a convex combination of at most $\tau+2$ curve points. Replacing $q_{s,k}$ by the corresponding atomic measure preserves its mean and every observer type’s valuation of it.

Perform this replacement for every $s,k$. Within $P_s$, realize each marginal consecutively on intervals and refine by the union of all good-specific breakpoints. Each marginal contributes at most $\tau+1$ internal breakpoints. Hence type $s$ requires at most
$$ 1+m(\tau+1) $$
intervals. Summing over types proves the result. ∎

Thus unrestricted alternatives can be reduced to finite deterministic fields, but allowing real amounts and probabilities remains essential in this proposition.

3. The rational finite-grid problem and a sharper output bound

Let $G\subseteq[0,1]$ be a finite rational grid containing $0$ and $1$. Query every $f_{t,k}(x)$ for $x\in G$.

Use nonnegative variables $q_{s,k,x}$ and impose
$$ \sum_{x\in G}q_{s,k,x}=1 \qquad(s,k), $$
$$ \sum_s\mu_s\sum_{x\in G}xq_{s,k,x}\le b_k \qquad(k), $$
and
$$ \sum_{k,x}f_{t,k}(x)q_{t,k,x} \ge \sum_{k,x}f_{t,k}(x)q_{s,k,x} \qquad(t\ne s). $$
Maximize
$$ W_G=\sum_t\mu_t\sum_{k,x}f_{t,k}(x)q_{t,k,x}. $$

This is a nonempty bounded rational linear program. For a useful welfare lower bound, define
$$ B=\sum_t\mu_t\sum_k b_kf_{t,k}(1). $$
Give every recipient type, for good $k$, amount $1$ with marginal probability $b_k$ and amount $0$ otherwise. All recipient types have identical marginals, so this is envy-free, and it consumes exactly $b_k$ of good $k$. Its welfare is $B$. Endpoint normalization gives
$$ \rho\le B\le W_G\le1. $$

Standard rational linear programming therefore computes an optimal rational solution in time polynomial in the number of variables, constraints, and coefficient bit lengths.

3.1 At most $m+\tau^2$ output intervals

Proposition 3. An optimal grid solution can be chosen so that its deterministic field uses at most $m+\tau^2$ rational intervals.

Proof. Choose an optimal vertex of the grid polytope. Such a vertex exists because the polytope is nonempty and bounded.

Let $P$ be the number of positive variables at this vertex. There are $m\tau$ normalization equalities and at most
$$ m+\tau(\tau-1) $$
resource and nontrivial envy inequalities. Hence
$$ P\le m\tau+m+\tau(\tau-1). $$
Here is a direct justification. If more variables were positive, there would be a nonzero perturbation supported on those variables and annihilating every equality and active inequality. Both sufficiently small signs of this perturbation would preserve positivity and all inactive inequalities. The alleged vertex would then be the midpoint of two distinct feasible points, a contradiction.

Let $r_{s,k}$ count the positive variables for marginal $s,k$. Its consecutive interval realization has $r_{s,k}-1$ internal breakpoints. After combining breakpoints across goods, type $s$ uses at most
$$ 1+\sum_k(r_{s,k}-1) $$
intervals. Thus the whole field uses at most
$$ \tau+P-m\tau \le m+\tau^2 $$
intervals.

Every interval length is $\mu_sq_{s,k,x}$, and every allocated amount belongs to $G$, so all amounts and endpoints are rational. ∎

An optimal vertex can be found in polynomial time, for example by successively maximizing each coordinate over the optimal face. Each step is a rational LP; after all coordinates are fixed, the resulting singleton is a vertex.

4. A certificate against every unrestricted alternative

Let $h$ be the maximum gap of $G$. For $x\in[0,1]$, let $r(x)$ be its largest grid predecessor. Then
$$ 0\le x-r(x)\le h. $$

Introduce dual multipliers $\lambda_{t,s}\ge0$ for the envy inequalities, $p_k\ge0$ for the resource inequalities, and unrestricted $z_{s,k}$ for normalization. Define
$$ A_{s,k}(x)= \left(\mu_s+\sum_{v\ne s}\lambda_{s,v}\right)f_{s,k}(x) -\sum_{t\ne s}\lambda_{t,s}f_{t,k}(x) -p_k\mu_sx. $$
The grid dual has constraints
$$ z_{s,k}\ge A_{s,k}(x) \qquad(x\in G) $$
and objective
$$ \sum_kp_kb_k+\sum_{s,k}z_{s,k}. $$
The primal is feasible with finite optimum, so strong LP duality supplies an optimal dual with objective $W_G$. Write
$$ \Lambda=\sum_{t\ne s}\lambda_{t,s}. $$

Proposition 4. Every feasible envy-free lottery satisfies
$$ W\le W_G+mHh(1+\Lambda). $$

Proof. When passing from $r(x)$ to $x$, monotonicity makes the negatively weighted valuation terms and resource term nonincreasing. The positively weighted valuation term increases by at most its coefficient times $Hh$. Therefore,
$$ A_{s,k}(x) \le z_{s,k} +Hh\left(\mu_s+\sum_{v\ne s}\lambda_{s,v}\right). $$

Represent an unrestricted alternative by its marginals, using Proposition 1. Its Lagrangian is
$$ W+ \sum_{t\ne s}\lambda_{t,s}(V_{t,t}-V_{t,s}) +\sum_kp_k\left(b_k-\sum_s\mu_s\int x\,dq_{s,k}(x)\right). $$
Every term added to $W$ is nonnegative because the alternative is envy-free and feasible.

Expanding this Lagrangian, integrating the bound on $A_{s,k}$, and using that every marginal has total mass one gives
$$ W\le W_G+ Hh\sum_{s,k} \left(\mu_s+\sum_{v\ne s}\lambda_{s,v}\right) = W_G+mHh(1+\Lambda). $$
This applies regardless of the alternative lottery’s support or its fields’ representation. ∎

In particular,
$$ mHh(1+\Lambda)<\epsilon W_G $$
is a valid, computable certificate for the task.

5. Quantitative control from separation of valuation types

Call two supported types equivalent if all their valuation functions are identical. Suppose there are $r\ge2$ equivalence classes, and put
$$ d=\frac{r(r-1)}2. $$
Assume that distinct classes satisfy the separation hypothesis with $0<\Delta\le1$.

Use a uniform grid of mesh $1/N$, where
$$ N\ge\frac{4H}{\Delta}. $$
For any two distinct classes, some good and some argument distinguish their functions by at least $\Delta$. Both functions are continuous, so their maximum difference is attained. Rounding that argument downward to the grid changes each value by at most $H/N$. Hence a grid point distinguishes the pair by at least
$$ \Delta-\frac{2H}{N}\ge\frac{\Delta}{2}. $$

Choose one such single-good bundle for each unordered pair of classes, giving bundles $z^1,\ldots,z^d$. Set
$$ v_{t,j}=u_t(z^j),\qquad v_t=(v_{t,1},\ldots,v_{t,d}). $$
Every coordinate is rational and belongs to $[0,1]$. For types in distinct classes,
$$ \|v_t-v_s\|^2\ge\frac{\Delta^2}{4}. $$

5.1 A feasible witness with an explicit envy margin

Set
$$ \alpha=\frac{\rho}{4d},\qquad \beta=\frac{\rho}{2}. $$
For recipient type $s$, use the bundle distribution assigning:

• probability $\alpha v_{s,j}$ to $z^j$;
• probability $\beta-\alpha\|v_s\|^2/2$ to the full bundle;
• the remaining probability to the zero bundle.

These are valid probabilities. Indeed, the full-bundle probability is at least
$$ \beta-\frac{\alpha d}{2}=\frac{3\rho}{8}, $$
and the total nonzero probability is at most
$$ \beta+\alpha d=\frac{3\rho}{4}\le1. $$
Each coordinate of each bundle is at most $1$, so every good’s population consumption is at most $3\rho/4$, which is below its capacity. Proposition 1 realizes these marginals as a feasible field.

Because every type values the full bundle at $1$, type $t$’s utility advantage from its own distribution over type $s$’s distribution is
$$ \begin{aligned} &\alpha\langle v_t,v_t-v_s\rangle -\frac{\alpha}{2}\bigl(\|v_t\|^2-\|v_s\|^2\bigr)\\ &\hspace{2em}=\frac{\alpha}{2}\|v_t-v_s\|^2. \end{aligned} $$
Thus every comparison between distinct classes has slack at least
$$ \gamma=\frac{\rho\Delta^2}{32d}. $$
Within a class the slack is zero. All witness amounts belong to the grid.

5.2 Removing envy constraints within equivalent classes

Remove only the envy inequalities between equivalent types. The reduced and full grid LPs have the same optimal welfare.

To prove this, take a reduced feasible solution. For each equivalence class $A$, write
$$ M_A=\sum_{s\in A}\mu_s, \qquad \bar q_{A,k}=\frac1{M_A}\sum_{s\in A}\mu_sq_{s,k}, $$
and assign $\bar q_{A,k}$ to every member of $A$.

This preserves resource consumption. It also preserves the class’s weighted welfare because its members have identical valuations.

For distinct classes $A,B$, let $F_A$ denote their common observer valuation. Every retained original inequality gives
$$ F_A(q_t)\ge F_A(q_s) \qquad(t\in A,\ s\in B). $$
Averaging independently over $t$ and $s$ with normalized population weights gives
$$ F_A(\bar q_A)\ge F_A(\bar q_B). $$
Within a class, identical marginals make every envy inequality an equality. The averaged solution is therefore feasible for the full LP with unchanged welfare.

5.3 A relative bound on the dual multipliers

Take an optimal dual of the reduced LP, and extend it to the full LP by setting the removed envy multipliers to zero. The equality of primal optima makes this extended dual optimal for the full LP.

Evaluate its Lagrangian at the witness. Dual feasibility bounds that Lagrangian above by $W_G$. Every retained envy slack is at least $\gamma$, and every resource slack is nonnegative. Thus
$$ W_G\ge W(\text{witness})+\gamma\Lambda\ge\gamma\Lambda. $$
Consequently,
$$ \frac{\Lambda}{W_G}\le\frac1\gamma =\frac{32d}{\rho\Delta^2}. $$

This relative inequality gives a sharper estimate than first bounding $\Lambda$ absolutely and then dividing by the baseline welfare. Since $W_G\ge B$,
$$ \frac{1+\Lambda}{W_G} \le \frac1B+\frac{32d}{\rho\Delta^2}. $$

If there is just one equivalence class, removing all envy constraints and applying the same averaging argument gives an optimal full dual with $\Lambda=0$.

6. The quantitative algorithm

Theorem 5. Suppose the separation hypothesis holds with a supplied rational lower bound $\Delta>0$. The requested output can be computed with query count and bit running time polynomial in
$$ m,\tau,L,C,1/\epsilon,1/\rho,1/\Delta. $$
Its lottery can have one outcome, represented on at most $m+\tau^2$ rational intervals.

Proof. Query endpoint values and compute $B$. Choose an integer $N$ satisfying
$$ N\ge\frac{4H}{\Delta} $$
and, conservatively,
$$ N> \frac{2mH}{\epsilon} \left(\frac1B+\frac{16\tau^2}{\rho\Delta^2}\right). $$
Query the uniform grid with mesh $1/N$.

Under the separation promise, two types are equivalent exactly when all their queried grid valuations agree. The forward implication is immediate; the reverse follows from the grid-distinguishing argument above.

Compute an optimal vertex of the full grid LP. Compute an optimal dual of the reduced LP obtained by removing within-class comparisons, and extend that dual by zero multipliers.

If there are at least two classes, then $32d\le16\tau^2$, so the preceding section gives
$$ \begin{aligned} mHh(1+\Lambda) &\le \frac{mH}{N}W_G \left(\frac1B+\frac{32d}{\rho\Delta^2}\right)\\ &<\frac{\epsilon W_G}{2}. \end{aligned} $$
For one class, $\Lambda=0$ gives the same conclusion from the chosen bound on $N$.

Proposition 4 now bounds every feasible envy-free alternative by
$$ W< \left(1+\frac{\epsilon}{2}\right)W_G < (1+\epsilon)W_G. $$
An alternative improving every utility by the required factor would have welfare at least $(1+\epsilon)W_G$, a contradiction.

There are $m\tau(N+1)$ value queries and $m\tau(N+1)$ primal variables. The grid coordinates have bit length $O(\log N)$. All LP coefficients therefore have bit length polynomial in $L+\log N$, and rational LP algorithms give polynomial bit running time in the stated extended parameters.

Finally, Proposition 3 supplies the rational field representation with at most $m+\tau^2$ intervals. ∎

Using $B\ge\rho$, a permissible grid size is
$$ N= O\!\left( \frac{H}{\Delta} + \frac{mH\tau^2}{\epsilon\rho\Delta^2} \right). $$
For $\tau\ge2$, the corresponding query count is
$$ O\!\left(\frac{H m^2\tau^3}{\epsilon\rho\Delta^2}\right). $$

6.1 Without a supplied separation bound

This also gives an instance-dependent bound for a terminating algorithm that does not know $\Delta$.

Use nested dyadic grids. At each level, solve the full primal and, among its optimal dual solutions, minimize $\Lambda$. Stop when
$$ mHh(1+\Lambda)<\epsilon W_G. $$
The secondary optimization is a rational LP on the optimal dual face.

For any fixed instance with more than one equivalence class, the minimum separation between distinct classes is positive: there are finitely many pairs, and every nonequivalent pair has a positive maximum function difference. Once the grid is sufficiently fine, Section 5 constructs an optimal full dual satisfying the stated relative bound. The dual minimizing $\Lambda$ does at least as well. Therefore the certificate eventually succeeds.

If all types are equivalent, an optimal full dual with $\Lambda=0$ exists, and refinement again eventually succeeds.

This proves termination, with a quantitative bound depending on the instance’s actual separation. It still does not give the requested uniform polynomial bound.

7. Identical supported valuations: polynomial time even for tiny capacities

Here there may be arbitrarily many supported types and arbitrary positive masses, but assume
$$ f_{t,k}=f_k \qquad\text{for every }t,k. $$

In any envy-free marginal system, all recipient utilities must be equal: the envy inequalities in both directions compare the same valuation function. Averaging the recipient marginals with weights $\mu_s$ preserves this common utility and resource consumption. Conversely, assigning identical marginals to every type is envy-free.

The problem therefore reduces exactly to maximizing
$$ U(q)=\sum_k\int f_k(x)\,dq_k(x) $$
subject to
$$ \int x\,dq_k(x)\le b_k. $$
Let its optimum be $U_*$. It exists because the probability-measure spaces are compact in the weak topology, and all constraint and objective integrands are continuous.

Define
$$ B_0=\sum_k b_kf_k(1). $$
Endpoint lotteries show that
$$ U_*\ge B_0\ge\rho>0. $$

Set
$$ \delta=\frac{\epsilon}{4}, \qquad x_0=\frac{\delta B_0}{mH}. $$
Use the rational grid consisting of $0$, the successive points
$$ x_0,\ x_0(1+\delta),\ x_0(1+\delta)^2,\ldots $$
while below $1$, and finally $1$.

Transform any feasible marginal system as follows. Amounts below $x_0$ become zero; all other amounts are rounded upward to the next grid point. Every transformed amount is at most $(1+\delta)x$. Upward rounding does not lower utility, and discarding the small amounts loses at most
$$ mHx_0=\delta B_0 $$
utility.

Then retain each transformed marginal with probability $1/(1+\delta)$ and otherwise give zero. This restores every resource constraint. Its utility is at least
$$ \frac{U-\delta B_0}{1+\delta}. $$
Hence the optimal grid utility satisfies
$$ U_G \ge \frac{U_*-\delta B_0}{1+\delta} \ge \frac{1-\delta}{1+\delta}U_*. $$
Finally,
$$ (1+\epsilon)(1-\delta)-(1+\delta) = \frac{\epsilon(2-\epsilon)}4>0, $$
so
$$ (1+\epsilon)U_G>U_*. $$
Assigning these grid marginals identically to all types gives the required allocation.

The grid contains
$$ O\!\left( 1+\frac1\epsilon \log\frac{mH}{\epsilon B_0} \right) $$
points. Since $B_0\ge\rho$ and positive binary-rational capacities have $\log(1/\rho)=O(L)$, this number is polynomial in the parameters requested in the task. Repeated rational multiplication produces grid coordinates of polynomial bit length. The queries, LP computation, and interval construction consequently have polynomial bit complexity.

8. What remains unresolved

The new quantitative result controls the envy multipliers without an unspecified witness margin: its additional dependence is explicitly on $\rho$ and $\Delta$. It also shows that a large queried grid need not produce a large interval partition.

However, the additional parameters can be exponentially unfavorable.

For capacities, the permitted input
$$ b_k=2^{-r} $$
has encoding length $O(r)$ but inverse capacity $2^r$.

For separation, consider one good and two types with
$$ f_1(x)=x,\qquad f_2(x)=x+2^{-r}x(1-x). $$
Both are nondecreasing, are $2$-Lipschitz, vanish at zero, and equal $1$ at one. Their exact values at rational arguments are rational. Their separation is
$$ \sup_x|f_2(x)-f_1(x)|=2^{-r-2}. $$
Thus normalization and a constant Lipschitz bound do not provide an inverse-polynomial separation guarantee.

These examples demonstrate limitations of the proved bound. They do not establish hardness: in particular, nearly identical types might be handled by a different argument that avoids resolving their small differences.

The general target therefore remains open in this write-up. What is still needed is either a uniform algorithm avoiding inverse-capacity and inverse-separation dependence, or a valid hardness reduction for precisely the stated oracle problem.

⟨structured verdict parsed — rendered above⟩

Overall assessment: valid partial progress. The principal reductions, dual certificate, separation-dependent algorithm, and identical-valuation special case are sound. The output does not resolve the general polynomial-time versus NP-hardness question, and explicitly acknowledges this. I found two minor defects in the presentation of its subsidiary results.

1. Reduction to marginal distributions

Proposition 1 correctly captures both directions.

For a feasible lottery, averaging the distribution of allocations within each recipient type produces probability measures $q_{s,k}$. Additivity gives the stated valuation formula, and averaging the resource constraints gives
$$ \sum_s\mu_s\int x\,dq_{s,k}(x)\le b_k. $$
All integrands are bounded, so these expectations and integrals are finite.

Conversely, quantile functions realize the prescribed marginal distributions on each type interval. Their measurability and distributional property apply to arbitrary Borel probability measures on $[0,1]$, including measures with atoms. The resulting deterministic field preserves every valuation integral and every resource consumption. No joint-distribution restriction is missing: the utilities and constraints are additive across goods.

The welfare bounds also hold. Monotonicity, nonnegativity, and endpoint normalization imply
$$ 0\le u_t(x)\le\sum_k f_{t,k}(1)=1. $$
Because all $\mu_t$ are positive, the proposed weighted-welfare certificate correctly excludes an alternative improving every utility by the required factor. It excludes even weak factor improvement in every coordinate, so the task’s additional requirement of one strict inequality causes no difficulty.

2. Finite representations of arbitrary alternatives

Proposition 2 is correct.

The affine-dependence argument establishes the stated bound of $D+1$ points for a convex combination in dimension $D$. The resulting compactness argument for the convex hull of a compact set is valid.

The nearest-point argument correctly shows that the integral of the curve lies in its convex hull. In particular, if $y$ were outside that hull, the displayed strict separation would contradict integration against the probability measure.

Here the curve has dimension $\tau+1$, so each marginal needs at most $\tau+2$ atoms. Consequently, each good contributes at most $\tau+1$ internal breakpoints within a recipient interval. The total bound
$$ \tau\bigl(m(\tau+1)+1\bigr) $$
follows.

The qualification that these amounts and breakpoints may be real is necessary and correctly stated. This proposition alone does not establish an algorithm producing the required rational representation.

3. The grid LP and its output representation

The grid LP correctly expresses normalization, feasibility, exact envy-freeness, and weighted welfare. It is nonempty and bounded.

The endpoint construction is feasible because each good has mean allocation $b_k$. Identical recipient marginals ensure envy-freeness. Its welfare is exactly $B$, and
$$ B\ge \rho\sum_t\mu_t\sum_k f_{t,k}(1)=\rho. $$
Thus
$$ 0<\rho\le B\le W_G\le1. $$

The stated polynomial-time rational LP result applies: the LP has finitely many rational coefficients, polynomially many explicitly represented variables and constraints relative to the grid size, and a finite optimum.

The vertex-support argument is correct. If the number of positive variables exceeded the number of normalization equalities plus active resource and envy constraints, a nonzero perturbation supported on those variables would preserve all active constraints. Both sufficiently small signs would remain feasible, contradicting extremality.

The resulting interval count
$$ \tau+P-m\tau\le m+\tau^2 $$
is correct. The proposed successive coordinate optimization also produces an optimal vertex in polynomially many rational LP calls.

Minor issue: the interval-length statement is false as written.

The assertion

“Every interval length is $\mu_sq_{s,k,x}$”

does not hold after combining the breakpoint sets of different goods.

For example, with $\mu_s=1$, marginal probabilities $1/3,2/3$ for one good and $1/2,1/2$ for another produce refined interval lengths
$$ \frac13,\qquad\frac16,\qquad\frac12. $$
The middle length is not one of those marginal probabilities.

This does not invalidate rationality or the interval-count bound. The minimum clarification is to distinguish the original good-specific interval lengths from the lengths after their common refinement, and explain rationality using the refined endpoints.

4. Dual certificate against unrestricted alternatives

The displayed dual has the correct signs.

The positively weighted valuation coefficient for recipient $s$ is
$$ \mu_s+\sum_{v\ne s}\lambda_{s,v}, $$
while incoming envy multipliers contribute the negative observer terms. The resource term is correctly
$$ -p_k\mu_sx. $$

Strong LP duality applies because the finite primal is feasible and has a finite optimum. It supplies an attained dual optimum with objective $W_G$.

The predecessor comparison is valid. Moving from $r(x)$ to $x$ cannot increase the negatively weighted valuation terms or the resource term. The positively weighted valuation term increases by at most its coefficient times $Hh$, since $H\ge C$.

For a feasible envy-free alternative, every additional term in the stated Lagrangian is nonnegative. Integrating the pointwise bound therefore gives
$$ W\le W_G+mHh(1+\Lambda). $$
The summation uses $\sum_s\mu_s=1$ and counts every envy multiplier once for each good.

Consequently,
$$ mHh(1+\Lambda)<\epsilon W_G $$
is indeed a sufficient certificate against every alternative allowed by the task, including arbitrary-support lotteries and arbitrary measurable fields.

5. Separation and multiplier control

The grid-distinguishing argument is correct under the stated range
$$ 0<\Delta\le1. $$
Continuity ensures the maximum difference is attained, and downward rounding changes the difference by at most $2H/N$. The condition
$$ N\ge\frac{4H}{\Delta} $$
therefore preserves a difference of at least $\Delta/2$.

Choosing one distinguishing bundle for each pair of equivalence classes gives
$$ \|v_t-v_s\|^2\ge\frac{\Delta^2}{4} $$
for distinct classes.

The witness probabilities are valid. The full-bundle probability is at least $3\rho/8$, and the total assigned nonzero probability is at most $3\rho/4$. Every good’s consumption is therefore at most $3\rho/4$, below its capacity.

The utility-gap identity is correct:
$$ \alpha\langle v_t,v_t-v_s\rangle -\frac{\alpha}{2}\bigl(\|v_t\|^2-\|v_s\|^2\bigr) = \frac{\alpha}{2}\|v_t-v_s\|^2. $$
With $\alpha=\rho/(4d)$, the claimed margin
$$ \gamma=\frac{\rho\Delta^2}{32d} $$
follows.

The equivalence-class averaging argument preserves resources and weighted welfare. Averaging the retained cross-class inequalities preserves those inequalities, while identical marginals enforce all within-class comparisons. Hence the reduced and full LPs have equal optimal welfare.

Extending an optimal reduced dual by zero multipliers is consequently valid. Evaluating it at the witness gives
$$ W_G\ge W(\text{witness})+\gamma\Lambda\ge\gamma\Lambda, $$
and the subsequent relative multiplier bound follows.

6. Quantitative and adaptive algorithms

For the separation range used in Section 5, Theorem 5 follows from the preceding bounds.

The chosen grid satisfies the distinguishing condition and makes the dual error strictly less than $\epsilon W_G/2$. Since $W_G>0$, the resulting welfare bound excludes simultaneous factor improvement.

The query count is correctly $m\tau(N+1)$. Grid coordinates, LP coefficients, vertex coordinates, and output endpoints have bit lengths polynomial in the stated extended parameters and numerical encoding lengths. A deterministic field with probability one is a finite-support lottery of the required form.

The adaptive algorithm also terminates as claimed. With finitely many equivalence classes, the minimum separation over distinct pairs is positive. Eventually, Section 5 supplies an optimal dual with bounded $\Lambda/W_G$. Minimizing $\Lambda$ over the optimal dual face can only improve that certificate. The secondary LP is feasible and bounded below because $\Lambda\ge0$.

Minor issue: the separation range is inconsistent across statements.

Section 5 assumes $0<\Delta\le1$, but the opening claim and Theorem 5 say only $\Delta>0$.

If there are distinct classes, normalization already forces $\Delta\le1$. If all types are equivalent, however, the separation condition is vacuous and permits arbitrarily large $\Delta$. In that case, the opening query estimate
$$ O\!\left(\frac{Hm^2\tau^3}{\epsilon\rho\Delta^2}\right) $$
can tend to zero while the described algorithm still makes endpoint queries and selects a grid using its $1/B$ term.

The minimum clarification is to state a consistent admissible range for $\Delta$ in the opening quantitative claim, theorem, and simplified query estimates. This does not affect the substantive separation-dependent argument.

7. Identical supported valuations

The special-case polynomial-time result is sound.

Envy-freeness forces all recipient utilities to coincide when observer valuations are identical. Population-weighted averaging preserves that common utility and all resources. Assigning common marginals gives the converse.

The asserted optimum exists: probability measures on the compact interval $[0,1]$ are compact in the weak topology, and the continuous objective and constraint integrands make the feasible set closed.

The geometric grid construction has the stated approximation properties. Discarding allocations below $x_0$ loses at most $mHx_0=\delta B_0$. Upward rounding multiplies retained amounts by at most $1+\delta$, including the final interval ending at $1$. Mixing with zero with probability $\delta/(1+\delta)$ restores feasibility.

Thus
$$ U_G\ge\frac{1-\delta}{1+\delta}U_*. $$
The critical arithmetic is correct:
$$ (1+\epsilon)(1-\delta)-(1+\delta) = \frac{\epsilon(2-\epsilon)}4>0. $$
It follows that $(1+\epsilon)U_G>U_*$, which excludes the requested improving alternative.

The grid-size and bit-complexity claims also hold. Positive binary-rational capacities give $\log(1/\rho)=O(L)$, and the number and bit lengths of the geometric grid points are polynomial in the requested parameters.

8. What remains unresolved

The examples of exponentially small capacity and separation are valid. For the latter, the displayed second valuation is nondecreasing and $2$-Lipschitz for positive integer $r$, and its separation is exactly $2^{-r-2}$.

These examples show that the additional parameters are not controlled polynomially by the task’s stated parameters. They establish no hardness result, as the prover correctly acknowledges.

The missing general complexity classification is an acknowledged scope deficit, not a false inference in the partial results. Completing the assignment requires either the requested uniform polynomial query and bit bound or a valid hardness reduction for the stated problem.

⟨structured verdict parsed — rendered above⟩