婚活において積極的行動が必要な理由をGSアルゴリズムで検証してみる

最近はゼ●クシィ縁結びというサイトが主な活動領域だ。絶大なブランド力を持った大手がきちんと運営しているサイトであり、とても良い。

しかし未だ結果に結びついていない。己を鼓舞して必死こいて愛想振りまき慣れぬコミニュケーションを懸命に試み努力したにも関わらず、一人孤独な夜に震える生活は何一つ変化していない。

結局、自分じゃダメなのか？否、それを認めては己が立ちいかない。そうだ、戦略が悪いのだ。

インターネットにおけるマッチングは旧来の「天然物」とはまるで前提が違う。最小化されたしたしがらみに、最大化された検索効率。パラダイムの変更を正しく認識し、適切なる戦略を的確なる戦術において実践しなければ成果には結びつかない。

そのためにまず必要なのは情報だ。そう、先人の知恵を借りるのだ。
台頭して日の浅い婚活サイトに形式化された知など未だ存在しないことが予想されるが、問題を抽象化し本質を取り出し、広い命題として捉えば先例の研究はあるはずだ。

そこで見つけたのがこれ

https://en.wikipedia.org/wiki/Stable_marriage_problem

Gale–Shapley algorithmという名前のゲーム理論のアルゴリズムがまさに探していた命題ではないか。

当たられた状況の中、限られた選択肢を前にして、己の利得をどう最大化するか。まさに人生そのものだ。

あまり難しい内容ではないようだ。しかし分かったような気がしただけでは分かったうちには入らない。

プログラマの端くれならば自分で書いてみるしかない

## GSアルゴリズムを実装してみる

とりあえず一番慣れてるjsで。


### 問題設定

今回はとても簡単な問題設定にする

* Men/Womenが同数ずついる
* それぞれのメンバーは全ての異性に対して、自分の中での好みの順位をもつ
* 相手のいないそれぞれのMenは１ターンに一度、自分を拒否したことないWomenのうち、もっとも好みの相手にプロポーズする
* WomenはプロポーズしてきたMenの中で一番好みなのをkeepする。それ以外は拒否する
* 最後のターンが終わった時点でkeepされていれば成婚

というものだ。ざっくりいうと常にオファーを出すのはMen側でWomen側は現状一位をキープして良いのが来たら乗り換える。最後まで生き残ったら成立。

Men側からみるとなんという理不尽なルール。しかし己の経験と比べてみるとなんとなくそれが世の中の真実な気がする。よし、この前提で進めてみよう。

### Men/Womenの定義

コードにするとこんな感じになる。配列のシャッフルの実装は意外に大変なので、[shuffle-array](https://www.npmjs.com/package/shuffle-array)というパッケージに任せることにした

```js
const shuffle = require('shuffle-array')

function defineMembers (memberCount = 10) {
  const men = shuffle(new Array(memberCount).fill(null).map((_, i) => ({
    name: `man#${i}`,
    rejectedBy: [], // 自分を拒否した異性の名前
    likes: [], // 好みの異性
  })))
  const women = shuffle(new Array(memberCount).fill(null).map((_, i) => ({
    name: `woman#${i}`,
    proposedBy: [], // プロポーズしてきた異性の名前
    keeps: null, // キープしている異性。最後まで残ったら結ばれる
    likes: [], // 好みの異性
  })))

  for (const m of men) {
    // 好みの順に異性を登録
    m.likes = shuffle(women).map(({name}) => name)
  }

  for (const w of women) {
    // 好みの順に異性を登録
    w.likes = shuffle(men).map(({name}) => name)
  }

  return {men, women}
}
```

### ゲームの実行

```js


const memberCount = 10
const {men, women} = defineMembers(memberCount)

// 配列だけだと不便なのでnameをキーにした辞書を用意
const menByName = Object.assign({}, ...men.map((man) => ({
  [man.name] : man
})))
const womenByName = Object.assign({}, ...women.map((woman) => ({
  [woman.name] : woman
})))

// 複数回ラウンドを行う
const rounds = 4
for (let round = 0; round < rounds; round++) {
  // Men側
  for (const m of men) {
    const isKept = women.some(({keeps}) => keeps === m.name)
    if (!isKept) { 
　　　　// キープされていない孤独なmenはまだ自分をrejectしてない最良の相手を探す
      const best = m.likes.find((name) => !m.rejectedBy.includes(name))
      if (best) {
        // 最良のWomanにプロポーズする
        womenByName[best].proposedBy.push(m.name)
      }
    }
  }
  // Women側
  for (const w of women) {
    // プロポーズして来た相手を、暫定一位とその他に切り分ける
    const [best, ...notGoodEnough] = w.proposedBy.sort((a, b) =>
      w.likes.indexOf(a) - w.likes.indexOf(b)
    )
    w.keeps = best || null // 一番良いのをキープ
    for (const n of notGoodEnough) {
      menByName[n].rejectedBy.push(w.name) // それ以外は拒否
    }
  }
}

```

### 表示

```js

// ゲームが終わった時点でキープしている場合に成約とする
const couples = women
    .map(({name, keeps}) => keeps ? [name, keeps] : null)
    .filter(Boolean)
    .map(([wName, mName]) => [
      womenByName[wName],
      menByName[mName]
    ])

  const successCount = couples.length
  const failureCount = memberCount - successCount
  console.log(`${successCount} success, ${failureCount} failure`)
  console.log(
    couples.map(([w, m]) => [
      // それぞれの名前と、何番目に好みの相手と結ばれたかを表示する
      w.name, w.likes.indexOf(m.name), m.name, m.likes.indexOf(w.name)
    ])
  )
```

ここまでのコードをまとめて書くと以下の結果になる

https://gist.githubusercontent.com/okunishinishi/0ff3e169031445ec7575d4ac1c9d0716/raw/638cfa69f4fd6251c916dc85964048dbb03c2667/gs-example01.js


## 試してみた結果

やってみると、予期せぬ結果に。

実行すると、例えばこんな数値が出てくる

```bash
10 success, 0 failure
[ [ 'woman#1', 1, 'man#3', 0 ],
  [ 'woman#2', 0, 'man#1', 1 ],
  [ 'woman#7', 0, 'man#7', 0 ],
  [ 'woman#5', 0, 'man#0', 1 ],
  [ 'woman#8', 7, 'man#6', 2 ],
  [ 'woman#3', 2, 'man#8', 0 ],
  [ 'woman#4', 1, 'man#4', 1 ],
  [ 'woman#9', 1, 'man#2', 0 ],
  [ 'woman#0', 4, 'man#5', 1 ],
  [ 'woman#6', 9, 'man#9', 2 ] ]
```

それぞれの配列の二つ目と四つ目はそれぞれ、「自分が何番目に好みと思う相手と結ばれたか」である。

見ての通り、menの方がwomenよりも数値が小さい。つまりこのゲーム設定だとmenの方がより「自分が好ましいと思う相手と結ばれる」可能性が高いのだ。

よく考えてみればそりゃそうだ。己の好みが反映されるのが、選択肢を出す前か後かの違いで言えば、先にフィルタリングされている方が反映度が高いに決まっている。

なんてこった。

やはり行動するのが正解なのである。

婚活サイトではいいねを押すのもメッセージを出すのもデートに誘うのも圧倒的に男から行動を取ることが多く、どうして一方的にリスクを背負わされるのかとその理不尽さに嘆いた日々もあった。しかしそのリスクは必要な犠牲だったのだ。「こっち来た奴のベスト」より「こっちから行ったベスト」の方が良い結果を残す可能性が高いとは。


## 結論

古来から言われて来たとおりだ。

「とにかく行動しろ」

諦めたらそこで試合終了ですよという監督の声が聞こえてくる。めげずに明日からも頑張ろう。