Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems
Document Open Access Logo

Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems

Authors Niclas Boehmer, Klaus Heeger, Rolf Niedermeier

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.21.pdf
  • Filesize: 0.76 MB
  • 15 pages

Document Identifiers

Author Details

Niclas Boehmer
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany
Klaus Heeger
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany
Rolf Niedermeier
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany

Acknowledgements

NB was supported by the DFG project MaMu (NI 369/19) and by the DFG project ComSoc-MPMS (NI 369/22). KH was supported by the DFG Research Training Group 2434 "Facets of Complexity" and by the DFG project FPTinP (NI 369/16).

Cite As Get BibTex

Niclas Boehmer, Klaus Heeger, and Rolf Niedermeier. Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.21

Abstract

When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change over time. Consequently, an initially stable matching may become unstable. Then, a natural goal is to find a matching which is stable with respect to the modified preferences and as close as possible to the initial one. For Stable Marriage/Roommates, this problem was formally defined as Incremental Stable Marriage/Roommates by Bredereck et al. [AAAI '20]. As they showed that Incremental Stable Roommates and Incremental Stable Marriage with Ties are NP-hard, we focus on the parameterized complexity of these problems. We answer two open questions of Bredereck et al. [AAAI '20]: We show that Incremental Stable Roommates is W[1]-hard parameterized by the number of changes in the preferences, yet admits an intricate XP-algorithm, and we show that Incremental Stable Marriage with Ties is W[1]-hard parameterized by the number of ties. Furthermore, we analyze the influence of the degree of "similarity" between the agents' preference lists, identifying several polynomial-time solvable and fixed-parameter tractable cases, but also proving that Incremental Stable Roommates and Incremental Stable Marriage with Ties parameterized by the number of different preference lists are W[1]-hard.

Subject Classification

ACM Subject Classification
  • Theory of computation → W hierarchy
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Algorithmic game theory
Keywords
  • Stable Marriage
  • Stable Roommates
  • adapting to changing preferences
  • NP-hardness
  • W[1]-hardness
  • XP
  • FPT
  • master lists
  • incremental algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mohammad Akbarpour, Shengwu Li, and Shayan Oveis Gharan. Thickness and information in dynamic matching markets. J. Political Econ., 128(3):783-815, 2020. Google Scholar
  2. Mariagiovanna Baccara, SangMok Lee, and Leeat Yariv. Optimal dynamic matching. Theor. Econ., 15(3):1221-1278, 2020. Google Scholar
  3. Sayan Bhattacharya, Martin Hoefer, Chien-Chung Huang, Telikepalli Kavitha, and Lisa Wagner. Maintaining near-popular matchings. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP '15), pages 504-515. Springer, 2015. Google Scholar
  4. Niclas Boehmer, Robert Bredereck, Klaus Heeger, and Rolf Niedermeier. Bribery and control in stable marriage. J. Artif. Intell. Res., 71:993-1048, 2021. Google Scholar
  5. Niclas Boehmer, Klaus Heeger, and Rolf Niedermeier. Theory of and experiments on minimally invasive stability preservation in changing two-sided matching markets. CoRR, abs/2112.05777, 2021. Accepted at AAAI'22. URL: http://arxiv.org/abs/2112.05777.
  6. Niclas Boehmer and Rolf Niedermeier. Broadening the research agenda for computational social choice: Multiple preference profiles and multiple solutions. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '21), pages 1-5. ACM, 2021. Google Scholar
  7. Robert Bredereck, Jiehua Chen, Dušan Knop, Junjie Luo, and Rolf Niedermeier. Adapting stable matchings to evolving preferences. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI '20), pages 1830-1837. AAAI Press, 2020. Full version available at arxiv.org/abs/1907.01375. Google Scholar
  8. Robert Bredereck, Klaus Heeger, Dušan Knop, and Rolf Niedermeier. Multidimensional stable roommates with master list. In Proceedings of the 16th International Conferenc of the Web and Internet Economics (WINE '20), pages 59-73. Springer, 2020. Google Scholar
  9. Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. SIAM J. Comput., 33(6):1417-1440, 2004. Google Scholar
  10. Jiehua Chen, Rolf Niedermeier, and Piotr Skowron. Stable marriage with multi-modal preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC '18), pages 269-286. ACM, 2018. Google Scholar
  11. Jiehua Chen, Piotr Skowron, and Manuel Sorge. Matchings under preferences: Strength of stability and tradeoffs. ACM Trans. Economics and Comput., 9(4):20:1-20:55, 2021. Google Scholar
  12. Ágnes Cseh and David F. Manlove. Stable marriage and roommates problems with restricted edges: Complexity and approximability. Discret. Optim., 20:62-89, 2016. Google Scholar
  13. Lin Cui and Weijia Jia. Cyclic stable matching for three-sided networking services. Comput. Networks, 57(1):351-363, 2013. Google Scholar
  14. Ettore Damiano and Ricky Lam. Stability in dynamic matching markets. Games Econ. Behav., 52(1):34-53, 2005. Google Scholar
  15. Laura Doval. Dynamically stable matching. CoRR, abs/1906.11391v5, 2021. URL: http://arxiv.org/abs/1906.11391.
  16. David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility location in evolving metrics. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP '14), pages 459-470. Springer, 2014. Google Scholar
  17. Tomás Feder. A new fixed point approach for stable networks and stable marriages. J. Comput. Syst. Sci., 45(2):233-284, 1992. Google Scholar
  18. Itai Feigenbaum, Yash Kanoria, Irene Lo, and Jay Sethuraman. Dynamic matching in school choice: Efficient seat reallocation after late cancellations. Manag. Sci., 66(11):5341-5361, 2020. Google Scholar
  19. Tamás Fleiner, Robert W. Irving, and David F. Manlove. Efficient algorithms for generalized stable marriage and roommates problems. Theor. Comput. Sci., 381(1-3):162-176, 2007. Google Scholar
  20. Karthik Gajulapalli, James A. Liu, Tung Mai, and Vijay V. Vazirani. Stability-preserving, time-efficient mechanisms for school choice in two rounds. In Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS '20), pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  21. Begum Genc, Mohamed Siala, Barry O'Sullivan, and Gilles Simonin. Finding robust solutions to stable marriage. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI '17), pages 631-637. ijcai.org, 2017. Google Scholar
  22. Begum Genc, Mohamed Siala, Barry O'Sullivan, and Gilles Simonin. Robust stable marriage. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI '17), pages 4925-4926. AAAI Press, 2017. Google Scholar
  23. Begum Genc, Mohamed Siala, Gilles Simonin, and Barry O'Sullivan. Complexity study for the robust stable marriage problem. Theor. Comput. Sci., 775:76-92, 2019. Google Scholar
  24. Michel X. Goemans and Francisco Unda. Approximating incremental combinatorial optimization problems. In Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM 2017), pages 6:1-6:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  25. Anupam Gupta, Kunal Talwar, and Udi Wieder. Changing bases: Multistage optimization for matroids and matchings. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP '14), pages 563-575. Springer, 2014. Google Scholar
  26. Dan Gusfield and Robert W. Irving. The Stable Marriage Problem - Structure and Algorithms. Foundations of computing series. MIT Press, 1989. Google Scholar
  27. Kathrin Hanauer, Monika Henzinger, and Christian Schulz. Recent advances in fully dynamic graph algorithms (invited talk). In Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND '22), pages 1:1-1:47. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  28. Sepp Hartung and Rolf Niedermeier. Incremental list coloring of graphs, parameterized by conservation. Theor. Comput. Sci., 494:86-98, 2013. Google Scholar
  29. Robert W. Irving, David F. Manlove, and Sandy Scott. The stable marriage problem with master preference lists. Discret. Appl. Math., 156(15):2959-2977, 2008. Google Scholar
  30. Naoyuki Kamiyama. Many-to-many stable matchings with ties, master preference lists, and matroid constraints. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS '19), pages 583-591. IFAAMAS, 2019. Google Scholar
  31. S. Kumar and P. Gupta. An incremental algorithm for the maximum flow problem. J. Math. Model. Algorithms, 2(1):1-16, 2003. Google Scholar
  32. Adam Kunysz. An algorithm for the maximum weight strongly stable matching problem. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC '18), pages 42:1-42:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  33. Adam Kunysz, Katarzyna E. Paluch, and Pratik Ghosal. Characterisation of strongly stable matchings. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16), pages 107-119. SIAM, 2016. Google Scholar
  34. Ce Liu. Stability in repeated matching markets. CoRR, abs/2007.03794v2, 2021. URL: http://arxiv.org/abs/2007.03794.
  35. Junjie Luo, Hendrik Molter, André Nichterlein, and Rolf Niedermeier. Parameterized dynamic cluster editing. Algorithmica, 83(1):1-44, 2021. Google Scholar
  36. Tung Mai and Vijay V. Vazirani. Finding stable matchings that are robust to errors in the input. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA '18), pages 60:1-60:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  37. Dániel Marx and Ildikó Schlotter. Parameterized complexity and local search approaches for the stable marriage problem with ties. Algorithmica, 58(1):170-187, 2010. Google Scholar
  38. Kitty Meeks and Baharak Rastegari. Solving hard stable matching problems involving groups of similar agents. Theor. Comput. Sci., 844:171-194, 2020. Google Scholar
  39. Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci., 67(4):757-771, 2003. Google Scholar
  40. G. Ramalingam and Thomas W. Reps. An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms, 21(2):267-305, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact