« 読了：Chen, et al.(2010) LMSR予測市場で他人を騙す方法とその防止策 (を考えたが貴様ら凡人にはわかるまい) | メイン | 読了：Peters, et al. (2007) 逐次凸パリ・ミュチュエル・メカニズム »
2015年11月24日 (火)
読んだとは到底いえないが、諦めをつけるために記録しておく。
Agrawal, S., Delage, E., Peters, M., Wang, Z., Ye, Y. (2011) A unified framework for dynamic prediction market design. Operations Research, 59(3), 550-568.
予測市場、金融市場、賭け市場などなど、「ある出来事が起きたらある金を払う」タイプの市場(contingent claim markets)は数多い。連続的ダブル・オークションとかだと市場が薄いときに流動性がなくなっちゃうので、自動マーケット・メーカが使われることが多い。いろんなメカニズムが提案されている。コール・オークションに由来するメカニズム(SCPM)や、スコアリング・ルールに由来するメカニズム(LMSR)があるが、「敗者が払った金を勝者に分配する」という意味でいずれもパリ・ミュチュエルである。[←他の論文でもそうなんだけど、この著者らはパリ・ミュチュエルという言葉をかなり広い意味で使っているようだ]
メカニズムを比較する研究はすでにある(Chen & Pennock, 2007; Peters, Ye, & Son, 2007)。本論文は異なるメカニズムを統合するフレームワークを提案します。
メカニズム概観。以下、「ある出来事が実現したら1ドル払う」という証券について考える。
その1, マーケット・スコアリング・ルール(MSR)。
出来事$\omega$の確率推定値を$r = (r_1, r_2, \ldots, r_N)$とする。$\omega$の結果$i$が実現したときに$S=S_i(r)$となるような$S=S_1(r), S_2(r), \ldots, S_N(r)$をスコアリング・ルールという。信念の真実申告を促進するスコアリング・ルールをプロパー・スコアリング・ルールという。
Hansonの考えたMSRとは、マーケット・メーカ(MM)がまず初期確率推定値$r_0$を持っていて、取引でそれが変わるたびに、その取引を行った投資家にプロパー・スコアリング・ルールで求めたスコアを払わせる、というもの。スコアリング・ルールとしては、
対数スコアリング・ルール $S_i(r) = b \log (r_i)$
二次スコアリング・ルール $S_i(r) = 2br_i - b \sum_j r_j^2$
が用いられる。
MSRは投資家のtruthfulなbidを引き出すことが知られている[←近視眼的な投資家については、ってことなんだろうけど]。
その2, コスト関数ベースMM (Chen & Pennock, 2007)。
投資家たちが現在維持している、それぞれの状態についてのクレームの数をベクトル$q \in R^N$とする[←発行株数量のことだろうか？]。全注文$q$の合計コストを、なんらかのコスト関数$C(q)$で決める。さて、ある投資家がある注文を投げたとしよう。この注文を、状態$i$についての彼のクレームを要素$a_i$とするベクトル$a \in R^N$で表す。MMはその投資家に$C(q+a) - C(q)$を課金する。
... という枠組みで考えると、HansonのLMSRは
$ C(q) = b \log (\sum_j \exp(q_j/b))$
として表される。もっと一般的に言うと、所与のスコアリング・ルール$S$によるMSRは、以下の条件を満たすコスト関数ベースMMと等価である。
すべての$i$について$S_i(p) = q_i - C(q) + k_i$ (k_iは任意の定数)
$\sum_i p_i = 1$
すべての$i$について$p_i = \frac{\partial C}{\partial q_i}$
その3, 効用関数ベースMM (これもChen & Pennock, 2007)。
MMは最終的ペイオフ$x$について効用関数$u(x)$を持ち、市場をやっている間じゅう、主観確率分布$\theta$に基づく期待効用を一定に維持し続ける。
全状態についてのペイオフをベクトル$m$とする。$x$における$u(\cdot)$の導関数を$u'(x)$とする。状態$i$のリスク中立価格を
$p_i = \frac{\theta_i u'(m_i)}{\sum_j \theta_j u'(m_j)}$
とすると、効用$\sum_j \theta_j u(m_j)$が定数になる。
将来のペイオフに関するMMのリスク態度という観点から問題定式化した初めての提案であったが、MMはふつうそれぞれの結果の確率を知らない、という点が問題。
その4, 逐次凸パリ・ミュチュエル・メカニズム(SCPM)。
[このSCPMというモデル、全然理解できない。引用されている Peters, Ye, So (2007) もめくってみたんだけど、とてもじゃないが私の理解が及ぶところではなかった。腹が立つので全訳する]
SCPMは以下のように設計されている。投資家に、次の3つの要素を含む注文を投げるように求める: 指値 $\pi \in R$, 数量上限$l$, 注文を記述するベクトル$\vec{a}$。$a$の各要素は1(その状態を望んでいるというclaim)ないし0(望んでいないというclaim)からなる。指値とは、投資家が1株に対して払いたい最大の量を指す。数量上限とは、投資家が買いたいと思う株の最大数量を表す。マーケット・メーカは、ある新しい注文について、そのうち$x$株を承諾する、そしてそれにいくらいくら課金する、と決める。マーケット・メーカは以下の最適化問題を解くことによってこの決定を行う。
${maximize}(x,z,\vec{s}) \ \ \ \pi x - z + \sum_i \beta_i \log(s_i)$
$s.t. \ \ \ \vec{a}x + \vec{s} + \vec{q} = z \vec{e}, \ \ 0 \leq x \leq l$
パラメータ$\vec{q}$は、この新しい注文$(\pi, l, \vec{a})$が到着する前にthe traders[たぶん投資家サイド全体という意味]が持っていた株の数量を表す。新しい注文が到着するたびに、上記の最適化問題が解かれ、state prices $\vec{p}$が、the optimal-dual variables associated with the first set of constraintsとして定義される。投資家には、state priceのベクトルと実現された注文の内積$\vec{p}^T\vec{a}$が課金される。
[具体例でいこう。巨人阪神戦の賭けで考える。すでに巨人株が3枚, 阪神株が1枚売れている($q = (3,1)^T$)。で、「巨人株くれ、最大で一株あたり0.8ドル出す, 最大で3枚まで買う」という注文が届く。$\pi = 0.8, l = 3, \vec{a} = (1,0)^T$。市場運営者は、全株あわせて各銘柄について最大で$z$枚まで売ろう、と思っている。今回の売り枚数を$x$とすると、それは0以上、3以下。そして
$1 x + s_1 + 3 = z$
$0 x + s_2 + 1 = z$
あ、そうか、$s_1, s_2$は「あと何枚売れるか」を表しているのか。
その上で、以下を最大化する。
$0.8 x - z + (\beta_1 \log s_1) + (\beta_2 \log s_2)$
ってことは、$\beta_1, \beta_2$は売り控えを奨励する程度を表す係数だ。で、$0.8x$が今回の売上の最大値。$z$は最悪の場合の支払額だ。仮に$\beta_1 = \beta_2 = 1$とすると、目的変数は
$0.8 x - z + \log (z-3-x) + \log(z - 1)$
ここからがわかんないんだけど、これが常に解けるんでしょうね、きっと。で、ここからどうにかして$p$が出てくるんでしょうね、きっと。いいよもう、理系の人のいうことを信じるよ]
その他、Pennockの動的パリ・ミュチュエル市場(DPM)があるけど、最後の注文が来るまで勝ち注文の価値が決まらないという特徴があるので、以下では扱わない。
以上を統合するフレームワークとして以下を提案する。これはオリジナルのSCPMを一般化したもので、最大化する関数を
$maximize(x,z,\vec{s}) \ \ \ \pi x - z + v(\vec{s})$
としたもの。以下ではこっちをSCPMと呼ぶ。
$v(\cdot)$がなんであれ、VCG値付けスキーマの下で、SCPMメカニズムは近視眼的にtruthful biddingを許容することが証明できる。
[VCGメカニズムって、まずパレート効率的に落札者を決めて、落札者は自分の言い値じゃなくて、Vickreyオークションみたいな謎のルールで決まる謝罪料金みたいなものを払う、ってやつだよね... 駄目だ、私の能力を超えた話になってきた...]
... まだ全体の1/3くらいだけど、文字通り力尽きたので、ここからは見出しだけ。
SCPMをコスト関数ベースMMとしてみたらそのコスト関数はどうなるか。
SCPMではMMは最悪でいくら損するか。
SCPMをリスク最小化という観点から定式化するという長い長い話(全然理解できない)。
既存のメカニズムを片っ端からSCPMの特殊ケースとして位置づける。LMSRは$v(\vec{s})=-b \log (\sum_i \exp(-s_i /b )) $であるSCPMである、とか。
どんなSCPMだとどういう性質を持つか。たとえば、SCPM+VCG値付けスキーマは、真実申告性、コスト関数ベースMMとの等価性、スコアリングルールとの等価性を持つ、とか。
SCPMに基づき新たなるメカニズムを考えてみよう、とか。この辺になるともう目を通してもいない。視線がつつつーっと文面をすべっていくような感じ。
だ・め・だ。降参。これは私には無理だ。。。
正直、わからなすぎて途中で吐きそうになった。なんでこんなの読もうとしているんだ、という惨めな思いで胸が一杯だ。
論文：予測市場 - 読了：Agrawal et al.(2011) ありとあらゆる自動マーケット・メーカを統一的に説明する枠組み(ま、おまえら素人には百年経ってもわからんだろうがな)