0-1对策的完全混合Nash均衡的代数求解法

将求解一般0-1策略对策的完全混合Nash均衡的问题转化为求解根为正的纯小数的高次代数方程组的问题.作为一种特殊而重要的情形,利用Pascal矩阵,Newton矩阵(对角元素为Newton二项式系数的对角矩阵)和Pascal-Newton矩阵(Pascal矩阵和Newton矩阵的逆阵的乘积)将求解对称0-1对策的完全混合Nash均衡的问题转化为求解根为正的纯小数的高次代数方程的问题,并给出第二问题的反问题(由完全混合Nash均衡求解对称0-1对策族)的求解方法.同时,给出了一些算例来说明对应问题的算法.     

随机广义拟变分不等式的迭代解法及应用

为了获得Hilbert空间中一类随机广义拟变分不等式的迭代解法,证明了点到由具闭(凸)值的随机集值映射所刻画的变约束集上的投影算子的可测性.利用该可测性结果和可测选择定理,构造了求解随机广义拟变分不等式的随机迭代算法.在单调性及Lipschitz连续性条件下,获得了由算法生成的随机序列的收敛性.作为应用,给出了随机广义Nash博弈和随机Walrasian均衡问题的一些刻画性结果.     

一类多个下层的双层规划问题

本文研究了一类多个下层的双层规划问题.利用文[1]有关理论与方法,获得了该类多下层双层规划问题与一类广义纳什均衡问题的联系,然后通过寻找该广义纳什均衡问题的均衡点求解该双层规划问题.同时给出了一种求解此类广义纳什均衡问题的算法,并进行了一定的理论分析与数值计算.     

求解带有三元函数的广义半均衡问题的预测校正法

本文介绍一类新的均衡问题--带有三元函数的广义半均衡问题.借助于辅助原理法提出了求解此类问题的一个三步预测-校正迭代法,并分析了算法的收敛性.     

求解广义纳什均衡问题的增量罚算法

研究每个局中人的决策集都有可能与竞争者的决策集有关的广义纳什均衡问题.给出了该广义纳什均衡问题罚函数形式的再定式.通过分析其KKT点的特点,进一步给出了求解广义纳什均衡问题的增量罚算法.     

相对非扩张映射和均衡问题的投影迭代算法

本文利用广义f-投影,在Banach空间中,建立求解相对非扩张映射不动点集合和均衡问题解集的公共元素的迭代算法.在适当条件下,我们也得到关于相对非扩张映射和均衡问题的强收敛性定理.     

囚犯难题与二步Nash均衡

Nash均衡点是非合作对策分析中的一个重要概念,本文基于冲突分析理论中的一些概念,提出一个考虑局中人二步行为的Nash均衡概念.并使用F-H稳定性分析方法求解这扩展的Nash平衡点,最后,基于这二步Nash均衡的概念对囚犯难题进行实证分析,并利用此概念解决了"囚犯难题"的悖论.     

广义均衡问题的算法及强收敛性——基于Wiener-Hopf方程技巧

利用广义Wiener-Hopf方程技巧构造了求解广义混合均衡问题、无限个非扩张映射的不动点问题及变分不等式问题的公共元的迭代算法,并在Hilbert空间中获得了两个强收敛定理.最后利用这些新算法研究了几类优化问题.以上方法和结果不同于前人并且推广了Shi和Noor的结果.     

约束形式下广义最大元Nash均衡的存在性

运用广义最大元方法在非传递性偏好下给出了博弈均衡的存在性定理,推广了一些经典的博弈均衡存在性定理.在文中介绍策略式博弈的Nash均衡具有宽泛的条件,在微观经济理论中有广泛的应用.     

一个求解广义圆锥互补问题的无导数光滑算法

本文研究了一个求解广义圆锥互补问题的无导数光滑算法.利用光滑函数将广义圆锥互补问题等价转化成一个光滑方程组,然后再利用牛顿法求解此方程组.该算法采用了一种新的非单调无导数线搜索技术,并且在适当条件下具有全局和局部二次收敛性质.数值实验结果表明算法是非常有效的.     

求解广义纳什均衡问题的指数型惩罚函数方法

本文利用指数型惩罚函数部分地惩罚耦合约束,从而将广义纳什均衡问题(GNEP)的求解转化为求解一系列光滑的惩罚纳什均衡问题 (NEP)。我们证明了若光滑的惩罚NEP序列的解序列的聚点处EMFCQ成立,则此聚点是 GNEP的一个解。进一步,我们把惩罚 NEP的KKT条件转化为一个非光滑方程系统,然后应用带有 Armijo 线搜索的半光滑牛顿法来求解此系统。最后,数值结果表明我们的指数型惩罚函数方法是有效的。     

Restricted generalized Nash equilibria and controlled penalty algorithm

The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem, in which each player’s strategy set may depend on the rival players’ strategies. The GNEP has recently drawn much attention because of its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. However, a GNEP usually has multiple or even infinitely many solutions, and it is not a trivial matter to choose a meaningful solution from those equilibria. The purpose of this paper is two-fold. First we present an incremental penalty method for the broad class of GNEPs and show that it can find a GNE under suitable conditions. Next, we formally define the restricted GNE for the GNEPs with shared constraints and propose a controlled penalty method, which includes the incremental penalty method as a subprocedure, to compute a restricted GNE. Numerical examples are provided to illustrate the proposed approach.     

A Penalty Approach for Generalized Nash Equilibrium Problem

The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem (NEP),in which both the utility function and the strategy space of each player depend on the strategies chosen by all other players.This problem has been used to model various problems in applications.However,the convergent solution algorithms are extremely scare in the literature.In this paper,we present an incremental penalty method for the GNEP,and show that a solution of the GNEP can be found by solving a sequence of smooth NEPs.We then apply the semismooth Newton method with Armijo line search to solve latter problems and provide some results of numerical experiments to illustrate the proposed approach.     

On solving generalized Nash equilibrium problems via optimization

This paper deals with the generalized Nash equilibrium problem (GNEP), i.e. a noncooperative game in which the strategy set of each player, as well as his payoff function, depends on the strategies of all players. We consider an equivalent optimization reformulation of GNEP using a regularized Nikaido–Isoda function so that solutions of GNEP coincide with global minima of the optimization problem. We then propose a derivative-free descent type method with inexact line search to solve the equivalent optimization problem and we prove that our algorithm is globally convergent. The convergence analysis is not based on conditions guaranteeing that every stationary point of the optimization problem is a solution of GNEP. Finally, we present the performance of our algorithm on some examples.     

Partial penalization for the solution of generalized Nash equilibrium problems

In this paper we reformulate the generalized Nash equilibrium problem (GNEP) as a nonsmooth Nash equilibrium problem by means of a partial penalization of the difficult coupling constraints. We then propose a suitable method for the solution of the penalized problem and we study classes of GNEPs for which the penalty approach is guaranteed to converge to a solution. In particular, we are able to prove convergence for an interesting class of GNEPs for which convergence results were previously unknown.     

An improved two-step method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is a noncooperative game in which the strategy set of each player, as well as his payoff function, depend on the rival players strategies. As a generalization of the standard Nash equilibrium problem (NEP), the GNEP has recently drawn much attention due to its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. In this paper, we propose an improved two-step (a prediction step and a correction step) method for solving the quasi-variational inequality (QVI) formulation of the GNEP. Per iteration, we first do a projection onto the feasible set defined by the current iterate (prediction) to get a trial point; then, we perform another projection step (correction) to obtain the new iterate. Under certain assumptions, we prove the global convergence of the new algorithm. We also present some numerical results to illustrate the ability of our method, which indicate that our method outperforms the most recent projection-like methods of Zhang et al. (2010).     

THE CONVERGENCE OF APPROACH PENALTY FUNCTION METHOD FOR APPROXIMATE BILEVEL PROGRAMMING PROBLEM

' 1 IntroductionWe collsider the fOllowi11g bilevel programndng problen1:max f(x, y),(BP) s.t.x E X = {z E RnIAx = b,x 2 0}, (1)y e Y(x).whereY(x) = {argmaxdTyIDx Gy 5 g, y 2 0}, (2)and b E R", d, y E Rr, g E Rs, A, D.and G are m x n1 s x n aild 8 x r matrices respectively. If itis not very difficult to eva1uate f(and/or Vf) at all iteration points, there are many algorithmeavailable fOr solving problem (BP) (see [1,2,3etc1). However, in some problems (see [4]), f(x, y)is too com…     

A half-space projection method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is an n-person noncooperative game in which each player’s strategy set depends on the rivals’ strategy set. In this paper, we presented a half-space projection method for solving the quasi-variational inequality problem which is a formulation of the GNEP. The difference from the known projection methods is due to the next iterate point in this method is obtained by directly projecting a point onto a half-space. Thus, our next iterate point can be represented explicitly. The global convergence is proved under the minimal assumptions. Compared with the known methods, this method can reduce one projection of a vector onto the strategy set per iteration. Numerical results show that this method not only outperforms the known method but is also less dependent on the initial value than the known method.     

Generalization of the weighted voting method using penalty functions constructed via faithful restricted dissimilarity functions

In this paper we present a generalization of the weighted voting method used in the exploitation phase of decision making problems represented by preference relations. For each row of the preference relation we take the aggregation function (from a given set) that provides the value which is the least dissimilar with all the elements in that row. Such a value is obtained by means of the selected penalty function. The relation between the concepts of penalty function and dissimilarity has prompted us to study a construction method for penalty functions from the well-known restricted dissimilarity functions. The development of this method has led us to consider under which conditions restricted dissimilarity functions are faithful. We present a characterization theorem of such functions using automorphisms. Finally, we also consider under which conditions we can build penalty functions from Kolmogoroff and Nagumo aggregation functions. In this setting, we propose a new generalization of the weighted voting method in terms of one single variable functions. We conclude with a real, illustrative medical case, conclusions and future research lines.     

Gap Function Approach to the Generalized Nash Equilibrium Problem

We consider an optimization reformulation approach for the generalized Nash equilibrium problem (GNEP) that uses the regularized gap function of a quasi-variational inequality (QVI). The regularized gap function for QVI is in general not differentiable, but only directionally differentiable. Moreover, a simple condition has yet to be established, under which any stationary point of the regularized gap function solves the QVI. We tackle these issues for the GNEP in which the shared constraints are given by linear equalities, while the individual constraints are given by convex inequalities. First, we formulate the minimization problem involving the regularized gap function and show the equivalence to GNEP. Next, we establish the differentiability of the regularized gap function and show that any stationary point of the minimization problem solves the original GNEP under some suitable assumptions. Then, by using a barrier technique, we propose an algorithm that sequentially solves minimization problems obtained from GNEPs with the shared equality constraints only. Further, we discuss the case of shared inequality constraints and present an algorithm that utilizes the transformation of the inequality constraints to equality constraints by means of slack variables. We present some results of numerical experiments to illustrate the proposed approach.