Stable matchings, choice functions, and linear orders

Alexander V. Karzanov

Published 2024-08-30Version 1

We consider a model of stable edge sets (``matchings'') in a bipartite graph $G=(V,E)$ in which the preferences for vertices of one side (``firms'') are given via choice functions subject to standard axioms of consistence, 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(|E|^2)$ (including oracle calls). As a consequence, one can obtain a ``compact'' affine representation of stable matchings and efficiently solve some related problems. (The paper is written in Russian.)