2024-03-29T18:07:22Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000917822024-03-29T05:26:34Z01164:02592:07086:07157
安定結婚問題における最大最適選好マッチングの頂点集合の一意性jpnhttp://id.nii.ac.jp/1001/00091766/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=91782&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Information Processing Society of Japan九州大学九州大学九州大学九州大学平川瑞樹山内由紀子来嶋秀治山下雅史本稿では安定結婚問題における最適選好マッチングの解構造ついて考える.安定結婚問題の入力は,男性集合と女性集合および各人の選好順序からなる.本稿では,男性の人数と女性の人数が異なる場合を許し,選好順序は全順序制約を満たす不完全リストとする.最適選好マッチングとは,あるマッチングMよりも多くの人々に好まれるマッチングM′が存在しないようなマッチングMのことであり,安定マッチングの緩和概念として知られる.本稿では,特に最適選好マッチングのサイズに着目した議論を行う.具体的には,最大最適選好マッチングを構成する男女はマッチングによらず一意であることを示す.また最適選好マッチングを構成する頂点集合の包含関係に関する半順序構造について考察する.AN1009593X研究報告アルゴリズム(AL)2013-AL-14419142013-05-102013-04-24