Googleの人のオークション理論論文でも読んでみる その1
Goel, G., Mirrokni, V. and Leme, R. P., Polyhedral Clinching Auctions and the Adwords Polytope, 44th ACM Symposium on Theory of Computing (STOC 2012).
Google の2012年excellent paperが挙げられていて，その中にオークション理論の論文があった．Machine Learningと異なり，オークション理論，メカニズムデザインは自分の専門分野の一つなので，かいつまんで紹介してみる．あまり厳密な数学的記述は行わず，わかりやすさ重視で説明してみたい．
まず，オークションに関する多くの誤解を解いておきたい．オークションというとある品物（財）を高く売りつける方法，または（ヤフオクのように）いらないものを処分する方法と実用上，捉えられがちであるが，オークション理論が目指すのは，様々な情報の非対称性がある中で，ある財をできる限り最適に割り当てることである．
簡単な例で説明しよう．ある分割不可能財を最適に割り当てたいとする．ここでいう最適とは「最も欲しい（その財の価値を高く評価している）人に割り当てること」と緩い定義をしておく．分割不可能財というのはホールケーキのようにみんなで分け合うことができず，ある人が所有した場合，別の人は所有できないものである．
たとえば，あるアイドルとの1日デート権が2日分ある状況を考えよう．それに対して，4人のファン(A, B, C, D)が表1の評価値をもっているとしよう．簡単に説明すると，Aさんは6/15でも6/16でもどちらでも都合が良さそうだ．二日間独り占めすると評価値の合計は各1日分の合計より少なくなっているので限界効用は低減している．Bさんは6/16の方を高く評価しているが2日分は限界効用が低減している．Cさんは6/15のみ都合が良いようで，2日分手に入れたとしても評価値は6/15と変わっていない．Dさんは独占欲が強く，2日分手に入れない限り価値はないと思っているようだ．
表1 各プレイヤーの真の評価値
| プレイヤー | 6/15 | 6/16 | 6/15, 6/16 |
|---|---|---|---|
| A | 10万 | 10万 | 15万 |
| B | 9万 | 12万 | 20万 |
| C | 15万 | 0 | 15万 |
| D | 0 | 0 | 25万 |
このような評価値の場合，最適な割当は(6/15, 6/16) = (C, B)で，価値の合計は27万円となる．でも，現実問題としてこのような割当を達成させることができるのか？というのがオークション理論のモチベーションである．なぜ達成できない可能性があるのかというと，各個人が嘘の入札(高めに入札，低めに入札)を行う可能性があるためである．たとえば，Dが6/15, 6/16両方の2日分に対して28万円と入札すると，(6/15, 6.16) = (D, D)という割当になってしまい，価値の合計は25万円のまま(Dの真の価値は25万)なので，最適な割当よりも非効率な割当が実現してしまう．Dにこのような入札をさせないようにするにはどうすればいいのだろうか？
そこで，オークション理論で考えるオークションメカニズムによって実現する割当には満たすべき3つの重要な性質がある．個人合理性(Individual Rationality)，パレート最適性(Pareto-optimality)，インセンティブ両立性(誘因性とも; Incentive compatibility)である．
個人合理性とは，自分があるオークションへの入札行動を行うことで，実現する期待利得が非負であることである．（そうでなければ入札などするはずないでしょ？）
パレート最適性とは，他のプレイヤーが得られる利得を減らすことなく，あるプレイヤーの利得を増加させることができない状態であり，経済学においてしばしば効率性を表現するのに使われる．上の例で言えば，2日分のデート権をみんながごみ箱に捨てるよりはAさんが所有した方がパレート改善的(0万円から15万円の価値になる)であり，Aさんが2日分所有するよりAさんが1日目，Bさんが2日目の方がパレート改善的(15万円が22万円の価値になる)が，Cさんが1日目，Bさんが2日目の割当(27万円の価値)以上にパレート改善的な割当は存在しない．
インセンティブ両立性とはオークション理論やメカニズムデザインにおいて，最も重要な概念であり，各プレイヤーが虚偽表明をしないという性質である．個人合理性やパレート最適性は他の経済学でもしばしば登場するが，このインセンティブ両立性がメカニズムデザインたらしめているといっても良い．これはオークションの価格の支払いルールについての性質と考えて良く，どういう価格の支払いルールであれば，全ての個人は自分の評価値通りの入札(表明)を行うかという話である．
たとえば，上記の評価値を持っていて，入札値で最も高い人がその入札値で落札しましょうというルールだった場合，最適な割当は(6/15, 6/16) = (C, B)だが，CやBが得られる利得は自分の評価値15万円(Bは12万円)，支払額15万円(Bは12万円)なので両者の差額である落札者の利得は0である．一方，落札できなかったAやDも利得は0なので，CやBは何のために落札したのかわからない．となると，この支払ルールのもとでは，みんな自分の評価値よりも若干低めに入札することになるだろう．たとえば表2のように．括弧内は真の評価値を表す．
表2 虚偽表名による入札値
| プレイヤー | 6/15 | 6/16 | 6/15, 6/16 |
|---|---|---|---|
| A | 9万(10万) | 9万(10万) | 13万(15万) |
| B | 4万(9万) | 7万(12万) | 15万(20万) |
| C | 12万(15万) | 0 | 12万(15万) |
| D | 0 | 0 | 24万(25万) |
この入札された評価値で最も入札値の合計が高くなるように割当を決めると，(6/15, 6/16) = (D, D)の24万である．でも，これは最適な割当ではない．このように支払ルールを変に設定してしまうと，みんなが嘘をついてしまい，その結果として，最適な割当も達成することができないといった問題が生じてしまう．なので，入札値で高い順に落札者を決め，落札者にはその入札額で支払ってもらうというオークションルールは「インセンティブ両立性を満たしていない」ということになる．
それではどうすればいいのか，というモチベーションで生まれたのがVCGメカニズム(Vickrey-Clarke-Groves)メカニズムである．これは
- 評価値の和を最大にするような割当を行い，落札者を決定する
- 落札者の支払額は[自分が入札しなかった場合(自分がいなかった場合)の落札者の評価値の合計]と[自分が落札したときの自分以外の落札者の評価値の合計]との差額
という支払ルールである．これを予め全プレイヤーに伝えておくことで，全プレイヤーは自分の真の評価値で入札することが支配戦略(嘘をつかない=インセンティブ両立性を満たす)となる．
これを表1, 表2の場合で確かめてみる．表1のようにみんなが真の評価値で入札した場合，割当は(6/15, 6/16) = (C, B)で27万ある．Cの支払額は，C以外の落札者の評価値の和はBの12万，もしCがいないと割当は(6/15, 6/16) = (D, D)で評価値の和は25万なので，Cの支払額は25万-12万=13万である．よって，Cは15万-12万=3万円の利得がある．一方，Bも同様に計算をすると，Bの支払額は10万であり，12万-10万=2万円の利得がある．結果として，割当は(6/15, 6/16) = (C, B)，6/15のデート権価格は12万，6/16のデート権価格は10万となる．もしDが自分が落札するために28万と高めに入札する嘘をついていたら，Dの支払額は27万になり，自分の評価値を超えてしまうので損であり，嘘をつくことができない．よって，自分の評価値よりも高く入札するインセンティブはどの個人にも存在しない．
逆にVCGメカニズムの下で表2の入札が起こると，割当は(6/15, 6/16) = (D, D)であり，Dの支払額は21万，Dの利得は4万円である．しかし，CやBにとっては正直に表明していれば，それぞれ3万円，2万円の利得があったにもかかわらず，自分がわざと小さめに評価値を言ったことで利得が0になってしまった．わざわざ自分の利得を減らすような入札を行うことは考えられないので，このような入札行動を行うインセンティブはBやCには存在しない．よって，どの個人も真の評価値よりも低く入札することはない．
以上より，このようなメカニズムの下ではどの個人も正直に入札することが支配戦略である．その結果，単純に評価値の和を最大にするような割当を考えれば良いし，それがパレート最適(効率的な割当)になる．また，VCGメカニズムに基づいて価格も決めればよい．これで万事解決であるというのがVCGメカニズムの素晴らしき理論的特性である．感動的！
ということで，じゃあ，オークション理論にもう問題点なんかないじゃん．VCGメカニズムで万事解決という雰囲気がするかもしれませんが，そうではないのです．たとえば，Cは15万円の価値を感じているが，Cはお子様で3万円しかもっていないかもしれない．そんな予算制約があるとき，どういう風にオークション理論(メカニズムデザイン)は考えれば良いのか？予算制約がない場合，VCGメカニズムは完璧っぽいが*1，現実には予算制約があるし，やっぱり最適割当なんかできないんじゃないか？という次なるモチベーションがあります．そこにトライしたのが，このGoel et al.(2012)である．(だと思うのですが，実はまだちゃんと読んでない…)ということで，長くなったので次のエントリにたぶん続く．
