ベイズ最適メカニズム

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

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

• ベイズ的手法とは、エージェントの評価値がどの確率分布から抽出されるかを知っていることを意味します（事前確率分布を仮定しない事前フリーのメカニズム設計とは対照的です）。
• 最適とは、競売人の期待収益を最大化することを意味し、その期待値は、エージェントによる評価のランダム性を考慮した上でのものである。
• メカニズムとは、各エージェントが自身の真の値を報告するインセンティブを持つような、真実に基づいたメカニズムを定義するルールを設計することを意味します。

販売商品は1点です。購入希望者は2名です。各購入希望者の評価額は、[0,1]の一様分布から独立同分布で抽出されます。

ヴィックリーオークションは真実性を備えたメカニズムであり、この場合の期待利益は1/3です（第一価格封印入札オークションは真実性を備えていないメカニズムであり、期待利益は同じです）。

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

エージェントは、単一アイテムオークションのような単一パラメータ効用関数を持つと仮定します。各エージェント${\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)}$

割り当てはベクトルです${\displaystyle x}$、すべての${\displaystyle i}$、${\displaystyle x_{i}}$エージェントが1の場合${\displaystyle i}$勝利の場合は 0、それ以外の場合は 0 となります。各割り当てにはオークション主催者にとってコストがかかる場合があります。${\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}}$エージェントは支払いを少なくするために、嘘をついて低い金額を報告するだろう。マイヤーソン・メカニズムは、この問題に対処するために考案された。

ロジャー・マイヤーソンは、単一パラメータ効用エージェントのためのベイズ最適メカニズムを設計した。マイヤーソンのメカニズムの鍵となるのは、仮想評価を用いることである。すべてのエージェントについて${\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メカニズムを使用することです。${\displaystyle w_{i}}$VCGメカニズムは、仮想余剰を最大化する配分と価格ベクトルの両方を返します。価格ベクトルは仮想評価に対応するため、それを実評価空間に変換し直す必要があります。したがって、このメカニズムの最終ステップは次のとおりです。

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

ベイズ最適メカニズム設計では、エージェントの評価値がどの分布から抽出されるかを知る必要がある。しかし、この要件は常に満たせるとは限らない。そこで、いくつかの代替案が考えられる。

• 分布が不明な場合は、事前情報に依存しないメカニズムを用いることができる。
• エージェントが何らかの確率分布から抽出されたと仮定することさえできない場合は、事前情報に依存しないメカニズムを用いるべきである。