[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Stabilization of capacitated matching games

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

An edge-weighted, vertex-capacitated graph \(G\) is called stable if the value of a maximum-weight capacity-matching equals the value of a maximum-weight fractional capacity-matching. Stable graphs play a key role in characterizing the existence of stable solutions for popular combinatorial games that involve the structure of matchings in graphs, such as network bargaining games and cooperative matching games. The vertex-stabilizer problem asks to compute a minimum number of players to block (i.e., vertices of \(G\) to remove) in order to ensure stability for such games. The problem has been shown to be solvable in polynomial-time, for unit-capacity graphs. This stays true also if we impose the restriction that the set of players to block must not intersect with a given specified maximum matching of \(G\). In this work, we investigate these algorithmic problems in the more general setting of arbitrary capacities. We show that the vertex-stabilizer problem with the additional restriction of avoiding a given maximum matching remains polynomial-time solvable. Differently, without this restriction, the vertex-stabilizer problem becomes NP-hard and even hard to approximate, in contrast to the unit-capacity case.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Algorithm 2
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. It was stated in [15, corollary 1] that \(M\) is maximum if and only if \(M'\) is maximum, but this example shows the forward direction to be false.

  2. In fact, this is the way the \(M\)-vertex-stabilizer problem is defined in [12]. We instead use the original definition in [8, 9] which assumes \(M\) to be maximum.

  3. [14] assumes that the graph is bipartite, but bipartiteness is not needed in their proof.

  4. It is stated in [18] (theorem 2.3.9) that a stable allocation for capacitated CMG exists iff \(G\) is stable, but this example shows this statement is not correct.

References

  1. Shapley, L.S., Shubik, M.: The assignment game i: The core. International Journal of Game Theory 1(1), 111–130 (1971)

    Article  MathSciNet  Google Scholar 

  2. Kleinberg, J., Tardos, E.: Balanced outcomes in social exchange networks. In: Proceedings of the 40th STOC, pp. 295–304 (2008)

  3. Nash, J.F.: The bargaining problem. Econometrica 18, 155–162 (1950)

    Article  MathSciNet  Google Scholar 

  4. Deng, X., Ibaraki, T., Nagamochi, H.: Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res. 24(3), 751–766 (1999)

    Article  MathSciNet  Google Scholar 

  5. Biró, P., Kern, W., Paulusma, D.: On solution concepts for matching games. In: Kratochvíl, J., Li, A., Fiala, J., Kolman, P. (eds.) Theory and Applications of Models of Computation, pp. 117–127. Springer, Berlin (2010)

    Chapter  Google Scholar 

  6. Könemann, J., Larson, K., Steiner, D.: Network bargaining: using approximate blocking sets to stabilize unstable instances. In: Serna, M. (ed.) Algorithmic Game Theory, pp. 216–226. Springer, Berlin (2012)

    Chapter  Google Scholar 

  7. Bock, A., Chandrasekaran, K., Könemann, J., Peis, B., Sanità, L.: Finding small stabilizers for unstable graphs. Math. Program. 154, 173–196 (2015)

    Article  MathSciNet  Google Scholar 

  8. Chandrasekaran, K., Gottschalk, C., Könemann, J., Peis, B., Schmand, D., Wierz, A.: Additive stabilizers for unstable graphs. Discrete Optim. 31, 56–78 (2019)

    Article  MathSciNet  Google Scholar 

  9. Ahmadian, S., Hosseinzadeh, H., Sanità, L.: Stabilizing network bargaining games by blocking players. Math. Program. 172, 249–275 (2018)

    Article  MathSciNet  Google Scholar 

  10. Chandrasekaran, K.: In: Fukunaga, T., Kawarabayashi, K.-i. (eds.) Graph Stabilization: A Survey, pp. 21–41. Springer, Singapore (2017)

  11. Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y., Okamoto, Y.: Efficient stabilization of cooperative matching games. Theor. Comput. Sci. 677, 69–82 (2017)

    Article  MathSciNet  Google Scholar 

  12. Koh, Z.K., Sanità, L.: Stabilizing weighted graphs. Math. Oper. Res. 45(4), 1318–1341 (2020)

    Article  MathSciNet  Google Scholar 

  13. Gottschalk, C.: Personal communication (2018)

  14. Bateni, M., Hajiaghayi, M., Immorlica, N., Mahini, H.: The cooperative game theory foundations of network bargaining games. arXiv (2010)

  15. Farczadi, L., Georgiou, K., Könemann, J.: Network Bargaining with General Capacities. arXiv preprint arXiv:1306.4302 (2013)

  16. Alimonti, P., Kann, V.: Some apx-completeness results for cubic graphs. Theor. Comput. Sci. 237, 123–134 (2000)

    Article  MathSciNet  Google Scholar 

  17. Halldórsson, M.M.: Approximating the minimum maximal independence number. Inf. Process. Lett. 46(4), 169–172 (1993)

    Article  MathSciNet  Google Scholar 

  18. Farczadi, L.: Matchings and games on networks. PhD thesis, University of Waterloo (2015)

  19. Biró, P., Kern, W., Paulusma, D., Wojuteczky, P.: The stable fixtures problem with payments. In: Mayr, E.W. (ed.) Graph-Theoretic Concepts in Computer Science, pp. 49–63. Springer, Berlin (2016)

    Chapter  Google Scholar 

  20. Benedek, M., Biró, P., Kern, W., Pálvölgyi, D., Paulusma, D.: Partitioned Matching Games for International Kidney Exchange (2023)

Download references

Acknowledgements

The second and third authors are supported by the NWO VIDI grant VI.Vidi.193.087. The second author thanks the 2021 Hausdorff Research Institute for Mathematics Program Discrete Optimization, during which part of this work was developed.

Author information

Authors and Affiliations

  1. Mathematics, University of Waterloo, 200 University Avenue West, Waterloo, N2L 3G1, ON, Canada

    Matthew Gerstbrein

  2. Computing Sciences, Bocconi University, Via Roentgen 1, 20136, Milan, Lombardy, Italy

    Laura Sanità

  3. Mathematics and Computer Science, Eindhoven University of Technology, Groene Loper 3, Eindhoven, 5612 AE, Noord-Brabant, The Netherlands

    Lucy Verberk

Authors
  1. Matthew Gerstbrein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Laura Sanità
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lucy Verberk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lucy Verberk.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gerstbrein, M., Sanità, L. & Verberk, L. Stabilization of capacitated matching games. Math. Program. (2024). https://doi.org/10.1007/s10107-024-02169-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10107-024-02169-x

Keywords

Mathematics Subject Classification

Search

Navigation