All Finite Lattices Are Stable Matching Lattices

References

• [1] Abdulkadiroğlu A, Sönmez T (2003) School choice: A mechanism design approach. Amer. Econom. Rev. 93(3):729–747.Crossref, Google Scholar
• [2] Alkan A (2001) On preferences over subsets and the lattice structure of stable matchings. Rev. Econom. Design 6(1):99–111. Crossref, Google Scholar
• [3] Avann SP (1961) Application of the join-irreducible excess function to semi-modular lattices. Math. Ann. 142(4):345–354.Crossref, Google Scholar
• [4] Bansal V, Agrawal A, Malhotra VS (2007) Polynomial time algorithm for an optimal stable assignment with multiple partners. Theoret. Comput. Sci. 379(3):317–328.Crossref, Google Scholar
• [5] Bĕlohlávek R (2004) Concept lattices and order in fuzzy logic. Ann. Pure Appl. Logic 128(1–3):277–298.Crossref, Google Scholar
• [6] Birkhoff G (1937) Rings of sets. Duke Math. J. 3(3):443–454.Crossref, Google Scholar
• [7] Blair C (1984) Every finite distributive lattice is a set of stable matchings. J. Combin. Theory Ser. A 37(3):353–356.Crossref, Google Scholar
• [8] Blair C (1988) The lattice structure of the set of stable matchings with multiple partners. Math. Oper. Res. 13(4):619–628.Link, Google Scholar
• [9] Dilworth RP (1990) Lattices with unique irreducible decompositions. Bogart KP, Freese R, Kung JPS, eds. The Dilworth Theorems, Contemporary Mathematicians (Birkhäuser, Boston), 93–99.Crossref, Google Scholar
• [10] Echenique F (2007) Counting combinatorial choice rules. Games Econom. Behav. 58(2):231–245.Crossref, Google Scholar
• [11] Echenique F, Oviedo J (2006) A theory of stability in many-to-many matching markets. Theoret. Econom. 1(2):233–273.Google Scholar
• [12] Edelman PH, Jamison RE (1985) The theory of convex geometries. Geometriae Dedicata 19(3):247–270.Crossref, Google Scholar
• [13] En C, Faenza Y (2025) Non-distributive lattices, stable matchings, and linear optimization. Megow N, Basu A, eds. Integer Programming Combin. Optim. 26th Internat. Conf. IPCO 2025 Proc. (Springer-Verlag, Berlin), 228–241.Google Scholar
• [14] Faenza Y, Zhang X (2023) Affinely representable lattices, stable matchings, and choice functions. Math. Programming 197(2):721–760.Crossref, Google Scholar
• [15] Faenza Y, Foussoul A, He C (2024) Two-stage stochastic stable matching. Vygen J, Byrka J, eds. Integer Programming Combin. Optim. 25th Internat. Conf. IPCO 2024 Proc. (Springer-Verlag, Berlin), 154–167.Google Scholar
• [16] Faenza Y, Mourtos I, Samaris M, Sethuraman J (2021) (Un)stable matchings with blocking costs. Oper. Res. Lett. 49(5):655–662.Crossref, Google Scholar
• [17] Fleiner T (2000) Stable and crossing structures. PhD thesis, Technische Universiteit Eindhoven, Eindhoven, Netherlands.Google Scholar
• [18] Fleiner T (2001) A matroid generalization of the stable matching polytope. Aardal K, Gerards B, eds. Proc. 8th Internat. Conf. Integer Programming Combin. Optim. (Springer-Verlag, Berlin), 105–114.Google Scholar
• [19] Fleiner T, Kamiyama N (2016) A matroid approach to stable matchings with lower quotas. Math. Oper. Res. 41(2):734–744.Link, Google Scholar
• [20] Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.Crossref, Google Scholar
• [21] Garg VK (2015) Introduction to Lattice Theory with Computer Science Applications (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• [22] Gusfield D, Irving RW (1989) The Stable Marriage Problem: Structure and Algorithms (MIT Press, Cambridge, MA).Google Scholar
• [23] Hatfield JW, Milgrom PR (2005) Matching with contracts. Amer. Econom. Rev. 95(4):913–935.Crossref, Google Scholar
• [24] Hitsch GJ, Hortaçsu A, Ariely D (2010) Matching and sorting in online dating. Amer. Econom. Rev. 100(1):130–163.Crossref, Google Scholar
• [25] Immorlica N, Echenique F, Vazirani VV (2023) Online and Matching-Based Market Design (Cambridge University Press, Cambridge, UK).Google Scholar
• [26] Irving RW, Leather P, Gusfield D (1987) An efficient algorithm for the “optimal” stable marriage. J. ACM 34(3):532–543.Crossref, Google Scholar
• [27] Iwata S, Yokoi Y (2020) Finding a stable allocation in polymatroid intersection. Math. Oper. Res. 45(1):63–85.Link, Google Scholar
• [28] Karp RM (2009) Reducibility among combinatorial problems. Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art (Springer, Berlin), 219–241.Google Scholar
• [29] Király T, Pap J (2008) Total dual integrality of Rothblum’s description of the stable-marriage polyhedron. Math. Oper. Res. 33(2):283–290.Link, Google Scholar
• [30] Knuth DE (1976) Mariages stables et leurs relations avec d’autres problems combinatoires (Les Presses de l’Université de Montréal, Montreal).Google Scholar
• [31] Konishi H, Ünver MU (2006) Credible group stability in many-to-many matching problems. J. Econom. Theory 129(1):57–80.Crossref, Google Scholar
• [32] Korte B, Schrader R, Lovász L (2012) Greedoids, Algorithms and Combinatorics, vol. 4 (Springer Science & Business Media, New York).Google Scholar
• [33] Manlove D (2013) Algorithmics of Matching Under Preferences, vol. 2 (World Scientific, Singapore).Crossref, Google Scholar
• [34] Merckx K (2019) Optimization and realizability problems for convex geometries. PhD thesis, Université Libre de Bruxelles, Brussels.Google Scholar
• [35] Reynolds JC (1970) Transformational systems and the algebraic structure of atomic formulas. Machine Intelligence 5(1):135–152.Google Scholar
• [36] Roth AE (1984) Stability and polarization of interests in job matching. Econometrica 52(1):47–58.Crossref, Google Scholar
• [37] Roth AE, Sotomayor M (1992) Two-sided matching. Aumann R, Hart S, eds. Handbook of Game Theory with Economic Applications, vol. 1 (Elsevier, Amsterdam), 485–541.Crossref, Google Scholar
• [38] Rothblum UG (1992) Characterization of stable matchings as extreme points of a polytope. Mathematical Programming. 54(1-3):57–67. Crossref, Google Scholar
• [39] Sönmez T, Ünver MU (2010) Course bidding at business schools. Internat. Econom. Rev. 51(1):99–123.Crossref, Google Scholar
• [40] Vande Vate JH (1989) Linear programming brings marital bliss. Oper. Res. Lett. 8(3):147–153.Crossref, Google Scholar
• [41] Wang X, Agatz N, Erera A (2018) Stable matching for dynamic ride-sharing systems. Transportation Sci. 52(4):850–867.Link, Google Scholar
• [42] Yang Y-Y (2020) Rationalizable choice functions. Games Econom. Behav. 123(1):120–126.Crossref, Google Scholar