Algorithmic exact approach to game theory on graphs and networks

图和网络博弈论的算法精确方法

• 批准号: 18710130
• 负责人: OKAMOTO Yoshio
• 金额: $ 2.43万
• 依托单位: Tokyo Institute of Technology (2007-2008)Toyohashi University of Technology (2006)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18710130/
• 关键词: OR; アルゴリズム理論; 組合せ最適化; ゲーム理論; アルゴリズム; グラフ; ネットワーク; 計算幾何; オペレーションズ・リサーチ; 多主体意思決定; 公平配分問題

グラフ・ネットワークに関わる協力ゲーム理論について,アルゴリズム理論・計算理論の観点から精緻な議論を行った.特に,最小彩色ゲームと呼ばれる費用分担問題に対して,今までに提案された公平な費用分担の中のいくつかが効率よく計算できることを示した.それに加えて,コア安定性問題に対する計算量理論的な解析も行った.さらに,最小費用全域木ゲームと呼ばれる費用分担問題に対して,公平費用分担が効率よく計算できるための十分条件である劣モジュラ性を満たす場合の考察をした.

The theory of computation theory and the theory of computation theory are discussed in detail. In particular, the minimum color of the call to share the cost of the problem, now we propose to share the cost of fairness in the middle of the calculation of the efficiency of the problem. The analysis of computational quantity theory for stability problems. The cost sharing problem of minimum cost global system is discussed in this paper.

项目成果

協力ゲーム理論におけるアルゴリズム

合作博弈论中的算法

• 发表时间: 2009
• 作者: 小澤勇騎;大東俊博;森井昌克;Sang Won Bae and Yoshio Okamoto;Yoshio Okamoto;Yoshio Okamoto;岡本吉央;岡本吉央
• 通讯作者: 岡本吉央

Untangling a planar graph.

解开平面图。

• 发表时间: 2009
• 期刊: Discrete & Computational Geometry 42
• 作者: Xavier Goaoc;Jan Kratochvil;Yoshio Okamoto;Chan-Su Shin;Andreas Spillner;Alexander Wolff
• 通讯作者: Alexander Wolff

The Holt-Klee condition for oriented matroids.

定向拟阵的 Holt-Klee 条件。

• 发表时间: 2009
• 期刊: European Journal of Combinatorics 30
• 作者: Komei Fukuda;Sonoko Moriyama;Yoshio Okamoto
• 通讯作者: Yoshio Okamoto

How to make a picturesque maze.

如何制作一个风景如画的迷宫。

• 发表时间: 2009
• 作者: Yoshio Okamoto;Ryuhei Uehara
• 通讯作者: Ryuhei Uehara

A polynomial-time-delay polynomial-space algorithm for enumeration problems in multi-criteria optimization

多标准优化中枚举问题的多项式时滞多项式空间算法

• DOI: 10.1016/j.ejor.2010.10.008
• 发表时间: 2011
• 期刊: European Journal of Operational Research
• 影响因子: 6.4
• 作者: Yoshio Okamoto;Yota Otachi;Ryuhei Uehara;and Takeaki Uno;Kazushige Terui;Kazushige Terui;照井一成;Yoshio Okamoto and Takeaki Uno
• 通讯作者: Yoshio Okamoto and Takeaki Uno