オークション理論(auction theory)とは、競売の方式ごとに、自分だけが知る評価値をもつ入札者の均衡での入札と売り手の収入を計算し、方式を比べる数理である。第二価格入札では評価値どおりに入札することが支配戦略である。評価値が独立で入札者が危険中立なら、均衡での支払いの期待値は勝つ確率の関数と評価値 $0$ の人の期待効用だけで決まり(収入同値定理)、評価値が同じ分布に従えば第一価格・第二価格・全員払いなどの方式で収入の期待値は等しく、2 番目に高い評価値の期待値になる。この関係から第一価格入札などの均衡入札が計算でき、最低価格を付けたり入札者が危険回避的だったりすると同値は成り立たない。
オークション理論(auction theory)とは、競売の方式ごとに、入札者がどう入札するか(均衡)と、売り手がいくら受け取るか(収入)を計算し、方式を比べる数理である。各入札者は品物に自分だけが知る評価値をもち、ほかの人の評価値は確率分布としてしか知らない。この不確かさのもとでの戦略の釣り合いを、ゲーム理論 の Bayes 版の Nash均衡 として扱う。
典型的な問いは「最高額の入札者が自分の入札額を払う方式(第一価格)と、2 番目の入札額を払う方式(第二価格)では、売り手の収入はどちらが多いか」である。第一価格では人は入札額を評価値より下げ、第二価格では評価値どおりに入札するので、どちらとも言えそうに見える。答えは、評価値が独立で同じ分布に従い、入札者が危険中立なら収入の期待値は同じ、というものである(収入同値定理)。
この記事では、第二価格入札で評価値どおりに入札することが支配戦略であること(thm-at-truthful)と、均衡での支払いが勝つ確率だけで決まること(thm-at-re、収入同値定理)を証明し、それを使って各方式の均衡入札と収入を計算する手順を示す。最適な方式の設計(最低価格の選び方、Myerson の最適オークション)と VCG 機構は メカニズムデザイン で扱う。
品物 1 つを $n\ge2$ 人の入札者に売る。各入札者 $i$ は非負の額 $b_i$ を封をして出す。最高額の入札者が品物を得る(同額のときは等確率のくじで決める)。支払いの規則により、次の方式がある。
競り下げ式では、各人は「価格が $b$ まで下がったら手を挙げる」と事前に決めることしかできず、勝者は自分の $b$ を払うので、第一価格入札と戦略として同じものである。競り上げ式では、価格が評価値より低い間は残り、超えたら降りることが支配戦略で、勝者はおおよそ 2 番目の人が降りた価格を払うので、第二価格入札に近い(KP17 §14.1, p. 234 と p. 237)。
次の (i)〜(iii) を仮定する。
(i) は、ほかの人の評価値を知っても自分の評価値が変わらないことを含む。油田の採掘権のように品物の価値が共通の未知の量に依存する場合は (i) が成り立たず、以下の結果はそのままでは使えない。
評価値は独立で同じ分布 $F$ に従い、$F$ は $[0,h]$($h\le\infty$)の上で連続かつ狭義増加、$F(0)=0$ で、平均は有限とする。$G(v)=F(v)^{n-1}$ は、ほかの $n-1$ 人の評価値の最大値 $Y$ の分布関数である。表の最後の列は、評価値が $[0,1]$ の一様分布のときの値である($G(v)=v^{n-1}$)。
| 方式 | 対称な均衡入札 $\beta(v)$ | 支払いの期待値 $p(v)$ | 一様分布での $\beta(v)$ と収入 | 根拠 |
|---|---|---|---|---|
| 第二価格 | $v$(支配戦略) | $\int_0^vw\,dG(w)$ | $v$、$\frac{n-1}{n+1}$ | thm-at-truthful、cor-at-iid |
| 第一価格 | $v-\frac1{G(v)}\int_0^vG(w)\,dw$ | 同上 | $\frac{n-1}nv$、$\frac{n-1}{n+1}$ | prop-at-first-price |
| 全員払い | $vG(v)-\int_0^vG(w)\,dw$ | 同上 | $\frac{n-1}nv^n$、$\frac{n-1}{n+1}$ | prop-at-first-price |
| 競り下げ式 | 第一価格と同じ | 同上 | 第一価格と同じ | 戦略として同じ(def-at-auction のあと) |
| 競り上げ式 | 価格が $v$ に達したら降りる | 同上 | 第二価格と同じ | KP17 §14.1, p. 234(この記事では証明しない) |
どの方式でも支払いの期待値 $p(v)$ が同じになることが thm-at-re の内容で、売り手の収入の期待値はどれも 2 番目に高い評価値の期待値 $E[V_{(2)}]$ である。
図: 横軸は評価値 v(0 から 1)、縦軸は入札額。入札者 2 人で評価値が一様分布のときの、第二価格の均衡入札 v の直線、第一価格の均衡入札 v/2 の直線、全員払いの均衡入札 v²/2 の曲線が描かれている。点線は 3 方式に共通の支払いの期待値 v²/2 で、全員払いの曲線と重なる。
第二価格入札で、評価値 $v$ の入札者にとって、$v$ を入札することは弱い意味の支配戦略である。すなわち、ほかの人の入札がどうであっても、$v$ を入札したときの効用は、ほかのどの額 $b$ を入札したときの効用以上である。さらに $b\ne v$ なら、$v$ を入札したほうが効用が真に大きくなるほかの人の入札の組がある。
ほかの人の入札額の最大値を $m$ とする。どの額を入札しても、結果は「勝って $m$ を払う(効用 $v-m$)」か「負けて払わない(効用 $0$)」のどちらかである(同額でくじになる場合もこのどちらかになる)。したがって、どの入札の効用も $\max(v-m,0)$ 以下である。
$v$ を入札すると、$v>m$ なら勝って効用 $v-m$、$v< m$ なら負けて効用 $0$、$v=m$ なら勝っても負けても効用 $0$ である。いずれの場合も効用は $\max(v-m,0)$ に等しく、上限に達している。
$b>v$ なら、$v< m< b$ となる $m$ をとると、$b$ では勝って効用 $v-m< 0$、$v$ では $0$ である。$b< v$ なら、$b< m< v$ となる $m$ をとると、$b$ では負けて $0$、$v$ では $v-m>0$ である。$\square$
結果は評価値の分布にも、ほかの人が合理的かどうかにもよらない。入札者に評価値を正直に申告させる性質を 誘因両立性(incentive compatibility)という。また効用の比較は「勝って $v-m$」と「$0$」の大小だけで決まるので、(ii) の危険中立の仮定も要らない。これらは KP17 Theorem 14.2.3(p. 237)にあり、この方式の利点は Vickrey が 1960 年に見いだした(KP17 p. 237)。
def-at-ipv の (i)(ii) のもとで、入札者 $i$ を 1 人固定し、ほかの人の戦略を固定する。添字 $i$ を省いて $a(w)$、$p(w)$、$u(w\mid v)$ と書き、評価値のとりうる範囲を $J=[0,h]$($h=\infty$ なら $J=[0,\infty)$)とする。
1. $u(w\mid v)=v\,a(w)-p(w)=u(w)+(v-w)a(w)$ である。$u(v)\ge u(w\mid v)$ と、$v,w$ を入れ替えた $u(w)\ge u(v\mid w)=u(v)+(w-v)a(v)$ を合わせると
$$
(v-w)\,a(w)\le u(v)-u(w)\le(v-w)\,a(v)
$$
を得る。$v>w$ なら両端を $v-w$ で割って $a(w)\le a(v)$ だから、$a$ は広義単調増加である。
次に $v\in J$、$v>0$ を固定し、$0=z_0< z_1<\dots< z_N=v$ を幅 $v/N$ の等分点とする。上の不等式を $(v,w)=(z_k,z_{k-1})$ に当てて $k=1,\dots,N$ について足すと、
$$
\sum_{k=1}^N(z_k-z_{k-1})\,a(z_{k-1})\le u(v)-u(0)\le\sum_{k=1}^N(z_k-z_{k-1})\,a(z_k)
$$
である。$a$ は単調で有界($0\le a\le1$)なので Riemann 積分可能であり、両端は $N\to\infty$ で $\int_0^va(z)\,dz$ に収束する(両端の差は $\frac vN(a(v)-a(0))\le\frac vN$ である)。よって $u(v)=u(0)+\int_0^va$ で、$p(v)=v\,a(v)-u(v)$ から $(\ast)$ の第 2 式を得る。
2. $(\ast)$ の第 2 式から $u(w)=w\,a(w)-p(w)=u(0)+\int_0^wa$ である。よって
$$
u(v)-u(w\mid v)=u(v)-u(w)-(v-w)a(w)=\int_w^va(z)\,dz-(v-w)\,a(w)
$$
である。$v>w$ なら右辺は $\int_w^v\bigl(a(z)-a(w)\bigr)dz\ge0$、$v< w$ なら $\int_v^w\bigl(a(w)-a(z)\bigr)dz\ge0$ である。
収入について。 売り手の収入の期待値は $\sum_iE[p_i(V_i)]$ で、各 $p_i$ は $a_i$ と $u_i(0)$ だけで決まるから、これらが同じなら収入の期待値も同じである。$\square$
この定理は KP17 Theorem 14.4.2(p. 240)に、対称な均衡の形で述べられている。上の証明は微分可能性を仮定しない。$a$ は単調なので、凸関数 $u$ の 劣微分 の元になっていると見ることもできる($u$ は $a$ の積分で、$a$ が単調増加だから凸)。
評価値が独立で同じ分布 $F$ に従い($F$ は $[0,h]$、$h\le\infty$ の上で連続かつ狭義増加、$F(0)=0$、平均は有限)、対称な均衡 $\beta$ が狭義単調増加で、最高額の入札者が勝ち、$u(0)=0$ とする。ほかの $n-1$ 人の評価値の最大値を $Y$、その分布関数を $G=F^{n-1}$ とすると、
$$
a(v)=G(v),\qquad p(v)=\int_0^v\bigl(G(v)-G(w)\bigr)dw=\int_0^vw\,dG(w)=E[Y;\,Y\le v]
$$
である。売り手の収入の期待値は、どの方式でも 2 番目に高い評価値 $V_{(2)}$ の期待値 $E[V_{(2)}]$ に等しい。
$\beta$ が狭義単調増加で $F$ が連続だから、同額は確率 $0$ で起こり、評価値 $v$ の人は $Y< v$ のとき、そのときに限り勝つ。よって $a(v)=P(Y< v)=G(v)$ である。$(\ast)$ から $p(v)=vG(v)-\int_0^vG=\int_0^v(G(v)-G(w))\,dw$ で、部分積分により $\int_0^vw\,dG(w)$ に等しい。これは $Y\le v$ のときに $Y$ を払う第二価格入札の支払いの期待値 $E[Y;\,Y\le v]$ である。第二価格入札で全員が評価値どおりに入札すると、売り手は 2 番目に高い評価値を受け取るので、収入の期待値は $E[V_{(2)}]$ である。ほかの方式でも $a$ と $u(0)=0$ が同じだから、thm-at-re により収入の期待値は同じである。$\square$
$E[\,\cdot\,;\,Y\le v]$ は事象 $Y\le v$ の上だけで積分した期待値で、条件付き期待値を使えば $G(v)E[Y\mid Y\le v]$ である(KP17 Corollary 14.4.4, p. 240)。一様分布では $V_{(2)}$ の期待値は $\frac{n-1}{n+1}$ である(順序統計量)。
cor-at-iid は「均衡なら支払いはこうなる」と言うだけで、均衡の存在は言わない。各方式の支払いの規則と $p(v)$ を突き合わせて $\beta$ の候補を出し、thm-at-re の 2 で均衡であることを確かめる。
cor-at-iid の分布の条件のもとで、$I(v)=\int_0^vG(w)\,dw$ とおく。
候補の出し方。 第一価格入札では勝ったときだけ入札額を払うので $p(v)=G(v)\beta(v)$ で、cor-at-iid の $p(v)=vG(v)-I(v)$ と等しいとおくと 1 の式になる。全員払い入札では $p(v)=\beta(v)$ なので 2 の式になる。
単調性。 $0\le v< v'$ とする。$G$ は $[0,h]$ で狭義増加、$v>0$ で $G(v)>0$ である。$I(v')=I(v)+\int_v^{v'}G\le I(v)+(v'-v)G(v')$ だから、第一価格の $\beta$ について $v>0$ なら
$$
\beta(v')-\beta(v)=(v'-v)-\frac{I(v')}{G(v')}+\frac{I(v)}{G(v)}\ge I(v)\Bigl(\frac1{G(v)}-\frac1{G(v')}\Bigr)>0
$$
である($I(v)>0$)。$v=0$ なら $\beta(v')=\frac1{G(v')}\int_0^{v'}(G(v')-G(w))\,dw>0=\beta(0)$ である。全員払いの $\beta$ についても同じ評価から
$$
\beta(v')-\beta(v)=v'G(v')-vG(v)-\int_v^{v'}G\ge v\bigl(G(v')-G(v)\bigr)
$$
で、$v>0$ なら正、$v=0$ なら $\beta(v')=\int_0^{v'}(G(v')-G(w))\,dw>0$ である。
値域の中の入札。 全員が狭義単調増加の $\beta$ を使うので、cor-at-iid の計算と同じく $a(w)=G(w)$ であり、$p$ は作り方から $(\ast)$ をみたす。$u(0)=0$ でもある。thm-at-re の 2 により、$\beta$ の値域の入札 $\beta(w)$ に替えても得をしない。
値域の外の入札。 入札額は非負で $\beta(0)=0$、$\beta$ は連続なので、値域の外は $\beta$ の上限 $\bar b=\sup\beta$ 以上の額である。$\bar b$ 以上を入札すると確実に勝ち、その額を払う(全員払いでも同じ)ので、効用は $v-b\le v-\bar b$ である。$h< \infty$ なら $\bar b=\beta(h)$ で、$\beta(h)$ の入札も確実に勝つから効用 $v-\bar b$ は $u(h\mid v)\le u(v)$ である。$h=\infty$ なら $u(w\mid v)\to v-\bar b$($w\to\infty$)で、やはり $v-\bar b\le u(v)$ である。$\square$
一様分布では $G(v)=v^{n-1}$、$I(v)=v^n/n$ で、第一価格の $\beta(v)=\frac{n-1}nv$、全員払いの $\beta(v)=\frac{n-1}nv^n$ を得る(KP17 §14.4.3, p. 241 と一致する)。第一価格入札の均衡入札は $\beta(v)=E[Y\mid Y< v]$ とも書け、「自分が勝つとき、2 番目の人の評価値の条件付き期待値を入札する」と読める。
評価値が独立同分布 $F$ で、最高額の入札者が勝つ方式の対称な均衡と収入は、次の手順で求める。
評価値は $[0,1]$ の一様分布、$n=3$ とする。
使う公式:prop-at-first-price の 1、cor-at-iid。
答え:$\beta(v)=\frac23v$(評価値 $0.9$ の人は $0.6$ を入札する)。収入の期待値は $\frac12=0.5$ で、第二価格入札の $E[V_{(2)}]=\frac12$ と一致する。
手順 1:$G(v)=v^2$、$I(v)=v^3/3$。手順 2:$p(v)=v^3-\frac{v^3}3=\frac23v^3$。手順 3・4:$v^2\beta(v)=\frac23v^3$ から $\beta(v)=\frac23v$。手順 6:$3E[\frac23V^3]=2\cdot\frac14=\frac12$。直接には、勝者の評価値は最大値 $V_{(1)}$(期待値 $\frac34$)で、支払いは $\frac23V_{(1)}$ だから $\frac23\cdot\frac34=\frac12$。
評価値は平均 $1$ の指数分布 $F(v)=1-e^{-v}$($v\ge0$)、$n=2$ とする。
使う公式:prop-at-first-price の 1($h=\infty$ の場合)。
答え:$\beta(v)=1-\dfrac v{e^v-1}$。$\beta(1)=1-\frac1{e-1}\approx0.418023$。入札額は $1$ を超えない。収入の期待値は $E[\min(V_1,V_2)]=\frac12$。
$G(v)=1-e^{-v}$、$I(v)=v-(1-e^{-v})$。$\beta(v)=v-\frac{v-1+e^{-v}}{1-e^{-v}}=1-\frac{ve^{-v}}{1-e^{-v}}=1-\frac v{e^v-1}$。$\frac v{e^v-1}$ は $v>0$ で正かつ減少で、$v\to\infty$ で $0$ に近づくので、$\beta$ は狭義増加で上限 $\bar b=1$ をもつ。$\min(V_1,V_2)$ は平均 $\frac12$ の指数分布である。
評価値は $[0,1]$ の一様分布、$n=2$ とする。
使う公式:prop-at-first-price の 2。
答え:$\beta(v)=\frac{v^2}2$(評価値 $0.8$ の人は $0.32$ を入札し、負けても払う)。収入の期待値は $2E[V^2/2]=\frac13\approx0.333333$ で、第二価格入札と一致する。
$G(v)=v$、$I(v)=v^2/2$、$\beta(v)=v^2-\frac{v^2}2=\frac{v^2}2$。$E[V^2]=\frac13$ なので $2\cdot\frac12\cdot\frac13=\frac13$。$E[V_{(2)}]=E[\min(V_1,V_2)]=\frac13$。
評価値の分布は $F(v)=v^2$($0\le v\le1$)、$n=2$ とする。
使う公式:prop-at-first-price の 1、cor-at-iid。
答え:$\beta(v)=\frac23v$。収入の期待値は $\frac8{15}\approx0.533333$。
$G(v)=v^2$、$I(v)=v^3/3$、$\beta(v)=v-\frac v3=\frac23v$。勝者の評価値 $\max(V_1,V_2)$ の分布関数は $v^4$ で期待値は $\frac45$、支払いは $\frac23\cdot\frac45=\frac8{15}$。第二価格入札の側では、$P(\min(V_1,V_2)>t)=(1-t^2)^2$ から $E[\min]=\int_0^1(1-t^2)^2dt=1-\frac23+\frac15=\frac8{15}$ で一致する。
thm-at-re と cor-at-iid を使ってよい条件は次のとおりである。
入札者 2 人、評価値は $[0,1]$ の一様分布とする。各行は条件をちょうど 1 つ外す。
| 外す条件 | 例 | 成り立たなくなること |
|---|---|---|
| (iii) 同じ配分 | 第二価格入札に最低価格 $\frac12$ を付ける(2 人とも $\frac12$ 未満なら売らない) | 収入は $\frac5{12}\approx0.416667$ で、$\frac13$ と異なる |
| (iv) 同じ $u(0)$ | 第二価格入札で、参加者全員に $c>0$ を配る | 配分は同じだが $u(0)=c$ で、収入は $\frac13-2c$ |
| (ii) 危険中立 | 効用が $x\ge0$ で $x^\rho$($\rho=\frac12$)、$x<0$ で負の値になる入札者の第一価格入札 | 均衡は $\beta(v)=\frac v{1+\rho}=\frac23v$ で、収入は $\frac49\approx0.444444>\frac13$ |
| thm-at-truthful の支払いの規則 | 第一価格入札で評価値どおりに入札する | 勝っても効用 $0$。相手が $\frac w2$ を入札するとき $\frac v2$ を入札すれば期待効用 $\frac{v^2}2>0$ |
1 行目:2 人とも $\frac12$ を超える(確率 $\frac14$)と、低いほうの評価値を払い、その条件付き期待値は $\frac12+\frac12\cdot\frac13=\frac23$。ちょうど 1 人が超える(確率 $\frac12$)と $\frac12$ を払う。収入は $\frac14\cdot\frac23+\frac12\cdot\frac12=\frac5{12}$。評価値の低い買い手が買えなくなるので配分が変わり、thm-at-re の前提 (iii) が成り立たない。最低価格の選び方は メカニズムデザイン で扱う。
3 行目:相手が $\beta(w)=\frac w{1+\rho}$ を入札するとき、$b\le\frac1{1+\rho}$ を入札して勝つ確率は $(1+\rho)b$ で、期待効用は $\varphi(b)=(1+\rho)b(v-b)^\rho$($0\le b\le v$)。$b>v$ の入札は、勝つと効用が負になるので期待効用が $0$ 以下で、最良にならない。$\varphi'(b)=(1+\rho)(v-b)^{\rho-1}\bigl((v-b)-\rho b\bigr)$ は $b< \frac v{1+\rho}$ で正、それより大きい $b$ で負なので、$b=\frac v{1+\rho}$ が最良である。$\frac1{1+\rho}$ より大きい入札は、確実に勝つ $\frac1{1+\rho}$ の入札より払う額が多いだけである。収入は $E[\max(V_1,V_2)]/(1+\rho)=\frac23\cdot\frac23=\frac49$。第二価格入札では thm-at-truthful が効用の形によらず成り立つので収入は $\frac13$ のままであり、危険回避的な入札者のもとでは第一価格入札の収入のほうが大きい。
4 行目:相手が $\frac w2$ を入札すると、$\frac v2$ の入札が勝つ確率は $P(\frac W2< \frac v2)=v$ で、勝ったときの効用は $v-\frac v2=\frac v2$ だから、効用の期待値は $v\cdot\frac v2=\frac{v^2}2$ である。評価値どおりの入札では、勝っても負けても効用は $0$ である。
非対称な入札者(評価値の分布が人によって異なる場合)では、第一価格入札で評価値の最も高い人が勝つとは限らず、(iii) が成り立たず収入が一致しないことがある(KP17 Remark 14.6.3, p. 246。この記事では証明しない)。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 第一価格入札でも評価値どおりに入札するのが最適だとする | 評価値より下げて入札する。一様分布で $n$ 人なら $\frac{n-1}nv$ | 評価値どおりでは勝っても効用 $0$(ex-at-table の 4 行目) |
| 収入同値を「どの方式でも収入は同じ」と読む | 勝つ確率の関数と $u(0)$ が同じ方式どうしでだけ同じ | 最低価格を付けると変わる(ex-at-table の 1 行目) |
| 2 番目の額しか払わないので、第二価格入札の収入は第一価格入札より少ないとする | 独立同分布・危険中立なら収入の期待値は同じ | 第一価格では入札額が下がる(cor-at-iid) |
| $p(v)$ を「勝ったときの支払い」と読む | $p(v)$ は勝ち負けを込めた支払いの期待値。勝ったときの支払いの期待値は $p(v)/G(v)$ | 全員払いでは負けても払う |
| 手順 5 を省き、$\beta$ の候補をそのまま均衡とする | 狭義単調増加と値域の外の入札を確かめる | thm-at-re の 2 は値域の中の入札しか比べない |
収入同値定理は、評価値の分布と配分が決まれば支払いが決まるという「支払いの公式」であり、メカニズムデザイン の Myerson の補題と同じ構造をもつ。そこでは配分の規則を設計の対象にし、仮想評価値を最大にする配分で収入の期待値を最大にする最適オークションを導く。複数の品物を売る場合や、評価値が独立でない場合(価値が共通の未知の量に依存する場合)は、この記事の枠の外である。
模型、第二価格入札の誘因両立性、収入同値定理、第一価格と全員払いの均衡入札、最低価格の例、非対称な場合の注意は KP17 第 14 章(§14.1, p. 234、Theorem 14.2.3, p. 237、Theorem 14.4.2 と Corollary 14.4.4, p. 240、§14.4.3, p. 241、§14.5, p. 243、Remark 14.6.3, p. 246)による。thm-at-re の 1 の Riemann 和による証明、prop-at-first-price の単調性と値域の外の入札の扱い、危険回避的な入札者の例は、この記事の組み立てである。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する