Stable Matchings, Choice Functions, and Linear Orders

A model of stable edge subsets (“matchings”) in a bipartite graph G = (V, E) is considered, in which preferences for vertices of one side (“firms”) are given by choice functions with standard properties of consistency, substitutability, and cardinal monotonicity, and preferences for vertices of the other side (“workers”) are given by linear orders. For such a model,we give a combinatorial description of the structure of rotations and propose an algorithm for constructing a rotation poset with a time complexity estimate O(|E|2) (including calls to oracles associated with choice functions). As a consequence, a “compact” affine representation of stable matchings can be obtained and related problems can be solved efficiently.