組み合わせオークション

組み合わせオークションは、参加者が個々のアイテムや連続した量ではなく、離散的な異質アイテムの組み合わせ、つまり「パッケージ」に入札できるタイプのスマートマーケットです。これらのパッケージはロットとも呼ばれ、オークション全体はマルチロットオークションと呼ばれます。^[1]組み合わせオークションは、入札者がアイテムの束に対して非加法的な評価を持っている場合、つまり、組み合わせの個々の要素の評価の合計よりも高いか低いアイテムの組み合わせを評価する場合に適用されます。

不動産オークションでは、アイテムのパッケージに対する入札を受け入れるのが一般的な手順である単純な組み合わせオークションが長年使用されてきました。最近では、トラック輸送、バス路線、産業調達、無線通信用の無線周波数の割り当てに使用されています。近年、調達チームは商品やサービスの調達に逆組み合わせオークションを適用しています。このアプリケーションは、しばしば調達最適化と呼ばれます。建設調達では、複数のコンポーネントをめぐる交渉が含まれることが多いため、この業界では、組み合わせ逆オークションがコスト削減に推奨されています。^[2]

組み合わせオークションでは、入札者の表現力が高まりますが、従来のオークションと比較すると、計算上およびゲーム理論上の課題があります。計算上の問題の例としては、入札がオークション主催者に提出された後、どのように効率的に割り当てを決定するかが挙げられます。これは勝者決定問題と呼ばれます。

勝者決定問題は、次のように表現できます。組み合わせオークションの入札セットが与えられた場合、オークション主催者が一部のアイテムを保持する可能性も含め、オークション主催者の収益を最大化する入札者へのアイテムの割り当てを見つけます。この問題は、大規模なインスタンスでは困難です。具体的には、NP 困難であり、最適な割り当てを見つける多項式時間アルゴリズムは存在しないと推測されます。組み合わせオークション問題は、セットパッキング問題としてモデル化できます。そのため、組み合わせオークション問題の近似解を見つけるためのアルゴリズムが多数提案されています。たとえば、Hsieh (2010) は、組み合わせ逆オークション問題に対するラグランジュ緩和アプローチを提案しました。

組み合わせオークションのこれらの側面の多くは、いくつかの現実世界の例も含めて、Cramton、Shoham、Steinberg (2006) が編集した包括的な書籍でも説明されています。

組み合わせオークションは、空港の着陸スロットの割り当てのために、ラッセンティ、スミス、ブルフィン (1982) によって初めて提案されました。彼らの論文では、オークション主催者の問題の数理計画法による定式化、勝者決定問題とセットパッキング問題の関係、計算の複雑さの問題、組み合わせオークションをテストするための実験経済学の手法の使用、組み合わせオークションにおけるインセンティブの適合性と需要の開示の問題の考慮など、組み合わせオークションに関する 多くの重要なアイデアが紹介されました。

組み合わせオークションの特殊なケースとして、組み合わせクロックオークション（CCA）があります。これは、入札者が価格上昇に応じて確認を行うクロックオークションと、入札者が密封されたパッケージ入札を行うその後の密封入札オークションを組み合わせたものです。競売人は最終入札を使用して、最良価値配分とヴィックリー支払いを計算します。^{[3] [4]} CCAは、競合他社のコストを引き上げやすいことが示されています。^{[5] [6]}

• 最適化（数学）  - 最適化問題に対する数学的アルゴリズムの研究Pages displaying short descriptions of redirect targets
• 組合せゲーム理論 – 完全情報を持つ2人プレイヤーの連続ゲームに関するゲーム理論の分野
• ファーストプライスオークション – 参加者全員が同時に非公開の入札を行うオークションPages displaying short descriptions of redirect targets

• Peter Cramton、 Yoav Shoham、Richard Steinberg (2006)。Combinatorial Auctions。MIT Press。ISBN 0-262-03342-9 。このトピックを幅広くカバーする寄稿本。 
• de Vries, S.; Vohra, R. (2003). 「組み合わせオークション: 調査」(PDF) . INFORMS Journal on Computing . 15 (3): 284–309. CiteSeerX  10.1.1.23.8046 . doi :10.1287/ijoc.15.3.284.16077. ISSN  1526-5528.少し古いですが、古典的な調査です。
• ヴァジラニ、ヴィジェイ V. ;ニサン, ノーム;ティム・ラフガーデン;タルドス、エヴァ(2007)。アルゴリズムゲーム理論(PDF)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0。. コンピュータサイエンス理論の観点から組み合わせオークションについて優れた入門章を備えた寄稿本。第11章を参照。^{: 267–299}
• Rassenti, Stephen J. ; Smith, Vernon L.; Bulfin, Robert L. (1982). 「空港のタイムスロット割り当てのための組み合わせオークションメカニズム」(PDF) . Bell Journal of Economics . 13 (2): 402–417. doi :10.2307/3003463. JSTOR  3003463. 2009-01-15 にオリジナルからアーカイブ。2023-06-22に取得。{{cite journal}}: CS1 maint: bot: original URL status unknown (link)組み合わせオークションのアイデアを普及させた初期の作品。
• Rothkopf, M.; Pekec, A.; Harstad, R. (1998). 「計算的に管理可能な組み合わせオークション」. Management Science . 44 (8): 1131–1147. CiteSeerX  10.1.1.723.9753 . doi :10.1287/mnsc.44.8.1131.計算上の考慮事項に関する影響力のある初期の論文。
• Hammami, Farouk; Rekik, Monia; Coelho, Leandro C. (2019)。「異機種車両による輸送調達オークションの入札構成問題に対する正確かつヒューリスティックなソリューションアプローチ」。輸送研究パート E: ロジスティクスと輸送レビュー。127 : 150–177。doi : 10.1016 /j.tre.2019.05.009。S2CID 182223089  。輸送サービスの調達における組み合わせオークションの応用。
• Hsieh, Fu-Shiung (2010). 「ラグランジュ乗数の発見に基づく組み合わせ逆オークション」(PDF) .意思決定支援システム. 48 (2): 323–330. doi :10.1016/j.dss.2009.08.009.
• パラシオス・ウエルタ、イグナシオ、デイビッド・C・パークス、リチャード・スタインバーグ。2024年。「組み合わせオークションの実践」経済文献ジャーナル、62（2）：517-53。
• ショーハム、ヨアブ、レイトンブラウン、ケビン (2009)。マルチエージェントシステム：アルゴリズム、ゲーム理論、論理的基礎。ニューヨーク：ケンブリッジ大学出版局。ISBN 978-0-521-89943-7。教科書形式の概要。セクション 11.3 を参照してください。オンラインで無料でダウンロードできます。