watermint.org

9月から就職活動をしてみた経験と、アルゴリズムデザインに載っている完全マッチングアルゴリズムからの考察です。今回の転職では数社のエージェント(民間職業紹介業者)に協力いただいています。そのエージェントの働き方と、安定マッチングアルゴリズムの挙動とは興味深い類似性があることに気づきました。安定マッチングアルゴリズムは上述のアルゴリズムデザインという本で最初に紹介されているアルゴリズムです。アルゴリズムに興味がある方は、重くて高価な本ですが、ぜひ読んでみてください。高いので図書館で借りて読むといいと思います(なければリクエストすると買っていただけることがあります)。

安定マッチングとは大まかには、企業と就職希望者のようにお互いに自由な希望順位をもった者同士を安定的にマッチングさせることです。ここで、安定的といっているのは、ある希望者Aさんが、企業XにAさんの希望順位通り内定をもらったとします。その後、希望者Bさんの話を聞いていて気が変わって企業Yに興味を持つようになり、内定を辞退するようなことになると、収拾が付かなくなってしまいます。そこで、問題を捕らえるに当たって、希望順位は不動とすることで、マッチングの結果が安定します。

アルゴリズムデザインでは、安定マッチングの例を男女の結婚マッチングとして紹介しています。これは、就職希望の例だと企業Xが複数の希望者を採用しても良いので、アルゴリズムとして設計する難易度が上がってしまうため、男女の結婚のように1対1のペアとしてマッチングさせるアルゴリズムを最初に紹介しています。このアルゴリズムはGaleとShapleyによるものなので、GSアルゴリズムと紹介されています。
昨今の経済状況では、ある企業の採用枠は高々1人のことが多いので、転職エージェントはGSアルゴリズムが使えそうです。

GSアルゴリズムを使うとして、転職エージェントが行うことは次のようになります。

1. 最初に、同数の企業と希望者がいて、まだ誰も内定もオファーももらっていないとします。
2. 企業xが優先順位としてもっとも高く、まだオファーを出していない希望者aを選びます。希望者aが別の企業yから内定をもらっていない場合、希望者aは内定を受諾します。
3. 希望者aが別の企業yから内定をもらっている場合、希望者aが企業xをより好むなら企業yの内定を辞退し、企業xの内定を受諾します。希望者aが企業yをより好むなら、企業xはオファーを出しません。
4. すべての就職希望者にオファーを出していない、採用枠が埋まっていない企業が存在する間このプロセスを繰り返します。

これでしばらく操作を続ければ、企業と採用希望者の安定マッチングが得られます。

このGSアルゴリズムを使ったマッチングは、O(n²)で終了する優れたアルゴリズムです(その証明など詳しくはアルゴリズムデザインで確認してください)。安定マッチングが得られてよしよしと思うところですが、このアルゴリズムでは就職希望者の優先順位よりも企業側の優先順位がより優先されます。企業の優先順位と、就職希望者の優先順位がうまく合致する場合にはフェアな安定マッチングとなりますが、そうではない場合企業側の優先順位に基づいて安定マッチングが完了し、就職希望者は不満を持つかもしれません。

不況のさなか、就職希望者側にアンフェアに感じるマッチングであったとしても、満足すべきだろうと言い聞かされるかもしれません。しかしながら、就職希望者側の希望条件すらヒアリングしない転職エージェントが今回多かったような印象を持ったのは、やはり転職エージェントにとってのスポンサーが企業側だからのように見えて仕方がありません。
企業側とはネゴシエーションをしないし、就職希望者側を説得にかかるエージェントはまさにGSアルゴリズムでの安定マッチングを経験的に実践しているのでしょう。そういうエージェントに限って「あなたの将来を考えて」などと発言するのです。

秋の夜長にぴったりな本がたくさんそろいました。全部読み終わるのはいつになるだろう。特にKnuth先生のThe Art of Computer Programming Volume 1-3のボックスセットは邦訳のほうではなく、原書なので余計に時間がかかりそうです。2010年ぐらいまでには読み終わりたいですね。

ほしかったアルゴリズムデザインという本を八重洲ブックセンターで買ってきました。実は最近、何件か本屋さんを回って探していましたがおいていたのはここが初めてでした。しかも2冊もおいてた。やるな、八重洲ブックセンター。アマゾンで買ったらアマゾンのポイントが付いてお得かなあと思ってましたが、買ったら八重洲ブックセンターにあるカフェの一品無料券が付いてきたので少しお得感がありました。
さて、実際の本の内容ですが最近買った本の中では一番好きかもしれません。重めの本でいうと、

• コンピュータの数学
• コンピュータプログラミングの概念・技法・モデル

というのがあります。どちらも、とてもいい本ですが、今すぐ読みたくなるということだとアルゴリズムデザインに軍配が上がります。コンピュータの数学なんかは1年ぐらいかけてじっくり読みたいです。

きしださんが読んでいるという「アルゴリズムデザイン」という本が欲しい。重そうなので引っ越ししてから買いたいのだけど、きしださんのエントリーをみる度にどんどんほしくなってしまう。今ほしい、けど重そう。今買ってもすぐ読まないだろうしなあ・・・。