オークション理論

同義語:auction theory

概要

オークション理論(auction theory)とは、競売の方式ごとに、自分だけが知る評価値をもつ入札者の均衡での入札と売り手の収入を計算し、方式を比べる数理である。第二価格入札では評価値どおりに入札することが支配戦略である。評価値が独立で入札者が危険中立なら、均衡での支払いの期待値は勝つ確率の関数と評価値 $0$ の人の期待効用だけで決まり(収入同値定理)、評価値が同じ分布に従えば第一価格・第二価格・全員払いなどの方式で収入の期待値は等しく、2 番目に高い評価値の期待値になる。この関係から第一価格入札などの均衡入札が計算でき、最低価格を付けたり入札者が危険回避的だったりすると同値は成り立たない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: ゲーム理論, Nash均衡, 期待値, 順序統計量

オークション理論(auction theory)とは、競売の方式ごとに、入札者がどう入札するか(均衡)と、売り手がいくら受け取るか(収入)を計算し、方式を比べる数理である。各入札者は品物に自分だけが知る評価値をもち、ほかの人の評価値は確率分布としてしか知らない。この不確かさのもとでの戦略の釣り合いを、ゲーム理論 の Bayes 版の Nash均衡 として扱う。
典型的な問いは「最高額の入札者が自分の入札額を払う方式(第一価格)と、2 番目の入札額を払う方式(第二価格)では、売り手の収入はどちらが多いか」である。第一価格では人は入札額を評価値より下げ、第二価格では評価値どおりに入札するので、どちらとも言えそうに見える。答えは、評価値が独立で同じ分布に従い、入札者が危険中立なら収入の期待値は同じ、というものである(収入同値定理)。
この記事では、第二価格入札で評価値どおりに入札することが支配戦略であること(thm-at-truthful)と、均衡での支払いが勝つ確率だけで決まること(thm-at-re、収入同値定理)を証明し、それを使って各方式の均衡入札と収入を計算する手順を示す。最適な方式の設計(最低価格の選び方、Myerson の最適オークション)と VCG 機構は メカニズムデザイン で扱う。

定義と使える条件

封印入札の方式

品物 1 つを $n\ge2$ 人の入札者に売る。各入札者 $i$ は非負の額 $b_i$ を封をして出す。最高額の入札者が品物を得る(同額のときは等確率のくじで決める)。支払いの規則により、次の方式がある。

  1. 第一価格入札:勝者が自分の入札額 $b_i$ を払う。ほかの人は払わない。
  2. 第二価格入札(Vickrey オークション):勝者がほかの人の入札額の最大値 $\max_{j\ne i}b_j$ を払う。ほかの人は払わない。
  3. 全員払い入札(all-pay オークション):勝ち負けにかかわらず全員が自分の入札額を払う。
    公開の方式として、価格を少しずつ上げて最後に残った人が売る 競り上げ式(English オークション)と、価格を下げていき最初に手を挙げた人がその価格で買う 競り下げ式(Dutch オークション)がある。

競り下げ式では、各人は「価格が $b$ まで下がったら手を挙げる」と事前に決めることしかできず、勝者は自分の $b$ を払うので、第一価格入札と戦略として同じものである。競り上げ式では、価格が評価値より低い間は残り、超えたら降りることが支配戦略で、勝者はおおよそ 2 番目の人が降りた価格を払うので、第二価格入札に近い(KP17 §14.1, p. 234 と p. 237)。

独立な私的価値のモデルと Bayes–Nash 均衡

次の (i)〜(iii) を仮定する。

  • (i) 独立な私的価値:入札者 $i$ の評価値 $V_i$ は互いに独立な確率変数で、$i$ は自分の $V_i$ だけを知る。分布は全員に知られている。
  • (ii) 危険中立:評価値 $v$ の人が品物を得て $q$ を払うときの効用は $v-q$、得ずに $q$ を払うときは $-q$ で、人は効用の期待値を最大にする。
  • (iii) 各入札者の戦略は、評価値から入札額への関数 $\beta_i$ である。
    戦略の組 $(\beta_1,\dots,\beta_n)$ を固定する。入札者 $i$ が、評価値が $w$ であるかのように $\beta_i(w)$ を入札したときの勝つ確率を $a_i(w)$、支払いの期待値を $p_i(w)$ とする(ほかの人は $\beta_j(V_j)$ を入札し、確率は $V_j$($j\ne i$)についてとる)。評価値 $v$ の人の期待効用は
    $$ u_i(w\mid v)=v\,a_i(w)-p_i(w) $$
    で、$u_i(v)=u_i(v\mid v)$ と書く。すべての $i$、$v$、$w$ で $u_i(v)\ge u_i(w\mid v)$ が成り立ち、さらにどの $i$ と $v$ についても、$\beta_i$ の値域の外の入札額では期待効用が $u_i(v)$ を超えないとき、戦略の組を Bayes–Nash 均衡 という。全員が同じ $\beta$ を使う均衡を 対称な均衡 という。

(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(0 から 1)、縦軸は入札額。入札者 2 人で評価値が一様分布のときの、第二価格の均衡入札 v の直線、第一価格の均衡入札 v/2 の直線、全員払いの均衡入札 v²/2 の曲線が描かれている。点線は 3 方式に共通の支払いの期待値 v²/2 で、全員払いの曲線と重なる。

第二価格入札と誘因両立性

第二価格入札では評価値どおりの入札が支配戦略

第二価格入札で、評価値 $v$ の入札者にとって、$v$ を入札することは弱い意味の支配戦略である。すなわち、ほかの人の入札がどうであっても、$v$ を入札したときの効用は、ほかのどの額 $b$ を入札したときの効用以上である。さらに $b\ne v$ なら、$v$ を入札したほうが効用が真に大きくなるほかの人の入札の組がある。

最大値 $m$ との大小で分ける

ほかの人の入札額の最大値を $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. すべての $v,w\in J$ で $u(v)\ge u(w\mid v)$ なら、$a$ は広義単調増加で、
    $$ u(v)=u(0)+\int_0^va(z)\,dz,\qquad p(v)=v\,a(v)-\int_0^va(z)\,dz-u(0)\qquad(\ast) $$
    が成り立つ。
  2. 逆に、$a$ が広義単調増加で $p$ が $(\ast)$ の第 2 式をみたせば、すべての $v,w\in J$ で $u(v)\ge u(w\mid v)$ である。
    とくに、勝つ確率の関数 $a$ と $u(0)$ が同じ 2 つの均衡では、支払いの期待値 $p(v)$ が同じであり、売り手の収入の期待値も同じである。
2 つの評価値で比べて挟む

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$ とおく。

  1. 第一価格入札では、$\beta(v)=v-\dfrac{I(v)}{G(v)}$($v>0$)、$\beta(0)=0$ が対称な Bayes–Nash 均衡である。
  2. 全員払い入札では、$\beta(v)=vG(v)-I(v)$ が対称な Bayes–Nash 均衡である。
    どちらも狭義単調増加で、支払いの期待値は cor-at-iid の $p(v)$ に等しい。
単調性を確かめ、値域の外を除く

候補の出し方。 第一価格入札では勝ったときだけ入札額を払うので $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$ で、最高額の入札者が勝つ方式の対称な均衡と収入は、次の手順で求める。

  1. $G$ を求める。 $G(v)=F(v)^{n-1}$、$I(v)=\int_0^vG(w)\,dw$ を計算する。
  2. 支払いの期待値を求める。 cor-at-iid により $p(v)=vG(v)-I(v)$ である。
  3. 支払いの規則を $\beta$ で書く。 第一価格なら $p=G\beta$、全員払いなら $p=\beta$、勝者が $\beta$ の半分を払う方式なら $p=\frac12G\beta$ のように、方式の規則から $p(v)$ を $\beta(v)$ で表す。
  4. $\beta$ について解く。 3 の式に 2 の $p$ を代入する。
  5. 均衡であることを確かめる。 $\beta$ が狭義単調増加であることと、$\beta$ の値域の外の入札で得をしないことを確かめる(prf-at-first-price と同じ)。狭義単調増加でなければ、この手順の前提が成り立っておらず、候補は均衡でない。
  6. 収入を求める。 収入の期待値は $nE[p(V)]=E[V_{(2)}]$ である。検算として、勝者の支払いの期待値を直接計算してもよい。
    3 で $p(v)$ を $\beta$ で書けるのは、勝つ確率が $G(v)$ で決まり、支払いが自分の入札額だけで決まる方式に限られる。第二価格入札では支払いがほかの人の入札で決まるので、手順によらず thm-at-truthful を使う。

例題

一様分布、3 人の第一価格入札

評価値は $[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$。

指数分布、2 人の第一価格入札

評価値は平均 $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$ の指数分布である。

一様分布、2 人の全員払い入札

評価値は $[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$。

一様でない分布、2 人の第一価格入札

評価値の分布は $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 を使ってよい条件は次のとおりである。

  • (i) 評価値が独立で、各人が自分の評価値だけを知る(独立な私的価値)。
  • (ii) 入札者が危険中立である。
  • (iii) 比べる方式で勝つ確率の関数 $a$ が同じである(独立同分布で狭義単調増加の対称な均衡なら、最高の評価値の人が勝つこと)。
  • (iv) 評価値が最低の人の期待効用 $u(0)$ が同じである。
条件を外した反例

入札者 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 の単調性と値域の外の入札の扱い、危険回避的な入札者の例は、この記事の組み立てである。

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, 著者公開版(2016 年 12 月 13 日)の番号と頁:§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)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する