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

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

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

大規模市場におけるRSM

市場半減計画

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

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

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

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

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

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

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

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

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

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

グラム （ S ） := ∑ 私 ∈ S グラム （ 私 ） {\displaystyle g(S):=\sum _{i\in S}g(i)}

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

お P T G （ S ） := 最大 グラム ∈ G グラム （ S ） {\displaystyle OPT_{G}(S):=\max _{g\in G}g(S)}

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

グラム s := 引数 ⁡ 最大 グラム ∈ G グラム （ M s ） {\displaystyle g_{s}:=\arg \max _{g\in G}g(M_{s})}

このオファーは の購入者に適用されます。つまり、と回答した購入者はオファーされた割り当てを受け取り、 を支払います。と回答した購入者は、 を受け取らず、何も支払いません。の購入者にも同様の方法で オファーが適用されます。 グラム L {\displaystyle g_{L}} M R {\displaystyle M_{R}} 私 ∈ M R {\displaystyle i\in M_{R}} グラム L （ 私 ） > 0 {\displaystyle g_{L}(i)>0} グラム L （ 私 ） {\displaystyle g_{L}(i)} M R {\displaystyle M_{R}} グラム L （ 私 ） ＝ 0 {\displaystyle g_{L}(i)=0} グラム R {\displaystyle g_{R}} M L {\displaystyle M_{L}}

利益オラクル計画

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

お （ n 2 K 2 ） {\displaystyle O(n^{2}K^{2})}

オラクル利益への呼び出し。

小規模市場におけるRSM

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

市場の半減、デジタル商品

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

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

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

単一サンプルの物理的な商品

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

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

サンプルの複雑さ

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

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

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

エージェントが独立同値（各エージェントの価値が異なる正規分布から抽出される）でなく、財の供給が限られている場合、状況はさらに複雑になります。エージェントが異なる分布から抽出される場合、単品オークションにおける最適期待収益の近似のサンプル複雑度は[9]のようになります。 け {\displaystyle k} 1 − ϵ {\displaystyle 1-\epsilon }

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

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

お （ （ H ϵ ） 2 （ D ln ⁡ （ H ϵ ） + ln ⁡ （ 1 δ ） ） ） {\displaystyle O{\bigg (}({H \over \epsilon })^{2}(D\ln({H \over \epsilon })+\ln({1 \over \delta })){\bigg )}}

どこ：

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

特に、彼らは-レベルオークションと呼ばれる単純なオークションのクラス、すなわち最低落札価格のあるオークション（最低落札価格が1つしかないヴィックレイオークションは1レベルオークションである）を考察する。彼らはこのクラスの擬似VC次元が であることを証明し、これは直ちに一般化誤差とサンプル複雑度の上限につながる。また、このクラスのオークションの表現誤差の上限も証明している。 t {\displaystyle t} t {\displaystyle t} お （ n t ln ⁡ （ n t ） ） {\displaystyle O(nt\ln(nt))}

妬み

ランダムサンプリング方式の欠点は、羨望の影響を受けないわけではないことです。例えば、2つのサブマーケットとサブマーケットの最適価格が異なる場合、それぞれのサブマーケットの買い手には異なる価格が提示されます。言い換えれば、価格差別が生じます。これは、最適利益を近似する単一価格の戦略不可能なオークションは存在しないという点で避けられません。 [12] M L {\displaystyle M_{L}} M R {\displaystyle M_{R}}

参照

参考文献

  1. ^ ヴァジラニ、ヴィジェイ V. ;ニサン, ノーム;ティム・ラフガーデン;タルドス、エヴァ(2007)。アルゴリズムゲーム理論(PDF)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0。
  2. ^ Balcan, Maria-Florina ; Blum, Avrim ; Hartline, Jason D. ; Mansour, Yishay (2008). 「機械学習によるメカニズム設計からアルゴリズム設計への還元」. Journal of Computer and System Sciences . 74 (8): 1245. doi : 10.1016/j.jcss.2007.08.002 .
  3. ^ Edith Elkind (2007).最適有限サポートオークションの設計と学習. SODA.
  4. ^ Goldberg, Andrew V.; Hartline, Jason D. (2001). 「複数のデジタル商品のための競争オークション」. Algorithms — ESA 2001 . Lecture Notes in Computer Science. Vol. 2161. p. 416. CiteSeerX 10.1.1.8.5115 . doi :10.1007/3-540-44676-1_35. ISBN  978-3-540-42493-2。
  5. ^ Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R.; Saks, Michael; Wright, Andrew (2006). 「競争オークション」. Games and Economic Behavior . 55 (2): 242. doi :10.1016/j.geb.2006.02.003.
  6. ^ フェイジ, ウリエル; フラックスマン, エイブラハム; ハートライン, ジェイソン・D.; クラインバーグ, ロバート (2005). 「ランダムサンプリングオークションの競争比率について」.インターネットとネットワーク経済学. コンピュータサイエンス講義ノート. 第3828巻. p. 878. CiteSeerX 10.1.1.136.2094 . doi :10.1007/11600930_89. ISBN  978-3-540-30900-0。
  7. ^ Alaei, Saeed; Malekian, Azarakhsh; Srinivasan, Aravind (2009). 「デジタル商品のランダムサンプリングオークションについて」.第10回ACM電子商取引会議 - EC '09 議事録. p. 187. CiteSeerX 10.1.1.758.3195 . doi :10.1145/1566374.1566402. ISBN  9781605584584. S2CID  582565。
  8. ^ ab Dhangwatnotai, Peerapong; Roughgarden, Tim; Yan, Qiqi (2015). 「単一サンプルによる収益最大化」. Games and Economic Behavior . 91 : 318–333 . doi : 10.1016/j.geb.2014.03.011 .
  9. ^ ab リチャード・コール、ティム・ラフガーデン (2014). 「収益最大化のサンプル複雑性」.第46回ACMコンピューティング理論シンポジウム - STOC '14 論文集. p. 243. arXiv : 1502.00963 . doi :10.1145/2591796.2591867. ISBN 9781450327107。
  10. ^ ハートライン、ジェイソン・D.、ラフガーデン、ティム (2009). 「シンプルなメカニズムと最適なメカニズム」.第10回ACM電子商取引会議 - EC '09 議事録. p. 225. doi :10.1145/1566374.1566407. ISBN 9781605584584。
  11. ^近似最適オークション の擬似次元について。NIPS。2015年。arXiv : 1506.03684。Bibcode :2015arXiv150603684M 。
  12. ^ Andrew V. Goldberg、Jason D. Hartline (2003). 「コンセンサスによる競争力」.第14回ACM-SIAM離散アルゴリズムシンポジウム議事録. SODA '03 . 2016年1月7日閲覧。
「https://en.wikipedia.org/w/index.php?title=ランダムサンプリング機構&oldid=1318897976」より取得