Online multi-stage Colonel Blotto game solving method for resource allocation under contested condition

CHEN Shaofei; ZOU Mingwo; SU Xiaolong; LUO Junren; FENG Junqiao

doi:10.11959/j.issn.2096-6652.202341

您当前的位置：

首页 >

文章列表页 >

Online multi-stage Colonel Blotto game solving method for resource allocation under contested condition

Papers and Reports | 更新时间：2024-04-07

- Online multi-stage Colonel Blotto game solving method for resource allocation under contested condition
- Chinese Journal of Intelligent Science and Technology Vol. 5, Issue 4, Pages: 464-476(2023)
- 作者机构：
  
  国防科技大学智能科学学院，湖南长沙 410073
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-6652.202341
  CLC： TP39
- Received：30 June 2023，
  
  Revised：2023-09-08，
  
  Published：15 December 2023
- 稿件说明：
移动端阅览
CHEN Shaofei, ZOU Mingwo, SU Xiaolong, et al. Online multi-stage Colonel Blotto game solving method for resource allocation under contested condition[J]. Chinese Journal of Intelligent Science and Technology, 2023, 5(4): 464-476.
DOI：

CHEN Shaofei, ZOU Mingwo, SU Xiaolong, et al. Online multi-stage Colonel Blotto game solving method for resource allocation under contested condition[J]. Chinese Journal of Intelligent Science and Technology, 2023, 5(4): 464-476. DOI： 10.11959/j.issn.2096-6652.202341.

摘要

未来战场上的作战资源分配是一个存在总资源预算约束的多阶段对抗问题，具有环境高复杂性、动态不确定性、博弈强对抗性。基于布洛托博弈模型，首先把多阶段对抗场景下的资源分配问题建模为双层在线布洛托博弈，然后将原资源分配问题转化为有向无环图上的在线最短路径问题，并借鉴拉格朗日博弈对资源分配问题进行分析求解。此外，提出LagrangeBwK-Exp3-G算法以实现多阶段对抗条件下资源分配问题的高概率遗憾最小化，进一步通过数学推导获得关于时间范围

的高概率遗憾界。最后，设计一个多阶段对抗条件下的卫星通信多信道功率分配实验，从而验证LagrangeBwK-Exp3-G算法具有良好性能。

Abstract

The allocation of combat resources on the future battlefield is a multi-stage confrontation problem with total resource budget constraints

which is characterized by high complexity of environment

dynamic uncertainty

and strong game confrontation. Based on the Blotto game model

the research firstly modelled the resource allocation problem in the multi-stage confrontation scenario as a two-level online Blotto game

then transformed the original problem into an online shortest path problem on a directed acyclic graph to realize the intuitive formulation of the resource allocation problem. The resource allocation problem was analyzed and solved by referring to the Lagrange game. In addition

the LagrangeBwK-Exp3-G algorithm was proposed to minimize the high probability regret of the resource allocation problem under the condition of multi-stage antagonism

and the high-probability regret bound of the algorithm on the time range

was obtained by mathematical derivation. Finally

a multi-channel power allocation experiment of satellite communication under the condition of multi-stage confrontation was designed

to verify the good performance of LagrangeBwK-Exp3-G algorithm.

关键词

Keywords

references

郭行 , 符文星 , 闫杰 . 浅析美军马赛克战作战概念及启示 [J ] . 无人系统技术 , 2020 , 3 ( 6 ): 92 - 106 .

GUO H , FU W X , YAN J . Analysis and inspiration of the U. S. force's concept of mosaic warfare [J ] . Unmanned Systems Technology , 2020 , 3 ( 6 ): 92 - 106 .

吴明曦 . 智能化战争: AI军事畅想 [M ] . 北京 : 国防工业出版社 , 2020 .

WU M X . Intelligent warfare: the imagination of the AI military [M ] . Beijing : National Defense Industry Press , 2020 .

GRANA J , LAMB J , O'DONOUGHUE N A . Findings on mosaic warfare from a colonel blotto game [M ] . Santa Monica : RAND Corporation , 2021 .

BOREL E . La théorie du jeu et les équations intégralesa noyau symétrique [J ] . Comptes Rendus De l'AcadÉMie Des Sciences , 1921 , 173 : 1304 - 1308 .

KOVENOCK D , ROBERSON B . Generalizations of the general lotto and colonel blotto games [J ] . Economic Theory , 2021 , 71 ( 3 ): 997 - 1032 .

ZOU M W , CHEN S F , LUO J R , et al . An evolutionary learning approach for anti-jamming game in cognitive radio confrontation [C ] // Proceedings of 2022 IEEE International Conference on Systems, Man, and Cybernetics . Piscataway : IEEE Press , 2022 : 3210 - 3215 .

ZHANG L , WANG Y , MIN M H , et al . Privacy-aware laser wireless power transfer for aerial multi-access edge computing: a colonel blotto game approach [J ] . IEEE Internet of Things Journal , 2023 , 10 ( 7 ): 5923 - 5939 .

ZHOU X B , DONG X D , ZHAO L P , et al . Learning-driven cloud resource provision policy for content providers with competitor [J ] . IEEE Transactions on Cloud Computing , 2022 , 10 ( 3 ): 1913 - 1924 .

CHEN A K , FERGUSON B L , SHISHIKA D , et al . Path defense in dynamic defender-attacker blotto games (dDAB) with limited information [C ] // Proceedings of 2023 American Control Conference (ACC) . Piscataway : IEEE Press , 2023 : 447 - 453 .

SHISHIKA D , GUAN Y , DOROTHY M , et al . Dynamic defender-attacker blotto game [C ] // Proceedings of 2022 American Control Conference (ACC) . Piscataway : IEEE Press , 2022 : 4422 - 4428 .

KHARLAMOV V V . On asymptotic strategies in the stochastic colonel blotto game [J ] . Theory of Probability & Its Applications , 2022 , 67 ( 2 ): 318 - 326 .

ANBARCI N , CINGIZ K , ISMAIL M S . Proportional resource allocation in dynamic n-player Blotto games [J ] . Mathematical Social Sciences , 2023 , 125 : 94 - 100 .

NEU G . Explore no more: improved high-probability regret bounds for non-stochastic bandits [J ] . Advances in Neural Information Processing Systems , 2015 , 2015-January: 3168- 3176 .

FREUND Y , SCHAPIRE R E . A decision-theoretic generalization of on-line learning and an application to boosting [J ] . Journal of Computer and System Sciences , 1997 , 55 ( 1 ): 119 - 139 .

DANI V , KAKADE S M , HAYES T . The price of bandit information for online optimization [C ] // Proceedings of the 20th International Conference on Neural Information Processing Systems . New York : ACM , 2007 : 345 - 352 .

PANIGRAHY N K , BASU P , NAIN P , et al . Resource allocation in one-dimensional distributed service networks with applications [J ] . Performance Evaluation , 2020 , 142 : 102110 .

ABDALLAH M . Effects of behavioral decision-making in game-theoretic frameworks for security resource allocation in networked systems [D ] . West Lafayette : Purdue University Graduate School , 2022 .

VU D Q , LOISEAU P . Colonel blotto games with favoritism: competitions with pre-allocations and asymmetric effectiveness [C ] // Proceedings of the 22nd ACM Conference on Economics and Computation . New York : ACM , 2021 : 862 - 863 .

张骁雄 , 葛冰峰 , 谭跃进 . 军事攻防中的多属性资源分配对策模型 [J ] . 国防科技大学学报 , 2018 , 40 ( 5 ): 153 - 160 .

ZHANG X X , GE B F , TAN Y J . Multi-attribute game theoretic model for resource allocation in military attack-defense application [J ] . Journal of National University of Defense Technology , 2018 , 40 ( 5 ): 153 - 160 .

刘冰雁 , 叶雄兵 , 周赤非 , 等 . 基于改进DQN的复合模式在轨服务资源分配 [J ] . 航空学报 , 2020 , 41 ( 5 ): 256 - 264 .

LIU B Y , YE X B , ZHOU C F , et al . Allocation of composite mode on-orbit service resource based on improved DQN [J ] . Acta Aeronautica et Astronautica Sinica , 2020 , 41 ( 5 ): 256 - 264 .

孙宇祥 , 彭益辉 , 李斌 , 等 . 智能博弈综述: 游戏AI对作战推演的启示 [J ] . 智能科学与技术学报 , 2022 , 4 ( 2 ): 157 - 173 .

SUN Y X , PENG Y H , LI B , et al . Overview of intelligent game: enlightenment of game AI to combat deduction [J ] . Chinese Journal of Intelligent Science and Technology , 2022 , 4 ( 2 ): 157 - 173 .

李宪港 , 李强 . 典型智能博弈系统技术分析及指控系统智能化发展展望 [J ] . 智能科学与技术学报 , 2020 , 2 ( 1 ): 36 - 42 .

LI X G , LI Q . Technical analysis of typical intelligent game system and development prospect of intelligent command and control system [J ] . Chinese Journal of Intelligent Science and Technology , 2020 , 2 ( 1 ): 36 - 42 .

ROBBINS H . Some aspects of the sequential design of experiments [J ] . Bulletin of the American Mathematical Society , 1952 , 58 ( 5 ): 527 - 535 .

GYÖRGY A , LINDER T , LUGOSI G , et al . The on-line shortest path problem under partial monitoring [J ] . Journal of Machine Learning Research , 2007 , 8 ( 10 ): 2369 - 2403 .

LAI T L , ROBBINS H , et al . Asymptotically efficient adaptive allocation rules [J ] . Advances in Applied Mathematics , 1985 , 6 ( 1 ): 4 - 22 .

AUER P , CESA-BIANCHI N , FISCHER P . Finite-time analysis of the multiarmed bandit problem [J ] . Machine Learning , 2002 , 47 ( 2 ): 235 - 256 .

AUER P , CESA-BIANCHI N , FREUND Y , et al . The nonstochastic multiarmed bandit problem [J ] . SIAM Journal on Computing , 2002 , 32 ( 1 ): 48 - 77 .[LinkOut ]

IMMORLICA N , SANKARARAMAN K A , SCHAPIRE R , et al . Adversarial bandits with knapsacks [C ] // Proceedings of 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) . Piscataway : IEEE Press , 2019 : 202 - 219 .

BADANIDIYURU A , KLEINBERG R , SLIVKINS A . Bandits with knapsacks [C ] // Proceedings of 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . Piscataway : IEEE Press , 2013 : 207 - 216 .

AGRAWAL S, DEVANUR N R. Linear contextual bandits with knapsacks[EB]. arXiv preprint, 2015, arXiv: 1507.06738.

LI X, SUN C, YE Y. The symmetry between arms and knapsacks: a primal-dual approach for bandits with knapsacks[EB]. arXiv preprint, 2021, arXiv: 2102.06385.

LEON V , ETESAMI S R . Bandit learning for dynamic colonel blotto game with a budget constraint [C ] // Proceedings of 2021 60th IEEE Conference on Decision and Control (CDC) . Piscataway : IEEE Press , 2021 : 3818 - 3823 .

VU D Q , LOISEAU P , SILVA A , et al . Path planning problems with side observations—when colonels play hide-and-seek [J ] . Proceedings of the AAAI Conference on Artificial Intelligence , 2020 , 34 ( 2 ): 2252 - 2259 .

CESA-BIANCHI N , LUGOSI G . Prediction, learning, and games [M ] . Cambridge : Cambridge University Press , 2006 .

Views

517

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Cerberus: a cross-site social bot detection system based on deep learning

Related Author

No data

Related Institution

No data

Postal code：100079
Tel：（010）53879206 Email：cjist@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
Total Visits：162003 Visits Today：166

⁰