Stable Matchings, Choice Functions, and Linear Orders

We consider a model of stable edge sets (“matchings”) in a bipartite graph $$G = (V,E)$$ where the preferences for vertices of one side (“firms”) are given via choice functions subject to standard axioms of consistency, substitutability and cardinal monotonicity, whereas the preferences for the vertices of the other side (“workers’) via linear orders. For such a model, we present a combinatorial description of the structure of rotations and develop an algorithm to construct the poset of rotations, in time $$O(|{\kern 1pt} E{\kern 1pt} {{|}^{2}})$$ (including “oracle calls”). As consequences, we obtain a “compact” affine representation of stable matchings and efficiently solve some related problems.