Answer: \(\mathrm{NP}\)-complete, even when every house has capacity \(1\).
Theorem 3 — class: hardness
Given finite houses \(H\), rational capacities \(\kappa_h\), and a distribution \(\mu\) over complete agent types, with a designated type \(t^\star\) of mass \(\rho>0\), identical true ranking and utility \(u^\star\), and all other types truthful, choose one strict report \(r\) for the cohort. Run continuum PS with each reported type's mass eating at unit rate and house \(h\) having capacity \(\kappa_h\); ask whether \(U(r)=\rho^{-1}\sum_{h\in H}u^\star(h)x_{r,h}\ge T\), or compute a maximizing \(r\), where \(x_{r,h}\) is the cohort's allocation.
Let \(H\) contain \(m\ge 1\) houses with capacities \(\kappa_h\in\mathbb{Q}_{>0}\). A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a complete strict true ranking of \(H\). The designated type \(t^\star\) has mass \(\rho=\mu_{t^\star}>0\) and a common utility function \(u^\star:H\to\mathbb{Q}_{\ge0}\), strictly consistent with its true ranking. All other types report truthfully.
The entire designated cohort chooses one complete strict report \(r\). Continuum probabilistic serial makes each type consume its highest reported house with remaining capacity at aggregate rate \(\mu_t\). Exhausted houses are skipped immediately; simultaneous exhaustions are processed together. Consumption continues until every house is exhausted, at time \(\sum_h\kappa_h\).
Let \(x_{r,h}\) be the total capacity of house \(h\) consumed by the designated cohort, and define its utility per unit mass by \(U(r)=\rho^{-1}\sum_{h\in H}u^\star(h)x_{r,h}\). Given a binary rational threshold \(T\), the decision problem asks whether some report satisfies \(U(r)\ge T\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this continuous cohort-report decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite agents and unit-capacity houses, computing an expected-utility best response is \(\mathrm{NP}\)-hard, and the corresponding utility-threshold decision problem is \(\mathrm{NP}\)-complete; with two agents, a best response is computable in linear time. [Source](https://cgi.cse.unsw.edu.au/~tw/agmmnwaamas2015.pdf)
No result settling the exact positive-mass, common-report continuous problem was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, even when every house has capacity \(\kappa_h=1\). Consequently, it is polynomial-time solvable if and only if \(\mathrm{P}=\mathrm{NP}\).
The key is an exact reduction: a positive-mass cohort can reproduce the consumption of one finite agent after a rescaling of time.
We use the finite utility-threshold problem established in the proof of Theorem 3 of [Aziz et al., *Manipulating the Probabilistic Serial Rule*](https://cgi.cse.unsw.edu.au/~tw/agmmnwaamas2015.pdf): given \(\mathrm{PS}\) with \(\ n\) agents, \(\ m\) unit-capacity houses, fixed complete strict reports for all agents except agent \(\ 1\), nonnegative rational utilities \(\ u\), and a rational threshold \(\ S\), deciding whether some complete strict report gives agent \(\ 1\) utility at least \(\ S\) is \(\mathrm{NP}\)-complete. Their process continues until all houses are exhausted, at time \(\ m/n\).
We first show that requiring strictly ordered utilities preserves this hardness.
Lemma. A finite threshold instance can be transformed in polynomial time into one with distinct nonnegative rational utilities, preserving the answer for every report.
Proof. Let \(\ p_{r,h}\) denote agent \(\ 1\)'s allocation under report \(\ r\), and let
\(\ V(r)=\sum_h u(h)p_{r,h}\).
Set \(\ D=(n!)^m\). We claim that every \(\ p_{r,h}\), for every report, has denominator dividing \(\ D\).
There are at most \(\ m\) exhaustion stages. At stage \(\ j\), choose a house exhausting at the next event, and let \(\ k_j\in\{1,\ldots,n\}\) be its number of consumers. Initially all residual capacities are integers. Inductively, if residual capacities and accumulated allocations have denominators dividing \(\ \prod_{i<j}k_i\), dividing the chosen house’s residual capacity by \(\ k_j\) gives the next stage duration with denominator dividing \(\ \prod_{i\le j}k_i\). Subtracting integer consumption rates times that duration preserves this denominator bound. Since each \(\ k_i\) divides \(\ n!\), the final denominators divide \(\ D\). Simultaneous exhaustions do not change this argument.
Let \(\ Q\) be the product of the denominators of all utilities and of \(\ S\). Thus \(\ V(r)-S\) is an integer multiple of \(\ g=1/(QD)\). In particular,
\(\ V(r)<S\ \Longrightarrow\ V(r)\le S-g\).
Order the houses by nonincreasing \(\ u\), breaking ties arbitrarily. Assign distinct integers \(\ b_h\in\{1,\ldots,m\}\), with larger integers assigned to earlier houses, and define
\(\ \delta=g/(2m^2),\qquad u'(h)=u(h)+\delta b_h\).
The utilities \(\ u'\) are nonnegative and strictly decreasing in the chosen order. Every finite agent consumes exactly \(\ m/n\) units, so
\(\ 0\le V'(r)-V(r)=\delta\sum_h b_hp_{r,h}\le\delta m(m/n)\le g/2\).
Therefore, if \(\ V(r)\ge S\), then \(\ V'(r)\ge S\); if \(\ V(r)<S\), then \(\ V'(r)\le S-g/2<S\). The threshold answer is preserved for every report.
Finally, \(\ \log D=O(mn\log n)\), and \(\ \log Q\) is bounded by the numerical input length. The transformation therefore has polynomial encoding length and running time. ∎
The designated agent’s true ranking can now be defined by decreasing \(\ u'\): its true ranking does not restrict its possible reports.
For completeness, this reduction also works if “types” means distinct rankings. In the cited hardness construction, the designated agent’s two highest-utility houses are the first main-part literal pair. Every fixed agent has a different first two houses: literal agents follow their own literal across rounds, and auxiliary manipulators start in another part. Thus the designated ranking differs from every fixed ranking. The perturbation preserves this property. We may restrict to constructions with at least two variables without affecting hardness. [Source, construction in Section 5.2](https://cgi.cse.unsw.edu.au/~tw/agmmnwaamas2015.pdf)
Take a finite hard instance with distinct utilities, writing these utilities as \(\ u\).
Construct the continuous instance as follows:
All listed masses are positive, and their sum is \(\ 1\). The support size satisfies \(\ \tau\le n\). By the ranking property above, grouping does not absorb any fixed agent into the designated type.
Claim. For every designated report \(\ r\), the continuous allocation satisfies \(\ x_{r,h}=p_{r,h}\) for every house \(\ h\).
Proof. Compare finite time \(\ s\) with continuous time \(\ t=ns\).
Initially, both processes have identical residual capacities. Suppose they have identical residual capacities and identical surviving houses at corresponding event times. A house consumed by \(\ k\) finite agents has finite aggregate rate \(\ k\). Its corresponding continuous aggregate rate is \(\ k/n\), because grouping identical reports preserves their total rate.
Consequently, every candidate exhaustion duration in the continuous process is exactly \(\ n\) times its finite counterpart. The same houses exhaust next, including all simultaneous exhaustions. During the corresponding intervals, a fixed group consumes the same amount in both processes:
\(\ (c/n)(n\,\Delta s)=c\,\Delta s\).
Likewise, the designated cohort consumes
\(\ \rho(n\,\Delta s)=(1/n)(n\,\Delta s)=\Delta s\),
which equals agent \(\ 1\)'s finite consumption.
Induction over exhaustion events proves the claim. The terminal times also correspond: finite time \(\ m/n\) becomes continuous time \(\ m\), the total continuous capacity. ∎
It follows that
\(\ U(r)=\rho^{-1}\sum_hu^\star(h)x_{r,h} =n\sum_hu(h)p_{r,h}=nV(r)\).
Hence, report by report,
\(\ U(r)\ge T\ \Longleftrightarrow\ nV(r)\ge nS \ \Longleftrightarrow\ V(r)\ge S\).
This proves both directions of the reduction. Grouping rankings, encoding masses \(\ c/n\), and multiplying the threshold by \(\ n\) take polynomial time and produce polynomial-length output. Thus the continuous problem is \(\mathrm{NP}\)-hard, already with unit capacities.
A certificate is a complete strict report, encoded by a permutation of the houses using \(\ O(m\log m)\) bits.
Here is an exact verifier, including its numerical complexity.
Write each mass as \(\ \mu_t=a_t/b_t\). Let
\(\ A=\prod_t b_t,\qquad w_t=A\mu_t\).
Then every \(\ w_t\) is a positive integer and \(\ \sum_t w_t=A\). Let \(\ C\) be the product of the capacity denominators. Both \(\ A\) and \(\ C\) have \(\ O(L)\) bits.
Maintain every residual capacity and designated allocation with a common denominator \(\ E\), initially \(\ E=C\). At a stage, let \(\ R_h/E\) be house \(\ h\)'s residual capacity, and let \(\ W_h\) be the sum of the integer weights of its current consumers. Its consumption rate is \(\ W_h/A\).
Among houses with \(\ W_h>0\), choose a minimizer \(\ b\) of \(\ R_h/W_h\), using exact cross multiplication. The stage duration is
\(\ \Delta=AR_b/(EW_b)\).
After this stage, use common denominator \(\ E'=EW_b\). Every residual capacity has integer numerator
\(\ R'_h=R_hW_b-W_hR_b\).
If the designated cohort currently consumes house \(\ a\), its allocation to that house increases by
\(\ w_{t^\star}R_b/(EW_b)\).
Thus its allocation numerators also remain integers with denominator \(\ E'\). Remove every house with \(\ R'_h=0\) simultaneously, and advance each type to its highest surviving reported house.
There are at most \(\ m\) stages. Since \(\ 1\le W_b\le A\),
\(\ E\le CA^m,\qquad \log E=O(mL)\).
Residual capacities and allocations are bounded by total capacity, whose encoding magnitude contributes only \(\ O(L+\log m)\) additional bits. Therefore all maintained numerators and denominators have \(\ O(mL)\) bits. The final utility-threshold comparison also uses numbers of this size, after incorporating the input utility, mass, and threshold denominators.
Preference pointers advance at most \(\ m\) times per type. Computing rates and updating capacities and allocations takes \(\ O(m(\tau+m))\) arithmetic operations overall. With ordinary quadratic-time integer arithmetic, a sufficient verification bound is
\(\ O\!\left(m(\tau+m)(mL)^2\right)\)
bit operations.
The verifier accepts exactly those reports satisfying the threshold. Therefore the problem belongs to \(\mathrm{NP}\).
The exact reduction proves \(\mathrm{NP}\)-hardness, and the exact verifier proves membership in \(\mathrm{NP}\). The problem is therefore \(\mathrm{NP}\)-complete.
A report can be checked in \(\ O(m(\tau+m)(mL)^2)\) bit operations. Enumerating all reports gives a deterministic algorithm with running time
\(\ O\!\left(m!\,m(\tau+m)(mL)^2\right)\).
No open mathematical step remains in this classification.
⟨structured verdict parsed — rendered above⟩
Assessment: proved. The output establishes that the continuous cohort-report decision problem is \(\mathrm{NP}\)-complete, including when all capacities are one. The reduction respects positive cohort mass, complete strict rankings, strictly consistent nonnegative rational utilities, and explicit support encoding. I found no major or minor mathematical issues.
The proof of Theorem 3 explicitly establishes hardness of the utility-threshold decision problem, rather than merely hardness of computing an optimal report. Its finite process uses unit consumption rates and continues until all houses are exhausted, at time \(\frac{m}{n}\). These conventions match the reduction. The source states the threshold problem for integer utilities; using it within the larger rational-utility domain is valid. [Aziz et al., Theorem 3 and Section 3](https://cgi.cse.unsw.edu.au/~tw/agmmnwaamas2015.pdf)
The finite input explicitly lists agents and their rankings. Consequently, polynomial bounds involving the finite number of agents are polynomial in that input length. The reduction does not depend on expanding a succinctly encoded population.
Finding: The cited hardness result is applicable.
The denominator induction is correct:
Thus all final allocation denominators divide \(\prod_j k_j\), which divides \(D=(n!)^m\). Simultaneous exhaustions introduce no additional division and do not invalidate the bound.
With \(Q\) the product of utility and threshold denominators, every \(V(r)-S\) is an integer multiple of \(g=\frac{1}{QD}\). Therefore the asserted implication
\[
V(r)<S\ \Longrightarrow\ V(r)\le S-g
\]
is valid.
The perturbation assigns larger \(b_h\) to earlier houses in nonincreasing utility order. It therefore preserves every existing strict utility comparison and separates every tie. Nonnegativity is preserved.
The bound
\[
0\le V'(r)-V(r)\le \delta m\frac{m}{n}\le \frac{g}{2}
\]
is correct because every agent consumes exactly \(\frac{m}{n}\), every \(b_h\le m\), and \(n\ge1\).
Accordingly:
The argument includes equality at the threshold and applies uniformly to every complete report.
Finally, the stated bit-length bounds for \(D\), \(Q\), and the perturbed utilities are polynomial.
Finding: The lemma is correct as stated.
This condition matters under the interpretation that types are distinct rankings: a fixed agent sharing the designated true ranking could otherwise belong to the same reporting cohort.
The cited construction supports the claimed distinction. The designated utility order begins with the main-part first literal pair. Literal agents begin with their own literal houses across successive rounds; auxiliary manipulators begin in other parts. With at least two variables, their initial pairs differ from the designated pair. The perturbation preserves these comparisons. [Aziz et al., Section 5.2](https://cgi.cse.unsw.edu.au/~tw/agmmnwaamas2015.pdf)
Restricting away instances with fewer than two variables does not affect hardness.
The reduction therefore uses a hard family satisfying the distinctness condition; it need not establish that condition for every arbitrary finite threshold instance.
Finding: Grouping fixed agents does not absorb any of them into the designated type.
All construction requirements are satisfied:
Grouping, perturbation, and threshold scaling all take polynomial time.
Finding: The reduction produces valid instances of the task.
The event induction is valid. At corresponding event times, identical surviving houses and residual capacities imply identical choices by each finite agent and its continuous counterpart.
A finite aggregate rate \(k\) becomes continuous rate \(\frac kn\). Every candidate exhaustion duration therefore scales by \(n\). The minimizing houses, including simultaneous ties, coincide.
The consumption identities
\[
\frac cn(n\Delta s)=c\Delta s,
\qquad
\frac1n(n\Delta s)=\Delta s
\]
correctly establish preservation of fixed-group consumption and designated consumption.
The terminal times also correspond. Hence \(x_{r,h}=p_{r,h}\) holds for every house and every report.
The normalization is handled correctly:
\[
U(r)=nV(r),\qquad T=nS.
\]
Because \(n>0\), the two threshold conditions are equivalent in both directions.
Finding: The reduction proves \(\mathrm{NP}\)-hardness with unit capacities.
The integer-weight representation is valid: \(w_t=A\mu_t\) is a positive integer and the weights sum to \(A\).
Selecting a minimizer of \(\frac{R_h}{W_h}\) among positive-rate houses gives the next exhaustion event. Such a house exists whenever capacity remains, since every type has a complete report and positive mass.
Both update formulas are correct:
\[
\Delta=\frac{AR_b}{EW_b},
\qquad
R'_h=R_hW_b-W_hR_b.
\]
The allocation increment \(\frac{w_{t^\star}R_b}{EW_b}\) is also correct. Updating the common denominator requires only integer rescaling of previously stored allocation numerators.
Removing all zero residuals together correctly implements simultaneous exhaustions.
There are at most \(m\) stages. The bounds \(W_b\le A\) and \(E\le CA^m\) yield \(O(mL)\)-bit maintained integers. Capacity magnitudes and the final utility comparison fit the stated bit bound.
Preference pointers advance at most \(m\) times per type. The claimed \(O(m(\tau+m))\) arithmetic-operation bound covers rate computation, comparisons, updates, and pointer advancement. Quadratic integer arithmetic therefore gives the sufficient verification bound
\[
O\!\left(m(\tau+m)(mL)^2\right).
\]
The verifier covers arbitrary positive rational capacities and masses, single-house instances, and simultaneous events.
Finding: Membership in \(\mathrm{NP}\) and the stated verification running time are established.
The hardness reduction and polynomial certificate verification establish the claimed \(\mathrm{NP}\)-completeness. Multiplying the verification bound by \(m!\) also gives the stated exhaustive-search bound.
No repair or additional mathematical clarification is required.
⟨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.