Multi-Apartment Rent Division

The strongest case is a high-multiplicity mirror of the paper’s negotiated-envy-free optimization result, with Theorem 4.9 as the lead anchor. The theorem is proved in this paper; its proof is deferred to Appendix B.8. It states that, given polynomially many linear objectives, one can compute in polynomial time a solution maximizing the minimum objective value over all negotiated envy-free solutions.

The appropriate regime is a large co-living cooperative or housing cohort. There are \(N\) renters, with \(N\) large, considering \(m\) candidate buildings. Each building has \(N\) rooms. Renters fall into \(\tau\) complete valuation types, where a type records the renter’s values for every apartment-room feature, together with any other parameter used by the model. Each type \(t\) has rational mass \(\mu_t\), and \(\tau\ll N\). Rooms likewise come in finitely many feature classes. A class \(b\) in apartment \(j\) has rational capacity \(\rho_{jb}\), representing \(\rho_{jb}N\) repeated rooms, and all rooms in that class have the same value to every renter type.

This is a genuine high-multiplicity setting: an instance with rational masses can be scaled by clearing denominators into \(N\) cloned renters and \(N\) repeated rooms. It is not a fractional-room or lottery interpretation. Every clone still receives one room in every candidate apartment, and the final solution still selects one actual apartment.

I would call the problem Mass-Negotiated Envy-Free Rent Division with Linear Fairness Optimization, or M-NEFRD. An instance consists of:

• a finite type set \(T\), masses \(\mu_t\in\mathbb Q_{\ge 0}\) summing to \(1\);
• apartments \(j\in[m]\);
• room classes \(B_j\), with capacities \(\rho_{jb}\in\mathbb Q_{\ge0}\) summing to \(1\);
• values \(v_t(j,b)\in\mathbb Q_{\ge0}\);
• per-capita rents \(R_j\in\mathbb Q\);
• polynomially many rational linear objectives \(f_1,\ldots,f_s\).

The normalization corresponding to the paper’s assumption can be imposed as

\[ \sum_{j\in[m]}\sum_{b\in B_j}\rho_{jb}v_t(j,b) = \sum_{j\in[m]}R_j \]

for every type \(t\).

The assignment variable is a clone-consistent family of matchings. For each apartment \(j\), let \(a^j_{tb}\) be the mass of type \(t\) assigned to room class \(b\), with

\[ \sum_{b\in B_j}a^j_{tb}=\mu_t, \qquad \sum_{t\in T}a^j_{tb}=\rho_{jb}. \]

The assignment in every apartment must be welfare-maximizing:

\[ \max \sum_{t\in T}\sum_{b\in B_j}a^j_{tb}v_t(j,b). \]

To preserve the fact that the same renter is assigned a room in every candidate apartment, use a common nonatomic interval \(I_t\) of mass \(\mu_t\) for each type \(t\). A measurable map \(b_j:I_t\to B_j\) realizes the flow \(a^j\). Thus an infinitesimal renter \(u\in I_t\) has the assignment vector

\[ (b_1(u),\ldots,b_m(u)). \]

With rational data, the flows can be chosen rational, the intervals can be partitioned rationally, and denominator clearing recovers an ordinary finite assignment of cloned renters.

A candidate solution consists of these assignments, room prices \(p_{jb}\), a chosen apartment \(j^\star\), and a witness price system \(q_{jb}\). Both price systems satisfy

\[ \sum_{b\in B_j}\rho_{jb}p_{jb}=R_j, \qquad \sum_{b\in B_j}\rho_{jb}q_{jb}=R_j. \]

The solution is negotiated envy-free if, for every type \(t\) and almost every \(u\in I_t\),

\[ v_t(j^\star,b_{j^\star}(u))-p_{j^\star,b_{j^\star}(u)} \ge v_t(j,b_j(u))-p_{j,b_j(u)} \]

for every apartment \(j\), so the chosen apartment is a consensus apartment;

\[ v_t(j,b_j(u))-q_{j,b_j(u)} \ge v_t(j,b)-q_{jb} \]

for every room class \(b\) in every apartment \(j\), so \(q\) is individually envy-free; and

\[ \sum_{j\in[m]}p_{j,b_j(u)} = \sum_{j\in[m]}q_{j,b_j(u)}, \]

so the final prices are reachable from the individually envy-free prices by the paper’s fair negotiations.

The computational question is:

Given an M-NEFRD instance, compute a negotiated-envy-free solution maximizing
\[ > \max_{q\in[s]} f_q(\mathbf u), > \]
where \(\mathbf u\) is the vector of selected-apartment utilities of the finitely many assignment cells.

The usual maximin objective is obtained by taking one \(f_q\) for each positive-mass cell and setting \(f_q(\mathbf u)=u_q\). Equitability is represented by the pairwise linear objectives \(u_h-u_{h'}\), exactly in the spirit of Theorem 4.9.

I expect this problem to be Class A. Each apartment’s welfare-maximizing assignment is a maximum-weight transportation problem. Once a canonical rational assignment is fixed, the price variables \(p,q\), the consensus inequalities, the individual envy inequalities, the negotiation equalities, and the objective threshold are all linear. Enumerating the \(m\) possible chosen apartments gives polynomially many LPs. The number of assignment cells can be kept polynomial by realizing each type’s apartment-wise transportation flows using interval partitions and taking their common refinement.

The bridge to Theorem 4.9 is unusually clean. Clearing denominators gives a finite instance of exactly the paper’s model: cloned players, repeated room classes, one assignment per apartment, quasi-linear utilities, one chosen apartment, and negotiated envy-freeness. Conversely, any finite instance with these clone symmetries compresses to the mass formulation. Theorem 4.8, also proved here, provides supporting evidence: the paper’s universal existence construction should survive this scaling, so the optimization LP is expected to be feasible for every such instance.

I would not use Theorems 3.2, 3.3, or Corollary 3.4 as anchors. They are named probabilistic existence results about universal envy-freeness as the number of apartments grows, not computational complexity results about continuizing the population. They may motivate separate questions about random type-mass models, but they are outside the lead case.

The weakest point is that arbitrary type splitting and cross-apartment assignment correlations cannot be represented by independent marginal flows alone. If one simply writes \(a^j_{tb}\) for each apartment and forgets which clone receives which tuple of rooms, it can create artificial negotiated-envy-free solutions that do not correspond to any finite assignment. The common interval representation above is therefore essential. A second limitation is that the objective must be clone-symmetric or represented over the finitely many positive-mass cells; an arbitrary named-player objective from Theorem 4.9 has no meaningful compressed form.

That concession narrows the claim, but does not destroy it. The paper’s central object—large groups choosing one apartment, assigning repeated rooms, setting rents, and negotiating from an envy-free baseline—has a recognizable high-multiplicity regime. Theorem 4.9 then gives a precise Class-A research question: whether its polynomial LP method extends from named players to rational masses of exchangeable renter types while preserving clone-consistent assignments.

Further questions include whether the full split-flow version admits a polynomial-size configuration LP, whether continuous optima round exactly to finite cloned instances, and whether the same mirror can be developed for strong negotiated envy-freeness.