Answer: Both the total-subsidy and maximum-subsidy decision problems are in \(\mathrm P\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf the valuations are doubly monotone or n = 2, there exists an envy-free allocation with a subsidy (A, p) such that maxn i=1 pi ≤n−1 and Pn i=1 pi ≤Pn ℓ=1(n−ℓ) = n(n −1)/2. Moreover, such an envy-free allocation with a subsidy can be computed in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses over finitely many complete monotone additive valuation types, integral bundle classes built from repeated indivisible item copies with rational masses, and a baseline type–bundle incidence promised to be EF1, choose a mass-preserving reassignment of bundle classes and nonnegative subsidies for occupied type–bundle pairs so that every recipient weakly prefers its subsidized bundle to every other occupied recipient's bundle, minimizing total mass-weighted subsidy or maximum subsidy, and determine whether Theorem 1-style polynomial-time bounds hold.
A society is given by its support: the list of \(\tau\) valuation types with positive binary-rational masses \(a_t\), with \(\sum_t a_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) item kinds, with arbitrarily repeated indivisible copies. Type \(t\) has complete monotone additive valuations given by rational per-copy values \(v_{te}\in[0,1]\). There are \(k\geq1\) distinct bundle classes \(b_j\in\mathbb Z_{\geq0}^{m}\), encoded in binary, with positive binary-rational masses \(c_j\) summing to one; empty bundles are permitted.
An input baseline incidence \(x^0_{tj}\geq0\), encoded as binary rationals, has row sums \(a_t\) and column sums \(c_j\). It is promised EF1: for every two occupied pairs \((t,j),(u,h)\), type \(t\) weakly prefers \(b_j\) to \(b_h\) after removing at most one copy from \(b_h\).
A reassignment is a nonnegative real incidence \(x\) with the same row and column sums. Mass may split among classes, but each recipient receives one intact bundle; bundle contents cannot change. Assign a nonnegative real per-recipient subsidy \(p_{tj}\) to each occupied pair, requiring \(v_t(b_j)+p_{tj}\geq v_t(b_h)+p_{uh}\) whenever \(x_{tj}>0\) and \(x_{uh}>0\); ties are allowed.
For the chosen objective, minimize either \(\sum_{t,j:x_{tj}>0}x_{tj}p_{tj}\) or \(\max_{t,j:x_{tj}>0}p_{tj}\). Given a nonnegative binary-rational budget \(B\), the decision problem asks whether the chosen objective can be at most \(B\).
For each objective, is this decision problem in \(\mathrm P\), or is it NP-hard? State running times in \(m,\tau,k,L\), where \(L\) is the total input bit length.
For finite societies with normalized doubly monotone valuations, an EF1 allocation can be permuted in polynomial time to achieve envy-freeness with maximum subsidy at most \(n-1\) and total subsidy at most \(n(n-1)/2\); this is a guarantee, not a global subsidy-minimization theorem. [Kawase et al.](https://arxiv.org/pdf/2308.11230)
No result settling the exact mass-incidence problem above was located.
Both decision problems are in \(\mathrm P\). Each reduces exactly to feasibility of a rational linear program with \(\tau k+\tau+k\) variables and \(O(\tau k+\tau+k)\) constraints.
The argument permits mass splitting and preserves every bundle intact. It also applies without the EF1 promise.
Write \(V_{tj}=v_t(b_j)=\sum_{e=1}^{m}v_{te}b_{je}\).
Suppose \((x,p)\) is feasible and envy-free. If \(x_{tj}>0\) and \(x_{uj}>0\), comparing these two occupied pairs in both directions gives
\(V_{tj}+p_{tj}\ge V_{tj}+p_{uj}\), and \(V_{uj}+p_{uj}\ge V_{uj}+p_{tj}\).
Consequently, \(p_{tj}=p_{uj}\). Thus every recipient of class \(j\) receives the same subsidy, denoted \(q_j\). Since \(c_j>0\), every class has a recipient, so every \(q_j\) is defined.
Similarly, all occupied pairs of a fixed type \(t\) have the same subsidized utility: applying envy-freeness in both directions to \((t,j)\) and \((t,h)\) gives
\(V_{tj}+q_j=V_{th}+q_h\).
Denote this utility by \(U_t\). It is defined because \(a_t>0\).
For every class \(h\), choose an occupied pair receiving that class. Envy-freeness then implies
\(U_t\ge V_{th}+q_h\).
For every occupied pair, equality holds:
\(x_{tj}>0\ \Longrightarrow\ U_t=V_{tj}+q_j\).
Consider real variables \(x_{tj}\), \(U_t\), and \(q_j\), subject to:
Every constraint is linear. In particular, the last equality contains no product of variables.
Claim. Feasible solutions of this system correspond exactly to envy-free reassignments with nonnegative subsidies.
Forward direction. Given an envy-free reassignment, construct \(q_j\) and \(U_t\) as in Section 1. The first five constraints hold. Because \(U_t=V_{tj}+q_j\) on occupied pairs,
\(\sum_ta_tU_t=\sum_{t,j}x_{tj}U_t=\sum_{t,j}x_{tj}(V_{tj}+q_j)=\sum_{t,j}V_{tj}x_{tj}+\sum_jc_jq_j\).
This proves the last equality.
Reverse direction. Given a feasible solution of the linear system, define the nonnegative slack
\(s_{tj}=U_t-q_j-V_{tj}\ge0\).
Using the marginal constraints and the last equality yields
\(\sum_{t,j}x_{tj}s_{tj}=\sum_ta_tU_t-\sum_jc_jq_j-\sum_{t,j}V_{tj}x_{tj}=0\).
Every summand is nonnegative. Therefore, whenever \(x_{tj}>0\), we have \(s_{tj}=0\), hence \(U_t=V_{tj}+q_j\).
Assign \(p_{tj}=q_j\) on every occupied pair. For any two occupied pairs \((t,j)\) and \((u,h)\),
\(V_{tj}+p_{tj}=U_t\ge V_{th}+q_h=V_{th}+p_{uh}\).
This is exactly the required envy-freeness condition. The marginal constraints ensure that the reassignment preserves every class’s mass. ∎
For any envy-free solution, the total subsidy equals
\(\sum_{t,j:x_{tj}>0}x_{tj}p_{tj}=\sum_jq_j\sum_tx_{tj}=\sum_jc_jq_j\).
Thus, for the total-subsidy decision problem, append the single inequality
\(\sum_jc_jq_j\le B\).
Since every class is occupied, the maximum subsidy equals
\(\max_{t,j:x_{tj}>0}p_{tj}=\max_jq_j\).
Thus, for the maximum-subsidy decision problem, append
\(q_j\le B\) for every \(j\).
By the equivalence proved above, each resulting rational linear system is feasible if and only if the corresponding decision instance is a yes-instance. This proves the reduction for both objectives.
The formulation also explains why it works. Consider the transportation LP
\(\max\sum_{t,j}V_{tj}x_{tj}\),
subject to nonnegativity and the prescribed row and column sums. Its dual is
\(\min\bigl(\sum_ta_tU_t-\sum_jc_jq_j\bigr)\),
subject to \(U_t-q_j\ge V_{tj}\), with \(U_t,q_j\) unrestricted.
The transportation LP is feasible because \(x^0\) has the required marginals. It is bounded because \(x_{tj}\ge0\), \(\sum_{t,j}x_{tj}=1\), and all \(V_{tj}\) are finite. Strong duality therefore gives attained primal and dual optima with equal values. This is the standard finite-dimensional LP duality theorem; see [MIT’s duality notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/b23096080e3d2142c3c8337bdcd9d3c7_lect9_19.pdf).
A common shift \(U_t\mapsto U_t+C\), \(q_j\mapsto q_j+C\) preserves every dual constraint and changes the dual objective by
\(C\bigl(\sum_ta_t-\sum_jc_j\bigr)=0\).
Choosing \(C=-\min_jq_j\) makes all class subsidies nonnegative. The shifted dual optimum and a primal optimum therefore satisfy the system in Section 2.
Consequently:
Both subsidy minima are attained. For total subsidy, minimize \(\sum_jc_jq_j\) over the system. For maximum subsidy, add a variable \(z\), impose \(z\ge q_j\) for every \(j\), and minimize \(z\). These are nonempty rational LPs with objectives bounded below by zero.
Let \(N=\tau k+\tau+k\).
Each derived value \(V_{tj}\) has \(O(L)\) bits. To see this, write \(v_{te}=r_{te}/d_{te}\) and use the common denominator \(D_t=\prod_ed_{te}\). Its bit length is at most the sum of the input denominator lengths. The numerator
\(\sum_er_{te}b_{je}(D_t/d_{te})\)
also has \(O(L)\) bits: each factor comes from the input or from \(D_t\), and summation contributes only \(O(\log m)\) additional bits.
Computing all values by elementary exact rational arithmetic takes \(O(m\tau kL^2)\) bit operations. The decision LP has exactly \(N\) variables and \(O(N)\) constraints; a dense encoding has length \(O(N^2L)\).
Rational LP feasibility is decidable exactly in time polynomial in its binary encoding length; this standard bit-complexity guarantee is recalled in [Dadush et al., Section 1](https://link.springer.com/article/10.1007/s10107-023-01956-2). Hence a valid running-time bound for either objective is
\(O(m\tau kL^2)+\bigl((\tau k+\tau+k)^2L\bigr)^{O(1)}\)
bit operations.
This bound depends on the listed support size \(\tau\) and the binary descriptions of the bundles. It requires neither enumerating possible valuation types nor expanding repeated copies. Empty bundles and the cases \(m=1\), \(\tau=1\), or \(k=1\) are covered by the same proof.
⟨structured verdict parsed — rendered above⟩
The prover resolves both assigned decision problems correctly: both are in \(\mathrm P\). The linear formulation is exact, both budget constraints are correct, and the stated running time is polynomial in the binary input length. I found no mathematical gaps requiring repair.
The comparisons in Section 1 are valid under the task’s envy-freeness condition. For occupied pairs \((t,j)\) and \((u,j)\), both recipients receive the same bundle, so the bundle-value terms cancel in each comparison. This gives \(p_{tj}\ge p_{uj}\) and \(p_{uj}\ge p_{tj}\), hence equality.
The assumption \(c_j>0\), together with the column-sum constraint and nonnegativity of incidence, guarantees an occupied pair in every class. Thus every \(q_j\) is defined.
Likewise, the two comparisons between occupied pairs of the same type give equality of subsidized utilities. Since \(a_t>0\), every type has an occupied pair, so every \(U_t\) is defined.
Finally, comparing any occupied pair of type \(t\) with an occupied recipient of class \(h\) gives \(U_t\ge V_{th}+q_h\). This holds for every type and every class, including pairs with zero incidence.
Assessment: Correct, with all required positivity hypotheses supplied by the task.
All six displayed constraints are linear. In particular, \(a_t\), \(c_j\), and \(V_{tj}\) are fixed input-derived coefficients. The final equality contains no product of decision variables.
Forward direction. The calculation uses the row and column sums correctly. Terms with zero incidence contribute zero, so equality of utility on occupied pairs suffices to establish the final equality.
Reverse direction. Each slack \(s_{tj}=U_t-q_j-V_{tj}\) is nonnegative. The marginal constraints and final equality imply that the finite sum \(\sum_{t,j}x_{tj}s_{tj}\) is zero. Since each summand is nonnegative, every occupied pair has zero slack.
Assigning \(p_{tj}=q_j\) therefore satisfies the required envy-freeness comparison for every ordered pair of occupied pairs. Nonnegative subsidies follow from \(q_j\ge0\).
This also handles the strict occupancy condition \(x_{tj}>0\) exactly; the proof does not replace it with a stronger condition on unoccupied pairs.
Assessment: Correct. This is the central equivalence, and neither direction has a gap.
For total subsidy, constant subsidies within a class and the prescribed column sums give precisely \(\sum_jc_jq_j\). Adding \(\sum_jc_jq_j\le B\) therefore represents the requested budget.
For maximum subsidy, every class is occupied because \(c_j>0\). Consequently, the maximum over occupied pairs is exactly \(\max_jq_j\), and the inequalities \(q_j\le B\) represent the budget exactly.
Both reductions preserve the non-strict budget comparison, including \(B=0\).
Assessment: Correct for both objectives.
The transportation dual is written correctly: using unrestricted row potentials \(U_t\) and column potentials \(-q_j\) gives the displayed constraints and objective.
The hypotheses for strong duality are verified:
The conclusion that primal and dual optima are attained with equal values is a valid application of finite-dimensional LP duality. The cited [MIT duality notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/b23096080e3d2142c3c8337bdcd9d3c7_lect9_19.pdf) support this use.
The common shift preserves every dual constraint. Its objective change is zero because both sets of masses sum to one. Choosing \(C=-\min_jq_j\) makes all class subsidies nonnegative.
The subsequent welfare claims also follow from the previously established zero-gap calculation. In particular, any primal optimum and any dual optimum have equal objective values, so their nonnegative weighted slacks vanish on occupied pairs.
Finally, the subsidy minimization LPs are nonempty and have objectives bounded below. The standard LP attainment property applies even though their feasible regions need not be bounded.
Assessment: Correct. This section establishes the claimed additional properties; the decision reductions already stand independently.
The derived coefficient-size bound is valid. The product denominator \(D_t\) has bit length bounded by the sum of the input denominator lengths. Each numerator term has \(O(L)\) bits, and summing \(m\) terms adds at most \(O(\log m)\) bits. Thus \(V_{tj}\) has \(O(L)\) bits despite binary-encoded bundle multiplicities.
The bound \(O(m\tau kL^2)\) for constructing all values is a valid conservative bound using elementary exact arithmetic on numbers of \(O(L)\) bits.
The decision formulation has exactly \(N=\tau k+\tau+k\) variables. Before adding the budget, counting each equality as one constraint gives \(2\tau k+\tau+2k+1\) constraints. Either budget adds only \(O(k)\) constraints, so the claimed \(O(N)\) count is correct. A dense encoding of length \(O(N^2L)\) is also valid.
The invoked theorem is polynomial-time feasibility for rational linear systems in their binary encoding length. Its rationality and finite-size hypotheses hold here. Section 1 of the cited [Dadush et al. article](https://link.springer.com/article/10.1007/s10107-023-01956-2) recalls the polynomial bit-complexity guarantee.
Therefore, the stated bound
\(O(m\tau kL^2)+((\tau k+\tau+k)^2L)^{O(1)}\)
is valid for both decision problems.
Assessment: Correct. This establishes polynomial bit complexity, without claiming a strongly polynomial algorithm.
The proof uses the listed support size \(\tau\), permits real mass splitting, and preserves each bundle class and its mass. It does not expand repeated copies.
Empty bundles merely give zero derived values in their columns. The cases \(m=1\), \(\tau=1\), and \(k=1\) do not invalidate any step. Positive masses ensure that the utilities and class subsidies remain defined in these cases.
The EF1 promise is unnecessary for this argument, as the prover states. Its omission therefore strengthens the result without changing the assigned problem.
Required clarification or repair: None.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.