マトロイド理論・離散凸解析理論に基づく社会システム解析理論の構築

基于拟阵理论和离散凸分析理论的社会系统分析理论构建

基本信息

批准号：
20K11699
负责人：
高澤兼二郎
金额：
$ 2.66万
依托单位：
Hosei University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

本年度の研究業績のうち，本研究課題において重要なものは，論文「A common generalization of budget games and congestion games」である．Budget game (予算ゲーム) とは，資源配分問題に由来する非協力ゲームのモデルである．予算ゲームについては，各プレイヤーの戦略空間がマトロイドの基族である場合に純粋ナッシュ均衡が存在するなど，混雑ゲームと様々な共通点をもつことが示されていたが，混雑ゲームとの理論的な関係は明らかにされていなかった．本論文では，一般化予算ゲームという，予算ゲームと混雑ゲームの共通の一般化を提案することを通じて，これら二つのゲームがもつ共通の構造を明らかにした．本論文は，アルゴリズム的ゲーム理論に関する査読付き国際会議「The 15th International Symposium on Algorithmic Game Theory (SAGT 2022)」に採択された．また，論文「Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications」では，マトロイドのロバスト最適化や，混雑ゲームの社会的最適解の計算を含む離散凸最適化の枠組みに対し，効率的なアルゴリズムを設計した．本論文は，数理最適化に関するトップジャーナル「Mathematical Programming」に採録された．その他，M凸関数の制約付き最適化や，劣モジュラ関数の一般化の最適化に関する論文などが新たに査読付き国際論文誌に採録された．

在今年的研究成果中，本研究课题最重要的就是《预算博弈和拥堵博弈的共同概括》论文。预算博弈是一种源于资源分配问题的非合作博弈模型。预算博弈已被证明与拥塞博弈有许多相似之处，例如当每个参与者的策略空间是拟阵矩阵时是否存在纯纳什均衡关系尚未明确。在本文中，我们提出了预算博弈和拥堵博弈的共同推广，称为广义预算博弈，并阐明了这两种博弈的共同结构。该论文被第 15 届算法博弈论国际研讨会 (SAGT 2022) 接收，这是一个经过同行评审的算法博弈论国际会议。此外，论文《具有交集约束的最优拟阵基：评估拟阵、M-凸函数及其应用》介绍了离散凸优化的框架，包括拟阵的鲁棒优化和拥塞博弈的社会最优解的计算为此，我们设计了一种高效的算法。该论文被数学优化领域顶级期刊《Mathematical Planning》接收。此外，关于M凸函数的约束优化和子模函数的广义优化的论文也被同行评审的国际期刊新接收。

项目成果

期刊论文数量（26）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

在顶点加权有向图中查找流行分支

DOI：
10.1016/j.tcs.2023.113799
发表时间：
2023
期刊：
影响因子：
1.1
作者：
Kei Natsui; Kenjiro Takazawa
通讯作者：
Kenjiro Takazawa

Minimizing submodular functions on diamonds via generalized fractional matroid matchings

通过广义分数拟阵匹配最小化钻石的子模函数

DOI：
10.1016/j.jctb.2022.07.005
发表时间：
2022
期刊：
影响因子：
0
作者：
Fujishige Satoru;Kiraly Tamas;Makino Kazuhisa;Takazawa Kenjiro;Tanigawa Shin
通讯作者：
Tanigawa Shin

A common generalization of budget games and congestion games

预算博弈和拥堵博弈的常见概括