一种求解合作博弈最公平核心的非精确平行分裂算法

doi:10.15960/j.cnki.issn.1007-6093.2016.02.010

运筹学学报

一种求解合作博弈最公平核心的非精确平行分裂算法

王斯琪^1,*谢政¹ 戴丽¹

1. 国防科学技术大学理学院数学与系统科学系, 长沙 410073

收稿日期:2015-11-02 出版日期:2016-06-15 发布日期:2016-06-15
通讯作者: 王斯琪 wangsq92@163.com

A kind of inexact parallel splitting method for solving the fairest core in cooperative game

WANG Siqi^1,*XIE Zheng¹DAI Li¹

1. Department of Mathematics and System Science, College of Science, National University of Defense Technology, Changsha 410073, China

Received:2015-11-02 Online:2016-06-15 Published:2016-06-15

摘要/Abstract

摘要：

针对合作博弈核心和Shapley值的特点, 将最公平核心问题转化为带有两个变量的可分离凸优化问题, 引入结构变分不等式的算子分裂方法框架, 提出了求解最公平核心的一种非精确平行分裂算法. 而且, 该算法充分利用了所求解问题的可行域的简单闭凸性, 子问题的非精确求解是容易的. 最后, 简单算例的数值实验表明了算法的收敛性和有效性.

关键词: 合作博弈, 最公平核心, 变分不等式, 非精确平行分裂算法

Abstract:

In this paper, considering the characteristics of the core and the Shapley value in cooperative game, we transform the fairest core problem into a separable convex optimization problem with two variable. A kind of inexact parallel splitting method is proposed for solving the fairest core by introducing the operator splitting method framework of structured variational inequalities. Furthermore, the proposed method makes full use of the simple closed convexity of the feasible region in the solved problem, and all sub-problems are easy to be solved inexactly. Finally, some numerical results of a simple example indicate the convergence and validity of this method.

Key words: cooperative game, fairest core, variational inequality, inexact parallel splitting method

王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2016.02.010.

WANG Siqi, XIE Zheng, DAI Li. A kind of inexact parallel splitting method for solving the fairest core in cooperative game[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.02.010.

参考文献

[1] 谢政. 对策论导论 [M]. 北京: 科学出版社, 2010.

[2] Peleg B, Sudh\"{o}lter P. Introduction to the Theory of Cooperative Games [M]. Berlin: Springer, 2007.

[3] Nguyen T D. The fairest core in cooperative games with transferable utilities [J]. Operations Research Letters, 2015, 43(1): 34-39.

[4] Lemke C E. Bimatrix equilibrium points and mathematical programming [J]. Management Science, 1965, 11: 681-689.

[5] Monteiro D C, Adler I. Interior path following primal-dual algorithms. Part II: Convex quadratic programming [J]. Mathematical Programming, 1989, 44(1): 43-66.

[6] Fletcher R. A general quadratic programming algorithm [J]. Journal of the Institute of Mathematics and its Applications, 1971, 7: 76-91.

[7] He B S. A projection and contraction method for a class of linear complementarity problem and its application in convex quadratic programming [J]. Applied Mathematics and Optimization, 1992, 25(3): 247-262.

[8] He B S, Yuan X M, Zhang W X. A customized proximal point algorithm for convex minimization with linear constraints [J]. Computation Optimization and Applications, 2013, 56(3): 559-572.

[9] Ye C H, Yuan X M. A descent method for structured monotone variational inequalities [J]. Optimization Methods and Software, 2007, 22(2): 329-338.

[10] He B S. Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities [J]. Computation Optimization and Applications, 2009, 42(2): 195-212.

[11] Tao M, Yuan X M. An inexact parallel splitting augmented Lagrangian method for monotone variational inequalities with separable structures [J]. Computation Optimization and Applications, 2012, 52(2): 439-461.

[12] 杨赟, 彭拯. 可分离凸优化问题的非精确平行分裂算法 [J]. 运筹学学报, 2014, 18(3): 33-46.

一种求解合作博弈最公平核心的非精确平行分裂算法

A kind of inexact parallel splitting method for solving the fairest core in cooperative game

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价

[1]	黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114.
[2]	肖燕, 李登峰. 带策略约束的区间数双矩阵博弈的双线性规划求解方法[J]. 运筹学学报, 2019, 23(4): 59-70.
[3]	于晓辉, 杜志平, 张强, 周珍, 逄金辉. 一种资源投入不确定情形下的合作博弈形式及收益分配策略[J]. 运筹学学报, 2019, 23(4): 71-85.
[4]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[5]	冯俊锴, 张海斌, 秦嫒, 张凯丽. 解一类结构变分不等式问题的非精确并行交替方向法[J]. 运筹学学报, 2018, 22(2): 18-30.
[6]	何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31.
[7]	何炳生. 修正乘子交替方向法求解三个可分离算子的凸优化[J]. 运筹学学报, 2015, 19(3): 57-70.
[8]	杨赟, 彭拯. 可分离凸优化问题的非精确平行分裂算法[J]. 运筹学学报, 2014, 18(3): 33-46.
[9]	黄正海, 林贵华, 修乃华. 变分不等式与互补问题、双层规划与平衡约束数学规划问题的若干进展[J]. 运筹学学报, 2014, 18(1): 113-133.
[10]	邓喜才，向淑文，左羽. 不确定性下强Berge均衡的存在性[J]. 运筹学学报, 2013, 17(3): 101-107.