Piecewise affine parameterized value-function based bilevel non-cooperative games

• 成果类型: Article
• 署名作者: Hao, Tianyu; Pang, Jong-Shi
• 署名单位: University of Southern California
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1344-7
• 发表日期: 2020
• 页码: 33-73
• 关键词: equilibria

摘要

Generalizing certain network interdiction games communicated to us by Andrew Liu and his collaborators, this paper studies a bilevel, non-cooperative game wherein the objective function of each player's optimization problem contains a value function of a second-level linear program parameterized by the first-level variables in a non-convex manner. In the applied network interdiction games, this parameterization is through a piecewise linear function that upper bounds the second-level decision variable. In order to give a unified treatment to the overall two-level game where the second-level problems may be minimization or maximization, we formulate it as a one-level game of a particular kind. Namely, each player's objective function is the sum of a first-level objective function +/- a value function of a second-level maximization problem whose objective function involves a difference-of-convex (dc), specifically piecewise affine, parameterization by the first-level variables. This non-convex parameterization is a major difference from the family of games with min-max objectives discussed in Facchinei et al. (Comput Optim Appl 59(1):85-112, 2014) wherein the convexity of the overall games is preserved. In contrast, the piecewise affine (dc) parameterization of the second-level objective functions to be maximized renders the players' combined first-level objective functions non-convex and non-differentiable. We investigate the existence of a first-order stationary solution of such a game, which we call a quasi-Nash equilibrium, and study the computation of such a solution in the linear-quadratic case by Lemke's method using a linear complementarity formulation.