IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v157y2026icp322-350.html

Adapting stable matchings to evolving preferences

Author

Listed:
  • Bredereck, Robert
  • Chen, Jiehua
  • Knop, Dušan
  • Luo, Junjie
  • Niedermeier, Rolf

Abstract

Adaptivity to changing environments and constraints is key to success in modern society. We address this principle by proposing “incrementalized versions” of Stable Marriage and Stable Roommates, asking what the computational cost is of adapting an existing stable matching after agents’ preferences have changed. We additionally require that the new stable matching should not deviate too much from the old one. After formalizing these incremental versions, we provide a comprehensive computational complexity landscape of Incremental Stable Marriage and Incremental Stable Roommates. To this end, we exploit the parameters “degree of change” in the input (difference between old and new preference profile) and in the output (difference between old and new stable matching). We obtain both hardness and tractability results. In particular, with ties in preferences, both problems remain computationally intractable even under minimal preference changes, whereas with strict preferences, both become (fixed-parameter) tractable, regardless of the extent of preference changes.

Suggested Citation

  • Bredereck, Robert & Chen, Jiehua & Knop, Dušan & Luo, Junjie & Niedermeier, Rolf, 2026. "Adapting stable matchings to evolving preferences," Games and Economic Behavior, Elsevier, vol. 157(C), pages 322-350.
    • Handle: RePEc:eee:gamebe:v:157:y:2026:i:c:p:322-350
    DOI: 10.1016/j.geb.2026.02.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825626000278
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2026.02.006?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Prajakta Nimbhorkar & V. Arvind Rameshwar, 2019. "Dynamic rank-maximal and popular matchings," Journal of Combinatorial Optimization, Springer, vol. 37(2), pages 523-545, February.
    2. Shuichi Miyazaki & Kazuya Okamoto, 2019. "Jointly stable matchings," Journal of Combinatorial Optimization, Springer, vol. 38(2), pages 646-665, August.
    3. Itai Feigenbaum & Yash Kanoria & Irene Lo & Jay Sethuraman, 2020. "Dynamic Matching in School Choice: Efficient Seat Reassignment After Late Cancellations," Management Science, INFORMS, vol. 66(11), pages 5341-5361, November.
    4. Gonczarowski, Yannai A. & Nisan, Noam & Ostrovsky, Rafail & Rosenbaum, Will, 2019. "A stable marriage requires communication," Games and Economic Behavior, Elsevier, vol. 118(C), pages 626-647.
    5. Renhua Li & Leonie U Hempel & Tingbo Jiang, 2015. "A Non-Parametric Peak Calling Algorithm for DamID-Seq," PLOS ONE, Public Library of Science, vol. 10(3), pages 1-12, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Carlos V. G. C. Lima & Dieter Rautenbach & Uéverton S. Souza & Jayme L. Szwarcfiter, 2022. "On the computational complexity of the bipartizing matching problem," Annals of Operations Research, Springer, vol. 316(2), pages 1235-1256, September.
    2. Hans L. Bodlaender & Josse Dobben de Bruyn & Dion Gijswijt & Harry Smit, 2022. "Constructing tree decompositions of graphs with bounded gonality," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2681-2699, November.
    3. Mustafa Oğuz Afacan & Eray Cumbul, 2025. "Waitlist engineering in discrete object allocations with outside option," International Journal of Game Theory, Springer;Game Theory Society, vol. 54(1), pages 1-22, June.
    4. Bhaskar Ray Chaudhury & Jugal Garg & Kurt Mehlhorn & Ruta Mehta & Pranabendu Misra, 2024. "Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number," Mathematics of Operations Research, INFORMS, vol. 49(4), pages 2323-2340, November.
    5. Dmitry V. Gribanov & Dmitry S. Malyshev & Panos M. Pardalos & Nikolai Yu. Zolotykh, 2025. "A new and faster representation for counting integer points in parametric polyhedra," Computational Optimization and Applications, Springer, vol. 92(3), pages 811-861, December.
    6. Suat Evren, 2023. "Social Surplus Maximization in Sponsored Search Auctions Requires Communication," Papers 2305.07729, arXiv.org.
    7. Édouard Bonnet & Sergio Cabello, 2021. "The complexity of mixed-connectivity," Annals of Operations Research, Springer, vol. 307(1), pages 25-35, December.
    8. Matheus J. Ota & Ricardo Fukasawa, 2025. "Hardness of Pricing Routes for Two-Stage Stochastic Vehicle Routing Problems with Scenarios," Operations Research, INFORMS, vol. 73(4), pages 2177-2187, July.
    9. Fomin, Fedor V. & Fraigniaud, Pierre & Golovach, Petr A., 2022. "Present-biased optimization," Mathematical Social Sciences, Elsevier, vol. 119(C), pages 56-67.
    10. Nicole Immorlica & Brendan Lucier & Vahideh Manshadi & Alexander Wei, 2023. "Designing Approximately Optimal Search on Matching Platforms," Management Science, INFORMS, vol. 69(8), pages 4609-4626, August.
    11. Yannai A. Gonczarowski & Clayton Thomas, 2022. "Structural Complexities of Matching Mechanisms," Papers 2212.08709, arXiv.org, revised Mar 2024.
    12. Klaus Heeger & Danny Hermelin & George B. Mertzios & Hendrik Molter & Rolf Niedermeier & Dvir Shabtay, 2023. "Equitable scheduling on a single machine," Journal of Scheduling, Springer, vol. 26(2), pages 209-225, April.
    13. Irene Lo & Vahideh Manshadi & Scott Rodilitz & Ali Shameli, 2024. "Commitment on Volunteer Crowdsourcing Platforms: Implications for Growth and Engagement," Manufacturing & Service Operations Management, INFORMS, vol. 26(5), pages 1787-1805, September.
    14. Naonori Kakimura & Donghao Zhu, 2021. "Dynamic Bipartite Matching Market with Arrivals and Departures," Papers 2110.10824, arXiv.org.
    15. Suresh P. Sethi & Sushil Gupta & Vipin K. Agrawal & Vijay K. Agrawal, 2022. "Nobel laureates’ contributions to and impacts on operations management," Production and Operations Management, Production and Operations Management Society, vol. 31(12), pages 4283-4303, December.
    16. Yu, Renjie & Oron, Daniel, 2025. "Single-machine scheduling with fixed energy recharging times to minimize the number of late jobs and the number of just-in-time jobs: A parameterized complexity analysis," European Journal of Operational Research, Elsevier, vol. 324(1), pages 40-48.
    17. Juho Lauri & Sourav Dutta & Marco Grassia & Deepak Ajwani, 2023. "Learning fine-grained search space pruning and heuristics for combinatorial optimization," Journal of Heuristics, Springer, vol. 29(2), pages 313-347, June.
    18. Danny Hermelin & Matthias Mnich & Simon Omlor, 2024. "Serial batching to minimize the weighted number of tardy jobs," Journal of Scheduling, Springer, vol. 27(6), pages 545-556, December.
    19. Martin Koutecký & Johannes Zink, 2025. "Complexity of scheduling few types of jobs on related and unrelated machines," Journal of Scheduling, Springer, vol. 28(1), pages 139-156, February.
    20. Niels Lindner & Julian Reisch, 2022. "An analysis of the parameterized complexity of periodic timetabling," Journal of Scheduling, Springer, vol. 25(2), pages 157-176, April.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:157:y:2026:i:c:p:322-350. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.