caa a22 4500 477048684 CHVBK 20180405111336.0 cr unu---uuuuu 170330e19960601xx s 000 0 eng 10.1007/BF01247099 doi (NATIONALLICENCE)springer-10.1007/BF01247099 Canonical monotone decompositions of fractional stable matchings [Elektronische Daten] [Hernán Abeledo, Yosef Blum, Uriel Rothblum] This paper continues recent work that introduced algebraic methods for studying the stable marriage problem of Gale and Shapley [1962]. Vande Vate [1989] and Rothblum [1992] identified a set of linear inequalities which define a polytope whose extreme points correspond to the stable matchings. Points in this polytope are called fractional stable matchings. Here we identify a unique representation of fractional stable matchings as a convex combination of stable matchings that are arrangeable in a man-decreasing order. We refer to this representation and to a dual one, in terms of woman-decreasing order, as the canonical monotone representations. These representations can be interpreted as time-sharing stable matchings where particular stable matchings are used at each time-instance but the scheduled stable matchings are (occasionally) switched over time. The new representations allow us to extend, in a natural way, the lattice structure of the set of stable matchings to the set of all fractional stable matchings. Physica-Verlag, 1996 Abeledo Hernán Department of Operations Research, The George Washington University, 20052, USA aut Blum Yosef Faculty of Industrial Engineering and Management Technion, Israel Institute of Technology, 32000, Technion City, Haifa, Israel aut Rothblum Uriel Faculty of Industrial Engineering and Management Technion, Israel Institute of Technology, 32000, Technion City, Haifa, Israel aut International Journal of Game Theory Physica-Verlag 25/2(1996-06-01), 161-176 0020-7276 25:2<161 1996 25 182 https://doi.org/10.1007/BF01247099 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01247099 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Abeledo Hernán Department of Operations Research, The George Washington University, 20052, USA aut NATIONALLICENCE 700 1- Blum Yosef Faculty of Industrial Engineering and Management Technion, Israel Institute of Technology, 32000, Technion City, Haifa, Israel aut NATIONALLICENCE 700 1- Rothblum Uriel Faculty of Industrial Engineering and Management Technion, Israel Institute of Technology, 32000, Technion City, Haifa, Israel aut NATIONALLICENCE 773 0- International Journal of Game Theory Physica-Verlag 25/2(1996-06-01), 161-176 0020-7276 25:2<161 1996 25 182 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer