On one generalization of stable allocations in a two-sided market

In the stable allocation problem on a two-sided market introduced and studied by Baiou and Balinski in the early 2000’s, one is given a bipartite graph $G=(V,E)$ with capacities $b$ on the edges (contracts'') and quotas $q$ on the vertices (agents’‘). Each vertex $v\in V$ is endowed with a linear order on the set $E_v$ of edges incident to $v$, which generates preference relations among functions (contract intensities'') on $E_v$, giving rise to a model of \it{stable allocations} for $G$. This is a special case of Alkan-Gale's stability model for a bipartite graph with edge capacities in which, instead of linear orders, the preferences of each agent’’ $v$ are given via a choice function that acts on the box $\{z\in {\mathbb{R}}_{+}^{E_v}\text{\hspace{0.17em}⁣}:z(e)\le b(e),e\in E_v\}$ or a closed subset in it and obeys the (well motivated) axioms of consistence, substitutability and cardinal monotonicity. By central results in Alkan-Gale’s theory, the set of stable assignments generated by such choice functions is nonempty and forms a distributive lattice. In this paper, being in frameworks of Alkan-Gale’s model and generalizing the stable allocation one, we consider the situation when the preferences of agents'' of one side (workers’‘) are given via linear orders, whereas the ones of the other side (firms'') via integer-valued choice functions subject to the three axioms as above, thus introducing the model of \it{generalized allocations}, or g-allocations for short. Our main aims are to characterize and efficiently construct rotations, functions on $E$ associated with immediately preceding relations in the lattice $(S,\prec)$ of stable g-allocations, and to estimate the complexity of constructing a poset generated by rotations for which the lattice of closed functions is isomorphic to $(S,\prec)$, obtaining a compact’’ representation of the latter.