ダブルオークション

ダブルオークションは、複数の売り手と複数の買い手による商品の売買プロセスです。 ^[1]潜在的な買い手は入札価格を、潜在的な売り手は売り値を市場機関に提出します。その後、市場機関は市場を均衡させる価格p を選択します。つまり、 p未満の価格を要求したすべての売り手はこの価格 p で売り、 p を超える価格を要求したすべての買い手はこの価格pで買います。p とまったく同じ価格で入札または売り注文した売り手と買い手も含まれます。ダブルオークションの一般的な例としては、株式取引所があります。

ダブルオークションは、直接的な関心だけでなく、ワルラスオークションを彷彿とさせ、通常の市場での価格決定を研究するためのツールとして使用されてきました。ダブルオークションは、物々交換取引で通貨の交換がなくても可能です。物々交換ダブルオークションは、すべての参加者が複数の属性からなる需要とオファーを持ち、金銭が関与しないオークションです。^[2]満足度レベルの数学的モデリングには、オファーと需要がベクトルとして扱われる ユークリッド距離が使用されます。

ダブルオークションの簡単な例としては、二国間貿易のシナリオが挙げられます。このシナリオでは、自分の製品をS (たとえば、製品の生産コスト) と評価する単一の売り手と、その製品をBと評価する単一の買い手が存在します。

経済学者の観点から見ると、興味深い問題は、競争の均衡、つまり供給が需要に等しい状況を見つけることです。

単純な二国間貿易のシナリオでは、B ≥ Sの場合、供給と需要の両方が 1 に等しいため、範囲 [ S、B ] 内のどの価格も均衡価格です。 Sより低い価格は需要が過剰であるため均衡価格ではなく、Bより高い価格は供給が過剰であるため均衡価格ではありません。B < Sの場合、供給と需要の両方が 0 に等しいため (価格は買い手にとっては高すぎ、売り手にとっては低すぎます)、範囲 ( B、S ) 内のどの価格も均衡価格です。

より一般的なダブルオークションでは、それぞれが 1 単位を保有する多数の売り手と、それぞれが 1 単位を希望する多数の買い手が存在するため、買い手と売り手の自然な順序を使用して均衡価格を見つけることができます。

• 買い手を入札額の降順で並べます: b ₁ ≥ b ₂ ≥...≥ b _n。
• 売り手を入札額の昇順で並べます: s ₁ ≤ s ₂ ≤...≤ s _n。
• k を、 b _k ≥ s _kとなる最大の指数（「損益分岐指数」）とします。

需要と供給は両方ともkなので、範囲 [max( s _k , b _k+1 ),min( b _k , s _k+1 )] 内のすべての価格は均衡価格です。4 つの可能なケースそれぞれにおける均衡価格の範囲を考慮すると、これがより簡単にわかります ( kの定義により、b _k+1 < s _k+1であることに注意してください)。

ダブルオークションはゲームとして分析できます。プレイヤーは買い手と売り手です。彼らの戦略は、買い手にとっては入札、売り手にとっては売り値です (買い手と売り手の評価によって異なります)。報酬は、取引価格 (オークション主催者が決定) とプレイヤーの評価によって異なります。興味深い問題は、ナッシュ均衡(どのトレーダーも入札/売り値を一方的に変更するインセンティブを持たない状況) を見つけることです。

買い手がbの入札を提出し、売り手がs を提出する二国間取引のシナリオを考えてみましょう。

競売人が次のように価格を設定するとします。

• s > bの場合、取引は発生しません (売り手は買い手が支払う金額よりも多くを要求します)。
• s ≤ bの場合、 p =( b + s )/2です。

購入者の効用は次のとおりです。

• s > bの場合は 0 ;
• s ≤ bの場合はBp (ここで、Bは購入者の真の値)。

売り手の効用は次のとおりです。

• s > bの場合は 0 ;
• s ≤ bの場合はpS (ここでSは売り手の真の値)。

完全な情報があり、評価が両当事者に共通の知識である場合、純粋戦略効率の良いナッシュ均衡の連続体が存在することが示されます。これは、B>Sの場合、両方のプレーヤーが真の値を宣言する均衡は存在しないことを意味します。つまり、買い手はより低い値を宣言して利益を得ることができるか、売り手はより高い値を宣言して利益を得ることができるかのどちらかです。 ${\displaystyle b=s=p\in [B,S].}$

不完全情報（非対称情報）の場合、買い手と売り手は自分の評価額しか知りません。これらの評価額が同じ区間に均一に分布していると仮定します。すると、そのようなゲームには線形戦略を持つベイジアン ナッシュ均衡があることが示されます。つまり、両方のプレイヤーの入札額が評価額の線形関数である場合に均衡が存在します。また、これは他のベイジアン ナッシュ均衡よりもプレイヤーに高い期待利益をもたらします（Myerson–Satterthwaite 定理を参照）。

競売人は取引価格をどのように決定すべきでしょうか? 理想的なメカニズムは、次の特性を満たします。

1.個人合理性(IR): オークションに参加することで損をする人はいないはずです。特に、すべての取引買い手について: p ≤ B、すべての取引売り手について: p ≥ Sです。

2.均衡予算(BB) には 2 つの種類があります。

• 強力な均衡予算 (SBB): すべての金銭の移動は買い手と売り手の間で行われなければならず、競売人は金銭を失ったり得たりしてはなりません。
• 弱い均衡予算 (WBB): 競売人はお金を失うことはないが、お金を得る可能性はある。

3.インセンティブ適合性(IC) は、真実性または戦略耐性とも呼ばれ、2 つの種類があります (無条件のIC は通常、より強力なバージョンを意味します)。

• より強い概念は、支配的戦略インセンティブ互換性 (DSIC) です。これは、真の値を報告することがすべてのプレイヤーにとって支配的な戦略であるべきであることを意味します。つまり、他のプレイヤーがどのようにプレイするかに関係なく、プレイヤーは他のプレイヤーをスパイして、自分の真の値とは異なる「最適な」宣言を見つけようとすることで利益を得ることはできないはずです。
• より弱い概念は、ナッシュ均衡インセンティブ適合性 (NEIC) です。これは、すべてのプレーヤーが真の評価を報告するナッシュ均衡が存在することを意味します。つまり、1 人を除くすべてのプレーヤーが誠実である場合、残りのプレーヤーも誠実であることが最善です。

4.経済効率(EE): 社会全体の福祉 (すべてのプレイヤーの価値の合計) は、可能な限り最高である必要があります。特に、これは、すべての取引が完了した後、アイテムが、それを最も高く評価する人の手に渡る必要があることを意味します。

残念ながら、これらすべての要件を同じメカニズムで実現することはできません ( Myerson-Satterthwaite の定理を参照)。ただし、それらのいくつかを満たすメカニズムは存在します。

前のセクションで説明したメカニズムは、次のように n 人のプレーヤーに一般化できます。

• 買い手と売り手を自然な順序で並べ、損益分岐点指数kを見つけます。
• 価格をk番目の値の平均に設定します: p =( b _k + s _k )/2。
• 最初のk人の売り手が最初のk 人の買い手に商品を販売します。

このメカニズムは次のとおりです。

• IR - 順序付けにより、最初のk 人のプレイヤーは各アイテムを少なくともpと評価し、最初のk 人の販売者は各アイテムを最大pと評価するためです。
• SBB - すべての金銭の送金は買い手と売り手の間で行われるためです。
• EE - n 個のアイテムは、それらを最も価値あるものと考えるn人のプレイヤーによって保持されるためです。
• IC ではありません - 買い手k には低い値を報告するインセンティブがあり、売り手kには高い値を報告するインセンティブがあるためです。

VCGメカニズムは、真実性を達成しながら社会福祉を最適化する一般的なメカニズムです。これは、各エージェントに、自分の欲望が社会に引き起こす「損害」を支払わせることによって実現されます。

単純な二国間貿易の設定では、これは次のメカニズムに相当します。

• b ≤ sの場合、取引は行われず、商品は売り手のもとに残ります。
• b > sの場合、製品は買い手に行き、買い手はsを支払い、売り手はb を受け取ります。

このメカニズムは次のとおりです。

• IR は、買い手が自分の価値よりも少ない金額を支払い、売り手が自分の価値よりも多くの金額を受け取るためです。
• IC は、買い手が支払う価格は売り手によって決定され、その逆も同様であるためです。誤報告を試みた場合、誤報告者の効用はゼロまたはマイナスになります。
• EE です。製品はそれを最も高く評価する人の手に渡るからです。
• SBB でも WBB でもありません。なぜなら、競売人はb - s を支払わなければならないからです。競売人は実際に取引を補助しなければなりません。

一般的なダブルオークションの設定では、メカニズムは買い手と売り手を自然な順序で並べ、損益分岐点指数kを見つけます。次に、最初のk人の売り手が最初のk 人の買い手に商品を渡します。次の表に示すように、各買い手は最低均衡価格 max( s _k , b _k+1 ) を支払い、各売り手は最高均衡価格 min( b _k , s _k+1 ) を受け取ります。

二国間貿易のシナリオと同様に、メカニズムは IR、IC、EE（社会福祉の最適化）ですが、BB ではなく、オークション主催者が貿易を補助します。

価格の一意性定理^[3]は、この補助金問題が避けられないことを意味しています。つまり、社会福祉を最適化する誠実なメカニズムは、（各トレーダーの売り/買い価格から独立した関数まで）同じ価格になります。取引を補助せずにメカニズムを誠実に保ちたい場合は、効率性を妥協し、最適ではない社会福祉関数を実装する必要があります。

以下のメカニズムは、真実性を維持するために単一の取引を放棄します。^[4]

• 買い手と売り手を自然な順序で並べ、損益分岐点指数kを見つけます。
• 最初のk -1人の売り手は商品を提供し、オークション主催者からsk_を受け取ります。
• 最初のk -1 人の購入者が商品を受け取り、オークション主催者にb _kを支払います。

このメカニズムは次のとおりです。

• IRは以前と同じです。
• IC: 最初のk -1 人の買い手と売り手は、宣言を変更しても価格に影響がないため、宣言を変更するインセンティブがありません。k番目の買い手と売り手は、いずれにせよ取引を行わないため、変更するインセンティブがありません。また、彼らが取引を開始した場合 (たとえば、b _kが宣言をb _{k -1}より上に増やした場合)、取引による利益はマイナスになります。
• SBB ではありません。なぜなら、競売人には ( k -1)( b _k - s _k )の余剰が残るからです。しかし、競売人は少なくとも取引を補助する必要がないので、WBB です。
• EE ではありません。買い手k は売り手kよりも商品の価値が高いと考えていますが、 b _kとs _{k は}取引しません。

このメカニズムを効率的にするために、k番目の買い手と売り手に取引をさせようとすると、価格を変更するインセンティブが生まれるため、不誠実になります。

社会福祉は最適ではないが、禁じられた取引は最も不利な取引なので、最適に近い。したがって、貿易による利益は少なくとも最適である。 ${\displaystyle 1-1/k}$

二国間貿易の設定では、k =1 であり、唯一の効率的な取引を放棄するため、貿易はまったく行われず、貿易による利益は 0 になることに注意してください。これは、マイヤーソン-サッタースウェイトの定理に従います。

ババイオフ、ニサン、パブロフ^{[5]は、貿易削減メカニズムを}空間的に分散した市場に一般化した。つまり、買い手と売り手が複数の異なる場所にいて、商品の一部はこれらの場所間で輸送される必要がある場合である。輸送コストは、したがって、売り手の生産コストに加算される。

マカフィー^[4]は貿易削減メカニズムの次のようなバリエーションを提示した。

• 買い手と売り手を自然な順序で並べ、損益分岐点指数kを見つけます。
• 計算：p =( b _{k +1} + s _{k +1} )/2。
• b _k ≥ p ≥ skの場合、最初のk 人の買い手と売り手_は価格pで商品を取引します。
• それ以外の場合、最初のk -1 人の売り手はs _kと取引し、最初のk -1 人の買い手は、取引削減メカニズムと同様にb _{kと取引します。}

トレード削減メカニズムと同様に、このメカニズムはIR、IC、WBBですが、SBB（2番目のケース）やEE（2番目のケース）ではありません。買い手と売り手の値がすべてゼロより上に制限されていると仮定すると、マカフィーはトレード効率の損失が1/min（買い手の数、売り手の数）に制限されることを証明しています。^[4]

p∈ [0,1]が与えられた場合、入札が提出された後、確率pでトレード削減メカニズムを使用し、確率1- pでVCGメカニズムを使用します。^[6] このメカニズムは、その親のすべてのプロパティ、つまりIRとICを継承します。パラメータpは、EEとBBのトレードオフを制御します。

• 貿易による利益の損失は 0 (VCG によって達成) または 1/ k (貿易削減によって達成) のいずれかです。したがって、貿易による利益の期待損失は最大でp / kです。
• 競売人の余剰は、負（VCG の場合）または正（取引削減の場合）のいずれかです。したがって、期待余剰はp *（取引削減の余剰）-（1- p）*（VCG の赤字）です。トレーダーの値が既知の分布から得られる場合、期待余剰が 0 になるようにp を選択できます。つまり、メカニズムは事前の SBB です。

このメカニズムのバリエーション^[6]では、入札が提出された後、k -1人の安い売り手がk -1人の高い買い手と取引します。彼らはそれぞれ、元のメカニズムの期待される支払いを受け取り/支払います。つまり、各買い手は を支払い、各売り手は を受け取ります。次に、確率pで、買い手kはを支払い、売り手kから商品を購入します。売り手kはを受け取ります。最初のバリエーションと同様に、このバリエーションはIRであり、同じ期待効率と余剰があります。その利点は、そのランダムな特性をほぼすべてのトレーダーから「隠す」ことです。欠点は、メカニズムが事前にのみ真実であることです。つまり、リスク中立のトレーダーは、自分の価値を誤って報告することで期待値を獲得することはできませんが、ロットの結果を知った後、別の方法で報告しなかったことを後悔するかもしれません。 ${\displaystyle pb_{k}+(1-p)\max {(b_{k+1},s_{k})}}$${\displaystyle ps_{k}+(1-p)\min {(s_{k+1},b_{k})}}$${\displaystyle \max {(b_{k+1},s_{k})}}$${\displaystyle \min {(s_{k+1},b_{k})}}$

Segal-Halevi、Hassidim、Aumann ^[7]は、SBBであり、IRとICであり、最適GFTの(1-1/k)を達成する貿易削減メカニズムを提示している。

ババイオフとニサン^{[6] ：第4章では、}さまざまなメカニズムの理論的比較と実証的比較の両方が提供されています。

Dütting、Roughgarden、Talgam-Cohen ^[8]は、ダブルオークションの設計にモジュール方式を提案した。彼らのフレームワークでは、ダブルオークションは市場の各サイドのランキングアルゴリズムと構成ルールで構成されていると考えられており、複雑な市場に適用できる。このフレームワークの直接的な結果は、トレード削減メカニズムなどの古典的なダブルオークションメカニズムが戦略耐性だけでなく、弱いグループ戦略耐性も備えていることである（つまり、買い手と売り手のグループが共同で好みを誤って報告しても利益を得ることはできない）。

基本的なダブルオークションモデルには、買い手と売り手という2つのカテゴリーのトレーダーが関与します。BabaioffとNisan ^[6]は、このモデルを拡張してサプライチェーン（ある市場の買い手が次の市場の売り手になる市場の連鎖）を扱えるようにしました。例えば、農家は果物市場で果物を販売し、ジュース製造業者は果物市場で果物を購入し、ジュースを作ってジュース市場で消費者に販売します。BabaioffとWalsh ^{[9]は、このモデルを任意の有向}非巡回グラフの市場を扱えるように拡張しました。

Gilor、Gonen、Segal-Halevi ^[10]は、エージェントカテゴリの集合Gを持つ多国間市場を研究しています。市場は、市場のレシピと呼ばれるサイズ | G |の整数ベクトルrによって特徴付けられます。市場における各取引には、Gの各gに対して、カテゴリgのr _gエージェントが関与します。標準的なダブルオークション市場は、2つのカテゴリ（買い手と売り手）があり、レシピがr =(1,1)である特殊なケースです。彼らは、SBB、IC、IRであり、最適 GFT の(1-1/ k ) を達成するアルゴリズムを提示しています。1つのアルゴリズムは、取引削減に基づく直接開示メカニズムであり、もう1つは、IC であるだけでなく明らかに ICでもある価格上昇メカニズムです。

Gilor、Gonen、Segal-Halevi ^[11]は、より一般的な多国間市場を研究しています。この市場では、複数の異なるレシピが森のように配置されており、各レシピは根から葉へのパスです。彼らは、普遍的にIR、明らかにIC、SBBであり、漸近的に最適なGFTを達成するランダムな価格上昇メカニズムを提示しています。

• サプライチェーン オークション- ダブル オークションを 2 つ以上のエージェント カテゴリに一般化したもの。
• マイヤーソン・サッタースウェイトの定理- 買い手が 1 人、売り手が 1 人、品物が 1 つしかない場合でも、IR、IC、BB、EE のいずれのメカニズムも存在しません。