ベイズ最適メカニズム

ベイズ最適メカニズム(BOM)とは、設計者がメカニズムの設計対象となるエージェントの評価を知らないが、それらがランダム変数であることと、これらの変数の 確率分布を知っているメカニズムです。

典型的な応用例は、潜在的な買い手にいくつかの商品を販売したい売り手です。売り手は利益を最大化するように商品の価格を設定したいと考えています。最適な価格は、各買い手が各商品に支払う意思のある金額によって異なります。売り手はこれらの金額を知りませんが、特定の既知の確率分布から引き出されたものと想定しています。「ベイズ最適メカニズム設計」というフレーズは、次の意味を持ちます。^{[1] : 335–338}

• ベイズとは、エージェントの評価が導き出される確率分布を知っていることを意味します（事前確率分布を仮定しない事前フリーメカニズム設計とは対照的です）。
• 最適とは、オークション主催者の予想収益を最大化することを意味し、その期待値はエージェントの評価におけるランダム性を超えています。
• メカニズムとは、各エージェントが自分の真の値を報告するインセンティブを持つ、真実のメカニズムを定義するルールを設計することを意味します。

販売されている商品は 1 つあります。潜在的な購入者は 2 人います。各購入者の評価は、[0,1] 上の一様分布から iid で抽出されます。

ヴィックレイオークションは誠実な仕組みであり、この場合の期待利益は 1/3 です (第一価格密封入札オークションは誠実でない仕組みであり、その期待利益は同じです)。

このオークションは最適ではありません。予約価格を設定することで、より良い利益を得ることができます。予約価格1/2のヴィックレイオークションでは、期待利益は5/12となり、この場合は最適です。^[2]

エージェントは、単一アイテムオークションのような単一パラメータの効用関数を持つと仮定します。各エージェントは、エージェントの「勝利値」（たとえば、エージェントのアイテムの評価）を表す値を持ちます。これらの値はわかりませんが、それぞれが特定の確率分布から iid で抽出されることはわかっています。累積分布関数で次のように表します。 ${\displaystyle i}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle F_{i}}$

${\displaystyle F_{i}(z)=\Pr[v_{i}<z]}$

そして確率分布関数によって： ${\displaystyle f_{i}}$

${\displaystyle f_{i}(z)=F_{i}'(z)}$

割り当てはベクトル であり、任意の に対して、エージェントが勝った場合は 1、そうでない場合は 0 になります。各割り当てには、競売人へのコストがかかる場合があります。 ${\displaystyle x}$${\displaystyle i}$${\displaystyle x_{i}}$${\displaystyle i}$${\displaystyle c(x)}$

割り当ての余剰は次のように定義され ます。

${\displaystyle S(x)=\sum _{i}x_{i}\cdot v_{i}-c(x)}$

これは、エージェントの総利益から競売人の費用を差し引いたものです。

余剰は、最大限に得られる利益です。落札した各エージェントが自分の価値とまったく同じ金額を支払う場合、競売人の利益は余剰とまったく同じになります。つまり、競売人は余剰をすべて自分のものにし、エージェントには効用をまったく残さないことになります。 ${\displaystyle i}$${\displaystyle v_{i}}$${\displaystyle S(x)}$

この最大利益は達成できません。なぜなら、オークション主催者が落札した各エージェントに価値を請求しようとすると、エージェントは支払いを少なくするために嘘をつき、より低い価値を報告するからです。マイヤーソン機構はこの問題に対処するために登場しました。 ${\displaystyle v_{i}}$

Roger Myerson は、単一パラメータのユーティリティエージェントのためのベイズ最適メカニズムを設計しました。Myerson のメカニズムの重要なトリックは、仮想評価を使用することです。すべてのエージェントについて、仮想評価を次のように定義します。 ${\displaystyle i}$

${\displaystyle w_{i}(v_{i})=v_{i}-{\frac {1-F_{i}(v_{i})}{f_{i}(v_{i})}}}$

仮想評価は通常、実際の評価よりも小さくなることに注意してください。実際の評価がプラスであっても、仮想評価がマイナスになる可能性もあります。

割り当ての仮想余剰を次のように定義します。 ${\displaystyle x}$

${\displaystyle S^{*}(x)=\sum _{i}x_{i}\cdot w_{i}(v_{i})-c(x)}$

仮想余剰は通常、実際の余剰よりも小さくなることに注意してください。

マイヤーソンの重要な定理は次の通りである: ^{[1] : 336  [3]}

あらゆる真実のメカニズムの期待利益は、その期待仮想余剰に等しい。

(期待値はエージェントの評価におけるランダム性に左右されます)。

この定理は次のようなメカニズムを示唆しています。

• 各エージェントに評価額を報告してもらう${\displaystyle i}$${\displaystyle v_{i}}$
• 答えと既知の分布関数に基づいて、 を計算します。${\displaystyle F_{i},f_{i}}$${\displaystyle w_{i}}$
• 仮想余剰を最大化する割り当て x を計算します。${\displaystyle S^{*}(x)}$

メカニズムの説明を完了するには、各勝者が支払う価格を指定する必要があります。価格を計算する 1 つの方法は、仮想評価に対してVCG メカニズムを使用することです。VCG メカニズムは、仮想余剰を最大化する割り当てと価格ベクトルの両方を返します。価格ベクトルは仮想評価に対応しているため、実際の評価空間に変換する必要があります。したがって、メカニズムの最終ステップは次のようになります。 ${\displaystyle w_{i}}$

• 各勝利エージェントから価格を取得します。ここで、価格は VCG メカニズムによって決定されます。${\displaystyle i}$${\displaystyle p_{i}=w_{i}^{-1}(p'_{i})}$${\displaystyle p'_{i}}$

マイアソン機構は、配分規則が弱単調性特性を満たす場合、つまり、配分関数がエージェントの評価において弱増加である場合に常に真実です。VCG 配分規則は確かに評価において弱増加ですが、実際の評価ではなく仮想評価で使用します。したがって、仮想評価が実際の評価において弱増加である場合、マイアソン機構は真実です。つまり、すべての に対して:が の弱増加関数である場合です。 ${\displaystyle i}$${\displaystyle w_{i}}$${\displaystyle v_{i}}$

が の弱増加関数でない場合は、Myerson アイロニングを使用できます。 ${\displaystyle w_{i}}$${\displaystyle v_{i}}$

マイヤーソンのメカニズムはさまざまな設定に適用できます。以下に 2 つの例を示します。

単一の商品を販売したいとします。すべてのエージェントの評価は、関数 を持つ同じ確率分布から得られることがわかっています。この場合、すべての入札者は同じ仮想評価関数 を持ちます。この関数が弱増加であるとします。この場合、VCG メカニズムはVickrey オークションに簡略化されます。つまり、最大評価 (最高入札) を持つエージェントに商品を割り当てます。しかし、Myerson のメカニズムは、負の可能性がある仮想評価を持つ VCG を使用します。したがって、この場合、Myerson のメカニズムは、留保価格 を持つ Vickrey オークションに簡略化されます。仮想評価が少なくとも 0 の場合のみ、最大評価を持つエージェントに商品を割り当てます。つまり、Myerson のメカニズムの留保価格は正確に次のようになります。 ${\displaystyle F,f}$${\displaystyle w}$

${\displaystyle w^{-1}(0)}$

したがって、確率分布関数がわかっていれば、関数を計算し、そこから最適な予約価格を見つけることができます。 ${\displaystyle F,f}$${\displaystyle w}$

デジタル商品のオークションでは、同一の商品が無制限に供給されます。各エージェントは最大で 1 つの商品を希望します。エージェントの商品に対する評価は、関数と仮想評価関数 を使用した同じ確率分布から得られます。VCG メカニズムは、各エージェントに非負の仮想評価を持つ商品を割り当て、最低落札価格を請求します。これは次のとおりです。 ${\displaystyle F,f}$${\displaystyle w}$

${\displaystyle w^{-1}(0)}$

これは、評価の分布を考慮すれば売り手の利益の 期待値を最大化する価格である最適な販売価格とまったく同じです。

${\displaystyle \arg \max _{z}{z\cdot (1-F(z))}}$

ベイズ最適メカニズム設計では、エージェントの評価が引き出される分布を知る必要があります。この要件は必ずしも実現可能ではありません。他の代替手段がいくつかあります。

• 分布が不明な場合は、事前に依存しないメカニズムを使用できます。
• エージェントが何らかの確率分布から抽出されると想定することさえできない場合は、事前フリーメカニズムを使用する必要があります。