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

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

• 批准号: 20K19739
• 负责人: 河瀬 康志
• 金额: $ 2.66万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K19739/
• 关键词: 公平割当; 無羨望性; 多項式時間アルゴリズム; NP困難性; 組合せ最適化; 公平分割; アルゴリズム的ゲーム理論

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

The purpose of this study is to explore the ways in which rational decision-makers can understand the state of the theory, realize the solution, design and calculate the system. When the year is over, the main three research topics are selected. 1. Research on "Distribution Method of Material by Multiple Persons" This topic is based on the application of the data in the distribution of operations. In this case, all the staff are the same. In the case of Shapley's value, the distribution is fair. In the case of multiple distribution, the distribution is standard. This research is aimed at improving the quality of life, social stability, and social stability. 2. The research topic of the present study is: "To confirm the effectiveness of the control system." There are many problems in the social market. This study is based on the characteristics of successive autocratic approaches, and the conditions and constraints of successive autocratic approaches. 3. The research topic of this paper is "Design of the most suitable materials based on the theory of accumulation". The theory of accumulation and rational decision-making under uncertain conditions are discussed in this paper. This study proposes a theoretical basis for calculating the optimal solution for maximizing the return rate of revenue in the case of sales.

项目成果

Online Scheduling on Identical Machines with a Metric State Space

• DOI: 10.4230/lipics.stacs.2022.32
• 发表时间: 2022
• 作者: Hiromichi Goko;A. Kawamura;Yasushi Kawase;K. Makino;Hanna Sumita

Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks

• DOI: 10.1145/3539597.3570444
• 发表时间: 2022-11
• 期刊: Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining
• 作者: Yasushi Kawase;Atsushi Miyauchi;Hanna Sumita

Fair Ride Allocation on a Line

线路上的公平乘车分配

• DOI: 10.1007/978-3-031-15714-1_24
• 发表时间: 2022
• 期刊: Lecture Notes in Computer Science
• 作者: Yuki Amano;Ayumi Igarashi;Yasushi Kawase;Kazuhisa Makino;Hirotaka Ono
• 通讯作者: Hirotaka Ono

Efficient matching under general constraints

• DOI: 10.1016/j.geb.2024.03.013
• 发表时间: 2024-03
• 期刊: Games Econ. Behav.
• 作者: Kenzo Imamura;Yasushi Kawase

オンライン最適化の競合比解析

在线优化的竞争比分析

• 发表时间: 2021
• 作者: 安澤俊紀;中村友美;上嶋 繁;美馬 晶;Tomoaki Kawano;河瀬康志
• 通讯作者: 河瀬康志