Multi-Apartment Rent Division (aaai25-33538)

Given rational type masses \(\mu_t\), room-class capacities \(\rho_{jb}\), values \(v_t(j,b)\), per-capita rents \(R_j\), and polynomially many rational linear objectives, choose configuration masses \(z_{t,\mathbf b}\) for \(\mathbf b=(b_1,\ldots,b_m)\), welfare-maximizing apartment-wise marginals, class prices \(p_{jb},q_{jb}\), and a chosen apartment \(j^\star\). Require \(\sum_{\mathbf b}z_{t,\mathbf b}=\mu_t\), \(\sum_{t,\mathbf b:b_j=b}z_{t,\mathbf b}=\rho_{jb}\), valid rent totals for \(p\) and \(q\), consensus and individual envy-freeness on every positive-mass configuration, and \(\sum_j p_{j,b_j}=\sum_j q_{j,b_j}\) on every such configuration; maximize \(\min_{\ell\in[s]}f_\ell(\mathbf u)\) over the resulting selected-apartment utilities.

A society is given by its support: a list of \(\tau\) types with positive binary rational masses \(\mu_t\), with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) apartments; apartment \(j\) has \(k_j\ge1\) room classes, with rational capacities \(\rho_{jb}>0\) summing to \(1\). Values \(v_t(j,b)\) and per-capita rents \(R_j\) are nonnegative rationals, normalized by \(\sum_{j,b}\rho_{jb}v_t(j,b)=\sum_jR_j\) for every type. Let \(L\) be the total input bit length.
Choose nonnegative real configuration masses \(z_{t,\mathbf b}\), where \(\mathbf b\in\prod_j\{1,\ldots,k_j\}\), satisfying \(\sum_{\mathbf b}z_{t,\mathbf b}=\mu_t\) and \(\sum_{t,\mathbf b:b_j=b}z_{t,\mathbf b}=\rho_{jb}\). Define \(x^j_{tb}=\sum_{\mathbf b:b_j=b}z_{t,\mathbf b}\); each \(x^j\) must maximize \(\sum_{t,b}x^j_{tb}v_t(j,b)-R_j\) over nonnegative matrices with row sums \(\mu_t\) and column sums \(\rho_{jb}\).
Choose real class prices \(p_{jb},q_{jb}\), unrestricted in sign, and an apartment \(j^\star\), with \(\sum_b\rho_{jb}p_{jb}=\sum_b\rho_{jb}q_{jb}=R_j\) for every apartment.
For every \(z_{t,\mathbf b}>0\), require consensus \(v_t(j^\star,b_{j^\star})-p_{j^\star,b_{j^\star}}\ge v_t(j,b_j)-p_{j,b_j}\) for every \(j\), individual envy-freeness of the starting prices \(v_t(j,b_j)-q_{j,b_j}\ge v_t(j,c)-q_{jc}\) for every \(j,c\), and rent preservation \(\sum_jp_{j,b_j}=\sum_jq_{j,b_j}\). All comparisons are weak; any tied chosen apartment is allowed.
Define selected-apartment type utilities by \(u_t=\mu_t^{-1}\sum_{\mathbf b}z_{t,\mathbf b}[v_t(j^\star,b_{j^\star})-p_{j^\star,b_{j^\star}}]\). Given \(s\ge1\) rational linear functions \(f_\ell:\mathbb R^\tau\to\mathbb R\), with \(s\) polynomially bounded in the explicit input dimensions, maximize \(\min_{\ell\in\{1,\ldots,s\}}f_\ell(\mathbf u)\).

Is this continuous optimization problem solvable in time polynomial in \(m,\tau,\sum_jk_j,s,L\), or is it NP-hard?

For finite societies with one distinct room per player in each apartment, optimization of the minimum of polynomially many linear selected-player utility objectives under negotiated envy-freeness is polynomial-time solvable. [Procaccia, Schiffer, and Zhang](https://arxiv.org/html/2403.08051v2)
No result settling the continuous problem defined here was identified in the literature search.

NP-hardness with three types and three apartments

The problem is NP-hard, even when \(m=\tau=3\), \(s=1\), all values and rents are nonnegative integers bounded by \(4\), and every instance produced by the reduction is feasible.

We prove this by a polynomial-time reduction from PARTITION. The constructed instance has optimal value exactly \(3\) when the PARTITION instance is a YES-instance, and exactly \(7/3\) otherwise.

1. Construction

We use the NP-complete positive-integer PARTITION problem: given positive integers \(a_1,\ldots,a_n\), written in binary, decide whether some subset \(S\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in S}a_i=A/2\), where \(A=\sum_{i=1}^n a_i\). This is the standard PARTITION problem from [Karp’s NP-completeness theorem](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

There are three types, with masses

\[ \mu_1=\mu_2=\frac14,\qquad \mu_3=\frac12. \]

There are three apartments, each with rent \(R_j=2\). Their room classes are:

• Apartment \(1\): ordinary classes \(i\in\{1,\ldots,n\}\), with capacities \(\rho_{1i}=a_i/(2A)\), and a distinguished class \(d_1\), with capacity \(1/2\).
• Apartment \(2\): ordinary classes \(e_1,e_2\), each with capacity \(1/4\), and a distinguished class \(d_2\), with capacity \(1/2\).
• Apartment \(3\): an ordinary class \(c\), with capacity \(1/2\), and a distinguished class \(d_3\), with capacity \(1/2\).

Values are constant across the ordinary classes of an apartment:

| Type | Apartment \(1\), ordinary | \(d_1\) | Apartment \(2\), ordinary | \(d_2\) | Apartment \(3\), \(c\) | \(d_3\) |
|---|---:|---:|---:|---:|---:|---:|
| \(1\) | \(3\) | \(3\) | \(0\) | \(0\) | \(3\) | \(3\) |
| \(2\) | \(1\) | \(1\) | \(2\) | \(2\) | \(3\) | \(3\) |
| \(3\) | \(1\) | \(3\) | \(1\) | \(3\) | \(0\) | \(4\) |

We use the single linear objective \(f_1(\mathbf u)=u_3\).

All capacities and masses are positive and have the required totals. The normalization holds for types \(1\) and \(2\), because their values are room-independent within each apartment and

\[ 3+0+3=1+2+3=6=\sum_jR_j. \]

For type \(3\), the capacity-weighted value in each apartment is \(2\):

\[ \frac12(1)+\frac12(3)=2,\qquad \frac12(1)+\frac12(3)=2,\qquad \frac12(0)+\frac12(4)=2. \]

Thus its total normalized value is also \(6\).

2. Welfare maximization forces the distinguished assignments

Types \(1\) and \(2\) have room-independent values within each apartment. Consequently, their contributions to apartment welfare depend only on their row sums.

Let \(H_j=v_3(j,d_j)\) and let \(L_j\) be type \(3\)’s value for an ordinary class. Its value contribution in apartment \(j\) is

\[ H_jx^j_{3d_j}+L_j\left(\frac12-x^j_{3d_j}\right). \]

Here \(H_j>L_j\), and \(x^j_{3d_j}\leq1/2\). Assigning all type \(3\) mass to \(d_j\) is feasible: the remaining ordinary capacity is \(1/2\), exactly the combined mass of types \(1\) and \(2\).

Therefore, every welfare-maximizing marginal satisfies \(x^j_{3d_j}=1/2\). It follows that type \(3\) occupies only distinguished classes, while types \(1\) and \(2\) occupy only ordinary classes.

The resulting maximum net welfares are

\[ W_1=\frac14(3)+\frac14(1)+\frac12(3)-2=\frac12, \]

\[ W_2=\frac14(0)+\frac14(2)+\frac12(3)-2=0, \]

\[ W_3=\frac14(3)+\frac14(3)+\frac12(4)-2=\frac32. \]

These conclusions also hold configuration by configuration: a positive configuration mass cannot use an assignment whose marginal mass is zero.

3. Consensus forces selection of apartment \(3\)

For a positive configuration, write its utility in apartment \(j\) as \(U_j=v_t(j,b_j)-p_{j,b_j}\).

The population’s total utility in apartment \(j\) is

\[ \sum_{t,\mathbf b}z_{t,\mathbf b}U_j =\sum_{t,b}x^j_{tb}v_t(j,b)-\sum_b\rho_{jb}p_{jb} =W_j. \]

Consensus requires \(U_{j^\star}\geq U_j\) for every positive configuration. Multiplying these inequalities by configuration masses and summing gives \(W_{j^\star}\geq W_j\).

Since \(W_3\) is strictly largest, every feasible solution selects apartment \(3\).

Both ordinary types occupy its single ordinary class \(c\), where both have value \(3\). Thus their selected utilities coincide, configuration by configuration:

\[ u_1=u_2=u:=3-p_{3c}. \]

Type \(3\)’s selected utility is \(u_3=4-p_{3d_3}\). Apartment \(3\)’s budget equation gives \(p_{3c}+p_{3d_3}=4\), so

\[ u_3=3-u. \]

Maximizing the stated objective therefore amounts to minimizing \(u\).

4. Every feasible solution has \(u\geq0\)

Let \(c_j=\min_b q_{jb}\). Since the capacity-weighted mean starting price is \(2\), we have \(c_j\leq2\).

For either ordinary type, values within an apartment are room-independent. Starting-price envy-freeness therefore forces every assigned room to have starting price \(c_j\).

Fix any positive configuration of either ordinary type. Rent preservation and normalization imply

\[ \sum_{j=1}^3U_j =\sum_{j=1}^3v_t(j,b_j)-\sum_{j=1}^3q_{j,b_j} =6-\sum_{j=1}^3c_j=:D. \]

Because each \(c_j\leq2\), we have \(D\geq0\).

Consensus gives \(U_j\leq u\) for every apartment, while \(U_3=u\). Hence \(D\leq3u\), proving \(u\geq0\). In particular,

\[ u_3=3-u\leq3. \]

We also obtain a useful lower bound on every assigned utility. The other two apartment utilities are at most \(u\), so

\[ U_j=D-\sum_{h\neq j}U_h\geq D-2u\geq-2u. \]

Consequently, every assigned ordinary-type utility belongs to \([-2u,u]\).

5. If \(u<2/3\), the item capacities encode a partition

Suppose apartment \(1\)’s ordinary class \(i\) receives positive mass of type \(1\). Its value is \(3\), so the preceding utility bounds imply

\[ 3-u\leq p_{1i}\leq3+2u. \]

If the same class receives positive mass of type \(2\), whose value is \(1\), then

\[ 1-u\leq p_{1i}\leq1+2u. \]

A shared class would therefore require \(3-u\leq1+2u\), or \(u\geq2/3\).

Thus, when \(u<2/3\), no ordinary class of apartment \(1\) can be shared by types \(1\) and \(2\). Type \(3\) occupies only \(d_1\), so each ordinary class must be occupied entirely by one of the two ordinary types.

Let \(S\) be the classes occupied by type \(1\). Its mass constraint gives

\[ \sum_{i\in S}\frac{a_i}{2A}=\frac14, \]

equivalently, \(\sum_{i\in S}a_i=A/2\).

Therefore, if the PARTITION instance is a NO-instance, every feasible solution satisfies \(u\geq2/3\), and hence

\[ u_3\leq\frac73. \]

6. Every constructed instance has a feasible solution of value \(7/3\)

Set every starting price to \(q_{jb}=2\). Define configuration masses by

\[ z_{1,(i,e_1,c)}=\frac{a_i}{4A},\qquad z_{2,(i,e_2,c)}=\frac{a_i}{4A} \]

for each \(i\), and \(z_{3,(d_1,d_2,d_3)}=1/2\). Set all other masses to zero.

These masses have the required type and class marginals. They are welfare-maximizing by Section 2.

Use the following final prices, with the ordinary price applying to every ordinary class of the indicated apartment:

| Apartment | Ordinary final price | Distinguished final price |
|---|---:|---:|
| \(1\) | \(7/3\) | \(5/3\) |
| \(2\) | \(4/3\) | \(8/3\) |
| \(3\) | \(7/3\) | \(5/3\) |

Each apartment has ordinary and distinguished capacities \(1/2\), so its weighted final price is \(2\). Starting prices also satisfy the budgets.

Starting-price envy-freeness holds: ordinary types are indifferent among rooms within each apartment, and type \(3\) strictly prefers the distinguished class.

Every ordinary-type configuration has total final price \(7/3+4/3+7/3=6\). The distinguished configuration has total final price \(5/3+8/3+5/3=6\). Both equal the total starting price, proving rent preservation.

The configuration utilities are:

| Type | Apartment \(1\) | Apartment \(2\) | Apartment \(3\) |
|---|---:|---:|---:|
| \(1\) | \(2/3\) | \(-4/3\) | \(2/3\) |
| \(2\) | \(-4/3\) | \(2/3\) | \(2/3\) |
| \(3\) | \(4/3\) | \(1/3\) | \(7/3\) |

Apartment \(3\) satisfies all weak consensus inequalities. The objective value is \(7/3\).

Combined with Section 5, this proves that every NO-instance has optimum exactly \(7/3\).

7. A partition gives a feasible solution of value \(3\)

Suppose \(S\) satisfies \(\sum_{i\in S}a_i=A/2\). Define configuration masses by assigning:

• Mass \(a_i/(2A)\) to type \(1\)’s configuration \((i,e_1,c)\) for \(i\in S\).
• Mass \(a_i/(2A)\) to type \(2\)’s configuration \((i,e_2,c)\) for \(i\notin S\).
• Mass \(1/2\) to type \(3\)’s configuration \((d_1,d_2,d_3)\).

The partition identity ensures that both ordinary types have mass \(1/4\). All class capacities are filled, and all marginals maximize welfare.

Again use \(q_{jb}=2\). Set final prices as follows:

| Apartment | Ordinary final prices | Distinguished final price |
|---|---|---:|
| \(1\) | \(p_{1i}=3\) for \(i\in S\); \(p_{1i}=1\) otherwise | \(2\) |
| \(2\) | \(p_{2e_1}=0\), \(p_{2e_2}=2\) | \(3\) |
| \(3\) | \(p_{3c}=3\) | \(1\) |

The weighted price totals are

\[ \frac14(3)+\frac14(1)+\frac12(2)=2, \]

\[ \frac14(0)+\frac14(2)+\frac12(3)=2, \]

\[ \frac12(3)+\frac12(1)=2. \]

Starting-price envy-freeness holds as before. Every positive configuration has total final price \(6\): the totals are \(3+0+3\), \(1+2+3\), and \(2+3+1\). Thus rent preservation holds.

Both ordinary types have zero utility in every apartment. Type \(3\)’s utilities are \((1,0,3)\). Therefore apartment \(3\) satisfies consensus, and \(u_3=3\).

Section 4 already proved the upper bound \(u_3\leq3\), so every YES-instance has optimum exactly \(3\).

8. Complexity conclusion and relation to the finite result

The construction has \(m=\tau=3\), \(s=1\), and \(\sum_jk_j=n+6\). Its only nonconstant numerical entries are capacities \(a_i/(2A)\), whose binary encoding lengths are polynomial in the PARTITION input length.

We have proved the exact dichotomy:

• A YES-instance of PARTITION produces optimum \(3\).
• A NO-instance produces optimum \(7/3\).

Thus deciding whether a feasible solution has objective at least \(8/3\) is NP-hard. Exact polynomial-time optimization would imply \(\mathrm P=\mathrm{NP}\). The proof establishes this hardness even on the promise that a feasible solution exists.

The finite result of [Procaccia, Schiffer, and Zhang](https://arxiv.org/html/2403.08051v2#S4.SS4) allows prices to be adjusted separately for distinct assigned rooms. Here, one price applies to an entire room class. The reduction exploits precisely that requirement: sufficiently low ordinary-type utilities force each item class to belong entirely to one type, turning divisible allocation into a PARTITION constraint.

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the requested problem: the continuous optimization problem is NP-hard, even with \(m=\tau=3\), \(s=1\), and guaranteed feasibility. I found no major or minor mathematical issues.

• Source problem and reduction direction.

The prover states the required source problem precisely: binary-encoded positive integers, with the question whether a subset has half the total sum. This version of PARTITION is NP-complete; the binary encoding is essential to the complexity claim. See [Theorem 6.4 in the cited complexity reference](https://hardness.mit.edu/drafts/2022-12-15.pdf).

The reduction proceeds in the correct direction: from PARTITION to a fixed-threshold decision problem for the continuous optimization problem.

• Construction and input requirements.

Every constructed mass and capacity is positive. Since \(A=\sum_i a_i>0\), all denominators are valid. The ordinary capacities in apartment \(1\) sum to \(1/2\), and each apartment’s total capacity is \(1\). The type masses also sum to \(1\).

All values and rents are nonnegative integers bounded by \(4\). The objective \(f_1(\mathbf u)=u_3\) is an allowed rational linear function.

The normalization calculations are correct. Types \(1\) and \(2\) have total capacity-weighted values \(6\), and type \(3\) has capacity-weighted value \(2\) in each apartment. These equal the total rent \(6\).

The three valuation profiles are distinct, so the construction genuinely has support size \(\tau=3\).

• Welfare maximization and support restrictions.

In each apartment, the welfare contributions of types \(1\) and \(2\) are fixed by their row sums. Type \(3\)’s contribution increases strictly with its mass assigned to the distinguished class.

The maximum possible distinguished mass is \(1/2\), and the prover correctly verifies its attainability: types \(1\) and \(2\) can fill the remaining ordinary capacity. Hence every maximizing marginal assigns all type \(3\) mass to the distinguished class.

Because that class’s capacity is exactly \(1/2\), no mass of types \(1\) or \(2\) can occupy it. Nonnegativity of configuration masses then justifies the claimed configuration-level restrictions.

The recomputed maximum net welfares are exactly
\[ W_1=\frac12,\qquad W_2=0,\qquad W_3=\frac32. \]

• Consensus forces apartment \(3\).

The population utility identity is valid: summing utilities against configuration masses produces marginal welfare minus the capacity-weighted final-price total. The final-price budget therefore makes this sum equal to \(W_j\).

Summing the configuration-level consensus inequalities gives \(W_{j^\star}\ge W_j\) for every apartment. Since \(W_3\) is uniquely largest, the selected apartment must be \(3\). Weak comparisons and permission to choose tied apartments cause no ambiguity here.

Both ordinary types necessarily occupy class \(c\), so their selected utilities equal \(u=3-p_{3c}\). The apartment \(3\) budget gives
\[ p_{3c}+p_{3d_3}=4,\qquad u_3=4-p_{3d_3}=3-u. \]
These identities also agree with the task’s averaged definition of type utilities, since the selected utility is constant over each type’s supported configurations.

• Universal utility bounds.

Each \(c_j=\min_b q_{jb}\) exists because the class set is finite. Its capacity-weighted mean is \(2\), so \(c_j\le2\), regardless of whether some prices are negative.

For either ordinary type, values are constant across all classes within an apartment, including the distinguished class. Starting-price envy-freeness consequently forces every assigned class to have price \(c_j\).

Rent preservation then gives, for every supported ordinary-type configuration,
\[ \sum_j U_j=6-\sum_j c_j=D\ge0. \]
Consensus gives \(U_j\le u\) for all three apartments, hence \(D\le3u\) and \(u\ge0\). It follows that \(u_3\le3\).

The further bound is also correct:
\[ U_j=D-\sum_{h\ne j}U_h\ge D-2u\ge-2u. \]
Thus every assigned ordinary-type utility lies in \([-2u,u]\). These are bounds on individual supported configurations, which is exactly what the next step requires.

• Extraction of a partition.

Positive marginal mass in a class guarantees a positive configuration using that class. Applying the preceding bounds therefore yields the stated price intervals:
\[ 3-u\le p_{1i}\le3+2u \]
for a class used by type \(1\), and
\[ 1-u\le p_{1i}\le1+2u \]
for one used by type \(2\).

If both types use the class, these intervals require \(3-u\le1+2u\), equivalently \(u\ge2/3\).

Consequently, when \(u<2/3\), every ordinary class is assigned entirely to one ordinary type: type \(3\) cannot use it, and its positive capacity must be filled. The type \(1\) row sum then gives
\[ \sum_{i\in S}\frac{a_i}{2A}=\frac14, \]
exactly the required partition identity.

The contrapositive is valid: every feasible solution for a NO-instance has \(u\ge2/3\), hence \(u_3\le7/3\). The strict inequality used for extraction correctly leaves the boundary value available.

• Universal feasible solution with value \(7/3\).

The specified configuration masses give each ordinary type mass \(1/4\), fill each item class to \(a_i/(2A)\), and fill all remaining classes to their capacities. Their marginals satisfy the welfare restrictions already proved sufficient for optimality.

All starting-price budgets hold with \(q_{jb}=2\). Starting envy-freeness holds for every alternative class: ordinary types are indifferent, while type \(3\) strictly prefers its distinguished class.

Each final-price budget equals \(2\). Every supported ordinary configuration has total final price \(6\), and the distinguished configuration also has total final price \(6\), so rent preservation holds individually.

Every entry in the displayed utility table is correct. Apartment \(3\) weakly dominates both alternatives for each supported type. Thus the construction is feasible for every source instance and achieves \(u_3=7/3\).

• YES-instance solution with value \(3\).

The partition identity gives the claimed type masses and all class marginals. The three displayed final-price budget calculations are correct.

Starting envy-freeness remains valid. The supported configuration price totals are respectively \(3+0+3\), \(1+2+3\), and \(2+3+1\), all equal to \(6\).

Both ordinary types have utility zero in every apartment. Type \(3\)’s utilities are exactly \((1,0,3)\), so apartment \(3\) satisfies consensus. The objective equals \(3\), matching the universal upper bound.

Both claimed optimal values are therefore attained; no assumption about attainment of a general continuous optimum is needed.

• Encoding and hardness conclusion.

The class count is correctly computed as \((n+1)+3+2=n+6\). The binary length of \(A\), and hence of each capacity \(a_i/(2A)\), is polynomial in the source input length. The valuation table has only linearly many entries.

The established optima \(3\) and \(7/3\) lie strictly on opposite sides of \(8/3\). Thus a feasible solution meeting that fixed threshold exists exactly for YES-instances. This proves NP-hardness under the requested binary rational encoding and under guaranteed feasibility.

The proof does not claim NP-completeness or strong NP-hardness, so neither requires additional justification.

• Relation to the finite result.

The cited finite optimization result concerns individually assigned rooms; its negotiated envy-freeness definition preserves each player’s total assigned-room rent. The prover’s comparison is consistent with that model. See [Definition 4.4 and Theorem 4.9](https://arxiv.org/html/2403.08051v2#S4.SS4).

In this reduction, the shared class price is explicitly the obstruction used in the partition-extraction step. The finite result is contextual and is not used to justify any step of the reduction.

No corrective feedback or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩