Asymptotic Existence of Class Envy-free Matchings (aamas25-00251)

Given finite classes \(P\), complete agent types \(T\) with class map \(p:T\to P\), item categories \(J\), rational type masses \(\mu_t\), rational supply masses \(\sigma_j\), and utilities \(u_t(j)\in[0,1]\), find rational class allocations \(b_{pj}\ge0\) with \(\sum_{p\in P}b_{pj}\le\sigma_j\) and within-class transports attaining each assignment valuation \(V_p(b_p)\), such that \(2V_p(b_p)\ge V_p(b_q)\) for every \(p\ne q\), while no positive item-category mass can be transferred between classes to increase the receiving class's valuation without decreasing the giving class's valuation; otherwise report infeasibility.

Let \(P\) be \(k\ge1\) classes and \(J\) be \(m\ge1\) item categories. A society is given by its support: the list \(T\) of \(\tau\) complete types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Each type specifies its class \(p(t)\) and rational utilities \(u_t(j)\in[0,1]\); every class has positive mass. Supplies \(\sigma_j>0\) are binary rationals, with unrestricted total supply. Let \(L\) be the total input bit length.
For \(T_p=\{t:p(t)=p\}\) and a nonnegative bundle vector \(b\), define the assignment valuation \(V_p(b)=\max\{\sum_{t\in T_p,j\in J}u_t(j)x_{tj}:x_{tj}\ge0,\ \sum_jx_{tj}\le\mu_t,\ \sum_{t\in T_p}x_{tj}\le b_j\}\). Thus each unit of agent mass receives at most one unit of item mass.
An allocation consists of rational \(b_{pj}\ge0\) with \(\sum_pb_{pj}\le\sigma_j\), together with rational transports attaining \(V_p(b_p)\) and satisfying \(\sum_{t\in T_p}x_{tj}=b_{pj}\). It is \(\tfrac12\)-class envy-free if \(2V_p(b_p)\ge V_p(b_q)\) for all distinct \(p,q\).
Write \(r_j=\sigma_j-\sum_pb_{pj}\) and let \(e_j\) be the coordinate vector for category \(j\). Non-wastefulness means there are neither \(p,j,0<\delta\le r_j\) with \(V_p(b_p+\delta e_j)>V_p(b_p)\), nor distinct \(p,q\), a category \(j\), and \(0<\delta\le b_{qj}\) with \(V_p(b_p+\delta e_j)>V_p(b_p)\) and \(V_q(b_q-\delta e_j)=V_q(b_q)\). These conditions quantify over real transfer amounts.

Is finding a rational non-wasteful \(\tfrac12\)-class envy-free allocation and attaining transports, or reporting infeasibility, solvable in polynomial time in \(m,\tau,k,L\), or is this task NP-hard?

For indivisible items and finitely many agents, round-robin computes a non-wasteful \(\tfrac12\)-class envy-free-up-to-one-item matching in polynomial time: after removing at most one item from the envied bundle, twice the receiving class's utility bounds its assignment valuation. [Yokoyama–Igarashi](https://arxiv.org/pdf/2502.14371).
For binary utilities, an online fractional matching algorithm achieves \((1-1/e)\)-class envy-freeness and its stated non-wastefulness condition. This concerns finite unit-capacity agents and a different efficiency definition; it does not settle the arbitrary-utility mass problem above. [Hosseini–Huang–Igarashi–Shah](https://ojs.aaai.org/index.php/AAAI/article/download/25704/25476).

Polynomial-time solvability

The task is solvable in polynomial time in $m,\tau,k,L$. Every valid instance is feasible.

The algorithm approximates Nash welfare to a prescribed accuracy, uses that approximation to construct a rational quadratic objective, and solves the resulting convex quadratic program exactly. The key lemma is that, at a weighted-welfare optimum, a class with a small item-price bill has utility close to a fixed rational lattice. This permits an exact factor-$2$ envy bound.

1. Transport formulation and non-wastefulness

Let $P_+$ consist of the classes having at least one strictly positive utility, and put $h=|P_+|$. Give every other class an empty bundle and zero transport. If $h=0$, this already solves the problem.

Assume $h\ge1$. We use transport variables only for types belonging to positive classes, and define the rational polytope
$$ X=\left\{x\ge0: \sum_jx_{tj}\le\mu_t\ \text{for every retained type }t,\quad \sum_tx_{tj}\le\sigma_j\ \text{for every }j \right\}. $$
It is nonempty and compact, since every coordinate satisfies $0\le x_{tj}\le\mu_t\le1$.

For $p\in P_+$, write
$$ U_p(x)=\sum_{t\in T_p,j}u_t(j)x_{tj}, \qquad b_{pj}(x)=\sum_{t\in T_p}x_{tj}. $$
In particular, $0\le U_p(x)\le1$.

Lemma 1. If $x\in X$ maximizes
$$ \sum_{p\in P_+}w_pU_p(x) $$
for strictly positive weights $w_p$, its induced bundles and transports attain their assignment valuations and satisfy both non-wastefulness conditions.

Proof. If a class’s transport failed to attain $V_p(b_p(x))$, replace it by an optimal transport under those bundle bounds. This preserves feasibility in $X$ and strictly increases the weighted objective, a contradiction. The original transport has exactly the column sums defining $b_p(x)$.

If unused supply allowed a strict improvement for a class, replace its transport by an optimal transport under the enlarged bundle bounds. The replacement is feasible in $X$ and strictly improves the weighted objective.

If a transfer from $q$ to $p$ strictly improved $p$ while preserving $q$’s valuation, replace both transports by optimal transports under their modified bundle bounds. Their combined category bounds are unchanged, so the replacement is feasible in $X$. Its weighted objective strictly increases.

These arguments apply to every permitted real transfer amount. A zero-valuation class cannot strictly improve and has nothing to donate. $\square$

2. A dual criterion and the rational lattice lemma

Fix positive weights $w_p$ and a maximizer $x$ of their weighted welfare. Its transport linear program has the dual
$$ \min_{\alpha,\beta} \left\{ \sum_t\mu_t\alpha_t+\sum_j\sigma_j\beta_j: \alpha_t,\beta_j\ge0,\quad \alpha_t+\beta_j\ge w_{p(t)}u_t(j) \right\}. $$
The primal is feasible and bounded, and the dual is feasible, for example with $\beta_j=0$ and sufficiently large $\alpha_t$. Linear-programming duality therefore gives an optimal dual solution.

Define
$$ A_p=\sum_{t\in T_p}\mu_t\alpha_t, \qquad B_p=\sum_j\beta_jb_{pj}(x), \qquad C_p=w_pU_p(x). $$
Complementary slackness gives
$$ C_p=A_p+B_p. $$
Indeed, every used edge has $\alpha_t+\beta_j=w_pu_t(j)$, and every type with $\alpha_t>0$ has its capacity saturated.

For any transport evaluating class $p$’s valuation of class $q$’s bundle, the dual inequalities give
$$ w_pV_p(b_q(x)) \le A_p+B_q =C_p-B_p+B_q. $$
Consequently, the following conditions suffice for the desired envy bound:
$$ C_p\le1 \quad\text{and}\quad C_p+B_p\ge1 \qquad(p\in P_+). $$
Under these conditions, $B_q\le C_q\le1$, and hence
$$ w_pV_p(b_q(x)) \le C_p-B_p+1 \le2C_p =2w_pU_p(x). $$

We next establish the lattice property used to enforce those conditions.

Choose a positive integer $D$ such that
$$ D\mu_tu_t(j)\in\mathbb Z \qquad\text{for every }t,j. $$
For example, take the product of the denominators of all input masses and utilities. This integer has $O(L)$ bits.

Lemma 2. For every class $p$ at a weighted-welfare optimum as above, there is
$$ R_p\in D^{-1}\mathbb Z_{\ge0} $$
such that
$$ 0\le U_p(x)-R_p\le\frac{B_p}{w_p}. $$

Proof. Let
$$ S_p=\{t\in T_p:\alpha_t>0\}. $$
Every type in $S_p$ receives its full mass $\mu_t$. For each such type, choose a used category $j_t$ minimizing $\beta_j$ among its used categories. Complementary slackness gives
$$ w_pu_t(j_t)=\alpha_t+\beta_{j_t}. $$
Set
$$ R_p=\sum_{t\in S_p}\mu_tu_t(j_t). $$
By the definition of $D$, this belongs to the stated lattice. Moreover,
$$ w_pR_p=A_p+\sum_{t\in S_p}\mu_t\beta_{j_t}. $$
Since each selected type is fully served and $j_t$ has minimum price among its used categories,
$$ \sum_{t\in S_p}\mu_t\beta_{j_t} \le \sum_{t\in S_p,j}\beta_jx_{tj} \le B_p. $$
Using $w_pU_p(x)=A_p+B_p$, we obtain
$$ w_p\bigl(U_p(x)-R_p\bigr) = B_p-\sum_{t\in S_p}\mu_t\beta_{j_t} \in[0,B_p]. $$
Dividing by $w_p>0$ proves the lemma. $\square$

3. A sufficiently accurate Nash-welfare approximation

We first construct an explicit positive lower bound on all Nash-optimal utilities.

Let
$$ \theta=\min\left\{1,\min_t\mu_t,\min_j\sigma_j\right\}, \qquad v=\min\{u_t(j):u_t(j)>0\}, $$
and put
$$ \delta=\frac{\theta}{2h}, \qquad \nu=\delta v, \qquad a=\nu^h. $$
All these numbers are positive rationals with polynomial encoding length.

For each positive class, select one positive-utility type-category pair and assign $\delta$ along that pair. This is feasible: each selected type receives at most half its capacity, and each category receives at most $h\delta=\theta/2$. Every positive class obtains utility at least $\nu$.

The continuous product $\prod_{p\in P_+}U_p(x)$ therefore has a positive maximum on $X$. Let $U^*$ be its maximizing utility vector. Each coordinate is positive, and
$$ \prod_pU_p^*\ge\nu^h=a. $$
Since every other coordinate is at most one,
$$ U_p^*\ge a \qquad(p\in P_+). $$

Let
$$ \mathcal C=\{(U_p(x))_{p\in P_+}:x\in X\}, \qquad f(U)=\sum_p\log U_p. $$
Strict concavity makes $U^*$ unique. First-order optimality gives
$$ \nabla f(U^*)\cdot(U-U^*)\le0 \qquad(U\in\mathcal C). $$
This also holds when $U$ has zero coordinates: an initial segment from $U^*$ toward $U$ remains strictly positive, so its directional derivative is defined.

On positive utility vectors whose coordinates are at most one,
$$ \nabla^2f(U) =-\operatorname{diag}(U_p^{-2}) \preceq-I. $$
It follows that every positive $U\in\mathcal C$ satisfies
$$ f(U^*)-f(U)\ge\frac12\|U-U^*\|_2^2. $$

Set
$$ \rho=\frac{a^3}{1024hD}, \qquad \varepsilon=\frac{\rho^2}{32}. $$
We compute a rational $\widetilde x$ in
$$ K=\{x\in X:U_p(x)\ge a/2\ \text{for all }p\in P_+\} $$
with
$$ f(U(\widetilde x))\ge f(U^*)-\varepsilon. $$
This requires only polynomial time. We use the standard weak convex-optimization result for logarithmic Nash-welfare programs: over a bounded rational polytope with an encoded positive utility lower bound, additive objective accuracy $\varepsilon$ can be obtained in time polynomial in the input length and $\log(1/\varepsilon)$. This follows from ellipsoid optimization; see [Hosseini–Vazirani, Sections 1.2 and 2.1](https://drops.dagstuhl.de/opus/volltexte/2022/15682/pdf/LIPIcs-ITCS-2022-86.pdf).

Here the hypotheses hold:

• $K$ is a bounded rational polytope described by polynomially many explicit inequalities.
• It is nonempty and contains the Nash optimum.
• All utilities on $K$ lie in $[a/2,1]$. Logarithms can be evaluated to any prescribed precision in polynomial time, and the transport-coordinate gradient is the rational quantity $u_t(j)/U_{p(t)}(x)$.
• The required bounds on the feasible region have polynomial encoding length.

For the last point, an interior ball can also be exhibited explicitly. Let $N$ be the number of retained transport variables. Add
$$ \lambda=\frac{\theta}{8(N+1)} $$
to every coordinate of the small allocation constructed above. Each row and column then uses at most $5\theta/8$, every coordinate is positive, and every class still obtains utility at least $\nu\ge a$. A Euclidean ball around this point of radius
$$ r=\min\left\{\frac{\lambda}{2}, \frac{\theta}{8(N+1)}, \frac{a}{4(N+1)}\right\} $$
lies in $K$: coordinate changes preserve nonnegativity, row and column changes are at most $\theta/8$, and utility changes are at most $a/4$. Also, $K$ lies in a ball of radius $\sqrt N$ around the origin.

Write $\widetilde U_p=U_p(\widetilde x)$. The strong-concavity bound yields
$$ \|\widetilde U-U^*\|_2 \le\sqrt{2\varepsilon} =\frac{\rho}{4}. $$
In particular,
$$ |\widetilde U_p-U_p^*|\le\frac{\rho}{4}. $$

4. The rational quadratic program

For each class, compute
$$ n_p=\left\lfloor D\widetilde U_p+\frac12\right\rfloor. $$
Choose the rational center
$$ c_p= \begin{cases} n_p/D,&\text{if }|\widetilde U_p-n_p/D|\le\rho,\\ \widetilde U_p,&\text{otherwise}. \end{cases} $$
Thus
$$ |c_p-U_p^*| \le \rho+\frac{\rho}{4} =\frac{5\rho}{4} <2\rho. $$
Since $\rho\le a/1024$ and $a\le U_p^*\le1$, we have
$$ \frac a2\le c_p\le2. $$

Now maximize, over the original polytope $X$, the rational quadratic objective
$$ Q(U(x)) = \sum_{p\in P_+} \left( \frac{2U_p(x)}{c_p} -\frac{U_p(x)^2}{2c_p^2} \right). $$
Its negative Hessian in the transport variables is positive semidefinite, being a sum of positive semidefinite rank-one matrices. Thus this is a convex quadratic minimization problem after negating the objective.

A convex quadratic program with rational coefficients and rational linear constraints can be solved exactly, with rational output, in polynomial time. This is the theorem of [Kozlov–Tarasov–Khachiyan, *The polynomial solvability of convex quadratic programming*](https://www.mathnet.ru/eng/zvmmf5189). Its hypotheses apply here: the coefficients are rational, the quadratic matrix is positive semidefinite after negation, and the feasible set is nonempty and compact. Clearing denominators produces the integer-coefficient form of that theorem with only polynomial growth in encoding length.

Let $x$ be any exact rational maximizer, and write $U=U(x)$.

5. The quadratic optimum stays close to the Nash optimum

We prove the quantitative estimates needed for exact envy-freeness.

For each coordinate,
$$ \frac{\partial Q}{\partial U_p}(U^*) -\frac{\partial f}{\partial U_p}(U^*) = \frac{2c_p-U_p^*}{c_p^2}-\frac1{U_p^*} = -\frac{(U_p^*-c_p)^2}{c_p^2U_p^*}. $$
Let this gradient difference be $g$. The bounds from the preceding sections give
$$ |g_p|\le\frac{16\rho^2}{a^3}, \qquad \|g\|_2\le\frac{16\sqrt h\,\rho^2}{a^3}. $$

Put $\Delta=U-U^*$. Because $U$ maximizes $Q$ on $\mathcal C$,
$$ \nabla Q(U)\cdot\Delta\ge0. $$
Also,
$$ \nabla Q(U) = \nabla f(U^*)+g -\operatorname{diag}(c_p^{-2})\Delta. $$
Combining this identity with first-order optimality at $U^*$ and $c_p\le2$ gives
$$ 0 \le\nabla Q(U)\cdot\Delta \le g\cdot\Delta-\frac14\|\Delta\|_2^2. $$
Cauchy–Schwarz therefore implies
$$ \|U-U^*\|_2 \le4\|g\|_2 \le\frac{64h\rho^2}{a^3} =\frac{\rho}{16D} \le\frac{\rho}{16}. $$
The same conclusion is immediate if $\Delta=0$.

Consequently,
$$ |U_p-c_p| \le\frac{\rho}{16}+\frac{5\rho}{4} <2\rho, $$
and
$$ |U_p-\widetilde U_p| \le\frac{\rho}{16}+\frac{\rho}{4} <\frac{\rho}{2}. $$

Define the rational welfare weights
$$ w_p=\frac{\partial Q}{\partial U_p}(U) =\frac{2c_p-U_p}{c_p^2}. $$
They are strictly positive. Indeed,
$$ w_pc_p =1-\frac{U_p-c_p}{c_p} \ge1-\frac{4\rho}{a} \ge\frac12. $$
In particular,
$$ w_p\ge\frac1{2c_p}\ge\frac14. $$

First-order optimality of $x$ for $Q(U(x))$ gives
$$ \sum_pw_p\bigl(U_p(z)-U_p(x)\bigr)\le0 \qquad(z\in X). $$
Thus $x$ maximizes the positive weighted linear welfare objective with these weights. Lemma 1 already proves attainment and non-wastefulness.

6. Exact factor-$2$ envy-freeness

Apply Section 2 to $x$ and its positive weights $w_p$, obtaining optimal dual variables and quantities $A_p,B_p,C_p$.

The special quadratic derivative gives the exact identity
$$ C_p=w_pU_p =\frac{2U_p}{c_p}-\frac{U_p^2}{c_p^2} = 1-\frac{(U_p-c_p)^2}{c_p^2}. $$
In particular, $C_p\le1$. Set
$$ E=\frac{16\rho^2}{a^2}. $$
The proximity estimates imply
$$ 1-E\le C_p\le1. $$
Our choice of $\rho$ also gives
$$ E\le\frac14, \qquad 4E\le\frac{\rho}{16}, \qquad \rho<\frac1{2D}. $$
For example,
$$ 4E =\rho\frac{64\rho}{a^2} =\rho\frac{a}{16hD} \le\frac{\rho}{16}. $$

We show that $C_p+B_p\ge1$ for every class.

Case 1: $B_p\ge E$. Then
$$ C_p+B_p\ge1-E+E=1. $$

Case 2: $0\le B_p<E$. By Lemma 2, there is a lattice value $R_p$ satisfying
$$ 0\le U_p-R_p\le\frac{B_p}{w_p}\le4B_p<4E. $$
Therefore,
$$ |\widetilde U_p-R_p| \le|\widetilde U_p-U_p|+|U_p-R_p| <\frac{\rho}{2}+\frac{\rho}{16} <\rho. $$
Since $\rho<1/(2D)$, this $R_p$ is the unique nearest multiple of $1/D$ to $\widetilde U_p$. The center-selection rule in Section 4 consequently chose
$$ c_p=R_p. $$
Using the sharper conclusion of Lemma 2 and $w_pc_p\ge1/2$,
$$ 1-C_p =\frac{(U_p-c_p)^2}{c_p^2} \le\frac{B_p^2}{(w_pc_p)^2} \le4B_p^2 \le B_p. $$
The last inequality follows from $B_p<E\le1/4$. Hence $C_p+B_p\ge1$ in this case as well.

We have now established both conditions from Section 2:
$$ C_p\le1, \qquad C_p+B_p\ge1. $$
Thus, for distinct positive classes,
$$ w_pV_p(b_q(x)) \le C_p-B_p+B_q \le C_p-B_p+1 \le2C_p. $$
Dividing by $w_p>0$ and using Lemma 1 gives
$$ V_p(b_q(x)) \le2U_p(x) =2V_p(b_p(x)). $$
Comparisons involving a zero-valuation class hold because such classes receive empty bundles.

7. Algorithm and encoding bounds

The algorithm is therefore:

• Identify positive classes; assign empty bundles to all other classes.
• Compute $D,\theta,v,\nu,a,\rho,\varepsilon$ as above.
• Obtain the rational Nash-welfare approximation $\widetilde x$.
• Construct the rational centers $c_p$.
• Solve the rational quadratic program exactly.
• Output its transport $x$ and the bundles $b_{pj}=\sum_{t\in T_p}x_{tj}$.

Every step has polynomial bit complexity:

• $D$ has $O(L)$ bits.
• $\nu$ has polynomial encoding length, so $a=\nu^h$ has encoding length polynomial in $h,L$.
• Consequently, $\rho,\varepsilon$ and $\log(1/\varepsilon)$ have polynomial size.
• The approximation has polynomial-size rational output.
• Finding the nearest lattice value uses exact rational arithmetic.
• The quadratic program has at most $\tau m$ variables and polynomial-size rational coefficients, so its exact rational solution is computable in polynomial time.

Lemma 1 proves the required attainment and non-wastefulness, including the conditions quantified over real transfer amounts. Section 6 proves exact $\tfrac12$-class envy-freeness. Thus the algorithm returns a valid rational allocation on every valid input.

⟨structured verdict parsed — rendered above⟩

Verification report

The prover’s argument establishes the claimed result: the task is solvable in polynomial time in $m,\tau,k,L$, and every valid instance admits a rational allocation satisfying the stated requirements.

I found no major or minor issues. The verification below checks the transport formulation, both non-wastefulness conditions, the lattice lemma, the optimization theorems, and the constants used to obtain exact envy-freeness.

1. Transport formulation and non-wastefulness

Removing classes whose utilities are identically zero is valid. Such a class cannot strictly improve under either non-wastefulness condition. Giving it an empty bundle also satisfies every envy comparison involving it. If all classes have zero utilities, the empty allocation resolves the instance.

For the remaining classes, $X$ is a nonempty, compact rational polytope. Nonnegativity and the type-capacity constraints imply
$$ 0\le x_{tj}\le\mu_t\le1. $$
The class utilities satisfy $0\le U_p(x)\le1$ because utilities are at most one and total society mass is one.

Lemma 1 is correct.

• A failure to attain $V_p(b_p(x))$ would permit a feasible replacement transport with strictly larger positive weighted welfare.
• A strict improvement using unused supply likewise gives a feasible replacement in $X$.
• In the transfer condition, the modified bounds for the two classes have unchanged combined category bounds. Optimal replacement transports therefore remain globally feasible. The receiving class strictly improves, while the donating class preserves its utility, contradicting optimality.

The replacement transports need only respect the modified bundle bounds to yield these contradictions. They need not exhaust those bounds.

The arguments apply to arbitrary permitted real transfer amounts. Thus the lemma verifies the exact non-wastefulness definition in USER_TASK, including its real quantifiers.

2. Dual criterion and lattice lemma

The displayed dual is the correct dual of the weighted transport linear program. The primal is feasible and bounded, and the dual is feasible. Consequently, optimal dual variables exist, and complementary slackness applies.

For each class, complementary slackness correctly yields
$$ w_pU_p(x)=A_p+B_p. $$
The edge equalities account for used transport, and the saturation of types with positive $\alpha_t$ accounts for $A_p$.

For any transport evaluating $V_p(b_q(x))$, summing the dual inequalities gives
$$ w_pV_p(b_q(x))\le A_p+B_q. $$
Nonnegative dual variables justify replacing actual row and column usage by their capacity bounds.

The proposed sufficient conditions are correct. If
$$ C_p\le1,\qquad C_p+B_p\ge1, $$
then $B_q\le C_q\le1$, and the displayed argument implies the required factor-$2$ inequality.

The construction of $D$ is valid: the product of the input denominators makes every $D\mu_tu_t(j)$ integral. Its binary encoding length is $O(L)$.

Lemma 2 is correct. Each type with $\alpha_t>0$ is fully served and therefore has a used category from which $j_t$ can be selected. The minimum-price selection gives
$$ \sum_{t\in S_p}\mu_t\beta_{j_t} \le \sum_{t\in S_p,j}\beta_jx_{tj} \le B_p. $$
The resulting $R_p$ belongs to the stated nonnegative rational lattice, and the displayed identity proves both bounds on $U_p(x)-R_p$. The argument also covers $S_p=\varnothing$, with $R_p=0$.

3. Nash-welfare approximation

The initial positive allocation is feasible. There is one selected pair per positive class, so a selected type receives only $\delta$, and any category receives at most $h\delta=\theta/2$. Each positive class obtains at least $\nu$.

Compactness ensures that the utility product attains its maximum. Since the initial product is at least $a>0$, every Nash-optimal coordinate is positive. The bound
$$ U_p^*\ge a $$
follows correctly from the product bound and the upper bound of one on every other coordinate.

The utility image $\mathcal C$ is convex and compact. Strict concavity of the logarithmic objective gives uniqueness of the maximizing utility vector. The stated first-order inequality applies to all of $\mathcal C$; the directional argument correctly handles comparison vectors with zero coordinates.

The Hessian bound
$$ \nabla^2f(U)\preceq-I $$
is valid on positive vectors with coordinates at most one. Combined with first-order optimality, it yields the displayed utility-distance estimate from additive objective accuracy.

The weak optimization result is stated with the relevant accuracy dependence. The cited paper confirms polynomial dependence on input size and the number of accuracy bits for the logarithmic convex programs. [Hosseini–Vazirani](https://drops.dagstuhl.de/opus/volltexte/2022/15682/pdf/LIPIcs-ITCS-2022-86.pdf).

The hypotheses are supported here: $K$ has explicit rational inequalities, positive utility bounds, computable objective values and gradients, and encoded inner and outer radius bounds. The proposed interior point and radius check out:

• Initial row and column usage is at most $\theta/2$.
• Adding $\lambda$ to every coordinate increases each such usage by less than $\theta/8$.
• Perturbations within the specified radius preserve nonnegativity and capacity constraints.
• Utilities remain above $a/2$.

Finally,
$$ \sqrt{2\varepsilon}=\rho/4 $$
is correct.

4. Rational centers and exact quadratic optimization

The rounding rule computes a nearest lattice point, with a fixed convention for ties. Either branch of the center-selection rule gives
$$ |c_p-U_p^*|\le5\rho/4. $$
The bounds $a/2\le c_p\le2$ follow from $\rho\le a/1024$ and $a\le U_p^*\le1$. In particular, every denominator involving $c_p$ is nonzero.

After negating $Q$, its Hessian in transport coordinates is positive semidefinite. All objective coefficients and constraints are rational.

The exact quadratic-programming theorem is applicable. The original paper explicitly treats positive semidefinite quadratic objectives with integer linear constraints and provides polynomial-time exact optimization, including an attaining point; it also establishes rational optimal points. Rational coefficients can be converted to that form with polynomial encoding growth. [Kozlov–Tarasov–Khachiyan](https://www.mathnet.ru/php/getFT.phtml?jrnid=zvmmf&option_lang=eng&paperid=5189&what=fullt).

Thus the use of an exact rational quadratic optimizer is justified, including when the quadratic matrix is singular.

5. Proximity to the Nash optimum

The gradient-difference identity is algebraically correct:
$$ \frac{2c_p-U_p^*}{c_p^2}-\frac1{U_p^*} = -\frac{(U_p^*-c_p)^2}{c_p^2U_p^*}. $$
The bounds on $c_p$, $U_p^*$, and their difference imply the stated estimates for $g$.

The first-order inequality at the quadratic optimum has the correct sign:
$$ \nabla Q(U)\cdot(U-U^*)\ge0. $$
Combining it with Nash first-order optimality and $c_p^{-2}\ge1/4$ correctly yields
$$ \|U-U^*\|_2\le4\|g\|_2. $$
Replacing $\sqrt h$ by $h$ weakens the bound validly. Substitution of $\rho$ gives exactly
$$ \frac{64h\rho^2}{a^3}=\frac{\rho}{16D}. $$

The subsequent bounds on $|U_p-c_p|$ and $|U_p-\widetilde U_p|$ follow.

The welfare weights are strictly positive because
$$ w_pc_p\ge1-\frac{4\rho}{a}\ge\frac12. $$
The lower bound $w_p\ge1/4$ follows from $c_p\le2$.

Finally, first-order optimality of the quadratic objective shows that its optimizer also maximizes the displayed positive weighted linear objective. Applying Lemma 1 at this point is justified.

6. Exact factor-$2$ envy-freeness

The identity
$$ C_p=1-\frac{(U_p-c_p)^2}{c_p^2} $$
is correct and gives $C_p\le1$. The proximity estimates give $C_p\ge1-E$.

All three numerical bounds used in the case analysis hold:
$$ E\le\frac14,\qquad 4E\le\frac{\rho}{16},\qquad \rho<\frac1{2D}. $$

When $B_p\ge E$, the claimed inequality $C_p+B_p\ge1$ follows immediately.

When $B_p<E$, Lemma 2 and $w_p\ge1/4$ place $R_p$ within $\rho$ of $\widetilde U_p$. Because this distance is strictly less than half the lattice spacing, $R_p$ is the unique nearest lattice point. Therefore the center-selection rule indeed chose $c_p=R_p$.

The remaining calculation is valid:
$$ 1-C_p \le \frac{B_p^2}{(w_pc_p)^2} \le4B_p^2 \le B_p, $$
where the last inequality uses $0\le B_p<E\le1/4$. This includes $B_p=0$.

Both dual sufficient conditions are therefore established exactly. The final division by $w_p$ is legitimate, and Lemma 1 identifies $U_p(x)$ with $V_p(b_p(x))$. Comparisons involving omitted zero-valuation classes are also satisfied.

7. Output and encoding bounds

The encoding analysis is sound. Raising $\nu$ to the integer power $h$, forming the accuracy parameters, rounding on the rational lattice, and constructing the quadratic coefficients all require polynomial encoding length and arithmetic time.

The transport program has at most $\tau m$ variables. Its exact rational solution has polynomial encoding length under the cited theorem. Summing its coordinates produces rational bundles with polynomial encoding length, and those same transports exhaust their induced bundles and attain their valuations.

The argument accommodates zero utilities, a single class, and unrestricted positive total supply. No infeasibility branch is needed because the construction succeeds on every valid input.

Feedback to the prover: No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩