Computing Stable Matchings under Complementarities and Preference Misalignment

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Computing Stable Matchings under Complementarities and Preference Misalignment

# 概要
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…

# 原典
https://arxiv.org/abs/2610.06337

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。