Metraipolis › archive › dc_a43856144d89

Computing Stable Matchings under Complementarities and Preference Misalignment — arXiv:2610.06337

Source
arXiv
Original
https://arxiv.org/abs/2610.06337
License (as archived)
CC0-1.0
Archived
2026-10-06T05:29:26.536Z
SHA-256 of the archived text
83905fb0780502b1b95b365d8adad4f35ae77bd8db9c8fae77643f30c509a5f3
Stable URL of this page
https://metraipolis.com/documento/dc_a43856144d89

How to cite

Computing Stable Matchings under Complementarities and Preference Misalignment — arXiv:2610.06337 — arXiv, https://arxiv.org/abs/2610.06337 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a43856144d89 (Metraipolis archive dc_a43856144d89, sha256 83905fb0780502b1b95b365d8adad4f35ae77bd8db9c8fae77643f30c509a5f3)
BibTeX
@misc{dca43856144d89,
  title = {Computing Stable Matchings under Complementarities and Preference Misalignment — arXiv:2610.06337},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.06337},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a43856144d89; sha256 83905fb0780502b1b95b365d8adad4f35ae77bd8db9c8fae77643f30c509a5f3},
  year = {2026}
}

Archived text

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

We study many-to-one, two-sided stable matching problems in which preferences are complementary and firms and workers may rank the same allocation differently. Here a coalition is a group of workers that can be jointly matched with a firm. With complementary preferences, a stable matching need not exist. We show that a stable matching exists for every instance when two conditions hold. The first requires each firm to have an anchor worker who is included in every feasible coalition that can be matched with that firm. The second is Transitive Alignment, which means there must be an overall ranking across different coalitions that is consistent with the workers' preferences. We propose CDAR (Combinatorial Deferred Acceptance with Reproposals), a Deferred Acceptance-style algorithm that permits reproposals, and prove its finite-time convergence and its output of a stable matching by constructing an $N$-digit potential function. Moreover, we show that, under strict preferences, the output of CDAR is Pareto optimal among stable matchings. The proposed framework naturally captures applications such as vehicle-route assignment for traffic safety and the misaligned interests of labor and management in wage negotiation.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2610.06337 — 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-06T05:25:35.318Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).