Pay-Per-Click（ペイ・パー・クリック）広告とGSPオークション、その２　理論編

今回はGoogleの秘密に理論的に迫ってみる。話を簡単にするために、二つのリンクのオークションに三人が参加しているとしてみよう。一番上にあるリンク - 仮にリンク１と呼ぶ - は一日当たり200クリック、そしてその下にあるリンク２は、一日当たり100クリックを集める。個人１、２、３それぞれについて、クリック当たりの価値が、それぞれ$10,$5,$1だと設定する。*1

さて、彼らはいったいこのオークションでいくらビッドするだろうか。彼らはいつでもビッドを変更することが出来るので、もしビッドがどこかに落ちついたならば、そこでは、誰も自分のビッドを変更するインセンティブを持たないはずだ。言い換えると、この３人のビッドは、ナッシュ均衡になってなくっちゃいけない。*2

ここでさらに話を簡単にするために、個人３は$1をビッドするとする。また、b1がb2より大きいというのも仮定してしまえ。*3よりたくさん金を払う用意のある人が、いいリンクをゲットするのは、別に変な仮定じゃないだろう。すると、いくつかb1、b2が満たさなきゃいけない条件が出てくる。

まず、b2が高すぎると、個人１はあえて低くビッドすることで上のリンクを譲るインセンティブが出てくる。クリック数は半分になるが、クリック当たりの支払いはb2の替わりに$1になるからだ。この条件は、 $10 \times 200 - b2 \times 200 \geq 10 \times 100 - 1 \times 100$ と書ける。

次に、b1が低すぎると、個人２が上のリンクを奪うインセンティブが出てくる。この場合、クリック当たりの支払いは$1からb1にあがるが、クリック数は倍増する。この条件は、 $5 \times 100 - 1 \times 100 \geq 5 \times 200 - b1 \times 200$ と書ける。

これをまとめると、b2が$5.5以下（で、もちろん$1より大きい値）で、b1がb2より大きいとき、３人のビッドは（ここで仮定したような）ナッシュ均衡になっていることがわかる。

もちろん、均衡でのグーグルの売上も計算することが出来る。グーグルの売上は、 $b2 \times 200 + 1 \times 100$ なので、この場合売上は最低で$300、最大で$1200ということになる。しかしこれだと均衡になるb2の幅が広いので、もうすこし精確な値を求めることが出来ないかちょっと考えてみよう。直観的には、自分のビッドを上げても自分の支払いは増えないので（困るのは上の人）、リンクの配分が変わらない限り、出来るだけ高くビッドしたほうが得なような気がする。これに関して、前掲の論文が次のようなアイデアを提案している。人々は、最低でも、一つ上のリンクの人をうらやまない程度には（Envy-free）自分の価格を釣上げるという考え方だ。もしも、自分が一つ上の立場になったら今と比べてどうかと考えるわけだ。個人２についてこれを数式で書くと、 $5 \times 100 - 1 \times 100 \geq 5 \times 200 - b2 \times 200$ となる。つまり、b2は$3以上になるという結論が導かれる。上の２番目の式と違うことに注意してほしい。個人２は、自分が上のリンクをゲットしても、クリック当たりb2しか払わないことを夢想してるのだ。それが、上で「自分が一つ上の立場になったら」といった意味だ。*4これからすると、グーグルの売上は最低でも$700になることがわかる。この結果を信じるかどうかは、Envy-freeがどれぐらい信用できる条件かによるが、論文によると、Envy-freeは実際のデータとそこそこ整合的である（と言っている人がいる）らしい。

この結果がどういう意味をもつかは、何かベンチマークがないとわからないかもしれない。このオークション（GSPオークション）とは別のタイプの（そしてより有名な）セカンド・プライス・オークションの一般化であるメカニズムとしてVCG(Vickrey-Clark-Gloves)メカニズムがあるが、VCGメカニズムの元では個人１の支払いは$600で個人2の支払いは$100になることが知られている。GSPオークションは、少なくともそれよりは高い売上をたたき出しているわけだ。（詳しくは追記参照）

(追記）さて、この話はちょこっとだけ難しくなる。上のような話は、N人の個人がいて、Kのリンクがあるときにも適用できる。その場合、個人ｎはｎ−１番目の人をうらやまないだけ価格を釣上げる。すると、出てくるのは、次のような式だ： $v(n) \times a(n) - p(n) \geq v(n) \times a(n-1) - p(n-1)$ 。ここで、v(n)はｎ番目の人のクリック当たりの価値、a(n)はｎ番目のリンクの一日当たりのクリック数、そしてp(n)=bn+1*a(n)はn番目の人のトータルの支払いだ。この式を書き直すと、 $p(n-1) - p(n) \geq v(n) \times (a(n-1) - a(n))$ 。これが意味しているのはｎ−１番目の人は、ｎ番目の人の支払いに加えて、ｎ番目の人がｎ−１番目からｎ番目に落ちたことによるの厚生の損失分を最低でも支払わなくてはいけない、ということだ。つまり、ｎ−１番目の人は少なくとも「ｎ番目の人の支払い＋ｎ番目の人に与えた負の外部性」を支払っている。とすると、ｎ−１番目の人(そして全ての参加者）の支払いがVCGメカニズムに比べて増えていることは明らかだ。VCGメカニズムは、定義よりｎ−１番目の人が「ｎ番目の人の支払い＋ｎ番目の人に与えた負の外部性」を支払うメカニズムだからだ。

*1:実際には、クリックの数だけではなく、クリックされるリンクの位置もクリック当たりの価値に影響を与えるかもしれない。特定の位置にあるリンクをクリックするのは、特定の人々であるかもしれないから。

*2:セカンド・プライス・オークションでは明らかに自分の価値自体をビッドするのが他の人のビッドに関わらず最適になっているので（弱支配戦略）、わざわざナッシュ均衡を求めるまでもなかった。しかしGSPオークションではこの性質は成立しない。例えば、個人１が$10、個人２が$9.99、個人３が$1をビッドしたとしたら、個人１は最適にビッドをしているだろうか?

*3:biは個人iのビッド。

*4:実は、b3=$1はこの条件を満たしている。個人３のための条件は、b3が$1以上になることに他ならない。