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

[2J5-GS-5-01] ソーシャルネットワーク上での両方向マッチングにおける公平性と効率性

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

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

両方向マッチングは, 学校選択制や研修医配属などの実世界の様々な場面で応用され, 多くの研究が行われているが, その基本的な前提に基づくと，効率性と公平性が両立しないという問題を抱えている. 特に，既知の不可能性定理の結果は, いかなる学生も他の学生に対して妥当な嫉妬を抱き得るという前提に基づいている. しかし, 実際には, 知り合い（隣人）に対してのみ妥当な嫉妬を抱き得ると考えることが自然な場合がある. そのため，隣人への嫉妬が存在しない性質を局所公平性として定義することが，竹島らによって提案されている．ここで，隣人関係は無向グラフで表現することができる．本研究では, このグラフの構造を制限することによって，公平性と効率性のトレードオフが改善できるかどうかを明らかにする. 特に, 木幅を制限したグラフに対して, パレート効率性を満たすメカニズムによって達成可能な局所公平性の度合いを明らかにする.