安定結婚問題における最大最適選好マッチングの頂点集合の一意性  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

本稿では安定結婚問題における最適選好マッチングの解構造ついて考える.安定結婚問題の入力は,男性集合と女性集合および各人の選好順序からなる.本稿では,男性の人数と女性の人数が異なる場合を許し,選好順序は全順序制約を満たす不完全リストとする.最適選好マッチングとは,あるマッチングMよりも多くの人々に好まれるマッチングM′が存在しないようなマッチングMのことであり,安定マッチングの緩和概念として知られる.本稿では,特に最適選好マッチングのサイズに着目した議論を行う.具体的には,最大最適選好マッチングを構成する男女はマッチングによらず一意であることを示す.また最適選好マッチングを構成する頂点集合の包含関係に関する半順序構造について考察する.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 2013-AL-144(19), 1-4, 2013-05-10

    Information Processing Society of Japan (IPSJ)

Codes

  • NII Article ID (NAID)
    110009579695
  • NII NACSIS-CAT ID (NCID)
    AN1009593X
  • Text Lang
    JPN
  • Article Type
    Technical Report
  • ISSN
    09196072
  • Data Source
    NII-ELS  IPSJ 
Page Top