安定したルームメイト問題

数学、経済学、コンピュータサイエンス、特に組合せ論、ゲーム理論、アルゴリズムの分野において、安定ルームメイト問題( SRP ) は、偶数サイズの集合に対して安定的なマッチングを見つける問題です。マッチングとは、集合を互いに素なペア (「ルームメイト」) に分けることです。マッチングは、ルームメイトではない 2 つの要素がマッチングのもとで互いにルームメイトよりも好意的である場合に安定しています。安定ルームメイト問題では、「男性」と「女性」のクラス間だけでなく、任意の 2 つの要素間のマッチングが可能である点で、安定結婚問題とは異なります。

一般的には次のように述べられます。

安定ルームメイト問題 (SRP) の特定のインスタンスでは、2n 人の参加者のそれぞれが、他の参加者を厳密な優先順位でランク付けします。マッチングは、n 組の互いに素な参加者のペアの集合です。SRP のインスタンスのマッチングM は、 M内のパートナーよりも相手を好む 2 人の参加者xとyが存在しない場合に安定です。このようなペアはM をブロックする、またはMに関してブロッキング ペアであると言われます。

安定した結婚問題とは異なり、参加者とその好みの特定のセットでは安定したマッチングが存在しない場合があります。安定したペアリングが存在しない最小限の例として、順位が次の 4 人の人々A、B、C、Dを考えます。

A:(B,C,D)、B:(C,A,D)、C:(A,B,D)、D:(A,B,C)

このランキングでは、A、B、C のそれぞれが、誰かにとって最も好ましい人物です。どのソリューションでも、A、B、C のいずれか 1 つをD とペアにし、他の 2 つを互いにペアにする必要があります(たとえば、AD と BC)。ただし、D とペアになっている人の場合、別のメンバーが彼らを最も高く評価し、D のパートナーは D よりもこの別のメンバーを好みます。この例では、AC は AD よりも好ましいペアですが、残りの必要な BD のペアでも同じ問題が発生し、これらの参加者とその好みの安定したマッチングが存在しないことがわかります。

効率的なアルゴリズム (Irving 1985) は次のとおりです。このアルゴリズムは、問題のあらゆるインスタンスに対して、安定したマッチングが存在するかどうかを判断し、存在する場合は、そのようなマッチングを見つけます。適切なデータ構造を使用して、優先リストの必要な操作と回転の識別を実装する場合、 Irving のアルゴリズムの複雑度はO( n ² )です。

このアルゴリズムは 2 つのフェーズで構成されています。フェーズ 1 では、参加者は、安定結婚問題に対するGale-Shapley アルゴリズムと同様の方法で、互いにプロポーズします。各参加者は、他のメンバーを好みによって順序付けし、その結果、他の参加者の順序付けられたセットである好みリストが作成されます。次に、参加者はリスト上の各人に順番にプロポーズし、現在のプロポーズが拒否された場合は次の人に進みます。参加者は、すでに好みの人からプロポーズを受けている場合、プロポーズを拒否します。参加者は、後で好みのプロポーズを受けた場合も、以前に受け入れたプロポーズを拒否します。この場合、拒否された参加者は、リスト上の次の人にプロポーズし、プロポーズが再び受け入れられるまで続けます。いずれかの参加者が最終的に他のすべての参加者に拒否された場合、これは安定したマッチングが不可能であることを示します。それ以外の場合、フェーズ 1 は、各人が他のいずれかの人からのプロポーズを受けている状態で終了します。

2 人の参加者qとpについて考えます。q がpからの提案を保持している場合、qのリストからp以降のすべての参加者x を削除し、対称的に、削除された参加者xごとに、 xのリストからq を削除します。これにより、 q はpのリストの最初になり、pはq のリストの最後になります。これは、 qとx は、安定したマッチングのパートナーになることができないためです。結果として得られる削減された優先リストのセット全体をフェーズ 1 テーブルと呼びます。このテーブルでは、削減されたリストが空の場合、安定したマッチングはありません。それ以外の場合、フェーズ 1 テーブルは安定したテーブルです。安定したテーブルは、定義により、1 つ以上のリストからメンバーが削除された後の元のテーブルの優先リストのセットであり、次の 3 つの条件が満たされます (削減されたリストは、安定したテーブル内のリストを意味します)。

(i) p がqの縮小リストの最初である場合、かつその場合に限ります。qがpの縮小リストの最後である場合、かつその場合に限ります。
(ii) p がqの縮小リストに含まれていない場合、かつその場合に限ります。qがリストの最後の人物をpよりも好む場合、または、リストの最後の人物であるp がqよりも好む場合、かつその場合に限ります 。(iii) 縮小リストは空ではありません。

安定したテーブルには、残りの手順を正当化するために使用されるいくつかの重要なプロパティがあります。

1. 安定したテーブルは、フェーズ 1 テーブルのサブテーブルである必要があります。サブテーブルは、サブテーブルの優先リストがスーパーテーブルの優先リストであり、一部の個人が互いのリストから削除されているテーブルです。
2. どのような安定したテーブルでも、縮小されたリストにそれぞれ 1 人の個人が含まれている場合、各個人をそのリスト上の 1 人の人物とペアにすると、安定したマッチングが得られます。
3. 安定したルームメイト問題インスタンスに安定したマッチングがある場合、安定したテーブルのいずれかに安定したマッチングが含まれます。
4. 安定したテーブルの任意の安定したサブテーブル、特に 2 のように安定したマッチングを指定する任意の安定したサブテーブルは、安定したテーブル上の回転消去のシーケンスによって取得できます。

これらの回転除去は、アーヴィングのアルゴリズムのフェーズ 2 を構成します。

2 により、フェーズ 1 テーブルの各縮小リストに正確に 1 人の個人が含まれている場合、マッチングが行われます。

それ以外の場合、アルゴリズムはフェーズ 2 に入ります。安定したテーブルT内の回転は、( x ₀、y ₀ )、( x ₁、y ₁ )、...、( x _k-1、y _k-1 ) のシーケンスとして定義されます。ここで、 x _{i は}別個であり、y _{i は}x _iの縮小リストの最初であり(またはx _iはy _iの縮小リストの最後であり)、 y _i+1はx _iの縮小リストの 2 番目であり、i = 0、...、k-1 です。ここで、インデックスは k を法として取られます。したがって、少なくとも 2 つの個体を含む縮小リストを持つ安定したテーブルでは、このような回転が常に存在します。これを探すには、縮小リストに少なくとも 2 つの個体を含むようなp _{0から始めて、} q _{i+1 を}p _iのリストの 2 番目、 p _{i+1 を}q _i+1のリストの最後として再帰的に定義し、このシーケンスがp _{j を}繰り返すまで続けます。その時点で回転が見つかります。回転は、 ( p _j、q _j ) の最初の出現から始まり、最後の出現の 1 つ前のペアで終わるペアのシーケンスです。p _jまでのp _{iのシーケンスは、回転の}末尾と呼ばれます。この検索が行われる安定したテーブルであるという事実は、各p _iのリストに少なくとも 2 つの個体がある ことを保証します。

回転をなくすために、各iについて、 y _{i は}x _{i を}拒否し、x _{i が}y _i+1に提案するようにします。安定したテーブル特性 (i) と (ii) を復元するために、各iについて、 x _i-1の後継者はすべてy _iのリストから削除され、y _{i は}それらのリストから削除されます。これらの削除中に縮小されたリストが空になった場合、安定したマッチングは存在しません。それ以外の場合、新しいテーブルは再び安定したテーブルであり、各リストに正確に 1 つの個体が含まれているため既にマッチングが指定されているか、または見つけて除去する別の回転が残っているため、この手順が繰り返されます。

アルゴリズムのフェーズ 2 は次のように要約できます。

T =フェーズ1テーブル; while ( true ) { T内の回転rを識別します; Tからr を削除します; T内のリストが空になった場合はnullを返します; (安定したマッチングは存在できません) else if ( T内の縮小された各リストのサイズが1 )マッチングを返しますM = {{ x , y } | xとy はT内の互いのリストにあります} ; (これは安定したマッチングです) }    
  
         
       
          
              
             
                              

O( n2 ) の実行時間を達成するには、i 番目のリストにおける j 番目の個体の位置を i 行 j 列のエントリとするランキング マトリックス^を使用します。これにはO( n2 )^の時間がかかります。ランキング マトリックスを使用すると、マトリックス内の順位を比較することで、ある個体が別の個体よりも好むかどうかのチェックを定数時間で実行できます。さらに、優先リストから要素を明示的に削除する代わりに、各個体の縮小リストの最初、2 番目、最後のインデックスが維持されます。一致しない最初の個体、つまり縮小リストに少なくとも 2 つある最初の個体も維持されます。次に、フェーズ 2 では、ローテーションを見つけるために「トラバース」されたp _{iのシーケンスがリストに格納され、標準的な}深さ優先探索グラフ トラバーサルと同様に、配列を使用して個体が訪問済みとしてマークされます。回転の除去後、その末尾があればリストに、また配列内で訪問済みであればその末尾のみを保存し、末尾の最後の個体から次の回転の検索を開始します。末尾がない場合は、次の一致しない個体から検索を開始します。これにより、末尾は回転の除去による影響をほとんど受けないため、末尾の繰り返し走査が削減されます。

以下は、6 人の参加者が参加する Stable Roommates インスタンスの優先リストです: 1、2、3、4、5、6。

1 :   3   4   2   6  5
2 :   6   5   4   1  3
3 :   2   4   5   1  6
4 :   5   2   3   6  1
5 :   3   1   2   4  6
6 :   5   1   3   4  2

フェーズ 1 の可能な実行は、次の提案と拒否のシーケンスで構成されます。ここで、→ はへの提案を表し、× はへの拒否を表します。

1 → 3
2 → 6
3 → 2
4 → 5
5 → 3;  3 × 1
1 → 4
6 → 5;  5×6
6→1

したがって、フェーズ 1 は、次の削減された優先リストで終了します。(たとえば、1: は少なくとも 6 を取得するため、5 を 1: に置き換えます)

1 :  3   4   2   6   5
2 :   6   5   4   1  3
3 :   2   4   5  1   6
4 :   5   2   3   6  1
5 :   3  1   2   4   6
6 :  5   1  3   4  2

フェーズ 2 では、回転r ₁ = (1,4), (3,2) が最初に特定されます。これは、2 が 1 の 2 番目に人気のある値であり、4 が 3 の 2 番目に人気のある値であるためです。r 1 を削除すると、次のようになり_ます。

1 :  3   4   2   6   5
2 :   6   5   4   1   3
3 :  2   4   5  1   6
4 :   5   2   3  6   1
5 :   3  1   2   4   6
6 :  5   1  3   4  2

次に回転r ₂ = (1,2)、(2,6)、(4,5)が識別され、これを消去すると次の式が得られます。

1 :  3   4   2   6   5
2 :  6   5   4  1   3
3 :  2   4   5  1   6
4 :  5   2   3  6   1
5 :   3  1   2  4   6
6 :  5   1  3   4   2

したがって、1と6は一致します。最後に、回転r ₃ = (2,5), (3,4)が識別され、それを消去すると次のようになります。

1 :  3   4   2   6   5
2 :  6   5   4  1   3
3 :  2   4   5  1   6
4 :  5   2  3   6   1
5 :   3  1   2   4   6
6 :  5   1  3   4   2

したがって、{1, 6}、{2,4}、{3, 5}のマッチングは安定しています。

• Python : アーヴィングのアルゴリズムの実装はmatchingライブラリの一部として利用可能です。^[1]
• Java : 不完全リストのルームメイト問題におけるすべての安定したマッチングを見つける制約プログラミングモデルは、CRAPLライセンスの下で利用可能です。^{[2] [3]}
• R : 同じ制約プログラミングモデルはRmatchingMarketsパッケージの一部としても利用可能です。^{[4] [5]}
• API : MatchingTools APIはアルゴリズム用の無料のアプリケーションプログラミングインターフェースを提供します。^[6]
• Webアプリケーション：「Dyad Finder」Webサイトでは、WebサイトのソースコードとJavaScriptで書かれたソルバーを含む、アルゴリズムの無料のWebベースの実装を提供しています。^[7]
• Matlab : このアルゴリズムは、米国海軍研究所の無料トラッカーコンポーネントライブラリassignStableRoommatesの一部である関数に実装されています。 ^[8]

• アーヴィング、ロバート W. (1985)、「「安定したルームメイト」問題に対する効率的なアルゴリズム」、アルゴリズムジャーナル、6 (4): 577–595、doi :10.1016/0196-6774(85)90033-1

• Fleiner, Tamás; Irving, Robert W.; Manlove, David F. (2007)、「「安定したルームメイト」問題に対する効率的なアルゴリズム」、理論計算機科学、381 (1–3): 162–176、doi : 10.1016/j.tcs.2007.04.029
• ガスフィールド、ダニエル M.、アーヴィング、ロバート W. (1989)、安定した結婚問題: 構造とアルゴリズム、MIT プレス
• アーヴィング、ロバート W.、マンラブ、デビッド F. (2002)、「同点のある安定したルームメイト問題」(PDF)、アルゴリズムジャーナル、43 (1): 85–105、CiteSeerX  10.1.1.108.7366、doi :10.1006/jagm.2002.1219