Technical Note—Characterizing and Computing the Set of Nash Equilibria via Vector Optimization

1. Introduction

The Nash equilibrium is a fundamental concept in game theory. Proposed by John Nash in his seminal papers (Nash 1950, 1951), the Nash equilibrium notion provides a stable strategy set in a noncooperative game setting. Specifically, these solutions are such that no player can unilaterally reduce her costs when all other players fix their own strategies. Though an equilibrium of a noncooperative game was first introduced as the solution to a special linear program by von Neumann (1928) in a two-player zero-sum setting, a general N-player game is solved via fixed-point arguments. Even for games with convex costs and constraints, fixed-point arguments are required, as demonstrated in Rosen (1965); there always exists a Nash equilibrium for a convex game, but stronger convexity conditions are required to guarantee uniqueness. In this work, we are not concerned with the existence or uniqueness of Nash equilibria. Instead, our aim is to fully characterize, and thus enable the computation of, the set of all Nash equilibria. As such, these results are independent of the set of equilibria being a singleton, containing several or even infinitely many elements, or being an empty set.

A Nash game is defined by a collection of optimization problems. Mathematically, this is encoded by cost functions and constraint sets for each player. Though it is tempting to consider the vector optimization problem constructed from the N-player noncooperative game in which all players simultaneously attempt to minimize their costs, the set of minimizers of this vector optimization problem generally does not coincide with the set of the Nash equilibria for the game. Our primary motivation within this work is to construct a particular vector optimization problem that provides exactly the set of Nash equilibria as its minimizers. This allows us to think about Nash equilibria as just a special type of Pareto efficiency.

Importantly, where the appropriate vector optimization algorithms exist, this new optimization construction of the set of Nash equilibria allows for a novel computational technique that provides all Nash equilibria. This proposed technique does not require any fixed-point iterations. For example, algorithms—like those proposed in Armand (1993), Van Tu (2017), and Tohidi and Hassasi (2018)—can be used to solve the corresponding linear vector optimization problems appearing in the Pareto characterization of the set of Nash equilibria for games with linear objectives and constraints. For convex and nonconvex games, the corresponding vector optimization problems can in practice only be solved approximately. The corresponding relation between epsilon Pareto-optimal solutions and epsilon Nash equilibria and the development of numerical algorithms is ongoing work; for the convex case, see Feinstein et al. (2023). The present paper will therefore focus on the equivalent characterization holding for all noncoorporative games and illustrate the theoretical results both on games that can be solved analytically and on linear games, where existing vector optimization algorithms can be applied to compute the set of Nash equilibria.

The problem of finding a single Nash equilibrium has been well studied for (nearly) all classes of games. For instance, Rosen (1965) provides an efficient algorithm to compute the unique equilibrium for a class of convex games. However, for games with multiple equilibria, understanding the entire set of Nash equilibria is vitally important to fully characterize the possible (jointly) rational behaviors of the players in the game. Despite the importance of finding all Nash equilibria in practice, this problem has received less attention, and results are so far limited to specific classes of games. There have been numerous studies on computing all Nash equilibria for finite games; we refer the interested reader to, for example, McKelvey and McLennan (1996), Parsopoulos and Vrahatis (2004), Herings and Peeters (2005), Wu et al. (2015), references therein, and citations thereof. We also wish to highlight Judd et al. (2012), which utilizes algebraic geometry to find (a superset of) all Nash equilibria in continuous games without binding constraints, that is, where the equilibria lie within the interior of the feasible region. Generalized Nash games have additionally been approached as quasi-variational inequalities (Harker 1991). Such an approach allows for the computation of (a superset of) all Nash equilibria by considering an infinite number of variational inequalities in a shared-constraint setting (Nabetani et al. 2011). In contrast to these aforementioned approaches, our methodology merely relies on the appropriate vector optimization algorithms to compute all Nash equilibria. In fact, our approach can be readily extended to vector games (Corley 1985, Bade 2005) in which the computation of Nash equilibria is often considered a challenge because of the large number of solutions and for which, as far as the authors are aware, there do no exist any algorithms to compute all equilibria for general classes of problems. To highlight the novelty of our approach, we provide numerical examples in which we compute all Nash equilibria in settings where these prior cited approaches cannot be applied.

The primary contribution of this work is threefold. First, we provide an equivalent characterization of the set of all Nash equilibria of a game as Pareto-optimal points of a certain vector optimization problem. This holds for all noncooperative games without any further assumptions. We highlight in Remark 2.9 a relation between the solutions of the specified vector optimization problem and the best response functions of all players; this connects our results to the well-known simple characterization of the set of Nash equilibria as the intersection of the graphs of the best response functions for all players (see, e.g., the introduction section in Beck and Stein 2023). We will illustrate this characterization on a simple game with nonconvex cost functions. Second, for generalized Nash games, we construct two bounding vector optimization problems that provide, respectively, necessary and sufficient conditions for the Nash equilibria and correspond to specific shared-constraint games considering the union or intersection of the players’ constraints, respectively. Furthermore, and as a third contribution, this vector optimization reformulation of the Nash game permits us to consider optimization-based methods for finding all Nash equilibria. This is in contrast to the typical approaches that construct just a single Nash equilibrium as well as the aforementioned works on the computation of all Nash equilibria for specific classes of games. This extends well beyond finite games to provide the theoretical foundation for a numerical technique to find all Nash equilibria for, for example, convex games or even for vector-valued games.

The organization of this paper is as follows. In Section 2, the set of Nash equilibria for a Nash game with a shared constraint are completely characterized as the Pareto solutions to an appropriate vector optimization problem with a nonconvex ordering cone. Because of the special structure of this cone, we present a decomposition that allows for its tractable use. We extend this result in Section 3 to study the use of the proposed vector optimization problems for generalized Nash games. In such a setting, we first construct a characterization of the set of Nash equilibria. Second, we use our vector optimization framework to construct bounds around the set of Nash equilibria. Specifically, we find that one proposed vector optimization problem leads to a necessary condition, and a different one to a sufficient condition for the Nash equilibria. We further extend these results in Section 4 to study vector-valued games. Importantly, all of the prior results hold under only minimal modifications to the ordering cone. We present a number of illustrative examples throughout this work to demonstrate the application of the proposed results for the computation of the set of Nash equilibria.

2. Shared-Constraint Nash Games as Vector Optimization

In this section, we will construct a particular vector optimization problem whose Pareto-optimal points coincide with, and thus equivalently characterize, the set of equilibria of shared-constraint Nash games. Section 2.1 will introduce the basic notation and definitions of Nash equilibria, vector optimization, and Pareto-optimal points. Section 2.2 will contain the main results of this section on the characterization of the set of equilibria of shared-constraint Nash games as Pareto-optimal points of a certain vector optimization problem. In Section 2.3, we will illustrate these results with examples.

2.1. Background and Notation

Let us now introduce the two disparate frameworks for studying competing interests in optimization: Pareto optimality and Nash equilibria. In doing so, we will provide basic definitions and notation which will be utilized for the remainder of this work.

Throughout this work, we will study $N\ge 2$-player noncooperative games. We will occasionally refer to these as Nash games as the relevant solution concept is that of a Nash equilibrium (see Definition 2.2). Player i (for $i=1,\dots ,N$) of this game considers strategies in the linear space ${\mathcal{X}}_i$; we do not impose any condition that ${\mathcal{X}}_i$ and ${\mathcal{X}}_j$ are equal. In addition, each player i has a cost function $f_i:{\prod }_{j=1}^N{\mathcal{X}}_j\to \mathbb{R}$ she seeks to minimize. This cost function $f_i(x)$ for $x\in {\prod }_{j=1}^N{\mathcal{X}}_j$ may depend on player i’s strategy $x_i\in {\mathcal{X}}_i$ as well as the strategy chosen by all other players, $x_{-i}\in {\prod }_{j\ne i}{\mathcal{X}}_j$. Finally, in order to complete the setup of the N-player noncooperative game, we wish to introduce the notion of a shared constraint $\mathbb{X}\subseteq {\prod }_{j=1}^N{\mathcal{X}}_j$, which must be satisfied by the joint strategy $x\in {\prod }_{j=1}^N{\mathcal{X}}_j$ of all players. This shared-constraint condition is common in the literature (see, e.g., Rosen 1965, Facchinei et al. 2007).

Remark 2.1.

By utilizing the constraint set $\mathbb{X}\subseteq {\prod }_{j=1}^N{\mathcal{X}}_j$ in the product of the linear spaces ${\mathcal{X}}_i$, we allow for either pure or mixed strategy Nash equilibria. Furthermore, the use of the general constraint set $\mathbb{X}$ permits us to study, for example, both discrete or continuous games. For example, in a two-player game in which both players can only select in the strategy set {0, 1}, ${\mathcal{X}}_1={\mathcal{X}}_2=\mathbb{R}$ with $\mathbb{X}={\{0,1\}}^2$. If one allows mixed strategies in this game, which are encoded by the probability $x_i\in [0,1]$ as the probability of selecting strategy 1, one would set $\mathbb{X}={[0,1]}^2$.

Given all other players fix their strategies $x_{-i}^{*}\in {\prod }_{j\ne i}{\mathcal{X}}_j$, player i seeks to optimize

$$\underset{x_i\in {\mathcal{X}}_i}{\min }\left\{f_i(x_i,x_{-i}^{*})|(x_i,x_{-i}^{*})\in \mathbb{X}\right\}.$$(1)

If this is the aim of all players $i=1,\dots ,N$, this leads to the definition of a Nash equilibrium.

Definition 2.2.

Consider the shared-constraint Nash game with N players described by (1). That is, player i has strategies in the space ${\mathcal{X}}_i$, cost function $f_i:{\prod }_{j=1}^N{\mathcal{X}}_j\to \mathbb{R}$, and the joint strategies must satisfy a shared feasibility condition $x\in \mathbb{X}\subseteq {\prod }_{j=1}^N{\mathcal{X}}_j$. A joint strategy $x^{*}\in \mathbb{X}$ is called a Nash equilibrium if, for any player i, $f_i(x_i,x_{-i}^{*})\ge f_i(x^{*})$ for any strategy $x_i\in {\mathcal{X}}_i$ such that $(x_i,x_{-i}^{*})\in \mathbb{X}$. The set of all Nash equilibria will be denoted by $\mathrm{NE}(f,\mathbb{X})$.

Later in this work, we will relax the assumption of the shared constraint to study generalized Nash games (see Section 3). We will, additionally, relax the assumption that the cost functions are real valued to study vector-valued games in Section 4.

The main focus of this work is the relation between the set of Nash equilibria and the Pareto-optimal points of a certain vector optimization problem. Let us now introduce the basic notations needed for that. Consider a linear space $\mathcal{Z}$. A set $C\subseteq \mathcal{Z}$ is called a cone if $\alpha C\subseteq C$ for all $\alpha \ge 0$. A cone $C\subseteq \mathcal{Z}$ introduces a binary relation ${\le }_C$ on $\mathcal{Z}$ via

$$x{\le }_{C}y\iff y-x\in C,$$

for $x,y\in \mathcal{Z}$. This relation is reflexive. If the cone C is additionally convex, that is, if it holds $C+C\subseteq C$, then the relation ${\le }_C$ is reflexive and transitive, and thus defines a preorder relation on $\mathcal{Z}$. If C is not convex, then the relation ${\le }_C$ is not transitive, and so it is not a preorder relation and is sometimes called a “nonconvex preference” (for a discussion of nonconvex preferences, see Anderson 1985). We will also, in that case, refer to the cone C as the ordering cone of $\mathcal{Z}$. From now on, we consider a linear space $\mathcal{Z}$ endowed with an ordering cone C. When $\mathcal{Z}=\mathbb{R}$ and $C={\mathbb{R}}_{+}$, we will leave off the explicit notation for the cone C, that is, $x\le y$ if and only if $y-x\in {\mathbb{R}}_{+}$ for $x,y\in \mathbb{R}$.

A vector optimization problem is an optimization problem of the form

$$C\text{-min}\{g(x)|x\in \mathbb{X}\}$$(2)

for some feasible region $\mathbb{X}\subseteq \mathcal{X}$ for a linear space $\mathcal{X}$, a function $g:\mathbb{X}\to \mathcal{Z}$, and an ordering cone $C\subseteq \mathcal{Z}$. Note that we do not necessarily assume the cone C to be convex. The notation $C\text{-min}$ used in (2) means that one is minimizing the vector-valued function g, where the usage of C in this notation emphasizes that one minimizes with respect to (w.r.t.) the binary relation introduced by the ordering cone C. To minimize this vector-valued function, and thus to solve the vector optimization problem (2), means to compute the set of minimizers, also called Pareto-optimal points, or efficient points, which are defined as follows. We use the notation $g[\mathbb{X}]≔\{g(x)|x\in \mathbb{X}\}\subseteq \mathcal{Z}$ for the image of the feasible set $\mathbb{X}$.

Definition 2.3.

The set of minimizers or Pareto-optimal points of problem (2) is defined as

$$C\text{-arg}\hspace{0.17em}\text{min}\{g(x)|x\in \mathbb{X}\}=\{x^{*}\in \mathbb{X}|g(x^{*}){\le }_{C}g(x)\hspace{0.17em}\forall x\in \mathbb{X}\hspace{0.17em}\text{with}\hspace{0.17em}g(x){\le }_{C}g(x^{*})\}.$$

This is the set of feasible points $x^{*}$ that map to minimal elements of $g[\mathbb{X}]$, that is, the set of points $x^{*}\in \mathbb{X}$ such that if $g(x){\le }_{C}g(x^{*})$ for some $x\in \mathbb{X}$, then $g(x^{*}){\le }_{C}g(x)$ holds.

The above definitions can be found in (Jahn 2011, definitions 3.1(c), 4.1(a), and 7.1(a)) for the case of a convex cone C and partially ordered normed space $\mathcal{Z}$ (but can also be stated on the general level provided here, i.e., for a cone C and linear space $\mathcal{Z}$). They also coincide with the more general definitions given in (Tammer and Weidner 2020, chapter 6) by setting the reference set there to be $D=C\backslash (-C)$.

2.2. Nash Equilibria as Pareto-Optimal Points

In this section, we want to deduce a relation between the set of Nash equilibria and the Pareto-optimal points of a certain vector optimization problem. Note that the Definition 2.2 of a Nash equilibrium can equivalently be written as follows: the joint strategy $x^{*}\in \mathbb{X}$ is called a Nash equilibrium if, for any player i,

Naively, one may attempt to construct the vector optimization problem

with $f(x)≔(f_1(x),f_2(x),\dots ,f_N(x))$ from the N-player noncooperative game. However, it is well known that the minimizers of this vector optimization problem generally do not coincide with any of the Nash equilibria for the game (see, e.g., Tadelis 2013, chapter 3.3). This is because, in the underlying optimization problem for each player i in (3), the strategy $x_{-i}^{*}$ of all other players is fixed. We will now construct a vector optimization problem that will exactly take these considerations into account.

In order to facilitate this, we will need two modifications to (4). First, we need to put the strategy in the objective as well such that one can consider, for each player, $x_{-i}$ and $f_i(x)$ at the same time. That is, we will set $g(x)=(x,f(x))$ as the objective function in (2) instead of $g(x)=f(x)$, as was done in (4). Thus, the linear space $\mathcal{Z}$ in (2) is chosen to be ${\prod }_{i=1}^N{\mathcal{X}}_i\times {\mathbb{R}}^N$. Second, we will define a particular ordering cone that can “fix” the component $x_{-i}$ of the vector x for player i. That is, we will consider the following vector optimization problem

with ordering conewhere the zero in $x_{-i}=0$ is the zero in the space ${\prod }_{j\ne i}{\mathcal{X}}_j$. Though the ordering cone C is not convex, it is of the form $C={\cup }_{i=1}^N{C}_i$ for convex cones C_i defined aswhere $0_{{\mathcal{X}}_j}$ denotes the zero in the space ${\mathcal{X}}_j$. Whenever the space is clear from the context, we will, for the remainder of this work, drop the subscript notation and just use 0 for the zero in the corresponding space. The decomposition of C into the cones C_i will be utilized in the following and plays a particular role in the examples via Corollary 2.8. The following remarks motivate and illustrate the choice of the vector optimization problem (5) and its cone (6).

Example 2.4.

Let us, for illustration purposes, consider the cone C in the easiest setup of a two-player game (N = 2) with ${\mathcal{X}}_1={\mathcal{X}}_2=\mathbb{R}$. Then, $C\subseteq {\mathbb{R}}^4$ is given by

$$\begin{array}{ll}C\hfill & =\{(x,y)\in {\mathbb{R}}^2\times {\mathbb{R}}^2|\exists i\in \{1,2\}:\hspace{0.17em}{x}_{-i}=0,\hspace{0.17em}{y}_i\ge 0\}\hfill \\ \hfill & =(\mathbb{R}\times \{0\}\times {\mathbb{R}}_{+}\times \mathbb{R})\cup (\{0\}\times \mathbb{R}\times \mathbb{R}\times {\mathbb{R}}_{+})=C_1\cup C_2.\hfill \end{array}$$(8)

For a two-player game (N = 2) with ${\mathcal{X}}_1={\mathcal{X}}_2={\mathbb{R}}^2$, the cone $C\subseteq {\mathbb{R}}^6$ is given by

$$C=({\mathbb{R}}^2\times \{(0,0)\}\times {\mathbb{R}}_{+}\times \mathbb{R})\cup (\{(0,0)\}\times {\mathbb{R}}^2\times \mathbb{R}\times {\mathbb{R}}_{+})=C_1\cup C_2.$$(9)

Remark 2.5.

Note the roles the different components in the cones C (respectively, C_i) play. Consider the following three ordering cones in $\mathbb{R}$:

• The component ${\mathbb{R}}_{+}$ is the natural ordering cone and characterizes the usual order relation $x\le y\iff x{\le }_{{\mathbb{R}}_{+}}y\iff y-x\in {\mathbb{R}}_{+}$ that is, for example, considered in player i’s optimization problem (1) (see also (3), when player i minimizes her objective function f_i).

• The component $\{0\}$ is an ordering cone that allows us to “fix” the corresponding component in the sense that $x{\le }_{\{0\}}y\iff y-x\in \{0\}\iff x=y$; that is, the only element that can be compared with x is x itself. This becomes important because we need, in player i’s optimization problem (1), to fix the other players strategies to be $x_{-i}^{*}$.

• The component $\mathbb{R}$ is an ordering cone that allows us to ignore the corresponding component in the sense that $x{\le }_{\mathbb{R}}y\iff y-x\in \mathbb{R}\iff x{\ge }_{\mathbb{R}}y$ is true for all $x,y\in \mathbb{R}$. That is, with respect to this ordering cone, every point would be minimal. Thus, with respect to the corresponding component, where this ordering cone is considered, nothing needs be optimized, so this component is ignored. This becomes important as player i does not care about the cost functions of his opponents in his optimization problem (1). Additionally, the full space also appears as the ordering cone in the component concerned with the strategy x_i of player i. In such a capacity, this ordering cone models the idea that there are no further restrictions player i imposes on his own strategy (besides the constraint set $\mathbb{X}$ that is incorporated already in Problem (5)).

The interpretations of the last two cones above hold analogously if one considers the cones $\{(0,0)\}$ or ${\mathbb{R}}^2$ if ${\mathcal{X}}_i={\mathbb{R}}^2$, or, for more general ${\mathcal{X}}_i$, the cones $\{0_{{\mathcal{X}}_i}\}$ or ${\mathcal{X}}_i$.

Consider now the specific structure of the preferences induced by the ordering cone C and its decomposition $C={\cup }_{i=1}^N{C}_i$. These structures are central to relating the set of Nash equilibria to the Pareto-optimal points of (5) as is provided in Theorem 2.6 below. Let us first study the cone C_i: Consider $x,\overline{x}\in {\prod }_{i=1}^N{\mathcal{X}}_i$; then $(x,f(x)){\ge }_{C_i}(\overline{x},f(\overline{x}))$ for some player i if and only if $x_{-i}={\overline{x}}_{-i}$ and $f_i(x)\ge f_i(\overline{x})$. That is, for a “fixed” strategy of all other players, the cost of player i is greater under x than $\overline{x}$. For the full cone C, the relation $(x,f(x)){\ge }_C(\overline{x},f(\overline{x}))$ holds if and only if there exists some player i such that $(x,f(x)){\ge }_{C_i}(\overline{x},f(\overline{x}))$. From this, the correspondence to the Nash equilibrium becomes clear, as both the Nash and the Pareto solutions with ordering cone C focus on a comparison in which the strategies of all other players have been “fixed.”

We can now present the main result of this work—the equivalence between the set of all Nash equilibria for the N-player game (1) and the Pareto minimizers of the vector optimization problem (5).

Theorem 2.6.

Consider the shared-constraint noncooperative game (1). The strategy $x^{*}$ is a Nash equilibrium if and only if it is a minimizer of (5), that is,

$$\mathrm{NE}(f,\mathbb{X})=C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\},$$

where the ordering cone C is defined in (6).

To prove the theorem, we will need the following lemma. Recall from Definition 2.3 that $x^{*}\in C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$ if and only if $(x,f(x)){\ge }_C(x^{*},f(x^{*}))$ for any $x\in \mathbb{X}$ such that $(x,f(x)){\le }_C(x^{*},f(x^{*}))$.

Lemma 2.7.

It holds that $C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}={\cap }_{i=1}^N{C}_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\},$ where C and C_i are as defined in (6) and (7).

Proof.

Let $x^{*}\in C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$ and assume $x^{*}\notin C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$ for some player i. Therefore, by the construction of the C_i minimizers, there exists some $x\in \mathbb{X}$ such that $x_{-i}=x_{-i}^{*}$ with $f_i(x)<f_i(x^{*})$. By construction of the cone C, this implies $(x,f(x)){\le }_C(x^{*},f(x^{*}))$ as well. However, as $x^{*}$ is a C minimizer, it must follow that $(x,f(x)){\ge }_C(x^{*},f(x^{*}))$, that is, there exists some player j such that $x_{-j}=x_{-j}^{*}$ and $f_j(x)\ge f_j(x^{*})$. If $j\ne i$, then $x=x^{*}$ (i.e., $f_i(x)=f_i(x^{*})$); if j = i, then $f_i(x)\ge f_i(x^{*})$. In either case, we recover a contradiction.

Now consider $x^{*}\in {\cap }_{i=1}^N{C}_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$ and assume that $x^{*}\notin C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$, that is, there is an $x\in \mathbb{X}$ with $(x,f(x)){\le }_{C_i}(x^{*},f(x^{*}))$ for some i such that there is no $j=1,\dots ,N$ with $(x,f(x)){\ge }_{C_j}(x^{*},f(x^{*}))$. In particular, $(x,f(x)){\ge }_{C_i}(x^{*},f(x^{*}))$ does not hold, which contradicts $x^{*}\in C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$. □

Proof of Theorem 2.6.

Consider $x^{*}$ to be a Nash equilibrium of the game. By definition of the Nash equilibrium, for any player i, if $x\in \mathbb{X}$ with $x_{-i}=x_{-i}^{*}$, then $f_i(x)\ge f_i(x^{*})$. Therefore, if $(x,f(x)){\le }_C(x^{*},f(x^{*}))$, then $x_{-i}=x_{-i}^{*}$ for some i, and, from being a Nash equilibrium, we know $f_i(x)\ge f_i(x^{*})$, that is, $(x,f(x)){\ge }_C(x^{*},f(x^{*}))$.

Now consider $x^{*}$ to be a minimizer of the vector optimization problem, that is, $x^{*}\in C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$. For each player i, consider $x_{-i}=x_{-i}^{*}$ with $x\in \mathbb{X}$. Then, if $f_i(x)\le f_i(x^{*})$, the minimality of $x^{*}$ and Lemma 2.7 imply $f_i(x)\ge f_i(x^{*})$. This is the definition of the Nash equilibrium; that is, for every player i, $(x_i,x_{-i}^{*})\in \mathbb{X}$ implies $f_i(x_i,x_{-i}^{*})\ge f_i(x^{*})$. □

The following corollary is immediate and shows that $x^{*}$ is a Nash equilibrium if and only if it is a minimizer with respect to C_i for each player i. We wish to highlight this result, as it can be directly expanded to generalized games; see Section 3.1. Additionally, this construction is useful in the subsequent examples, as each of these cones C_i is convex in contrast to the full ordering cone C that is nonconvex. This allows for the application of traditional vector optimization algorithms as used, for example, in Examples 3.3 and 4.6 in the more general settings.

Corollary 2.8.

The strategy $x^{*}$ is a Nash equilibrium if and only if $x^{*}\in C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$ for every $i=1,\dots ,N$, that is,

$$\mathrm{NE}(f,\mathbb{X})={\displaystyle \underset{i=1}{\overset{N}{\cap }}{C}_i}\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}.$$

Proof.

This follows immediately by Theorem 2.6 and Lemma 2.7. □

Remark 2.9.

As will be made explicit in Examples 2.10 and 2.11, the minimizers $C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$ with respect to player i’s ordering cone C_i exactly coincide with the graph of player i’s best response function $B_i:{\prod }_{j\ne i}{\mathcal{X}}_j\to 2^{{\mathcal{X}}_i}$:

$$\mathrm{graph}{B}_i≔\left\{x^{*}\in \mathbb{X}|x_i^{*}\in \underset{x_i\in {\mathcal{X}}_i}{\text{arg}\hspace{0.17em}\text{min}}\{f_i(x_i,x_{-i}^{*})|(x_i,x_{-i}^{*})\in \mathbb{X}\}\right\}.$$

As such, the result presented in Corollary 2.8 can be reformulated as the well-known characterization (see, e.g., Beck and Stein 2023)

$$\mathrm{NE}(f,\mathbb{X})={\displaystyle \underset{i=1}{\overset{N}{\cap }}\mathrm{graph}\hspace{0.17em}}{B}_i,$$

but it now also allows one to compute $\mathrm{graph}{B}_i$ via vector optimization techniques. In this way, Corollary 2.8 can also be seen through the lens of finding a fixed point of the best response functions $x^{*}\in B(x^{*})≔(B_1(x_{-1}^{*}),\dots ,B_N(x_{-N}^{*}))$.

Furthermore, for a differentiable and convex game (i.e., f_i is differentiable and convex for every player i and $\mathbb{X}$ is convex), the first-order sufficient condition of the vector optimization problem $C_i\text{-min}\{(x,f(x))|x\in \mathbb{X}\}$ is equivalent to the first-order sufficient condition for the best response function for player i. That is, by modification of theorem 12.3.1 of Khan et al. (2015) (to account for the possibility that $C_i\cap (-C_i)\supseteq \{0\}$) and setting $g(x)≔(x,f(x))$,

$$D(g+C_i)(x^{*},g(x^{*}))(x-x^{*})\cap -C_i\subseteq C_i\forall x\in \mathbb{X},$$

where $D(g+C_i)(x^{*},g(x^{*}))(\overline{x})≔\{y\in {\mathcal{Y}}_i|\exists t_n\searrow 0,\hspace{0.17em}(x_n,y_n)\to (\overline{x},y):\hspace{0.17em}g(x^{*})+t_n{y}_n\in g(x^{*}+t_n{x}_n)+C_i\}$ is the contingent derivative of the upper image of g at $(x^{*},g(x^{*}))$, that is, the mapping whose graph is the cone tangent to the graph of the upper image of g at $(x^{*},g(x^{*}))$. This first-order condition is satisfied if and only if ${\nabla }_{x_i}{f}_i{(x^{*})}^{\top }(x_i-x_i^{*})\ge 0$ for every $x_i\in {\mathcal{X}}_i$ such that $(x_i,x_{-i}^{*})\in \mathbb{X}$. This follows from the particular structure of the cone C_i and properties of the contingent derivative. We note that such results can be compared with, for example, the (quasi-)variational inequality sufficient condition for Nash games presented in, for example, Harker (1991) and Facchinei et al. (2007).

2.3. Examples

We will now illustrate the characterization of the set of Nash equilibria as the intersection of minimizers of N vector optimization problems given in Corollary 2.8 on two examples. We chose two simple examples in which the set of Nash equilibria can easily be deduced and the set of minimizers of the vector optimization problems can be easily depicted. More complex examples, where the characterization of the set of Nash equilibria as the intersection of minimizers of N vector optimization problems is computationally exploited, will be presented in the more general settings of Sections 3 and 4.

Example 2.10.

Consider the zero-sum two-player game of odds and evens. In this game, both players must choose to say zero or one simultaneously. If the sum is even, then player 1 receives a payout of one from player 2, and vice versa if the sum is odd. For this game, we will consider the mixed strategies so that player 1 says one with probability $x_1\in [0,1]$, and similarly for player 2 with probability $x_2\in [0,1]$. The cost functions $f_1:{\mathbb{R}}^2\to \mathbb{R}$ and $f_2:{\mathbb{R}}^2\to \mathbb{R}$, providing the expected losses of each player, are given by

$$\begin{array}{ll}{f}_1(x)\hfill & =-x_1{x}_2-(1-x_1)(1-x_2)+x_1(1-x_2)+(1-x_1)x_2=-1+2x_1+2x_2-4x_1{x}_2,\hfill \\ f_2(x)\hfill & =x_1{x}_2+(1-x_1)(1-x_2)-x_1(1-x_2)-(1-x_1)x_2=1-2x_1-2x_2+4x_1{x}_2.\hfill \end{array}$$

As the strategies consist of choosing the probabilities x_i, the shared constraint set is $\mathbb{X}≔{[0,1]}^2$ with real-valued strategies ${\mathcal{X}}_1={\mathcal{X}}_2=\mathbb{R}$. The cones C and C_i are given as in (8) with $\mathcal{Z}={\mathbb{R}}^4$. Note that because the objective functions are not convex, the subproblems $C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$, despite having a convex ordering cone C_i for i = 1, 2, are not convex vector optimization problems. However, as they are easy to solve, one obtains that the set of Pareto-optimal points of problem $C_1\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}\subseteq {\mathbb{R}}^2$, also depicted in Figure 1(a), is given by

$$C_1\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}=\left\{(0,x_2)|x_2\in [0,0.5)\right\}\cup \left\{(x_1,0.5)|x_1\in [0,1]\right\}\cup \left\{(1,x_2)|x_2\in (0.5,1]\right\}.$$

Similarly, the set of Pareto-optimal points of problem $C_2\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$, which is depicted in Figure 1(b), is given by

$$C_2\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}=\left\{(x_1,1)|x_1\in [0,0.5)\right\}\cup \left\{(0.5,x_2)|x_2\in [0,1]\right\}\cup \left\{(x_1,0)|x_1\in (0.5,1]\right\}.$$

From this we find that the intersection of these two sets of Pareto-optimal points, and thus, by Corollary 2.8, the set of Nash equilibria as well as the set of Pareto-optimal points of $C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$, is given by

$$\mathrm{NE}(f,\mathbb{X})={\displaystyle \underset{i=1}{\overset{2}{\cap }}{C}_i}\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}=\{(0.5,0.5)\}.$$

Thus, in this example, there is a unique Nash equilibrium, and this equilibrium consists of the optimal strategy for both players to say zero or one randomly with probability 0.5. This solution can be verified against the minimax approach pioneered from von Neumann (1928), as this is a two-player zero-sum finite game.

Recall from Remark 2.9 that the Pareto-optimal points $C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$ provide the graph of the best response function for player i. This can be seen directly in Figure 1(a) and (b).

Example 2.11.

We now consider a modification to the zero-sum game presented in Example 2.10 to make it a general-sum game and such that the set of Nash equilibria will no longer be a singleton. Specifically, player 1 is exactly as in Example 2.10, whereas player 2 has the new cost function so that she is penalized for diverging in her strategy from player 1. Mathematically, this is encoded in the game with cost functions

$$f_1(x)=-1+2x_1+2x_2-4x_1{x}_2,\hspace{1em}\hspace{1em}{f}_2(x)=|x_1-x_2|$$

and constraint set $\mathbb{X}={[0,1]}^2$ with real-valued strategies ${\mathcal{X}}_1={\mathcal{X}}_2=\mathbb{R}$. The cones $C,C_i$, and space $\mathcal{Z}$ are as in Example 2.10 above. The set $C_1\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$ of the (nonconvex) first problem is exactly as in Example 2.10. The set of minimizers of the (C₂-convex) second problem is

$$C_2\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}=\{(x,x)|x\in [0,1]\}.$$

Both are depicted in Figure 2. Their intersection is, by Corollary 2.8, the set of Nash equilibria

$$\mathrm{NE}(f,\mathbb{X})={\displaystyle \underset{i=1}{\overset{2}{\cap }}{C}_i}\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}=\{(0,0),(0.5,0.5),(1,1)\}.$$

By Theorem 2.6 or Lemma 2.7, this also coincides with the set of Pareto-optimal points of the vector optimization problem $C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$. Thus, this Nash game has three equilibria, which can also be seen as the three intersection points marked in black in Figure 2.

3. Generalized Nash Games as Vector Optimization

In this section, we consider generalized Nash games, that is, where we do not assume shared constraints as in Section 2. In Section 3.1, the set of generalized Nash equilibria is shown to coincide with the intersection of Pareto-optimal points of N vector optimization problems. In Section 3.2, a relationship between generalized and shared-constraint games constructed from the individual constraints is deduced. In particular, in Theorem 3.6 and Corollary 3.8, a superset and a subset of the set of generalized Nash equilibria are derived based on Pareto-optimal points of certain vector optimization problems corresponding to these shared-constraint games. We illustrate these results with two examples that we study in both sections.

3.1. Characterization of Generalized Nash Equilibria

Within this section, we study generalized Nash games, that is, N-player noncooperative games without the requirement that the constraint sets for all players coincide. That is, each player i has a constraint set ${\mathbb{X}}_i\subseteq {\prod }_{j=1}^N{\mathcal{X}}_j$ on the joint strategy of all players. With this modification, a generalized Nash game is one in which, given all other players fix their strategies $x_{-i}^{*}\in {\prod }_{j\ne i}{\mathcal{X}}_j$, player i seeks to optimize

This construction leads to an updated definition of a Nash equilibrium.

Definition 3.1.

Consider the generalized game with N players described by (10); that is, player i has strategies in the linear space ${\mathcal{X}}_i$, cost function $f_i:{\prod }_{j=1}^N{\mathcal{X}}_j\to \mathbb{R}$, and the joint strategies must satisfy the feasibility condition $x\in {\mathbb{X}}_i\subseteq {\prod }_{j=1}^N{\mathcal{X}}_j$. The joint strategy $x^{*}\in {\cap }_{i=1}^N{\mathbb{X}}_i$ is called a (generalized) Nash equilibrium if, for any player i, $f_i(x_i,x_{-i}^{*})\ge f_i(x^{*})$ for any strategy $x_i\in {\mathcal{X}}_i$ such that $(x_i,x_{-i}^{*})\in {\mathbb{X}}_i$. The set of all Nash equilibria will be denoted by $\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)$.

Note again, that the joint strategy $x^{*}\in {\cap }_{i=1}^N{\mathbb{X}}_i$ is called a Nash equilibrium if, for any player i,

$$x_i^{*}\in \underset{x_i\in {\mathcal{X}}_i}{\text{arg}\hspace{0.17em}\text{min}}\{f_i(x_i,x_{-i}^{*})|(x_i,x_{-i}^{*})\in {\mathbb{X}}_i\}.$$(11)

Immediately, we are able to provide the second main result of this paper, which characterizes the set of generalized Nash equilibria as the intersection of N vector optimization problems. The result of Corollary 3.2 can be readily compared with Corollary 2.8 for shared-constraint games.

Corollary 3.2.

Consider the generalized noncooperative game (10). The strategy $x^{*}$ is a Nash equilibrium if and only if $x^{*}\in C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in {\mathbb{X}}_i\}$ for every $i=1,\dots ,N$, that is,

$$\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)={\displaystyle \underset{i=1}{\overset{N}{\cap }}{C}_i}\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in {\mathbb{X}}_i\}.$$

As the proof of Corollary 3.2 follows comparably to that of Theorem 2.6, we omit its proof. Intuitively, this result follows because the set of Nash equilibria are all of the fixed points of the best response functions and, as discussed in Remark 2.9, $C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in {\mathbb{X}}_i\}$ coincides with the graph of player i’s best response function.

The following two examples will illustrate Corollary 3.2. Both examples are two-player games with linear objectives and constraints. This allows us to utilize methods for linear vector optimization to construct the set of optimizers. Details on this are given in Remark 3.5 below. As far as the authors are aware, no prior methods exist that are able to compute the set of all Nash equilibria in these examples.

Example 3.3.

Consider the N = 2-player generalized game with linear objectives and constraints

$$\begin{array}{l}{x}_1^{*}\in \underset{x_1\in {\mathbb{R}}^2}{\text{arg}\hspace{0.17em}\text{max}}\{2x_{11}+x_{12}|(x_1,x_2^{*})\in {\mathbb{X}}_1\},\\ x_2^{*}\in \underset{x_2\in {\mathbb{R}}^2}{\text{arg}\hspace{0.17em}\text{max}}\{2x_{21}+3x_{22}|(x_1^{*},x_2)\in {\mathbb{X}}_2\},\end{array}$$

$${\mathbb{X}}_1=\left\{x\in {\mathbb{R}}^4|\left(\begin{array}{cccc}4& 1& -\frac{16}{3}& -\frac{1}{3}\\ 1& 2& 0& 0\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)\le \left(\begin{array}{c}0\\ 5\end{array}\right),\begin{array}{l}{x}_1\in [0,5]\times [0,2.5],\hfill \\ x_2\in [0,1.5]\times [0,6]\hfill \end{array}\right\},$$(12)

$${\mathbb{X}}_2=\left\{x\in {\mathbb{R}}^4|\left(\begin{array}{cccc}0& 0& 4& 1\\ 15& -10& 1& 2\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)\le \left(\begin{array}{c}6\\ 0\end{array}\right),\begin{array}{l}{x}_1\in [0,5]\times [0,2.5],\hfill \\ x_2\in [0,1.5]\times [0,6]\hfill \end{array}\right\},$$(13)

in which player 1 plays strategy $x_1=(x_{11},x_{12})\in {\mathcal{X}}_1={\mathbb{R}}^2$ and player 2 plays strategy $x_2=(x_{21},x_{22})\in {\mathcal{X}}_2={\mathbb{R}}^2$. Thus, we consider a generalized game (10) with $f_1(x)=-(2x_{11}+x_{12}),\hspace{0.17em}{f}_2(x)=-(2x_{21}+3x_{22})$, and where the constraint sets are given by (12) and (13).

In order to solve for the set of Nash equilibria, we solve (by Corollary 3.2) the corresponding two linear vector optimization problems $C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in {\mathbb{X}}_i\}$ with polyhedral convex cones C_i for i = 1, 2. The intersection of these two sets of Pareto-optimal points, and thus the set of Nash equilibria, is given by

$$\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^2)=\{x^1,\dots ,x^4\}$$

with equilibrium points $x^1=((0,0),(0,0))$, $x^2=((0,2),(0,6))$, $x^3=((1,2),(1,2))$, and $x^4\approx ((1.1876,1.9062),(1.2481,0))$.

The following example shows that the proposed method can also find a set of Nash equilibria consisting of infinitely many equilibria.

Example 3.4.

Consider now the following modification of the N = 2-player game given in Example 3.3:

$$\begin{array}{l}{x}_1^{*}\in \underset{x_1\in {\mathbb{R}}^2}{\text{arg}\hspace{0.17em}\text{max}}\{2x_{11}+x_{12}|(x_1,x_2^{*})\in {\widehat{\mathbb{X}}}_1\},\\ x_2^{*}\in \underset{x_2\in {\mathbb{R}}^2}{\text{arg}\hspace{0.17em}\text{max}}\{2x_{21}+3x_{22}|(x_1^{*},x_2)\in {\widehat{\mathbb{X}}}_2\},\end{array}$$

with ${\widehat{\mathbb{X}}}_1={\mathbb{X}}_1\cap \{x\in {\mathbb{R}}^4|4x_{21}+x_{22}\le 6\}$ and ${\widehat{\mathbb{X}}}_2={\mathbb{X}}_2\cap \{x\in {\mathbb{R}}^4|4x_{11}+x_{12}\le \frac{16}{3}{x}_{21}+\frac{1}{3}{x}_{22}\}$, where ${\mathbb{X}}_1$ and ${\mathbb{X}}_2$ are defined as in (12) and (13). As in Example 3.3, player 1 plays strategy $x_1\in {\mathbb{R}}^2$, and player 2 plays strategy $x_2\in {\mathbb{R}}^2$. The objectives f₁, f₂ and the cones $C,C_1,C_2$ are as in Example 3.3; only the constraint sets ${\widehat{\mathbb{X}}}_i$ are different from Example 3.3.

As with Example 3.3, in order to solve for the set of Nash equilibria, we solve (by Corollary 3.2) the corresponding two linear vector optimization problems $C_i\text{-argmin}\{(x,f(x))|x\in {\widehat{\mathbb{X}}}_i\}$ with polyhedral convex cones C_i for i = 1, 2. The intersection of these two sets of Pareto-optimal points, and thus the set of Nash equilibria, is given by

$$\mathrm{NE}(f,{({\widehat{\mathbb{X}}}_i)}_{i=1}^2)=\{x^1\}\cup P_2\cup P_3\cup \{x^4\},$$

where $P_2=\mathrm{co}\{x^2,x^5\}$ and $P_3=\mathrm{co}\{x^3,x^5\}$ for extremal points $x^1,\dots ,x^4$ as in Example 3.3, and $x^5=((0,2.5)\hspace{0.17em},(0.125,5.5))$. Here, we denote by $\mathrm{co}A$ the convex hull of a set A.

Remark 3.5.

Both Examples 3.3 and 3.4 considered in this section are Nash games with linear objectives and linear constraints with ${\mathcal{X}}_i={\mathbb{R}}^2$. This implies that for each i, all of the considered vector optimization problems $C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in {\mathbb{X}}_i\}$ are linear vector optimization problems. However, the cones C_i are unusual in the sense that they contain lines and have an empty interior. Because of this, standard solvers might not be applied directly. However, these linear vector optimization problems can be transformed into multiobjective linear programs (i.e., into linear vector optimization problems with a natural ordering cone) by multiplying the objective function with the matrix Z_i containing the m_i generating vectors of the positive dual cone of C_i. The particular structure of C_i will always lead to $Z_i^{\top }(x,f(x))=(x_{-i},-x_{-i},f_i(x))$. That is,

$${\mathbb{R}}_{+}^{m_i}\text{-arg}\hspace{0.17em}\text{min}\{(x_{-i},-x_{-i},f_i(x))|x\in {\mathbb{X}}_i\}=C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in {\mathbb{X}}_i\}.$$

(See Sawaragi et al. (1985, lemma 2.3.4) for pointed polyhedral convex cones, though this can be extended to any polyhedral convex cone (by noting that $C_i=\{x|Z_i^{\top }x\ge 0\}$ and therefore $\widehat{y}-y\in C_i$ if and only if $Z_i^{\top }(\widehat{y}-y)\ge 0$).) Note that both of the cones C_i in Examples 3.3 and 3.4 have positive dual cones with m_i = 5 generating vectors. Hence, in this case, this transformation turns a linear vector optimization problem with a six-dimensional image space into a standard multiobjective linear program with a five-dimensional image space (further dimension reduction is discussed in Feinstein et al. 2023), which can be solved, for example, with Armand (1993), Van Tu (2017), and Tohidi and Hassasi (2018). Note that for the results of this paper, the whole set of minimizers, that is, the set of all Pareto-optimal points of the corresponding vector optimization problems/multiobjective linear programs, is needed. This can be seen clearly in Example 3.4, as there are entire line segments that are Nash equilibria. Algorithms such as those in Evans and Steuer (1973), Hamel et al. (2014), and Rudloff et al. (2017) provide only the set of all efficient extreme points of the problems considered here (though this is true only for Hamel et al. (2014) and Rudloff et al. (2017) because of the particular structure of the objective function used here). In contrast, the algorithms of Armand (1993), Van Tu (2017), and Tohidi and Hassasi (2018) provide the set of all Pareto-optimal points, that is, also the efficient faces.

3.2. Relation to Shared-Constraint Games

We continue our study of generalized Nash games (see Definition 3.1) by finding meaningful shared-constraint games that produce a sandwich principle on the set of Nash equilibria. This is in contrast to the characterization of the set of Nash equilibria from Corollary 3.2 in which a set of N vector optimization problems are considered. Though it may seem counterintuitive to consider such a game when Corollary 3.2 already provides a procedure for determining the set of Nash equilibria for the generalized game, we refer the interested reader to Braouezec and Kiani (2023). For instance, consider section 3.1 in Braouezec and Kiani (2023), in which nations participate in a game to determine their pollution levels (e.g., carbon emissions) subject to individual constraints on desired industrial production. Assuming linear objectives, this generalized game can be written as a linear game and thus solved directly using the methodology proposed in Remark 3.5. However, as proved in Braouezec and Kiani (2023, proposition 2), this generalized game may fail to admit any Nash equilibria at all. But enforcing a shared constraint for all nations (e.g., through treaty obligations) can guarantee the existence of a Nash equilibrium and, as proved below in Theorem 3.6 and, independently, in proposition 1 of Braouezec and Kiani (2023), will always admit any generalized equilibrium as a solution as well.

Motivated thusly, we wish to consider shared-constraint games associated with the generalized Nash game $(f,{({\mathbb{X}}_i)}_{i=1}^N)$. As expected from the pollution game of (Braouezec and Kiani 2023, section 3.1), the lack of a shared feasibility constraint in (11) makes it impossible to find an appropriate (meaningful) set $\mathbb{X}$ that would provide an equivalence between the solutions of the generalized Nash game (11) and the single vector optimization problem (5). Instead, for generalized games, we find that particular constructions of the constraint set $\mathbb{X}$ can lead to necessary or sufficient conditions for a Pareto solution to be a generalized Nash equilibrium. This is proved in Theorem 3.6 below. Thus, by solving an appropriate vector optimization problem, one can obtain a superset of the set of all generalized Nash equilibria, whereas by solving a different appropriate vector optimization problem, one can obtain a subset of the set of all generalized Nash equilibria. This will be made precise in the following theorem, which is our third main result of this paper.

Theorem 3.6.

Consider the generalized noncooperative game (10):

1. Let $\overline{\mathbb{X}}\subseteq {\cap }_{i=1}^N{\mathbb{X}}_i$. The strategy $x^{*}\in \overline{\mathbb{X}}$ is a Nash equilibrium only if it is a minimizer of (5) with constraint set $\overline{\mathbb{X}}$, that is,

   $$\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)\cap \{\overline{\mathbb{X}}\}\subseteq C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \overline{\mathbb{X}}\},$$(14)
   with ordering cone C defined as in (6). In particular, if we set $\overline{\mathbb{X}}={\cap }_{i=1}^N{\mathbb{X}}_i$, then every Nash equilibrium is a minimizer of (5) with constraint set $\overline{\mathbb{X}}$, that is,
   $$\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)\subseteq C\text{-arg}\hspace{0.17em}\text{min}\left\{(x,f(x))|x\in {\displaystyle \underset{i=1}{\overset{N}{\cap }}{\mathbb{X}}_i}\right\}.$$(15)

2. Let $\underset{¯}{\mathbb{X}}\supseteq {\cup }_{i=1}^N{\mathbb{X}}_i$. The strategy $x^{*}$ is a Nash equilibrium if it is feasible for the generalized game and a minimizer of (5) with constraint set $\underset{¯}{\mathbb{X}}$ and ordering cone C as defined in (6), that is,

   $$\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)\supseteq \{C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \underset{¯}{\mathbb{X}}\}\}\cap \left\{{\displaystyle \underset{i=1}{\overset{N}{\cap }}{\mathbb{X}}_i}\right\}.$$(16)

Proof.

Recall from Definition 2.3 that $x^{*}\in C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathbb{X}\}$ if and only if $(x,f(x)){\ge }_C(x^{*},f(x^{*}))$, for any $x\in \mathbb{X}$ satisfying $(x,f(x)){\le }_C(x^{*},f(x^{*}))$.

For part 1 of the theorem, consider $x^{*}\in \overline{\mathbb{X}}$ to be a Nash equilibrium of the game. By definition of the Nash equilibrium, for any player i, if $x\in {\mathbb{X}}_i$ with $x_{-i}=x_{-i}^{*}$, then $f_i(x)\ge f_i(x^{*})$. In particular, this is true for $x\in \overline{\mathbb{X}}\subseteq {\mathbb{X}}_i$ as well. Therefore, if $(x,f(x)){\le }_C(x^{*},f(x^{*}))$, then $x_{-i}=x_{-i}^{*}$ for some i for which, from a Nash equilibrium, we know $f_i(x)\ge f_i(x^{*})$, that is, $(x,f(x)){\ge }_C(x^{*},f(x^{*}))$. Therefore (15) trivially follows as $\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)\subseteq {\cap }_{i=1}^N{\mathbb{X}}_i$.

For part 2, consider $x^{*}$ to be a minimizer of the vector optimization problem with constraints $\underset{¯}{\mathbb{X}}$ that is feasible for the original game (i.e., $x^{*}\in {\cap }_{i=1}^N{\mathbb{X}}_i$). By definition of the Pareto minimizers and Lemma 2.7, for any player i, if $x\in \underset{¯}{\mathbb{X}}$ with $x_{-i}=x_{-i}^{*}$, then $f_i(x)\ge f_i(x^{*})$. In particular, this is true for $x\in {\mathbb{X}}_i\subseteq \underset{¯}{\mathbb{X}}$ as well. This immediately implies $x^{*}$ is a Nash equilibrium of the game. □

Remark 3.7.

Within the context of Theorem 3.6, the most useful sets to consider are $\overline{\mathbb{X}}={\cap }_{i=1}^N{\mathbb{X}}_i$ and $\underset{¯}{\mathbb{X}}=\mathrm{cl}\mathrm{co}{\cup }_{i=1}^N{\mathbb{X}}_i$ (i.e., the closed and convex hull of ${\cup }_{i=1}^N{\mathbb{X}}_i$). In particular, if we additionally assume that ${\mathbb{X}}_i$ is closed and convex for every i, then the choice of $\overline{\mathbb{X}}={\cap }_{i=1}^N{\mathbb{X}}_i$ in (14) leads on the one hand to the largest possible set of Nash equilibria in (14) (as $\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)\subseteq {\cap }_{i=1}^N{\mathbb{X}}_i$ ensures $\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)\cap \{\overline{\mathbb{X}}\}=\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)$ for this choice of $\overline{\mathbb{X}}$), and on the other hand to the smallest possible superset in (14) among all closed and convex constraint sets. Similarly, and again assuming that ${\mathbb{X}}_i$ is closed and convex for every i, the choice of $\underset{¯}{\mathbb{X}}=\mathrm{cl}\mathrm{co}{\cup }_{i=1}^N{\mathbb{X}}_i$ in (16) leads to the largest possible subset in (16) among all closed and convex constraint sets.

We will occasionally refer to $C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in {\cap }_{i=1}^N{\mathbb{X}}_i\}$ appearing in (15) as the “intersection game,” and to $C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \mathrm{cl}\mathrm{co}{\cup }_{i=1}^N{\mathbb{X}}_i\}$ appearing in (16) when setting $\underset{¯}{\mathbb{X}}=\mathrm{cl}\mathrm{co}{\cup }_{i=1}^N{\mathbb{X}}_i$ as the “union game,” of the generalized Nash game (10). The names are justified, as the intersection game and the union game are both shared-constraint Nash games by Theorem 2.6. The intersection game as a necessary condition for the generalized Nash equilibrium encoded in (15) is independently presented in a purely game theoretic setting (i.e., without the connection to vector optimization) in Braouezec and Kiani (2023, proposition 1).

By Lemma 2.7, the following corollary is immediate.

Corollary 3.8.

It holds that

$$\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)\subseteq {\displaystyle \underset{i=1}{\overset{N}{\cap }}{C}_i}\text{-arg}\hspace{0.17em}\text{min}\left\{(x,f(x))|x\in {\displaystyle \underset{i=1}{\overset{N}{\cap }}{\mathbb{X}}_i}\right\}.$$(17)

Furthermore, for any choice of $\underset{¯}{\mathbb{X}}\supseteq {\cup }_{i=1}^N{\mathbb{X}}_i$, it holds that

$$\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)\supseteq \left\{{\displaystyle \underset{i=1}{\overset{N}{\cap }}{C}_i}\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \underset{¯}{\mathbb{X}}\}\right\}\cap \left\{{\displaystyle \underset{i=1}{\overset{N}{\cap }}{\mathbb{X}}_i}\right\}.$$

Let us now return to the superset relation (15) in Theorem 3.6 (respectively, relation (17) in Corollary 3.8). We now want to characterize those Pareto points in the superset that are not generalized Nash equilibria. This will provide an economic interpretation for the discrepancy between the set of generalized Nash equilibria and the set of Pareto-optimal points.

Note that, in the generalized Nash game, player i seeks to minimize her cost function f_i, given the strategy $x_{-i}^{*}\in {\prod }_{j\ne i}{\mathcal{X}}_j$ of the other players in (10). Player i takes, however, only her own constraint set ${\mathbb{X}}_i$ into account. So her set of feasible strategies can produce joint strategies $(x_i,x_{-i}^{*})\notin {\mathbb{X}}_j$ for some $j\ne i$. Thus, it can very well happen that

So the setup of a generalized Nash game takes on an egocentric point of view. Player i does not care about the consequences of changing her strategy with respect to feasibility of the others. She cares only about her own feasibility and minimizing her own cost. So the setup of a generalized Nash game excludes possible equilibria, where a player could decrease her cost only by strategies that are not feasible for other players. These excluded points are indeed equilibria, but of a shared-constraint Nash game that coincides with the generalized Nash game but considers in the player’s best response problem only the set of strategies that lead to joint strategies that stay feasible for all. Recall from Theorem 2.6 that the Nash equilibria $\mathrm{NE}(f,{\cap }_{i=1}^N{\mathbb{X}}_i)$ of this shared-constraint game coincide with the set of Pareto-optimal points of the vector optimization problem (5) with constraint set $\mathbb{X}={\cap }_{i=1}^N{\mathbb{X}}_i$ considered in (15), that is,

This explains why the set of Pareto-optimal points in (15) can be larger than the set of generalized Nash equilibria, and it provides an economic interpretation for when this happens.

We wish to conclude this section by illustrating the results relating generalized Nash games to shared-constraint games. In Example 3.9, we will revisit Example 3.3 to show that the superset relation (15) in Theorem 3.6 (respectively, relation (17) in Corollary 3.8) can be strict.

Examples 3.9 and 3.10 also show that the subset relation (16) in Theorem 3.6 (respectively, in Corollary 3.8) can be strict. It can even lead to an empty set on the right-hand side of (16) as demonstrated in Example 3.9. Example 3.10 revisits Example 3.4 and is a modification of Example 3.9, where the subset relation (16) is strict, but does not lead to an empty set.

Example 3.9.

Recall the generalized game from Example 3.3. Let us now consider the intersection game, that is, the vector optimization problem $C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in {\cap }_{i=1}^2{\mathbb{X}}_i\}$ appearing in (15) in Theorem 3.6, where the cone $C\subseteq {\mathbb{R}}^6$ is given as in (9). The Pareto optimizers of this intersection game provide a superset of the Nash equilibria of the generalized game by Theorem 3.6. In order to solve the vector optimization problem with nonconvex ordering cone C, we solve (by Lemma 2.7) the corresponding two linear vector optimization problems with convex ordering cones C_i and take an intersection of their Pareto-optimal points leading to $P^{\cap }=\{x_1\}\cup {\cap }_{k=2}^5{P}_k,$ where P₂, P₃ are as in Example 3.4; $P_4=\mathrm{co}\{x^3,x^6\},\hspace{0.17em}{P}_5=\mathrm{co}\{x^4,x^6\}$ for extremal points $x^1,\dots ,x^4$ are as in Example 3.3; x⁵ is as in Example 3.4; and $x^6=((1.175,1.9125),(1.5,0))$. Condition (18) characterizes exactly those points in the superset $P^{\cap }$ that are not generalized Nash equilibria. Removing those points from $P^{\cap }$ leads to the set of generalized Nash equilibria of this game as already computed in Example 3.3.

For completeness, let us now also consider the union game, that is, the vector optimization problem $C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \underset{¯}{\mathbb{X}}\}$ appearing in the subset relation (16) in Theorem 3.6 for $\underset{¯}{\mathbb{X}}=\mathrm{cl}\mathrm{co}{\cup }_{i=1}^2{\mathbb{X}}_i$. Although the union game has Pareto-optimal points consisting of two efficient faces (a plane and a line) including four extremal points, the intersection with the feasibility condition ${\cap }_{i=1}^2{\mathbb{X}}_i$ in (16) leads to an empty set on the right-hand side of (16) in this example. We wish to highlight that although the union game is a convex, shared-constraint game (and thus existence of a Nash equilibrium is guaranteed as found computationally here; see also theorem 1 of Rosen 1965), the feasibility condition can lead to an empty set of equilibria in the sufficient condition (16).

Example 3.10.

Consider again the modified N = 2-player game given in Example 3.4. Consider first its related union game, that is, problem $C\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in \underset{¯}{\mathbb{X}}\}$ appearing in the subset relation (16) in Theorem 3.6 for $\underset{¯}{\mathbb{X}}=\mathrm{cl}\mathrm{co}{\cup }_{i=1}^2{\widehat{\mathbb{X}}}_i$. This union game has a single line segment minimizer that is also feasible for the generalized game (i.e., an element of ${\cap }_{i=1}^2{\widehat{\mathbb{X}}}_i$) and is given by $P^{\cup }=P_2$, where P₂ is as in Example 3.4, that is, $P_2=\mathrm{co}\{x^2,x^5\}$ for $x^2=((0,2),(0,6))$ and $x^5=((0,2.5),(0.125,5.5))$. Thus, in contrast to Example 3.9, one obtains already a set of Nash equilibria from the union game by applying relation (16) in Theorem 3.6. Thus, $P_2\subseteq \mathrm{NE}(f,{({\widehat{\mathbb{X}}}_i)}_{i=1}^N).$

Note that, as by construction, ${\widehat{\mathbb{X}}}_1\cap {\widehat{\mathbb{X}}}_2={\mathbb{X}}_1\cap {\mathbb{X}}_2$, the corresponding intersection game is identical to that of Example 3.9. Therefore, it has the same set of Pareto-optimal points $P^{\cap }$ providing a superset of the generalized Nash equilibria of this game by (17) in Corollary 3.8.

4. Vector-Valued Nash Games as Vector Optimization

In this section, we consider (generalized) noncooperative games in which the N players have vector-valued payoffs. This extends the settings of Sections 2 and 3 by allowing for the space of costs to be partially ordered. As formalized below, and as stated in, for example, Shapley and Rigby (1959) and Bade (2005), the Nash equilibria in such a setting are w.r.t. Pareto-efficient costs. The problem of finding any of these Nash equilibria is typically extremely challenging and often requires the consideration of an infinite number of scalarized problems (see Corley 1985, Bade 2005; see Remark 4.2). Such problems naturally arise due to incomplete preferences in the costs, for example, costs in multiple assets with transaction costs between these assets.

In Section 4.1, we will present the primary theoretical results of this section extending, for example, Corollary 3.2 to provide Corollary 4.4, which proves that the same characterization of Nash games as Pareto-optimal points of a certain vector optimization problem also holds for vector-valued games. Within this context, we also provide a brief introduction to vector-valued Nash games. In Section 4.2, we will illustrate these results with a numerical example, which also demonstrates the computational advantages of the Pareto reformulation of vector-valued Nash games.

4.1. Characterization of Nash Equilibria for Vector-Valued Games

Within this section, we study vector-valued Nash games, that is, N-player noncooperative games in which the costs are partially ordered. We will present these results in the context of generalized Nash games as in Section 3.

Specifically, each player i has a cost function $f_i:{\prod }_{j=1}^N{\mathcal{X}}_j\to {\mathcal{Y}}_i$ mapping to some partially ordered space ${\mathcal{Y}}_i$ with associated convex ordering cone $K_i\subseteq {\mathcal{Y}}_i$. As in Section 3, each player i also has a constraint set ${\mathbb{X}}_i\subseteq {\prod }_{j=1}^N{\mathcal{X}}_j$ on the joint strategy of all players. With this setup, the Nash game is one in which, given all other players fix their strategies $x_{-i}^{*}\in {\prod }_{j\ne i}{\mathcal{X}}_j$, player i seeks to optimize

Within (19), the minimum is in the sense of Pareto optimality (see Definition 2.3). This construction leads to the notion of the Nash equilibrium for vector-valued games as is provided in, for example, Shapley and Rigby (1959) and Bade (2005). The Nash equilibrium in vector-valued games is also called, for example, the Shapley equilibrium in Hamel and Löhne (2018), the Pareto equilibrium in Voorneveld (1999, chapter 11), and the Pareto Nash equilibrium in De Marco and Morgan (2007).

Definition 4.1.

Consider the generalized vector-valued Nash game with N players described by (19). That is, player i has strategies in the space ${\mathcal{X}}_i$, cost function $f_i:{\prod }_{j=1}^N{\mathcal{X}}_j\to {\mathcal{Y}}_i$ with ordering cone $K_i\subseteq {\mathcal{Y}}_i$, and the joint strategies must satisfy the feasibility condition $x\in {\mathbb{X}}_i\subseteq {\prod }_{i=1}^N{\mathcal{X}}_i$. The joint strategy $x^{*}\in {\cap }_{i=1}^N{\mathbb{X}}_i$ is called a generalized Nash equilibrium for a vector-valued game if, for any player i, $f_i(x_i,x_{-i}^{*}){\ge }_{K_i}{f}_i(x^{*})$ for any $x_i\in {\mathcal{X}}_i$ such that $(x_i,x_{-i}^{*})\in {\mathbb{X}}_i$ and $f_i(x_i,x_{-i}^{*}){\le }_{K_i}{f}_i(x^{*})$. The set of all Nash equilibria will be denoted by $\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)$; we simplify the notation to $\mathrm{NE}(f,\mathbb{X})$ if this is a shared-constraint game (i.e., if $\mathbb{X}={\mathbb{X}}_i$ for every player i as in Section 2).

Note again that the joint strategy $x^{*}\in {\cap }_{i=1}^N{\mathbb{X}}_i$ is called a Nash equilibrium if, for any player i,

$$x_i^{*}\in K_i\text{-}\underset{x_i\in {\mathcal{X}}_i}{\text{arg}\hspace{0.17em}\text{min}}\{f_i(x_i,x_{-i}^{*})|(x_i,x_{-i}^{*})\in {\mathbb{X}}_i\}.$$

Remark 4.2.

Let us shortly review the scalarization techniques used in the literature so far to solve vector-valued Nash games. For that purpose, let us for now assume the following. Let ${\mathcal{Y}}_i$ be a topological space with dual ${\mathcal{Y}}_i^{*}$ and bilinear form $〈·,·〉:{\mathcal{Y}}_i^{*}\times {\mathcal{Y}}_i\to \mathbb{R}$. Let $K_i\subseteq {\mathcal{Y}}_i$ be a closed and convex ordering cone. Furthermore, let $f_i(·,x_{-i}^{*})$ be K_i-convex for every $x_{-i}^{*}\in {\prod }_{j\ne i}{\mathcal{X}}_j$, that is, $f_i(\lambda x_i+(1-\lambda ){\overline{x}}_i,x_{-i}^{*}){\le }_{K_i}\lambda f_i(x_i,x_{-i}^{*})+(1-\lambda )f_i({\overline{x}}_i,x_{-i}^{*})$ for any $\lambda \in [0,1]$ and $x_i,{\overline{x}}_i\in {\mathcal{X}}_i$, and let ${\mathbb{X}}_i$ be a convex set. Then, as discussed in (Jahn 2011, chapter 11.2.1), $x_i^{*}$ solves the player i best response function (19) if and only if there exists some $w_i\in K_i^{+}≔\{k_i^{*}\in {\mathcal{Y}}_i^{*}|〈k_i^{*},k_i〉\ge 0\hspace{0.17em}\forall k_i\in K_i\}$ such that

$$x_i^{*}\in \underset{x_i\in {\mathcal{X}}_i}{\text{arg}\hspace{0.17em}\text{min}}\{〈w_i,f_i(x_i,x_{-i}^{*})〉|(x_i,x_{-i}^{*})\in {\mathbb{X}}_i\}.$$(20)

Equation (20) is often called the linear or weighted-sum scalarization of the vector optimization problem (19). Because of the infinite number of linear scalarizations for a vector optimization problem, the traditional methods for finding Nash equilibria of vector-valued games generally fail. Corley (1985, section 4, p. 498) explicitly discusses “the impossible task of solving all possible scalarizations.”

Remark 4.3.

Note that we recover the typical (scalar-valued) definition for a Nash equilibrium (see Definitions 2.2 and 3.1) if ${\mathcal{Y}}_i=\mathbb{R}$ and $K_i={\mathbb{R}}_{+}$ for every player i. This is because ${\mathbb{R}}_{+}\text{-}{\text{arg}\hspace{0.17em}\text{min}}_{x_i\in {\mathcal{X}}_i}\{f_i(x_i,x_{-i}^{*})|(x_i,x_{-i}^{*})\in {\mathbb{X}}_i\}$ provides the usual definition for the minimizers.

In contrast to the scalarization techniques described in Remark 4.2, we want to relate, similar to the preceding sections for real-valued games, vector-valued Nash games to Pareto-optimal points of certain vector optimization problems. We will see that the additional assumptions stated in Remark 4.2 are not necessary for that. Example 4.6 below will show that the approach proposed here has clear computational advantages for game with linear objectives and constraints.

Consider again the vector optimization problem (5) but with a modification to the ordering cone C that accounts for the more general spaces of costs ${\mathcal{Y}}_i$ with ordering cones K_i. Thus, for a constraint set $\mathbb{X}$, consider the following vector optimization problem and ordering cone:

$$C\text{-min}\{(x,f(x))|x\in \mathbb{X}\},$$(21)

$$C≔\{(x,y)\in {\displaystyle \prod _{i=1}^N{\mathcal{X}}_i}\times {\displaystyle \prod _{i=1}^N{\mathcal{Y}}_i}|\exists i\in \{1,\dots ,N\}:x_{-i}=0_{{\prod }_{j\ne i}{\mathcal{X}}_j},\hspace{0.17em}{y}_i\in K_i\}.$$(22)

Similar to the cone defined in (6), the ordering cone C is nonconvex but can be decomposed into convex cones C_i such that $C={\cup }_{i=1}^N{C}_i$ by defining

$$C_i≔\left({\displaystyle \prod _{j=1}^{i-1}\{0_{{\mathcal{X}}_j}\}}\right)\times {\mathcal{X}}_i\times \left({\displaystyle \prod _{j=i+1}^N\{0_{{\mathcal{X}}_j}\}}\right)\times \left({\displaystyle \prod _{j=1}^{i-1}{\mathcal{Y}}_j}\right)\times K_i\times \left({\displaystyle \prod _{j=i+1}^N{\mathcal{Y}}_j}\right).$$(23)

As in Section 3, if ${\mathbb{X}}_i\ne {\mathbb{X}}_j$ for two players $i\ne j$, then, for vector-valued games, we can consider either a collection of N vector optimization problems to characterize the set of Nash equilibria or consider two specific vector optimization problems to produce a sandwich principle. In fact, in the following corollary—the final main result of this work—we will prove that the relations between the Nash equilibria and Pareto optimizers presented for real-valued games in Corollary 3.2 hold without modification for vector-valued games.

Corollary 4.4.

Consider the generalized vector-valued noncooperative game (19). The strategy $x^{*}$ is a Nash equilibrium if and only if $x^{*}\in C_i\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in {\mathbb{X}}_i\}$ for every $i=1,\dots ,N$, that is,

$$\mathrm{NE}(f,{({\mathbb{X}}_i)}_{i=1}^N)={\displaystyle \underset{i=1}{\overset{N}{\cap }}{C}_i}\text{-arg}\hspace{0.17em}\text{min}\{(x,f(x))|x\in {\mathbb{X}}_i\}.$$

Remark 4.5.

Before continuing, we wish to make a few notes comparing our results for vector-valued games to the more traditional scalar-valued games presented previously:

1. The proof is in total analogy to the proof of Corollary 3.2 by just replacing the cones with the ones defined in (23).

2. Under the shared-constraint setting (i.e., $\mathbb{X}={\mathbb{X}}_i={\mathbb{X}}_j$ for every pair of two players i, j), the set of all Nash equilibria in Corollary 4.4 can be reformulated as the single vector optimization problem (21) through an application of Lemma 2.7. Thus, the obtained result gives a equivalent characterization of the set of all shared-constraint Nash equilibria of a vector-valued game as the Pareto-optimal points of the vector optimization problem (21) with cone C as given in (22), which is in total analogy to the real-valued case of Theorem 2.6.

3. Theorem 3.6 and Corollary 3.8 hold in exactly the same formulation also for vector-valued games, only replacing the cones with the ones defined in (22) and (23).

4.2. Examples

Within this section, we will consider a shared-constraint vector-valued Nash game to illustrate the results derived in Section 4.1, in particular, Corollary 4.4 in the shared-constraint case. As with the examples of Section 3, this example is a two-player game with linear objectives and constraints. As such, we are able to utilize the methods for linear vector optimization to construct the set of optimizers as detailed in Remark 3.5. This methodology is particularly noteworthy because, as far as the authors are aware, all prior works would require the study of an infinite number of scalarizations; see, for example, Bade (2005). As noted in Corley (1985), such an approach is computationally intractable. We refer the interested reader to De Marco and Morgan (2007, p. 171) for a survey of various refinements of the Nash equilibria for vector-valued games that take “into account the methodology of the scalarization which adds to the original problem new endogenous parameters.” As such, as far as the authors are aware, there does not exist any other methodology that computes the set of all Nash equilibria for this vector-valued game.

Example 4.6.

Consider the N = 2 player vector-valued game with shared constraints

$$\begin{array}{l}{x}_1^{*}\in {\mathbb{R}}_{+}^2\text{-}\underset{x_1\in {\mathbb{R}}^2}{\text{arg}\hspace{0.17em}\text{max}}\{{(2x_{11},x_{12})}^{\top }|(x_1,x_2^{*})\in \mathbb{X}\},\\ x_2^{*}\in {\mathbb{R}}_{+}^2\text{-}\underset{x_2\in {\mathbb{R}}^2}{\text{arg}\hspace{0.17em}\text{max}}\{{(2x_{21},3x_{22})}^{\top }|(x_1^{*},x_2)\in \mathbb{X}\},\end{array}$$

in which player 1 plays strategy $x_1=(x_{11},x_{12})\in {\mathcal{X}}_1={\mathbb{R}}^2$, and player 2 plays strategy $x_2=(x_{21},x_{22})\in {\mathcal{X}}_2={\mathbb{R}}^2$. We set the shared constraints $\mathbb{X}$ to be the intersection of the constraints from Example 3.3, that is, $\mathbb{X}={\mathbb{X}}_1\cap {\mathbb{X}}_2$ for ${\mathbb{X}}_1$ and ${\mathbb{X}}_2$ as in (12) and (13). Thus, we consider a vector-valued game (21) with linear objectives $f_1(x)=-{(2x_{11},x_{12})}^{\top },\hspace{0.17em}{f}_2(x)=-{(2x_{21},\hspace{0.17em}3x_{22})}^{\top }$ both ordered by the natural ordering cone, that is, the positive orthant $K_i={\mathbb{R}}_{+}^2$ for i = 1, 2.

Note that the scalarization of this game with fixed weights $w_1={(1,1)}^{\top }$ and $w_2={(1,1)}^{\top }$ coincides with the intersection game of Examples 3.9 and 3.10 (see Remark 4.2). Therefore, $\{x^1\}$ and the sets $P_2,\dots ,P_5$ (described in Examples 3.3, 3.4, and 3.9) must consist of Nash equilibria of this vector-valued game as well. However, as will be found below, these are not the only Nash equilibria for this game, as some equilibria correspond to different weighted-sum scalarizations. By applying Corollary 4.4 under the shared-constraint setting (as discussed in Remark 4.5), we will solve (21) with respect to the nonconvex ordering cone

$$C=({\mathbb{R}}^2\times \{(0,0)\}\times {\mathbb{R}}_{+}^2\times {\mathbb{R}}^2)\cup (\{(0,0)\}\times {\mathbb{R}}^2\times {\mathbb{R}}^2\times {\mathbb{R}}_{+}^2)=C_1\cup C_2\subseteq {\mathbb{R}}^8.$$

We will follow the same algorithmic approach as considered in Remark 3.5 with updated generators Z₁, Z₂ for the positive dual cones of C₁, C₂ respectively. In this example, there are $m_1=m_2=6$ generating vectors for both of these positive dual cones. Thus, instead of considering two vector optimization problems with eight-dimensional image spaces, one can equivalently solve two multiobjective linear programs with six-dimensional image spaces (with further dimension reduction possible as in Feinstein et al. 2023) using, for example, Van Tu (2017).

The set of Nash equilibria using Corollary 4.4 is given by the union

$$\mathrm{NE}(f,\mathbb{X})≔{\mathrm{NE}}_1\cup {\mathrm{NE}}_2\cup {\mathrm{NE}}_3\cup {\mathrm{NE}}_4$$

of the four convex polyhedrons ${\mathrm{NE}}_1=\mathrm{co}\{x^1,\hspace{0.17em}{x}^3,x^4,x^8\},\hspace{0.17em}{\mathrm{NE}}_2=\mathrm{co}\{x^2,x^3,x^5,x^8\}$, ${\mathrm{NE}}_3=\mathrm{co}\{x^3,x^5,x^6,x^7\}$, and ${\mathrm{NE}}_4=\mathrm{co}\{x^3,x^4,x^6\}$ for extremal points $x^1,\dots ,x^6$ as given in the scalar games of Examples 3.3, 3.4, and 3.9 and $x^7=((0,2.5),(1.5,0)),\hspace{0.17em}{x}^8=\left(\left(\frac{8}{55},\frac{78}{55}\right),(0,6)\right)$. As $x^1,\dots ,x^6$ coincide exactly with extremal points found in scalar games of Examples 3.3, 3.4, and 3.9, all those solutions are equilibria w.r.t. the scalarizations $w_1=w_2={(1,1)}^{\top }$. The other two extremal solutions are new to this vector-valued game: x⁷ is an equilibrium w.r.t. the scalarizations $w_1={(0,1)}^{\top }$ and $w_2={(1,0)}^{\top }$; x⁸ is an equilibrium w.r.t. the scalarizations $w_1={(2,1)}^{\top }$ and $w_2={(1,1)}^{\top }$. Note that even though, for example, ${\mathrm{NE}}_4$ has extremal points all with scalarizations $w_1=w_2={(1,1)}^{\top }$, not every point within that polyhedron ${\mathrm{NE}}_4$ is a Nash equilibrium w.r.t. those scalarizations. This can be seen through a comparison of the above representation for the set of equilibria to that given for the intersection game in Examples 3.9 and 3.10; that is, ${\mathrm{NE}}_4\backslash P^{\cap }\ne \varnothing$. This demonstrates a clear computational advantage to considering the vector optimization formulation presented herein over the more traditional scalarization approach because the convex combination of solutions for a fixed scalarization does not necessarily result in another Nash equilibrium with those weights.