ルームシェアのアルゴリズム：みんなで納得して決めるための方法

ハッピーコンピューター R&D担当の白川です。

日常生活において複数人で何かを決める場面はたくさんあると思いますが、「みんなで何かを決める方法」と聞いてどのような方法を思い浮かべるでしょうか？

話し合い、多数決（1人1票の最もシンプルな投票）、もしくはくじ引きやジャンケンなど運に任せる方法を思い浮かべた人が多いのではないでしょうか。

話し合いは決定力に欠けるため、最終的に必ず決まる方法となったら多数決か運ベースの方法のどちらかが圧倒的に多いと思います。

しかしこれらのよく使われる方法は、一部の人にとって大変不満足な結果になってしまう可能性が高く、みんなで決めるというよりは勝者と敗者を決める方法になっています。

そのため、「みんなで決める」「みんなが納得する」ことを目指し、様々な決定方法についてこれまで研究されてきました。

今回はその中の一つとして、公平分割問題（fair division problem）の一種であるルームシェアの問題（rental harmony）を取り上げてみます。

ルームシェアの問題

仲良し4人組が、東京で家賃10万円、4LDKの物件を借りてルームシェアをしようとしています。

都内で4LDKで10万円・・・果たしていったいどんな物件なのか、そこは本当に東京なのか、気になりますね。

それはさておき、4つの部屋はそれぞれ広さや採光など条件が異なるため、誰がどの部屋にするか、また家賃をどの程度負担するか決めかねています。

部屋1: 8畳洋室、窓あり
部屋2: 6畳洋室、窓（二面採光）あり
部屋3: 6畳和室、窓あり
部屋4: 4.5畳洋室、窓なし

一般的には話し合いで決めそうな問題ですが、4.5畳窓なしの部屋の押し付け合いが始まりそうです。

さて、何かいい決め方はないものでしょうか？

解決方法

ルームシェアのように「固定の全体支出額」と「再分割不可能なリソース群」が与えられたとき（＝「家賃」と「広さや特徴が決まっている4つの部屋」）、全員が納得する（＝「あっちの部屋がよかったのに」とならない）方法がいくつか提案されています。

ここでは、紙と鉛筆があればすぐにできるHaakeらの方法で決めたいと思います。

1. 各々が思う「各部屋の価値」を出し合う

まず、一人ひとりが思う各部屋の価値、すなわち「この部屋ならこれぐらいの家賃を負担してもよい」という金額を書き出します。

ただし書き出す金額には制約があり、各部屋の価値の合計を家賃に一致させる必要があります。金額に制約のあるオークションっぽいですね。

その後、全員でその金額を共有します。

例えば以下のようになったとして、次に進みましょう。

	部屋1	部屋2	部屋3	部屋4	合計＝家賃
Aさん	3.5万円	3.0万円	2.5万円	1.0万円	10.0万円
Bさん	3.2万円	2.8万円	2.5万円	1.5万円	10.0万円
Cさん	4.0万円	3.1万円	2.0万円	0.9万円	10.0万円
Dさん	4.5万円	3.5万円	1.5万円	0.5万円	10.0万円

2. 価値が最大となるように部屋を割り振る

各部屋に対して4人が思う価値は異なっていますが、この価値を最大化するように部屋を割り当てることで、全体として家賃分以上の価値を得ることができます（最悪でも家賃と同等の価値となる）。

先ほどの表で計算すると、部屋1をDさん、部屋2をCさん、部屋3をAさん、部屋4をBさんに割り当てたときに、全体の価値が4.5万円＋3.1万円＋2.5万円＋1.5万円＝11.6万円と最大になります。

	部屋1	部屋2	部屋3	部屋4
Aさん	3.5万円	3.0万円	2.5万円〇	1.0万円
Bさん	3.2万円	2.8万円	2.5万円	1.5万円〇
Cさん	4.0万円	3.1万円〇	2.0万円	0.9万円
Dさん	4.5万円〇	3.5万円	1.5万円	0.5万円

3. 余ったお金を均等に還元する

実際には家賃は10万円なので、　余った1.6万円を4千円ずつ4人に返すことができます。

その結果、Dさんが4.1万円、Cさんが2.7万円、Aさんが2.1万円、Bさんが1.1万円の負担となります。

この方法で負担額と部屋を決めることで、必ず全員が自身の部屋に対して思う価値以下の負担となることが保証されます。

これにて一件落着。

解決方法その2

・・・Dさんが何か言いたげなようです。

言い分を聞いてみると、「Cさんが自分の3.5万円よりも安い3.1万円で部屋2に決まったのが解せない」とのことです。

Dさんも部屋1に自身が思う価値よりも4千円安く住めているのだから別にいいじゃんと思う人もいるかもしれませんが、この「他の部屋は全部自分よりも高い値付けをした人が住んでくれないと損した気分になる」と思う状態をenvy（妬み）と呼び、envy-free（妬みがない）な状態にすることで初めて全員が納得したと考える人もいるようです。

確かに先ほどの方法では、他の人の金額の並び次第で誰かが自分よりもおトクに部屋に住めているように感じるケースがあります。

そこで、余ったお金の還元方法をより納得感が得られるように（＝他の人の割り当てをみても自分よりおトクに部屋が決まったと感じないように）変更します。

3-B. 妬みを解消するように余ったお金を補填する

今回の場合、Dさんが部屋2に3.5万円の価値を付けており、それより4千円安い3.1万円の価値を付けたCさんが部屋2に決まったので、差額の4千円を先にDさんに補填します。

これにより、Dさんは各部屋に4千円安く値付けをしたとみなすことができるため、Dさんの妬みは解消されました。

小難しい話になりますが、この妬みの解消は必ず成功する（余った金額の範囲内で全員の妬みを解消できる）ことが理論的に保証されています。

妬みの解消が終われば、あとはさっきと同じように余ったお金（Dさんに4千円を補填し、残り1.2万円）を全員に還元するだけです。

最終的に、Dさんが3.8万円、Cさんが2.8万円、Aさんが2.2万円、Bさんが1.2万円の負担となります。

補足

実は、今回ご紹介したHaakeらの方法をそのまま適用すると家賃の負担額がマイナスになるケース（＝他のルームメイトからお金をもらいながら住む状態）がごくまれに発生しますが、その場合、ルームメイトにとってはその人を追い出して空室状態にしたほうが負担が軽くなるというバグがあるため、最終的な負担額を0円以上に調整する必要があります。

家賃の負担額が絶対にマイナスにならないような決め方もあり、これを非負性（non-negativity）といいますが、非負性を満たすと妬みの解消を保証できなくなることが証明されています。