1 Introduction↩︎

The multi-leader–follower game (MLFG) is a hierarchical noncooperative model that extends the classical Stackelberg game. In this framework, multiple leaders first take into account the response of (possibly multiple) followers, who subsequently engage in a Nash equilibrium problem among themselves. Such a game was introduced in Heinrich F. von Stackelberg’s seminal work in 1934, prior to Nash’s equilibrium theory of noncooperative games in 1950 [1].

In recent decades, the MLFG has gained significant attention across various fields due to its ability to model hierarchical decision-making in decentralized systems. Some applications include strategic bidding in electricity markets [2]–[4], resource management in cloud and edge computing [5]–[9], and market design [10], [11], Kumar2022?. For instance, in electricity markets studied by Leyffer and Munson [4] and Pang and Fukushima [12], generators (leaders) set prices strategically before the market clears, while other market participants (followers) respond by adjusting their demand and supply accordingly. For surveys of the MLFG, see Hu and Fukushima [13] and Aussel and Svensson [14].

Despite their applicability, solving MLFGs remains challenging. In fact, MLFGs are more complex than standard bilevel optimization because they necessitate finding a Nash equilibrium at the upper level, where each leader’s strategy is constrained by the equilibrium of the lower-level game. Historically, two main approaches have been considered in the MLFG literature.

One approach is to solve the MLFG by reformulating it into an equilibrium problem with equilibrium constraints (EPEC). By replacing the followers’ Nash equilibrium problems with Karush–Kuhn–Tucker (KKT) conditions, each leader’s problem is transformed into a mathematical problem with equilibrium constraints (MPEC). Leyffer and Munson [4] proposed an MPEC-based method by considering a first-order necessary condition of all leaders’ MPECs, leading to systems of complementarity conditions. Then, they are solved with algorithms given by Su [15]. Later, Hori and Fukushima [16] proposed a diagonal method for the resultant EPEC using a penalty method adapted to MLFGs and utilizing a sequential penalty method developed by Huang et al. [17].

Another approach introduces a response function of followers’ game, assuming the uniqueness of the Nash equilibrium. By plugging the unique response (e.g., denoted by \(y(x)\), where \(x\) is a tuple of leaders’ strategies) into each leader’s problem, the MLFG is reduced to an ordinary single-level Nash equilibrium problem. However, because the response function \(y(x)\) is generally nonsmooth, smoothing schemes are required. Hu and Fukushima [18] first proposed a response-based method where a single follower solves an equality-constrained quadratic optimization problem with an analytical response. Herty et al. [19] extended this framework to followers with linear inequality constraints and proposed a smoothing scheme to obtain an approximate leader–follower Nash equilibrium with gradient-based methods. These studies assumed that the followers’ response \(y(x)\) is analytically obtained. In contrast to these approaches, Hori et al. [20] proposed a general framework that does not assume specific structures for players’ objective functions and constraints.

Despite those developments, existing studies have some drawbacks. For the EPEC-based method, reformulating the followers’ game as a KKT system requires first-order derivatives. As a consequence, solving the resulting EPEC often requires higher-order derivatives of the followers’ functions. Moreover, when the lower-level problem is not convex, MPEC and EPEC reformulations are usually not equivalent to the original problem; see [21], [22]. As for response-based approaches, they often assume the uniqueness of the followers’ response, which is practically the same as assuming strong convexity or monotonicity in the followers’ noncooperative game.

In this paper, motivated by those limitations, we propose a new reformulation of the MLFG by utilizing the Nikaido–Isoda function for the followers’ game. Our approach neither needs any derivative information nor assumes strong convexity in the followers’ problems. We reformulate the MLFG into a differentiable single-level Nash equilibrium problem with penalty terms, and then analyze the relationship between the resultant Nash game and the original MLFG. In fact, similar approaches have recently attracted the attention of researchers in bilevel optimization, where several algorithms [23]–[26] have been proposed, which support our approach.

Our contributions are summarized as follows:

• We propose a differentiable single-level reformulation of the MLFG, which does not use any derivative information with respect to each follower’s problem, by using the regularized Nikaido–Isoda function.

• We establish the relationship between the leader–follower equilibrium of the original MLFG and Nash equilibrium of the resultant single-level Nash equilibrium problem (Theorem 2);

• We also establish the relationship between the variational equilibria, which means the stationarity condition, of the original MLFG and the single-level Nash equilibrium problem (Theorem 4).

This paper is organized as follows: Section 2 introduces mathematical notions and Nash equilibrium problems to provide fundamental tools for analysis. Section 3 proposes a new level-reduction technique for the MLFG with regularized Nikaido–Isoda function and approximates it by a certain penalized problem. Section 4 analyzes the relationship between the penalized problem and the original MLFG. Section 5 concludes this paper.

Throughout this work, we use the following notations: Given \(m\) vectors \(x^1,\dots,x^m\), where \(x^i\in\mathbb{R}^{n_i}\) for \(i=1,\dots,m\), the concatenated vector \(x\coloneq ((x^1)^\top,\dots,(x^m)^\top)^\top\) with \(^\top\) being the transpose, is simply written as \(x=(x^1,\dots,x^m)\). To emphasize the \(i\)th subvector \(x^i\in\mathbb{R}^{n_i}\), \(x\) is sometimes denoted as \(x=(x^i,x^{-i})\), where \(x^{-i}\coloneq (x^1,\dots,x^{i-1},x^{i+1},\dots,x^m)\) represents the tuple of all subvectors except \(x^i\). For the real-valued function \(f\colon\mathbb{R}^{n+m}\to\mathbb{R}\), \(\nabla_y f(x,y)\) denotes the partial gradient of \(f\) with respect to the second variable \(y\). For the vector-valued function \(F\colon\mathbb{R}^n\to\mathbb{R}^m\), the transposed Jacobi matrix \(\mathcal{J}F(x)^\top\) is denoted by \(\nabla F(x)\in\mathbb{R}^{n\times m}\); we simply call it the Jacobian or Jacobi matrix of \(F\). Similarly, for \(F\colon\mathbb{R}^{n+m}\to\mathbb{R}^l\), the partial (transposed) Jacobi matrix with respect to \(x\) is denoted by \(\nabla_x F(x,y)\). Also, the Euclidean norm and inner product are written as \(\|\cdot\|\) and \(\langle \cdot,\cdot \rangle\), respectively. We denote by \(\mathbb{B}\) the open unit ball centered at 0, and let \(\mathbb{B}(x,\varepsilon)\coloneq\{y\in\mathbb{R}^n\mid \|y-x\|<\varepsilon\} =x+\varepsilon\mathbb{B}\) for a vector \(x\in\mathbb{R}^n\) and positive real number \(\varepsilon>0\). Let \(\bar{\mathbb{B}}\) and \(\bar{\mathbb{B}}(x,\varepsilon)\) be the closure of the open balls, i.e., the closed balls. We denote the normal cone to a convex set \(\Sigma \subset \mathbb{R}^n\) at \(x\in\Sigma\) as \(\mathcal{N}_{\Sigma}(x) \coloneq \{s\in\mathbb{R}^n \mid \langle s, y-x \rangle \le 0\; \forall y \in \Sigma\}\). The Euclidean distance from \(x\in\mathbb{R}^n\) to \(S\subset\mathbb{R}^n\) is denoted by \(\mathrm{dist}(x,S)\).

2 Preliminaries↩︎

In this section, we provide some concepts regarding convex analysis and recall the (generalized) Nash equilibrium problem.

2.1 Notations and fundamental properties↩︎

The graphs \(\mathrm{gph}\ f\) and \(\mathrm{gph}\ T\) of the real-valued function \(f\colon\mathbb{R}^n\to\mathbb{R}\) and set-valued mapping \(T\colon\mathbb{R}^n\rightrightarrows\mathbb{R}^m\) are defined as follows: \[\mathrm{gph}\ f\coloneq\{(x,\lambda)\in\mathbb{R}^n\times\mathbb{R}\mid \lambda=f(x)\},\] and \[\mathrm{gph}\ T\coloneq\{(x,\lambda)\in\mathbb{R}^n\times\mathbb{R}^m\mid \lambda\in T(x)\},\] respectively. The function \(f\) is \(L\)-smooth if there exists \(L>0\) such that \[\|\nabla f(x)-\nabla f(x')\|\le L\|x-x'\|\quad\forall x,x'\in \mathbb{R}^n,\] and \(f\) is said to be \(\mu\)-weakly convex with \(\mu > 0\) if \(f+\mu/2\|\cdot\|^2\) is convex.

The following lemmas are well-known results in nonlinear optimization; we omit those proofs.

Next, we introduce the subanalyticity along with other relevant concepts.

Loosely speaking, a (globally) subanalytic function is a function described as a combination of locally analytic functions. Subanalyticity may be generally satisfied by many widely-used objective functions [27]. They exhibit a “tame” geometry, thus stability under basic operations, and desirable properties for optimization [23]. One of them is the Hölderian error bound defined later.

If the HEB condition holds for a function, it measures the distance in a certain sense between the solution set to the optimization problem by the gap of objective function values.

The following lemma ensures that if a solution set and objective function are globally subanalytic, the objective function satisfies the HEB for some \((\xi,\eta)\).

2.2 Nash equilibrium problem↩︎

Consider an \(N\)-person noncooperative game [1]. Player labeled with \(\nu\in\{1,\dots,N\}\) solves \[\begin{align} \label{prob:player} \min_{x^\nu\in\mathbb{R}^{n_\nu}}\quad \theta^\nu(x^\nu,x^{-\nu})\qquad \text{s.t}\quad x^\nu\in X^\nu, \end{align}\tag{1}\] where \(x^\nu\in\mathbb{R}^{n_\nu}\) denotes a strategy for player \(\nu\), and \(\theta^\nu\colon\mathbb{R}^n\to\mathbb{R}\) and \(X^\nu\subset\mathbb{R}^{n_\nu}\) denote their cost function and strategy space, respectively. Here, \(n\coloneq n_1+\dots+n_N\).

The NE means that nobody can reduce their cost function by only changing their strategy unilaterally. We refer to the problem to find the NE of the noncooperative game as a Nash equilibrium problem (NEP). The following proposition ensures the existence of NE for the NEP. For a proof, we refer the reader to the literature, e.g., Aubin [31].

Now we introduce the Nikaido–Isoda (NI) function (sometimes called the Ky-Fan function) for the NEP as follows: \[\Psi(x,z) \coloneq \sum_{\nu=1}^N \left[\theta^\nu(x^\nu,x^{-\nu})-\theta^\nu(z^\nu,x^{-\nu})\right],\] We also introduce the value-function or gap function for the NEP defined by \[V(x) \coloneq \sup_{z\in X} \Psi(x,z).\] It is easy to see that \(x^*\in X\) is an NE if and only if \(V(x^*)=0\).

Next, we introduce the regularized NI function for the NEP as follows: \[\Psi_\mu(x,z) \coloneq \sum_{\nu=1}^N [ \theta^\nu(x^\nu,x^{-\nu})-\theta^\nu(z^\nu,x^{-\nu}) ] -\frac{1}{2\mu}\|x-z\|^2,\] where \(\mu>0\) is referred to as a regularization parameter, and its value-function is \(V_\mu(x) \coloneq \sup_{z\in X}\Psi_\mu(x,z)\); we refer to \(V_\mu\) as a regularized value-function. The regularized value-function is often used in NEPs and their generalization [32]–[34] which are introduced later. In fact, those ideas are based on the Moreau–Yosida regularization or Moreau envelope of \(\theta^\nu\). When \(\theta^\nu(\cdot,x^{-\nu})\) is convex for each \(\nu\), \(V_{\mu}\) is differentiable, whereas \(V\) is not in general.

If each player’s problem is convex, \(x^*\in X\) is an NE if and only if \(V_\mu(x^*)=0\). Otherwise, this equivalency is not true as illustrated in the following example.

The generalized Nash equilibrium problem (GNEP) extends the NEP by allowing each player’s strategy set to depend on the other players’ strategies. More precisely, the constraint of each player \(\nu\) in the GNEP is represented as \(x^\nu \in X^\nu(x^{-\nu})\). Such constraints are called coupling constraints. In this paper, we consider a particular class of GNEP with \(K\subset\mathbb{R}^n\), where each player solves \[\begin{align} \label{prob:player46GNEP} \min_{x^\nu\in\mathbb{R}^{n_\nu}}\quad \theta^\nu(x^\nu,x^{-\nu}) \qquad \text{s.t.} \quad (x^\nu,x^{-\nu})\in K. \end{align}\tag{2}\] In this GNEP, \(X^\nu(x^{-\nu})=\{x^\nu\in\mathbb{R}^{n_\nu}\mid (x^\nu,x^{-\nu})\in K\}\) for each \(\nu\), which means that all the players share the same coupling constraint.

3 Level-reduction technique for MLFGs and its penalty minimization with regularized Nikaido–Isoda functions↩︎

In this section, we begin by formally formulating the MLFG considered in this paper. Subsequently, we reformulate the MLFG as a GNEP and propose a penalty minimization approach using the regularized NI function to solve the obtained GNEP.

3.1 Problem formulation↩︎

In this paper, we consider the MLFG comprising \(N\) leaders and \(M\) followers. In this MLFG, NEPs are induced on both the leaders’ side and the followers’ side. We denote a leader \(\nu\)’s strategy and a tuple of their rivals’ strategies by \(x^{\nu}\in \mathbb{R}^{n_{\nu}}\) and \(x^{-\nu}\in \mathbb{R}^{n-n_{\nu}}\) with \(n \coloneq n_1+\dots+n_N\), respectively. We also denote a follower \(\omega\)’s strategy and a tuple of their rivals’ strategies by \(y^{\omega}\in \mathbb{R}^{m_{\omega}}\) and \(y^{-\omega}\in \mathbb{R}^{m-m_{\omega}}\) with \(m \coloneq m_1+\dots+m_M\), respectively. Each leader indexed by \(\nu\in\{1,\dots,N\}\) solves the following problem: \[\begin{align} \label{prob:leader} \min_{x^\nu\in\mathbb{R}^{n_\nu}}\quad \theta^\nu(x^\nu,x^{-\nu},y)\qquad \text{s.t.}\quad x^\nu\in X^\nu, \end{align}\tag{3}\] where \(\theta^\nu\colon\mathbb{R}^{n+m}\to\mathbb{R}\). On the other hand, each follower indexed by \(\omega\in\{1,\dots,M\}\) solves \[\begin{align} \label{prob:follower} \min_{y^\omega\in\mathbb{R}^{m_\omega}} \quad \gamma^\omega(x,y^\omega,y^{-\omega}) \qquad \text{s.t.}\quad y^\omega\in Y^\omega, \end{align}\tag{4}\] where \(\gamma^{\omega}\colon\mathbb{R}^{n+m}\to\mathbb{R}\). Hereinafter, let \[X \coloneq X^1\times X^2 \times \cdots\times X^N\subset \mathbb{R}^n,\; Y \coloneq Y^1\times Y^2\times \cdots \times Y^M\subset \mathbb{R}^m.\]

3.2 Existing level-reduction approaches↩︎

In this subsection, suppose that \(Y^\omega\) is given by \[Y^\omega = \{y^\omega\in\mathbb{R}^{m_\omega}\mid g^\omega(y^\omega)\le 0\} \footnote{Although we can also consider equality constraints, we omit them for simplicity.},\] where \(g^\omega\colon\mathbb{R}^{m_\omega}\to\mathbb{R}^{p_\omega}\). Moreover, assume that each follower’s problem is convex, i.e., 4 is convex for arbitrary fixed \(x\) and \(y^{-\omega}\), and suitable constraint qualifications hold. The Nash game is equivalently reformulated as the following KKT systems: \[\begin{align} \label{KKT46system} \begin{cases} \nabla_{y^\omega} \gamma^\omega(x,y^\omega,y^{-\omega}) + \nabla_{y^\omega} g^\omega(y^\omega)\lambda^\omega = 0,\\ 0\le\lambda^\omega \perp g^\omega(y^\omega)\le 0 \end{cases} \quad\forall \omega\in \{1,\dots,M\}, \end{align}\tag{5}\] where \(\lambda^\omega\in\mathbb{R}^{p_\omega}\) is the Lagrange multiplier for the inequality constraint \(g^\omega(y^\omega)\le 0\), and \(\lambda^\omega\perp g^\omega(y^\omega)\) means that \(\langle \lambda^\omega,g^\omega(y^\omega)\rangle=0\).

Incorporating 5 into the constraint of each leader’s problem 3 , we have the following mathematical problem with equilibrium constraints (MPEC): Leader \(\nu\) solves \[\begin{align} \label{prob:MPEC} \min_{x^\nu,y,\lambda} \theta^\nu(x^\nu,x^{-\nu},y) \qquad \text{s.t. } x^\nu\in X^\nu,~\eqref{KKT46system}. \end{align}\tag{6}\] The NEP in which leader \(\nu\) solves 6 is referred to as an equilibrium problem with equilibrium constraints (EPEC).

A typical approach to address the EPEC associated with the MLFG is based on methods for MPECs [4], [16], [35]. Those methods are gradient-based, which, in turn, require Hessians \(\nabla^2_y \gamma^\omega\) and \(\nabla^2_{y^\omega}g^\omega\) or higher-order derivatives.

Specifically, if the followers’ best response is unique for every \(x\in X\), there exists a mapping of the response \(y\colon x \mapsto y(x)\). Then, plugging \(y(x)\) into each leader’s problem, the MLFG is reduced to an ordinary NEP as follows: Leader \(\nu\) solves \[\begin{align} \label{prob:response} \min_{x^\nu\in X^\nu} \quad& \theta^\nu(x^\nu,x^{-\nu},y(x^\nu,x^{-\nu})). \end{align}\tag{7}\] Since \(y(x)\) is not necessarily smooth, Hori et al. [20] proposed a smoothing scheme. To obtain a smooth approximated response, they utilized a smoothing approximation of a nonlinear equation induced from the KKT systems 5 , in which the complementarity conditions are replaced by the smoothing Fischer–Burmeister functions [36]. Then, the reduced problem 7 is approximated by the following (differentiable) problem: \[\begin{align} \label{prob:response46approx} \min_{x^\nu\in X^\nu} \quad& \theta^\nu(x^\nu,x^{-\nu},y_\varepsilon(x^\nu,x^{-\nu})), \end{align}\tag{8}\] where \(y_\varepsilon(x)\) is the \(y\)-part of a solution to the smoothed approximated nonlinear equations for 5 , and \(\varepsilon>0\) is a smoothing parameter. When applying first-order methods to 8 , one needs to compute \(\nabla y_\varepsilon (x)\), which involves computing \(\nabla^2_{y} \gamma^\omega\) and \(\nabla^2_{y^\omega} g^\omega\) via the implicit function theorem; see the appendix for details. However, this can be computationally demanding in large-scale settings.

Consequently, both EPEC and the best response approaches require computing the Hessians of the followers’ defining functions \(\gamma^\omega\) and \(g^\omega\). This motivates us to develop an alternative reformulation for the MLFG.

3.3 Level-reduction of the MLFG into a single-level GNEP↩︎

Using the Nikaido–Isoda function, the set of NE for the followers’ NEP is represented by \[S(x) \coloneq \{y\in Y\mid h(x,y) \coloneq \sup_{z\in Y} \Psi(x,y,z)\le 0\},\] where \[\Psi(x,y,z) \coloneq \sum_{\omega=1}^M [\gamma^\omega(x,y^\omega,y^{-\omega})- \gamma^\omega(x,z^\omega,y^{-\omega})].\] We refer to the function \(h\) as a value-function for the followers’ NEP. By letting \[\phi^\omega(x,y^{-\omega}) \coloneq \min_{z^\omega\in Y^\omega} \gamma^\omega(x,z^\omega,y^{-\omega}),\] we have \[h(x,y)=\sum_{\omega=1}^M [\gamma^\omega(x,y^\omega,y^{-\omega}) -\phi^\omega(x,y^{-\omega})].\]

Incorporating the condition \(y\in S(x)\) into each leader’s problem reduces the MLFG to the following single-level GNEP with shared coupling constraints: \[\begin{align} \label{prob:reduced46before} \min_{x^\nu,\hat{y}^\nu} \quad \theta^\nu(x^\nu,x^{-\nu},{\hat{y}}^\nu) \qquad \text{s.t.} \quad x^\nu\in X^\nu,\;\hat{y}^\nu\in S(x^\nu,x^{-\nu}). \end{align}\tag{9}\] Note that \(y^{\omega}\in \mathbb{R}^{m_{\omega}}\) denotes the follower \(\omega\)’s strategy, whereas \(\hat{y}^{\nu}\in \mathbb{R}^m\) denotes a tuple of all the followers’ strategies observed by leader \(\nu\). Let \[\begin{align} \hat{y} \coloneq (\hat{y}^1,\dots,\hat{y}^N)\in\mathbb{R}^{Nm},\;w^\nu \coloneq (x^\nu,\hat{y}^\nu)\in\mathbb{R}^{n_\nu+m}, \end{align}\] and \[W^\nu_0(x^{-\nu}) \coloneq \{w^\nu\in\mathbb{R}^{n_\nu+m}\mid x^\nu\in X^\nu, \hat{y}^\nu\in S(x^\nu,x^{-\nu})\}.\] With these notations, 9 is simply rewritten as \[\begin{align} \label{prob:reduced} \min_{w^\nu\in\mathbb{R}^{n_\nu+m}} \quad \theta^\nu(w^\nu,x^{-\nu})\qquad \text{s.t.}\quad w^\nu\in W^\nu_0(x^{-\nu}). \end{align}\tag{10}\]

The reduced noncooperative game in which each leader \(\nu\) solves 10 is denoted as \(\mathrm{GNEP}(\{(W^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\). Now, we introduce an equilibrium concept for the MLFG via \(\mathrm{GNEP}(\{(W^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\) as follows:

Note that the term leader–follower NE is used because the GNE of the problem \(\mathrm{GNEP}(\{(W^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\) is a solution of the MLFG, and vice versa. The definition originates from an ‘optimistic’ LFNE introduced by Hu and Fukushima [13].

Note further that the above reformulation does not require any derivative information on followers’ functions, whereas the existing level-reduction approaches require it as explained in the previous subsection.

3.4 Differentiable penalty minimization problem↩︎

In this section, we introduce a new penalized problem for solving 10 . To this end, we first define a ‘regularized’ Nikaido–Isoda function for the followers’ NE as follows: \[\Psi_\mu(x,y,z) \coloneq \sum_{\omega=1}^M \{\gamma^\omega(x,y^\omega,y^{-\omega})-\gamma^\omega(x,z^\omega,y^{-\omega})\}- \frac{1}{2\mu}\|y-z\|^2.\] Accordingly, the ‘regularized’ value-function for the followers’ NEP is defined as \[h_\mu(x,y) \coloneq \max_{z\in Y} \Psi_\mu(x,y,z).\] Letting \[\phi^\omega_\mu(x,y^\omega,y^{-\omega}) \coloneq \min_{z^\omega\in Y^\omega}\gamma^\omega(x,z^\omega,y^{-\omega})+ \frac{1}{2\mu}\|y^\omega-z^\omega\|^2,\] it holds that \[h_\mu(x,y)=\sum_{\omega=1}^M \gamma^\omega(x,y^\omega,y^{-\omega})- \phi^\omega_\mu(x,y^\omega,y^{-\omega}). \label{eq:hmu}\tag{11}\]

Next, we make the following assumptions on the MLFG. Notice that convexity is assumed for neither the leaders’ functions \(\theta^{\nu}\) nor the followers’ functions \(\gamma^{\omega}\).

Under these conditions, we can ensure the functions \(\theta^{\nu},\gamma^{\omega}\), and \(\phi^{\omega}_{\mu}\) are tractable in the following sense:

In the literature, \(h_\mu(x,y)\) has been extensively investigated for convex NEPs, i.e., the case where \(\gamma^\omega(x,\cdot,y^{-\omega})\) is convex for any fixed \(x\) and \(y^{-\omega}\), and \(Y^\omega\) is convex. These results can be extended to nonconvex NEPs as follows:

Hereinafter, assume that \(\mu<\ell^{-1}\). From Danskin’s theorem, we have \[\nabla h_\mu(x,y) = \sum_{\omega=1}^M \begin{bmatrix} \nabla_x \gamma^\omega(x,y) - \nabla_x \gamma^\omega(x,z^{*,\omega}(x,y),y^{-\omega}) \\ \nabla_y \gamma^\omega(x,y) - \varpi^\omega(x,z^{*,\omega}(x,y),y^{-\omega}) \end{bmatrix},\] where \(z^{*,\omega}(x,y)=\argmin_{z^\omega\in Y^\omega} \{\gamma^\omega(x,z^\omega,y^{-\omega})+1/(2\mu)\|z^\omega-y^\omega\|^2\}\) and \[\varpi^\omega(x,z^{*,\omega}(x,y),y^{-\omega}) \coloneq \begin{bmatrix} \nabla_{y^1} \gamma^\omega(x,z^{*,\omega}(x,y),y^{-\omega}) \\ \vdots \\ \nabla_{y^{\omega-1}} \gamma^\omega(x,z^{*,\omega}(x,y),y^{-\omega}) \\ \frac{1}{\mu}(y^\omega-z^{*,\omega}(x,y)) \\ \nabla_{y^{\omega+1}} \gamma^\omega(x,z^{*,\omega}(x,y),y^{-\omega}) \\ \vdots \\ \nabla_{y^M} \gamma^\omega(x,z^{*,\omega}(x,y),y^{-\omega}) \end{bmatrix}.\]

Define \[\hat{S}(x) \coloneq \{y\in Y \mid h_\mu(x,y)\le 0\}.\] By Proposition [prop:NIfunc], it holds that \[S(x) \subset \hat{S}(x),\label{eq:sxshs}\tag{13}\] where the equality holds if \(\gamma^\omega(x,\cdot,y^{-\omega})\) is convex. The following proposition characterizes \(\hat{S}(x)\) by the first-order conditions of the followers’ problems. The proof is similar to the result by [38] for bilevel optimization.

Define the following problem by replacing the followers’ Nash equilibrium condition \(y\in S(x)\) in 10 with \(y\in\hat{S}(x)\): \[\begin{align} \label{prob:reduced46relaxed} \min_{w^\nu \in \mathbb{R}^{n_\nu+m}} \quad \theta^\nu(w^\nu,x^{-\nu}) \qquad \text{s.t.} \quad w^\nu=(x^\nu,\hat{y}^\nu)\in\hat{W}^\nu_0(x^{-\nu}), \end{align}\tag{14}\] where \[\begin{align} \hat{W}_0^\nu(x^{-\nu}) \coloneq& \{w^\nu\in\mathbb{R}^{n_\nu+m} \mid x^\nu\in X^\nu, \hat{y}^\nu\in\hat{S}(x^\nu,x^{-\nu})\}\\ =& \{w^\nu\in\mathbb{R}^{n_\nu+m} \mid x^\nu\in X^\nu, \hat{y}^\nu\in Y, h_{\mu}(x^{\nu},x^{-\nu},\hat{y}^\nu)\le 0\}. \end{align}\] We denote by \(\widehat{\mathrm{GNEP}}(\{(\hat{W}^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\) the game in which leader \(\nu\) solves 14 . \(\widehat{\mathrm{GNEP}}(\{(\hat{W}^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\) is a relaxation of \(\mathrm{GNEP}(\{(W^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\) due to  13 . If the followers’ NEP is convex, i.e., the objective function \(\gamma^\omega(x,\cdot,y^{-\omega})\) is convex, \(\hat{S}(x)=S(x)\) holds and hence this relaxation is tight; otherwise, the concept of the equilibrium differs from each other.

The following assertion holds obviously.

Despite the regularization of the value-function \(h(x,y)\) (called \(h_\mu(x,y)\)), \(\widehat{\mathrm{GNEP}}(\{(\hat{W}^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\) is still difficult to solve in practice since

• the constraint of each leader’s problem still depends on \(x^{-\nu}\);

• ordinary constraint qualifications, such as the Mangasarian–Fromovitz constraint qualification, do not hold in general [39], which will be discussed in detail in Section 4.2.

Now we consider a partially penalized problem of 14 as follows: \[\begin{align} \label{prob:penalty} \begin{aligned} \min_{w^\nu} &\quad \Theta^\nu_\mu(w^\nu,x^{-\nu};\rho) \coloneq \theta^\nu(w^\nu,x^{-\nu})+\rho h_\mu(w^\nu,x^{-\nu}) \\ \text{s.t.} &\quad w^\nu \in W^\nu \coloneq X^\nu\times Y, \end{aligned} \end{align}\tag{15}\] where \(\rho>0\) is a penalty parameter. The penalization utilizes the property of \(h_\mu\) that

• \(h_\mu(x,y)\ge 0\) for all \(x\in X\) and \(y\in Y\);

• \(h_\mu(x,y)\le 0\) implies that \(y\in\hat{S}(x)\) (respectively, \(y\in S(x)\) if \(\gamma^\omega(x,\cdot,y^{-\omega})\) is convex).

Note that 15 for \(\nu=1,\dots,N\), are regarded as a single-level NEP; thus, the game in which leader \(\nu\in\{1,\dots,N\}\) solves 15 is referred to as \(\mathrm{NEP}_\rho(\{(W^\nu,\Theta^\nu_\mu(\cdot;\rho))\}_{\nu=1}^N)\) or \(\rho\)-penalized NEP, and \(\widehat{\mathrm{GNEP}}(\{(\hat{W}^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\) is referred to as constrained GNEP.

In order to analyze some properties of \(\mathrm{NEP}_\rho(\{(W^\nu,\Theta^\nu_\mu(\cdot;\rho))\}_{\nu=1}^N)\) in the next section, we introduce the following relaxed \(\widehat{\mathrm{GNEP}}(\{(\hat{W}^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\), in which each leader’s reduced problem 14 is relaxed as \[\begin{align} \label{prob:relaxed46problem} \min_{w^\nu}\quad \theta^\nu(w^\nu,x^{-\nu}) \qquad \text{s.t.}\quad w^\nu\in\hat{W}^\nu_{\delta^\nu}(x^{-\nu}), \end{align}\tag{16}\] where \[\hat{W}^\nu_{\delta^\nu}(x^{-\nu}) \coloneq \{w^\nu\in W^\nu\mid h_\mu(w^\nu,x^{-\nu})\le\delta^\nu\}.\] For \(\delta\coloneq(\delta^1,\dots,\delta^N)\), we denote by \(\widehat{\mathrm{RGNEP}}_{\delta}(\{(\hat{W}^\nu_{\delta^\nu}(\cdot),\theta^\nu)\}_{\nu=1}^N)\) the noncooperative game in which leader \(\nu\in\{1,\dots,N\}\) solves 16 , which is called \(\delta\)-relaxed GNEP.

4 Relationships between \(\rho\)-penalized NEP and \(\delta\)-relaxed GNEP↩︎

In this section, we study the relationships between \(\mathrm{NEP}_\rho(\{(W^\nu,\Theta^\nu_\mu(\cdot;\rho))\}_{\nu=1}^N)\) and \(\widehat{\mathrm{RGNEP}}_{\delta}(\{(\hat{W}^\nu_{\delta^\nu}(\cdot),\theta^\nu)\}_{\nu=1}^N)\) with particular emphasis on their solution sets. We summarize the relationships between the MLFG and these NEPs in Figure 1 and Table 1, provided in the end of this section.

4.1 Approximate Nash equilibria of \(\rho\)-penalized NEP and relaxed GNEP↩︎

First, we introduce an approximate NE of \(\mathrm{NEP}_\rho(\{(W^\nu,\Theta^\nu_\mu(\cdot;\rho))\}_{\nu=1}^N)\) and an approximate GNE of \(\widehat{\mathrm{RGNEP}}_{\delta}(\{(\hat{W}^\nu_{\delta^\nu}(\cdot),\theta^\nu)\}_{\nu=1}^N)\).

We analyze the relationship between \(\mathrm{NEP}_\rho(\{(W^\nu,\Theta^\nu_\mu(\cdot;\rho))\}_{\nu=1}^N)\) and
\(\widehat{\mathrm{RGNEP}}_{\delta}(\{(\hat{W}^\nu_{\delta^\nu}(\cdot),\theta^\nu)\}_{\nu=1}^N)\) in terms of approximate (G)NE. Some auxiliary lemmas are given before the main assertions.

The following lemma concerns the gap of the objective values \(\Theta^\nu_\mu\) between a feasible point of \(\hat{W}^\nu_0(x^{-\nu})\) and some point \(w^\nu\in W^\nu\) for a fixed \(x^{-\nu}\).

The following theorem states that if a point is an approximate \(\varepsilon\)-NE of \(\mathrm{NEP}_\rho(\{(W^\nu,\Theta^\nu_\mu(\cdot;\rho))\}_{\nu=1}^N)\), then it is also that of \(\widehat{\mathrm{RGNEP}}_{\delta}(\{(\hat{W}^\nu_{\delta^\nu}(\cdot),\theta^\nu)\}_{\nu=1}^N)\) for some \(\delta\) depending on the penalty parameter \(\rho\).

Theorem 2 means that for \(\{\varepsilon_k\}\) and \(\{\rho_k\}\) with \(\varepsilon_k\to 0\) and \(\rho_k\to\infty\), the convergent point of the sequence \(\{w_k\}\) of \(\varepsilon_k\)-NE of \(\rho_k\)-penalized NEP is a NoLFNE.

Before proceeding to the next section, we show Assumptions [asmp:compact46follower] and [asmp:smooth46follower] are sufficient conditions for \(\hat{W}^\nu_0(x^{-\nu}_{\rho_k})\neq\emptyset\).

4.2 Variational equilibrium of \(\rho\)-penalized NEP and its feasibility↩︎

Since \(\rho\)-penalized NEP is nonconvex, it may not have any NE in general. Hence, we introduce a weaker concept of equilibrium referred to as a variational equilibrium. First, let us define the variational equilibrium for penalized NEP.

Since \(W^\nu\) is compact and convex, and \(\nabla_{w^\nu}\Theta^\nu_\mu\) is continuous, the existence of the VE for \(\mathrm{NEP}_\rho(\{(W^\nu,\Theta^\nu_\mu(\cdot;\rho))\}_{\nu=1}^N)\) is shown in the same manner as Proposition [prop:suff46nonempty46W].

Now, we discuss the first-order optimality condition, or necessary condition for NoLFNE of \(\widehat{\mathrm{GNEP}}(\{(\hat{W}^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\). In bilevel optimization, the optimality condition is discussed over a couple of decades [21], [39], [41]. Based on such literature, we extend their concept to MLFG.

Next, we introduce partial calmness for 14 , which serves as a constraint qualification-like condition. It is known that 14 does not satisfy standard constraint qualifications for nonlinear optimization, such as the Mangasarian–Fromovitz (MFCQ) or the constant-rank constraint qualifications (CRCQ), due to \(h_\mu(x,y)\le 0\) [39]. Then, Ye and Zhu [39] proposed a weaker version of calmness [42] for level-reduced bilevel optimization.

To introduce the partial calmness condition of our context, we let \(p^\nu\in \mathbb{R}\) for each \(\nu\in \{1,\ldots,N\}\) and consider the following perturbed problem for 14 : \[\begin{align} \label{prob:reduced46perturbed} \min_{w^\nu}\quad \theta^\nu(w^\nu,x^{-\nu}) \qquad \text{s.t.} \quad w^\nu\in W^\nu,\;h_\mu(w^\nu,x^{-\nu})+p^\nu=0. \end{align}\tag{17}\] The difference between 14 and 17 lies in the perturbation of the constraint \(h_\mu(w^\nu,x^{-\nu})\le 0\). The partial calmness condition is defined as follows.

Recalling the first assertion of Proposition [prop:NIfunc], i.e., \(h_\mu\ge 0\), note that inequality 18 can also be written as follows if \(w^\nu\) is feasible to 17 : \[\theta^\nu(w^\nu,x^{-\nu})-\theta^\nu(\bar{w}^\nu,x^{-\nu})+\rho^\nu h_\mu(w^\nu,x^{-\nu})\ge 0.\] This inequality means that the variation in the leader \(\nu\)’s objective from \(\bar{w}^\nu\) to \({w}^\nu\) being feasible to 17 , \(\theta^\nu({w}^\nu,x^{-\nu})-\theta^\nu(\bar{w}^\nu,x^{-\nu})\), is bounded below by \(\rho^\nu\) times some perturbation for \(-h_\mu\). It can also be seen that the partial calmness condition, in practice, requires \(\widehat{\mathrm{GNEP}}(\{(\hat{W}^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\) to admit a Lagrange multiplier associated with the inequality constraint \(h_\mu(w^\nu,x^{-\nu})\le 0\) for each leader’s reduced problem 14 .

The following lemma implies that for a given point \(x^*\in X\), if \(h_\mu(\cdot,x^{*,-\nu})\) satisfies HEB for all \(\nu\) and the objective function is locally Lipschitz continuous around a feasible point of \(h_\mu(w^\nu,x^{*,-\nu})\le 0\), 14 is partially calm at \(w^{*,\nu}\in \hat{W}^\nu_0(x^{*,-\nu})\).

The assumption of the HEB with \(\eta\le 1\) in Lemma 11 requires that \(h_\mu(\cdot,x^{*,-\nu})\) converges to zero no faster than \(\xi\|w^\nu-w^{*,\nu}\|^\eta\) with \(\eta\le 1\).

As stated below, if \(\widehat{\mathrm{GNEP}}(\{(\hat{W}^\nu_0(\cdot),\theta^\nu)\}_{\nu=1}^N)\) is partially calm at some NoLFNE (see Definition 7), then the first-order optimality conditions hold for all \(\nu\).

In the rest of this section, we establish the relationship between VE of \(\mathrm{NEP}_\rho(\{(W^\nu,\Theta^\nu_\mu(\cdot;\rho))\}_{\nu=1}^N)\) and \(\widehat{\mathrm{RGNEP}}_{\delta}(\{(\hat{W}^\nu_{\delta^\nu}(\cdot),\theta^\nu)\}_{\nu=1}^N)\) and also show that the constraint \(h_\mu(w^\nu,x^{-\nu})\le 0\) is approximately satisfied at a VE of \(\mathrm{NEP}_\rho(\{(W^\nu,\Theta^\nu_\mu(\cdot;\rho))\}_{\nu=1}^N)\).

The following theorem shows that the VE of \(\mathrm{NEP}_\rho(\{(W^\nu,\Theta^\nu_\mu(\cdot;\rho))\}_{\nu=1}^N)\) is also that of
\(\widehat{\mathrm{RGNEP}}_{\delta}(\{(\hat{W}^\nu_{\delta^\nu}(\cdot),\theta^\nu)\}_{\nu=1}^N)\).

Lastly, we conclude this section with the proposition concerning the bounds on the feasibility violation of \(h_\mu(w^\nu,x^{-\nu})\le 0\) around an approximate VE of the \(\rho\)-penalized NEP. We make the following assumption, which imposes a Kurdyka–Łojasiewicz-like property on \(h_{\mu}\).

Finally, we summarize the relationships between the MLFG and all the NEPs in Figure 1 and Table 1.

5 Conclusions↩︎

This paper proposed a new reformulation for the MLFG by exploiting the regularized Nikaido–Isoda function. Unlike traditional reformulations such as EPEC and response-based approaches, our reformulation does not use any derivative information regarding each follower’s problem. We analyzed the relation between the (No)LFNE and the approximated NE for the resulting NEP. Although we assumed that the followers’ constraint sets are independent of \(x\) throughout this paper, readers may be interested in the more general case of \(Y^\omega(x)\). However, the analysis may become much more difficult since it may require the set-valued analysis as well. We also leave it for future work.

Appendix: Implicit differentiation of the followers’ response↩︎

Using Fischer–Burmeister functions [40], the complementarity conditions of KKT system 5 are equivalently reformulated as a nonsmooth equation as follows: \[0=H_0(x,y,\lambda) \coloneq \begin{bmatrix} \nabla_{y^\omega}\gamma^\omega(x,y^\omega,y^{-\omega})+\nabla_{y^\omega} g^\omega(y^\omega)\lambda^\omega \\ [\phi(\lambda^\omega_i,-g^\omega_i(y^\omega))]_{i=1}^{p_\omega} \end{bmatrix}_{\omega=1}^M \in\mathbb{R}^{m+p},\] where \(p \coloneq p_1+\dots+p_M\) and \(\phi\colon\mathbb{R}^2\to\mathbb{R}\) satisfies \(\phi(a,b)=0\) if and only if \(0\le a \perp b\ge 0\). Since \(\phi(a,b)\) is not differentiable at some points in general, a smoothing approximated Fischer–Burmeister function \(\phi_\varepsilon\), where \(\varepsilon>0\) denotes an approximation parameter, is adopted such that \(\lim_{\varepsilon\searrow 0}\phi_\varepsilon(a,b)=\phi(a,b)\) for any \(a,b\in\mathbb{R}^2\). Then, by replacing \(\phi\) with \(\phi_\varepsilon\), the function \(H_0\) is approximated by the smoothed system of equations: \(H_\varepsilon(x,y,\lambda)=0\).

Under the uniqueness assumption of \(y\) and \(\lambda\) for \(H_\varepsilon(x,y,\lambda)=0\), the solution to the equation with respect to \(y\) and \(\lambda\) is written as \(y_\varepsilon(x)\) and \(\lambda_\varepsilon(x)\). By using the implicit function theorem [20], the Jacobian \([\nabla y_\varepsilon(x), \nabla \lambda_\varepsilon(x)]\) is computed as \[[\nabla y_\varepsilon(x), \nabla \lambda_\varepsilon(x)] =-\nabla_x H_\varepsilon(x,y_\varepsilon(x),\lambda_\varepsilon(x)) \begin{bmatrix} \nabla_y H_\varepsilon(x,y_\varepsilon(x),\lambda_\varepsilon(x)) \\ \nabla_\lambda H_\varepsilon(x,y_\varepsilon(x),\lambda_\varepsilon(x)) \end{bmatrix}^{-1}.\] This means that the gradient computation of the (implicit) response requires Hessian matrices \(\nabla^2_y \gamma^\omega\) and \(\nabla^2_{y^\omega}g^\omega\) and inverse matrix as shown above.

References↩︎

---

1. Graduate School of Engineering, Nagoya Institute of Technology, Aichi, Japan.↩︎

2. Faculty of Science and Technology, Seikei University, Tokyo, Japan.↩︎

3. Graduate School of Informatics, Kyoto University, Kyoto 606–8501, Japan.↩︎

4. This work was supported by Japan Society for the Promotion of Science, and Grant-in-Aid for Early-Career Scientists (JP26K21172), Grant-in-Aid for Scientific Research (C) (JP25K15008, JP25K15002), and Grant-in-Aid for Scientific Research (B) (JP25K03082).↩︎

5. Recalling Proposition [prop:NIfunc], note that from the assumption \(\hat{W}^\nu_0(x^{*,-\nu})\neq\emptyset\), we have \(\min_{w^\nu} h_\mu(w^\nu,x^{*,-\nu}) = 0\).↩︎