ランダムサンプリングメカニズム

ランダムサンプリング メカニズム (RSM) は、事前情報のないメカニズムと事前情報のないメカニズムで近似的に最適なゲインを達成するためにサンプリングを使用する真実のメカニズムです。

オークションでいくつかの品物を販売し、最大の利益を得たいとします。決定的な問題は、各購入者が品物にいくら支払う意思があるかがわからないことです。少なくとも、購入者の評価が既知の確率分布を持つランダム変数であることがわかっていれば、ベイズ最適メカニズムを使用できます。しかし、多くの場合、分布はわかりません。この場合、ランダムサンプリングメカニズムが代替ソリューションを提供します。

市場が大きい場合、次のような一般的なスキームを使用することができる。^{[1] : 341–344}

1. 買い手は評価額を明らかにするよう求められます。
2. 購入者は、単純ランダムサンプリングを使用して、 2 つのサブ市場(「左」) と(「右」) に分割されます。各購入者は、公平なコインを投げて、どちらかの側に移動します。${\displaystyle M_{L}}$${\displaystyle M_{R}}$
3. 各サブマーケットにおいて、経験的分布関数が計算されます。${\displaystyle M_{s}}$ ${\displaystyle F_{s}}$
4. ベイズ最適メカニズム（マイヤーソンのメカニズム）は、分布 のサブ市場と のサブ市場 に適用されます。${\displaystyle M_{R}}$${\displaystyle F_{L}}$${\displaystyle M_{L}}$${\displaystyle F_{R}}$

この方式は「ランダムサンプリング経験的マイヤーソン」(RSEM) と呼ばれます。

各買い手の申告は、その買い手が支払う価格には影響しません。価格は他のサブマーケットの買い手によって決定されます。したがって、買い手が真の評価を明らかにすることは、支配的な戦略です。言い換えれば、これは真実のメカニズムです。

直感的には、大数の法則により、市場が十分に大きい場合、経験的分布は実際の分布と十分に類似しているため、RSEM はほぼ最適な利益を達成すると予想されます。ただし、これは必ずしもすべての場合に当てはまるわけではありません。いくつかの特殊なケースでは当てはまることが証明されています。

最も単純なケースは、デジタル商品のオークションです。ここでは、ステップ 4 は単純で、各サブマーケットの最適価格を計算することだけで構成されています。 の最適価格はに適用され、その逆も同様です。したがって、このメカニズムは「ランダム サンプリング最適価格」(RSOP) と呼ばれます。このケースが単純なのは、常に実行可能な割り当てを計算するためです。つまり、一方側で計算された価格を他方側に適用することが常に可能です。これは、物理的な商品の場合に必ずしも当てはまるわけではありません。 ${\displaystyle M_{L}}$${\displaystyle M_{R}}$

デジタル商品のオークションでも、RSOP は必ずしも最適利益に収束するわけではありません。RSOP は、評価額が制限されているという仮定のもとでのみ収束します。つまり、各購入者にとって、商品の評価額は 1 から の間であり、 は定数です。RSOP が最適値に収束する率は に依存します。収束率は、メカニズムによって考慮される可能性のある「オファー」の数にも依存します。^[2]${\displaystyle h}$${\displaystyle h}$${\displaystyle h}$

「オファー」とは何かを理解するために、購入者の評価額（ドル建て）が の範囲内であることが分かっているデジタル商品のオークションを考えてみましょう。メカニズムがドル単位の価格のみを使用する場合、可能なオファーは のみです。${\displaystyle [1,h]}$${\displaystyle h}$

一般に、最適化問題には単一の価格以上のものが関係することがあります。たとえば、それぞれ異なる価格の複数の異なるデジタル商品を販売したいとします。そこで、「価格」の代わりに「オファー」について考えます。可能なオファーのグローバル セットがあると仮定します。すべてのオファーとエージェントについて、はエージェントがオファー を提示されたときに支払う金額です。デジタル商品の例では、は可能な価格のセットです。すべての可能な価格 について、 が0 ( の場合) または( の場合) となるような関数が存在します。 ${\displaystyle G}$${\displaystyle g\in G}$${\displaystyle i}$${\displaystyle g(i)}$${\displaystyle i}$${\displaystyle g}$${\displaystyle G}$${\displaystyle p}$${\displaystyle g_{p}}$${\displaystyle g_{p}(i)}$${\displaystyle v_{i}$${\displaystyle p}$${\displaystyle v_{i}\geq p}$

エージェントの各セットについて、エージェントにオファーを提示することによるメカニズムの利益は次のとおりです。 ${\displaystyle S}$${\displaystyle g}$${\displaystyle S}$

${\displaystyle g(S):=\sum _{i\in S}g(i)}$

そして、このメカニズムの最適利益は次のようになります。

${\displaystyle OPT_{G}(S):=\max _{g\in G}g(S)}$

RSM は、各サブマーケットについて、次のように最適なオファーを計算します。 ${\displaystyle M_{s}}$${\displaystyle g_{s}}$

${\displaystyle g_{s}:=\arg \max _{g\in G}g(M_{s})}$

オファーはの購入者に適用されます。つまり、 と言った各購入者はオファーされた割り当てを受け取り、 を支払います。と言ったの各購入者は何も受け取らず、何も支払いません。 オファーはの購入者にも同様に適用されます。 ${\displaystyle g_{L}}$${\displaystyle M_{R}}$${\displaystyle i\in M_{R}}$${\displaystyle g_{L}(i)>0}$${\displaystyle g_{L}(i)}$${\displaystyle M_{R}}$${\displaystyle g_{L}(i)=0}$${\displaystyle g_{R}}$${\displaystyle M_{L}}$

プロフィットオラクルは、大規模市場で使用できるもう1つのRSMスキームです。^[3]これは、エージェントの評価に直接アクセスできない場合（たとえば、プライバシー上の理由により）に役立ちます。私たちにできることは、オークションを実行して、予想される利益を監視することだけです。入札者がいて、各入札者に対して最大で可能な値（未知の確率でランダムに選択）がある単一アイテムオークションでは、最大収益オークションは次のように学習できます。 ${\displaystyle n}$${\displaystyle K}$

${\displaystyle O(n^{2}K^{2})}$

オラクル利益を呼び出します。

RSM は、市場が小さい最悪のシナリオでも研究されました。このような場合、市場規模に依存しない絶対的な乗法近似係数を取得する必要があります。

この設定での最初の研究は、単一パラメータ効用を持つデジタル商品オークションを対象としたものであった。^[4]

ランダムサンプリング最適価格メカニズムについては、いくつかのより優れた近似値が計算されています。

• ^[5]によれば、メカニズムの利益は最適値の少なくとも1/7600である。
• ^[6]によれば、メカニズムの利益は最適値の少なくとも1/15である。
• ^[7]によれば、メカニズムの利益は少なくとも最適値の1/4.68であり、ほとんどの場合最適値の1/4であり、これは厳しい。

エージェントの評価が何らかの技術的な規則性条件（単調ハザード率と呼ばれる）を満たす場合、次のメカニズムを使用して最大利益オークションの定数係数近似を達成することが可能である：^[8]

• 単一のランダムエージェントをサンプリングし、その値を照会します (エージェントは単一パラメータユーティリティを持つと想定されます)。
• 他のエージェントでは、サンプル エージェントによって決定された最低入札価格でVCG オークションを実行します。

このメカニズムの利益は少なくとも です。ここで はエージェントの数です。エージェントが 2 人の場合は 1/8 で、エージェントの数が増えるにつれて 1/4 に近づいていきます。このスキームは、同時に落札できるエージェントのサブセットに関する制約 (たとえば、アイテムの数は有限) を処理するために一般化できます。また、異なる属性を持つエージェント (たとえば、若い入札者と年配の入札者) を処理することもできます。 ${\displaystyle {n-1 \over 4n}}$${\displaystyle n}$

ランダム サンプリング メカニズムのサンプル複雑度は、最適な福祉の合理的な近似値を得るためにサンプリングする必要があるエージェントの数です。

^[8]の結果は、単一商品オークションの収益最大化のサンプル複雑性に関するいくつかの境界を示唆している。^[9]

• 最適期待収益の近似値を求めるには、サンプルの複雑さは1つのサンプルで十分である。これは入札者がiidでない場合でも当てはまる^[10]${\displaystyle 1/4}$${\displaystyle 1}$
• 最適期待収益の近似値の場合、入札者が iid であるか、アイテム（デジタル商品）の供給が無制限である場合、エージェントの分布が単調なハザード率を持つとき、サンプル複雑度は、エージェントの分布が正規分布だが単調なハザード率を持たないときです。${\displaystyle 1-\epsilon }$${\displaystyle O(1/\epsilon ^{2})}$${\displaystyle O(1/\epsilon ^{3})}$

エージェントがiidでない場合（各エージェントの価値が異なる正規分布から抽出される）、および商品の供給が限られている場合、状況はさらに複雑になります。エージェントが異なる分布から来る場合、単一アイテムオークションでの最適期待収益の近似のサンプル複雑度は次のようになります。 ^[9]${\displaystyle k}$${\displaystyle 1-\epsilon }$

• 最大で、経験的マイヤーソンオークションの変形を使用します。${\displaystyle O({k^{10} \over \epsilon ^{7}}\ln ^{3}{k \over \epsilon })}$
• 少なくとも（単調ハザード率の通常評価の場合）および少なくとも（任意の通常評価の場合）。${\displaystyle \Omega ({k \over {\sqrt {\epsilon \ln k}}})}$${\displaystyle \Omega ({k \over \epsilon })}$

^[11]は、単一パラメータ効用エージェント（単一アイテムオークションだけでなく）と任意のオークションメカニズム（特定のオークションだけでなく）による任意のオークションについて議論している。サンプル複雑性に関する既知の結果に基づいて、彼らは、与えられたオークションクラスから最大収益オークションを近似するために必要なサンプル数は、

${\displaystyle O{\bigg (}({H \over \epsilon })^{2}(D\ln({H \over \epsilon })+\ln({1 \over \delta })){\bigg )}}$

どこ：

• エージェントの評価は の範囲内にあり、${\displaystyle [1,H]}$
• オークションのクラスの疑似VC次元は最大で、${\displaystyle D}$
• 必要な近似係数は、${\displaystyle 1-\epsilon }$
• 必要な成功確率は です。${\displaystyle 1-\delta }$

特に、彼らはレベルオークションと呼ばれる単純なオークションのクラス、すなわち最低落札価格のあるオークション（単一の最低落札価格のある Vickrey オークションは レベルオークションです）を検討します。彼らはこのクラスの疑似 VC 次元が であることを証明します。これは、一般化誤差とサンプル複雑度の境界に直ちに変換されます。彼らはまた、このクラスのオークションの表現誤差の境界も証明します。 ${\displaystyle t}$${\displaystyle t}$${\displaystyle O(nt\ln(nt))}$

ランダムサンプリングメカニズムの欠点は、嫉妬がないわけではないということである。例えば、2つのサブマーケットとにおける最適価格が異なる場合、各サブマーケットの買い手には異なる価格が提示される。言い換えれば、価格差別が存在する。これは、最適利益を近似する単一価格の戦略不可能なオークションは存在しないという意味で避けられない。^[12]${\displaystyle M_{L}}$${\displaystyle M_{R}}$

• 市場調査
• 価格
• コンセンサス推定-事前フリーメカニズム設計の代替アプローチ。