Answer: —
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateLet ≻H be a many–to–one market. Then, any stable matching is obtained in some equilibrium that consists of dropping strategies. In particular, Σ(PH) ⊆O(≻H) and O(≻H) ̸= ∅.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses μ_t over student types, per-capita hospital capacities κ_h, additive hospital values u_h(t), and a stable flow x with ∑_h x_{th} ≤ μ_t and ∑_t x_{th} ≤ κ_h, does there exist a profile of hospital reports, each an ordered list of types, such that mass-based student-proposing deferred acceptance returns x and no hospital can improve its value by changing its report? Each type records a student’s ranking of hospitals and the priority ranks assigned by every hospital; mass-based acceptance may split a type at a capacity boundary.
Let \(H\) be a nonempty set of \(m\) hospitals. A society is given by its support: the list \(T\) 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 strict ranking of \(H\cup\{0\}\), where \(0\) means unmatched, and a true priority rank at every hospital. Hospital capacities \(\kappa_h>0\) are fixed binary rationals. Values \(u_h(t)\) are binary rationals, nonzero and pairwise distinct for each hospital; true hospital priorities rank types by decreasing value, with \(0\) valued at zero. Thus a type is hospital-acceptable exactly when \(u_h(t)>0\).
A feasible flow satisfies \(x_{th}\geq0\), \(\sum_hx_{th}\leq\mu_t\), and \(\sum_tx_{th}\leq\kappa_h\); put \(x_{t0}=\mu_t-\sum_hx_{th}\). Stability means positive assignments are mutually acceptable, and no positive mass of a type assigned to a less-preferred hospital or unmatched wants an acceptable hospital that has spare capacity or holds positive mass of a strictly lower-priority type.
Students report truthfully. Each hospital may report any strict ordered list of a subset of \(T\), including the empty list; omitted types are rejected. Reports treat all mass of a type identically and may include truly unacceptable types.
Mass-based student-proposing deferred acceptance proceeds in simultaneous rounds: initially all mass proposes to its favorite student-acceptable hospital; subsequently rejected mass proposes to its next such hospital. Each hospital retains, from held mass and new proposals, listed types in reported order up to capacity, splitting the boundary type and rejecting the rest. Mass exhausting its list stays unmatched. Denote the resulting flow by \(\operatorname{DA}(Q)\).
Hospital \(h\) evaluates a flow \(y\) by \(U_h(y)=\sum_tu_h(t)y_{th}\). A report profile \(Q\) is a pure Nash equilibrium when \(U_h(\operatorname{DA}(Q))\geq U_h(\operatorname{DA}(Q'_h,Q_{-h}))\) for every hospital and every alternative report.
Given a binary-rational flow \(x\), promised stable under the true preferences, is deciding whether some pure Nash equilibrium \(Q\) satisfies \(\operatorname{DA}(Q)=x\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? Measure running times in \(m\), \(\tau\), and the total input bit length \(L\).
In finite many-to-one markets with responsive hospital preferences, every stable matching is induced by a pure Nash equilibrium consisting of reports obtained by deleting students from true acceptable lists while preserving their order. [Jaramillo–Kayı–Klijn](https://bw.bse.eu/wp-content/uploads/2015/09/686-file.pdf)
Continuum stable matchings have been characterized through supply and demand equations in a different model; this does not settle the report-equilibrium decision problem above, for which no exact result was identified. [Azevedo–Leshno](https://eduardomazevedo.github.io/papers/Azevedo-Leshno-Supply-and-Demand-Matching.pdf)
The general complexity classification remains unresolved. I prove two new results:
The proofs allow arbitrary unilateral reports, including reports that list truly unacceptable types.
For a report profile $Q$, call a flow *reported-stable* if stability is evaluated using the listed types and their reported priorities, while retaining the students’ true preferences.
For two flows $z,w$, say that $z$ *student-dominates* $w$ if, for every type and every preference threshold, the mass assigned at or above that threshold is at least as large under $z$.
For every report profile $Q$, the flow $y=\operatorname{DA}(Q)$ is reported-stable and student-dominates every rational reported-stable flow.
Proof. Choose a positive integer $D$ clearing the denominators of the masses and capacities. Replace type $t$ by $D\mu_t$ individual students, numbered consecutively. Hospital $h$ has capacity $D\kappa_h$ and ranks students by their reported type order, breaking ties within each type by increasing individual number.
This is a finite many-to-one market with strict preferences and responsive hospital choice. Its simultaneous student-proposing DA, aggregated by type and divided by $D$, reproduces the stated mass-based algorithm: each hospital retains successive type blocks up to capacity, splitting the boundary block.
We use the standard finite DA theorem: student-proposing DA is stable and gives every student a weakly preferred assignment relative to every stable matching. The finite model and this student-optimality property are described in [Jaramillo–Kayı–Klijn](https://bw.bse.eu/wp-content/uploads/2015/09/686-file.pdf). The expansion satisfies its hypotheses: finite populations, integer capacities, strict student preferences, and strict responsive hospital priorities.
Aggregation preserves stability. Indeed, a mass-level block involving a vacancy or a strictly lower-priority type would supply an individual blocking pair in the expanded market.
Now let $z$ be a rational reported-stable flow, and enlarge $D$ to clear its denominators too. Within each type, assign consecutive individuals to destinations in decreasing student-preference order, putting unmatched individuals last.
This individual matching is stable. A blocking individual–hospital pair involving a vacancy or a different lower-priority type would contradict reported stability of $z$. A replacement involving the same type cannot block: every individual assigned to the proposed hospital has a smaller number than any same-type individual assigned somewhere worse.
Finite student optimality therefore applies to this representation of $z$. Summing its individual comparisons within each type gives the asserted cumulative mass inequalities. $\square$
For a flow $y$, let $G(y)$ be the undirected bipartite graph on $T$ and $H\cup\{0\}$, with edge $th$ exactly when $y_{th}>0$. If $y=\operatorname{DA}(Q)$, then $G(y)$ is a forest.
Proof. Suppose a simple cycle exists. Each cycle type chooses its preferred one of its two incident cycle destinations.
No hospital can be chosen by both adjacent cycle types. Both would have positive mass at a worse destination; the higher-ranked one would block with the hospital’s positive assignment of the lower-ranked one. The destination $0$ cannot be chosen, because positive hospital assignments are student-acceptable.
The cycle has equally many type and destination vertices. Thus it cannot contain $0$, and every cycle hospital is chosen exactly once.
Choose a positive rational $\varepsilon$ smaller than every cycle-edge assignment. Transfer $\varepsilon$ for each cycle type from its worse cycle destination to its better one. Every type total and every hospital load remains unchanged. Every positive edge remains positive, and no new edge appears.
Reported stability depends on positive support, hospital slack, acceptability, and priority comparisons. All are unchanged, so the perturbed flow remains reported-stable. It strictly improves the cumulative allocation of every cycle type at some threshold and worsens none. This contradicts Lemma 1. $\square$
Given $Q$, the exact flow $\operatorname{DA}(Q)$ can be computed in time polynomial in $m,\tau,L$.
The relevant established algorithmic result is the following.
Stable allocation theorem. A bipartite stable allocation instance with strict preference lists, vertex quotas, and edge upper bounds admits a strongly polynomial algorithm computing the allocation that lexicographically maximizes each proposing vertex’s allocation vector among stable allocations. An elementary implementation uses polynomially many additions, subtractions, minima, and comparisons; integer inputs remain integral. This is the job-optimal allocation algorithm of [Dean–Munshi, Sections 2–3](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
Here lexicographic comparison lists destinations from best to worst. I verify the reduction and its correspondence with the specified DA outcome.
Proof. Let $D$ be the product of the denominators of the masses and capacities, and set
$$ a_t=D\mu_t,\qquad b_h=D\kappa_h,\qquad A=\sum_ta_t=D,\qquad B=\sum_hb_h. $$
These are integers with polynomial binary length.
Create a real job for each type, with quota $a_t$, and a real machine for each hospital, with quota $b_h$. Include real edge $th$ exactly when $h$ is student-acceptable to $t$ and $Q_h$ lists $t$. Its upper bound is $\min(a_t,b_h)$. Use the student and reported hospital orders on these edges.
To accommodate unmatched mass and unused capacity, add a dummy job $d$ of quota $B$ and a dummy machine $z$ of quota $A$. Add edges:
Every real job ranks $z$ last; every real machine ranks $d$ last. The dummy job ranks all real machines above $z$, and the dummy machine ranks all real jobs above $d$, using arbitrary strict orders otherwise.
Every feasible scaled original flow $w$ has a unique extension filling all quotas:
$$ w_{tz}=a_t-\sum_hw_{th},\qquad w_{dh}=b_h-\sum_tw_{th},\qquad w_{dz}=\sum_{t,h}w_{th}. $$
The last quantity is at most both $A$ and $B$, so all edge bounds are respected.
This extension is stable exactly when the original flow is reported-stable. Dummy edges cannot block: on each such edge, at least one endpoint ranks the other last. On a real edge, a worse allocation at the job means a worse hospital or unmatched mass, while a worse allocation at the machine means a lower-ranked real type or spare capacity.
The real edge upper bound causes no discrepancy. An original blocking pair has positive worse mass of the type and either spare capacity or positive lower-priority mass at the hospital. Consequently its current edge allocation is strictly below both $a_t$ and $b_h$.
Apply the stable allocation theorem and restrict its output to real edges, obtaining $v$. Integer arithmetic makes $v$ integral.
Let $y=D\operatorname{DA}(Q)$. DA uses only additions, subtractions, and minima, so $y$ is integral. It is reported-stable by Lemma 1 and therefore extends to a stable allocation in the constructed instance.
Job optimality says that each real type’s vector under $v$ is lexicographically at least its vector under $y$. Conversely, Lemma 1 says that $y/D$ student-dominates $v/D$, which implies the reverse lexicographic comparison. Hence every real type’s vector is equal:
$$ v=D\operatorname{DA}(Q). $$
The constructed graph has $\tau+m+2$ vertices and at most $m\tau+m+\tau+1$ edges. All scaled quotas and bounds have polynomial binary length. The elementary stable allocation algorithm performs polynomially many arithmetic operations on integer flow and residual quantities bounded by the total quotas. Thus its bit running time is polynomial. Dividing the real allocation by $D$ gives the exact DA outcome. $\square$
The general equilibrium-attainability problem belongs to $\Sigma_2^{\mathrm P}$.
Proof. A report profile has encoding length
$$ O\!\left(m\tau\log(\tau+1)\right). $$
A hospital index and one alternative report also have polynomial encoding length. By Proposition 3, the predicate
$$ \operatorname{DA}(Q)=x \quad\text{and}\quad U_h\!\left(\operatorname{DA}(Q'_h,Q_{-h})\right)\le U_h(x) $$
is decidable in polynomial time. The utility comparisons are exact binary-rational comparisons.
The requested condition is therefore an existential choice of $Q$ followed by a universal choice of $(h,Q'_h)$, with a polynomial-time predicate. Invalid universal encodings can be accepted automatically, while invalid existential encodings are rejected. This is the defining form of $\Sigma_2^{\mathrm P}$. $\square$
There is also a deterministic bound without exponential dependence on the numerical denominator. One hospital has
$$ R_\tau=\sum_{k=0}^{\tau}\frac{\tau!}{(\tau-k)!} $$
possible reports. Enumerating profiles and unilateral deviations, using Proposition 3, gives running time
$$ R_\tau^m(1+mR_\tau)\operatorname{poly}(m,\tau,L) = 2^{O((m+1)\tau\log(\tau+1))} \operatorname{poly}(m,\tau,L). $$
Neither bound establishes membership in $\mathrm P$ or $\mathrm{NP}$.
Let $G_H(x)$ be the positive-assignment graph with the unmatched destination omitted. Call a type *shared* if it has positive assignments at at least two hospitals.
Suppose $x$ is true-stable and each connected component of $G_H(x)$ contains at most one shared type. Then $x$ is induced by a pure Nash equilibrium. Such reports can be constructed in polynomial time.
We first record the consequence of stability that controls the construction.
Call an incumbent type $t$ a *boundary type at $h$* if $x_{th}>0$ and some positive mass of $t$ is assigned to a destination worse than $h$.
At each hospital:
Indeed, a boundary type wants more of $h$. Stability excludes spare capacity and any lower-priority incumbent. Distinct values give the strict comparison. Two boundary types would require each to have lower value than the other.
Write
$$ F_h=\{t:x_{th}=\mu_t\},\qquad M_h=\sum_{t\in F_h}\mu_t. $$
Consider a component containing a shared type $c$. Every hospital in that component must be adjacent to $c$: without another shared type, there is no other way to connect distinct hospitals. Order these hospitals by $c$’s preference:
$$ h_1\succ_c h_2\succ_c\cdots\succ_c h_k, \qquad p_i=x_{ch_i}>0. $$
Every other positively assigned type in the component is assigned to just one hospital. It is either in $F_h$ or has positive unmatched mass.
For every $i<k$, type $c$ is a boundary type at $h_i$. Therefore
$$ \kappa_{h_i}=M_{h_i}+p_i, $$
and no other partially assigned type can occur there.
At $h_k$, if $x_{c0}>0$, the same statements hold. If $x_{c0}=0$, there may instead be one additional type $r$ assigned partly to $h_k$ and partly to $0$. This $r$ is the boundary type.
At every hospital, report:
Omit all other types. Components without a shared type consist of one hospital and its singly assigned types, so the same construction applies.
The total supply of $F_h$ is $M_h\le\kappa_h$, and these types precede all other listed types. Hospital $h$ therefore never rejects them. Each is listed only at its assigned hospital, so all its mass eventually reaches that hospital and is accepted.
A shared type $c$ consequently passes through its supported hospitals in the order $h_1,\ldots,h_k$. Omitted hospitals can delay proposals but retain no mass.
For $i<k$, after the full types are assigned, the capacity available for $c$ is exactly $p_i$. Inductively, at least $p_i$ of $c$ reaches $h_i$, because
$$ \mu_c=\sum_{j=1}^kp_j+x_{c0}. $$
Thus $h_i$ retains exactly $p_i$.
If $x_{c0}>0$, the last hospital also has residual capacity exactly $p_k$. If $x_{c0}=0$, exactly $p_k$ reaches the last hospital and is accepted before any additional unmatched-boundary type.
An additional boundary type $r$ is listed only at its assigned hospital. That hospital is full in $x$, and its residual capacity after the preceding types equals $x_{rh}$. It therefore retains exactly that amount. Types assigned entirely unmatched are omitted everywhere.
Hence $\operatorname{DA}(Q)=x$.
Fix a hospital $h$, an arbitrary report $Q'_h$, and let
$$ y=\operatorname{DA}(Q'_h,Q_{-h}). $$
At every fixed hospital $g$, its full types $F_g$ remain protected: their entire supply fits its capacity and precedes all other listed types.
For later use, suppose a shared type $c$ sends total proposal mass $P$ to a fixed supported hospital $g$. Let $M'_g\le M_g$ be the total full-type mass actually reaching $g$. Since $c$ precedes any additional boundary type, its final retained mass is
$$ \min(P,\kappa_g-M'_g)\ge \min(P,x_{cg}). $$
Thus the total mass of $c$ rejected there is at most
$$ \max(P-x_{cg},0). $$
This holds for the entire DA run: the hospital retains the highest-ranked mass among its cumulative proposals, and no full type can be rejected.
Bound A: every positive-value newcomer wants $h$ under $x$.
Suppose $x_{th}=0$, $y_{th}>0$, and $u_h(t)>0$.
If $x_{t0}>0$, the unmatched mass witnesses that $t$ wants $h$, because a positive DA assignment makes $h$ student-acceptable.
If $t$ is fully assigned to one other hospital $g$, protection at $g$ prevents it from reaching a less-preferred $h$. Hence it must prefer $h$ to $g$.
The remaining case is a shared type $c$ with $x_{c0}=0$. Suppose it does not want $h$ under $x$. Then every supported hospital $h_i$ is preferred to $h$, and all these hospitals are fixed. Applying the rejection bound successively shows that proposal mass reaching $h_i$ is at most
$$ \mu_c-\sum_{j<i}p_j. $$
At $h_k$, this is at most $p_k$, and all of it is accepted. No mass reaches $h$, a contradiction.
Bound B: every incumbent that is not a boundary type satisfies $y_{th}\le x_{th}$.
For a full type, this follows from $x_{th}=\mu_t$.
The only other possibility is a shared type $c$. If it is not a boundary type at $h$, then $x_{c0}=0$ and $h$ is its least-preferred supported hospital. All preceding supported hospitals are fixed. The same successive rejection bound shows that at most $x_{ch}$ reaches $h$, proving the assertion.
A singly assigned type with positive unmatched mass is always a boundary type, so there are no further cases.
If $h$ has slack in $x$, it has no boundary type. Bound A and true stability exclude every positive-value newcomer. Bound B prevents any incumbent’s allocation from increasing. Since incumbents have positive values and all remaining newcomers have negative values,
$$ U_h(y)\le U_h(x). $$
Now suppose $h$ is full.
If it has a boundary type $b$, put $v=u_h(b)>0$ and let $I$ be its other incumbents. Otherwise, let $I$ be all incumbents and put
$$ v=\min_{t\in I}u_h(t)>0. $$
The latter minimum exists because $\kappa_h>0$ and $h$ is full.
In either case, every $t\in I$ has $u_h(t)\ge v$ and satisfies $y_{th}\le x_{th}$ by Bound B. Every positive-value newcomer has value strictly below every incumbent: by Bound A it wants $h$, and otherwise it would block $x$. Negative-value newcomers also have value below $v$. A boundary incumbent, when present, has value exactly $v$.
Capacity feasibility therefore gives
$$ U_h(y) \le \sum_{t\in I}u_h(t)y_{th} + v\left(\kappa_h-\sum_{t\in I}y_{th}\right). $$
Full occupancy of $x$ gives equality in the corresponding expression:
$$ U_h(x) = \sum_{t\in I}u_h(t)x_{th} + v\left(\kappa_h-\sum_{t\in I}x_{th}\right). $$
Subtracting,
$$ U_h(y)-U_h(x) \le \sum_{t\in I}(u_h(t)-v)(y_{th}-x_{th}) \le 0. $$
The deviation was arbitrary. Thus $Q$ is a pure Nash equilibrium.
The component condition, the relevant type classes, and the reports are computable by graph traversal, rational comparisons, and sorting in polynomial time. $\square$
If $m=2$ and $x$ is promised true-stable, then
$$ x\text{ is induced by a pure Nash equilibrium} \quad\Longleftrightarrow\quad G(x)\text{ is a forest}. $$
Consequently, the two-hospital problem is polynomial-time solvable.
Proof. Necessity follows from Lemma 2.
For sufficiency, if two distinct types were shared between the two hospitals, their four positive hospital-assignment edges would form a cycle. Hence a forest $G(x)$ allows at most one shared type. In particular, every component of $G_H(x)$ satisfies Theorem 5, which constructs a supporting equilibrium. $\square$
This result permits unequal masses, split assignments, unmatched mass, and arbitrary binary-rational capacities.
The sufficient condition does not cover a component with two shared types. Such a component can already fail with three hospitals.
Let $\mu_t=\mu_s=1/2$, with capacities
$$ \kappa_a=\kappa_c=\frac14,\qquad \kappa_b=\frac12. $$
Students rank
$$ t:\ a\succ b\succ c\succ0,\qquad s:\ c\succ b\succ a\succ0. $$
Use true values:
| Hospital | $u_h(t)$ | $u_h(s)$ |
|---|---:|---:|
| $a$ | $1$ | $2$ |
| $b$ | $2$ | $1$ |
| $c$ | $2$ | $1$ |
The target has
$$ x_{ta}=x_{tb}=x_{sb}=x_{sc}=\frac14, $$
with all other assignments zero. Its support is the path $a-t-b-s-c$.
It is true-stable. All hospitals are full, and the only desired improvements are $t$ from $b$ to $a$ and $s$ from $b$ to $c$. Each desired hospital holds only that same type.
Reports $(t)$ at $a$, $(t,s)$ at $b$, and $(s)$ at $c$ induce the target. Nevertheless, no inducing profile is an equilibrium.
Every inducing profile must list $t$ at $a$, both types at $b$, and $s$ at $c$.
Additional entries at the fixed outer hospital do not affect these deviations: the other type is retained entirely at $b$.
Thus forest support alone cannot settle equilibrium attainability once three hospitals and two shared types in one component are allowed.
The general problem now has polynomial-time outcome evaluation and a $\Sigma_2^{\mathrm P}$ upper bound. Theorem 5 supplies a supporting equilibrium for a substantial class of split flows and completely resolves the two-hospital case.
For general inputs with at least three hospitals, I have neither a polynomial-time decision algorithm nor an $\mathrm{NP}$-hardness reduction. In particular, deciding equilibrium attainability for stable forest-supported flows whose hospital-assignment components contain multiple shared types remains open here.
⟨structured verdict parsed — rendered above⟩
Assessment: partial, with sound substantive progress. The output does not resolve the general decision problem in USER_TASK: it supplies neither a polynomial-time decision algorithm nor an $\mathrm{NP}$-hardness proof. It explicitly acknowledges this limitation.
The subsidiary results withstand verification, subject to minor wording corrections below. I found no false central step.
Verified.
The denominator expansion is legitimate for rational masses and capacities. The expanded populations and quotas are integers, and positive capacities become positive integer quotas. Listed types must be treated as acceptable under the reported preferences, irrespective of their true values; this agrees with the report model.
The finite theorem used is stated sufficiently precisely: under strict student preferences and strict responsive hospital preferences, student-proposing DA produces a stable matching weakly preferred by every student to every other stable matching. The cited paper describes this mechanism and its student-optimality property. Its hypotheses hold for the expansion. [Jaramillo–Kayı–Klijn](https://bw.bse.eu/wp-content/uploads/2015/09/686-file.pdf)
The individual tie-breaking rule preserves the aggregate DA process: hospital choices select type blocks in reported order, and rejected individuals of a type follow the same hospital ranking.
The representation of a rational reported-stable flow also handles same-type blocking correctly. Individuals assigned to better destinations receive smaller numbers. Consequently, an individual seeking a better hospital cannot displace a worse-ranked individual of its own type already assigned there. Blocking involving a different type or a vacancy would contradict mass-level reported stability.
Summing individual preference comparisons yields the stated cumulative inequalities. The restriction to rational comparison flows is explicit and sufficient for subsequent applications.
Verified.
Each cycle type has positive mass at its worse incident destination. If two adjacent types choose the same hospital, reported strict priorities identify one as higher-ranked; that type and the hospital form a reported blocking pair.
The unmatched destination cannot be chosen because every positive hospital assignment is student-acceptable. The counting argument therefore excludes a cycle containing $0$ and forces every hospital on any remaining cycle to be chosen exactly once.
The perturbation is valid:
Reported blocking conditions depend on precisely the support, acceptability, strict priorities, and slack preserved by this perturbation. The perturbed flow is rational and strictly student-improving, contradicting Lemma 1.
The conclusion concerns DA outcomes; the proof does not incorrectly claim that every stable flow has forest support.
Verified, with one minor domain correction.
The relevant result is supported by Dean–Munshi: their normalized bipartite model uses strict lists, edge capacities, filled quotas, and dummy vertices. They define job optimality through lexicographic maximization and provide a strongly polynomial algorithm. Their augmentation operations use residual minima and additions or subtractions, preserving integrality. The constructed instance matches that normalized model. [Dean–Munshi, Sections 2–3](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf)
The scaling factor $D$ has polynomial binary length: the bit length of a product is bounded by the sum of the factors’ bit lengths. The scaled quotas and their sums therefore also have polynomial binary length.
The dummy quotas balance total supply and demand. The displayed extension fills every quota, and its dummy-to-dummy allocation is bounded by both $A$ and $B$.
Dummy edges cannot block in these filled-quota extensions because an endpoint ranks the other endpoint last. Real-edge blocking corresponds exactly to original reported blocking. In particular, positive worse mass and either spare capacity or lower-priority incumbent mass imply that the real edge is strictly below both endpoint quotas, so its upper bound does not suppress an original blocking pair.
Minor issue: “Every feasible scaled original flow $w$” is too broad. Feasibility in USER_TASK does not require assignments to be mutually acceptable or listed. Such a flow can assign positive mass to an edge absent from the constructed graph.
Minimum clarification: restrict this sentence to feasible scaled flows supported on the included real edges. Every reported-stable flow subsequently used already satisfies this restriction, so the proof’s conclusion survives.
The computed allocation $v$ is integral and reported-stable after restriction. The scaled DA outcome $y$ is integral and extends to a stable allocation.
Job optimality gives the forward lexicographic comparison. Lemma 1 gives cumulative dominance in the reverse direction, which implies the reverse lexicographic comparison. Equality of the real allocation vectors follows.
The graph size and arithmetic bounds are polynomial in $m,\tau,L$. Scaling uses large integers but does not expand them into individual students computationally. Thus the bit-complexity conclusion is justified.
Verified.
Report profiles and unilateral reports have polynomial-length encodings. Exact DA evaluation and exact rational utility comparison provide the required polynomial-time predicate.
The existential profile and universally quantified hospital–deviation pair express precisely the equilibrium-attainability condition. The stated handling of invalid encodings is appropriate. The conclusion is membership in $\Sigma_2^{\mathrm P}$.
The report count
$$ R_\tau=\sum_{k=0}^{\tau}\frac{\tau!}{(\tau-k)!} $$
correctly counts all ordered subsets, including the empty report. The enumeration bound follows, including when $\tau=1$.
Neither result establishes polynomial-time solvability or hardness.
Minor provenance issue: the phrase “improving the earlier $\mathrm{PSPACE}$ upper bound” refers to an earlier result not supplied or cited in the provided materials.
Minimum clarification: identify that earlier result or omit the historical comparison. This does not affect the verified upper bound.
Verified, with one minor graph-description issue.
A boundary incumbent wants additional mass at its hospital. True stability therefore forces the hospital to be full and excludes every lower-priority incumbent. Pairwise distinct values imply the claimed strict inequalities and exclude two boundary types at one hospital.
Under the component hypothesis, every hospital in a component containing a shared type must be adjacent to that shared type. Any other connection between hospitals would require another shared type.
For each nonfinal supported hospital, the shared type is a boundary type. Hence no other partially assigned incumbent can occur there, and the residual capacity is exactly the shared type’s target assignment.
At the final hospital, the distinction according to whether the shared type has unmatched mass is correct. A possible additional partially unmatched incumbent is unique by the boundary observation.
Minor issue: the assertion that components without a shared type “consist of one hospital and its singly assigned types” overlooks isolated, fully unmatched type vertices if all vertices of $T$ remain in $G_H(x)$.
Minimum clarification: qualify this description as applying to components containing a hospital or positive assignment edge. The later instruction to omit fully unmatched types already handles these vertices.
Full types are protected because their total supply fits the hospital capacity and they precede all other listed types. Their mass eventually reaches their sole listed hospital.
The shared type’s passage through supported hospitals and the residual-capacity calculations yield the specified amounts. At the last hospital without unmatched shared mass, the remaining supply is exactly its target assignment. An additional boundary type is retained in the remaining capacity.
Transient arrival order does not invalidate these arguments: later higher-ranked proposals displace lower-ranked held mass under DA.
The protection argument at fixed hospitals remains valid even if the deviator intercepts some full-type mass.
The rejection bound correctly uses the total proposal mass reaching a fixed supported hospital. Since the shared type precedes the possible additional boundary type, its final retained mass is
$$ \min(P,\kappa_g-M'_g), $$
and the stated lower bound follows from the target residual capacity.
Bound A covers every positive-value newcomer:
Bound B covers every nonboundary incumbent. Full incumbents cannot exceed their total mass; a nonboundary shared incumbent is at its last supported hospital, and preceding fixed hospitals bound the mass reaching it.
These bounds allow arbitrary deviating reports, including truly unacceptable types.
For a slack hospital, stability and Bound A exclude positive-value newcomers, while Bound B bounds every incumbent.
For a full hospital, the chosen $v$ is positive. Every allocation outside $I$ has value at most $v$, and capacity feasibility justifies the displayed upper bound even if the deviating outcome leaves capacity unused. Equality for the target follows from full occupancy.
The final inequality uses both
$$ u_h(t)-v\ge 0 \quad\text{and}\quad y_{th}-x_{th}\le 0. $$
Its sign is correct. The report construction uses polynomial-time graph traversal and sorting.
Verified.
Two distinct shared types would create a four-edge cycle between the two hospitals. Forest support therefore satisfies Theorem 5’s component hypothesis. Necessity follows from Lemma 2.
The polynomial-time characterization applies to promised true-stable flows and includes unmatched edges in the forest test, as stated.
Verified.
The masses sum to one, capacities are positive, and values are nonzero and distinct at each hospital. The target has the required type totals and fills every hospital.
The only desired improvements are those listed. Each desired hospital holds only the requesting type, so neither improvement creates a strict-priority block.
The proposed reports induce the target. Every inducing profile necessarily lists the specified positive-assignment types.
Both deviation calculations are correct. Depending on the order at $b$, the deviating outer hospital receives $\frac14$ of the type valued at $2$, increasing utility from $\frac14$ to $\frac12$. Optional entries at the other outer hospital do not affect these calculations because the relevant other type is retained entirely at $b$.
Thus this example establishes that forest support alone is insufficient for equilibrium attainability with three hospitals.
The output establishes meaningful results, but the general problem requested in USER_TASK remains unresolved. This is a major incompleteness relative to the assignment, not a concealed error or an overclaim: the prover expressly reports partial status.
The minimum feedback is:
⟨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.