{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T06:42:39Z","timestamp":1773816159243,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,6,11]],"date-time":"2022-06-11T00:00:00Z","timestamp":1654905600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,6,11]],"date-time":"2022-06-11T00:00:00Z","timestamp":1654905600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2046146"],"award-info":[{"award-number":["2046146"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"DOI":"10.1007\/s10107-022-01838-z","type":"journal-article","created":{"date-parts":[[2022,6,11]],"date-time":"2022-06-11T10:02:42Z","timestamp":1654941762000},"page":"721-760","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Affinely representable lattices, stable matchings, and choice functions"],"prefix":"10.1007","volume":"197","author":[{"given":"Yuri","family":"Faenza","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6535-5449","authenticated-orcid":false,"given":"Xuan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,11]]},"reference":[{"issue":"2","key":"1838_CR1","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1257\/000282805774670167","volume":"95","author":"A Abdulkadiro\u011flu","year":"2005","unstructured":"Abdulkadiro\u011flu, A., Pathak, P.A., Roth, A.E.: The New York City high school match. Am. Econ. Rev. 95(2), 364\u2013367 (2005)","journal-title":"Am. Econ. Rev."},{"issue":"3","key":"1838_CR2","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1257\/000282803322157061","volume":"93","author":"A Abdulkadiro\u011flu","year":"2003","unstructured":"Abdulkadiro\u011flu, A., S\u00f6nmez, T.: School choice: a mechanism design approach. Am Econ. Rev. 93(3), 729\u2013747 (2003)","journal-title":"Am Econ. Rev."},{"issue":"5","key":"1838_CR3","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1109\/TAC.1981.1102777","volume":"26","author":"M Aizerman","year":"1981","unstructured":"Aizerman, M., Malishevski, A.: General theory of best variants choice: some aspects. IEEE Trans. Auto. Control 26(5), 1030\u20131040 (1981)","journal-title":"IEEE Trans. Auto. Control"},{"issue":"1","key":"1838_CR4","first-page":"99","volume":"6","author":"A Alkan","year":"2001","unstructured":"Alkan, A.: On preferences over subsets and the lattice structure of stable matchings. Rev. Econ. Des. 6(1), 99\u2013111 (2001)","journal-title":"Rev. Econ. Des."},{"issue":"4","key":"1838_CR5","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/s001990100179","volume":"19","author":"A Alkan","year":"2002","unstructured":"Alkan, A.: A class of multipartner matching markets with a strong lattice structure. Econ. Theory 19(4), 737\u2013746 (2002)","journal-title":"Econ. Theory"},{"issue":"3","key":"1838_CR6","doi-asserted-by":"publisher","first-page":"1857","DOI":"10.1137\/17M1116684","volume":"32","author":"M Aprile","year":"2018","unstructured":"Aprile, M., Cevallos, A., Faenza, Y.: On 2-level polytopes arising in combinatorial settings. SIAM J. Dis. Math. 32(3), 1857\u20131886 (2018)","journal-title":"SIAM J. Dis. Math."},{"issue":"5","key":"1838_CR7","doi-asserted-by":"publisher","first-page":"2050","DOI":"10.1257\/aer.103.5.2050","volume":"103","author":"O Ayg\u00fcn","year":"2013","unstructured":"Ayg\u00fcn, O., S\u00f6nmez, T.: Matching with contracts: comment. Am. Econ. Rev. 103(5), 2050\u201351 (2013)","journal-title":"Am. Econ. Rev."},{"key":"1838_CR8","doi-asserted-by":"crossref","unstructured":"Ayg\u00fcn, O., Turhan, B.: Dynamic reserves in matching markets: theory and applications. Available at SSRN 2743000 (2016)","DOI":"10.2139\/ssrn.2743000"},{"issue":"1\u20133","key":"1838_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0166-218X(99)00203-6","volume":"101","author":"M Ba\u00efou","year":"2000","unstructured":"Ba\u00efou, M., Balinski, M.: Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry). Dis. Appl. Math. 101(1\u20133), 1\u201312 (2000)","journal-title":"Dis. Appl. Math."},{"issue":"3","key":"1838_CR10","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s101070050004","volume":"87","author":"M Ba\u00efou","year":"2000","unstructured":"Ba\u00efou, M., Balinski, M.: The stable admissions polytope. Math. program. 87(3), 427\u2013439 (2000)","journal-title":"Math. program."},{"issue":"3","key":"1838_CR11","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/j.tcs.2007.02.050","volume":"379","author":"V Bansal","year":"2007","unstructured":"Bansal, V., Agrawal, A., Malhotra, V.S.: Polynomial time algorithm for an optimal stable assignment with multiple partners. Theor. Comput. Sci. 379(3), 317\u2013328 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1838_CR12","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1215\/S0012-7094-37-00334-X","volume":"3","author":"G Birkhoff","year":"1937","unstructured":"Birkhoff, G.: Rings of sets. Duke Math. J. 3(3), 443\u2013454 (1937)","journal-title":"Duke Math. J."},{"issue":"4","key":"1838_CR13","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1287\/moor.13.4.619","volume":"13","author":"C Blair","year":"1988","unstructured":"Blair, C.: The lattice structure of the set of stable matchings with multiple partners. Math. Oper. Res. 13(4), 619\u2013628 (1988)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1838_CR14","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1257\/mic.20150236","volume":"9","author":"CP Chambers","year":"2017","unstructured":"Chambers, C.P., Yenmez, M.B.: Choice and matching. Am. Econ. J. Microecon. 9(3), 126\u201347 (2017)","journal-title":"Am. Econ. J. Microecon."},{"issue":"6","key":"1838_CR15","doi-asserted-by":"publisher","first-page":"1144","DOI":"10.1137\/S0097539791278376","volume":"25","author":"J Cheriyan","year":"1996","unstructured":"Cheriyan, J., Hagerup, T., Mehlhorn, K.: An $$o(n^3)$$-time maximum-flow algorithm. SIAM J. Comput. 25(6), 1144\u20131170 (1996)","journal-title":"SIAM J. Comput."},{"key":"1838_CR16","doi-asserted-by":"crossref","unstructured":"Do\u011fan, B., Do\u011fan, S., Y\u0131ld\u0131z, K.: On capacity-filling and substitutable choice rules. Math. Oper. Res. (2021)","DOI":"10.1287\/moor.2021.1128"},{"issue":"2","key":"1838_CR17","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.geb.2006.03.009","volume":"58","author":"F Echenique","year":"2007","unstructured":"Echenique, F.: Counting combinatorial choice rules. Games Econ. Behav. 58(2), 231\u2013245 (2007)","journal-title":"Games Econ. Behav."},{"issue":"8","key":"1838_CR18","doi-asserted-by":"publisher","first-page":"2679","DOI":"10.1257\/aer.20130929","volume":"105","author":"F Echenique","year":"2015","unstructured":"Echenique, F., Yenmez, M.B.: How to control controlled school choice. Am. Econ. Rev. 105(8), 2679\u201394 (2015)","journal-title":"Am. Econ. Rev."},{"key":"1838_CR19","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-030-73879-2_7","volume-title":"Integer Programming and Combinatorial Optimization","author":"Y Faenza","year":"2021","unstructured":"Faenza, Y., Zhang, X.: Affinely representable lattices, stable matchings, and choice functions. In: Singh, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization, pp. 89\u2013103. Springer International Publishing, Cham (2021)"},{"issue":"2","key":"1838_CR20","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0165-4896(03)00074-X","volume":"46","author":"T Fleiner","year":"2003","unstructured":"Fleiner, T.: On the stable b-matching polytope. Math. Social Sci. 46(2), 149\u2013158 (2003)","journal-title":"Math. Social Sci."},{"issue":"1","key":"1838_CR21","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Monthly 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Monthly"},{"key":"1838_CR22","doi-asserted-by":"crossref","unstructured":"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\u2013245 (2020)","DOI":"10.1145\/3350755.3400235"},{"key":"1838_CR23","unstructured":"Gusfield, D., Irving, R.W.: The stable marriage problem: structure and algorithms. MIT press (1989)"},{"issue":"2","key":"1838_CR24","doi-asserted-by":"publisher","first-page":"325","DOI":"10.3982\/TE1135","volume":"8","author":"IE Hafalir","year":"2013","unstructured":"Hafalir, I.E., Yenmez, M.B., Yildirim, M.A.: Effective affirmative action in school choice. Theor. Econ. 8(2), 325\u2013363 (2013)","journal-title":"Theor. Econ."},{"issue":"4","key":"1838_CR25","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1257\/0002828054825466","volume":"95","author":"JW Hatfield","year":"2005","unstructured":"Hatfield, J.W., Milgrom, P.R.: Matching with contracts. Am. Econ. Rev. 95(4), 913\u2013935 (2005)","journal-title":"Am. Econ. Rev."},{"issue":"3","key":"1838_CR26","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1137\/0215048","volume":"15","author":"RW Irving","year":"1986","unstructured":"Irving, R.W., Leather, P.: The complexity of counting stable marriages. SIAM J. Comput. 15(3), 655\u2013667 (1986)","journal-title":"SIAM J. Comput."},{"key":"1838_CR27","doi-asserted-by":"crossref","unstructured":"Irving, R.W., Leather, P., Gusfield, D.: An efficient algorithm for the \u201coptimal\u201d stable marriage. J. ACM (JACM) 34(3), 532\u2013543 (1987)","DOI":"10.1145\/28869.28871"},{"issue":"1","key":"1838_CR28","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1257\/aer.20101552","volume":"105","author":"Y Kamada","year":"2015","unstructured":"Kamada, Y., Kojima, F.: Efficient matching under distributional constraints: theory and applications. Am. Econ. Rev. 105(1), 67\u201399 (2015)","journal-title":"Am. Econ. Rev."},{"key":"1838_CR29","doi-asserted-by":"crossref","unstructured":"Kelso\u00a0Jr, A.S., Crawford, V.P.: Job matching, coalition formation, and gross substitutes. Econ. J. Econ. Soc, pp. 1483\u20131504 (1982)","DOI":"10.2307\/1913392"},{"key":"1838_CR30","unstructured":"Knuth, D.E.: Marriages stables. Technical report (1976)"},{"key":"1838_CR31","doi-asserted-by":"crossref","unstructured":"Manlove, D.: Algorithmics of Matching Under Preferences, vol.\u00a02. World Scientific (2013)","DOI":"10.1142\/8591"},{"issue":"2","key":"1838_CR32","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.mathsocsci.2003.07.002","volume":"47","author":"R Mart\u00ednez","year":"2004","unstructured":"Mart\u00ednez, R., Mass\u00f3, J., Neme, A., Oviedo, J.: An algorithm to compute the full set of many-to-many stable matchings. Math. Social Sci. 47(2), 187\u2013210 (2004)","journal-title":"Math. Social Sci."},{"issue":"7","key":"1838_CR33","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/362619.362631","volume":"14","author":"DG McVitie","year":"1971","unstructured":"McVitie, D.G., Wilson, L.B.: The stable marriage problem. Commun. ACM 14(7), 486\u2013490 (1971)","journal-title":"Commun. ACM"},{"key":"1838_CR34","doi-asserted-by":"crossref","unstructured":"Nguyen, T., Vohra, R.: Stable matching with proportionality constraints. Oper. Res. (2019)","DOI":"10.1287\/opre.2019.1909"},{"issue":"11","key":"1838_CR35","doi-asserted-by":"publisher","first-page":"1268","DOI":"10.1287\/mnsc.22.11.1268","volume":"22","author":"JC Picard","year":"1976","unstructured":"Picard, J.C.: Maximal closure of a graph and applications to combinatorial problems. Manage. Sci. 22(11), 1268\u20131272 (1976)","journal-title":"Manage. Sci."},{"issue":"6","key":"1838_CR36","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1086\/261272","volume":"92","author":"AE Roth","year":"1984","unstructured":"Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92(6), 991\u20131016 (1984)","journal-title":"J. Polit. Econ."},{"key":"1838_CR37","doi-asserted-by":"crossref","unstructured":"Roth, A.E.: Stability and polarization of interests in job matching. Econ. J. Econ. Soc., pp. 47\u201357 (1984)","DOI":"10.2307\/1911460"},{"key":"1838_CR38","doi-asserted-by":"crossref","unstructured":"Roth, A.E.: On the allocation of residents to rural hospitals: a general property of two-sided matching markets. Econ. J. Econ. Soc., pp. 425\u2013427 (1986)","DOI":"10.2307\/1913160"},{"issue":"4","key":"1838_CR39","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1287\/moor.18.4.803","volume":"18","author":"AE Roth","year":"1993","unstructured":"Roth, A.E., Rothblum, U.G., Vande Vate, J.H.: Stable matchings, optimal assignments, and linear programming. Math. Oper. Res. 18(4), 803\u2013828 (1993)","journal-title":"Math. Oper. Res."},{"issue":"1\u20133","key":"1838_CR40","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01586041","volume":"54","author":"UG Rothblum","year":"1992","unstructured":"Rothblum, U.G.: Characterization of stable matchings as extreme points of a polytope. Math. Program. 54(1\u20133), 57\u201367 (1992)","journal-title":"Math. Program."},{"key":"1838_CR41","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency, vol.\u00a024. Springer Science & Business Media (2003)"},{"issue":"1","key":"1838_CR42","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF02187680","volume":"1","author":"RP Stanley","year":"1986","unstructured":"Stanley, R.P.: Two poset polytopes. Dis. Comput. Geometry 1(1), 9\u201323 (1986)","journal-title":"Dis. Comput. Geometry"},{"key":"1838_CR43","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.jet.2018.03.008","volume":"176","author":"K Tomoeda","year":"2018","unstructured":"Tomoeda, K.: Finding a stable matching under type-specific minimum quotas. J. Econ. Theory 176, 81\u2013117 (2018)","journal-title":"J. Econ. Theory"},{"issue":"3","key":"1838_CR44","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0167-6377(89)90041-2","volume":"8","author":"JHV Vate","year":"1989","unstructured":"Vate, J.H.V.: Linear programming brings marital bliss. Oper. Res. Lett. 8(3), 147\u2013153 (1989)","journal-title":"Oper. Res. Lett."},{"key":"1838_CR45","unstructured":"Zhang, X.: Two-sided matching markets: Models, Structures, and Algorithms. Ph.D. thesis, IEOR Department, Columbia University (2022)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01838-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01838-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01838-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:20:52Z","timestamp":1675704052000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01838-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,11]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1838"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01838-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,11]]},"assertion":[{"value":"31 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}