2025/04/28 by Alexander V. Karzanov, Karzanov, Alexander V. · 1 citation
Economics, Econometrics and Finance · Decision Sciences · #Game Theory and Voting Systems #Auction Theory and Applications #Economic theories and models
paper · pdf · doi:10.48550/arxiv.2504.19978
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∈ V is endowed with a linear order on the set Ev of edges incident to v, which generates preference relations among functions (``contract intensities'') on Ev, giving rise to a model of \itstable 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∈\mathbb R+Ev\colon z(e)≤ b(e), e∈ Ev\ 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 \itgeneralized 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.