Ant Colony Optimization for Continuous Domains Applied to Cooperative Game

doi:10.3778/j.issn.1002-8331.2007-0322

Abstract

Abstract:

In the theoretical research of cooperative games, the classic solution concept of cooperative game does not embody the limited rationality and interactional game-playing behavior of the player in the solution process. In the real world, the allocation schemes are often formed through the player’s rational interaction and strategic changes. This paper introduces rational factors and control factors to describe the players’ decision-making behaviors during the game, establishes a cooperative game model considering interaction behavior, and uses ant colony optimization for continuous domains to solve the cooperative game. An example shows that this method can ensure the allocation scheme satisfies the effectiveness and the individual rationality, and can quickly obtain the only allocation scheme of the alliance. It provides a new idea and tool for solving cooperative games.

Key words: cooperative game, interactive behavior, negotiation, ant colony optimization for continuous domains

摘要：

在合作博弈的理论研究中，经典的合作博弈解概念在求解过程中没有体现出局中人的有限理性和互动博弈行为。而在现实博弈环境中，联盟的分配方案更多是通过局中人间理性互动与策略博弈形成的。引入理性因子和控制因子来描述局中人在博弈过程中的决策行为，建立了考虑互动行为的合作博弈模型，并利用连续蚁群算法对合作博弈进行求解。算例表明该解法可以保证分配方案满足有效性和个体理性，并能快速得到联盟的唯一分配方案。这为合作博弈的求解提供了新的思路与工具。

关键词: 合作博弈, 互动行为, 谈判, 连续蚁群算法

LI Zhuangkuo, CHANG Kaixuan. Ant Colony Optimization for Continuous Domains Applied to Cooperative Game[J]. Computer Engineering and Applications, 2021, 57(24): 198-204.

李壮阔，常凯旋. 合作博弈的连续蚁群算法求解[J]. 计算机工程与应用, 2021, 57(24): 198-204.

References

[1] VON NEUMANN J，MORGENSTERN O.Theory of games and economic behavior[M].Princeton：Princeton University Press，1944.
[2] MAS-COLELL A.Cooperative equilibrium[M]//The new palgrave：a dictionary of economics，1989：95-102.
[3] GILLIES D.Some theorems on [n]-person games[M].Princeton：Princeton University Press，1953.
[4] AUMANN R J，MASCHLER M.The bargaining set for cooperative games[M].Princeton：Princeton University Press，1961.
[5] DAVIS M，MASCHLER M.The kernel of a cooperative game[J].Naval Research Logistics Quarterly，1965，12（3）：223-259.
[6] SCHMEIDLER D.The nucleolus of a characteristic function game[J].SIAM Journal on Applied Mathematics，1969，17（6）：1163-1170.
[7] SHAPLEY L S.A value for [n]-person games[J].Contributions to the Theory of Games，1953，28（2）：307-317.
[8] MYERSON R B.Graphs and cooperation in games[J].Mathematics of Operations Research，1977，2（3）：225-229.
[9] HERINGS P J J，VAN DER LAAN G，TALMAN A，et al.The average tree solution for cooperative games with communication structure[J].Games and Economic Behavior，2010，68（2）：626-633.
[10] BANZHAF J F.Weighted voting doesn’t work：a mathematical analysis[J].Rutgers Law Review，1964，19：317-343.
[11] BACKHOUSE R.New directions in economic methodology[M]//New directions in economic methodology.Routledge：[s.n.]，1994.
[12] 叶文海，陈亮，李廖平.Isight在博弈多目标优化中的应用[J].福州大学学报（自然科学版），2017，45（3）：391-397.
YE W H，CHEN L，LI L P.The application of Isight in multi-objective optimization with game[J].Journal of Fuzhou University（Natural Science Edition），2017，45（3）：391-397.
[13] 刘雨潇，王毅，袁磊，等.基于纳什议价解的多目标合作博弈云任务调度[J].计算机工程与设计，2017，38（12）：3316-3323.
LIU Y X，WANG Y，YUAN L，et al.Multi-objective cooperative game scheduling of cloud tasks based on Nash bargaining solution[J].Computer Engineering and Design，2017，38（12）：3316-3323.
[14] 潘颖慧，曾一锋.交互式动态影响图研究及其最优K模型解法[J].计算机学报，2018，41（1）：28-46.
PAN Y H，ZENG Y F.Interactive dynamic influence diagram research summary and new solutions on Top-[K] model selection[J].Chinese Journal of Computers，2018，41（1）：28-46.
[15] 侯德飞，田德红，林聪仁，等.基于博弈的多目标弹药调度策略优化研究[J].南京航空航天大学学报，2019，51（6）：841-847.
HOU D F，TIAN D H，LIN C R，et al.Optimization of Multi-objective ammunition scheduling strategies based on game theory[J].Journal of Nanjing University of Aeronautics & Astronautics，2019，51（6）：841-847.
[16] XU H L，ZHAI Z Y，WANG K，et al.Multiobjective distributed model predictive control method for facility environment control based on cooperative game theory[J].Turkish Journal of Electrical Engineering and Computer Sciences，2017，25（5）：4160-4171.
[17] 丁阳，汪沨，宾峰，等.基于博弈论的多目标配电网重构[J].电力自动化设备，2019，39（2）：28-35.
DING Y，WANG F，BIN F，et al.Multi-objective distribution network reconfiguration based on game theory[J].Electric Power Automation Equipment，2019，39（2）：28-35.
[18] SOCHA K，DORIGO M.Ant colony optimization for continuous domains[J].European Journal of Operational Research，2008，185（3）：1155-1173.
[19] OMRAN M G H，AL-SHARHAN S.Improved continuous Ant Colony Optimization algorithms for real-world engineering optimization problems[J].Engineering Applications of Artificial Intelligence，2019，85.
[20] 夏媛，李俊，周虎.基于跨邻域搜索的连续域蚁群优化算法[J].武汉科技大学学报，2019，42（3）：212-219.
XIA Y，LI J，ZHOU H.Optimized ant colony algorithm for continuous domains based on across neighborhood search[J].Journal of Wuhan University of Science and Technology，2019，42（3）：212-219.
[21] KALAYCI C B，POLAT O，AKBAY M A.An efficient hybrid metaheuristic algorithm for cardinality constrained portfolio optimization[J].Swarm and Evolutionary Computation，2020，54.