English

运筹学学报 >

2016 , Vol. 20 >Issue 2: 105 - 112

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.02.010

运筹学

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

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

收稿日期: 2015-11-02

  网络出版日期: 2016-06-15

收起

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

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

Received date: 2015-11-02

  Online published: 2016-06-15

Fold

摘要

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

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

本文引用格式

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

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

参考文献

[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.
Options
文章导航

/

〈 〉