Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 4.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor each linear order ≻π over agents, the REV π rule (i) complies with eligibility requirements, (ii) respects priorities, (iii) returns a matching of maximum size among feasible matchings, (iv) respects improvements, and (v) can be computed in strongly polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite complete patient types \(T\), rational masses \(\mu_t\) summing to \(1\), categories \(C\) with rational per-capita capacities \(\rho_c\), eligibility and weak priority orders over types, and a policy order \(\pi_T\), compute rational \(y_{t,c}\ge 0\) satisfying \(\sum_c y_{t,c}\le\mu_t\), \(\sum_t y_{t,c}\le\rho_c\), and \(y_{t,c}=0\) for ineligible pairs. Require that \(y_{t,c}>0\) implies every higher-priority eligible type \(t'\succ_c t\) has unmatched mass \(u_{t'}=\mu_{t'}-\sum_c y_{t',c}=0\); among such allocations, maximize \(\sum_{t,c}y_{t,c}\), then lexicographically maximize matched mass according to \(\pi_T\).
A society is given by its support: a list \(T\) of \(\tau\) patient types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. There are \(m=|C|\geq1\) categories with nonnegative binary-rational capacities \(\rho_c\); \(L\) is the total input bit length.
Each category has an explicitly given weak priority order \(\succeq_c\) on \(T\cup\{\varnothing\}\); type \(t\) is eligible exactly when \(t\succ_c\varnothing\). All patients of a type have identical eligibility and priority positions and are indifferent among eligible categories. The policy order \(\pi_T=(t_1,\ldots,t_\tau)\) is a strict order, with the first type taking precedence.
An allocation consists of rational masses \(y_{t,c}\geq0\) satisfying \(\sum_c y_{t,c}\leq\mu_t\), \(\sum_t y_{t,c}\leq\rho_c\), and \(y_{t,c}=0\) for ineligible pairs. Mass may be split among categories. Write \(s_t=\sum_c y_{t,c}\) and \(u_t=\mu_t-s_t\).
Respect of priorities requires \(y_{t,c}>0\Longrightarrow u_{t'}=0\) for every eligible \(t'\succ_c t\); tied types impose no such restriction on one another.
Among allocations satisfying these conditions, first maximize \(\sum_t s_t\), then lexicographically maximize \((s_{t_1},\ldots,s_{t_\tau})\). Any allocation attaining both objectives may be returned.
Is computing such an optimal allocation polynomial-time solvable in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For individual patients and integer quotas, Reverse Rejecting rules compute an eligibility-compliant, priority-respecting matching of maximum feasible size in strongly polynomial time and respect improvements ([Aziz–Brandl, 2024](https://cgi.cse.unsw.edu.au/~haziz/effreserves_journal.pdf)).
For unit-demand individuals, strict priorities, and integer quotas, Maximum Rationing Eating computes a fractional allocation respecting eligibility and priorities and attaining maximum size; it does not impose the policy-order objective ([Aziz, 2023](https://aamas.csc.liv.ac.uk/Proceedings/aamas2023/pdfs/p949.pdf)). No result located settles the stated rational-mass optimization problem.
Computing the required allocation is \(\mathrm{NP}\)-hard. This holds even when all masses and capacities are dyadic rationals and only one category has ties among eligible types.
The reduction makes the maximum total allocated mass explicitly known. The hardness lies in maximizing the first policy coordinate.
We reduce from CLIQUE: given a simple undirected graph \(G=(V,E)\) and an integer \(k\), decide whether \(G\) contains a clique of size \(k\). This problem is \(\mathrm{NP}\)-complete. [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Write \(V=\{1,\ldots,n\}\) and \(q=|E|\). We may restrict to \(2\leq k\leq n\) and \(q\geq1\): instances outside these restrictions are decidable directly, so this restriction preserves hardness.
Choose
\(a=\lceil\log_2(n+1)\rceil,\qquad b=\lceil\log_2(q+1)\rceil,\qquad d=2^{-a},\qquad h=2^{-(a+b)}.\)
These choices ensure
\(qh<d,\qquad 1-nd\geq d.\)
Create one type \(v_i\) for each vertex \(i\), and a distinguished type \(z\). Their masses are
\(\mu_{v_i}=d,\qquad \mu_z=1-nd.\)
All masses are positive dyadic rationals, and they sum to \(1\).
There are two kinds of categories.
\(v_1\sim_{c_0}\cdots\sim_{c_0}v_n\succ_{c_0}\varnothing\succ_{c_0}z.\)
Thus every vertex type is eligible, all vertex types are tied, and \(z\) is ineligible.
\(v_i\succ_{c_e}v_j\succ_{c_e}z\succ_{c_e}\varnothing.\)
All remaining types appear below \(\varnothing\), in any fixed strict order. Hence exactly the two endpoint types and \(z\) are eligible.
The policy order is \(\pi_T=(z,v_1,\ldots,v_n)\).
The construction has \(\tau=n+1\) types and \(m=q+1\) categories. Every rational number uses \(O(\log n+\log q)\) bits, and all orders can be listed explicitly in polynomial space. Thus the reduction has polynomial input length.
Define
\(F=kd+qh.\)
Every allocation has total allocated mass at most \(F\), because \(F\) is the sum of all category capacities. We prove that a priority-respecting allocation attaining \(F\) exists for every set \(S\subseteq V\) of size \(k\).
Construct the allocation as follows.
All unspecified allocations are zero.
Mass feasibility. Each selected vertex type receives exactly \(d\). Each unselected vertex type receives at most \(qh<d\). Type \(z\) also receives at most \(qh<d\leq\mu_z\). Every category is filled exactly to capacity, and every assigned pair is eligible.
Respect of priorities.
Thus the constructed allocation respects priorities and has total mass \(F\). Consequently, the first objective’s optimum is exactly \(F\).
Moreover, writing
\(E(S)=\{\{i,j\}\in E:i,j\in S\},\)
this construction gives \(s_z=h|E(S)|\).
Consider any feasible priority-respecting allocation, and let
\(S_y=\{i\in V:s_{v_i}=d\}\)
be its fully served vertex types.
Each such type consumes mass \(d\). Therefore
\(|S_y|d\leq\sum_{t\in T}s_t\leq F=kd+qh<(k+1)d.\)
Since \(|S_y|\) is an integer, it follows that \(|S_y|\leq k\).
Now suppose \(y_{z,c_e}>0\) for an edge \(e=\{i,j\}\). Both endpoint types strictly outrank \(z\) in \(c_e\). Respect of priorities therefore requires
\(s_{v_i}=d,\qquad s_{v_j}=d.\)
Hence \(e\in E(S_y)\). Type \(z\) is ineligible for \(c_0\), so its entire allocated mass comes from such edge categories. Each has capacity \(h\), giving
\(s_z\leq h|E(S_y)|.\)
Because \(|S_y|\leq k\leq n\), we can extend \(S_y\) to a set of exactly \(k\) vertices. Adding vertices cannot remove induced edges. Consequently,
\(s_z\leq h\max_{\substack{S\subseteq V\\|S|=k}}|E(S)|.\)
This upper bound applies even to allocations that do not attain maximum total mass.
Let \(s_z^\star\) denote the maximum possible value of \(s_z\) among allocations attaining total mass \(F\).
Section 3 supplies an upper bound, while Section 2 supplies a maximum-total allocation attaining \(h|E(S)|\) for every \(k\)-vertex set \(S\). Therefore
\(s_z^\star=h\max_{\substack{S\subseteq V\\|S|=k}}|E(S)|.\)
Since \(z\) is first in the policy order, every allocation satisfying both requested objectives must have this value of \(s_z\).
A simple graph on \(k\) vertices has at most \(\binom{k}{2}\) edges, with equality exactly when those vertices form a clique. Thus
\(G\text{ contains a clique of size }k\quad\Longleftrightarrow\quad s_z^\star\geq h\binom{k}{2}.\)
An algorithm computing the requested optimal allocation would therefore decide CLIQUE: construct this instance, compute the allocation, sum its entries for \(z\), and compare that rational number with \(h\binom{k}{2}\). Construction, summation, and comparison all take polynomial time.
This proves \(\mathrm{NP}\)-hardness. In particular, an algorithm polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The reduction does not obstruct maximum-size allocation: Section 2 constructs one directly for any \(k\)-vertex set. It establishes hardness of the additional policy-order objective, already at its first coordinate.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated task. It establishes \(\mathrm{NP}\)-hardness of computing the required optimal allocation, even with dyadic masses and capacities and only one category containing eligible ties. No major or minor issues were found.
The decisive distinction is verified: the construction always admits an allocation filling every category, while maximizing the first policy coordinate encodes the maximum number of edges induced by \(k\) vertices.
The source problem is stated precisely: determine whether a simple undirected graph contains a clique of size \(k\). Its \(\mathrm{NP}\)-completeness is the standard result attributed to [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
The restrictions \(2\leq k\leq n\) and \(q\geq1\) are legitimate. Instances excluded by these restrictions have directly decidable answers. Consequently, solving the restricted instances would suffice to solve general CLIQUE with polynomial-time preprocessing.
Assessment: Correct; no missing hypothesis affects the reduction.
The parameter choices give
\(2^a\geq n+1\) and \(2^b\geq q+1\). Therefore,
\[
qh=d\frac{q}{2^b}<d,
\qquad
1-nd=\frac{2^a-n}{2^a}\geq d>0.
\]
Thus every vertex mass is positive, the distinguished mass is positive, and their sum is exactly \(1\). All masses and capacities are dyadic rationals.
The priorities specify valid weak orders on all types together with \(\varnothing\). Their eligibility sets are exactly those claimed:
The policy order is strict and places \(z\) first.
The numerical bit lengths and the explicit priority lists are polynomial in the source input length. Although the write-up says the orders can be listed in “polynomial space,” the prescribed lists also plainly take polynomial time to generate.
Assessment: Correct; the constructed instance satisfies every input requirement.
Fix any \(S\subseteq V\) with \(|S|=k\).
The shared category gives exactly \(d\) to each selected vertex, using exactly its capacity \(kd\). Selected vertices receive no edge-category mass: an internal edge assigns to \(z\), and every other edge assigns to an endpoint outside \(S\).
Each unselected vertex receives at most \(qh<d\). The distinguished type receives at most \(qh<d\leq\mu_z\). Hence every type satisfies its mass constraint.
Every edge category assigns exactly \(h\) to an eligible type. Thus all category constraints hold, and every category is filled.
Assessment: Correct, including the possibility that one unselected vertex receives mass from many edge categories.
Each recipient case satisfies the stated priority condition:
Types below \(\varnothing\) are ineligible and impose no requirements.
Consequently, the constructed allocation respects priorities. Its total mass is \(F=kd+qh\), which is also the universal upper bound obtained by summing category capacities.
Assessment: Correct. The maximum-total objective is established exactly.
For an arbitrary feasible allocation, each vertex in \(S_y\) receives exactly \(d\). Hence
\[
|S_y|d\leq\sum_{t\in T}s_t\leq kd+qh<(k+1)d.
\]
Since \(d>0\) and \(|S_y|\) is an integer, \(|S_y|\leq k\).
If \(z\) receives positive mass in \(c_e\), both endpoints strictly outrank it. Priority respect requires both endpoints to be fully served, so \(e\in E(S_y)\).
Because \(z\) is ineligible for \(c_0\), its entire allocation comes from these edge categories. Their individual capacities imply
\[
s_z\leq h|E(S_y)|.
\]
Extending \(S_y\) to exactly \(k\) vertices is valid because \(|S_y|\leq k\leq n\). Such extension cannot remove induced edges.
Assessment: Correct. This argument covers arbitrary splitting and does not assume that the allocation attains maximum total mass.
Section 5 gives the claimed upper bound on \(s_z\). The construction attains that bound for a \(k\)-vertex set maximizing its induced edge count, while also attaining total mass \(F\). Thus the equality claimed for \(s_z^\star\) follows.
Since \(z\) is first in the policy order, every requested lexicographic optimum must attain \(s_z^\star\). Later coordinates cannot change this requirement.
A simple graph induced by \(k\) vertices has at most \(\binom{k}{2}\) edges, attaining that number exactly for a clique. The threshold equivalence is therefore correct, including when \(q<\binom{k}{2}\).
Assessment: Correct; both directions of the reduction hold.
A hypothetical polynomial-time algorithm returning the requested rational allocation would have polynomial-length output. Summing its entries for \(z\) and comparing exactly with the stated rational threshold takes polynomial time. The reduction therefore establishes the claimed computational hardness.
The proof does not claim membership in a complexity class or hardness of maximizing total mass alone. Its final discussion accurately identifies the additional policy objective as the source of hardness.
Actionable feedback: No repair or additional 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.