ゲーム理論から考えるセカンドプライスオークションにおけるベストな入札戦略

この記事はCyberAgent Developers #2 Advent Calendar 2018の16日目の記事です。

adventar.org

日本のアドテク界隈でもヘッダービッティングや1st プライスオークションが流行ってきたこの頃。

RTBにおける広告のオークションでは、セカンドプライスオークションが長らく使われてきましたが、メディア側の収益を最大化するという名目でファーストプライスオークションを導入するSSPやエクスチェンジャーが増えてきました。

果たして、オークション方式を変えることにメディア側の収益が変わるのか、はたまた入札を行うDSPなどの事業者としてどういう戦略を取るべきなのか気になる人も多いかと思います。

結論からいうと、収入等価定理(revenue equivalence theorem)で証明されているように、セカンドプライスオークションもファーストプライスオークションも売り手側の収益は、買い手の2番目に高い評価額となり変わらないという驚くべき結果が導かれます。

今回はその一端を垣間見るために、セカンドプライスオークションにおける最適な入札戦略を紹介したいと思います。

ゲーム理論って何??

そもそもゲーム理論という言葉を聞いたことはあるでしょうか??

ゲーム理論とは、 複数の意思決定をする主体がその意思決定に関して相互作用する状況を研究する理論です。

意思決定をする主体とは、個人であったり、企業であったり、1つの意思決定ができると認識できる単位を表します。

このような意思決定をする主体が2つ以上あり、相互に影響を及ぼし合いながら意思決定を行う時に、どのようにその意思決定が行われるかを考察するのがゲーム理論です。

今回のオークションの場合、意思決定をする主体というのは商品をいくらで入札するかという買い手のことを指し、他の買い手の入札額を考慮して自分の利益を最大化するには入札額をいくらに設定すべきかということを考えることになります。

セカンドプライスオークションにおけるベストな戦略

セカンドプライスオークションとは

そもそもセカンドプライスオークションとは、参加者の中で一番高い入札価格を提示した人が2番目に高い入札額でその商品を購入できるオークション方式のことをいいます。

例えば、Aさんがある商品を1万円で落札し、二番目に高いBさんが入札した金額が1000円だった場合、Aさんはその商品を1000円で購入することが出来ます。

セカンドプライスオークションにおける入札戦略と利益の関係

ここでは以下のような状況で商品をセカンドプライスオークションで購入するモデルを考えます。

・ある商品に対して買い手は二人(買い手1と買い手2)
・その商品の買い手1と買い手2の評価額はそれぞれ1500円と2500円
・最低入札額・最小入札単位はともに500円
・同じ入札額の場合二分の一の確率で商品を購入できる

入札額を決定するポイントとしては、買い手がそれぞれの入札額でオークションを行った時にどれくらいの利益を得ることができるかを考えることです。

500, 1000, ..., 3000とそれぞれの買い手が入札したときのそれぞれの利益を考えてみましょう。

f:id:b0941015:20181215202406p:plain
買い手1と買い手2の各入札額におけるそれぞれの利益

各行が買い手1の入札額を表し、各列が買い手2の入札額を表します。 各入札額における数値は (買い手1の利益, 買い手2の利益) として互いの利益を表します。

例として、買い手1と買い手2が共に500円で入札した場合、買い手1の利益は評価額から落札額の期待値を引いた値{ (1500 - 500) \times \frac{1}{2}) + 0 \times \frac{1}{2} = 500}円で計算されます。同様に買い手2の利益は、{(2500 - 500) \times \frac{1}{2} + 0 \times \frac{1}{2} = 1000}円となるので、1行1列目の値は(500, 1000)となります。

また、買い手1が1000円, 買い手2が500円で入札した場合、買い手1は評価額との差額、買い手2は商品を手に入れることは出来ないので0となり、表の値としては(買い手1の利益, 買い手2の利益) = (1500 - 500, 0) = (1000, 0)となります。

最適な入札戦略の見つけ方

互いに相手の入札額がわからない場合、入札額をいくらに設定すれば自分の利益を最大化できるでしょうか??

考え方としては、2つあります。

  1. どちらか一人が入札額を変えても利益が高くならない入札額の組を見つける(ナッシュ均衡)
  2. 自分の利益が同じ入札額が複数あった場合、相手の入札額によっては自分の利益が大きくなる入札額を選ぶ(弱支配)
どちらか一人が入札額を変えても利益が高くならない入札額の組を見つける(ナッシュ均衡)

1つ目は、ナッシュ均衡と呼ばれるもので、この入札額の組以外の入札を行うとそれぞれの買い手が損をするので、必ずこのナッシュ均衡となる入札戦略が最適な戦略となります。

ナッシュ均衡の見つけ方としては、それぞれの買い手の立場になって、相手の入札額ごとに利益が最大になる入札額を選び、結果として互いに利益が最大になる入札額の組がナッシュ均衡になります。

ナッシュ均衡を見つける例として、まず買い手1の立場に立って、買い手2が1500円で入札する場合を考えます。この場合買い手1はどの入札額でも利益は0で最大になります。

また、買い手2の立場になって、買い手1が1500円で入札をする場合を考えます。そうすると、2000以上で入札することが利益を最大化できることがわかります。

この時、買い手1が1500円、買い手2が2000円で入札する場合がナッシュ均衡の一つとなります。

上記の例のように相手の入札額を固定化した時に利益を最大化できる入札額をすべて見つけ出しに下線を引きます。 これをそれぞれの買い手で同様の操作を行い、互いに下線が引かれた入札額のペアを確認することで、ナッシュ均衡をすべて見つけることができます。 ナッシュ均衡の入札額のペアを背景を黄色としたセルにすると下の表のようになります。

f:id:b0941015:20181215214450p:plain
互いに自分の入札額を変えても利益が増えない入札額の組(ナッシュ均衡)

自分の利益が同じ入札額が複数あった場合、相手の入札額によっては、自分の利益が大きくなる入札額を選ぶ(弱支配)

さて、これらの入札額のペアからどうやって、最適な入札額を見つければ良いでしょうか。 そこで必要な考えが2つ目の弱支配と呼ばれる考え方です。

この考え方は、自分の2つの入札額を考えた時に、相手の入札額によっては利益が高くなるものを選ぶという考え方です。 相手が自分の利益になるような入札をしてくれる可能性があるなら、その入札戦略を選ばない理由は無いということですね。

f:id:b0941015:20181215215549p:plain
買い手1の立場で入札額が1000円と1500円を比較した場合、1500円で入札したほうが利益が高くなる可能性がある

上記2つの考え方を各立場で各入札額に適応すると買い手1は1500円、買い手2は2500円で入札することが自身の利益を最大化する入札額で、セカンドプライスオークションにおける解となります。

この金額というのは各買い手の評価額と一致するということにお気づきでしょうか??

つまりセカンドプライスオークションにおいて自分の利益を最大化するには、それぞれの自身の評価額で入札することが大事になるのです。

まとめ

今回はRTBのオークションで一般的に用いられているセカンドプライスオークションにおける最適な戦略について紹介しました。

その結果、自身の評価額のまま入札することが自分の利益を最大化することだということがわかりました。

少々難しくなるのですが、ファーストプライスオークションについても同様の考え方で、自分の利益を最大化するような入札戦略を考えるとセカンドプライスオークションと同じ結果になります。

詳しく知りたい方は、こちらを読んでいただけるとわかるかと思います。

ゼミナール ゲーム理論入門

ゼミナール ゲーム理論入門

どんなオークション形式でも収益が変わらないのであれば、シンプルに評価額を入札できるようなセカンドプライスオークションを採用するということも頷けます。

ファーストプライスにして収益が増加するということは、この理論を知らない、またはロジックとして未実装な買い手がオークションの参加者にいるということを意味するのではないでしょうか。

結局、情報格差によって損するか・得するかが別れ、ファーストプライスに設定してメディアやSSPの収益が改善した話を聞くと、情弱が損をする世の中なんだなとしみじみ。。。