Mechanisms for Fair Allocation Problems: No-Punishment Payment Rules in Verifiable Settings (d4-journals-jair-2014-0060)

Given finite worker types \(T\), job classes \(G\), rational masses \(\mu\), rational per-capita supplies \(\rho\), capacities \(\zeta_t\), verified values \(v_{tg}\), and an optimal mass allocation \(y^\star\) over integral bundles \(b\), define \(F_\rho(\nu)=\max\{\sum_{t,b}y_{t,b}v_t(b):\sum_b y_{t,b}=\nu_t,\ \sum_{t,b}b_g y_{t,b}\le\rho_g,\ y_{t,b}\ge0\}\) for \(\nu\le\mu\), where \(b\in\mathbb{Z}_{\ge0}^{G}\) and \(\sum_g b_g\le\zeta_t\). Under replication with \(N\mu_t\) workers of type \(t\) and \(N\rho_g\) jobs of class \(g\), compute exactly \(u_t=\int_0^1D_tF_\rho(\lambda\mu)\,d\lambda\) and \(P_t=\mu_tu_t-\sum_b y^\star_{t,b}v_t(b)\) for every \(t\) with \(\mu_t>0\), using verified values on the allocated support.

A society is given by its support: a list \(T\) of \(\tau\) worker types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\) job classes \(G\), binary-encoded integer capacities \(\zeta_t\ge1\), and additive signed rational values \(v_t(b)=\sum_{g\in G}b_gv_{tg}\). Jobs within a class are identical. Bundles belong to \(B_t=\{b\in\mathbb Z_{\ge0}^{G}:\sum_gb_g\le\zeta_t\}\), including the empty bundle.
The input includes an optimal allocation \(y^\star\), represented by its nonzero rational entries. For payment computation, only allocated jobs are available: \(G\) consists of the positively used classes and \(\rho_g=\sum_{t,b}b_gy^\star_{t,b}>0\). Verification supplies \(v_{tg}\) for every worker type and every such class, including types receiving no jobs of that class.
For \(\nu\in\mathbb R_{\ge0}^{T}\), define \(F_\rho(\nu)=\max\{\sum_{t,b\in B_t}y_{t,b}v_t(b):\sum_{b\in B_t}y_{t,b}=\nu_t,\ \sum_{t,b\in B_t}b_gy_{t,b}\le\rho_g,\ y_{t,b}\ge0\}\); \(y^\star\) is optimal at \(\nu=\mu\).
Define \(D_tF_\rho(\nu)=\lim_{h\downarrow0}(F_\rho(\nu+he_t)-F_\rho(\nu))/h\), where \(e_t\) is the coordinate unit vector, and \(u_t=\int_0^1D_tF_\rho(\lambda\mu)\,d\lambda\), \(P_t=\mu_tu_t-\sum_b y^\star_{t,b}v_t(b)\). Positive \(P_t\) is a transfer to type \(t\). If no jobs are allocated, all outputs are zero.
Is exact computation of all \(u_t\) and \(P_t\) polynomial-time solvable, or is it NP-hard? State running times in \(m\), \(\tau\), total input bit length \(L\), and the capacities \(\zeta_t\).
For finite agents with indivisible jobs and additive valuations, exact allocation-game Shapley values and their associated payments are reported to be \(\#\mathrm P\)-complete ([Greco–Scarcello](https://doi.org/10.1613/jair.4224)).
For continuous transportation cost games, an algorithm computes Aumann–Shapley prices ([Samet–Tauman–Zang](https://www.tau.ac.il/~samet/papers/transpotation.pdf)); this is a nearby result, not a verified complexity classification of the exact problem above.

Status and proven bounds

I do not settle the unrestricted polynomial-time versus $\mathrm{NP}$-hardness question. I establish two additional tractable cases and an exact algorithm whose running time depends polynomially on the number of changes in the marginal-value vector.

Let
$$ n=m+\tau, \qquad A=\max\bigl(\{0\}\cup\{v_{tg}:t\in T,\ g\in G\}\bigr). $$
When $A>0$, let $k$ be the number of distinct strictly positive values among the $v_{tg}$. Also, let $d>0$ be a rational number such that every strictly positive valuation is an integer multiple of $d$, and put
$$ M=A/d\in\mathbb Z_{>0}. $$
Such a $d$ can be computed in polynomial bit time by clearing denominators and taking a greatest common divisor.

The following are proven bit-complexity bounds:

| Task or restriction | Running time |
|---|---|
| Welfare and all right coordinate derivatives at a rational point $\nu$ | $\operatorname{poly}(m,\tau,L+\operatorname{bits}(\nu))$ |
| Exact utilities and payments, unrestricted | $2^{O(m+\tau)}\operatorname{poly}(m,\tau,L)$ |
| At most $k$ distinct strictly positive valuation levels | $(2(m+\tau)+1)^{O(k)}\operatorname{poly}(m,\tau,L)$ |
| Positive valuations are multiples of $d$ and at most $Md$ | $(1+\tau M)^{O(1)}\operatorname{poly}(m,\tau,L)$ |
| Fixed number of classes | $\bigl(2m+\tau m+\tau\binom m2\bigr)^{O(m)}\operatorname{poly}(m,\tau,L)$ |
| Fixed support size | $\bigl(2\tau+m\tau+m\binom\tau2\bigr)^{O(\tau)}\operatorname{poly}(m,\tau,L)$ |

Thus exact computation is polynomial-time solvable when $k$, $m$, or $\tau$ is fixed. The bound involving $M$ is pseudo-polynomial: $M$ can be exponentially large in $L$.

All these algorithms use the capacities through their binary encodings. They do not expand a capacity into individual jobs or slots.

1. Transportation formulation and exact derivatives

For each type and class, define
$$ x_{tg}=\sum_{b\in B_t}b_g y_{t,b}. $$
The bundle formulation is exactly equivalent to
$$ F_\rho(\nu)= \max\left\{ \sum_{t,g}v_{tg}x_{tg}: \sum_gx_{tg}\le\zeta_t\nu_t,\quad \sum_tx_{tg}\le\rho_g,\quad x_{tg}\ge0 \right\}. $$

Indeed, a feasible bundle allocation satisfies
$$ \sum_gx_{tg} =\sum_b y_{t,b}\sum_gb_g \le\zeta_t\nu_t. $$
Its class quantities and welfare are preserved.

Conversely, from any feasible $x$, use the empty bundle and the bundles $\zeta_t e_g$, assigning masses
$$ y_{t,\zeta_t e_g}=\frac{x_{tg}}{\zeta_t}, \qquad y_{t,0}=\nu_t-\frac{\sum_gx_{tg}}{\zeta_t}. $$
These masses are nonnegative, sum to $\nu_t$, and reproduce $x$ and its welfare. This construction is valid for signed valuations.

The supplied allocation therefore gives, in polynomial bit time,
$$ x^\star_{tg}=\sum_b b_g y^\star_{t,b}, \qquad W_t=\sum_gv_{tg}x^\star_{tg}, \qquad \rho_g=\sum_tx^\star_{tg}. $$
Its optimality implies
$$ \sum_tW_t=F_\rho(\mu). $$

Negative valuations can be replaced by zero when computing $F_\rho$. An allocation on a negative-valued edge can be deleted without violating any upper-bound constraint and with an increase in welfare. Zero-valued edges can likewise be deleted without changing welfare. Hence this replacement preserves the optimum.

The dual is
$$ F_\rho(\nu)= \min\left\{ \sum_t\zeta_t\nu_tq_t+\sum_g\rho_gp_g: q_t+p_g\ge v_{tg},\quad q_t,p_g\ge0 \right\}. $$
The primal is feasible and bounded, so strong duality applies. Clipping any dual coordinate above $A$ to $A$ preserves feasibility and cannot increase the objective. Consequently, the value is unchanged by restricting the dual to the compact polytope
$$ Q=\left\{ (q,p)\in[0,A]^{T\cup G}:q_t+p_g\ge v_{tg} \right\}. $$

Let $Q^\star(\nu)$ denote its optimal face. Then
$$ D_tF_\rho(\nu) =\zeta_t\min_{(q,p)\in Q^\star(\nu)}q_t. $$

To justify this formula, express the dual value as the minimum of the finitely many affine functions associated with the vertices of $Q$. At a fixed $\nu$, every inactive vertex has a strictly positive objective gap. For a sufficiently small positive increment in coordinate $t$, only currently active vertices can determine the minimum. The right derivative is therefore the smallest active coefficient $\zeta_tq_t$. Minimizing a linear coordinate over the optimal face gives the same minimum.

The computational theorem used here is the standard exact rational linear-programming theorem: a rational LP can be solved in polynomial bit time, and a finite attained optimum has an optimal rational value and an optimal solution of polynomial encoding length. Our LPs have polynomially many variables and constraints, polynomial-size rational data, and nonempty compact feasible regions or faces. Thus the theorem applies both to the dual optimization and to optimization over its optimal face.

2. Ordered dual optima along the ray

Set
$$ c_t=\zeta_t\mu_t>0. $$
Introduce transformed coordinates
$$ r_t=-q_t. $$
Dual feasibility becomes
$$ p_g-r_t\ge v_{tg}, \qquad -A\le r_t\le0, \qquad 0\le p_g\le A. $$
In these coordinates the ray objective is
$$ f_\lambda(r,p) =-\lambda\sum_tc_tr_t+\sum_g\rho_gp_g. $$

2.1 The feasible set and optimal faces are lattices

For vectors in the $(r,p)$ coordinates, let $\wedge$ and $\vee$ denote componentwise minimum and maximum.

Both operations preserve feasibility. For example, for the componentwise maximum, choose an input vector attaining the larger $r_t$. Its own $p_g$ is at most the larger $p_g$, so
$$ \max(p_g,p'_g)-\max(r_t,r'_t)\ge v_{tg}. $$
For the componentwise minimum, choose an input vector attaining the smaller $p_g$. Its own $r_t$ is at least the smaller $r_t$, giving the same inequality.

For any linear objective,
$$ f_\lambda(z\wedge z')+f_\lambda(z\vee z') =f_\lambda(z)+f_\lambda(z'). $$
If $z,z'$ are optimal, both terms on the left are at least the optimum. Their sum is twice the optimum, so both are optimal.

Every optimal face therefore has a greatest vector in this componentwise order. To construct it abstractly, choose an optimal vector maximizing each coordinate separately and take their finite componentwise maximum. Compactness ensures that the coordinate maxima are attained.

Write this greatest vector as $z^+(\lambda)=(r^+(\lambda),p^+(\lambda))$, and put $q^+(\lambda)=-r^+(\lambda)$. It simultaneously minimizes every worker coordinate $q_t$ over the optimal face.

For a fixed $q$, optimality and $\rho_g>0$ force
$$ p_g=\max\bigl(\{0\}\cup\{v_{tg}-q_t:t\in T\}\bigr). $$
Otherwise, reducing $p_g$ would strictly improve the objective. Thus $p$ is uniquely determined by an optimal $q$.

It follows that $z^+(\lambda)$ is the unique minimizer of $\sum_tq_t$ over the optimal face. Hence all derivatives can be obtained with two LPs: optimize the dual objective, then minimize $\sum_tq_t$ subject to equality with that optimal value.

2.2 Monotonicity theorem

Proven claim. If $\lambda_1<\lambda_2$, then every dual optimum $(q^1,p^1)$ at $\lambda_1$ and every dual optimum $(q^2,p^2)$ at $\lambda_2$ satisfy
$$ q^1_t\ge q^2_t\quad\text{for every }t, \qquad p^1_g\le p^2_g\quad\text{for every }g. $$

Proof. Use transformed vectors $z_1,z_2$, and define
$$ a=z_1\wedge z_2, \qquad b=z_1\vee z_2, \qquad \Delta_t=\max(r^1_t-r^2_t,0). $$
A direct calculation gives
$$ f_{\lambda_1}(a)+f_{\lambda_2}(b) -f_{\lambda_1}(z_1)-f_{\lambda_2}(z_2) =-(\lambda_2-\lambda_1)\sum_tc_t\Delta_t. $$
Optimality makes the left-hand side nonnegative; the right-hand side is nonpositive. Since all $c_t>0$, equality forces $\Delta_t=0$ for every $t$. Thus $r^1\le r^2$, equivalently $q^1\ge q^2$.

The two optimality inequalities must each be equalities. In particular,
$$ f_{\lambda_2}(b)=f_{\lambda_2}(z_2). $$
Because the worker coordinates of $b$ equal those of $z_2$, this equality says
$$ \sum_g\rho_g\bigl(\max(p^1_g,p^2_g)-p^2_g\bigr)=0. $$
Every summand is nonnegative and every $\rho_g>0$. Therefore $p^1\le p^2$. $\square$

Consequently,
$$ D_tF_\rho(\lambda\mu)=\zeta_tq_t^+(\lambda) $$
is nonincreasing in $\lambda$ for every type. This is stronger than concavity along the ray, which alone only controls the weighted sum of these derivatives.

3. Vertex coordinates and the new tractable cases

The greatest optimal vector $z^+(\lambda)$ is a vertex of $Q$. Indeed, if it were a nontrivial convex combination of two feasible vectors, linearity of the objective would make both vectors optimal. Both would be componentwise at most the greatest optimal vector. Their convex combination could equal it only if both equaled it.

We now bound the possible coordinates of vertices.

Construct a graph whose vertices are the $n$ dual coordinates $r_t,p_g$, and whose edges are the tight inequalities
$$ p_g-r_t=v_{tg}. $$
Mark a coordinate when one of its bounds is tight.

Every connected component of this graph has a marked coordinate. Otherwise, adding or subtracting a sufficiently small common amount from all coordinates of an unmarked component preserves its tight differences, its bounds, and every strictly slack inequality. This would express the point as the midpoint of two distinct feasible points, contradicting that it is a vertex.

Choose a simple path from any coordinate to a marked coordinate in its component. The path has at most $n-1$ edges. Successively using the tight differences expresses the chosen coordinate as an anchor from $\{-A,0,A\}$ plus a signed sum of at most $n-1$ valuations.

Negative valuations were already removed; zero valuations contribute nothing. If the distinct positive levels are $w_1,\ldots,w_k$, then $A$ is one of these levels. Every coordinate $q_t$ or $p_g$ at a vertex consequently belongs to
$$ \mathcal V= \left\{ \sum_{i=1}^k a_iw_i: a_i\in\mathbb Z,\quad |a_i|\le n \right\}. $$
In particular,
$$ |\mathcal V|\le(2n+1)^k. $$

Let $K$ be the number of distinct vectors $q^+(\lambda)$ attained as $\lambda$ ranges over $[0,1]$, including endpoint states. These vectors form a finite sequence: $Q$ has finitely many vertices, and changes of the active affine functions occur at finitely many parameters.

By monotonicity, each coordinate can strictly decrease at most $|\mathcal V|-1$ times. Every change of vector decreases at least one coordinate. Therefore
$$ K\le1+\tau\bigl((2n+1)^k-1\bigr). $$

If the positive valuations are multiples of $d$, the same path argument shows that every vertex coordinate is a multiple of $d$. Since $0\le q_t\le A=Md$, each coordinate can strictly decrease at most $M$ times. Thus
$$ K\le1+\tau M. $$

These bounds will yield the asserted algorithms once exact integration is shown to take time polynomial in $K$ and the input length.

4. Exact integration with a number of LP calls proportional to $K$

For a selected dual vector $z=(q,p)$, define its ray line
$$ \ell_z(\lambda)=S_z\lambda+B_z, \qquad S_z=\sum_tc_tq_t, \qquad B_z=\sum_g\rho_gp_g. $$
Write $H(\lambda)=F_\rho(\lambda\mu)$. It is a concave, continuous, piecewise-affine function, and
$$ H(\lambda)=\min_{z\text{ a vertex of }Q}\ell_z(\lambda). $$

The vector $z^+(\lambda)$ is also the state immediately to the right of $\lambda$. To see this, its $q$ coordinates simultaneously minimize all worker coordinates on the optimal face. Since $c_t>0$, it uniquely minimizes the slope $S_z$ among the active dual vectors. The inactive vertex lines have positive gaps, so this state remains optimal on a sufficiently short interval to the right.

Recursive algorithm

For an interval $[a,b]$, suppose its selected endpoint states are $z_L=z^+(a)$ and $z_R=z^+(b)$.

If their $q$ vectors coincide, monotonicity makes the marginal vector constant throughout the interval. Its contribution is
$$ u_t^{[a,b]}=\zeta_tq^L_t(b-a). $$

Otherwise, monotonicity gives $q^L\ge q^R$ with at least one strict inequality, so
$$ S_L>S_R. $$
Intersect the two lines at
$$ s=\frac{B_R-B_L}{S_L-S_R}. $$
Endpoint optimality gives $s\in[a,b]$. In fact $s>a$: equality at $a$ would make $z_R$ optimal there with a smaller slope than the selected right-hand state $z_L$.

Compute $H(s)$ and $z_M=z^+(s)$ exactly.

If
$$ H(s)=\ell_{z_L}(s)=\ell_{z_R}(s), $$
then concavity proves
$$ H(\lambda)=\ell_{z_L}(\lambda)\quad(a\le\lambda\le s), $$
and
$$ H(\lambda)=\ell_{z_R}(\lambda)\quad(s\le\lambda\le b). $$
For the first equality, the chord between $(a,H(a))$ and $(s,H(s))$ is $\ell_{z_L}$. Concavity gives $H\ge\ell_{z_L}$ there, whereas dual feasibility gives $H\le\ell_{z_L}$. The second equality follows identically.

On the interiors of these affine intervals, the corresponding right coordinate derivatives are $\zeta_tq^L_t$ and $\zeta_tq^R_t$. Here is a justification that does not assume that the ray slope determines the entire gradient: an active vertex line touching an affine interval at an interior point must have that interval’s slope, or it would fall below $H$ on one side. Comparing optimal vectors at two distinct interior parameters, monotonicity and equality of their slopes imply equality of every $q_t$, because all $c_t>0$.

The exact interval contribution is therefore
$$ u_t^{[a,b]} =\zeta_t\left(q^L_t(s-a)+q^R_t(b-s)\right). $$

If instead
$$ H(s)<\ell_{z_L}(s), $$
recurse on $[a,s]$ with states $z_L,z_M$, and on $[s,b]$ with states $z_M,z_R$.

In this second case, $s<b$. The new state differs from both endpoint states: equality of $q$ would also imply equality of $p$ and hence of the line. Thus
$$ S_L>S_M>S_R. $$
Moreover, $z_M$ occurs on an open interval immediately to the right of $s$.

Termination and bit complexity

Every unsuccessful intersection query introduces a new state strictly between its endpoint slopes. Such a state cannot be introduced again in another branch: descendant slopes lie strictly between their respective endpoint slopes, and sibling slope ranges are disjoint apart from their shared endpoint. There are at most $K$ states. The recursion therefore uses $O(K)$ queries, each requiring two rational LPs.

Every selected state is a vertex of the input-defined polytope $Q$, so its coordinates have polynomial bit length in $L$. The coefficients $S_z,B_z$, their intersection parameters, and the individual integration contributions consequently have polynomial bit length. Summing $O(K)$ rational contributions has bit complexity polynomial in $K,m,\tau,L$, including the cost of writing the outputs.

Thus the exact algorithm takes
$$ (K+1)^{O(1)}\operatorname{poly}(m,\tau,L) $$
bit time. Combined with Section 3, this proves the bounds for fixed $k$ and bounded scaled valuation range $M$.

5. An unrestricted exponential upper bound

For completeness, an explicit breakpoint bound gives the stated unrestricted exponential algorithm.

For subsets of types and classes, write
$$ c(I)=\sum_{t\in I}c_t, \qquad \rho(J)=\sum_{g\in J}\rho_g, $$
and define
$$ \mathcal R= \left\{ \frac{\rho(J)}{c(I)}: \varnothing\ne I\subseteq T,\quad \varnothing\ne J\subseteq G \right\}. $$

Proven claim. Every marginal vector is constant on each open interval between consecutive elements of
$$ \{0,1\}\cup(\mathcal R\cap(0,1)). $$

Proof. Add worker and class slacks to the transportation LP:
$$ \sum_gx_{tg}+s_t=\lambda c_t, \qquad \sum_tx_{tg}+r_g=\rho_g. $$
Negate the class rows. The resulting matrix is a reduced node–arc incidence matrix on vertices $T\cup G\cup\{o\}$. Transportation variables connect types to classes; slack variables connect their respective vertices to $o$.

The slack columns establish row rank $n$. A basis therefore consists of $n$ independent incidence columns. Its edges contain no cycle and hence form a spanning tree on the $n+1$ vertices.

Delete a basic edge and take the component not containing $o$. If its type and class sets are $I,J$, summing its balance equations shows that the corresponding basic variable is
$$ \pm\bigl(\lambda c(I)-\rho(J)\bigr). $$
This expression is not identically zero. A nonempty component containing types has $c(I)>0$; one containing classes has $\rho(J)>0$. Its only possible positive zero belongs to $\mathcal R$.

At a positive parameter outside $\mathcal R$, every feasible basis is therefore nondegenerate. Choose an optimal basic feasible solution. Strict positivity of its basic variables implies that all reduced costs are nonpositive: otherwise a sufficiently small increase in a nonbasic variable would preserve feasibility and improve welfare.

Reduced costs do not depend on the right-hand side. Within an interval avoiding $\mathcal R$, none of the basic variables can cross zero, so this basis stays feasible and optimal. Its strict positivity also persists under sufficiently small perturbations of the worker masses, giving a constant gradient throughout that interval. $\square$

There are at most
$$ (2^\tau-1)(2^m-1) $$
ratios. Enumerating and sorting them, evaluating derivatives at each intervening midpoint, and summing interval contributions gives an exact algorithm in
$$ 2^{O(m+\tau)}\operatorname{poly}(m,\tau,L) $$
bit time.

Each individual ratio and midpoint has polynomial encoding length. The final rational outputs may have exponentially many bits; the stated bound includes exact summation and output writing.

6. Fixed-dimension bounds

For fixed class prices, eliminate the worker coordinates:
$$ q_t(p)=\max\bigl(\{0\}\cup\{v_{tg}-p_g:g\in G\}\bigr). $$
Then
$$ F_\rho(\nu) =\min_{p\in[0,A]^m} \left( \sum_g\rho_gp_g+\sum_t\zeta_t\nu_tq_t(p) \right). $$
The following hyperplanes partition the cube into cells on which every $q_t(p)$ is affine:
$$ p_g=0,\quad p_g=A,\quad p_g=v_{tg}, \quad p_g-p_h=v_{tg}-v_{th}. $$
Their number is at most
$$ H_m=2m+\tau m+\tau\binom m2. $$

On a cell closure, the objective is affine and attains its minimum at a vertex. Every such vertex is the intersection of $m$ linearly independent defining hyperplanes. Enumerating these intersections supplies at most $H_m^m$ candidate prices sufficient for every $\nu$.

Each candidate produces a feasible dual vector. Hence $F_\rho$ is exactly the minimum of the resulting finite family of affine functions on the nonnegative mass domain. Restricting them to the ray, enumerating their pairwise intersections, and using the minimum active coordinate coefficient for each right derivative computes the integrals in
$$ H_m^{O(m)}\operatorname{poly}(m,\tau,L) $$
bit time. Rational linear algebra gives polynomial encoding lengths for the candidate intersections.

For fixed support size, instead eliminate
$$ p_g(q)=\max\bigl(\{0\}\cup\{v_{tg}-q_t:t\in T\}\bigr) $$
and use the hyperplanes
$$ q_t=0,\quad q_t=A,\quad q_t=v_{tg}, \quad q_t-q_s=v_{tg}-v_{sg}. $$
There are at most
$$ H_\tau=2\tau+m\tau+m\binom\tau2 $$
hyperplanes, yielding the analogous bound
$$ H_\tau^{O(\tau)}\operatorname{poly}(m,\tau,L). $$

7. Payments, budget balance, and the one-class case

Once the utilities have been computed, the payments require only
$$ P_t=\mu_tu_t-W_t. $$

On every open interval where the selected state is constant, the ray slope is
$$ H'(\lambda)=\sum_tc_tq_t^+(\lambda) =\sum_t\mu_tD_tF_\rho(\lambda\mu). $$
Integrating the finitely many affine intervals gives
$$ \sum_t\mu_tu_t=H(1)-H(0)=F_\rho(\mu), $$
because zero worker mass permits only $x=0$. Optimality of the supplied allocation therefore gives
$$ \sum_tP_t=0. $$

If $A=0$, welfare and all utilities vanish. Each $W_t$ is nonpositive, and their sum is the optimal welfare zero, so every $W_t$ and payment also vanish. The stipulated no-allocated-jobs case likewise has all outputs zero.

For one class, let its supply be $\rho$, and list the distinct positive valuations as
$$ w_1>w_2>\cdots>w_k>0, \qquad w_{k+1}=0. $$
Define
$$ I_i=\{t:v_{t1}\ge w_i\}, \qquad C_i=\sum_{t\in I_i}\zeta_t\mu_t. $$
Then
$$ u_t= \zeta_t \sum_{i:t\in I_i} (w_i-w_{i+1}) \min\left\{1,\frac{\rho}{C_i}\right\}. $$
Types with nonpositive valuations have zero utility.

To prove this formula while accounting correctly for signed valuations, first delete all nonpositive-valued assignments. This preserves feasibility and weakly increases welfare. For the remaining allocation, telescoping the positive levels expresses welfare as the sum of $(w_i-w_{i+1})$ times the quantity assigned to $I_i$. Each prefix quantity is at most
$$ \min\left\{\rho,\sum_{t\in I_i}\zeta_t\nu_t\right\}. $$
Greedy allocation in decreasing valuation order attains all these prefix bounds simultaneously. Consequently,
$$ F_\rho(\nu)= \sum_{i=1}^k (w_i-w_{i+1}) \min\left\{\rho,\sum_{t\in I_i}\zeta_t\nu_t\right\}. $$
Taking right coordinate derivatives and integrating along the ray gives the displayed utility formula. At equality with a supply threshold, the right derivative of the capped term is zero; this endpoint convention does not change its integral.

Sorting and cumulative sums evaluate all one-class utilities in $O(\tau\log\tau)$ rational arithmetic operations and polynomial bit time.

8. What remains open

The new monotonicity theorem and integration algorithm establish polynomial time for a fixed number of valuation levels and pseudo-polynomial time in the scaled valuation range. They do not bound $K$ polynomially for unrestricted binary-rational valuations.

The nearby [Samet–Tauman–Zang paper](https://www.tau.ac.il/~samet/papers/transpotation.pdf), particularly Section 5, describes gradient integration through a parametric transportation procedure. Its stated procedure does not supply the missing polynomial bit-complexity bound for this input model. Likewise, the discrete Shapley-value hardness result supplied in the question does not itself constitute a reduction to these ray integrals.

An unrestricted polynomial-time algorithm or a valid hardness reduction is still required.

⟨structured verdict parsed — rendered above⟩

The output establishes substantial partial results, but it does not resolve the unrestricted polynomial-time versus $\mathrm{NP}$-hardness question in USER_TASK. The main proofs are sound. I found one minor omission in the fixed-dimension algorithms: candidate hyperplane intersections must be filtered for membership in the stated cube.

The appropriate overall status is partial, consistent with the prover’s own disclaimer.

• Transportation formulation: verified.

Every feasible bundle allocation produces a feasible transportation allocation with identical class quantities and welfare. Conversely, the displayed construction using the empty bundle and bundles $\zeta_t e_g$ is valid because $\zeta_t$ is a positive integer and
$$ \sum_g x_{tg}\le \zeta_t\nu_t. $$
The constructed masses are nonnegative and sum exactly to $\nu_t$. Additivity preserves welfare, including for signed valuations. No enumeration of bundles or expansion of capacities is required.

Computing $x^\star$, $W_t$, and $\rho_g$ from the supplied sparse allocation takes polynomial bit time. The equality
$$ \sum_t W_t=F_\rho(\mu) $$
correctly uses the promised optimality of $y^\star$.

Replacing negative valuations by zero preserves the optimal value: negative-edge assignments can be deleted, and zero-edge assignments in the modified problem can likewise be deleted before returning to the original problem.

• Dual formulation and coordinate derivatives: verified.

The dual variables and their nonnegativity restrictions correctly correspond to the transportation upper bounds. The primal is feasible and bounded for every $\nu\in\mathbb R_{\ge0}^T$, so the stated strong-duality application is justified.

Clipping coordinates above $A$ preserves feasibility because every valuation is at most $A$ and the other coordinate in each constraint is nonnegative. It cannot increase the objective because all objective coefficients are nonnegative. Thus restriction to $Q$ preserves the value.

The derivative formula
$$ D_tF_\rho(\nu)=\zeta_t\min_{(q,p)\in Q^\star(\nu)}q_t $$
follows from the finite affine representation over vertices. Inactive vertices have positive gaps, and the right derivative selects the minimum active coefficient. This also handles boundary points with $\nu_t=0$.

The exact rational LP theorem is stated sufficiently precisely for these applications. The LPs and optimal-face constraints have polynomial-size rational descriptions, so welfare and all derivatives at a rational nonnegative point are computable in the claimed polynomial bit time.

• Lattice structure and simultaneous coordinate minimization: verified.

Both componentwise minimum and maximum preserve the transformed difference inequalities and coordinate bounds. The identity for the sum of the two objective values is correct, and it establishes closure of each optimal face under both operations.

Compactness and finitely many coordinate maxima justify existence of a greatest optimal vector. Its worker coordinates simultaneously minimize all $q_t$.

The condition $\rho_g>0$ is essential and is supplied by USER_TASK. It forces every optimal price to satisfy
$$ p_g=\max\bigl(\{0\}\cup\{v_{tg}-q_t:t\in T\}\bigr). $$
Consequently, $p$ is uniquely determined by an optimal $q$, and minimizing $\sum_t q_t$ selects the unique greatest transformed optimum. The two-LP computation is justified.

• Monotonicity theorem: verified.

Rechecking the displayed calculation gives
$$ f_{\lambda_1}(a)+f_{\lambda_2}(b) -f_{\lambda_1}(z_1)-f_{\lambda_2}(z_2) =-(\lambda_2-\lambda_1)\sum_t c_t\Delta_t. $$
Optimality makes the left side nonnegative. Since $\lambda_2>\lambda_1$ and every $c_t=\zeta_t\mu_t$ is strictly positive, all $\Delta_t$ must vanish.

This establishes the worker-coordinate ordering for every pair of optima at distinct parameters. Equality in the two optimality inequalities, together with $\rho_g>0$, then establishes the class-price ordering. The proof therefore supports the claimed coordinatewise monotonicity, rather than merely monotonicity of the weighted ray slope.

• Vertex-coordinate bounds and bounds on $K$: verified.

The greatest transformed optimum is a vertex: any feasible convex decomposition would consist of optimal points, each componentwise bounded by the greatest optimum, forcing the decomposition to be trivial.

The tight-constraint graph argument is valid. An unmarked component admits sufficiently small shifts in both directions, preserving its tight constraints, bounds, and finitely many slack inequalities; that contradicts extremality.

A simple path to a marked coordinate uses at most $n-1$ edges. Including the anchor contributes at most one further valuation level, so the coefficient bound $|a_i|\le n$ is sufficient. Hence
$$ |\mathcal V|\le(2n+1)^k. $$
Coordinatewise monotonicity then yields the stated bound on the number of distinct states.

The same reasoning establishes the multiple-of-$d$ property and
$$ K\le1+\tau M. $$
Clearing denominators and computing a greatest common divisor has polynomial bit complexity. The warning that $M$ may be exponentially large in $L$ is correct.

• Recursive exact integration: verified.

The selected state uniquely minimizes the ray slope on the optimal face because it simultaneously minimizes all worker coordinates and every $c_t$ is positive. The finite positive gaps to inactive vertex lines justify its persistence immediately to the right.

For distinct endpoint states, monotonicity gives $S_L>S_R$. Endpoint optimality places their intersection in $[a,b]$, and the right-state selection excludes $s=a$.

In the equality branch, concavity and dual feasibility give the two claimed affine pieces. The argument identifying the full marginal vector on each open affine interval is also valid: equal slopes and coordinatewise ordering force equality of every worker coordinate.

In the strict-inequality branch, the queried state differs from both endpoint states and has strictly intermediate slope. The disjoint slope ranges of recursive branches justify the $O(K)$ query count.

Selected states are vertices of the original rational polytope, so their encoding lengths are polynomially bounded. Intersections and individual contributions consequently have polynomial encoding lengths. Summing the contributions costs polynomial time in $K$ and the input length. No polynomial bound on the unrestricted $K$ follows from this argument.

• Unrestricted exponential algorithm: verified.

After negating the class rows, the augmented matrix is a reduced incidence matrix. The slack columns ensure full row rank. Independent basis columns therefore form a spanning tree.

Summing balances on a component obtained by deleting a tree edge gives the stated basic-variable expression
$$ \pm\bigl(\lambda c(I)-\rho(J)\bigr). $$
Strict positivity of worker capacities and class supplies excludes an identically zero expression. Any positive zero requires both subsets to be nonempty and belongs to $\mathcal R$.

Away from these ratios, feasible bases are nondegenerate. The reduced-cost argument establishes optimality throughout the interval, and local persistence under worker-mass perturbations establishes a constant gradient there.

The enumeration, sorting, midpoint evaluation, and exact summation therefore support
$$ 2^{O(m+\tau)}\operatorname{poly}(m,\tau,L). $$
Exponentially long outputs are compatible with this bound.

• Fixed-dimension algorithms: sound with a minor omission.

Eliminating either side of the dual is valid. The listed hyperplanes include all branch-equality boundaries of the relevant maxima and all cube boundaries. On each cell closure, the objective is affine and attains a minimum at a vertex. Such vertices are obtained from linearly independent defining hyperplanes.

Minor issue: unrestricted enumeration of hyperplane intersections also produces points outside the cube. The sentence “Each candidate produces a feasible dual vector” requires an explicit filtering qualification.

For example, take $m=2$, $\tau=1$, and valuations
$$ v_{11}=2,\qquad v_{12}=1,\qquad A=2. $$
The listed hyperplanes $p_1=0$ and $p_1-p_2=1$ intersect at
$$ p=(0,-1), $$
which violates dual nonnegativity. Computing $q(p)$ does not cure that violation.

Minimum clarification: state that only intersections lying in $[0,A]^m$, or respectively $[0,A]^\tau$, are retained. This is a routine feasibility check and does not alter the claimed bounds. Subject to that clarification, the finite affine representation and derivative computation are valid.

• Payments, budget balance, and special cases: verified.

The payment formula agrees with USER_TASK. Integrating the ray slopes over finitely many affine intervals gives
$$ \sum_t\mu_tu_t=F_\rho(\mu), $$
because $F_\rho(0)=0$. Optimality of $y^\star$ then gives budget balance.

When $A=0$, all $W_t$ are nonpositive and their sum is zero, so each is zero. The utilities and payments therefore vanish. The no-allocated-jobs case is also explicitly handled.

In the one-class case, deleting nonpositive assignments is valid, the telescoping expression is correct, and greedy allocation attains all nested prefix bounds simultaneously. The right derivative at a saturated threshold is correctly taken as zero. Since every $C_i>0$, the displayed utility formula has no undefined denominator. Sorting and cumulative sums support the stated arithmetic-operation bound.

• Resolution of USER_TASK: incomplete, explicitly acknowledged.

The output establishes an exact exponential algorithm, polynomial algorithms under several fixed-parameter restrictions, and a pseudo-polynomial valuation-range bound. It also correctly accounts for capacities through their binary encodings.

It establishes neither an unrestricted polynomial-time algorithm nor $\mathrm{NP}$-hardness. This is a major incompleteness relative to the assigned task, not a concealed flaw in the partial results.

The discussion of the nearby transportation paper is appropriately limited: its Section 5 describes parametric gradient integration but does not state the missing polynomial bit-complexity bound for this input model. [Samet–Tauman–Zang, Section 5](https://www.tau.ac.il/~samet/papers/transpotation.pdf)

To complete the assignment, the prover must supply an unrestricted polynomial-time argument with a justified bit-complexity bound, or a valid hardness reduction. The present upper bounds alone do not decide that question.

⟨structured verdict parsed — rendered above⟩