Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.17067 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912204875366400 |
|---|---|
| author | Karzanov, Alexander V. |
| author_facet | Karzanov, Alexander V. |
| contents | 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 consistency, 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 consequences, one can obtain a ``compact'' affine representation of stable matchings and efficiently solve some related problems.
Keywords: bipartite graph, choice function, linear preferences, stable matching, affine representation, sequential choice |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_17067 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Stable matchings, choice functions, and linear orders Karzanov, Alexander V. Combinatorics 91C02, 91C78 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 consistency, 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 consequences, one can obtain a ``compact'' affine representation of stable matchings and efficiently solve some related problems. Keywords: bipartite graph, choice function, linear preferences, stable matching, affine representation, sequential choice |
| title | Stable matchings, choice functions, and linear orders |
| topic | Combinatorics 91C02, 91C78 |
| url | https://arxiv.org/abs/2408.17067 |