On splitting properties of the stability problem with integer choice functions
Abstract
We consider the integer version of Alkan--Gale's model on stability in a two-sided market, called the stable generalized allocation one. It is given by a triple (G,b,C), where G=(V,E) is a finite bipartite graph with nonnegative integer capacities b(e)∈ℤ+ of edges e∈ E, and for each vertex (``agent'') v∈ V, the preferences on the set Ev of its incident edges depend on a choice function Cv. The latter acts on the set of vectors in ℤ+Ev bounded by the capacities and obeys the standard axioms of substitutability and size monotonicity. Alkan--Gale's prominent theorem implies that the stability problem in this case always has a stable solution x∈ℤ+E and, moreover, the set cal SG,b,C of these solutions (``stable generalized allocations'') forms a distributive lattice. However, this lattice is rather intricate to construct and work with, and we wonder whether it can be represented via a ``simpler'' stability model. Answering this issue, we arrange a sort of splitting techniques to embed cal SG,b,C, as a sublattice, in the lattice of stable matchings and, more compactly, in the lattice of stable allocations (as in Baiou--Balinski's stability model). This generalizes Fleiner's result on a detachment in the special case with all-unit capacities. Keywords: stable marriage, stable allocation, choice function, rotation, distributive lattice, poset representation
Related
- Indefinite integrals of Bessel and Struve functions with half-integer indices, and incomplete gamma functions with integer indices, all multiplied by Exp(−ax2) and divided by powers
- Integer points for iterated Weierstrass elliptic functions
- Completing the Existence Problem for Integer Relative Heffter Arrays Hk(n;k)
- Non-convex integer programming: a deterministic solution method of the large block sale problem
- Splitting Algorithms Using Pairs Monotonicity to Solve the Sum of Two Non-monotone Operators Problem
BibTeX
@misc{karzanov2026splitting,
title = {{On splitting properties of the stability problem with integer choice functions}},
author = {Alexander V. Karzanov},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.24581},
eprint = {2609.24581},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24581},
}
RIS
TY - UNPB
TI - On splitting properties of the stability problem with integer choice functions
AU - Alexander V. Karzanov
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.24581
UR - https://arxiv.org/abs/2609.24581
AB - We consider the integer version of Alkan--Gale's model on stability in a two-sided market, called the stable generalized allocation one. It is given by a triple (G,b,C), where G=(V,E) is a finite bipartite graph with nonnegative integer capacities b(e)∈ℤ_+ of edges e∈ E, and for each vertex (``agent'') v∈ V, the preferences on the set E_v of its incident edges depend on a choice function C_v. The latter acts on the set of vectors in ℤ_+^E_v bounded by the capacities and obeys the standard axioms of substitutability and size monotonicity. Alkan--Gale's prominent theorem implies that the stability problem in this case always has a stable solution x∈ℤ_+^E and, moreover, the set cal S_G,b,C of these solutions (``stable generalized allocations'') forms a distributive lattice. However, this lattice is rather intricate to construct and work with, and we wonder whether it can be represented via a ``simpler'' stability model. Answering this issue, we arrange a sort of splitting techniques to embed cal S_G,b,C, as a sublattice, in the lattice of stable matchings and, more compactly, in the lattice of stable allocations (as in Baiou--Balinski's stability model). This generalizes Fleiner's result on a detachment in the special case with all-unit capacities. Keywords: stable marriage, stable allocation, choice function, rotation, distributive lattice, poset representation
ER -