Answer: Polynomial-time solvable.
Theorem 11 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateCTTCR (Algorithm 2) outputs a 4-person stable assignment in time O(n5).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational resident masses \(\mu_t\) over \(\tau\) complete preference types and rational room supplies \(\rho_q\) over \(\kappa\) room categories, with \(\sum_t\mu_t=1\) and \(\sum_q\rho_q=1/2\), find a feasible mass assignment \(x_{\{t,u\},q}\) with no positive-mass 4PS-blocking exchange. Feasibility requires \(\sum_q(2x_{\{t,t\},q}+\sum_{u\ne t}x_{\{t,u\},q})=\mu_t\) for each type \(t\), and \(\sum_{t\le u}x_{\{t,u\},q}=\rho_q\) for each category \(q\). A blocking exchange is possible if two positive-mass room cohorts \((\{t,u\},q)\) and \((\{v,w\},p)\) contain a \(t\)-resident and a \(v\)-resident whose swap would strictly improve the utilities of both movers and both roommates.
A society is given by its support: the list of the \(\tau\) resident types with positive masses \(\mu_t\), each a binary rational; \(\tau\) is the support size, not the number of possible types. Room categories \(q\in\{1,\ldots,\kappa\}\) have positive binary-rational supplies \(\rho_q\), with \(\sum_t\mu_t=1\) and \(\sum_q\rho_q=1/2\).
Each type has complete, nonnegative binary-rational valuations \(h_t(u)\) for every roommate type and \(v_t(q)\) for every room category; utility is \(h_t(u)+v_t(q)\). Valuations need not be symmetric, and ties are allowed. Two distinct residents of the same type may share a room, using \(h_t(t)\).
An assignment consists of nonnegative rational room-cohort masses \(x_{\{t,u\},q}\), satisfying \(\sum_q(2x_{\{t,t\},q}+\sum_{u\ne t}x_{\{t,u\},q})=\mu_t\) and \(\sum_{t\le u}x_{\{t,u\},q}=\rho_q\).
A positive-mass blocking exchange swaps the \(t\)- and \(v\)-residents in equal positive-mass portions of cohorts \((\{t,u\},q)\) and \((\{v,w\},p)\), replacing them by \((\{v,u\},q)\) and \((\{t,w\},p)\), provided all four inequalities hold: \(h_t(w)+v_t(p)>h_t(u)+v_t(q)\), \(h_v(u)+v_v(q)>h_v(w)+v_v(p)\), \(h_u(v)>h_u(t)\), and \(h_w(t)>h_w(v)\).
Check every choice of mover in each cohort. The exchanged portions occupy distinct rooms; categories and resident types may coincide, and portions taken from the same cohort must be disjoint. An assignment is four-person stable (4PS) when no such exchange exists.
Is finding a feasible 4PS mass assignment solvable in polynomial time, or is it NP-hard? State running times in \(m=\kappa\), \(\tau\), and the total input bit length \(L\).
For discrete instances with \(2n\) residents and \(n\) rooms, CTTCR produces a 4PS assignment in \(O(n^5)\) time; serial dictatorship also produces one in \(O(n^2)\) time. [Leng–Roy](https://arxiv.org/html/2508.14194v1)
No result settling this exact mass-assignment problem was located in the literature search.
Finding a feasible 4PS mass assignment is polynomial-time solvable. A batched serial-dictatorship algorithm uses at most \(\tau+m-1\) iterations and produces an assignment with at most that many positive cohort masses.
With ordinary exact integer arithmetic, a conservative bit-complexity bound is \(O(L+(\tau+m)^2L^2)\) for sparse output, or \(O(L+(\tau+m)^2L^2+m\tau^2)\) for a dense array of all cohort masses.
The construction adapts the serial-dictatorship idea in [Leng–Roy, Section 4.1](https://arxiv.org/html/2508.14194v1#S4.SS1). The batching, stability, and bit-complexity arguments below directly address the stated mass model.
Let \(a_t\) be the unassigned resident mass of type \(t\), and let \(b_q\) be the unused supply of room category \(q\). Initialize \(a_t=\mu_t\), \(b_q=\rho_q\), and every assignment coordinate to zero.
Fix an order of the types. While some resident mass remains:
Break ties arbitrarily. Call \(d\) the *dictator* of this iteration.
The independent maximizations in steps 2 and 3 are valid because utility is additive. Every available roommate type can be combined with every available category in a sufficiently small positive mass.
Initially, and after every iteration, the following identity holds:
\(\displaystyle \sum_t a_t=2\sum_q b_q.\)
Indeed, allocating room mass \(\delta\) removes exactly \(2\delta\) resident mass, including when both residents have the same type.
Consequently, whenever resident mass remains, some room supply remains. Both maximization steps therefore have candidates. Their selected residual masses are positive, so \(\delta>0\).
The update preserves nonnegativity. It also accounts for resident and room usage exactly: a mixed-type cohort consumes mass \(\delta\) of each type, whereas a same-type cohort consumes mass \(2\delta\) of its type.
Every iteration exhausts at least one previously positive type residual or category residual, by the definition of \(\delta\). An exhausted residual never becomes positive again. There are initially \(\tau+m\) positive residuals, so termination is finite. At termination all resident residuals vanish; the displayed identity and nonnegativity imply that all category residuals vanish as well. Thus the output satisfies every required feasibility equation.
The final iteration exhausts at least one type and at least one category. Every preceding iteration exhausts at least one residual. Therefore the number of iterations is at most \(\tau+m-1\), and the number of positive output coordinates is at most the same quantity.
Suppose, for contradiction, that two positive output cohorts admit a blocking exchange. Write their oriented descriptions as \((\{t,u\},q)\) and \((\{v,w\},p)\), with \(t\) and \(v\) the movers.
Choose generating iterations for these cohorts. Relabel the two cohorts, if necessary, so that the iteration generating \((\{t,u\},q)\) is no later than the one generating \((\{v,w\},p)\). Let \(d\) be the dictator of the earlier iteration.
At the beginning of that iteration, all four types \(t,u,v,w\) and both categories \(q,p\) have positive residuals:
The dictator satisfies \(d=t\) or \(d=u\). There are two cases.
Case 1: \(d=t\). The dictator selected roommate type \(u\) and category \(q\). Since type \(w\) and category \(p\) were available, maximality gives \(h_t(u)\ge h_t(w)\) and \(v_t(q)\ge v_t(p)\). Adding these inequalities yields
\(\displaystyle h_t(u)+v_t(q)\ge h_t(w)+v_t(p).\)
This contradicts the strict improvement required for mover \(t\).
Case 2: \(d\ne t\). Then \(d=u\), and the dictator selected roommate type \(t\). Since type \(v\) was available, maximality gives \(h_u(t)\ge h_u(v)\). This contradicts the required strict improvement \(h_u(v)>h_u(t)\) for the nonmoving resident \(u\).
Both cases contradict blocking. Hence the output is 4PS.
This argument covers every mover orientation. It also covers repeated types, equal room categories, and exchanges between disjoint portions of the same cohort. In particular, allowing the dictator’s own type as a roommate candidate is essential to the maximality argument for repeated-type cases.
Put \(K=\tau+m\). Each iteration scans at most \(\tau\) types and \(m\) categories, then performs a constant number of mass updates. The algorithm therefore uses \(O(K^2)\) arithmetic operations and comparisons, apart from input and output handling.
To establish polynomial bit complexity, let \(D\) be the product of the denominators of all input masses and supplies, and use the fixed denominator \(H=2^K D\). Its bit length is \(O(L+K)\).
Represent each residual and allocated mass by its integer numerator over \(H\). Initially every residual numerator is divisible by \(2^K\). Inductively, after \(i\) iterations, every residual numerator is divisible by \(2^{K-i}\): a mixed-type allocation preserves the previous divisibility, and a same-type allocation can reduce it by at most one power of two. Thus every halving required by the algorithm is exact, since fewer than \(K\) iterations occur.
All residual and cohort masses lie between zero and one, so their numerators have \(O(L+K)\) bits. The explicit input includes \(\tau+m\) masses and supplies, hence \(K=O(L)\); all these integers consequently have \(O(L)\) bits.
Constructing the scale and initial numerators costs \(O(KL^2)\) bit operations using schoolbook arithmetic. Each valuation comparison uses cross multiplication of input integers and costs \(O(L^2)\). Mass comparisons and updates also fit this bound. Combining these costs gives \(O(L+K^2L^2)\) bit operations for sparse output. Writing all \(m\tau(\tau+1)/2\) coordinates adds \(O(m\tau^2)\) work.
No expansion into individual residents is needed, and the proof imposes neither symmetry nor strict preferences.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes a polynomial-time algorithm for the exact mass-assignment problem. The feasibility, stability, and bit-complexity arguments are valid. No major or minor mathematical issues were found.
The independent maximizations are justified: utility is additive, and every selected roommate type and room category can support a sufficiently small positive allocation. There are no additional compatibility restrictions in USER_TASK.
Consequently, positive remaining resident mass implies positive remaining room supply. The roommate maximization also has a candidate because the dictator itself is available. Thus the algorithm cannot become stuck with unassigned resident mass.
The consumption recorded by each update matches the required feasibility equations, including the coefficient \(2\) for same-type cohorts.
The sharper bound of \(\tau+m-1\) iterations is valid: the final iteration exhausts at least one type and at least one category, while every preceding iteration exhausts at least one residual. Each iteration contributes to only one coordinate, so the claimed bound on positive output coordinates follows even if coordinates receive multiple contributions.
Resources belonging to the later cohort were positive at the beginning of the earlier iteration because residuals only decrease. If the iterations coincide, both descriptions necessarily concern the single coordinate generated in that iteration. Thus the availability assertion used in the stability proof is justified.
If \(d=t\), the two maximality inequalities imply
\(h_t(u)+v_t(q)\ge h_t(w)+v_t(p)\), contradicting the mover’s required strict improvement.
If \(d\ne t\), then \(d=u\). Roommate maximality implies \(h_u(t)\ge h_u(v)\), contradicting the stationary resident’s required strict improvement.
Blocking requires all four inequalities simultaneously; contradicting either identified inequality suffices. The proof therefore does not need to analyze the remaining participants’ preferences.
Ties cause no difficulty because maximality yields weak inequalities whereas blocking requires strict improvements. For disjoint portions of one cohort, both descriptions can use its generating iteration; the same contradiction applies. No step assumes four distinct type labels or two distinct coordinates.
The stated divisibility induction is correct. Mixed-type updates preserve the existing power-of-two divisibility. Same-type updates can lose at most one power through halving. Since the iteration count is at most \(K-1\), every required halving is exact.
Residual and accumulated coordinate numerators are bounded by \(H\). Their bit lengths are therefore \(O(L+K)=O(L)\), using the explicit encoding of the \(K\) positive masses and supplies.
Thus the sparse-output bound \(O(L+(\tau+m)^2L^2)\) is supported. For dense output, writing zero coordinates adds \(O(m\tau^2)\); encoding the at most \(K-1\) positive rational coordinates is already covered by the sparse bound.
⟨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.