引越し先の選び方
さて恵比寿に引っ越したわけだけど、こないだ雑談をしながら、どうやって新居を決めるか、という話になって、なかなか面白かった。だいたい最初に見た物件で決めてしまうという人もいたり。基本的にはまず条件を明文化してぶらさない、家賃や面積などについてはソフトリミットとハードリミットを設ける、といったところは概ね合意が取れるところだとは思うが、さてどうやって部屋を選べばいいだろうか。
数学的には、これは典型的な秘書問題の一例になっている。秘書問題というのはこういう問題だ。ある事務所が秘書をひとり雇いたい。応募者は順番に面接するが、なぜか面接の直後に採用の是非を伝えなければならない。つまり、３人目で採用と決めたら残りの応募者との面接はできないし、逆にパスとなったらその人にもう一度連絡してやっぱり採用でした、などとするのも不許可とする。応募者のなかから最高の人を選びたい(面接をしたところ応募者の優劣はつけられる、というのが前提ね)。王様が妃を探すというパターンもあって「結婚問題」とか呼ばれたりもするらしい。
賃貸契約の場合も部屋をパスしたらだいたい他の人が応募して取られてしまうし、決めたらもう他の物件は見られないから、典型的にこの問題にマッチする。
かならず最高の部屋を選ぶアルゴリズムは実はないけれど、約37%の確率で最高の部屋を選べる方法が知られている。ただその場合、あらかじめ見る(内見する)物件の数の上限が決まっているとする。もちろん本当の上限はよくわからないが、時間とかけられるコスト、探しているエリアの状況などで、だいたい内見できる物件の数はおおざっぱにわかるはずだ。
で、その数をnとすると、はじめからn/2.7(本当は自然対数の底eだが)の数の物件は全部パスする。見てどんなもんかは確認するけど、絶対に採用しない。で、残りを見ていく中で、これまでのなかで最高の部屋を見かけたら即採用、とする。
どうしてこのやり方がうまくいくのか導出するのは面倒なので詳しくは他のページを読むのをお勧めするが、直感的には次のように考えるといい。2.7で割るのはなんかややこしいので、全体を半分に分けるとする。たとえば10件最大で内見するとして、はじめの5件は絶対にパスする。でそれ以降を見てきつつ、これまでで一番いい物件を見かけたらそれを選ぶ。ここでちょっと考えると、物件を見る順番がランダムだとすると、ベストな物件が前半に含まれる確率は50%、後半に含まれる確率も50%。一方、2位の物件も同じように前半に含まれる確率が50%ある。つまり、1位が前半で2位も前半、1位が前半で2位が後半、1位が後半で2位が前半、1位も2位も後半、という4つのパターンがあってどれも同じ確率だから、それぞれ25%ずつということになる。このうち3番目のパターン、つまり1位が後半で2位が前半のときにこの方法でベストな物件が選べる。ということはこの方法では少なくとも25%の確率でベストな物件が選べるというわけだ。実際には4番目のパターン(1位も2位も後半)の場合でも、場合によっては1位を選べる可能性があるので、本当の確率は25%よりは若干おおい。
で、この問題を詳細に検討すると、半々に分けるんじゃなくて、最初の1/2.7=約0.37%までをパスするときに成功確率が最大になることがわかったというわけです。
—
さて、この話はなかなか面白いのだけど、実は今回の場合には欠陥がある。というのも、秘書を選ぶにせよ部屋を選ぶにせよ、本当に一番良いのを選べればよくてダメなら採用しない、というわけにはいかない。一番良い候補を選ぶのに失敗したとしてもそこそこいいものは選べる、できるだけいい順位のものを選びたい、そんな方法はないだろうか。
英語のウィキペディアには、そっちの問題についても簡単な記述がある。Beardenという人が2006年というたいへん最近に書いた論文によると、このような場合には最適戦略がすこしかわり、√nまでをスキップし、これまでで一位更新になった物件を選ぶのが最適なんだそうだ。詳しくは論文をお読みください。期待値を定式化し、「ある数まではスキップして残りではじめて一位が更新されたときに選ぶ」という戦略を計算して、最大値を求めるといった方法論みたい。
—
しかし、現実にこのやり方ってうまくいくんだろうか。
上では強引に「最大で何件を見るかを意味するnは決まる、決められる」としたけど、そんな簡単でもないだろう。物件の良し悪し、候補の良し悪しなんてそんな簡単にランキング付けできるわけでもない。さらにいうと、候補が到着する順番が完全にランダムだということは考えづらい。物件の場合、自分で探すとすると適当に良さ気なやつを見つけてくるわけで、はじめに見つけたやつが一番いいやつな可能性が高い。不動産屋がどんどん勧めてくる場合は逆に、内見をしていくうちにこちらの反応を学習してもっと好みにマッチしたものを勧めてくるかもしれないから、そうなったらだんだんいいものが出てくるかもしれない。
それでも、厳密にn/eや√nという数字を採用するかはさておき、「はじめのほうはスキップして、それから最初に一位更新した物件を選ぶ」というアプローチは個人的にはぴったりくる考え方だと感じている。というか単に、いくつか内見することで相場の感覚がわかるから、それでよさ気なものが選べそう、という程度の意味合いでしかないかもしれないけれど。