Answer: Polynomial-time solvable
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet e ≡(N, A, v, r), b ≡(bi)i∈N, and, for s ∈[t], where t is polynomial in n, let fs : Rn →R be a linear function. Then there is a polynomial-time algorithm that determines whether Fb(e) ̸= ∅, and, if so, outputs an allocation (σ, p) ∈Fb(e) that maximizes min s∈[t] fs v1σ(1) −pσ(1), . . . , vnσ(n) −pσ(n) over all allocations in Fb(e). Gal et al.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational resident-type masses \(\mu_t\), room-class supplies \(\lambda_a\) with each summing to one, values \(v_{ta}\), budgets \(b_t\), per-capita rent \(R\), and rational linear objectives \(\ell_s\), decide whether there are prices \(p_a\) and assignment masses \(x_{ta}\ge 0\) such that \(\sum_a x_{ta}=\mu_t\), \(\sum_t x_{ta}=\lambda_a\), and \(\sum_a\lambda_a p_a=R\). For every \(x_{ta}>0\), require \(p_a\le b_t\) and \(v_{ta}-p_a\ge v_{tb}-p_b\) for every room class \(b\); then, if feasible, maximize \(\min_s\ell_s(u)\), where \(u_t=v_{ta}-p_a\) for any class assigned positive mass to type \(t\). Determine whether this can be done in time polynomial in the number of types, room classes, and input bit length.
A society is given by its support: a list of \(\tau\ge1\) resident types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) room classes with positive binary-rational supplies \(\lambda_a\), summing to \(1\). Values \(v_{ta}\), finite budgets \(b_t\), and per-capita rent \(R\) are arbitrary signed rationals, with no valuation normalization.
The input also explicitly lists \(k\ge1\) rational linear functions \(\ell_s:\mathbb R^\tau\to\mathbb R\); let \(L\) be the total binary input length.
An allocation consists of real class prices \(p_a\) and assignment masses \(x_{ta}\ge0\), satisfying \(\sum_a x_{ta}=\mu_t\), \(\sum_t x_{ta}=\lambda_a\), and \(\sum_a\lambda_a p_a=R\); negative prices are allowed.
Whenever \(x_{ta}>0\), require \(p_a\le b_t\) and \(v_{ta}-p_a\ge v_{tc}-p_c\) for every class \(c\), including unaffordable classes. Indifference permits splitting mass; these inequalities give each type a well-defined utility \(u_t=v_{ta}-p_a\) on all positively assigned classes.
The computational problem is to decide feasibility and, when feasible, compute an allocation maximizing \(\min_{1\le s\le k}\ell_s(u)\).
Is this feasibility-and-exact-optimization problem solvable in time polynomial in \(m,\tau,k,L\), or is it NP-hard?
For discrete bijective assignments, budget-constrained envy-free feasibility and optimization of a minimum of explicitly given linear utility functions are polynomial-time solvable ([Procaccia–Velez–Yu](https://procaccia.info/wp-content/uploads/2020/03/rent-budget.pdf)).
A different fractional model has polynomial-time feasibility with individual rationality, agent payments, and envy comparisons between entire fractional bundles ([Airiau et al.](https://www.lamsade.dauphine.fr/~lang/papers/airiau23a.pdf)); it does not impose the class-price and positive-assignment conditions above. No result settling this exact mass model was located.
The feasibility-and-exact-optimization problem is solvable in polynomial time in \(m,\tau,k,L\). Whenever feasible, it has a rational optimal allocation of polynomial encoding length.
The proof uses a component decomposition analogous to the discrete decomposition in [Procaccia–Velez–Yu, Section 3](https://procaccia.info/wp-content/uploads/2020/03/rent-budget.pdf), but establishes the required properties directly for the stated mass model.
Let \(\mathcal X\) be the transportation polytope consisting of all nonnegative matrices \(x\) with row sums \(\mu_t\) and column sums \(\lambda_a\). It is nonempty: \(x_{ta}=\mu_t\lambda_a\) belongs to it. It is compact because every coordinate satisfies \(0\le x_{ta}\le\mu_t\).
Consider the maximum-value transportation problem
\(\displaystyle W=\max_{x\in\mathcal X}\sum_{t,a}v_{ta}x_{ta}.\)
Its linear-programming dual is
\(\displaystyle \min_{u,p}\left(\sum_t\mu_tu_t+\sum_a\lambda_ap_a\right),\qquad u_t+p_a\ge v_{ta}\quad\text{for all }t,a,\)
where \(u,p\) are unrestricted in sign. The primal has a finite attained optimum, so strong duality gives an attained dual optimum with value \(W\).
For any primal-feasible \(x\) and dual-feasible \((u,p)\), their objective gap is
\(\displaystyle \sum_t\mu_tu_t+\sum_a\lambda_ap_a-\sum_{t,a}v_{ta}x_{ta} =\sum_{t,a}x_{ta}(u_t+p_a-v_{ta}).\)
Every summand on the right is nonnegative.
Suppose first that an allocation satisfies the problem’s envy conditions, temporarily ignoring budgets. Since \(\mu_t>0\), each type receives some class, and its utility is
\(\displaystyle u_t=\max_a(v_{ta}-p_a).\)
Consequently, \((u,p)\) is dual-feasible, and every positively assigned edge satisfies \(u_t+p_a=v_{ta}\). The gap identity therefore vanishes. Both \(x\) and \((u,p)\) are optimal.
Conversely, take any optimal transportation \(x\) and any optimal dual pair \((u,p)\). Their gap is zero, so
\(\displaystyle x_{ta}>0\ \Longrightarrow\ u_t+p_a=v_{ta}.\)
Together with all the dual inequalities, this gives exactly the required envy conditions. Because each type has positive mass, its assigned utility equals \(\max_a(v_{ta}-p_a)\).
Thus every optimal transportation is compatible with every optimal dual pair, before imposing budgets and rent.
Define
\(\displaystyle E^\star=\{(t,a):x_{ta}>0\text{ for some optimal transportation }x\}.\)
Every optimal transportation is supported on \(E^\star\). Moreover, every optimal dual pair satisfies
\(\displaystyle u_t+p_a=v_{ta}\qquad\text{for every }(t,a)\in E^\star.\)
Indeed, for a given edge in \(E^\star\), choose an optimal transportation positive on that edge and apply the gap identity.
Fix a rational optimal dual pair \((u^0,p^0)\), normalized so that
\(\displaystyle \sum_a\lambda_ap^0_a=0.\)
Such normalization is possible: adding a constant to all prices and subtracting it from all utilities preserves the constraints and dual objective, because both total masses equal \(1\).
Form the undirected bipartite graph with type vertices, class vertices, and edge set \(E^\star\). Let its connected components be \(\mathcal C\). For a component \(C\), denote its type vertices by \(T_C\), its class vertices by \(A_C\), and its edges by \(E_C\).
Every vertex is incident to an edge: any optimal transportation must meet all the strictly positive marginals. Each component is therefore nonempty on both sides.
A fixed optimal transportation has no positive entries between different components. Summing its row and column equations within \(C\) gives
\(\displaystyle w_C:=\sum_{t\in T_C}\mu_t=\sum_{a\in A_C}\lambda_a>0.\)
Also, \(\sum_{C\in\mathcal C}w_C=1\).
Let \((u,p)\) be any optimal dual pair. For every edge in \(E^\star\),
\(\displaystyle (u_t-u^0_t)+(p_a-p^0_a)=0.\)
Following paths in a connected component shows that there is one scalar \(d_C\) such that
\(\displaystyle p_a=p^0_a+d_C\quad(a\in A_C),\qquad u_t=u^0_t-d_C\quad(t\in T_C).\)
Write \(C(t)\) and \(C(a)\) for the components containing a type or class. Define the nonnegative reference slacks
\(\displaystyle \sigma_{ta}=u^0_t+p^0_a-v_{ta}.\)
For prices and utilities of the preceding form, dual feasibility is equivalent to
\[\displaystyle d_{C(t)}-d_{C(a)}\le\sigma_{ta}\qquad\text{for all }t,a.\tag{1}\]
Conversely, any component shifts satisfying (1) give an optimal dual pair. They give a feasible pair, and its objective equals
\(\displaystyle W+\sum_Cd_C\left(\sum_{a\in A_C}\lambda_a-\sum_{t\in T_C}\mu_t\right)=W,\)
by component balance.
The prescribed rent becomes
\[\displaystyle \sum_Cw_Cd_C=R,\tag{2}\]
using the normalization of \(p^0\).
Thus all envy-free price and utility vectors are described by the linear conditions (1) and (2). Budgets remain to be incorporated.
For an edge \((t,a)\in E_C\), define its affordability threshold
\(\displaystyle h_{ta}=b_t-p^0_a.\)
At component shift \(d_C=d\), this edge is affordable exactly when \(d\le h_{ta}\).
For a real number \(d\), let
\(\displaystyle E_C(d)=\{(t,a)\in E_C:h_{ta}\ge d\}.\)
Call \(d\) *locally feasible* if a nonnegative transportation supported on \(E_C(d)\) has row sums \((\mu_t)_{t\in T_C}\) and column sums \((\lambda_a)_{a\in A_C}\).
These conditions concern only assignments and budgets. The full envy inequalities remain in (1).
Let
\(\displaystyle H_C=\{h_{ta}:(t,a)\in E_C\}.\)
This is a finite, nonempty set. At \(d=\min H_C\), every edge of \(E_C\) is affordable, and the restriction of any optimal transportation witnesses local feasibility. Define
\(\displaystyle B_C=\max\{h\in H_C:h\text{ is locally feasible}\}.\)
The maximum therefore exists. Retain a witnessing transportation \(y^C\) supported on \(E_C(B_C)\).
Claim. A real shift \(d\) is locally feasible if and only if \(d\le B_C\).
Proof. If \(d\le B_C\), then \(E_C(B_C)\subseteq E_C(d)\), so the fixed transportation \(y^C\) remains feasible.
Conversely, suppose \(d>B_C\) were locally feasible. Its permitted edge set cannot be empty because the component has positive mass. Hence there exists a smallest threshold \(h^\star\in H_C\) satisfying \(h^\star\ge d\). By its minimality,
\(\displaystyle E_C(d)=E_C(h^\star).\)
Thus \(h^\star\) would be a locally feasible threshold larger than \(B_C\), contradicting the definition of \(B_C\). This proves the claim.
All budgets in a component are consequently captured by the single linear inequality
\[\displaystyle d_C\le B_C.\tag{3}\]
The witness \(y^C\) works at every shift satisfying this inequality.
Introduce a real objective variable \(z\). Solve the following rational linear program:
\(\displaystyle \text{maximize }z,\)
subject to
\(\displaystyle d_{C(t)}-d_{C(a)}\le\sigma_{ta}\qquad\text{for all }t,a,\)
\(\displaystyle \sum_Cw_Cd_C=R,\)
\(\displaystyle d_C\le B_C\qquad\text{for all }C,\)
\[\displaystyle z\le\ell_s\!\left((u^0_t-d_{C(t)})_{t=1}^{\tau}\right) \qquad\text{for }s=1,\ldots,k.\tag{4}\]
These are linear constraints because every \(\ell_s\) is explicitly given and linear.
Take any feasible allocation \((x,p)\), with utilities \(u\). Section 1 shows that \(x\) and \((u,p)\) are optimal for the transportation primal and dual.
Section 3 therefore supplies component shifts satisfying (1) and the rent equation (2). The assignment \(x\) is supported on \(E^\star\). Its restriction to each component is affordable at shift \(d_C\), so Section 4 gives \(d_C\le B_C\).
Hence these shifts, together with
\(\displaystyle z=\min_s\ell_s(u),\)
are feasible for (4).
Conversely, take shifts feasible for (4). Set
\(\displaystyle p_a=p^0_a+d_{C(a)},\qquad u_t=u^0_t-d_{C(t)}.\)
Construct \(x\) by combining the retained local transportations \(y^C\), with zero entries between different components. Its row and column marginals are the required ones.
If \(x_{ta}>0\), then \((t,a)\in E_C(B_C)\), and therefore
\(\displaystyle p_a=p^0_a+d_C\le p^0_a+B_C\le b_t.\)
Also, every edge of \(E^\star\) is tight at the reference pair, and both endpoints receive the same component shift. Thus
\(\displaystyle x_{ta}>0\ \Longrightarrow\ u_t+p_a=v_{ta}.\)
The first constraints of (4) give \(u_t+p_c\ge v_{tc}\) for every class \(c\), including unaffordable classes. This verifies exactly the task’s positive-assignment and envy requirements. The rent equation also holds.
The reconstructed allocation has utility vector \(u\), and its objective is at least \(z\). Together with necessity, this proves that the LP’s optimum equals the original problem’s optimum and that reconstruction yields an optimal allocation. LP infeasibility is equivalent to allocation infeasibility.
Every \(B_C\) is finite because all budgets and reference prices are finite. The upper bounds and rent equation imply the lower bounds
\(\displaystyle d_C\ge \frac{R-\sum_{D\ne C}w_DB_D}{w_C}.\)
Here \(w_C>0\). The feasible shift set is therefore closed and bounded. When nonempty, the continuous function
\(\displaystyle d\longmapsto\min_s\ell_s\!\left((u^0_t-d_{C(t)})_t\right)\)
attains a finite maximum.
We use the standard rational linear-programming theorem: feasibility and finite attained optima can be computed exactly in polynomial time, with rational outputs of polynomial encoding length.
All the required computations have polynomial size:
\(\displaystyle \max x_{ta}\quad\text{subject to }x\in\mathcal X,\quad\sum_{r,c}v_{rc}x_{rc}=W.\)
The edge belongs to \(E^\star\) exactly when this optimum is positive. These LPs optimize over a nonempty compact face, and positivity is tested exactly.
Every auxiliary LP has polynomial dimensions. The intermediate rational numbers—including \(W,u^0,p^0,w_C,h_{ta},B_C\)—have polynomial encoding length, so the final LP does too. Its optimal shifts and the retained local transportations give rational prices and assignment masses of polynomial encoding length.
All computations use the encoded masses directly. No expansion by a common denominator is required, and no valuation normalization or sign restriction is used.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves feasibility and exact optimization for the stated mass model. I found no major or minor mathematical issues. The component budget reduction is valid, and the algorithm has polynomial bit complexity.
1. Transportation duality and envy-freeness
The transportation polytope is nonempty: the proposed matrix \(x_{ta}=\mu_t\lambda_a\) has the required marginals because both total masses equal \(1\). Nonnegativity, closedness, and the coordinate bounds establish compactness. Signed valuations do not affect these facts.
The displayed dual is correct. Its variables are unrestricted because the primal marginal constraints are equalities. The primal has a finite attained optimum, so the application of linear-programming strong duality, including dual attainment, is justified.
The objective-gap identity follows directly from the marginal equations. Every summand is nonnegative under primal and dual feasibility.
For an envy-free allocation, positive type mass guarantees an assigned class. The envy inequalities imply that all positively assigned classes attain \(u_t=\max_a(v_{ta}-p_a)\). Consequently, the constructed dual pair is feasible and the gap vanishes.
Conversely, for any optimal primal solution and any optimal dual solution, the gap vanishes. Nonnegative summands then force equality on every positive assignment. This verifies both the universal compatibility claim and envy comparisons against unaffordable classes. Budgets and prescribed rent are correctly deferred.
2. Optimal-support graph
The definition of \(E^\star\) uses existence of an optimal transportation positive on an edge. Applying the preceding gap identity to such a witness proves that every optimal dual pair is tight on that edge. This argument correctly handles the quantifier “every optimal dual pair.”
Strictly positive marginals ensure that every vertex has an incident edge. Thus each connected component contains both types and classes.
Any fixed optimal transportation has support contained in \(E^\star\), so it has no positive assignments between distinct components. Summing its marginal equations within a component establishes the claimed balance and \(w_C>0\). No integrality or equal-mass assumption is used.
3. Component shifts and rent
The normalization of the reference dual pair is valid: adding a common constant to prices and subtracting it from utilities preserves feasibility and the objective because both total masses are \(1\). Rationality is preserved.
Subtracting tight-edge equalities gives the displayed relation between utility and price differences. Connectivity then gives exactly one price shift per component, with the opposite utility shift.
The sign in condition (1) is correct: substituting the component shifts into dual feasibility yields \(d_{C(t)}-d_{C(a)}\le \sigma_{ta}\).
The converse is also established. These inequalities give dual feasibility, while component balance makes the objective change zero. Hence the resulting pair is optimal.
The rent equation correctly becomes \(\sum_C w_Cd_C=R\). This characterizes the possible envy-free price and utility vectors before budgets.
4. Budget reduction
Affordability on a component edge is exactly \(d_C\le b_t-p_a^0\), including equality. The permitted edge sets therefore decrease monotonically with the shift.
The finite set \(H_C\) is nonempty. Its minimum permits every component edge, and restricting an optimal transportation supplies a feasible witness. Thus \(B_C\) exists and is finite.
Both directions of the local-feasibility claim are valid:
This verifies the central reduction to one upper bound per component. It allows the affordable transportation to change with prices; it does not assume that one arbitrarily selected optimal transportation satisfies all feasible budgets.
5. Final LP and reconstruction
Necessity is complete. Every feasible allocation supplies optimal primal and dual solutions, component shifts, the rent equation, locally affordable component assignments, and the objective constraints.
Sufficiency is also complete. Combining the retained local witnesses gives the required marginals. The upper bounds ensure affordability of every positive assignment. Tightness of component edges and the global dual inequalities establish exactly the required envy conditions. The rent equation is preserved.
The objective comparison is sufficient to prove equality of optima: every original allocation produces an LP point with its exact objective, while every LP point reconstructs an allocation with objective at least \(z\). Reconstruction at an LP optimum therefore yields an optimal original allocation.
Because \(k\ge1\) and all function values are finite, any feasible shift vector admits a feasible \(z\). Thus inclusion of the objective constraints does not alter the feasibility equivalence.
6. Attainment and edge cases
The displayed lower bound follows correctly from the rent equality, the positive weights, and all other component upper bounds. Consequently, the feasible shift set is closed and bounded.
The minimum of finitely many linear functions is continuous, so the claimed finite maximum is attained whenever the shift set is nonempty. The LP variable \(z\) being unbounded below does not affect this conclusion.
The argument covers single-type, single-class, and single-component instances. Arbitrary signed valuations, budgets, rents, and objective coefficients introduce no excluded cases. Negative prices remain permitted throughout. Equality at affordability thresholds is handled correctly.
7. Polynomial bit complexity
The stated rational linear-programming theorem applies to all proposed computations:
The intermediate quantities have polynomial encoding length. Normalization, threshold formation, component-weight summation, and substitution into the explicitly listed linear functions preserve polynomial encoding length. The retained witnesses and final optimal shifts consequently yield rational prices and assignments of polynomial encoding length.
No expansion by denominators occurs. The running-time claim therefore concerns the binary input representation required by the task.
The comparison with [Procaccia–Velez–Yu, Section 3](https://procaccia.info/wp-content/uploads/2020/03/rent-budget.pdf) is contextual; the mass-model decomposition is established directly rather than imported from its discrete theorem.
Required feedback: none. No missing lemma, unjustified theorem application, or blocking issue was identified.
⟨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.