Efficient and Fair Healthcare Rationing

The strongest positive case is a high-multiplicity version of the paper’s core rationing problem, with Theorem 4.2 as the lead anchor. The paper contains no comparable hardness theorem: the NP-hardness statement in related work concerns a different two-sided matching model and is cited rather than proved here. Thus this is necessarily a Class A case.

Take a finite set of categories \(C\), with per-capita capacities \(\rho_c\in\mathbb{Q}_{\ge 0}\), and a finite set of complete patient types \(T\). A type records everything relevant to the rationing problem: its eligibility set, and its position in every category’s priority order. The society is a rational distribution \(\mu\in\mathbb{Q}_{\ge0}^{T}\), with \(\sum_t\mu_t=1\). The number of actual patients may be enormous; \(\tau=|T|\) is the meaningful structural parameter.

The action is a mass allocation \(y=(y_{t,c})\), where \(y_{t,c}\) is the mass of type \(t\) receiving a unit from category \(c\). Individuals still receive an integral bundle—one unit or none—while \(y_{t,c}\) is fractional only because it aggregates many identical patients. The constraints are

\[ \sum_c y_{t,c}\le \mu_t,\qquad \sum_t y_{t,c}\le \rho_c,\qquad y_{t,c}=0 \]

whenever \(t\) is ineligible for \(c\). Let \(u_t=\mu_t-\sum_c y_{t,c}\) be unmatched mass. The natural continuous version of respecting priorities requires that, whenever \(t'\succ_c t\) and \(y_{t,c}>0\), we have \(u_{t'}=0\): a lower-priority type cannot receive category \(c\) while higher-priority eligible mass remains unmatched. The objective is to maximize \(\sum_{t,c}y_{t,c}\).

This regime is quite plausible for healthcare rationing: millions of patients are grouped by finitely many combinations of age band, occupation, vulnerability, eligibility, and priority class. A type is not merely a preference type artificially imposed for computation; it is a complete policy-relevant patient class. For example, all frontline workers in a given age and vulnerability band can share eligibility and priority information across all reserve categories. The quantities \(\mu_t\) and \(\rho_c\) then express population shares and doses per capita, which is exactly the scale at which a national allocation policy is stated.

The lead anchor is Theorem 4.2, proved in this paper. It states that, for every linear order \(\succ_\pi\) over agents, the Reverse Rejecting rule \(\mathrm{REV}_\pi\):

(i) complies with eligibility requirements;
(ii) respects category priorities;
(iii) returns a matching of maximum size among feasible matchings;
(iv) respects improvements, meaning that an agent already matched cannot become unmatched when that agent’s priority rises; and
(v) can be computed in strongly polynomial time.

I would mirror it with the following problem.

Continuous Reverse-Rejecting Mass Allocation. Given \((T,\mu,C,\rho)\), the category-specific weak priority orders, and a policy order \(\pi_T\) over types, compute a rational mass allocation \(y\) that is priority-respecting, has maximum total allocated mass, and is lexicographically maximal in the vector

\[ \left(\sum_c y_{t_1,c},\ldots,\sum_c y_{t_\tau,c}\right), \]

where \(t_1\succ_{\pi_T}\cdots\succ_{\pi_T}t_\tau\). This is the type-level quotient of Reverse Rejecting: it preserves as much matched mass as possible from the most protected types, subject to the same eligibility, priority, and maximum-size requirements.

The expected outcome is Class A. The discrete proof repeatedly calls a maximum-cardinality matching algorithm. In the continuous version, the corresponding primitive is a capacitated bipartite-flow or transportation computation over types and categories, with lexicographic refinement. The likely complexity target is polynomial in \(m\), \(\tau\), and the encoding length of \(\mu\), \(\rho\), and the priority data. The interesting questions are whether the exact type-level analogue preserves the improvement guarantee, whether every continuous allocation satisfying eligibility, priorities, and maximum size is obtainable from some type order, and how rational solutions round back to finite populations.

This is not merely replacing \(n\) by a real number. The population itself is now the input object, capacities are scaled per capita, and the output is a mass allocation representing integral allocations to a huge collection of indistinguishable patients. It also exposes the paper’s real structural reason for tractability: maximum matching survives aggregation, while the named individuals disappear.

A second, genuinely distinct anchor is Theorem 5.6, also proved in this paper. It states that the Smart Reverse Rejecting rule \(\mathrm{S\text{-}REV}_\pi\):

(i) complies with eligibility requirements;
(ii) yields a maximum beneficiary assignment;
(iii) respects priorities;
(iv) respects improvements;
(v) satisfies order preservation between first-processed unreserved units, preferential units, and last-processed unreserved units; and
(vi) is polynomial-time computable.

Its continuous mirror is Continuous Smart Reverse-Rejecting Allocation. The instance has preferential categories \(C_p\), universal categories \(c_u^1,c_u^2\), type masses \(\mu_t\), per-capita capacities, heterogeneous preferential priorities, and a baseline order \(\pi_T\). The rule must:

• allocate mass to \(c_u^1\), in baseline order, whenever doing so preserves the maximum achievable preferential-category mass;
• apply continuous Reverse Rejecting to the remaining mass and preferential categories;
• allocate \(c_u^2\) to the remaining mass in baseline order.

The required output maximizes

\[ \sum_{t}\sum_{c\in C_p}y_{t,c} \]

subject to eligibility and capacity constraints, respects priorities and improvements, and satisfies the continuous order-preservation condition. In support form, if positive mass of type \(t\) receives \(c_u^1\), while positive mass of type \(t'\) receives a category for which \(t\) is eligible, then \(t'\succ_{\pi_T}t\); the analogous condition for \(c_u^2\) uses the relevant category priority.

This is plausible in exactly the paper’s healthcare setting: some vaccine doses are universal, some are reserved for vulnerable or occupational groups, and policy may insist that universal doses be processed before or after reserve doses. The expected classification is again Class A, using repeated capacitated matching computations. Further questions include continuity under small changes in \(\mu\), exact finite-population rounding, uniqueness of the mass allocation, and whether the paper’s soft-reserve extension admits the same type-level treatment.

The weakest point is the anchor gate. A strict reader could say that Theorems 4.2 and 5.6 are theorems about allocation rules whose proofs include polynomial computability, rather than standalone complexity classifications of explicitly named decision problems. If “in P” is interpreted narrowly, the paper may be judged to contain no qualifying computational anchor. There is also a genuine modelling choice in replacing the individual order \(\pi\) by an order over types: if individual identities within a type carry substantive priority information, the mirror loses something. The positive case therefore depends on reading \(\pi\) as a policy-level tie-breaking or baseline order, which is natural for the healthcare regime but not forced by every instance in the paper.