実は、1対1という制約を課せば、全体として最も満足が行く縁結びを決定するアルゴリズムがすでに存在する。

金融日記:東京 - ニューヨーク - ロンドン - パリ　世界の先進国の恋愛シーンで今起こっていること
これから紹介する計量経済学モデルは、あらゆる社会科学の理論の中でも最もエレガントでそしてシンプルなもののひとつだと思います。
asin:4874084141
C言語による最新アルゴリズム事典
奥村晴彦
C言語による最新アルゴリズム事典 P. 4

安定な結婚の問題 stable mariage problem

N人の男性とN人の女性が集団見合いをし、おのおのの異性を好みの順に順位付けした。この順位表をもとにして安定な縁結びの仕方を決めるのがこの問題である。仮に男性M1と女性F1が結婚したが、じつはM1はF1よりF2を好み、F2はM2よりM1を好んだならば、将来問題が起こりかねない。
この問題には次のような非常に簡単な方法がある。まず男性1が彼のリストでトップの女性に申し込む(実際にではなく、アルゴリズム上での話である)。彼女はまだ誰からも声がかかっていないので、とりあえずオーケーする。次に、男性2が彼のリストでトップの女性に求婚するが、彼女がすでにほかの男性にオーケーを出していた場合、もし彼女が新しい求婚者の方を好めば、古い男性を振って新しい求婚者にオーケーを出す。振られた男性はすぐさま彼のリストで次のランクの女性に申し込む。以下同様に続ける。全員が納得できる縁結びがO(N2)ステップで完成する。

以下にJavaScriptに移植したものを。

function make_matches(gb, bg){
  var N = gb.length;
  var boy = [], girl = [], position = [], rank = [];
  var b, g, r, s, t;
  for (g = 1; g <= N; g++){
    rank[g] = [N+1];
    for (r = 1; r <= N; r++){
      b = gb[g-1][r-1];
      rank[g][b] = r;
    } 
    boy[g] = 0;
  }
  for (b = 1; b <= N; b++){
    girl[b] = [0];
    for (r = 1; r <= N; r++){
      girl[b][r] = bg[b-1][r-1];
    }
    position[b] = 0;
  }
  for (b = 1; b <= N; b++){
    s = b;
    while (s != 0){
      g = girl[s][++position[s]];
      if (rank[g][s] < rank[g][boy[g]]){
        t = boy[g]; boy[g] = s; s = t;
      }
    }
  }
  return boy;
}
プログラム:
出力:
エラー:

見てのとおり、この例(同書に乗っていたデータを援用)では、女1のみ第三希望とくっついているが、残りは男女とも第一希望とくっついている。女1はかわいそうだが、他が満足しているので他から男を奪うのは難しい。たしかに安定的ではある。

このアルゴリズム、男女に限らずあらゆる縁結びに使える。奥村先生は希望校と生徒の結びつけに使ったらどうかと同書で提案しているが、就職活動にも当然使えるだろう。

問題は、このアルゴリズム、個々の参加者にも結構面倒なことだろうか。好みの順位を付けるのは結構難しい。なにしろ順位の組み合わせはN!もあるのだ。このアルゴリズムの場合、同一順位はOKなので、だいたいの好みを入力させるという手が使えるかも知れない。

Dan the Match Maker