求解Nash均衡子问题的一个算法

n人有限博弈的混合策略组合（p1^*，…，pn^*)为Nash均衡，如果其中每一策略pi^*都是参与人i(i=1,2,…，n)，对其它n-1个参与人策略组合（p1^*,…,pi 1^*,pi-1^*,…,pn^*)的最优反应，即存在n个概率向量p1^*,…,pn^*使得对i=1,2,…,n及任意k1维概率向量pi恒有vi(p1^*,…,pn^*…)小于vi(pi^*,…,pi-1^*,pi 1^*，…pn^*)，其中vi为参与人i的支付函数，pi=(pil,…,piki)）为ki维概率向量，即满足条件，pij大于等于0，∑kij=1pij=1,ki是参与人i的策略空间中策略个数，i=1,2,…,n，由此，Nash均衡的求解可化为下列优化问题：求n个概率向量pi^*,…,pn^8，使得对i=1,2,…,n及任意ki维的概率向量pi满足maxxvi(P1^*,…,pi-1^*,pi,Pi 1^*,…,pn^*)=vi(P1^*,，…，Pn^*)。

AN ALGORITHM FOR SOLVING SUBPROBLEMS OF NASH EQUILIBRIUM

in this paper we propose an iterative algorithm for solving a nonlinear program with one equality constraint and bounded variables occurred subproblems of Nash equilibrium and prove it's convergence. At each iteration, a separable convex quadratic program with the same constraint set is solved, preliminary test suggests that this approach is efficient for problem with one linear constraint and bounded variables.