連続オークション

シーケンシャルオークションとは、複数の商品を同じ潜在的購入者グループに順番に販売するオークションです。シーケンシャル・ファーストプライスオークション（SAFP）では、個々の商品はファーストプライスオークションで販売されますが、シーケンシャル・セカンドプライスオークション（SASP）では、個々の商品はセカンドプライスオークションで販売されます。

シーケンシャルオークションは、多くのアイテムが同時にオークションにかけられ、エージェントが複数のアイテムをまとめて入札できるコンビナトリアルオークションとは異なります。シーケンシャルオークションは実装がはるかに簡単で、実務上もより一般的です。しかし、各オークションの入札者は、今後もオークションが行われることを知っており、これが戦略的な考慮に影響を与える可能性があります。以下にいくつか例を挙げます。

例1. [ ^1]売りに出されている商品が2つあり、アリスとボブという2人の買い手がいて、評価額は次の通りです。

• アリスは各アイテムを 5 と評価し、両方のアイテムを 10 と評価します (つまり、彼女の評価は加算的です)。
• ボブは各アイテムを 4 と評価し、両方のアイテムを 4 と評価します (つまり、彼の評価は単位需要です)。

SASPでは、各商品はセカンドプライスオークションにかけられます。通常、このようなオークションは誠実な仕組みであるため、各商品が個別に売却された場合、アリスは両方の商品を落札し、それぞれ4を支払います。アリスの合計支払額は4+4=8となり、アリスの純効用は5+5-8=2となります。しかし、アリスがボブの評価額を知っている場合、アリスはより良い戦略を立てることができます。最初の商品をボブに落札させる（例えば0で入札する）のです。そうすれば、ボブはセカンドプライスオークションには全く参加せず、アリスは2番目の商品を落札し、0を支払います。アリスの純効用は5-0=5となります。

SAFPでも同様の結果が得られます。各アイテムが個別に販売された場合、アリスが4をわずかに上回る価格で入札して勝利し、アリスの純効用が2をわずかに下回るナッシュ均衡が存在します。しかし、アリスがボブの評価額を知っていれば、第1ラウンドでボブが勝利し、第2ラウンドで0をわずかに上回る価格でアリスが勝利できるような戦略に転換することができます。

例 2。 [ ^2]複数の同一物件がオークションにかけられ、エージェントには予算上の制約がある。入札者にとっては、ライバルの価格を引き上げ予算を使い果たして 2 番目の物件をより安い価格で入手することを目的として、1 つの物件に積極的に入札することが有利になることがある。実際には、入札者は別の市場で優位に立つために、1 つの市場で「ライバルのコストを上げる」ことを望む可能性がある。このような考慮は、連邦通信委員会が実施した無線周波数ライセンスのオークションで重要な役割を果たしたと思われる。ライバル入札者の予算上の制約の評価は、 GTEの入札チーム による入札前準備の主要な要素であった。

ナッシュ均衡

シーケンシャルオークションはシーケンシャルゲームの特殊なケースである。このようなゲームにおいて自然に問われるのは、純粋戦略における部分ゲーム完全均衡（SPEPS）が存在するかどうかである。プレイヤーが完全情報（つまり、オークションの順序を事前に知っている）を持ち、各ラウンドで単一のアイテムが売却される場合、SAFPはプレイヤーの評価に関わらず、常にSPEPSを持つ。証明は後方帰納法による：^{[1] : 872–874}

• 最終ラウンドでは、単純なファーストプライスオークションが行われます。このオークションは純粋戦略ナッシュ均衡を持ち、最高値を提示したエージェントが2番目に高い値よりわずかに高い値で入札することで勝利します。
• これまでの各ラウンドでは、状況は外部性を伴うファーストプライスオークションの特殊なケースでした。このようなオークションでは、各エージェントは、自身が勝利した場合だけでなく、他のエージェントが勝利した場合にも価値を獲得する可能性があります。一般に、エージェントの評価はベクトル で表され、 はエージェントが勝利した場合の価値です。シーケンシャルオークションでは、外部性は将来のラウンドにおける均衡結果によって決定されます。導入例では、2つの結果が考えられます。 ${\displaystyle i}$ ${\displaystyle v_{i}[1],\dots ,v_{i}[n]}$ ${\displaystyle v_{i}[j]}$ ${\displaystyle i}$ ${\displaystyle j}$
  • アリスが第1ラウンドに勝った場合、第2ラウンドの均衡結果は、アリスが5ドル相当の商品を4ドルで購入することとなり、^[3]、彼女の純利益は1ドルとなります。したがって、第1ラウンドに勝ったことによる彼女の総価値は となります。${\displaystyle v_{\text{アリス}}[{\text{アリス}}]=5+1=6}$
  • ボブが第1ラウンドで勝った場合、第2ラウンドの均衡結果は、アリスが5ドル相当の商品を0ドルで購入することとなり、アリスの純利益は5ドルになります。したがって、ボブを勝たせることによるアリスの総合的な価値は となります。${\displaystyle v_{\text{アリス}}[{\text{ボブ}}]=0+5=5}$
• 外部性を考慮した各第一価格オークションには、純粋戦略ナッシュ均衡が存在する。^[1]上記の例では、第1ラウンドの均衡はボブが勝って1ドルを支払うというものである。
• したがって、後方誘導により、各 SAFP には純粋戦略 SPE が存在します。

注:

• この存在結果はSASPにも当てはまります。実際、外部性を伴う第一価格オークションの均衡結果は、同じ外部性を伴う第二価格オークションの均衡結果でもあります。
• 存在結果は入札者の評価に関わらず成立する。入札者は不可分財に対して任意の効用関数を持つ可能性がある。対照的に、すべてのオークションが同時に行われる場合、入札者が劣加法的な効用関数を持つとしても、純粋戦略ナッシュ均衡は必ずしも存在しない。^[4]

社会福祉

部分ゲーム完全均衡が存在することが分かれば、次に当然浮かぶ疑問は、それがどれほど効率的か、つまり最大の社会福祉が得られるか、ということだ。これは、無政府状態の価格（PoA）によって定量化される。PoAとは、達成可能な最大社会福祉と最悪の均衡における社会福祉の比である。導入例1では、達成可能な最大社会福祉は10（アリスが両方のアイテムを獲得した場合）であるが、均衡における社会福祉は9（ボブが最初のアイテムを獲得し、アリスが2番目のアイテムを獲得した場合）であるため、PoAは10/9となる。一般に、順次オークションのPoAは入札者の効用関数に依存する。

最初の 5 つの結果は、完全な情報を持つエージェントに適用されます(すべてのエージェントが他のすべてのエージェントの評価を知っています)。

ケース1：同一商品^{[5] [6]}同一商品が複数ある。入札者は2人いる。入札者の少なくとも1人は凹型評価関数（収穫逓減）を持つ。SASPのPoAは最大でである。数値結果によると、凹型評価関数を持つ入札者が多い場合、ユーザー数が増加するにつれて効率損失は減少する。 ${\displaystyle 1/(1-e)\approx 1.58}$

ケース2：加法的な入札者. ^{[1] : 885}商品はそれぞれ異なり、すべての入札者はすべての商品を独立財とみなすため、その評価は加法的な集合関数となる。SASPのPoAは非有界である。つまり、SPEPSにおける厚生は任意に小さくなる可能性がある。

ケース3：単位需要入札者。^{[1]すべての入札者はすべての商品を純粋}代替財と見なすため、その評価額は単位需要となる。SAFPのPoAは最大2である。SPEPSにおける厚生は最大値の少なくとも半分である（混合戦略が許容される場合、PoAは最大4）。対照的に、SASPのPoAはやはり無制限である。

これらの結果は驚くべきものであり、各ラウンドで（セカンドプライスオークションではなく）ファーストプライスオークションを使用するという設計上の決定の重要性を強調しています。

ケース4：劣モジュラー入札者。^[1]入札者の評価値は任意の劣モジュラー集合関数である（加法関数と単位需要関数は劣モジュラーの特殊ケースであることに注意）。この場合、SAFPとSASPの両方のPoAは、入札者が4人しかいない場合でも、有界ではない。直感的には、高値入札者は、将来のラウンドで直面する可能性のある競争を減らすために、低値入札者に勝たせることを好む可能性がある。

ケース5：加法的+UD。^[7]入札者の中には加法的評価を持つ者もいれば、単位需要評価を持つ者もいる。SAFPのPoAは少なくとも となる可能性がある。ここで、mは商品数、nは入札者数である。さらに、弱優位戦略の反復除去下でも、非効率な均衡は持続する。これは、以下を含む多くの自然な状況において線形非効率性を意味する。 ${\displaystyle \min(n,m)}$

• 総代替評価額を持つ入札者、
• 能力評価、
• 予算加算評価、
• 支払いに対する厳しい予算制約を伴う加算的な評価。

ケース6：不完全情報を持つ単位需要入札者。^[8]エージェントは他のエージェントの評価額を知らず、その評価額が導き出された確率分布のみを知っている。この場合、順次オークションはベイズゲームとなり、そのPoAは高くなる可能性がある。すべての入札者が単位需要評価額を持つ場合、 SAFPにおける ベイズ・ナッシュ均衡のPoAは最大で3となる。

収益最大化

複数の商品を販売する販売者にとって、収益を最大化するオークションをどのように設計するかは、実務上重要な問題です。いくつかの疑問があります。

• 1. シーケンシャルオークションと同時オークションのどちらが良いでしょうか？入札がセールの合間に発表されるシーケンシャルオークションの方が好ましいように思われます。なぜなら、入札によって後に販売される商品の価値に関する情報が伝わる可能性があるからです。オークションに関する文献によると、この情報効果は勝者の呪いを軽減するため、売り手の期待収益を増加させることが示されています。しかし、シーケンシャルオークションでは欺瞞効果も生じます。入札者が現在の入札によって後の商品に関する情報が明らかになることを知っていれば、入札額を低く抑えるインセンティブが働きます。^[9]
• 2. 順次オークションを使用する場合、売り手の収益を最大化するために、アイテムをどのような順序で販売する必要がありますか?

2つの商品があり、予算制約下にある入札者グループが存在すると仮定する。これらの商品はすべての入札者に共通の価値を持つが、必ずしも同一である必要はなく、補完財または代替財のいずれかである可能性がある。完全情報ゲームでは、次のようになる。^[2]

• 1. シーケンシャルオークションは、(a) 品物の価値の差が大きい場合、または (b) 品物に顕著な補完性がある場合、同時オークションよりも高い収益をもたらします。
  同時オークションとシーケンシャルオークションを組み合わせた形式は、シーケンシャルオークションよりも高い収益をもたらします。
• 2. オブジェクトが一連の公開オークションによって販売される場合、より価値の高いオブジェクトを最初に販売することが常に最適です (オブジェクトの値が一般に知られていると仮定)。

さらに、予算制約は内生的に生じる可能性があります。例えば、入札企業が担当者に「このオークションには最大Xまでしか出費できません」と伝えても、企業自身にははるかに多くの資金がある場合があります。事前に予算を制限することで、入札者は戦略的に有利になります。

複数の物品が販売される場合、予算制約は予期せぬ結果をもたらす可能性があります。例えば、最低落札価格は非常に低く設定されているため均衡状態において拘束力を持たないにもかかわらず、販売者の収益を増加させる可能性があります。

構成可能なメカニズム

順次オークションと同時オークションは、どちらもより一般的な設定の特殊なケースであり、同じ入札者が複数の異なるメカニズムに参加する。SyrgkanisとTardos ^{[10]は、プレーヤーが複数のメカニズムに同時または順次参加する場合でも良好な特性が保証された効率的なメカニズム設計のための一般的な枠組みを提案している。}滑らかなメカニズム（ほぼ市場均衡価格を生成するメカニズム ）のクラスは、 完全情報設定における均衡と学習結果の両方において、また参加者に関する不確実性を伴うベイズ均衡においても、高品質の結果をもたらす。滑らかなメカニズムはうまく合成される。つまり、各メカニズムにおける局所的な滑らかさは、全体的な効率性を意味する。良好なパフォーマンスを得るために入札者が自分の価値を超えて入札しないことが求められるメカニズムでは、 Vickreyオークションのような弱滑らかなメカニズムを使用することができる。これらは、過剰入札なしの仮定の下では近似的に効率的であり、弱い滑らかさの特性も合成によって維持される。結果の一部は、参加者に予算制約がある場合にも有効である。

参考文献

1. レメ、レナート・パエス、シルグカニス、ヴァシリス、タルドス、エヴァ (2012). 「シーケンシャルオークションと外部性」第23回ACM-SIAM離散アルゴリズムシンポジウム論文集. p. 869. arXiv : 1108.2452 . doi :10.1137/1.9781611973099.70. ISBN 978-1-61197-210-8。
2. Benoit, J.-P.; Krishna, V. (2001). 「予算制約のある入札者による複数オブジェクトオークション」. The Review of Economic Studies . 68 : 155–179 . doi :10.1111/1467-937X.00164.
3. 実際、アリスは4ドルよりわずかに高い金額を支払う可能性があります（例えば、入札がセント単位の場合、アリスは4.01ドルを支払う可能性があります）。簡潔にするため、このわずかな差は無視します。
4. Hassidim, Avinatan; Kaplan, Haim; Mansour, Yishay; Nisan, Noam (2011). 「離散財市場における非価格均衡」.第12回ACM電子商取引会議（EC '11）議事録. p. 295. arXiv : 1103.3950 . doi :10.1145/1993574.1993619. ISBN 9781450302616。
5. Bae, Junjik; Beigman, Eyal; Berry, Randall ; Honig, Michael; Vohra, Rakesh (2008). 「分散スペクトル共有のためのシーケンシャル帯域幅および電力オークション」. IEEE Journal on Selected Areas in Communications . 26 (7): 1193. doi :10.1109/JSAC.2008.080916. S2CID  28436853.
6. Bae, Junjik; Beigman, Eyal; Berry, Randall ; Honig, Michael L.; Vohra, Rakesh (2009). 「スペクトル共有におけるシーケンシャルオークションの効率性について」. 2009 International Conference on Game Theory for Networks . p. 199. CiteSeerX 10.1.1.148.7218 . doi :10.1109/gamenets.2009.5137402. ISBN  978-1-4244-4176-1。
7. Feldman, Michal ; Lucier, Brendan ; Syrgkanis, Vasilis (2013). 「シーケンシャルオークションにおける効率性の限界」. Web and Internet Economics . Lecture Notes in Computer Science. Vol. 8289. p. 160. arXiv : 1309.2529 . doi :10.1007/978-3-642-45046-4_14. ISBN 978-3-642-45045-7。
8. Syrgkanis, Vasilis; Tardos, Eva (2012). 「ベイズ逐次オークション」.第13回ACM電子商取引会議 – EC '12 議事録. p. 929. arXiv : 1206.4771 . doi :10.1145/2229012.2229082. ISBN 9781450314152。
9. Hausch, Donald B. (1986). 「複数物件オークション：順次販売と同時販売」. Management Science . 32 (12): 1599– 1610. doi :10.1287/mnsc.32.12.1599.
10. Syrgkanis, Vasilis; Tardos, Eva (2013). 「構成可能で効率的なメカニズム」.第45回ACMシンポジウム「計算理論に関するシンポジウム – STOC '13」の議事録. p. 211. arXiv : 1211.1325 . doi :10.1145/2488608.2488635. ISBN 9781450320290。