* [4] James V. Burke, Adrian S. Lewis, and Michael L. Overton.  A robust gradient sampling algorithm for nonsmooth, nonconvex optimization.  SIAM Journal on Optimization, 15(3):751–779, 2005.
  * [5] Margarida Carvalho, Gabriele Dragotto, Andrea Lodi, and Sriram Sankaranarayanan.  The cut and play algorithm: Computing Nash equilibria via outer approximations, 2021.
  * [6] Margarida Carvalho, Andrea Lodi, and João Pedro Pedroso.  Computing Nash equilibria for integer programming games, 2020.
  * [7] Carlo Cenedese, Michele Cucuzzella, Jacquelien M. A. Scherpen, Sergio Grammatico, and Ming Cao.  Highway traffic control via smart e-mobility – part i: Theory, 2021.
  * [8] Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli.  Extended formulations in combinatorial optimization.  4OR, 8(1):1–48, Mar 2010.
  * [9] G. Debreu.  Representation of a preference ordering by a numerical function.  In R. Thrall, C. Coombs, and R. Davies, editors, Decision Processes, pages 159–175. Wiley, Hoboken, NJ, USA, 1954.
  * [10] Axel Dreves.  Finding all solutions of affine generalized Nash equilibrium problems with one-dimensional strategy sets.  Math. Methods Oper. Res., 80(2):139–159, 2014.
  * [11] Axel Dreves.  Computing all solutions of linear generalized Nash equilibrium problems.  Math. Methods Oper. Res., 85(2):207–221, 2017.
  * [12] Axel Dreves, Francisco Facchinei, Christian Kanzow, and Simone Sagratella.  On the solution of the KKT conditions of generalized Nash equilibrium problems.  SIAM J. Optim., 21(3):1082–1108, 2011.
  * [13] Axel Dreves, Christian Kanzow, and Oliver Stein.  Nonsmooth optimization reformulations of player convex generalized Nash equilibrium problems.  Journal of Global Optimization, 53:1–28, 01 2010.
  * [14] Jack Edmonds and Rick Giles.  A min-max relation for submodular functions on graphs.  In P.L. Hammer, E.L. Johnson, B.H. Korte, and G.L. Nemhauser, editors, Studies in Integer Programming, volume 1 of Annals of Discrete Mathematics, pages 185 – 204. Elsevier, 1977.
  * [15] Filippo Fabiani and Sergio Grammatico.  Multi-vehicle automated driving as a generalized mixed-integer potential game.  IEEE Transactions on Intelligent Transportation Systems, 21(3):1064–1073, 2020.
  * [16] Francisco Facchinei and Christian Kanzow.  Generalized Nash equilibrium problems.  4OR, 5(3):173–210, 2007.
  * [17] Francisco Facchinei and Christian Kanzow.  Generalized Nash equilibrium problems.  Ann. Oper. Res., 175(1):177–211, 2010.
  * [18] Francisco Facchinei and Simone Sagratella.  On the computation of all solutions of jointly convex generalized Nash equilibrium problems.  Optim. Lett., 5(3):531–547, 2011.
  * [19] Eugene Fink and Derick Wood.  Restricted-orientation convexity.  Springer Science & Business Media, 2012.
  * [20] Andreas Fischer, Markus Herrich, and Klaus Schönefeld.  Generalized Nash equilibrium problems - recent advances and challenges.  Pesquisa Operacional, 34:521 – 558, 12 2014.
  * [21] Reiner Horst and Hoang Tuy.  Global optimization - deterministic approaches, 3. Edition.  Springer, 1996.
  * [22] Mustafa R. Kılınç and Nikolaos V. Sahinidis.  Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON.  Optimization Methods and Software, 33(3):540–562, 2018.
  * [23] Matthias Köppe, Christopher Thomas Ryan, and Maurice Queyranne.  Rational generating functions and integer programming games.  Operations Research, 59(6):1445–1460, Dec 2011.
  * [24] Kazuo Murota.  A survey of fundamental operations on discrete convex functions of various kinds, 2019.
  * [25] Hukukane Nikaidô and Kazuo Isoda.  Note on non-cooperative convex games.  Pacific J. Math., 5:807–815, 1955.
  * [26] Thomas Ottmann, Eljas Soisalon-Soininen, and Derick Wood.  On the definition and computation of rectilinear convex hulls.  Information Sciences, 33(3):157–171, 1984.
  * [27] R. Tyrrell Rockafellar.  Convex Analysis.  Princeton Landmarks in Mathematics and Physics. Princeton University Press, 1970.
  * [28] J. Rosen.  Existence and uniqueness of equilibrium points in concave $n$-player games.  Econometrica, 33(3):520–534, 1965.
  * [29] Robert Rosenthal.  A class of games possessing pure-strategy Nash equilibria.  Internat. J. Game Theory, 2:65–67, 1973.
  * [30] Simone Sagratella.  Computing all solutions of Nash equilibrium problems with discrete strategy sets.  SIAM J. Optim., 26(4):2190–2218, 2016.
  * [31] Simone Sagratella.  Algorithms for generalized potential games with mixed-integer variables.  Computational Optimization and Applications, 68:689–717, 2017.
  * [32] Simone Sagratella, Marcel Schmidt, and Nathan Sudermann-Merx.  The noncooperative fixed charge transportation problem.  European Journal of Operational Research, 284, 12 2019.
  * [33] A. Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency.  Springer, Berlin, Germany, 2003.
  * [34] Anna von Heusinger and Christian Kanzow.  Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-Type functions.  Computational Optimization and Applications, 43:353–377, 2009.

## Appendix

##  Appendix A Proof of the Reflexivity in Remark 5

###### Proof.

We start by the following two observations. Firstly, we note that for any pair
$I$ and $I^{\mathrm{conv}}\in\mathcal{I}^{\mathrm{conv}}(I)$ the inclusion
$\mathrm{rdom}X_{i}\subseteq\mathrm{rdom}X_{i}^{\mathrm{conv}}$ is valid for
all $i\in N$. To see this, let $i\in N$ and $x_{-i}\in\mathrm{rdom}X_{i}$ be
arbitrary. By definition, there exists $x_{i}\in\mathbb{R}^{k_{i}}$ with
$x=(x_{i},x_{-i})\in X\big{(}(x_{i},x_{-i})\big{)}$, that is, $x_{j}\in
X_{j}(x_{-j})$ for all $j\in N$. In particular, $x_{-j}\in\mathrm{rdom}X_{j}$
for all $j\in N$. Thus by the definition of a convexified instance, we have
$X_{j}^{\mathrm{conv}}(x_{-j})=\mathrm{conv}(X_{j}(x_{-j}))$ for all $j\in N$
which shows that $x\in X^{\mathrm{conv}}(x)$ and ultimately
$x_{-i}\in\mathrm{rdom}X_{i}^{\mathrm{conv}}$.

Secondly, by the definition of a convexified instance for an
$I^{\mathrm{conv}}\in\mathcal{I}^{\mathrm{conv}}(I)$, we have that
$I^{\mathrm{conv}2}=(N,(X_{i}^{\mathrm{conv}2})_{i\in N},(\varphi_{i})_{i\in
N})\in\mathcal{I}^{\mathrm{conv}}(I^{\mathrm{conv}})$ if and only if for all
$i\in N$ and $x_{-i}\in\mathrm{rdom}X_{i}^{\mathrm{conv}}$:

  1. 1.

$X_{i}^{\mathrm{conv}2}(x_{-i}):=\mathrm{conv}(X_{i}^{\mathrm{conv}}(x_{-i}))$

  2. 2.

$\varphi_{i}(x_{i},x_{-i}):=\varphi_{i}^{x_{-i}}(x_{i})$ for all
$x_{i}\in\mathrm{conv}(X_{i}^{\mathrm{conv}}(x_{-i}))$ where
$\varphi_{i}^{x_{-i}}(\cdot):\mathrm{conv}(X_{i}^{\mathrm{conv}}(x_{-i}))\to\mathbb{R}$
is the convex envelope of
$\phi_{i}(\cdot,x_{-i}):X_{i}^{\mathrm{conv}}(x_{-i})\to\mathbb{R}$,
$x_{i}\mapsto\phi_{i}(x_{i},x_{-i})$.

which become for
$x_{-i}\in\mathrm{rdom}X_{i}\subseteq\mathrm{rdom}X_{i}^{\mathrm{conv}}$:

  1. 1.

$X_{i}^{\mathrm{conv}2}(x_{-i}):=\mathrm{conv}(X_{i}^{\mathrm{conv}}(x_{-i})):=\mathrm{conv}(\mathrm{conv}(X_{i}(x_{-i})))=\mathrm{conv}(X_{i}(x_{-i}))$

  2. 2.

$\varphi_{i}(x_{i},x_{-i}):=\varphi_{i}^{x_{-i}}(x_{i})=\phi_{i}(x_{i},x_{-i}):=\phi_{i}^{x_{-i}}(x_{i})$
for all $x_{i}\in\mathrm{conv}(X_{i}(x_{-i}))$ because of the equality
$\mathrm{conv}(X_{i}^{\mathrm{conv}}(x_{-i}))=\mathrm{conv}(X_{i}(x_{-i}))$
and the fact that the function
$\phi_{i}(\cdot,x_{-i}):X_{i}^{\mathrm{conv}}(x_{-i})\to\mathbb{R}$ is the
_convex_ function
$\phi_{i}^{x_{-i}}:\mathrm{conv}(X_{i}(x_{-i}))\to\mathbb{R}$.

by the definition of of a convexified instance for $I$.

This shows that for any
$I^{\mathrm{conv}2}\in\mathcal{I}^{\mathrm{conv}}(I^{\mathrm{conv}})$ we have
$I^{\mathrm{conv}2}\in\mathcal{I}^{\mathrm{conv}}(I)$ and subsequently that

$\mathcal{I}^{\mathrm{conv}}(I^{\mathrm{conv}})\subseteq\mathcal{I}^{\mathrm{conv}}(I)$

holds. Thus $\subseteq$ in (2) holds and we only have to show $\supseteq$. For
the latter, let $I^{\mathrm{conv}}\in\mathcal{I}^{\mathrm{conv}}(I)$ with
$X_{i}^{\mathrm{conv}}(x_{-i}):=\emptyset$ for all $i\in N$ and
$x_{-i}\notin\mathrm{rdom}X_{i}$. Then
$\mathrm{rdom}X_{i}^{\mathrm{conv}}=\mathrm{rdom}X_{i}$ is valid which shows
together with our second observation that the conditions for a convexified
instance of $I^{\mathrm{conv}}$ coincide with the conditions for a convexified
instance of $I$ and thus
$\mathcal{I}^{\mathrm{conv}}(I^{\mathrm{conv}})=\mathcal{I}^{\mathrm{conv}}(I)$
holds. ∎

##  Appendix B Proof of Theorem 2

In this section we prove the well-known property of convex envelopes stated in
(6).

The fact that the left side can’t be smaller follows by Rockafellar’s
description in (3) of the convex envelope as it yields for an arbitrary
$\varepsilon>0$ and $y_{i}^{\prime}\in\mathrm{conv}(X_{i}(x_{-i}))$ an
$\alpha_{i}\in\Lambda_{k_{i}+1}$ such that
$\phi_{i}(y_{i}^{\prime},x_{-i})\geq\sum_{l=1}^{k_{i}+1}\alpha_{il}\pi_{i}(x_{i}^{l},x_{-i})-\varepsilon$
for some $x_{i}^{l}\in X_{i}(x_{-i}),l\in[k_{i}+1]$ with
$\sum_{l=1}^{k_{i}+1}\alpha_{il}x_{i}^{l}=y_{i}^{\prime}$. Note that
$X_{i}(x_{-i})\neq\emptyset$ as $x_{i}\in X_{i}(x_{-i})$. Since $x_{i}^{l}\in
X_{i}(x_{-i})$ for all $l$, we have

$\displaystyle\pi_{i}(x_{i}^{l},x_{-i})\geq\inf_{y_{i}\in
X_{i}(x_{-i})}\pi_{i}(y_{i},x_{-i})$ $\displaystyle\text{ for all
}l=1,\ldots,k_{i}+1.$

Therefore we get

$\displaystyle\phi_{i}(y_{i}^{\prime},x_{-i})$
$\displaystyle\geq\sum_{l=1}^{k_{i}+1}\alpha_{il}\pi_{i}(x_{i}^{l},x_{-i})-\varepsilon\geq\sum_{l=1}^{k_{i}+1}\alpha_{il}\inf_{y_{i}\in
X_{i}(x_{-i})}\pi_{i}(y_{i},x_{-i})-\varepsilon$
$\displaystyle=\left(\inf_{y_{i}\in
X_{i}(x_{-i})}\pi_{i}(y_{i},x_{-i})\right)\cdot\sum_{l=1}^{k_{i}+1}\alpha_{il}-\varepsilon=\inf_{y_{i}\in
X_{i}(x_{-i})}\pi_{i}(y_{i},x_{-i})-\varepsilon$

where the last equality follows from the fact that
$\alpha_{i}\in\Lambda_{k_{i}+1}$. Since
$y_{i}^{\prime}\in\mathrm{conv}(X_{i}(x_{-i}))$ and $\varepsilon>0$ were
arbitrary, we arrive at

$\displaystyle\inf_{y_{i}\in\mathrm{conv}(X_{i}(x_{-i}))}\phi_{i}(y_{i},x_{-i})\geq\inf_{y_{i}\in
X_{i}(x_{-i})}\pi_{i}(y_{i},x_{-i})$

To see that $\leq$ holds, we use the fact that for every $y_{i}\in
X_{i}(x_{-i})$ the inequality
$\phi_{i}(y_{i},x_{-i})\leq\pi_{i}(y_{i},x_{-i})$ is true since
$\phi_{i}(\cdot,x_{-i})$ is the convex envelope of $\pi_{i}(\cdot,x_{-i})$ due
to $x_{-i}\in\mathrm{rdom}X_{i}$. Keeping in mind that
$X_{i}(x_{-i})\subseteq\mathrm{conv}(X_{i}(x_{-i}))$ we conclude:

$\displaystyle\inf_{y_{i}\in\mathrm{conv}(X_{i}(x_{-i}))}\phi_{i}(y_{i},x_{-i})\leq\inf_{y_{i}\in
X_{i}(x_{-i})}\phi_{i}(y_{i},x_{-i})\leq\inf_{y_{i}\in
X_{i}(x_{-i})}\pi_{i}(y_{i},x_{-i}).$

Therefore the equality in (6) holds.

##  Appendix C Proof of Lemma 1

###### Proof.

We first show that the set of $\mathcal{O}$-lines is given by

$\displaystyle\mathcal{O}\text{-lines}=\Big{\\{}\\{\lambda\cdot(\tilde{x}_{i},0_{-i})+x\in\mathbb{R}^{k}\mid\lambda\in\mathbb{R}\\}\mid
i\in N,\tilde{x}_{i}\in\mathbb{R}^{k_{i}},x\in\mathbb{R}^{k}\Big{\\}}$ (34)

where $0_{-i}\in\mathbb{R}^{k_{-i}}$ denotes the vector only consisting of
zeros. For the inclusion $\supseteq$, let $i\in N$ and
$\tilde{x}_{i}\in\mathbb{R}^{k_{i}}$ be arbitrary. Let
$A\in\mathbb{R}^{k_{i}-1\times k_{i}}$ be a matrix with
$\ker(A)=\\{\lambda\tilde{x}_{i}\mid\lambda\in\mathbb{R}\\}$ and denote by
$A_{j}$ the $j$-th row (interpreted as a column vector). Then the hyperplanes
of the form
$\\{x\in\mathbb{R}^{k}\mid(A_{j},0_{-i})^{\top}x=0\\}\in\mathcal{O}$ for all
$j\in[k_{i}-1]$ are contained in $\mathcal{O}$. Similarly, we have
$\\{x\in\mathbb{R}^{k}\mid e_{lj}^{\top}x=0\\}\in\mathcal{O}$ for all $l\in
N,l\neq i$ and $j\in[k_{l}]$ where $e_{lj}$ denotes the standard basis vector
with a $1$ at the $lj$-th position. Intersecting all these above mentioned
hyperplanes results in

$\displaystyle\left(\quad\bigcap_{\mathclap{j\in[k_{i}-1]}}\\{x\in\mathbb{R}^{k}\mid(A_{j},0_{-i})^{\top}x=0\\}\right)\cap{\hbox{$\left(\vbox
to23.0pt{}\right.\n@space$}}\quad\bigcap_{\mathclap{\begin{subarray}{c}l\in
N,l\neq i\\\ j\in[k_{l}]\end{subarray}}}\\{x\in\mathbb{R}^{k}\mid
e_{lj}^{\top}x=0\\}{\hbox{$\left)\vbox
to23.0pt{}\right.\n@space$}}=\\{\lambda(\tilde{x}_{i},0_{-i})\in\mathbb{R}^{k}\mid\lambda\in\mathbb{R}\\}$

which shows $\supseteq$ in (34) as $\mathcal{O}$-lines are lines that are
parallel to some line constructible as the intersection of hyperplanes in
$\mathcal{O}$.

In order to show $\subseteq$ in (34), let
$\bigcap_{s\in[L]}\mathcal{H}_{s}=\\{\lambda\tilde{x}\in\mathbb{R}^{k}\mid\lambda\in\mathbb{R}\\}$
for some hyperplanes $\mathcal{H}_{s}\in\mathcal{O},s\in[L]$ for a
$L\in\mathbb{N}$. By the definition of $\mathcal{O}$, we can represent the
intersection as the linear equation system
$\mathrm{diag}(A_{1},\ldots,A_{n})x=0$ for a block diagonal matrix consisting
of some matrices $A_{i}\in\mathbb{R}^{L_{i}\times k_{i}},i\in N$ with
$\sum_{i\in N}L_{i}=L$. Thus,
$\ker(A_{i})=\\{\lambda\tilde{x}_{i}\mid\lambda\in\mathbb{R}\\}$ needs to hold
for any $i\in N$ which shows that only one $i\in N$ may exist with
$\tilde{x}_{i}\neq 0_{k_{i}}$ as otherwise the intersection of the hyperplanes
$\bigcap_{s\in[L]}\mathcal{H}_{s}$ would not be 1-dimensional. Thus,
$\subseteq$ in (34) holds.

Now we are ready to prove the equivalence of $k$-convexity and
$\mathcal{O}$-convexity. We start with the only if direction. Let
$X\subseteq\mathbb{R}^{k}$ be $k$-convex and let
$\mathcal{L}:=\\{\lambda\cdot(\tilde{x}_{i},0_{-i})+x\in\mathbb{R}^{k}\mid\lambda\in\mathbb{R}\\}$
be an arbitrary $\mathcal{O}$-line. Then $\mathcal{L}\cap
X=\mathcal{L}\cap\mathrm{res}\big{(}X,x_{-i}\big{)}$ which shows by $X$ being
$k$-convex that $\mathcal{L}\cap X$ is a convex set as it is the intersection
of two convex sets and thus is in particular connected.

For the if direction, let $X$ be an $\mathcal{O}$-convex set. Now assume for
contradiction that there exists $x_{-i}\in\mathbb{R}^{k_{-i}}$ such that
$\mathrm{res}\big{(}X,x_{-i}\big{)}$ is not convex, that is, there exist
$x^{1}:=(x_{i}^{1},x_{-i}),x^{2}:=(x_{i}^{2},x_{-i})\in\mathrm{res}\big{(}X,x_{-i}\big{)}$
and $\alpha\in(0,1)$ with $x^{\alpha}:=\alpha
x^{1}+(1-\alpha)x^{2}\notin\mathrm{res}\big{(}X,x_{-i}\big{)}$, i.e.
$x^{\alpha}\notin X$. This contradicts that $X$ is $\mathcal{O}$-convex as
$\mathcal{L}:=\\{\lambda\cdot(x_{i}^{1}-x_{i}^{2},0_{-i})+(x_{i}^{2},x_{-i})\in\mathbb{R}^{k}\mid\lambda\in\mathbb{R}\\}$
is an $\mathcal{O}$-line with $\mathcal{L}\cap X$ not being connected as
$x^{\alpha}\in\mathcal{L}$ and $x^{1},x^{2}\in\mathcal{L}\cap X$ but
$x^{\alpha}\notin X$. ∎