Pith. sign in

REVIEW 4 major objections 5 minor 13 references

Stability Notions for Hospital Residents with Sizes

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Every HRS instance has an occupancy-stable matching.

desk verdict The occupancy-stable existence theorem is correct and genuinely new; the paper deserves a serious referee, though it needs a round of presentation fixes before I would cite it. read the letter →

arxiv 2506.03638 v1 pith:D4LBNJHM submitted 2025-06-04 cs.DS

Haricharan Balasundaram , J B Krishnashree , Girija Limaye , Meghana Nasre This is my paper
classification cs.DS MSC 91B6868W2568Q17
keywords hospitalresidentsproblemagentsizesoccupancy-stablematchingstablegeneralizedmasterlistapproximationalgorithmNP-hardness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

In the hospital-residents problem with sizes (HRS), agents occupy multiple positions and the classical notion of stability may not exist. The paper proves that an alternative notion, occupancy-stable matching, always exists: every instance has at least one matching in which no agent-hospital pair can be added without lowering the hospital's occupancy. It gives a linear-time algorithm to compute one, and shows that finding a maximum-size occupancy-stable matching is NP-hard while a linear-time 3-approximation exists. For the classical stability notion, the paper shows that a generalized master-list restriction guarantees a stable matching, also computable in linear time, and gives an alternate NP-hardness proof for the decision problem.

What carries the argument

The carrying object is Algorithm 1, which partitions agents by size and processes the size classes in decreasing order. For each class, it constructs the subgraph induced by that class and all hospitals, computes a stable matching in that subgraph with current residual capacities via the Gale-Shapley algorithm, and unions the results. The monotonicity of hospital occupancy across iterations (Proposition 3) is what makes the union occupancy-stable: any later agent too large to fit would lower occupancy by replacing earlier agents, and any smaller agent that could fit was already rejected by a full hospital during its own iteration.

What would settle it

Exhaustively search all small HRS instances to find one that admits no occupancy-stable matching, or run Algorithm 1 and test whether its output has an occupancy-blocking pair; either would refute Theorem 3.

Watch

Extended reading notes

Core claim

The central discovery is that every HRS instance admits an occupancy-stable matching, and such a matching can be computed in O(m) time by running the Gale-Shapley algorithm on each group of agents of the same size in decreasing order of size, using residual hospital capacities. The resulting union of matchings is occupancy-stable because a blocking pair would have to involve an agent whose size class was processed after the hospital filled, and the size condition in the definition of an occupancy-blocking pair prevents replacing earlier matched larger agents. The paper further shows that maximizing the total size of an occupancy-stable matching is NP-hard even for very small sizes and lists, and that a 3-approximation can be obtained in linear time. Alongside this, it shows that if hospital preferences follow a generalized master list on a partition of agents by size, a stable matching in the classical sense always exists and can be computed in O(m) time.

Load-bearing premise

The existence theorem for occupancy-stable matchings assumes that a stable matching can always be computed in each single-size sub-instance even when the residual hospital capacity is not a multiple of that size, a reduction the paper does not explicitly prove.

Editorial extensions

If this is right

  • Every HRS instance, including those arising from couples and group applications, admits an occupancy-stable matching, so a stable-with-respect-to-fullness assignment can always be offered.
  • The linear-time algorithm gives a practical method to compute such a matching in applications like centralized admissions.
  • Finding a maximum-size occupancy-stable matching is NP-hard, so any efficient algorithm can only approximate it.
  • A 3-approximation is computable in linear time, and the paper's example shows that no better factor is attainable for this particular algorithm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the algorithm processes sizes in decreasing order, it implicitly prefers filling hospitals with larger agents; swapping the order would yield an occupancy-stable matching that favors smaller agents, and both are computable in linear time.
  • The proof that a stable matching exists in each single-size sub-instance with non-multiple residual capacities is left implicit; making it explicit via the floor-capacity reduction would close the only gap in the existence argument.
  • The generalized master-list condition is sufficient but likely not necessary for classical stability to exist; characterizing the boundary could connect to other tractable restrictions.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies the Hospital Residents problem with sizes (HRS), in which each agent has an integral size and consumes that many positions at a hospital. It analyzes occupancy-stable matchings, a relaxation in which an agent-hospital pair blocks a matching only if the hospital's occupancy does not decrease when lower-ranked agents are replaced. The main results are: (i) every HRS instance admits an occupancy-stable matching computable in O(m) time (Theorem 3); (ii) computing a maximum-size occupancy-stable matching is NP-hard even when all sizes and capacities are at most 2 and preference lists have length at most 4 (Theorem 4); (iii) a linear-time 3-approximation for the maximum-size problem (Theorem 5); (iv) a stable matching exists and is computable in O(m) time under a generalized master-list restriction on hospital preferences (Theorem 1); and (v) an alternative NP-hardness proof for the existence of a stable matching when every non-unit-sized agent has degree 1 (Theorem 2). The paper also positions this work relative to the original definition of occupancy stability in McDermid and Manlove [7].

Significance. If the results are correct, the paper fills a genuine gap: occupancy stability was defined in [7] but has apparently not been studied algorithmically. The guaranteed-existence result for occupancy-stable matchings contrasts sharply with the NP-hardness of classical stability in HRS, and the linear-time construction is elegant. The hardness reductions are from (3,3)-COM-SMTI, an independent NP-hard problem, and the approximation algorithm is parameter-free and does not rely on any fitted or data-dependent quantities. The generalized master-list restriction is a natural and practical tractable case. The main ideas of the proofs are sound, but the manuscript contains several errors in central proof objects—most notably an infeasible definition of T_b^j in Section 3 and an unstated reduction used inside Algorithm 1—so the paper needs a careful revision before the claims can be fully trusted as written.

major comments (4)
  1. [Section 2, Algorithm 1 and Lemma 2] The algorithm instructs the reader to compute a stable matching M_k in the sub-instance G_k, where every agent has the same size s_k and the residual capacities q_k(h) need not be multiples of s_k. The paper never states or proves that such a sub-instance reduces to classical HR with capacities floor(q_k(h)/s_k). This reduction is valid: with uniform agent size s, the HRS blocking condition in Definition 1 is equivalent to the HR blocking condition after replacing each capacity by floor(q(h)/s). However, the reduction is load-bearing for Theorem 3, because without it Gale-Shapley is not directly applicable to G_k and the crucial inequality O_{M(t_k)}(h)+s(a)>q(h) in Lemma 2 has no explicit justification. Please add this reduction as a separate lemma and use it in the proof of Lemma 2.
  2. [Section 3, definition of T_b^j] As printed, T_b^j = {(a1_j,h1_j), (a2_j,hb), (a3_j,h1_j), (a4_j,h1_j), (a1_j,alpha,h1_j,alpha), (a2_j,alpha,h2_j,alpha)} is infeasible: in the gadget of Fig. 4, h1_j has capacity 2 and a1_j has size 2, so a3_j and a4_j cannot also both be assigned to h1_j together with a1_j. From the proof of Lemma 5 and the mirror-image structure of T_a^j, the intended set must assign a3_j and a4_j to h2_j instead. Because Lemma 7 constructs M' using T_b^j and Lemma 8 reads the corresponding edges back from M', this typo is load-bearing for the correctness proof of Theorem 4 and must be corrected.
  3. [Section 3, Lemma 4] The proof of Lemma 4 says 'contradicting the assumption that M is A-perfect' in a lemma that is stated for arbitrary occupancy-stable matchings and contains no A-perfect assumption. If the lemma is intended only for A-perfect matchings, the statement should be restricted accordingly (which is how it is used in Lemma 5); otherwise the proof must be rewritten to handle the unmatched case directly. As written, the proof does not establish the stated statement for all occupancy-stable matchings.
  4. [Section 2.2, Lemma 3] The sentence 'at the end of the iteration that computed M_{s(a)}, every c \in M(h) was such that s(c) \ge s(a)' is false if M(h) denotes the final matching, because later iterations add smaller agents to h. The intended claim concerns only agents matched in earlier iterations, i.e., M(t_k)(h). Please correct the notation to M(t_k)(h) and state explicitly that if h had no previously matched agent of size at least s(a), then the inequality q(h) < s(a)+O_{M(t_k)}(h) would contradict the possibility of matching a to h at all. This is a local but necessary clarification for the approximation proof.
minor comments (5)
  1. [Section 2, Algorithm 1, line 4] The pseudo-code writes 'q_k(p) \leftarrow q(h) - O_{M(t_{k-1})}(h)'; the variable should be q_k(h), not q_k(p).
  2. [Remark after Lemma 3] The worked example for Fig. 3 is incorrect as stated: Algorithm 1 should compute M_1 = {(a1,h1)}, not {(a3,h1)}, because the first partition set is At1 = {a1} and a1's stable match in that sub-instance is h1. Additionally, the text first says 'we cannot obtain a factor of 2 using our algorithm' and then immediately says 'However, this does not hold'; this is self-contradictory and should be rewritten.
  3. [Section 4, Lemma 9] The proof says the subgraph induced by {qk_j,1, qk_j,2, qk_j,3, pk_j,2, pk_j,3} is 'exactly the instance in Fig 1 except the sizes being 3 instead of 2'. This is terse; please spell out the correspondence between qk_j,1/qk_j,2/qk_j,3 and a1/a2/a3 of Fig. 1 and explain why the same no-stable-matching argument applies despite the changed capacity of pk_j,3.
  4. [Section 3, Lemma 8] The sentence 'By Lemma 6, exactly one of {a1,a2} is matched to its top choice and the other to its second choice' should cite Lemma 5 together with Lemma 6, since Lemma 6 alone only rules out last-choice matches.
  5. [Throughout] There are several small typographical issues, including 'where whereas' in the caption of Fig. 1 and the ambiguous use of M(h) in Lemma 3; a careful proofreading pass would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation chain rests on external Gale-Shapley existence and independent NP-hard SMTI reductions, with no self-citation or fitted-input dependence.

full rationale

The paper's main claims are derived from external, independently grounded results. Theorem 3 and Lemma 2 use Algorithm 1, whose sub-instance G_k contains only agents of one size s; the paper invokes the classical Gale-Shapley algorithm [4] to obtain a stable matching there. Although the paper does not explicitly state the scaling reduction, such a uniform-size HRS sub-instance with residual capacities q_k(h) is equivalent to classical HR with capacities floor(q_k(h)/s), so the appeal to [4] is valid and does not presuppose the theorem being proved. Theorem 1 is proved directly from the generalized-master-list ordering. The hardness results, Theorems 2 and 4, reduce from the independent (3,3)-COM-SMTI problem proved NP-hard in [7], which is not the present authors' own work. The 3-approximation argument in Lemma 3 is a standalone charging proof, not a fitted parameter or renamed output. The paper's genuine weaknesses are an implicit, unstated reduction at Algorithm 1 line 6 and presentation defects such as the contradictory remark around Fig 3, but these are omitted justifications and typos, not circular reasoning. No self-definitional, fitted-input, self-citation, or ansatz-smuggling circularity is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on standard external results (Gale-Shapley, NP-hardness of (3,3)-COM-SMTI) and one implicit reduction of equal-size HRS instances to classical HR that the paper does not explicitly prove. No free parameters or invented entities are introduced.

assumptions (4)
  • domain assumption Every agent prefers any acceptable hospital to remaining unmatched (⊥ is last-ranked).
    Stated in Section 1.1 and used in all blocking-pair arguments, e.g., Definition 1 and Lemma 2.
  • standard math Gale-Shapley computes a stable matching in every classical HR instance.
    Invoked in Algorithm 1 for each equal-size sub-instance G_k; from [4].
  • standard math (3,3)-COM-SMTI is NP-hard.
    Used as the source problem for the reductions in Theorems 2 and 4; cited from [7].
  • ad hoc to paper An HRS instance in which all agents have the same size s reduces to classical HR with capacities floor(q(h)/s).
    Implicitly assumed when running Gale-Shapley on G_k; not stated or proved in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Stability Notions for Hospital Residents with Sizes." pith.science (2026). https://pith.science/paper/D4LBNJHM

@misc{pith2026250603638,
  author       = {Pith},
  title        = {Pith review of: Stability Notions for Hospital Residents with Sizes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D4LBNJHM}},
  note         = {Machine review of arXiv:2506.03638}
}
abstract

The Hospital Residents problem with sizes (HRS) is a generalization of the well-studied hospital residents (HR) problem. In the HRS problem, an agent $a$ has a size $s(a)$ and the agent occupies $s(a)$ many positions of the hospital $h$ when assigned to $h$. The notion of stability in this setting is suitably modified, and it is known that deciding whether an HRS instance admits a stable matching is NP-hard under severe restrictions. In this work, we explore a variation of stability, which we term occupancy-based stability. This notion was defined by McDermid and Manlove in their work, however, to the best of our knowledge, this notion remains unexplored. We show that every HRS instance admits an occupancy-stable matching. We further show that computing a maximum-size occupancy-stable matching is NP-hard. We complement our hardness result by providing a linear-time 3-approximation algorithm for the max-size occupancy-stable matching problem. Given that the classical notion of stability adapted for HRS is not guaranteed to exist in general, we show a practical restriction under which a stable matching is guaranteed to exist. We present an efficient algorithm to output a stable matching in the restricted HRS instances. We also provide an alternate NP-hardness proof for the decision version of the stable matching problem for HRS which imposes a severe restriction on the number of neighbours of non-unit sized agents.

Figures

Figures reproduced from arXiv: 2506.03638 by the authors.

Figure 1
Figure 1. HRS instance that does not admit a stable matching. The number preceding the agent shows the size of the agent where whereas the number preceding the hospital denotes the hospital capacity. For example, s(a3) = 2 and q(h2) = 2. McDermid and Manlove [7] showed that the problem of determining whether an HRS instance admits a stable matching is NP-hard. In light of this, we consider restricted settings of the instance … view at source ↗
Figure 2
Figure 2. Illustration of generalized master lists. Assume that s(a1) = s(a2) ̸= s(a3) and s(a4) = s(a5) ̸= s(a3). Let A = {At1 , At2 , At3 } where At1 = {a1, a2}, At2 = {a3}, At3 = {a4, a5}. It is easy to see that the preferences of hospitals follow the generalized master list ordering on agents because there exists an ordering ⟨At1 , At2 , At3 ⟩ on the sets in the partition such that every hospital h prefers all agents in A… view at source ↗
Figure 3
Figure 3. Example HRS instance whose maximum size occupancy-stable matching is larger than twice the occupancy-stable matching computed by Algorithm 1. For the instance in [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Agents and hospitals corresponding to a man in the SMTI instance in the gadget corresponding to mj are shown in [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Agents and hospitals corresponding to a man in the SMTI instance 3 instead of 2 and thus doesn’t admit a stable matching. The second statement of the lemma follows from the fact that if a k j is unmatched in N then (a k j , pk j,1 ) blocks N. ⊓⊔ Using same arguments as…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

13 extracted references · 9 canonical work pages

  1. [7]

    Journal of Combinatorial Optimization 19(3), 279--303 (2010)

    McDermid, E.J., Manlove, D.F.: Keeping partners together: algorithmic results for the hospitals/residents problem with couples. Journal of Combinatorial Optimization 19(3), 279--303 (2010). doi:10.1007/s10878-009-9257-2

    work page doi:10.1007/s10878-009-9257-2 2010

  2. [1]

    American Economic Review 93(3), 729--747 (2003)

    Abdulkadiro g lu, A., S\" o nmez, T.: School C hoice: A M echanism D esign A pproach. American Economic Review 93(3), 729--747 (2003). doi:10.1257/000282803322157061

    doi:10.1257/000282803322157061 2003

  3. [2]

    INFORMS Journal on Applied Analytics 49(5), 338--354 (2019)

    Baswana, S., Chakrabarti, P., Chandran, S., Kanoria, Y., Patange, U.: Centralized admissions for engineering colleges in india. INFORMS Journal on Applied Analytics 49(5), 338--354 (2019)

    work page 2019

  4. [3]

    In: Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006

    Dean, B.C., Goemans, M.X., Immorlica, N.: The unsplittable stable marriage problem. In: Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006. pp. 65--75 (2006)

    work page 2006

  5. [4]

    The American Mathematical Monthly 69(1), 9--15 (1962), http://www.jstor.org/stable/2312726

    Gale, D., Shapley, L.S.: College admissions and the stability of marriage. The American Mathematical Monthly 69(1), 9--15 (1962), http://www.jstor.org/stable/2312726

    arXiv 1962

  6. [5]

    Discrete Applied Mathematics 156(15), 2959--2977 (2008)

    Irving, R.W., Manlove, D.F., Scott, S.: The stable marriage problem with master preference lists. Discrete Applied Mathematics 156(15), 2959--2977 (2008). doi:https://doi.org/10.1016/j.dam.2008.01.002

    work page doi:10.1016/j.dam.2008.01.002 2008

  7. [6]

    https://josaa.nic.in/ (2025), accessed: 2025-05-23

    Joint Seat Allocation Authority (JoSAA) : Josaa - joint seat allocation authority official website. https://josaa.nic.in/ (2025), accessed: 2025-05-23

    work page 2025

  8. [8]

    Theoretical Computer Science 844, 171--194 (2020)

    Meeks, K., Rastegari, B.: Solving hard stable matching problems involving groups of similar agents. Theoretical Computer Science 844, 171--194 (2020). doi:https://doi.org/10.1016/j.tcs.2020.08.017

    work page doi:10.1016/j.tcs.2020.08.017 2020

Show all 13 references
  1. [9]

    https://www.nrmp.org (2023), accessed: 2025-05-23

    National Resident Matching Program : National resident matching program website. https://www.nrmp.org (2023), accessed: 2025-05-23

    2023

  2. [10]

    International Journal of Game Theory 36, 519--535 (2008)

    Perach, N., Polak, J., Rothblum, U.G.: A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the technion. International Journal of Game Theory 36, 519--535 (2008)

    2008

  3. [11]

    Econometrica 54(2), 425--427 (1986), http://www.jstor.org/stable/1913160

    Roth, A.E.: On the A llocation of R esidents to R ural H ospitals: A G eneral P roperty of T wo- S ided M atching M arkets. Econometrica 54(2), 425--427 (1986), http://www.jstor.org/stable/1913160

    1986

  4. [12]

    , " * write output.state after.block = add.period write

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION in...

  5. [13]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.