[2J5-GS-5] エージェント：

[2J5-GS-5-02] 両方向マッチングにおける局所公平性と束構造

〇黒木 歩¹、木村 慧¹、竹島 遼太¹、横尾 真¹ (1. 九州大学)

キーワード：メカニズムデザイン、両方向マッチング、グラフ理論

安定結婚問題や大学入学，研修医の配属などの両方向マッチング問題では，Gale-Shapleyアルゴリズムを用いることにより，片側最適なマッチングを多項式時間で求められることが知られている．ここで，片側最適なマッチングが存在するという事実は，安定マッチング集合が束と呼ばれる数学的な構造を持つことから導かれる．一方で，実際のマッチング市場では，知り合い（隣人）にのみ嫉妬を抱くことがより自然であると考えられる場合がある．そのため，隣人への嫉妬が存在しない性質を局所公平性として定義することが，竹島らによって提案されている．ここで，隣人関係は無向グラフで表現することができる．本論文では，このグラフの構造やマッチング参加者の選好への制限が，局所公平性を満たすマッチング集合の束構造の保有性について与える影響を議論する．