[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Affinely Representable Lattices, Stable Matchings, and Choice Functions

  • Conference paper
  • First Online:
Integer Programming and Combinatorial Optimization (IPCO 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12707))

Abstract

Birkhoff’s representation theorem [11] defines a bijection between elements of a distributive lattice \(\mathcal{L}\) and the family of upper sets of an associated poset \(\mathcal{B}\). When elements of \(\mathcal{L}\) are the stable matchings in an instance of Gale and Shapley’s marriage model, Irving et al. [22] showed how to use \(\mathcal{B}\) to devise a combinatorial algorithm for maximizing a linear function over the set of stable matchings. In this paper, we introduce a general property of distributive lattices, which we term as affine representability, and show its role in efficiently solving linear optimization problems over the elements of a distributive lattice, as well as describing the convex hull of the characteristic vectors of lattice elements. We apply this concept to the stable matching model with path-independent quota-filling choice functions, thus giving efficient algorithms and a compact polyhedral description for this model. To the best of our knowledge, this model generalizes all models from the literature for which similar results were known, and our paper is the first that proposes efficient algorithms for stable matchings with choice functions, beyond extension of the Deferred Acceptance algorithm [31].

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

Access this chapter

Log in via an institution

Subscribe and save

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

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The result proved by Birkhoff is actually a bijection between the families of lattices and posets, but in this paper we shall not need it in full generality.

References

  1. Abdulkadiroğlu, A., Sönmez, T.: School choice: a mechanism design approach. Am. Econ. Rev. 93(3), 729–747 (2003)

    Google Scholar 

  2. Aizerman, M., Malishevski, A.: General theory of best variants choice: some aspects. IEEE Trans. Autom. Control 26(5), 1030–1040 (1981)

    Article  MathSciNet  Google Scholar 

  3. Alkan, A.: On preferences over subsets and the lattice structure of stable matchings. Rev. Econ. Design 6(1), 99–111 (2001)

    Article  Google Scholar 

  4. Alkan, A.: A class of multipartner matching markets with a strong lattice structure. Econ. Theor. 19(4), 737–746 (2002)

    Article  MathSciNet  Google Scholar 

  5. Aprile, M., Cevallos, A., Faenza, Y.: On 2-level polytopes arising in combinatorial settings. SIAM J. Discret. Mathe. 32(3), 1857–1886 (2018)

    Article  MathSciNet  Google Scholar 

  6. Aygün, O., Sönmez, T.: Matching with contracts: comment. Am. Econ. Rev. 103(5), 2050–51 (2013)

    Article  Google Scholar 

  7. Aygün, o., Turhan, B.: Dynamic reserves in matching markets: Theory and applications. Available at SSRN 2743000 (2016)

    Google Scholar 

  8. Baïou, M., Balinski, M.: Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry). Discret. Appl. Math. 101(1–3), 1–12 (2000)

    Article  MathSciNet  Google Scholar 

  9. Baïou, M., Balinski, M.: The stable admissions polytope. Math. Program. 87(3), 427–439 (2000). https://doi.org/10.1007/s101070050004

    Article  MathSciNet  MATH  Google Scholar 

  10. Bansal, v., Agrawal, A., Malhotra, V.S.: Polynomial time algorithm for an optimal stable assignment with multiple partners. Theoret. Comput. Sci. 379(3), 317–328 (2007)

    Google Scholar 

  11. Birkhoff, G.: Rings of sets. Duke Math. J. 3(3), 443–454 (1937)

    Article  MathSciNet  Google Scholar 

  12. Blair, C.: The lattice structure of the set of stable matchings with multiple partners. Math. Oper. Res. 13(4), 619–628 (1988)

    Article  MathSciNet  Google Scholar 

  13. Chambers, C.P., Yenmez, M.B.: Choice and matching. Am. Econ. J. Microecon. 9(3), 126–47 (2017)

    Google Scholar 

  14. Echenique, F., Yenmez, M.B.: How to control controlled school choice. Am. Econ. Rev. 105(8), 2679–2694 (2015)

    Google Scholar 

  15. Faenza, Y., Zhang, X.: Affinely representable lattices, stable matchings, and choice functions (2020). Available on arXiv

    Google Scholar 

  16. Fleiner, T.: On the stable b-matching polytope. Math. Soc. Sci. 46(2), 149–158 (2003)

    Article  MathSciNet  Google Scholar 

  17. Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Month. 69(1), 9–15 (1962)

    Google Scholar 

  18. Garg, V.K.: Predicate detection to solve combinatorial optimization problems. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 235–245 (2020)

    Google Scholar 

  19. Gusfield, D., Irving, R.W.: The stable marriage problem: structure and algorithms. MIT press (1989)

    Google Scholar 

  20. Hatfield, J.W., Milgrom, P.R.: Matching with contracts. Am. Econ. Rev. 95(4), 913–935 (2005)

    Google Scholar 

  21. Irving, R.W., Leather, P.: The complexity of counting stable marriages. SIAM J. Comput. 15(3), 655–667 (1986)

    Google Scholar 

  22. Irving, R.W., Leather, P., Gusfield, D.: An efficient algorithm for the “optimal” stable marriage. J. ACM (JACM) 34(3), 532–543 (1987)

    Google Scholar 

  23. Kamada, Y., Kojima, F.: Efficient matching under distributional constraints: theory and applications. Am. Econ. Rev. 105(1), 67–99 (2015)

    Article  Google Scholar 

  24. Knuth, D.E.: Marriages stables. Technical report (1976)

    Google Scholar 

  25. Manlove, D.: Algorithmics of matching under preferences, vol. 2. World Scientific (2013)

    Google Scholar 

  26. Martínez, R., Massó, J., Neme, A., Oviedo, J.: An algorithm to compute the full set of many-to-many stable matchings. Math. Soc. Sci. 47(2), 187–210 (2004)

    Article  MathSciNet  Google Scholar 

  27. McVitie, D.G., Wilson, L.B.: The stable marriage problem. Commun. ACM 14(7), 486–490 (1971)

    Google Scholar 

  28. Nguyen, T., Vohra, R.: Stable matching with proportionality constraints. Oper. Res. 67(6), 1503–1519 (2019)

    Google Scholar 

  29. Picard, J.-C.: Maximal closure of a graph and applications to combinatorial problems. Manage. Sci. 22(11), 1268–1272 (1976)

    Article  MathSciNet  Google Scholar 

  30. Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econo. 92(6), 991–1016 (1984)

    Google Scholar 

  31. Roth, A.E.: Stability and polarization of interests in job matching. Econom. J. Econ. Soc. 52, 47–57 (1984)

    Google Scholar 

  32. Roth, A.E., Rothblum, U.G., Vate, J.H.V.: Stable matchings, optimal assignments, and linear programming. Math. Oper. Res. 18(4), 803–828 (1993)

    Google Scholar 

  33. Rothblum, U.G.: Characterization of stable matchings as extreme points of a polytope. Math. Program. 54(1–3), 57–67 (1992)

    Google Scholar 

  34. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer Science & Business Media, Heidelberg (2003)

    Google Scholar 

  35. Shapley, L.S., Shubik, M.: The assignment game I: the core. Int. J. Game Theory, 1(1), 111–130 (1971). https://doi.org/10.1007/BF01753437

  36. Stanley, R.P.: Two poset polytopes. Discret. Comput. Geom. 1(1), 9–23 (1986). https://doi.org/10.1007/BF02187680

    Article  MathSciNet  MATH  Google Scholar 

  37. Tomoeda, K.: Finding a stable matching under type-specific minimum quotas. J. Econ. Theory 176, 81–117 (2018)

    Article  MathSciNet  Google Scholar 

  38. Vate, J.H.V.: Linear programming brings marital bliss. Oper. Res. Lett. 8(3), 147–153 (1989)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Columbia University, New York, NY, 10027, USA

    Yuri Faenza & Xuan Zhang

Authors
  1. Yuri Faenza
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xuan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xuan Zhang .

Editor information

Editors and Affiliations

  1. Georgia Institute of Technology, Atlanta, GA, USA

    Mohit Singh

  2. Cornell University, Ithaca, NY, USA

    David P. Williamson

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Faenza, Y., Zhang, X. (2021). Affinely Representable Lattices, Stable Matchings, and Choice Functions. In: Singh, M., Williamson, D.P. (eds) Integer Programming and Combinatorial Optimization. IPCO 2021. Lecture Notes in Computer Science(), vol 12707. Springer, Cham. https://doi.org/10.1007/978-3-030-73879-2_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-73879-2_7

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-73878-5

  • Online ISBN: 978-3-030-73879-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation