安定結婚問題における最適選好マッチングの端点集合族の性質

平川瑞樹, 山内由紀子, 来嶋秀治, 山下雅史

本稿では,安定結婚問題における最適選好マッチングの解構造について考察する.ただし,入力として与えられる選好リストは全順序制約付きの不完全リストを仮定する.最適選好マッチングとは,任意のマッチングと比較したときに人気で負けないマッチングであり,安定マッチングの緩和概念として知られる.最適選好マッチングを構成している男女を各要素とする集合族には (唯一の) 最小元が必ず存在することが知られていた.本研究では,その集合族には (唯一の) 最大元も必ず存在することがわかっている.本稿では,その集合族が積や和の操作に関して閉じていないことを示す.

安定結婚問題における最適選好マッチングの端点集合族の性質

Search this article

Description

Journal

Details 詳細情報について

Export

Report a problem