We consider generalized Nash equilibrium problems (GNEPs) with non-convex strategy spaces and non-convex cost functions. This general class of games includes the important case of games with mixed-integer variables for which only a few results are known in the literature. We present a new approach to characterize equilibria via a convexification technique using the Nikaido-Isoda function. To any given instance of the GNEP, we construct a set of convexified instances and show that a feasible strategy profile is an equilibrium for the original instance if and only if it is an equilibrium for any convexified instance and the convexified cost functions coincide with the initial ones. We further develop this approach along three dimensions. We first show that for quasi-linear models, where a convexified instance exists in which for fixed strategies of the opponent players, the cost function of every player is linear and the respective strategy space is polyhedral, the convexification reduces the GNEP to a standard (non-linear) optimization problem. Secondly, we derive two complete characterizations of those GNEPs for which the convexification leads to a jointly constrained or a jointly convex GNEP, respectively. These characterizations require new concepts related to the interplay of the convex hull operator applied to restricted subsets of feasible strategies and may be interesting on their own. Finally, we demonstrate the applicability of our results by presenting a numerical study regarding the computation of equilibria for a class of integral network flow GNEPs.
翻译:我们考虑的是普通的纳什平衡问题(GNEPs),它具有非convex战略空间和非convex成本功能。这种一般游戏类别包括使用混合整数变量的游戏的重要案例,文献中只知道这些变量的少数结果。我们提出一种新的方法,使用Nikaido-Isoda功能,通过调和技术来描述平衡。对于任何特定的GNEP实例,我们建造了一套融合实例,并表明可行的战略剖面图是原始实例的平衡,如果并且只有它是一个任何融合实例的平衡,而且混和的成本功能与初始的相同。我们进一步从三个方面发展了这一方法。我们首先展示了准线性模型,在这种模型中,对对手的固定策略来说,每个玩家的成本功能是线性,而各自的战略空间是多面的,而混凝固化将GENEP降低为标准的(非线性)优化问题。第二,我们从对GNEP的深度流进行两次完整的电子剖析,对最终的GNEP的计算结果进行我们分别对GNEP的精确的精确的计算,对GNEP的精度进行共同的精度进行精确的计算。