Optimal Capacity Modification for Stable Matchings with Ties

Keshav Ranjan; Meghana Nasre; Prajakta Nimbhorkar

arxiv: 2411.10284 · v4 · submitted 2024-11-15 · 💻 cs.DS · cs.GT

Optimal Capacity Modification for Stable Matchings with Ties

Keshav Ranjan , Meghana Nasre , Prajakta Nimbhorkar This is my paper

Pith reviewed 2026-05-23 17:42 UTC · model grok-4.3

classification 💻 cs.DS cs.GT

keywords hospitals/residents problemstrong stabilityties in preferencescapacity augmentationMINSUMrural hospitals theorempolynomial-time algorithm

0 comments

The pith

The minimum total increase in hospital capacities to ensure a strongly stable matching can be found in polynomial time.

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

The paper examines the Hospitals/Residents problem with ties appearing only in hospital preference lists, where a strongly stable matching is not guaranteed to exist. The central task is to increase hospital quotas under the MINSUM objective of minimizing the sum of all increases, so that the modified instance admits a strongly stable matching. A polynomial-time algorithm is given for this task, together with an analog of the rural hospitals theorem that holds under the same augmentation. The result matters because strong stability is valued for its theoretical guarantees and practical properties, yet the standard model often requires such adjustments to achieve it.

Core claim

In the Hospitals/Residents problem with ties in hospital preferences, the MINSUM problem of minimizing the total capacity increase across hospitals to guarantee a strongly stable matching admits a polynomial-time algorithm. An analog of the rural hospitals theorem also holds in this MINSUM augmentation setting. The cost-weighted version of MINSUM is NP-hard even for zero-one costs, while the version with forced edges remains polynomial-time solvable. In contrast, MINMAX is NP-hard in general, but when ties have length at most ℓ+1 a polynomial-time method exists that increases every quota by at most ℓ and returns the residents-optimal strongly stable matching among all such augmentations.

What carries the argument

The MINSUM capacity-augmentation problem for strong stability in the Hospitals/Residents model with ties.

If this is right

MINSUM admits a polynomial-time algorithm.
An analog of the rural hospitals theorem holds for MINSUM augmentations.
The cost version of MINSUM is NP-hard and inapproximable even with zero-one costs.
With forced edges the MINSUM problem remains polynomial-time solvable.
When ties have length at most ℓ+1, a polynomial-time method increases each quota by at most ℓ and returns the residents-optimal strongly stable matching.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The rural hospitals analog may extend to other quota-modification settings that preserve strong stability.
The bounded-tie algorithm supplies an explicit bound on the per-hospital increase needed when preference lists are short.
The NP-hardness of MINMAX suggests that total-sum minimization is the more tractable route for capacity planning under strong stability.

Load-bearing premise

That raising only hospital quotas, without altering preferences or resident constraints, is always enough to produce a strongly stable matching in the modified instance.

What would settle it

An explicit Hospitals/Residents instance with ties where no finite total quota increase produces a strongly stable matching, or where the claimed polynomial-time procedure fails to return the minimum total increase.

Figures

Figures reproduced from arXiv: 2411.10284 by Keshav Ranjan, Meghana Nasre, Prajakta Nimbhorkar.

**Figure 1.** Figure 1: Gadget Gs used in the hardness reduction for MinSum-Cost problem (i) Preference lists of residents in the gadget Gs. (ii) Preference list of the hospital in the gadget Gs. We also associate a cost c(h) ∈ {0, 1} with each h ∈ H. We show that there exists an augmented instance G′ = (R ∪ H, E) with a total augmentation cost 0 that admits a strongly stable matching if and only if there exists an assignment of … view at source ↗

**Figure 2.** Figure 2: Preferences of global vertices in the hardness reduc [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

**Figure 3.** Figure 3: (i) Preference lists of residents in the gadget [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗

**Figure 5.** Figure 5: The instance G with ℓ = 1 does not admit a strongly stable matching. Executing Algorithm 1 on G outputs an augmented instance G ′ with q ′ (h1) = 2 and q ′ (h2) = 1, and a strongly stable matching M′ = (r1, h2),(r2, h1),(r3, h1). However, M′ is not the resident-optimal strongly stable matching in G ′ . Another augmented instance Gb obtained by setting ˆq(h1) = ˆq(h2) = 2 contains the matching Mc = {(r1, h1… view at source ↗

**Figure 6.** Figure 6: An example instance G for showing the non monotonicity property of strongly stable matching problem. B Background: An Algorithm for Strong Stability In this section, we look at the algorithm for determining the existence of a strongly stable matching for a given instance and computing one if it exists. Irving et al. [22] explored strong stability in the context of the HRT problem and presented an algorithm… view at source ↗

read the original abstract

We consider the Hospitals/Residents (HR) problem in the presence of ties in hospital preferences. Among the three notions of stability, namely weak stability, strong stability, and super-stability, we focus on the notion of strong stability. Strong stability has many desirable properties, both theoretically and in practice; however, its existence is not guaranteed. In this paper, our objective is to optimally increase the quotas of hospitals to ensure that a strongly stable matching exists in the modified instance. We explore two natural optimization criteria: (i) minimizing the total capacity increase across all hospitals (MINSUM) and (ii) minimizing the maximum capacity increase for any hospital (MINMAX). We show that the MINSUM problem admits a polynomial-time algorithm. We also establish an analog of the well-known rural hospitals theorem [Gale & Sotomayor, 1985; Roth, 1986], adapted to the MINSUM augmentation setting. We consider a generalization of the MINSUM problem in which each hospital incurs a cost per unit increase in its quota. We show that the cost version of the MINSUM problem is NP-hard and inapproximable within any multiplicative factor, even if the costs are zero or one. For the MINSUM objective with a set of forced edges, we give a polynomial-time algorithm. In contrast to the above results for the MINSUM problem, we show that the MINMAX problem is NP-hard. When hospital preference lists have ties of length at most $\ell+1$, we give a polynomial-time algorithm that increases each hospital's quota by at most $\ell$, ensuring the resulting instance admits a strongly stable matching. Moreover, among all such augmentations, our algorithm outputs the best strongly stable matching from the residents' perspective.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Poly-time algorithm for MINSUM quota increases to guarantee strong stability, plus hardness for MINMAX and costs.

read the letter

The core result is a polynomial-time algorithm for the MINSUM problem of minimally increasing hospital quotas so that a strongly stable matching exists in the hospitals/residents setting with ties only on the hospital side. They also give an analog of the rural hospitals theorem for this augmentation version. That is the main new piece: framing capacity changes as these two optimization problems and separating the tractable unweighted MINSUM case from the NP-hard cost version and from MINMAX. The bounded-tie-length algorithm for MINMAX that also picks the resident-optimal strongly stable matching is a useful practical add-on. The hardness results for general costs and for MINMAX look clean from the abstract and stress-test notes. The work sits squarely in the algorithmic stable-matching literature and extends prior results on strong stability without introducing obvious circularity or unfalsifiable claims. One minor soft spot is that the rural hospitals analog is stated at a high level; it would be worth checking in review whether the exact statement carries over without extra conditions on the augmentation. The assumption that only hospital quotas change (no resident-side changes) is standard for this model but limits applicability if real markets allow other adjustments. This paper is for researchers already working on stable matchings with ties or capacity-constrained assignment. It is focused and technically grounded enough to merit a serious referee, even if the results are incremental rather than sweeping. I would send it to peer review.

Referee Report

0 major / 3 minor

Summary. The manuscript studies the Hospitals/Residents problem with ties only in hospital preference lists, focusing on strong stability. It introduces two quota-augmentation problems to guarantee existence of a strongly stable matching: MINSUM (minimize total capacity increase) and MINMAX (minimize the maximum increase at any hospital). The central claims are a polynomial-time algorithm for unweighted MINSUM, an analog of the rural hospitals theorem in this augmentation setting, NP-hardness (and inapproximability) for the weighted MINSUM variant and for MINMAX, a polynomial-time algorithm for MINSUM with forced edges, and—for preference lists whose ties have length at most ℓ+1—a polynomial-time algorithm that augments each quota by at most ℓ while returning the resident-optimal strongly stable matching in the augmented instance.

Significance. If the algorithmic claims hold, the work is significant: it supplies the first efficient method for minimally enlarging capacities to restore strong stability, cleanly separates the tractable MINSUM case from the intractable MINMAX and weighted cases, and extends the classical rural hospitals theorem to the augmentation setting. The bounded-tie-length result for MINMAX further delineates the complexity landscape and yields a resident-optimal solution, which is a desirable property in applications.

minor comments (3)

[Abstract] The abstract states that the MINSUM algorithm is polynomial-time but does not indicate its degree; adding a concrete bound (e.g., O(n^3)) would help readers assess practicality.
The statement of the rural-hospitals analog should explicitly list the quantities that remain invariant (e.g., the set of matched residents or the number of residents assigned to each hospital) so that the precise analogy is immediately clear.
In the bounded-tie-length result, the paper should clarify whether the ℓ-increase bound is tight (i.e., whether there exist instances requiring an increase of exactly ℓ at some hospital).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, recognition of the significance of the results, and recommendation of minor revision. No major comments appear in the report, so we have no points to address point-by-point.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents new polynomial-time algorithms for MINSUM quota augmentation to guarantee strong stability, an adapted rural hospitals theorem, and contrasting NP-hardness results for MINMAX and the cost version. These are constructive algorithmic results and complexity classifications. No derivation reduces by construction to fitted parameters, self-definitional loops, or load-bearing self-citations; the central claims rest on independent algorithmic constructions rather than renaming or smuggling prior results.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definition of the Hospitals/Residents problem with ties and the three stability notions; no new free parameters, invented entities, or ad-hoc axioms are introduced beyond domain assumptions of matching theory.

axioms (2)

domain assumption Standard definition of strong stability in the Hospitals/Residents model with ties in hospital preferences
Invoked throughout the abstract as the target property to enforce via capacity changes.
domain assumption Existence of a strongly stable matching after suitable quota increases is always achievable
Implicit premise that the augmentation problems are well-posed.

pith-pipeline@v0.9.0 · 5866 in / 1364 out tokens · 30690 ms · 2026-05-23T17:42:58.521878+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

[1]

American Economic Review 95(2), 364–367 (2005)

Abdulkadiro˘ glu, A., Pathak, P.A., Roth, A.E.: The new yo rk city high school match. American Economic Review 95(2), 364–367 (2005)

work page 2005
[2]

Games Econ

Afacan, M.O., Dur, U.M., der Linden, M.V.: Capacity desig n in school choice. Games Econ. Behav. 146, 277– 291 (2024). https://doi.org/10.1016/J.GEB.2024.05.002 , https://doi.org/10.1016/j.geb.2024.05.002

work page doi:10.1016/j.geb.2024.05.002 2024
[3]

Economic theory 4(3), 417–435 (1994)

Alcalde, J., Barber` a, S.: Top dominance and the possibil ity of strategy-proof stable solutions to matching problems. Economic theory 4(3), 417–435 (1994)

work page 1994
[4]

Opera- tions Research Letters 5(4), 165–169 (1986)

Bartholdi III, J., Trick, M.A.: Stable matching with pref erences derived from a psychological model. Opera- tions Research Letters 5(4), 165–169 (1986)

work page 1986
[5]

INFORMS J

Baswana, S., Chakrabarti, P.P., Chandran, S., Kanoria, Y ., Patange, U.: Centralized ad- missions for engineering colleges in india. INFORMS J. Appl . Anal. 49(5), 338–354 (2019). https://doi.org/10.1287/INTE.2019.1007, https://doi.org/10.1287/inte.2019.1007

work page doi:10.1287/inte.2019.1007 2019
[6]

[BCDNG17] Nicola Basilico, Andrea Celli, Giuseppe De Nitti s, and Nicola Gatti

Bobbio, F., Carvalho, M., Lodi, A., Rios, I., Torrico, A.: Capacity planning in stable matching: An application to school choice. In: Leyton-Brown, K., Hartline, J.D., Sam uelson, L. (eds.) Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, U nited Kingdom, July 9-12, 2023. p. 295. ACM (2023). https://doi.org/10.1145/358...

work page doi:10.1145/3580507.3597771 2023
[7]

CoRR abs/2205.01302 (2022)

Bobbio, F., Carvalho, M., Lodi, A., Torrico, A.: Capacity variation in the many-to-one sta- ble matching. CoRR abs/2205.01302 (2022). https://doi.org/10.48550/ARXIV.2205.01302, https://doi.org/10.48550/arXiv.2205.01302

work page doi:10.48550/arxiv.2205.01302 2022
[8]

In: Agmon, N., An, B., Ricci, A., Yeoh, W

Boehmer, N., Heeger, K.: Adapting stable matchings to for ced and forbidden pairs. In: Agmon, N., An, B., Ricci, A., Yeoh, W. (eds.) Proceedings of the 2023 Intern ational Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, London, United Kingdom, 29 May 2023 - 2 June 2023. pp. 985–993. ACM (2023). https://doi.org/10.5555/3545946.3598738, ...

work page doi:10.5555/3545946.3598738 2023
[9]

Autonomous agents and mu lti-agent systems 34, 1–29 (2020)

Bredereck, R., Chen, J., Finnendahl, U.P., Niedermeier, R.: Stable roommates with narcissistic, single-peaked, and single-crossing preferences. Autonomous agents and mu lti-agent systems 34, 1–29 (2020)

work page 2020
[10]

In: Proceed- ings of the 2023 International Conference on Autonomous Age nts and Multiagent Systems, AAMAS

Chen, J., Cs´ aji, G.: Optimal capacity modiﬁcation for m any-to-one matching problems. In: Proceed- ings of the 2023 International Conference on Autonomous Age nts and Multiagent Systems, AAMAS

work page 2023
[11]

2880–2882

pp. 2880–2882. ACM, London, United Kingdom (2023). ht tps://doi.org/10.5555/3545946.3599110, https://dl.acm.org/doi/10.5555/3545946.3599110

work page doi:10.5555/3545946.3599110 2023
[12]

Cseh, ´A., Heeger, K.: The stable marriage problem with ties and res tricted edges. Discret. Optim. 36, 100571 (2020). https://doi.org/10.1016/J.DISOPT.2020.100571, https://doi.org/10.1016/j.disopt.2020.100571

work page doi:10.1016/j.disopt.2020.100571 2020
[13]

Darmann, A., D¨ ocker, J.: On a simple hard variant of not- all-equal 3-sat. Theor. Comput. Sci. 815, 147–152 (2020). https://doi.org/10.1016/J.TCS.2020.02.010, https://doi.org/10.1016/j.tcs.2020.02.010

work page doi:10.1016/j.tcs.2020.02.010 2020
[14]

Discrete Applied Mathematics 157(7), 1655–1659 (2009)

Denman, R., Foster, S.: Using clausal graphs to determin e the computational complexity of k-bounded positive one-in-three sat. Discrete Applied Mathematics 157(7), 1655–1659 (2009)

work page 2009
[15]

Journal of Artiﬁcial Intel- ligence Research 67, 797–833 (2020)

Fitzsimmons, Z., Lackner, M.: Incomplete preferences i n single-peaked electorates. Journal of Artiﬁcial Intel- ligence Research 67, 797–833 (2020)

work page 2020
[16]

The American Mathematical Monthly 69(1), 9–15 (1962)

Gale, D., Shapley, L.S.: College admissions and the stab ility of marriage. The American Mathematical Monthly 69(1), 9–15 (1962)

work page 1962
[17]

Discrete Applied Mathematics 11(3), 223–232 (1985)

Gale, D., Sotomayor, M.: Some remarks on the stable match ing problem. Discrete Applied Mathematics 11(3), 223–232 (1985)

work page 1985
[18]

Garey, M.R., Johnson, D.S.: Computers and Intractabili ty: A Guide to the Theory of NP- Completeness (Series of Books in the Mathematical Sciences ). W. H. Freeman, ﬁrst edition edn. (1979), http://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455

work page arXiv 1979
[19]

In: Proceedings of the 23rd International Conference o n Autonomous Agents and Multiagent Systems, AAMAS 2024

Gokhale, S., Singla, S., Narang, S., Vaish, R.: Capacity modiﬁcation in the stable matching prob- lem. In: Proceedings of the 23rd International Conference o n Autonomous Agents and Multiagent Systems, AAMAS 2024. pp. 697–705. International Foundatio n for Autonomous Agents and Mul- tiagent Systems / ACM, Auckland, New Zealand (2024). https: //doi.org/10....

work page doi:10.5555/3635637.3662922 2024
[20]

MIT Press, Cambridge, MA, USA (1989)

Gusﬁeld, D., Irving, R.W.: The stable marriage problem: structure and algorithms. MIT Press, Cambridge, MA, USA (1989)

work page 1989
[21]

Discret e Applied Mathematics 48(3), 261–272 (1994)

Irving, R.W.: Stable marriage and indiﬀerence. Discret e Applied Mathematics 48(3), 261–272 (1994)

work page 1994
[22]

In: Halld´ orsson, M.M

Irving, R.W., Manlove, D.F., Scott, S.: The hospitals/r esidents problem with ties. In: Halld´ orsson, M.M. (ed.) Algorithm Theory - SW AT 2000, 7th Scandinavian Worksh op on Algorithm Theory, Bergen, Norway, July 5-7, 2000, Proceedings. Lecture Notes in Computer Scie nce, vol. 1851, pp. 259–271. Springer (2000). https://doi.org/10.1007/3-540-44985-X 24, ...

work page doi:10.1007/3-540-44985-x 2000
[23]

In: Annual Sym- posium on Theoretical Aspects of Computer Science

Irving, R.W., Manlove, D.F., Scott, S.: Strong stabilit y in the hospitals/residents problem. In: Annual Sym- posium on Theoretical Aspects of Computer Science. pp. 439– 450. Springer (2003)

work page 2003
[24]

ACM Tran s

Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.E.: St rongly stable matchings in time O(nm) and extension to the hospitals-residents problem. ACM Tran s. Algorithms 3(2), 15 (2007). https://doi.org/10.1145/1240233.1240238, https://doi.org/10.1145/1240233.1240238

work page doi:10.1145/1240233.1240238 2007
[25]

Kavitha, T., Nasre, M.: Popular matchings with variable item copies. Theor. Comput. Sci. 412(12-14), 1263– 1274 (2011). https://doi.org/10.1016/J.TCS.2010.12.06 7, https://doi.org/10.1016/j.tcs.2010.12.067

work page doi:10.1016/j.tcs.2010.12.06 2011
[26]

Kavitha, T., Nasre, M., Nimbhorkar, P.: Popularity at mi nimum cost. J. Comb. Optim. 27(3), 574–596 (2014). https://doi.org/10.1007/S10878-012-9537-0, https://doi.org/10.1007/s10878-012-9537-0

work page doi:10.1007/s10878-012-9537-0 2014
[27]

In: Hsu, W., Lee, D., Liao, C

Kunysz, A.: An algorithm for the maximum weight strongly stable matching problem. In: Hsu, W., Lee, D., Liao, C. (eds.) 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan. LI PIcs, vol. 123, pp. 42:1–42:13. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik (2018). https: //doi.org/10.4230/...

work page doi:10.4230/lipics.isaac.2018.42 2018
[28]

In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algo rithms

Kunysz, A., Paluch, K., Ghosal, P.: Characterisation of strongly stable matchings. In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algo rithms. pp. 107–119. SIAM (2016)

work page 2016
[29]

Manlove, D.F.: Stable marriage with ties and unacceptab le partners. Tech. rep., Technical Report TR-1999-29, University of Glasgow, Department of Computing . . . (1999)

work page 1999
[30]

Manlove, D.F.: The structure of stable marriage with ind iﬀerence. Discret. Appl. Math. 122(1-3), 167–181 (2002). https://doi.org/10.1016/S0166-2 18X(01)00322-5, https://doi.org/10.1016/S0166-218X(01)00322-5

work page doi:10.1016/s0166-2 2002
[31]

Porschen, S., Schmidt, T., Speckenmeyer, E., Wotzlaw, A .: XSAT and NAE-SAT of linear CNF classes. Discret. Appl. Math. 167, 1–14 (2014). https://doi.org/10.1016/J.DAM.2013.10.0 30, https://doi.org/10.1016/j.dam.2013.10.030

work page doi:10.1016/j.dam.2013.10.0 2014
[32]

Econometric Society Monographs, Cambrid ge University Press (1990), https://books.google.co.in/books?id=JZNGHTZ6qX4C

Roth, A., Sotomayor, M.: Two-Sided Matching: A Study in G ame-Theoretic Model- ing and Analysis. Econometric Society Monographs, Cambrid ge University Press (1990), https://books.google.co.in/books?id=JZNGHTZ6qX4C

work page 1990
[33]

Econometrica: Journal of the Econometric Society pp

Roth, A.E.: On the allocation of residents to rural hospi tals: a general property of two-sided matching markets. Econometrica: Journal of the Econometric Society pp. 425–4 27 (1986)

work page 1986
[34]

In: Proceedings of the tenth annual ACM symposium on Theory of computing

Schaefer, T.J.: The complexity of satisﬁability proble ms. In: Proceedings of the tenth annual ACM symposium on Theory of computing. pp. 216–226 (1978) 30 K. Ranjan et al . A Non Monotonicity Property Here, we show that the HR-HT problem is not monotonic with respect to capacity aug- mentation. Consider the example instance G = ( R ∪ H , E ) shown in Fig....

work page 1978

[1] [1]

American Economic Review 95(2), 364–367 (2005)

Abdulkadiro˘ glu, A., Pathak, P.A., Roth, A.E.: The new yo rk city high school match. American Economic Review 95(2), 364–367 (2005)

work page 2005

[2] [2]

Games Econ

Afacan, M.O., Dur, U.M., der Linden, M.V.: Capacity desig n in school choice. Games Econ. Behav. 146, 277– 291 (2024). https://doi.org/10.1016/J.GEB.2024.05.002 , https://doi.org/10.1016/j.geb.2024.05.002

work page doi:10.1016/j.geb.2024.05.002 2024

[3] [3]

Economic theory 4(3), 417–435 (1994)

Alcalde, J., Barber` a, S.: Top dominance and the possibil ity of strategy-proof stable solutions to matching problems. Economic theory 4(3), 417–435 (1994)

work page 1994

[4] [4]

Opera- tions Research Letters 5(4), 165–169 (1986)

Bartholdi III, J., Trick, M.A.: Stable matching with pref erences derived from a psychological model. Opera- tions Research Letters 5(4), 165–169 (1986)

work page 1986

[5] [5]

INFORMS J

Baswana, S., Chakrabarti, P.P., Chandran, S., Kanoria, Y ., Patange, U.: Centralized ad- missions for engineering colleges in india. INFORMS J. Appl . Anal. 49(5), 338–354 (2019). https://doi.org/10.1287/INTE.2019.1007, https://doi.org/10.1287/inte.2019.1007

work page doi:10.1287/inte.2019.1007 2019

[6] [6]

[BCDNG17] Nicola Basilico, Andrea Celli, Giuseppe De Nitti s, and Nicola Gatti

Bobbio, F., Carvalho, M., Lodi, A., Rios, I., Torrico, A.: Capacity planning in stable matching: An application to school choice. In: Leyton-Brown, K., Hartline, J.D., Sam uelson, L. (eds.) Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, U nited Kingdom, July 9-12, 2023. p. 295. ACM (2023). https://doi.org/10.1145/358...

work page doi:10.1145/3580507.3597771 2023

[7] [7]

CoRR abs/2205.01302 (2022)

Bobbio, F., Carvalho, M., Lodi, A., Torrico, A.: Capacity variation in the many-to-one sta- ble matching. CoRR abs/2205.01302 (2022). https://doi.org/10.48550/ARXIV.2205.01302, https://doi.org/10.48550/arXiv.2205.01302

work page doi:10.48550/arxiv.2205.01302 2022

[8] [8]

In: Agmon, N., An, B., Ricci, A., Yeoh, W

Boehmer, N., Heeger, K.: Adapting stable matchings to for ced and forbidden pairs. In: Agmon, N., An, B., Ricci, A., Yeoh, W. (eds.) Proceedings of the 2023 Intern ational Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, London, United Kingdom, 29 May 2023 - 2 June 2023. pp. 985–993. ACM (2023). https://doi.org/10.5555/3545946.3598738, ...

work page doi:10.5555/3545946.3598738 2023

[9] [9]

Autonomous agents and mu lti-agent systems 34, 1–29 (2020)

Bredereck, R., Chen, J., Finnendahl, U.P., Niedermeier, R.: Stable roommates with narcissistic, single-peaked, and single-crossing preferences. Autonomous agents and mu lti-agent systems 34, 1–29 (2020)

work page 2020

[10] [10]

In: Proceed- ings of the 2023 International Conference on Autonomous Age nts and Multiagent Systems, AAMAS

Chen, J., Cs´ aji, G.: Optimal capacity modiﬁcation for m any-to-one matching problems. In: Proceed- ings of the 2023 International Conference on Autonomous Age nts and Multiagent Systems, AAMAS

work page 2023

[11] [11]

2880–2882

pp. 2880–2882. ACM, London, United Kingdom (2023). ht tps://doi.org/10.5555/3545946.3599110, https://dl.acm.org/doi/10.5555/3545946.3599110

work page doi:10.5555/3545946.3599110 2023

[12] [12]

Cseh, ´A., Heeger, K.: The stable marriage problem with ties and res tricted edges. Discret. Optim. 36, 100571 (2020). https://doi.org/10.1016/J.DISOPT.2020.100571, https://doi.org/10.1016/j.disopt.2020.100571

work page doi:10.1016/j.disopt.2020.100571 2020

[13] [13]

Darmann, A., D¨ ocker, J.: On a simple hard variant of not- all-equal 3-sat. Theor. Comput. Sci. 815, 147–152 (2020). https://doi.org/10.1016/J.TCS.2020.02.010, https://doi.org/10.1016/j.tcs.2020.02.010

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

[14] [14]

Discrete Applied Mathematics 157(7), 1655–1659 (2009)

Denman, R., Foster, S.: Using clausal graphs to determin e the computational complexity of k-bounded positive one-in-three sat. Discrete Applied Mathematics 157(7), 1655–1659 (2009)

work page 2009

[15] [15]

Journal of Artiﬁcial Intel- ligence Research 67, 797–833 (2020)

Fitzsimmons, Z., Lackner, M.: Incomplete preferences i n single-peaked electorates. Journal of Artiﬁcial Intel- ligence Research 67, 797–833 (2020)

work page 2020

[16] [16]

The American Mathematical Monthly 69(1), 9–15 (1962)

Gale, D., Shapley, L.S.: College admissions and the stab ility of marriage. The American Mathematical Monthly 69(1), 9–15 (1962)

work page 1962

[17] [17]

Discrete Applied Mathematics 11(3), 223–232 (1985)

Gale, D., Sotomayor, M.: Some remarks on the stable match ing problem. Discrete Applied Mathematics 11(3), 223–232 (1985)

work page 1985

[18] [18]

Garey, M.R., Johnson, D.S.: Computers and Intractabili ty: A Guide to the Theory of NP- Completeness (Series of Books in the Mathematical Sciences ). W. H. Freeman, ﬁrst edition edn. (1979), http://www.amazon.com/Computers-Intractability-NP-Completeness-Mathematical-Sciences/dp/0716710455

work page arXiv 1979

[19] [19]

In: Proceedings of the 23rd International Conference o n Autonomous Agents and Multiagent Systems, AAMAS 2024

Gokhale, S., Singla, S., Narang, S., Vaish, R.: Capacity modiﬁcation in the stable matching prob- lem. In: Proceedings of the 23rd International Conference o n Autonomous Agents and Multiagent Systems, AAMAS 2024. pp. 697–705. International Foundatio n for Autonomous Agents and Mul- tiagent Systems / ACM, Auckland, New Zealand (2024). https: //doi.org/10....

work page doi:10.5555/3635637.3662922 2024

[20] [20]

MIT Press, Cambridge, MA, USA (1989)

Gusﬁeld, D., Irving, R.W.: The stable marriage problem: structure and algorithms. MIT Press, Cambridge, MA, USA (1989)

work page 1989

[21] [21]

Discret e Applied Mathematics 48(3), 261–272 (1994)

Irving, R.W.: Stable marriage and indiﬀerence. Discret e Applied Mathematics 48(3), 261–272 (1994)

work page 1994

[22] [22]

In: Halld´ orsson, M.M

Irving, R.W., Manlove, D.F., Scott, S.: The hospitals/r esidents problem with ties. In: Halld´ orsson, M.M. (ed.) Algorithm Theory - SW AT 2000, 7th Scandinavian Worksh op on Algorithm Theory, Bergen, Norway, July 5-7, 2000, Proceedings. Lecture Notes in Computer Scie nce, vol. 1851, pp. 259–271. Springer (2000). https://doi.org/10.1007/3-540-44985-X 24, ...

work page doi:10.1007/3-540-44985-x 2000

[23] [23]

In: Annual Sym- posium on Theoretical Aspects of Computer Science

Irving, R.W., Manlove, D.F., Scott, S.: Strong stabilit y in the hospitals/residents problem. In: Annual Sym- posium on Theoretical Aspects of Computer Science. pp. 439– 450. Springer (2003)

work page 2003

[24] [24]

ACM Tran s

Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.E.: St rongly stable matchings in time O(nm) and extension to the hospitals-residents problem. ACM Tran s. Algorithms 3(2), 15 (2007). https://doi.org/10.1145/1240233.1240238, https://doi.org/10.1145/1240233.1240238

work page doi:10.1145/1240233.1240238 2007

[25] [25]

Kavitha, T., Nasre, M.: Popular matchings with variable item copies. Theor. Comput. Sci. 412(12-14), 1263– 1274 (2011). https://doi.org/10.1016/J.TCS.2010.12.06 7, https://doi.org/10.1016/j.tcs.2010.12.067

work page doi:10.1016/j.tcs.2010.12.06 2011

[26] [26]

Kavitha, T., Nasre, M., Nimbhorkar, P.: Popularity at mi nimum cost. J. Comb. Optim. 27(3), 574–596 (2014). https://doi.org/10.1007/S10878-012-9537-0, https://doi.org/10.1007/s10878-012-9537-0

work page doi:10.1007/s10878-012-9537-0 2014

[27] [27]

In: Hsu, W., Lee, D., Liao, C

Kunysz, A.: An algorithm for the maximum weight strongly stable matching problem. In: Hsu, W., Lee, D., Liao, C. (eds.) 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan. LI PIcs, vol. 123, pp. 42:1–42:13. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik (2018). https: //doi.org/10.4230/...

work page doi:10.4230/lipics.isaac.2018.42 2018

[28] [28]

In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algo rithms

Kunysz, A., Paluch, K., Ghosal, P.: Characterisation of strongly stable matchings. In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algo rithms. pp. 107–119. SIAM (2016)

work page 2016

[29] [29]

Manlove, D.F.: Stable marriage with ties and unacceptab le partners. Tech. rep., Technical Report TR-1999-29, University of Glasgow, Department of Computing . . . (1999)

work page 1999

[30] [30]

Manlove, D.F.: The structure of stable marriage with ind iﬀerence. Discret. Appl. Math. 122(1-3), 167–181 (2002). https://doi.org/10.1016/S0166-2 18X(01)00322-5, https://doi.org/10.1016/S0166-218X(01)00322-5

work page doi:10.1016/s0166-2 2002

[31] [31]

Porschen, S., Schmidt, T., Speckenmeyer, E., Wotzlaw, A .: XSAT and NAE-SAT of linear CNF classes. Discret. Appl. Math. 167, 1–14 (2014). https://doi.org/10.1016/J.DAM.2013.10.0 30, https://doi.org/10.1016/j.dam.2013.10.030

work page doi:10.1016/j.dam.2013.10.0 2014

[32] [32]

Econometric Society Monographs, Cambrid ge University Press (1990), https://books.google.co.in/books?id=JZNGHTZ6qX4C

Roth, A., Sotomayor, M.: Two-Sided Matching: A Study in G ame-Theoretic Model- ing and Analysis. Econometric Society Monographs, Cambrid ge University Press (1990), https://books.google.co.in/books?id=JZNGHTZ6qX4C

work page 1990

[33] [33]

Econometrica: Journal of the Econometric Society pp

Roth, A.E.: On the allocation of residents to rural hospi tals: a general property of two-sided matching markets. Econometrica: Journal of the Econometric Society pp. 425–4 27 (1986)

work page 1986

[34] [34]

In: Proceedings of the tenth annual ACM symposium on Theory of computing

Schaefer, T.J.: The complexity of satisﬁability proble ms. In: Proceedings of the tenth annual ACM symposium on Theory of computing. pp. 216–226 (1978) 30 K. Ranjan et al . A Non Monotonicity Property Here, we show that the HR-HT problem is not monotonic with respect to capacity aug- mentation. Consider the example instance G = ( R ∪ H , E ) shown in Fig....

work page 1978