パートナーとして容認できないメンバーを許す分散安定結婚問題の一考察

機関リポジトリ Web Site

書誌事項

タイトル別名
  • A Study on Distributed Stable Marriage Problem with Unacceptable Partners
  • パートナー ト シテ ヨウニン デキナイ メンバー オ ユルス ブンサン アンテイ ケッコン モンダイ ノ イチ コウサツ

この論文をさがす

説明

安定結婚問題は、男女n人ずつの二つの集合と、各メンバーが異性を好きな順にならべたプリファレンスリストを与えられたときに、安定なn組のペアを求める問題である。本問題に対しては、安定マッチングを求める多項式時間アルゴリズムの存在が知られている。また、この問題の条件緩和として、プリファレンスリストに異性全体を書かないことを許す場合や、異性の希望順位に同順位を許す場合などについて検討され、それぞれの場合で安定マッチングが得られる事が知られている。本研究では、安定結婚問題の自律分散環境への適用に始まり、参加メンバーの自律的な判断により、現在の安定マッチングから異なる安定マッチングへ組合せの構成を変化することが可能であるマッチング再構成と呼ばれる安定マッチングの遷移手法の提案を行った。本稿では、分散安定結婚問題の実問題への適用を考慮し、パートナーとして受け入れることができないメンバーとペアにならないことを許した場合、分散Gale-Shapleyアルゴリズムによって安定マッチングを得ることができるか、また、マッチング再構成によって任意の安定マッチングから異なる安定マッチングへ導くことができるかについて考察する。@@@Instance of the original stable marriage problem consists of men group and women group having n members each other.men and women. Each member submits a preference list in which he/she writes all the members of the opposite sex in the strict order. The problem is known to be solved in polynomial time. Considering practical applications, relaxations for the preference lists have been introduced. In the previous works, it has been proposed that stable marriage problem was applied to autonomous distributed environment, and introduced autonomous mechanism for exchanging partners, called matching reconstruction. In this paper, I consider, one of relaxations that to allow unacceptable partners.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ