Finding Equilibrium in Some Economics and Game Models
研究了用投影法求解三类经济与博弈模型中的均衡问题，发现额外伪梯度法在迭代次数上优于伪梯度投影法，且复杂度随问题规模线性增长。
Abstract We consider numerical aspects of finding classical J. Nash’s equilibrium in concave n -persons game, nonlinear equilibrium (NE), as an alternative to primal and dual linear programming (LP) problems, and recently introduced nonlinear production-consumption equilibrium (NPCE). The problems are particular cases of a general nonlinear equilibrium problem, which is equivalent to a variational inequality (VI). The corresponding VIs have simple feasible sets, that the projection on them is a low cost operation. Therefore, we apply two projection methods for finding the equilibrium: pseudo-gradient projection (PGP) and extra pseudo-gradient (EPG). We present and analyze results obtained on random generated sets of these three classes of problems. The obtained results show expected advantages of the EPG over PGP. What is most important: the number of iterations requited by EPG method to find an approximation for the equilibrium with a given accuracy grows linearly with the number of products in case of NE and NPCE, or with the number of active strategies in case of J. Nash’s equilibrium. The number of operations, or solution time grows as a cube of the corresponding parameters. These results corroborate the complexity bounds established in [18–20] under reasonable assumptions on the input data.