Answer: —
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe GDA-RO algorithm is strategy-proof for doctors and yields a non-wasteful and fair outcome under re- gional weights.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of doctor types \(T\) with rational masses \(\mu_t\), preferences, eligibility, and hospital and regional priority tiers, together with hospitals partitioned into regions, rational per-capita capacities \(q_h\), regional quotas \(\delta_r\), and regional weights \(w(h)\), can one compute a direct mechanism returning assignment masses \(x_{t,h}\) and unmatched masses \(x_{t,\emptyset}\)? Require \(\sum_{h\in H}x_{t,h}+x_{t,\emptyset}=\mu_t\), \(\sum_{t\in T}x_{t,h}\le q_h\), and \(\sum_{t\in T,\,h\in r}x_{t,h}\le\delta_r\). The induced lottery for a member of type \(t\) assigns hospital \(h\) with probability \(x_{t,h}/\mu_t\); require truthful preference reporting to be weakly preferred in stochastic dominance to any misreport by an infinitesimal member, and require mass-adapted versions of the paper's fairness and non-wastefulness conditions under regional weights.
A society is given by its support: the list of \(\tau\) doctor types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(m=|H|\), and let \(L\) be the total input bit length.
Hospitals are partitioned into nonempty regions \(R\). Hospital capacities \(q_h\) and regional upper quotas \(\delta_r\) are nonnegative binary rationals; weights \(w(h)\) are binary rationals. Each type has fixed eligibility and hospital and regional priority tiers, and a strict preference order \(\succ_t\) over eligible hospitals and \(\emptyset\). Eligible contracts are acceptable to both their hospital and region; no consistency between hospital and regional priorities is assumed. Strict priority comparisons \(\succ_h,\succ_r\) compare tiers, leaving equal tiers tied.
An assignment consists of nonnegative masses satisfying \(\sum_{h\in H}x_{t,h}+x_{t,\emptyset}=\mu_t\), \(\sum_t x_{t,h}\le q_h\), and \(\sum_{t,h\in r}x_{t,h}\le\delta_r\), with \(x_{t,h}=0\) whenever \(h\) is ineligible or \(\emptyset\succ_t h\).
For any mass array \(y\) and \(\varepsilon>0\), define \(A_\varepsilon(y,h)=w(h)\) if \(\sum_t y_{t,h}+\varepsilon\le q_h\), and \(A_\varepsilon(y,h)=-\infty\) otherwise. Let \(e_{t,b}\) denote the unit array at coordinate \((t,b)\), including \(b=\emptyset\).
Non-wastefulness forbids any eligible \(h\in r\), source \(b\), and \(0<\varepsilon\le x_{t,b}\) with \(h\succ_t b\) such that \(y=x-\varepsilon e_{t,b}\) and \(y+\varepsilon e_{t,h}\) is feasible, and either \(b=\emptyset\), \(b\notin r\), or \(b\in r\) and \(A_\varepsilon(y,h)>A_\varepsilon(y,b)\), or these two values are equal and \((t,h)\succ_r(t,b)\).
Fairness forbids disjoint positive portions of equal mass \(\varepsilon\) at \((t,b)\) and \((s,j)\), with an eligible \(h\succ_t b\) and \(h,j\in r\), such that, for \(y=x-\varepsilon e_{s,j}\), either \(h=j\) and both \((t,h)\succ_h(s,j)\) and \((t,h)\succ_r(s,j)\), or \(h\ne j\) and \(A_\varepsilon(y,h)>A_\varepsilon(y,j)\), or \(h\ne j\), these values are equal, and \((t,h)\succ_r(s,j)\). The portions may belong to the same type.
A direct mechanism must specify a lottery for every strict preference report by a member with fixed eligibility and priority tiers, including reports absent from the support. On supported reports it assigns probability \(x_{t,h}/\mu_t\). An infinitesimal member's report leaves the aggregate society unchanged; truthful reporting must weakly stochastic-dominate every misreport under that member's true preferences. Feasibility, individual rationality, fairness, and non-wastefulness must hold at every reported society.
Does such a direct mechanism exist on this entire domain, and, if it exists, is exact computation of its assignment masses and individual report lotteries polynomial-time in \(m,\tau,|R|,L\), or NP-hard?
For finite doctors with strict priorities, GDA-RO is strategy-proof and returns an individually rational, feasible, fair and non-wasteful assignment under regional weights ([Sun–Todo–Yokoo](https://www.ijcai.org/proceedings/2021/0058.pdf)).
Continuum matching has conditional stability-existence results for convex, continuous firm choices ([Che–Kim–Kojima](https://onlinelibrary.wiley.com/doi/pdf/10.3982/ecta13547)); these concern a different formulation. No result settling the exact mechanism question above was located.
A direct mechanism exists on the entire stated domain. Its outputs can be chosen rational with polynomial bit length, and an exact finite construction is available.
The general complexity classification remains unresolved. The results below additionally establish:
All arguments are self-contained. In particular, the polynomial bit-length bound is quantified.
Computing an individual lottery means evaluating it for one supplied report. Explicitly listing lotteries for every strict report could itself require factorial output size.
For a feasible assignment $x$, define its hospital and regional loads by
$$ \ell_h=\sum_t x_{t,h}, \qquad \ell_r=\sum_{h\in r}\ell_h. $$
For two eligible contracts in the same region, define
$$ (t,h)\triangleright_r(s,j) $$
to mean
$$ w(h)>w(j), $$
or
$$ w(h)=w(j) \quad\text{and}\quad (t,h)\succ_r(s,j). $$
This auxiliary comparison incorporates weights and regional priority, but does not incorporate hospital priority.
For a feasible, individually rational assignment, non-wastefulness fails exactly when there exist an eligible hospital $h\in r$ and a source $b$ such that
$$ x_{t,b}>0, \qquad h\succ_t b, \qquad \ell_h<q_h, $$
and one of the following holds:
Fairness fails exactly when there exist a source $(t,b)$, an occupant $(s,j)$, and an eligible target $h\succ_t b$, with $h,j\in r$, such that
$$ x_{t,b}>0, \qquad x_{s,j}>0, $$
and either
$$ h=j, \qquad (t,h)\succ_h(s,h), \qquad (t,h)\succ_r(s,h), $$
or
$$ h\ne j, \qquad \ell_h<q_h, \qquad (t,h)\triangleright_r(s,j). $$
For non-wastefulness, strict preference implies $h\ne b$. Moving a positive portion from $b$ to $h$ requires hospital slack at $h$. If the source lies outside $r$, it also requires regional slack. If the source lies inside $r$, regional load is unchanged.
Whenever the proposed move is feasible,
$$ A_\varepsilon(x-\varepsilon e_{t,b},h)=w(h). $$
If $b\in r$, restoring the removed source portion restores its original feasible hospital load, so
$$ A_\varepsilon(x-\varepsilon e_{t,b},b)=w(b). $$
The comparison in the definition therefore becomes precisely $\triangleright_r$.
Conversely, the stated strict slack conditions permit a sufficiently small positive $\varepsilon\le x_{t,b}$. All constraints other than the target hospital and, when applicable, the target region either remain unchanged or become weaker. Individual rationality of the move follows from $h\succ_t b$ and positive, individually rational source mass.
For fairness with $h\ne j$, restoring the occupant portion gives
$$ A_\varepsilon(x-\varepsilon e_{s,j},j)=w(j). $$
Because the removal occurred at another hospital,
$$ A_\varepsilon(x-\varepsilon e_{s,j},h)=w(h) $$
is possible for positive $\varepsilon$ exactly when $\ell_h<q_h$. The prohibited comparison is consequently $\triangleright_r$.
For $h=j$, the definition directly requires the two strict priority comparisons displayed above.
Conversely, choose $\varepsilon$ sufficiently small to fit within both positive masses and, in the different-hospital case, within target-hospital slack. Choosing
$$ \varepsilon\le \frac12\min\{x_{t,b},x_{s,j}\} $$
also permits disjoint portions if the source and occupant coordinates coincide. Thus the finite conditions supply the required witness. ∎
There are polynomially many candidate witnesses: at most
$$ O\!\left(\tau^2(m+1)m^2\right). $$
Hence feasibility, individual rationality, fairness, and non-wastefulness of a supplied rational assignment can all be checked in polynomial time in its encoding length.
Write $a$ for a member’s fixed eligibility and priority attributes. A supported type $t$ consists of attributes $a_t$ and a strict preference order.
For each region, write $\rho_r(a,h)$ for the ordered regional tier label of an eligible contract; smaller labels denote higher priority. These are the actual ordered tier labels, so an absent report’s attributes can also be compared with a supported contract’s tier.
Introduce a lottery variable $u$ uniformly distributed on $(0,1)$. For $h\in r$, define the key
$$ K(a,h,u)=\bigl(-w(h),\rho_r(a,h),u\bigr), $$
ordered lexicographically, with smaller keys ranked higher.
In particular,
$$ (t,h)\triangleright_r(s,j) \quad\Longrightarrow\quad K(a_t,h,u)<K(a_s,j,v) $$
for every $u,v\in(0,1)$.
Hospital priorities do not enter this key. This is sufficient because same-hospital fairness in the question requires a strict regional comparison as well as a strict hospital comparison.
Choose cutoffs $c_h$ and $c_r$. For a positive quota, a cutoff is either $+\infty$ or a pair
$$ c=\bigl((-w,\rho),z\bigr), \qquad z\in[0,1]. $$
For a zero quota, its cutoff is $-\infty$.
Define the menu
$$ \mathcal M_a(u) = \{\emptyset\} \cup \left\{ h: h\text{ is eligible for }a,\ K(a,h,u)<c_h,\ K(a,h,u)<c_{r(h)} \right\}. $$
For any strict report, select its most-preferred member of this menu. For a supported type, let $p_{t,b}$ denote the resulting probability and put
$$ x_{t,b}=\mu_t p_{t,b}. $$
A cutoff vector is a certificate if these masses are feasible and
$$ c_h\ne+\infty \quad\Longrightarrow\quad \ell_h=q_h, $$
and
$$ c_r\ne+\infty \quad\Longrightarrow\quad \ell_r=\delta_r. $$
Thus every restrictive cutoff certifies fullness. In particular,
$$ \ell_h<q_h\Longrightarrow c_h=+\infty, \qquad \ell_r<\delta_r\Longrightarrow c_r=+\infty. $$
For any attributes $a$ and hospital $h$, availability has the form
$$ h\in\mathcal M_a(u) \quad\Longleftrightarrow\quad u<z_{a,h} $$
for a threshold $z_{a,h}\in[0,1]$.
To obtain this threshold from one cutoff:
The hospital’s final threshold is the minimum of its hospital and regional thresholds.
For a supported type, let
$$ B_t=\{h:h\text{ is eligible and }h\succ_t\emptyset\}, $$
and define
$$ v_{t,h} = \max\left( \{z_{a_t,g}:g\in B_t,\ g\succ_t h\}\cup\{0\} \right). $$
Then
$$ p_{t,h} = \max\{0,z_{a_t,h}-v_{t,h}\}, \qquad h\in B_t, $$
and
$$ p_{t,\emptyset} = 1-\max\left( \{z_{a_t,h}:h\in B_t\}\cup\{0\} \right). $$
All other hospital probabilities are zero. Indeed, selecting $h$ means that $u$ is below its threshold and above every threshold of an acceptable hospital preferred to it.
Fix the aggregate society, a member’s attributes $a$, its true preference order $P$, and another report $P'$.
For every $u$, both reports face the same menu $\mathcal M_a(u)$. Truthful reporting selects its $P$-best element. Consequently, the truthful outcome is weakly preferred under $P$ to the outcome selected by $P'$ at that same $u$.
For every initial segment of $P$, membership of the misreported outcome in that segment implies membership of the truthful outcome. Taking probabilities proves weak stochastic dominance.
This argument applies whether or not either report occurs in the support. It uses exactly the stated infinitesimal interpretation: the member’s report leaves the aggregate society and its chosen certificate unchanged.
Individual rationality follows because $\emptyset$ is always available. Feasibility is part of the certificate definition.
Suppose a witness from Lemma 1 exists. Its target hospital has slack, hence $c_h=+\infty$.
If the source lies outside the target region, that region also has slack, hence $c_r=+\infty$. The preferred target is therefore available whenever type $t$ receives $b$, contradicting menu selection.
If $b\in r$, the witness requires
$$ (t,h)\triangleright_r(t,b). $$
Thus, at every $u$,
$$ K(a_t,h,u)<K(a_t,b,u). $$
Whenever the menu selects $b$, its key is below $c_r$, so the target’s key is also below $c_r$. Together with $c_h=+\infty$, this makes the preferred target available. Again menu selection gives a contradiction.
Suppose a witness from Lemma 1 exists. Positive source and occupant mass supply realizations $u,v$ at which type $t$ receives $b$ and type $s$ receives $j$.
If $h\ne j$, target-hospital slack gives $c_h=+\infty$, while
$$ (t,h)\triangleright_r(s,j) $$
gives
$$ K(a_t,h,u)<K(a_s,j,v)<c_r. $$
The target is available to the source member, contradicting $h\succ_t b$.
If $h=j$, strict regional priority gives
$$ K(a_t,h,u)<K(a_s,h,v). $$
The occupant’s key lies below both $c_h$ and $c_r$, so the source member’s target key does too. This is the same contradiction.
No argument requires distinct source and occupant types. Thus every certificate satisfies precisely the fairness and non-wastefulness conditions in the question.
The construction uses finite replicas only to prove existence; it does not claim an efficient algorithm in binary input length.
Give hospitals integer capacities $Q_h$, regions integer capacities $D_r$, and contracts a strict order within each region.
For a proposal set $S_r$, process its contracts in that order. Accept a contract whenever both its hospital and regional quotas permit it.
Fix a proposed contract $e$ at hospital $h\in r$. Let $n_g(e,S_r)$ be the number of proposals at hospital $g$ preceding $e$. The number accepted before reaching $e$ is
$$ \min\left\{ D_r,\ \sum_{g\in r}\min\{Q_g,n_g(e,S_r)\} \right\}. $$
Without the regional quota, the rule accepts the first $Q_g$ proposals at each hospital. The regional quota truncates that sequence after its first $D_r$ acceptances, proving the formula.
Therefore $e$ is rejected exactly when
$$ n_h(e,S_r)\ge Q_h $$
or
$$ \sum_{g\in r}\min\{Q_g,n_g(e,S_r)\}\ge D_r. $$
Both conditions persist when proposals are added. Rejection is permanent.
Moreover, in the final greedy choice, every rejected contract is blocked by either:
If the regional prefix has filled its quota, the second conclusion holds. Otherwise the rejection formula forces the first.
Initially no contracts have been proposed. An unheld doctor proposes its best unproposed acceptable contract. Regions recompute their greedy choices from all proposals received so far.
Permanent rejection implies that a doctor has at most one held contract: it proposes again only after its previous proposal is rejected, and earlier rejected proposals cannot return.
The process terminates because each contract is proposed at most once. Every acceptable contract preferred to a doctor’s final assignment was proposed and rejected.
Order contracts first by their keys $K$, then break remaining ties by fixed doctor and hospital identifiers. For each full hospital or region with positive quota, set its cutoff to the raw key of its worst assigned contract. Use $+\infty$ for a quota with slack and $-\infty$ for a zero quota.
The rejection lemma gives:
Tie-breaking does not invalidate these statements: preceding contracts have raw keys weakly smaller even when their raw keys coincide.
Thus the finite assignment agrees with strict-cutoff menu selection except possibly at lottery coordinates equal to cutoff coordinates.
Choose a common denominator $D$ for all masses and quotas. For
$$ N=kD, \qquad k=1,2,\ldots, $$
create
$$ n_t=N\mu_t $$
doctors of each supported type. Give hospitals capacities $Nq_h$ and regions quotas $N\delta_r$.
Assign the doctors of type $t$ the values
$$ u_{t,i}=\frac{i-\frac12}{n_t}, \qquad i=1,\ldots,n_t. $$
Run the finite proposal process.
Put
$$ d=m+|R|. $$
Each cutoff is either an infinity or has a weight-tier pair drawn from the fixed finite collection of supported eligible contracts and a coordinate in $[0,1]$. Extract a subsequence along which:
The second extraction is possible by compactness of a finite-dimensional cube. Let $c$ be the limiting cutoff vector.
Once the statuses and pairs are fixed, every availability threshold is a minimum of constants and cutoff coordinates. The probability formulas in Section 2 are therefore continuous in those coordinates.
For each supported type, at most $d$ grid doctors have a lottery coordinate equal to a cutoff coordinate. Away from these doctors, the finite assignment agrees with its strict menu.
A midpoint grid of $n_t$ points estimates the length of any interval with error at most $2/n_t$. If $x^{(N)}_{t,b}$ denotes the finite assigned count divided by $N$, and $p^{(N)}_{t,b}$ its strict-menu probability, then
$$ \left| x^{(N)}_{t,b}-\mu_t p^{(N)}_{t,b} \right| \le \frac{d+2}{N}. $$
Here each exceptional doctor has mass $1/N$, and
$$ \mu_t\frac{2}{n_t}=\frac2N. $$
Consequently,
$$ x^{(N)}_{t,b}\longrightarrow \mu_t p_{t,b}. $$
Feasibility passes to the limit. Every restrictive cutoff had its quota exactly full throughout the chosen subsequence, so its limiting quota is also full. Zero quotas retain cutoff $-\infty$.
Thus $c$ is a certificate. Combined with Section 3, this proves mechanism existence on the entire domain.
For every positive-quota hospital and region, enumerate either $+\infty$ or a finite cutoff pair drawn from supported eligible contracts in that container.
For each such choice, enumerate a weak ordering of the finite cutoff coordinates. Impose coordinate bounds
$$ 0\le z_i\le1. $$
Within one enumerated case, pair comparisons and the coordinate ordering determine every minimum, maximum, and positive-part branch in Section 2. Every probability is consequently a constant or a difference of two members of
$$ \{0,1,z_1,\ldots,z_f\}, $$
where $f\le d$ is the number of finite cutoffs.
Feasibility and restrictive-cutoff fullness become rational linear constraints. There are at most $6d$ inequalities after converting equalities to pairs of inequalities:
Equal coordinates cause no difficulty: alternative branches then have equal values.
The limiting certificate belongs to some enumerated case. Its linear program is therefore feasible. Its feasible set is bounded by the coordinate bounds.
Use the standard exact rational linear-programming theorem: feasibility and optimization are solvable in time polynomial in the number of variables, number of constraints, and coefficient encoding length. A rational vertex can be selected deterministically by sequentially maximizing the coordinates and fixing their optimal values. The resulting unique point is a vertex.
Selecting the first feasible case and this vertex defines a deterministic certificate choice at every reported society.
Take $D$ to be the product of the denominators appearing in the masses and quotas. Since their encodings are included in $L$,
$$ D\le 2^L. $$
An affine probability has coefficients in $\{-1,0,1\}$. A hospital or regional load is a sum of at most $\tau m$ such expressions weighted by masses.
For any one coefficient, its absolute value is at most
$$ m\sum_t\mu_t=m. $$
The same bound applies to the absolute constant term. Input quotas have absolute value at most $2^L$.
After clearing denominators using $D$, all matrix entries and right-hand sides therefore have absolute value at most $2^B$, where it is sufficient to take
$$ B=2L+\left\lceil\log_2(m+2)\right\rceil+3. $$
Suppose $f>0$. At a vertex, the active constraint normals span $\mathbb R^f$. Otherwise, a nonzero direction orthogonal to all active normals would permit sufficiently small perturbations in both directions, contradicting extremality.
Choose $f$ independent active constraints. The vertex solves
$$ Az=b, $$
where $A$ and $b$ are integer-valued and their entries have absolute value at most $2^B$.
Hadamard’s inequality bounds both $\det A$ and every Cramer numerator by
$$ f^{f/2}2^{fB}. $$
Hence every coordinate has numerator and denominator bit length at most
$$ 2+fB+\left\lceil\frac f2\log_2 f\right\rceil. $$
All coordinates can be represented over the common denominator $|\det A|$. Every probability is a constant or a coordinate difference, so its denominator divides $|\det A|$. Every assignment mass can be represented over
$$ D|\det A|. $$
Because assignment masses lie in $[0,1]$, their numerators obey the same bound as their denominators. Their bit lengths are polynomial in $m$ and $L$.
If $f=0$, all probabilities are constants and the conclusion follows directly from the input masses.
This proves the polynomial bit-length claim without leaving denominator clearing implicit.
A supplied certificate can be checked in polynomial time: compute its thresholds and probabilities, then check quotas and fullness exactly.
The construction is thus a total search problem on valid society inputs with polynomial-size rational witnesses and polynomial-time verification.
There are at most
$$ (\tau m+1)^d d! $$
enumerated cases. Since regions partition $m$ hospitals into nonempty sets,
$$ d=m+|R|\le2m. $$
Therefore, for every fixed $m$, this construction runs in polynomial time in the remaining input parameters. It is not a polynomial-time bound when $m$ varies.
Once a certificate is available, an individual report requires only:
This is polynomial-time exact computation in the society and query encoding lengths, including for reports absent from the support.
This section gives an additional tractable case that permits strict regional priorities and arbitrary hospital priorities.
Assume:
$$ w(h)=W_r \qquad\text{for every }h\in r. $$
$$
(a,h)\succ_r(a',j)
\quad\Longleftrightarrow\quad
\gamma(a)<\gamma(a').
$$
Equal doctor tiers give tied regional priorities.
Eligibility and hospital priorities remain unrestricted. Strict preferences also remain unrestricted.
Process the supported doctor tiers in increasing order.
During one tier, use a local time interval $[0,1]$. Each supported type $t$ in that tier consumes mass at rate $\mu_t$. At each time, it chooses its most-preferred option from:
Let $\bar q_h$ and $\bar\delta_r$ denote residual capacities. If the currently selected hospitals induce rates
$$ \lambda_h = \sum_{\substack{t\text{ in the current tier}\\t\text{ currently chooses }h}} \mu_t, \qquad \lambda_r=\sum_{h\in r}\lambda_h, $$
and the current local time is $v$, advance by
$$ \Delta = \min\left( \{1-v\} \cup \left\{\frac{\bar q_h}{\lambda_h}:\lambda_h>0\right\} \cup \left\{\frac{\bar\delta_r}{\lambda_r}:\lambda_r>0\right\} \right). $$
Assign $\mu_t\Delta$ to each type’s current option and update residual capacities.
An exhausted hospital closes permanently. An exhausted region permanently closes all its hospitals. At local time $1$, proceed to the next tier.
Every stage except a tier endpoint exhausts at least one previously unexhausted hospital or region. If there are $k$ supported tiers, the total number of stages is at most
$$ m+|R|+k\le m+|R|+\tau. $$
For a member in a supported tier, draw $u$ uniformly from that tier’s local interval $(0,1)$ and give it the most-preferred eligible open hospital or $\emptyset$ at time $u$, according to its report.
This agrees with the supported assignment masses: consuming at rate $\mu_t$ over an interval of length $\Delta$ assigns mass $\mu_t\Delta$.
An absent preference report with the same fixed attributes uses the same tier timeline. If an attribute profile has a tier absent from the support, use the available hospitals after all higher supported tiers have finished and before lower supported tiers begin; this menu is constant because that absent tier consumes no aggregate mass.
The aggregate timeline is unchanged by an infinitesimal member’s report. At every $u$, truthful reporting selects its most-preferred member of the same report-independent menu. The pointwise argument from Section 3 proves weak stochastic dominance over every misreport.
The event rule stops consumption when a quota is reached, so quotas are never exceeded. Each supported type consumes at rate $\mu_t$ for one unit of local time, including consumption of $\emptyset$, hence
$$ \sum_{h\in H}x_{t,h}+x_{t,\emptyset}=\mu_t. $$
Eligibility is imposed in each menu. Because $\emptyset$ is available, no type consumes an unacceptable hospital.
Consider the characterization in Lemma 1.
If the source lies outside the target region, a prohibited move requires final slack at both the target hospital and target region. These resources never exhausted, so the target was open throughout type $t$’s tier. A type could not consume a less-preferred source while that eligible target was open.
If the source lies inside the target region, the two hospital weights are equal. The two contracts also have the same regional priority because they belong to the same type. Thus
$$ (t,h)\triangleright_r(t,b) $$
is false, and no prohibited within-region move exists.
First suppose $h\ne j$. Equal regional weights mean that a fairness witness must have
$$ \gamma(a_t)<\gamma(a_s). $$
The source tier was therefore processed before the occupant tier.
Positive mass at $(s,j)$ implies that its region had not exhausted during the earlier source tier. Target-hospital slack implies that the target hospital never exhausted. Thus $h$ was open throughout the source tier, contradicting positive consumption of $b$ with $h\succ_t b$.
Now suppose $h=j$. A witness again requires
$$ \gamma(a_t)<\gamma(a_s). $$
Positive later-tier consumption at $h$ implies that neither $h$ nor its region exhausted during the earlier source tier. Hence $h$ was open throughout that tier, giving the same contradiction.
The proof excludes these witnesses using regional priority alone, so arbitrary hospital priorities cause no problem.
Use a common input denominator $D\le2^L$. Every positive consumption rate has the form
$$ \lambda=\frac{M}{D}, \qquad 1\le M\le D, $$
because the total society mass is $1$.
Suppose current quantities have a common denominator $E$ divisible by $D$. A quota event has duration
$$ \frac{a/E}{M/D}=\frac{aD}{EM}, $$
and a tier endpoint has duration with denominator dividing $E$.
After the updates, a valid common denominator is
$$ E'=EDM, $$
taking $M=1$ for a tier endpoint. Consequently, after $s$ stages,
$$ \log_2 E \le \log_2 D+2s\log_2 D = O\!\left((m+|R|+\tau)L\right). $$
Residual capacities are bounded by their input values, assignment masses by $1$, and local times by $1$. Their numerator lengths are therefore polynomial as well.
Each stage needs polynomially many comparisons and rational operations, and there are polynomially many stages. Individual report lotteries are obtained by summing the lengths of the intervals on which each reported option is best.
Thus the entire mechanism is exactly computable in polynomial time on this subclass, with no bound on $m$.
The unrestricted domain allows hospital-dependent regional priorities and arbitrary weights within a region. The tier-consumption proof above does not cover either feature.
The full-domain cutoff construction establishes existence, exact finite computability, and polynomial-size certificates. Its enumeration remains exponential when $m$ varies. Polynomial-size certificates and polynomial-time verification do not establish polynomial-time construction.
No hardness result is proved here. Consequently, the requested full-domain polynomial-time-versus-hardness classification remains open.
⟨structured verdict parsed — rendered above⟩
The output establishes full-domain mechanism existence and several computational results, but it does not settle the unrestricted polynomial-time-versus-hardness question. Its existence argument is sound as written. The main substantive omission is explicitly acknowledged by the prover. There is also a minor inconsistency between “weak ordering” enumeration and the stated enumeration bounds.
For non-wastefulness, strict preference gives $h\ne b$. Removing mass from the source therefore does not create hospital slack at $h$. A feasible positive transfer requires precisely $\ell_h<q_h$, together with $\ell_r<\delta_r$ when the source is outside the target region.
When $b\in r$, restoring the removed source mass restores its original feasible hospital load. Thus both availability values in the comparison are finite and equal to the corresponding weights. The comparison reduces correctly to $(t,h)\triangleright_r(t,b)$.
The converse correctly uses sufficiently small positive mass. Individual rationality of the target follows from positive, individually rational source mass and $h\succ_t b$.
For different-hospital fairness, restoring the occupant gives $A_\varepsilon(y,j)=w(j)$. Because removal at $j$ does not change the load at $h$, the target value is finite for some positive $\varepsilon$ exactly when $\ell_h<q_h$. An unavailable target cannot satisfy either comparison against the finite value $w(j)$.
Same-hospital fairness is recorded directly from the definition. The restriction
$$
\varepsilon\le \frac12\min\{x_{t,b},x_{s,j}\}
$$
correctly handles coincident source and occupant coordinates by permitting disjoint portions. No distinct-type assumption has been introduced.
The candidate count is polynomial, and exact rational verification of the resulting conditions is polynomial in the assignment’s encoding length.
The lexicographic key correctly ensures
$$
(t,h)\triangleright_r(s,j)
\Longrightarrow
K(a_t,h,u)<K(a_s,j,v)
$$
for every $u,v\in(0,1)$: either the weight coordinate or the regional tier coordinate decides the comparison before the lottery coordinate matters.
For each eligible hospital, comparison with a cutoff produces a threshold in $[0,1]$. Intersecting hospital and regional availability takes the minimum of the two thresholds.
A hospital $h$ is selected exactly when its threshold exceeds $u$ and every acceptable, more-preferred hospital’s threshold is at most $u$. Consequently, its selection set is an interval of length
$$
\max\{0,z_{a_t,h}-v_{t,h}\}.
$$
The outside option’s probability is also correct. Threshold endpoints have probability zero under the uniform lottery, so the strict cutoff convention creates no probability discrepancy.
The strategy-proofness proof uses a single report-independent menu and couples truthful and misreported outcomes using the same $u$. Truthful selection is pointwise weakly preferred under the true strict order. The implication for every initial segment establishes the required weak stochastic dominance.
This argument covers absent preference reports because the menu depends on fixed attributes and the aggregate certificate, rather than the member’s reported preference order. Keeping the certificate unchanged is justified by the task’s infinitesimal-report interpretation.
The non-wastefulness proof uses fullness correctly. A slack target hospital has unrestricted hospital cutoff. An outside-region source additionally supplies regional slack; an inside-region source supplies a strictly better regional key. Either condition makes the preferred target available whenever the source is selected.
The fairness proof also matches both cases in Lemma 1. For different hospitals, target slack and the strict auxiliary comparison suffice. For the same hospital, strict regional priority puts the target key below the occupant’s key and therefore below both relevant cutoffs. Ignoring hospital priorities is legitimate here because every same-hospital fairness witness also requires strict regional priority.
The formula
$$
\min\left\{
D_r,\sum_{g\in r}\min\{Q_g,n_g(e,S_r)\}
\right\}
$$
correctly counts accepted contracts preceding $e$. Before regional truncation, each hospital contributes its first $Q_g$ proposals; regional truncation retains the first $D_r$ acceptances.
The stated rejection conditions follow, including zero-capacity cases. Both conditions persist under additions to the proposal set, establishing permanent rejection.
Permanent rejection ensures that a doctor cannot acquire multiple held contracts through accumulated proposals. Finite termination and rejection of every acceptable contract preferred to the final outcome follow from the proposal rule.
In the final proposal set, each rejected contract is blocked by a full hospital or region containing preceding contracts. Passing from the strict tie-broken order to raw keys correctly gives weak inequalities. Assigned contracts also lie weakly below the worst assigned raw key in each relevant full container.
Away from lottery coordinates equal to cutoff coordinates, these weak inequalities determine strict-menu availability exactly. Hence the claimed finite assignment/menu agreement is justified.
The common denominator makes the replica counts and quotas integral. There are finitely many cutoff statuses and weight-tier pairs, so a subsequence with these data fixed exists. Compactness then applies to the finitely many cutoff coordinates in $[0,1]$.
With statuses and pairs fixed, the supported probabilities depend continuously on those coordinates through minima, maxima, and positive parts.
For each type, each finite cutoff coordinate can coincide with at most one midpoint-grid doctor. Thus the bound of at most $d$ exceptional doctors is valid. Every outcome’s menu-selection set is an interval, so the stated midpoint-grid error bound applies. The resulting estimate
$$
\left|x^{(N)}_{t,b}-\mu_t p^{(N)}_{t,b}\right|
\le \frac{d+2}{N}
$$
has the correct scaling.
Feasibility passes to the coordinatewise limit. Every restrictive cutoff corresponds to a container that was exactly full throughout the selected subsequence, so fullness passes to the limit as well. Zero quotas retain their stipulated cutoff.
This establishes a certificate on every valid society. Combined with the preceding mechanism argument, it establishes the claimed full-domain existence result.
Fixing cutoff pairs and coordinate orderings makes all supported probabilities affine. Feasibility and restrictive-cutoff fullness therefore become rational linear constraints. The existence argument supplies a feasible case.
The rational linear-programming theorem is stated with the relevant polynomial-time parameters. The enumerated systems have rational coefficients and bounded coordinate domains, so its hypotheses are satisfied. Sequential coordinate maximization produces a unique feasible point, and that point is a vertex.
The denominator and determinant calculations check out. The bound $D\le 2^L$ follows from taking the product of input denominators. The load-coefficient bound $m$ is conservative and valid. The proposed value of $B$ safely bounds denominator-cleared coefficients and right-hand sides.
Independent active constraints exist at a vertex. Hadamard’s inequality applies both to the active matrix and to each matrix used for a Cramer numerator, yielding
$$
f^{f/2}2^{fB}.
$$
The resulting coordinate, probability, and assignment-mass encoding lengths are polynomial. The case $f=0$ is handled correctly.
Minor issue: the literal enumeration of all weak orderings does not have at most $d!$ possibilities. Already for two coordinates there are three weak orderings, whereas $2!=2$.
This can also contradict the stated total-case bound. With one hospital, one region, positive quotas, and three distinct supported cutoff pairs available in each container, literal enumeration gives
$$
1+2\cdot3+3\cdot3^2=34
$$
cases, while the displayed bound gives
$$
(3+1)^2\,2!=32.
$$
The same terminology affects the claim of at most $f-1$ ordering inequalities: an explicitly imposed equality requires two inequalities under the stated conversion convention.
Minimum clarification needed: specify exactly which ordering cases are enumerated and make the case count and ordering-constraint count consistent with that definition. This is an expositional counting issue; it does not undermine finite computability, polynomial witness length, or polynomial-time construction for fixed $m$.
Given a certificate, evaluating one supplied report’s lottery is correctly polynomial in the society and query encoding lengths. The distinction from explicitly listing every possible report is appropriate.
The event rule respects residual hospital and regional capacities. Every non-endpoint event exhausts a previously unexhausted resource, while each supported tier contributes one endpoint. Thus the stated polynomial stage bound is valid.
Processing each type at rate $\mu_t$ for one unit of local time gives its required total mass, including outside-option consumption. Menus enforce eligibility and individual rationality.
For non-wastefulness, an outside-region witness requires resources that remain open throughout the source tier. Within a region, equal weights and a common doctor tier make the required strict auxiliary comparison false.
For fairness, strict regional priority places the source tier before the occupant tier. Positive later-tier occupancy shows that the relevant region—and, in the same-hospital case, the relevant hospital—remained available during the earlier tier. Target-hospital slack supplies the remaining availability condition in the different-hospital case. These observations justify the contradictions asserted.
The report-lottery construction uses the same aggregate timeline for every preference report with fixed attributes. The treatment of unsupported tiers is coherent because such tiers consume no aggregate mass.
The exact-arithmetic bound is valid. Positive rates have numerator at most $D$, and the proposed denominator update is sufficient. Polynomially many events therefore produce polynomial encoding lengths and polynomial total computation time.
The prover establishes existence, exact finite computability, polynomial-size certificates, polynomial-time verification, and polynomial-time construction in the two stated restricted regimes.
It does not establish either polynomial-time construction or hardness on the unrestricted domain. Exponential enumeration and polynomial-size witnesses imply neither alternative. The prover explicitly recognizes this limitation, so there is no false claim of a complete complexity classification.
Major issue relative to the assignment: the unrestricted complexity part of USER_TASK remains unanswered.
Minimum additional result needed: a justified unrestricted polynomial-time construction, or an appropriate hardness theorem for the unrestricted computation problem. This requires additional mathematics, rather than clarification of the existing write-up.
⟨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.