« 読了: Franco, Malhotra, & Simonovits (2014) 社会科学における「引き出し問題」はどのくらい深刻か | メイン | 読了：黒木(2014) 「原因の確率」とその評価 »
2015年2月19日 (木)
Chen, Y. & Pennock, D.M. (2010) Designing markets for prediction. AI Magazine, 31(4).
予測市場をはじめとした予測メカニズムについてのレビュー。
イントロ
- 予測のためのメカニズム・デザインには主に次のタイプがある: (1)予測市場, (2)ピア予測システム。後者はアウトカムがはっきりしない場合でも使える。
- 予測メカニズムの主目的は分散している情報を集約することだ。その重要な特徴として、表出性expressiveness(エージェントが柔軟に情報伝達できること)と流動性がある。また副次的目的として、誘因両立性、計算的扱いやすさ、個人的合理性がある。
スコアリング・ルール
- プロパー・スコアリング・ルールとは [...略]。
- 複数の予測を得たい場合はshared scoring ruleというのがある。[←M先生のレビューに出てきた「競争的スコアリング」のことらしい。Kilgour & Gershak(2004, Decision Analysis)。]
流動性とマーケット・メーカ
- オークションじゃなくてマーケット・メーカを使うと損失の可能性が生じるけど流動性が高まる。
- Hansonのマーケット・スコアリング・ルールについて。それはコスト関数ベースのマーケット・メーカと等価だ。例として対数スコアリング・ルールを使ったLMSRがある。なお、no-regret learningアルゴリズムとも深い関係がある[... よくわからんのでパス]。
- Chen & Pennock (2007) の効用ベース・マーケット・メーカ。
- Penncock(2004)のダイナミック・パリミュチュエル・マーケット[... DPMの説明、やっぱしよくわからん。困ったなあ]。
- 損失に上界があるか [...関心ないので略]。
- 現状ではLMSRがデファクト・スタンダードだが、流動性パラメータ(b)の決め方が難しい。bの値を徐々に変えていく提案もある(Othman et al., 2010 Proc.EC10)。
誘因両立性
- 予測メカニズムは一般に誘因両立性がない。たとえば連続的ダブル・オークションでは取引しない方が合理的だ(no tradeの定理)。ノイジーな投資家がいれば合理的投資家は取引するのが合理的になるかもしれないけど、依然として誘因両立性はないかもしれない。またMSRは近視眼的には誘因両立だが、ブラフで長期的に儲けようという発想もできる。
- メカニズム・デザインでいう誘因両立性とは、多くの場合、支配戦略誘因両立性のことを指している。いっぽう予測メカニズムでいう誘因両立性とは、ふつうベイジアン・ナッシュ誘因両立性だ[←真実申告がベイジアン・ナッシュ均衡になっている、という意味かしらん]。
- 予測市場で真実申告がゲーム理論的均衡になるかというと[...云々云々。このくだり、私には難しいので略]。
- 結果を意図的に操作する可能性とその対策について[...略。なにがなんだかさっぱりわかんないんだけど、Dimitrov & Sami (2010, Proc.EC10)というので、2つの市場が並行している状況のゲーム理論的分析をしているそうだ。ふーん]。
- ground truthがないときのピア予測手法について。その始まりはMiller, Resnick, Zeckhauser (2005 Mgmt Sci)[←読まなきゃ!!]。出来事を表す離散確率変数$\omega$について、その真の状態の下での確率分布からランダムドローされたシグナル$s$を、各エージェントが独立に受け取るとしよう。$\omega$の事前分布とシグナル$s_i | \omega$の条件付き確率分布が共有知識だとする。仮にエージェント$i$が$s_i$を真実申告していたら、リファレンスとなるエージェント$j$のシグナルについての$i$の事後確率$P(s_j|s_i)$を算出できるので、$j$の申告に従ったプロパー・スコアリング・ルールをつかって報酬を渡せる[...うむむむ...混乱してきた...]。こうすると、他の人が真実申告しているという前提の下で、$i$にとって報酬の期待値を最大化するのは真実申告だと言うことになる(ただしほかにも均衡がある)。この方向の提案として、Jurca & Faltings (2006, Proc.EC06)、Jurca & Faltings (2007, Proc.EC07)、Goel, Reeves, & Pennock(2009, Proc.EC09)がある。
- ピア予測手法は共通の事前分布が共有知識だという前提を持っている。いっぽうPrelec(2007)のベイジアン自白剤はもう少し弱い仮定を置いていて、事前分布は未知でよい。なおベイジアン自白剤では報酬が最後まで決まらないんだけど、Jurca&Flatings(2006)による提案もある(真実申告がベイジアンナッシュ均衡なわけじゃないけど、投票結果が真値に収束する)。
- 真実申告じゃなくて、代表的サンプルを抽出するメカニズム、という発想もある。Lambert & Shoham (2008 Proc.WINE08, 2009 Proc.EC09)。[←これも面白そう...]
表出性と計算的扱いやすさ
- 組み合わせビッドを許すと表出性が高まる。実施例もいくつかある。計算負荷は高くなるかもしれないけど。
- その特殊ケースとして... (1)boolean betting, (2)tournament betting, (3)permutation betting, (4)taxonomy betting. [あんまり関心ないのでパス]
...細かいところはちゃんと読んでないけど、読了にしておく。一番の収穫は、予測市場とベイジアン自白剤のようなタイプの手法とを、メカニズムデザインという視点から統一的に捉えているところ。勉強になりましたです。そうか、後者はピア予測システムって呼べばいいのか。
細かいことだけど、LMSRとかで使う「実現したら一ドル配当」型の証券のことをArrow-Debreu contractというらしい。へー。
論文：予測市場 - 読了：Chen & Pennock (2010) 予測メカニズム・レビュー