組合せ最適化を用いたゲーム理論的制度設計

使用组合优化的博弈论制度设计

基本信息

批准号：
20K19739
负责人：
河瀬康志
金额：
$ 2.66万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本研究の目的は、複数の意思決定者が関わるゲーム理論的な状況で、望ましい解を実現するための制度設計や計算手法を開発することです。当該年度には、主に3つの研究課題を取り上げました。1つ目は、「複数人で利用した料金の分配方法」についての研究です。この課題は、オフィスの使用料やタクシーの運賃を分配する場合に応用されます。この際、全員が同じタクシーを利用する場合はShapley値で分配することが公平な方法ですが、複数のタクシーに分かれる場合はどのように分配すればよいかの標準的な方法はありません。この研究では、無羨望性、社会的効率性、交換に関する安定性などの性質を調べ、いくつかの望ましい性質を満たすアルゴリズムを提案しました。2つ目の研究課題は、「制約付きマッチングにおける与えられたマッチングのパレート効率性を確認するアルゴリズム」です。制約付きマッチングは、異なるグループの要素を互いにマッチングさせる問題であり、実際の社会や市場において多くの問題があります。この研究では、パレート効率的なマッチングが逐次独裁方式で特徴づけられるための条件は、制約がマトロイド性を満たすことであることを明らかにしました。3つ目の研究課題は、「累積プロスペクト理論に基づく最適な宝くじの設計」です。累積プロスペクト理論は、不確実な状況下での意思決定モデルの1つであり、行動経済学の分野で提唱されました。本研究では、この理論に基づく選好を持つエージェントに対して宝くじを販売する場合に、どのような返金確率にすることが収益を最大化するために最適であるかをモデル化し、効率的に最適解を計算するアルゴリズムを提案しました。

本研究的目的是开发系统设计和计算方法，以在涉及多个决策者的博弈论情况下实现理想的解决方案。今年，我们主要开展了三个研究课题。首先是研究如何为多个用户分配费用。这一挑战适用于分配办公费和出租车费。在这种情况下，如果每个人都使用同一辆出租车，那么使用 Shapley 值进行分配是一种公平的方法，但如果有多辆出租车，则如何分配没有标准方法。在本研究中，我们研究了非嫉妒、社会效率和交换稳定性等属性，并提出了一种满足一些理想属性的算法。第二个研究主题是“一种在约束匹配中检查给定匹配的帕累托效率的算法。”约束匹配是不同群体的要素相互匹配的问题，在现实社会和市场中存在很多问题。在本研究中，我们阐明了帕累托有效匹配被表征为顺序独裁的条件是约束满足拟阵性。第三个研究课题是“基于累积前景理论设计最优彩票”。累积前景理论是行为经济学领域提出的不确定条件下的决策模型之一。在本研究中，我们基于该理论对向具有偏好的代理商出售彩票时实现利润最大化的最优回报概率进行了建模，并提出了一种计算解决方案的算法。

项目成果

期刊论文数量（13）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Efficient Matching under General Constraints

通用约束下的高效匹配

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
Kenzo Imamura;Yasushi Kawase
通讯作者：
Yasushi Kawase

Fair and Truthful Mechanism with Limited Subsidy

公平真实、有限补贴的机制

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
Hiromichi Goko; Ayumi Igarashi; Yasushi Kawase; Kazuhisa Makino; Hanna Sumita; Akihisa Tamura; Yu Yokoi;Makoto Yokoo
通讯作者：
Makoto Yokoo

不可分財の確率的公平割当

不可分割商品的概率公平分配