Document Open Access Logo

Stable Matching Games: Manipulation via Subgraph Isomorphism

Authors Sushmita Gupta, Sanjukta Roy

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.29.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Sushmita Gupta
Sanjukta Roy

Cite As Get BibTex

Sushmita Gupta and Sanjukta Roy. Stable Matching Games: Manipulation via Subgraph Isomorphism. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.29

Abstract

In this paper we consider a problem that arises from a strategic issue in the stable matching model (with complete preference lists) from the viewpoint of exact-exponential time algorithms. Specifically, we study the Stable Extension of Partial Matching (SEOPM) problem, where the input consists of the complete preference lists of men, and a partial matching. The objective is to find (if one exists) a set of preference lists of women, such that the men-optimal Gale Shapley algorithm outputs a perfect matching that contains the given partial matching. Kobayashi and Matsui [Algorithmica, 2010] proved this problem is NP-complete. In this article, we give an exact-exponential algorithm for SEOPM running in time 2^{O(n)}, where n denotes the number of men/women. We complement our algorithmic finding by showing that unless Exponential Time Hypothesis (ETH) fails, our algorithm is asymptotically optimal. That is, unless ETH fails, there is no algorithm for SEOPM running in time 2^{o(n)}. Our algorithm is a non-trivial combination of  a parameterized algorithm for Subgraph Isomorphism, a relationship between stable matching and finding an out-branching in an appropriate graph and enumerating non-isomorphic out-branchings.

Subject Classification

Keywords
  • stable matching
  • Gale-Shapley algorithm
  • suitor graph
  • subgraph iso- morphism
  • exact-exponential time algorithms

Metrics

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

References

  1. Omid Amini, Fedor V. Fomin, and Saket Saurabh. Counting subgraphs via homomorphisms. SIAM J. Discrete Math., 26(2):695-717, 2012. Google Scholar
  2. Terry Beyer and Sandra Mitchell Hedetniemi. Constant time generation of rooted trees. SIAM Journal on Computing, 9(4):706-712, 1980. Google Scholar
  3. Robert Bredereck, Jiehua Chen, Piotr Faliszewski, Jiong Guo, Rolf Niedermeier, and Gerhard J. Woeginger. Parameterized algorithmics for computational social choice: Nine research challenges. Tsinghua Science and Technology, 19(4):358-373, 2014. Google Scholar
  4. A. Cseh and D. F. Manlove. Stable marriage and roommates problems with restricted edges: complexity and approximability. In Proceedings of SAGT'15, volume 9347 of LNCS, pages 15-26, 2015. Google Scholar
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  6. Fedor V Fomin and Dieter Kratsch. Exact exponential algorithms. Springer Science &Business Media, 2010. Google Scholar
  7. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Representative sets of product families. In ESAs, volume 8737 of Lecture Notes in Computer Science, pages 443-454. Springer, 2014. Google Scholar
  8. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, and B. V. Raghavendra Rao. Faster algorithms for finding and counting subgraphs. J. Comput. Syst. Sci., 78(3):698-706, 2012. Google Scholar
  9. David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  10. D. Gusfield and R. W. Irving. The Stable Marriage Problem-Structure and Algorithm. The MIT Press, 1989. Google Scholar
  11. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  12. H. Kobayashi and T. Matsui. Successful manipulation in stable marriage model with complete preference. IEICE Trans. on Inf. Syst., E92-D(2):116-119, 2009. Google Scholar
  13. H. Kobayashi and T. Matsui. Cheating strategies for the gale-shapley algorithm with complete preference lists. Algorithmica, 58:151-169, 2010. Google Scholar
  14. D. F. Manlove. Algorithmics of matching under preferences, volume 2 of Theoretical Computer Science. World Scientific, 2013. Google Scholar
  15. 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
  16. Dániel Marx and Ildikó Schlotter. Stable assignment with couples: Parameterized complexity and local search. Discrete Optimization, 8(1):25-40, 2011. Google Scholar
  17. Richard Otter. The number of trees. Annals of Mathematics, pages 583-599, 1948. Google Scholar
  18. A. E. Roth and M. Sotomayor. Two-Sided Matching: A Study in Game Theoretic Modeling and Analysis. Cambridge Univ. Press, 1990. 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