予測市場におけるマーケットスコアリングルールについて(LMSRとLS-LMSRの説明と描画)

予測市場よりも遥か以前からスコアリングルールと呼ばれるものが存在した。 これは社会的意思決定理論の産物で、投票内容をどのようにアウトカム(投票結果)にマッピングするかを定義した関数。例えば

などがある。

しかし単なる投票だと、いずれの場合でも人数が増えるほど「投票者の無気力化(Voter Apathy)」 という問題が発生する。

予測市場ならばこの問題を乗り越えられるが、代わりに「単なるオッズ比では人数が少ないほど賭けるインセンティブが少ないため誰も最初の賭けをしたがらない」 という問題がある。 また、原理上「自分が他人よりもよく知っていると思っていること」に対してしか賭けが成立しないため、さらに参加者が少なくなる傾向がある。

マーケットスコアリングルールはこの両者の利点を橋渡しするためのもので、具体的にはコスト関数(あるいはスコア関数)と呼ばれるものを使用する。

Truthcoinでは(従来の多くの予測市場と同様に)LMSRと呼ばれるコスト関数を用いている

コスト関数とは

コスト関数とは、特定の証券を一定量買うのに必要な資金量を計算するための関数で、$C$で表される。

  • $o \in O$ ... 未来に発生する特定の事象(賭けの対象)
  • $q_o$ ... 現時点で市場に出回っている$o$の証券($o$が発生したときのみ1ドル、そうでなければ0ドルの価値を持つ)の総数。Securtyと呼ばれることもある(理由は知らない)
  • $r$ ... $O$次元の「購入ベクトル」、どの事象の証券をどれだけ買うかを表した物

とすると、購入時のコストは

$C(q + r) - C(q)$

対数マーケットスコアリングルール、Logarithmic Market Scoring Rule(LMSR)について

賭ける内容が二択の場合

例えばバイナリのDecisionの場合、以下のコスト関数を用いる。

$$C(q_0, q_1) = b * \ln(e^{q_0/b} + e^{q_1/b})$$

ただし

  • $b$ ... Authorが指定する流動性パラメータ。高いほど市場開始時の流動性を担保できる(誰もベットに参加しないことを避けられる)が、Marketの作成にあたってAuthorの払うコストが大きい
  • $e$ ... 自然対数の底

例えば0のアウトカムを13単位買いたい場合にかかる費用は$C(q_0+13, q_1)$ 1を150単位売りたい場合は$C(q_0, q_1-150)$がその費用となる。

複数次元のDecisionにおいて特定の次元のみを「見て」投票したい場合でも、十分な正確さとIncentive Compatibilityが見込める点にLogを使用するメリットがある。

賭ける内容がカテゴリカル(三択以上の場合)

$$C(q) = b \log \sum_{o \in O}e^{q_0/b}$$

ただし、$O$は取りうる全ての状態(アウトカム)で、$o$は購入対象

アウトカム$q_0$を$r$株買う際のコストは $C(q + r) - C(q) $となる。rが十分小さい時、コスト関数の導関数が実際にかかる費用になる。

見てわかるように、コスト関数が購入する対象だけに依存しており、マーケット全体の状態に依存しないので、複雑なマーケットでも計算が楽、あるいは購入時の認知コストが少ない

logを取る前の指数部分がかなり大きな値になる場合があるので、数値計算上の面倒が生じる可能性がある。

価格関数

特定の時刻におけるアウトカム$o$の証券の価格を$p_o (0 \le p_o \le 1 )$とすると、これは$q_o$の関数であり計算式は価格関数(price function)と呼ばれる。 LMSRの場合、価格関数は以下

$$p_o(q) = \frac{\partial{C(q)}}{\partial{q_o}} = \frac{e^{q_o/b}}{\sum_{o' \in O}e^{q_o'/b}}$$

LMSRは全体で微分可能なので、価格計算においても扱い安いことが普及の一因となっている。

また、$q_o$の合計は1(ドル)になるので、確率分布として扱え、「事象$o$の発生確率に関する現時点での市場の信念」として扱うことができる。

LMSRを用いた場合、マーケット作成者が失う金額の上限は$b\log|O|$となる。

代替案

LMSRは予測市場で最も一般的に使用されているもので、たとえば すでに以下で使用されている。

流動性パラメータ$b$をダイナミックに変更することで効率性を高めることができるという研究も存在する。

代替案には

などがある。(が、LMSRほどは使われていないようだ。)

LMSRの描画

二択の場合のコスト関数を描画する

interactiveに$\alpha$, $\beta$を変更できるようにしてありますが、htmlにレンダリングすると何故か消えてしまうので、興味のある人はGithubからソースコードをダウンロードしてください。そのうちfixするかもしれません。

In [1]:
import numpy as np
# for regular plotly ctions
import plotly.plotly as py
import plotly    

import plotly.graph_objs as go
from plotly.offline import init_notebook_mode, download_plotlyjs

# for widgets
from ipywidgets import interact, interactive
/opt/conda/lib/python3.5/site-packages/matplotlib/font_manager.py:273: UserWarning:

Matplotlib is building the font cache using fc-list. This may take a moment.

/opt/conda/lib/python3.5/site-packages/matplotlib/font_manager.py:273: UserWarning:

Matplotlib is building the font cache using fc-list. This may take a moment.

In [2]:
def LMSR(q0, q1, b):
    return b * np.log(np.power(np.e, (q0 / b)) + np.power(np.e, (q1 / b)))

x, y = np.meshgrid(np.linspace(0, 200, 32), np.linspace(0, 200, 32))

print(LMSR(0,0, 5))
3.4657359028
In [6]:
# setup plotly
init_notebook_mode(connected=True)
In [11]:
@interact(b=(0.5, 30.0, 1))
def plot(b=1):
    z = LMSR(x, y, b)
    trace1 = go.Surface(x = x, y = y, z=z, name="Cost function")     
    data=[trace1]
    layout = go.Layout(
        title='Cost function',

        margin=dict(
            l=0,
            r=0,
            b=100,
            t=100
        ),
        xaxis = dict(
            title="amount x bought",
        ),
        yaxis = dict(
            title="amount y bought",
        )
    )
    fig = go.Figure(data=data, layout=layout)
    URL = plotly.offline.iplot(fig, filename='Costfunction-3d-surface.html')

ある事象が起こると「Yes」証券は1ドル、「No」証券は0ドルになり、起こらなければ逆の価値を持つとする。

  1. x軸 ... 現時点で市場にある「Yes」証券の量($q_{yes}$)
  2. y軸 ... 現時点で市場にある「No」証券の量($q_{no}$)

b(liquidity係数)を変えると関数がなめらかになっていることがわかる。 先述のように購入にかかるコストはコスト関数から以下の式で直接計算できる。

$$C(q + r) - C(q)$$

描画してみる。こちらの方がわかりやすいかもしれない。

In [5]:
@interact(b=(0.5, 30.0, 1), amount_to_buy_x=(-30, 50, 10))
def plot(b=1, amount_to_buy_x = 10):
    z = LMSR(x + amount_to_buy_x, y, b) - LMSR(x, y, b)
    trace1 = go.Surface(x=x,y=y, z=z)     
    data=[trace1]
    layout = go.Layout(
    title='Cost to buy',
    margin=dict(
        l=0,
        r=0,
        b=0,
        t=0
        )
    )
    fig = go.Figure(data=data, layout=layout)
    plotly.offline.iplot(fig, filename='Costfunction-3d-surface')

$b$が大きいほど、関数がなめらかになり、購入に対する価格の反応が鈍くなることがわかる。

また、関数を微分すると一単位だけ購入した際の曲線と一致する。

In [8]:
@interact(b=(0.5, 30.0, 1))
def plot(b=1):
    z = LMSR(x, y, b)
    U,V = np.gradient(z)
    trace1 = go.Surface(x=x,y=y, z=U)     
    data=[trace1]
    layout = go.Layout(
    title='Cost to buy',
    margin=dict(
        l=0,
        r=0,
        b=0,
        t=0
        )
    )
    fig = go.Figure(data=data, layout=layout)
    plotly.offline.iplot(fig, filename='Cost_to_by_x-3d-surface')

Liqudity sensitive LMSR(LS-LMSR)

Augurで導入が検討されているコスト関数

上の図からわかるように、LMSRは市場に出回っている証券の総量($x+y$)と、関数の滑らかさに関係がない。 したがって

bが大きすぎると、参加者全員がbetした後でも証券ごとの価格がほとんど変わらない(最後までほぼ1:1のままである)危険がある。 bが小さすぎると、価格がめちゃくちゃに動いてしまう。

というトレードオフが生じ、最適な$b$は「そのマーケットがどれだけ人気があるか」に依存するので簡単に決めることができない。 そこで、LS-LMSRでは証券の総量に応じて$b$を決める。

具体的にはハイパーパラメータ$\alpha$を導入し

$b(q) = \alpha\sum_{i}q_i$

とする。描画してみる。

In [9]:
def LSLMSR(q0, q1, a):
    b = a * (q0 + q1)
    return LMSR(q0,q1,b)

    
@interact(a=(0.1, 30.0, 1))
def plot(a=1):
    z = LSLMSR(x, y, a)
    trace1 = go.Surface(x=x,y=y, z=z)     
    data=[trace1]
    layout = go.Layout(
    title='Cost to buy',
    margin=dict(
        l=0,
        r=0,
        b=0,
        t=0
        )
    )
    fig = go.Figure(data=data, layout=layout)
    plotly.offline.iplot(fig, filename='Cost_to_by_x-3d-surface')
/opt/conda/lib/python3.5/site-packages/ipykernel/__main__.py:2: RuntimeWarning:

invalid value encountered in true_divide

このままだとわかりにくいので、微分して価格関数をみる。

In [8]:
@interact(a=(0.1, 30.0, 1))
def plot(a=1):
    z = LSLMSR(x, y, a)
    U,V = np.gradient(z)
    trace1 = go.Surface(x=x,y=y, z=U)     
    data=[trace1]
    layout = go.Layout(
    title='Cost to buy',
    margin=dict(
        l=0,
        r=0,
        b=0,
        t=0
        )
    )
    fig = go.Figure(data=data, layout=layout)
    plotly.offline.iplot(fig, filename='Cost_to_by_x-3d-surface')
/opt/conda/lib/python3.5/site-packages/ipykernel/__main__.py:2: RuntimeWarning:

invalid value encountered in true_divide

価格($x+y$)が低いほど、購入に対する値動きが激しいように設定されていることがわかる。

$\alpha$が小さいほど「証券の総量が増えても、価格の変動のしやすさ(volatility)がなかなか変わらない」傾向がある。 したがって$\alpha$は直感的にはマーケットの「活力(vig)」として捉えることができる。

LMSRでは各証券の発行量のに基づいて値段が決まるが、LS-LMSRでは比率に基づいて決まる。

価格の合計値の上限

通常、裁定取引による利益を抑えるため、自動マーケットメイカーの提供する証券価格の合計は1になることが望ましいとされているが、LS-LMSRではこれを僅かに上回る可能性がある。具体的には $$ a \le \sum_iq_i \le 1+\alpha n * logn $$ となる。

このおかげで($b$と違って$a$は)あらかじめ決めておきやすいことがわかる。というのも、「bounded lossをいくらにしたいか」という観点から決めることができるためだ。

$\alpha$決定の自動化

$\alpha$が大きいほどマーケット作成者の持っていく手数料が大きいが、大きすぎるとトレードしにくくなる。

欠点

流通する証券の量が十分増えた後で、一気に均衡が崩れると(i.e. 新しい情報が周知され、人々の信念が大幅に移動すると)その反応が遅くなる。 Bayesian Market Makerならばこの問題は存在しないが、代わりにBounded Lossが存在しないという欠点がある。

In [ ]: