Metraipolis › archive › dc_1b0bb8d33cc2

On splitting properties of the stability problem with integer choice functions — arXiv:2609.24581

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.24581
License (as archived)
CC0-1.0
Archived
2026-10-09T21:49:51.951Z
SHA-256 of the archived text
bb3848b74b9e1f64c848aee6e0ada29e986747cffda605fd71098f0997e9aee9
Stable URL of this page
https://metraipolis.com/documento/dc_1b0bb8d33cc2

How to cite

On splitting properties of the stability problem with integer choice functions — arXiv:2609.24581 — arXiv (en), https://arxiv.org/abs/2609.24581 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1b0bb8d33cc2 (Metraipolis archive dc_1b0bb8d33cc2, sha256 bb3848b74b9e1f64c848aee6e0ada29e986747cffda605fd71098f0997e9aee9)
BibTeX
@misc{dc1b0bb8d33cc2,
  title = {On splitting properties of the stability problem with integer choice functions — arXiv:2609.24581},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.24581},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1b0bb8d33cc2; sha256 bb3848b74b9e1f64c848aee6e0ada29e986747cffda605fd71098f0997e9aee9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24581. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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)\in{\mathbb Z}_+$ of edges $e\in E$, and for each vertex (``agent'') $v\in 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 ${\mathbb Z}_+^{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\in{\mathbb Z}_+^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

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.24581 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T21:26:41.156Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).