Document Open Access Logo

On the Complexity of Stable Fractional Hypergraph Matching

Authors Takashi Ishizuka, Naoyuki Kamiyama

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.11.pdf
  • Filesize: 0.63 MB
  • 12 pages

Document Identifiers

Author Details

Takashi Ishizuka
  • Graduate School of Mathematics, Kyushu University, 744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan
Naoyuki Kamiyama
  • Institute of Mathematics for Industry, Kyushu University, JST, PRESTO, 744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan

Funding

  • Kamiyama, Naoyuki: This research was supported by JST PRESTO Grant Number JPMJPR1753, Japan.

Cite AsGet BibTex

Takashi Ishizuka and Naoyuki Kamiyama. On the Complexity of Stable Fractional Hypergraph Matching. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.11

Abstract

In this paper, we consider the complexity of the problem of finding a stable fractional matching in a hypergraphic preference system. Aharoni and Fleiner proved that there exists a stable fractional matching in every hypergraphic preference system. Furthermore, Kintali, Poplawski, Rajaraman, Sundaram, and Teng proved that the problem of finding a stable fractional matching in a hypergraphic preference system is PPAD-complete. In this paper, we consider the complexity of the problem of finding a stable fractional matching in a hypergraphic preference system whose maximum degree is bounded by some constant. The proof by Kintali, Poplawski, Rajaraman, Sundaram, and Teng implies the PPAD-completeness of the problem of finding a stable fractional matching in a hypergraphic preference system whose maximum degree is 5. In this paper, we prove that (i) this problem is PPAD-complete even if the maximum degree is 3, and (ii) if the maximum degree is 2, then this problem can be solved in polynomial time. Furthermore, we prove that the problem of finding an approximate stable fractional matching in a hypergraphic preference system is PPAD-complete.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • fractional hypergraph matching
  • stable matching
  • PPAD-completeness

Metrics

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

References

  1. R. Aharoni and T. Fleiner. On a lemma of Scarf. Journal of Combinatorial Theory, Series B, 87(1):72-80, 2003. Google Scholar
  2. P. Biró and T. Fleiner. Fractional solutions for capacitated NTU-games, with applications to stable matchings. Discrete Optimization, 22:241-254, 2016. Google Scholar
  3. P. Biró, T. Fleiner, and R. W. Irving. Matching couples with Scarf’s algorithm. Annals of Mathematics and Artificial Intelligence, 77(3-4):303-316, 2016. Google Scholar
  4. P. Biró and F. Klijn. MATCHING WITH COUPLES: A MULTIDISCIPLINARY SURVEY. International Game Theory Review, 15(02):1340008, 2013. Google Scholar
  5. X. Chen, X. Deng, and S.-H. Teng. Settling the Complexity of Computing Two-player Nash Equilibria. Journal of the ACM, 56(3):14:1-14:57, 2009. Google Scholar
  6. C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009. Google Scholar
  7. D. Gale and L. S. Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  8. D. Gusfield and R. W. Irving. The Stable Marriage Problem: Structure and Algorithm. MIT Press, 1989. Google Scholar
  9. L. G. Khachiyan. Polynomial algorithms in linear programming. USSR Computational Mathematics and Mathematical Physics, 20(1):53-72, 1980. Google Scholar
  10. S. Kintali, L. J. Poplawski, R. Rajaraman, R. Sundaram, and S.-H. Teng. Reducibility among Fractional Stability Problems. SIAM Journal on Computing, 42(6):2063-2113, 2013. Google Scholar
  11. N. Megiddo and C. H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317-324, 1991. Google Scholar
  12. J. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Science, 36(1):48-49, 1950. Google Scholar
  13. T. Nguyen and R. Vohra. Near Feasible Stable Matchings. In Proceedings of the 16th ACM Conference on Economics and Computation, pages 41-42, 2015. Google Scholar
  14. C. H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. Google Scholar
  15. C. H. Papadimitriou. The Complexity of Finding Nash Equilibria. In N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, editors, Algorithmic game theory, pages 29-52. Cambridge university press, 2007. Google Scholar
  16. H. E. Scarf. The Core of an N Person Game. Econometrica, 35(1):50-69, 1967. 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 Imprint Privacy Contact