Auction design for two-sided markets: an approach from discrete optimization

双边市场的拍卖设计：离散优化方法

• 批准号: 21K19759
• 负责人: 平井 広志
• 金额: $ 4.08万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Challenging Research (Exploratory)
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-07-09 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21K19759/
• 关键词: オークション; メカニズムデザイン; 双方向市場; ポリマトロイド; 予算制約; 多面体的クリンチングオークション; アルゴリズム

不可分財（分割できない品物）に対する多面体的クリンチングオークションの研究において進展があった。既存の多面体的クリンチングオークションの研究は可分財を対象とするが、実社会におけるオークションでは不可分財を扱うことが多く、不可分財での理論整備も重要である。双方向市場への更なる拡張を見据えたうえで、まずはGoel et al. (2015)による片方向市場の多面体的クリンチングオークションを不可分財に拡張する研究に取り組んだ。不可分財を扱うことは割当に整数制約が加わることに対応するが、本研究では需要の定義に修正を施すことで当該制約を満たすように拡張できることを明らかにした。次に、提案手法のもとでの性質を調べたところ、Goel et al. (2014)により可分財の場合で示された買い手の脱落に関する特徴付けが保持されないことがわかった。この特徴付けは効率性の理論保証の拠り所となっている重要な性質である。そこで提案手法における構造的な性質を調べ、買い手の脱落時に関する特徴付けを与えた。さらに、その特徴づけを利用し、効率性（パレート最適性・流動的余剰・社会余剰）の理論保証を与えた。これらの成果は双方向市場の多面体的クリンチングオークションの理論を深化させる際の土台となるものであるとともに、片方向市場の不可分財へのクリンチングオークションにおける既存の理論保証を大きく強化するものである。以上の成果を論文にまとめ、査読付き国際会議に投稿を行った。また、研究協力者の佐藤良亮氏（指導学生）によって、Hirai and Sato (2022)の多面体的クリンチングオークションを「単一サンプルの仮定」という比較的弱い仮定のもとで適用できるように拡張され、そのアルゴリズムが優れた性質を満たすことが明らかにされた。この成果についても論文にまとめられ、査読付き国際会議に現在投稿中である。

在对不可分割的商品（单个商品）的多面体倾斜拍卖的研究中，取得了进展。现有的多面体倾斜拍卖的研究集中在可分离的商品上，但是在现实世界中，拍卖中通常涉及不可分割的商品，而对不可分割的商品的理论开发也很重要。为了进一步扩展到双向市场，我们首先在Goel等人那里工作。 （2015年）将单向市场的多面体倾向拍卖扩大到不可分割的商品。处理不可分割的商品对应于在分配中增加整数约束，但是这项研究表明，通过修改需求的定义，可以将其扩展以满足约束。接下来，我们研究了所提出的方法的性质，并发现Goel等人。 （2014年）没有保留在可分开商品中显示的买方遗漏的表征。这种表征是基于理论保证效率的重要特性。因此，我们研究了所提出的方法的结构特性，并提供了有关丢弃买方的表征。此外，这种表征用于提供效率的理论保证（帕累托最优性，流体盈余，社会盈余）。这些结果为加深双向市场中多面体倾斜拍卖的理论提供了基础，并极大地增强了现有的理论保证，可以将拍卖限制在单向市场中不可分割的商品中。上述结果被编译成论文，并提交给同行评审的国际会议。此外，研究合作者Sato Ryosuke（讲师）扩展了Hirai和Sato（2022）的多面体冠军拍卖（2022年），将在“单个样本假设”的相对较弱的假设下应用，这表明该算法符合其出色的特性。该结果也已汇编成一篇论文，目前正在接受同行评审的国际会议。

项目成果

Polyhedral Clinching Auctions for Indivisible Goods

• DOI: 10.48550/arxiv.2303.00231
• 发表时间: 2023-03
• 期刊: ArXiv
• 作者: H. Hirai;Ryosuke Sato

多面体的クリンチングオークションの効率性について

论多面体咬合拍卖的效率

• 发表时间: 2022
• 作者: 佐藤 良亮;平井広志;佐藤 良亮
• 通讯作者: 佐藤 良亮