Department of Computer Science, Technion, 3200002,
<EMAIL_ADDRESS>Department of Computer
Science, Technion, 3200002, Israel<EMAIL_ADDRESS>Shaull
Almagor and Shai Guendelman [500]Theory of computation Algorithmic game theory
[500]Theory of computation Automata over infinite objects Bartek Klin,
Sławomir Lasota, and Anca Muscholl 3 33rd International Conference on
Concurrency Theory (CONCUR 2022) CONCUR 2022 CONCUR 2022 September 12–16, 2022
Warsaw, Poland 243 6

# Concurrent Games with Multiple Topologies

Shaull Almagor  Shai Guendelman

###### Abstract

Concurrent multi-player games with $\omega$-regular objectives are a standard
model for systems that consist of several interacting components, each with
its own objective. The standard solution concept for such games is Nash
Equilibrium, which is a “stable” strategy profile for the players.

In many settings, the system is not fully observable by the interacting
components, e.g., due to internal variables. Then, the interaction is modelled
by a partial information game. Unfortunately, the problem of whether a partial
information game has an NE is undecidable for the general case. A particular
setting of partial information arises naturally when processes are assigned
IDs by the system, but these IDs are not known to the processes. Then, the
processes have full information about the state of the system, but are
uncertain of the effect of their actions on the transitions.

We generalize the setting above and introduce Multi-Topology Games (MTGs) –
concurrent games with several possible topologies, where the players do not
know which topology is actually used. We show that extending the concept of NE
to these games can take several forms. To this end, we propose two notions of
NE: Conservative NE, in which a player deviates if she can strictly add
topologies to her winning set, and Greedy NE, where she deviates if she can
win in a previously-losing topology. We study the properties of these NE, and
show that the problem of whether a game admits them is decidable.

###### keywords:

Concurrent games, Nash Equilibrium, Symmetry, Partial information

###### category:

##  1 Introduction

Concurrent multi-player games of infinite duration over graphs are a standard
modelling tool for representing systems that consist of several interacting
components, each having its own objective. Each player in the game corresponds
to a component in the interaction. In each round of the game each of the
player chooses an action and the next state of the game is determined by the
current state and the vector of actions chosen. A strategy for a player is
then a mapping from the history of the game so far to the next action.

A strategy profile (i.e., a tuple of strategies, one for each player) induces
an infinite trace of states, and the goal of each player is to direct the game
into a trace that satisfies her specification. This is modeled by augmenting
the game with $\omega$-regular objectives describing the objectives of the
players.

Unlike traditional zero-sum games, here the objectives of the players do not
necessarily contradict each other. Accordingly, the typical questions about
these games concern their stability. Specifically, the most well-known
stability measure is Nash Equilibrium (NE): an NE is a strategy profile such
that no single player can improve her outcome by unilaterally deviating from
the profile. The problem of whether a multi-player game with $\omega$-regular
objectives has an NE was shown to be decidable in [6].

In many settings, the players only have partial information about the system,
or can view only certain parts of it. This happens when e.g., the system has
private and global variables, and the players model threads that can only view
the global variables. To this end, games with _partial information_ have been
extensively studied in various forms [3, 5, 9, 10]. However, in contrast to
the full-information setting, the problem of deciding whether a partial-
information multi-player game of infinite duration has a Nash equilibrium is
undecidable in the general case where there are 3 or more players [16] or in
the case of stochastic games [26].

In this work, we introduce and study _Multi-Topology Games (MTG)_.
Intuitively, an MTG is a concurrent multi-player game with several transition
functions (i.e., topologies). Then, players are fully aware of the possible
topologies of the game, but do not know which topology they currently play on.
Thus, MTGs capture a restricted form of partial information.

As we now demonstrate, MTGs naturally model the sort of partial information
that arises in the context of _process symmetry_.

######  Example 1.1.

Consider a virtual router with multiple ports. When the router is initialized,
several processes are plugged in. The router assigns each process to a port
id, but the id is not revealed to the processes. Each process attempts to send
messages, and its goal is to have its messages delivered (where some messages
may be dropped due to heavy traffic). While the processes know exactly how the
router works, they do not know which port they are assigned to. Therefore,
their strategies must be oblivious to their port number.

As a concrete example, consider the concurrent game in Figure 1 with players
$\\{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\texttt{blue}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\texttt{red}}\\}$.
When both players know the port assignment, for example,
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\texttt{blue}}\to$Port
$1$ and
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\texttt{red}}\to$Port
$2$, then blue can win by always taking action 1, and red will lose in any
strategy. However, if the port assignment is not known then in order for
either player to win under both port assignments, the players must coordinate
e.g., by taking turns trying to send a message. Thus, a-priori, the game has
two possible topologies: Figure 1(a) and Figure 1(b).

$ready$start$send_{1}$$send_{2}$0010,1101 (a)
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\texttt{blue}}\to$Port
$1$,
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\texttt{red}}\to$Port
$2$.

$ready$start$send_{1}$$send_{2}$0001,1110 (b)
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\texttt{blue}}\to$Port
$2$,
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\texttt{red}}\to$Port
$1$.

Figure 1: Router game from Example 1.1. The players are blue and red, and the
router has two ports $1,2$. In every round each player can try to _send_
(action 1), or _wait_ (action 0). The labels on the edges describe the actions
of the players. The first is the action of the blue player, and the second is
the action of the red player. From $ready$, if only the player in Port
$i\in\\{1,2\\}$ tries to send, the game transitions to $send_{i}$. If both
players try to send, the router prioritizes the request from Port $1$. The
objective of the player Port $i$ is to visit $send_{i}$ infinitely many times.
Note that $send_{i}$ is colored according to the player that tries to reach it
in each port assignment.

These type of settings are commonly referred to as _process symmetry_ [12, 15,
19, 20, 1], and have been studied in several contexts (e.g., model checking
with symmetry reductions). However, to our knowledge this setting has not been
studied in games. In Section 3.1 we demonstrate how MTGs can model the general
setting of process symmetry in games. ∎

In an MTG, a strategy for a player maps sequences of states to an action, and
hence does not depend on a certain topology. Unlike standard games, a strategy
profile in an MTG no longer induces a single trace, but rather a set of
traces, one per topology. Thus, a player can no longer be said to be “winning”
or “losing” in a strategy profile, as this may vary between topologies. In
particular, it is not clear how analogues of Nash equilibrium and social
optimum should be defined.

To this end, we propose two versions of Nash equilibria, corresponding to two
extremities: in a Conservative NE (CNE), a player deviates if she can increase
(w.r.t. containment) the set of topologies she wins in. In a Greedy NE (GNE),
a player deviates if she can win in a currently-losing topology (even at the
cost of losing some of the currently-winning topolgies).

We study the properties of CNE and GNE and compare their strictness, showing
that a GNE is also a CNE, but the converse does not hold. We also compare
their properties to those of the standard notion of NE. Our main technical
contribution is showing that the problem of whether a game has a CNE (resp.
GNE) is decidable.

#### Related Work

A central work concerning NE in concurrent games is [6], where the problem of
deciding whether a concurrent game admits an NE was studied for various
winning conditions. Apart from establishing tight complexity bounds, this work
also introduced the _suspect game_ – a useful technique for reasoning about
concurrent games. Interestingly, the suspect game does not seem to be
adaptable to reason about MTGs, suggesting a fundamental difference between
the models.

Zero-sum concurrent reachability games were studied in [13], where fundamental
techniques for reasoning about them were developed. We remark that the zero-
sum setting is technically very different to ours, due to the non-adversarial
nature of the players.

Concurrent games can be formulated in the turn-based setting using partial
information. The latter were extensively studied, e.g., in [9, 23, 10, 3, 8,
14], typically in the zero-sum setting.

Finally, the work in [3] extends strategy logic [11] with imperfect
information. The authors show that, in general, the model checking problem for
this logic is undecidable, but it is decidable in some special cases.
Unfortunately, these cases do not readily capture MTGs.

#### Paper organization

In Section 2 we present the basic definitions of concurrent games. In Section
3 we formally define MTGs, introduce two notions of equilibria for them, and
study their properties. In Section 4 we give our main technical result,
establishing the decidability of detecting CNE in MTGs. In Section 5 we
establish the decidability of detecting GNE. Finally, in Section 6 we discuss
our results and some extensions, and detail future directions.

##  2 Preliminaries

A _concurrent parity game_ is a tuple
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\delta,(\alpha_{p})_{p\in\mathsf{Pla}}\rangle$
where the components are as follows. $\mathsf{Pla}$ is a finite set of
players, $\mathsf{S}$ is a finite set of states, $s_{0}\in\mathsf{S}$ is an
initial state, $\mathsf{Act}$ is a finite set of actions. The transition
function $\delta:\mathsf{S}\times\mathsf{Act}^{\mathsf{Pla}}\to\mathsf{S}$
maps a state and an _action profile_ (i.e.,
$\boldsymbol{a}=(a_{p})_{p\in\mathsf{Pla}}\in\mathsf{Act}^{\mathsf{Pla}}$) to
the next state. Every player $p\in\mathsf{Pla}$ has a parity objective
$\alpha_{p}\subseteq\mathsf{S}^{\omega}$, as we describe below.

A _play_ of $\mathcal{G}$ is an infinite sequence of states
$\rho=s_{0},s_{1},\ldots\in\mathsf{S}^{\omega}$ such that for every step
$i\in{\rm Nature}$ there exists an action profile $\boldsymbol{a}$ such that
$s_{i+1}=\delta(s_{i},\boldsymbol{a})$. For $k\geq 1$ we denote the length-$k$
prefix of $\rho_{\leq k}=s_{0},\ldots,s_{k-1}\in\mathsf{S}^{+}$. We denote by
$\mathrm{Inf}(\rho)$ the set of states that occur infinitely often in $\rho$.
A _parity objective_ is given by a function
$\Omega:\mathsf{S}\to\\{0,\ldots,d\\}$ for some $d\in{\rm Nature}$. Then,
$\rho$ satisfies the objective if $\min\\{\Omega(s)\mid
s\in\mathrm{Inf}(\rho)\\}$ is even. Thus, the objective $\alpha_{p}$ is the
set of all plays that satisfy the parity function of Player $p$. In the
following, we mostly use the parity function implicitly, and so we do not
include $\Omega$ in the description of $\mathcal{G}$.

The _description size_ of $\mathcal{G}$, denoted $|\mathcal{G}|$ is the number
of bits required to represent the components of $\mathcal{G}$.

######  Remark 2.1 (Game representation).

Note that we assume an explicit representation of the transition function as a
table. In particular, we describe for every state the transition on every
action profile in $\mathsf{Act}^{\mathsf{Pla}}$. Thus, the size of the
transition functions is exponential in $|\mathsf{Pla}|$.

This is in contrast with a more succinct representation, i.e., representing
the transition function as a circuit. We choose this focus to eliminate the
complexity effect of succinct representation.

A _history_ of $\mathcal{G}$ is a finite prefix of a play
$h\in\mathsf{S}^{+}$. A _strategy_ for Player $p$ is a function
$\sigma:\mathsf{S}^{+}\to\mathsf{Act}$ that maps a history to the next action
of Player $p$. A _strategy profile_
$\boldsymbol{\sigma}=(\sigma_{p})_{p\in\mathsf{Pla}}$ is vector of strategies,
one for each player. We denote the set of all strategies by
$\Sigma_{\mathcal{G}}$ and the set of all strategy profiles by
$\Sigma^{\mathsf{Pla}}_{\mathcal{G}}$ (we omit the subscript $\mathcal{G}$
when it is clear from context). A strategy profile $\boldsymbol{\sigma}$ can
be thought as a function that maps histories to action profiles: given a
history $h\in\mathsf{S}^{+}$ we have
$\boldsymbol{\sigma}(h)=(\sigma_{p}(h))_{p\in\mathsf{Pla}}\in\mathsf{Act}^{\mathsf{Pla}}$.

For a strategy profile $\boldsymbol{\sigma}$ we define its _outcome_ to be the
infinite sequence of states (i.e. play) in $\mathcal{G}$ that is taken when
all the players follow their strategies in $\boldsymbol{\sigma}$. Formally,
$\mathrm{out}_{\mathcal{G}}({\boldsymbol{\sigma}})=s_{0}s_{1}\ldots\in\mathsf{S}^{\omega}$
where $s_{0}$ is the initial state, and for every $i\geq 1$ we have
$s_{i}=\delta(s_{i-1},\boldsymbol{\sigma}(s_{0},\ldots,s_{i-1}))$. Consider a
play $\rho\in\mathsf{S}^{\omega}$. The set of _winners_ in $\rho$ is the set
of players whose objectives are met in $\rho$. Formally,
$\mathrm{Win}_{\mathcal{G}}({\rho})=\\{p\in\mathsf{Pla}\mid\rho\in\alpha_{p}\\}\subseteq\mathsf{Pla}$.
The set of winners in a strategy profile $\boldsymbol{\sigma}$ is then
$\mathrm{Win}_{\mathcal{G}}({\boldsymbol{\sigma}})=\mathrm{Win}_{\mathcal{G}}({\mathrm{out}_{\mathcal{G}}({\boldsymbol{\sigma}})})$.
Player $p$ is said to be _losing_ if she is not winning.

######  Remark 2.2 (Action visibility).

Note that strategies are defined to “see” only the history of visited states,
and not the history of actions taken by the other players. This is a standard
and natural assumption [6, 10] for concurrent models. There are, however,
works (e.g., [2]) where players can view the entire action history. The latter
approach is slightly easier to reason about, as players have full information
on the game progress.

A strategy profile $\boldsymbol{\sigma}$ is a _Nash Equilibrium (NE)_ if,
intuitively, no single player can benefit from unilaterally changing her
strategy. Since the objectives in our setting are binary, “benefiting” amounts
to moving from the set of losers to the set of winners. We refer to such a
change as a _beneficial deviation_. Formally, consider a strategy profile
$\boldsymbol{\sigma}$, a player $p\in\mathsf{Pla}$ and a strategy
$\sigma_{p}^{\prime}\in\Sigma_{\mathcal{G}}$ for Player $p$. We denote by
${\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]\in\Sigma^{\mathsf{Pla}}$
the strategy profile obtained from $\boldsymbol{\sigma}$ by replacing
$\sigma_{p}$ with $\sigma^{\prime}_{p}$. Then, $\boldsymbol{\sigma}$ is an NE
if for every player $p\in\mathsf{Pla}$ and every strategy
$\sigma_{p}^{\prime}\in\Sigma_{\mathcal{G}}$ for Player $p$, if
$p\in\mathrm{Win}_{\mathcal{G}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})$
then $p\in\mathrm{Win}_{\mathcal{G}}({\boldsymbol{\sigma}})$. Viewed
contrapositively: if $p$ loses when $\mathcal{G}$ is played with
$\boldsymbol{\sigma}$, then $p$ also loses after changing her strategy.

##  3 Multi-Topology Games

A _multi-topology game (MTG)_ is a tuple
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\mathsf{Top},(\delta_{t})_{t\in\mathsf{Top}},(\alpha_{t,p})_{t\in\mathsf{Top},p\in\mathsf{Pla}}\rangle$
where $\mathsf{Pla}$, $\mathsf{S}$, $s_{0}$, $\mathsf{Act}$, are the same as
in concurrent games. $\mathsf{Top}$ is a finite set of _topologies_ , and for
every $t\in\mathsf{Top}$ we have a transition function
$\delta_{t}:\mathsf{S}\times\mathsf{Act}^{\mathsf{Pla}}\to\mathsf{S}$ and
objective $\alpha_{t,p}\subseteq\mathsf{S}^{\omega}$ for every player
$p\in\mathsf{Pla}$. An MTG can be thought of as a tuple of games over the same
states, players and actions. That is, for $t\in\mathsf{Top}$, we can define
$\mathcal{G}_{t}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\delta_{t},(\alpha_{t,p})_{p\in\mathsf{Pla}}\rangle$
to be the concurrent parity game obtained by fixing the transition function to
$\delta_{t}$ and the objective for Player $p$ to $\alpha_{t,p}$.

Crucially, the players are assumed to have no a-priori information on which
topology is selected when the game is played. This is captured in the
definition of strategies: a strategy for Player $p$ is identical to the
setting of concurrent parity games, i.e.,
$\sigma_{p}:\mathsf{S}^{+}\to\mathsf{Act}$. This lifts to strategy profiles
and outcomes, as per Section 2. In particular, a strategy $\sigma$ in
$\mathcal{G}$ can be applied to $\mathcal{G}_{t}$ for every
$t\in\mathsf{Top}$. Consider a strategy profile
$\boldsymbol{\sigma}\in\Sigma^{\mathsf{Pla}}$. The _winning topologies_ of
Player $p$ is the set of topologies that Player $p$ wins in when $\mathcal{G}$
is played with strategy profile $\boldsymbol{\sigma}$. Formally,
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=\\{t\in\mathsf{Top}\mid
p\in\mathrm{Win}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})\\}$.

###  3.1 Process Symmetry in Concurrent Games

As we discuss in Section 1, a central motivation for MTGs come from settings
where players plug in to the system without knowing their identity. This
setting is commonly referred to as _process symmetry_ [12, 15, 19, 20, 1].
Symmetry in games was studied in [25, 24, 7, 18] for _strategic form games_ ,
which are games with a single turn. In [5, 27], symmetry in concurrent games
was studied by imposing restrictions on the game structure. We consider a
different setting, where processes $1,\ldots,k$ log into a system described as
a concurrent game, but the index of the action controlled by each process is
not revealed to the processes. This setting is naturally modelled as an MTG,
as follows.

Consider a concurrent game
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\delta,(\alpha_{p})_{p\in\mathsf{Pla}}\rangle$
with $k\geq 2$ players, and that $\mathsf{Pla}=\\{1,\ldots,k\\}$. We obtain
from $\mathcal{G}$ an MTG with $k!$ topologies by letting each topology
correspond to a different permutation of the players. Formally, consider a
permutation $\pi\in\mathcal{S}_{k}$, were $\mathcal{S}_{k}$ is the set of
permutations over $\\{1,\ldots,k\\}$. For an action profile
$\boldsymbol{a}\in\mathsf{Act}^{\mathsf{Pla}}$ we define
$\pi(\boldsymbol{a})=(a_{\pi^{-1}(1)},\ldots,a_{\pi^{-1}(k)})$. That is, the
action performed by Player $i$ is taken at index $\pi(i)$. We now obtain the
MTG
$\mathcal{G}^{\prime}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\mathcal{S}_{k},(\delta_{\pi})_{\pi\in\mathcal{S}_{k}},(\alpha_{\pi,p})_{\pi\in\mathcal{S}_{k},p\in\mathsf{Pla}}\rangle$
where $\mathcal{S}_{k}$ is the set of topologies, $\delta_{\pi}$ is obtained
by applying $\pi$ to the action profile of the players, that is, for
$s\in\mathsf{S}$ and $\boldsymbol{a}\in\mathsf{Act}^{\mathsf{Pla}}$ we have
$\delta_{\pi}(s,\boldsymbol{a})=\delta(s,\pi(\boldsymbol{a}))$. Finally, the
objective of Player $p$ is $\alpha_{\pi,p}=\alpha_{\pi(p)}$. Figure 1 is an
example of such game.

###  3.2 Solution Concepts

Recall that in NE, a beneficial deviation moves a player from losing to
winning. In MTGs, however, winning is no longer binary. Indeed, a strategy
profile associates with each player a set of winning topologies. Thus, the
meaning of “beneficial deviation” becomes context dependent. We introduce and
study two notions of equilibria for MTGs that lie on two “extremities”: in the
_conservative_ approach, a deviation is beneficial if it strictly increases
(w.r.t. containment) the set of winning topologies. In the _greedy_ approach,
a deviation is beneficial if a previously-losing topology becomes winning. We
now turn to formally define and demonstrate these notions.

#### Conservative NE

A _conservative NE (CNE)_ is a strategy profile $\boldsymbol{\sigma}$ where no
player can deviate from $\boldsymbol{\sigma}$ and have her winning topologies
be a strict superset111we emphasize that the relation $\subsetneq$ means
“strictly contained”. of her winning topologies when obeying
$\boldsymbol{\sigma}$. Formally, $\boldsymbol{\sigma}\in\Sigma^{\mathsf{Pla}}$
is a CNE if the following holds:

$\begin{split}\forall p\in\mathsf{Pla}\
\forall\sigma_{p}^{\prime}\in\Sigma^{p}_{\mathcal{G}}\ (&(\forall
t\in\mathsf{Top}\
p\in\mathrm{Win}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})\to\mathrm{Win}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}}))\lor\\\
&(\exists t\in\mathsf{Top}\
p\notin\mathrm{Win}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})\land
p\in\mathrm{Win}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})))\end{split}$

Equivalently, this condition can be written in terms of the set of winning
topologies:

$\forall p\in\mathsf{Pla}\
\forall\sigma_{p}^{\prime}\in\Sigma^{p}_{\mathcal{G}}\
\neg(\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})\subsetneq\mathrm{WinTop}_{\mathcal{G}}^{p}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]}))$

We refer to this notion as _conservative_ since a deviating player wants to
conserve her existing winning strategies.

#### Greedy NE

A _greedy NE (GNE)_ is a strategy profile $\boldsymbol{\sigma}$ where no
player can unilaterally deviate and win in a previously-losing topology.
Formally, $\boldsymbol{\sigma}\in\Sigma^{\mathsf{Pla}}$ is a GNE if the
following holds:

$\forall p\in\mathsf{Pla}\
\forall\sigma_{p}^{\prime}\in\Sigma^{p}_{\mathcal{G}}\ \forall
t\in\mathsf{Top}\
(p\in\mathrm{Win}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})\to
p\in\mathrm{Win}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}}))$

Equivalently, this condition can also be written in terms of the set of
winning topologies:

$\forall p\in\mathsf{Pla}\
\forall\sigma_{p}^{\prime}\in\Sigma^{p}_{\mathcal{G}}\
(\mathrm{WinTop}_{\mathcal{G}}^{p}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})\subseteq\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}}))$

The latter formulation shows that in a GNE, for every player and for every
deviation, the player’s winning topologies when deviating are a subset of the
player’s winning topologies when obeying $\boldsymbol{\sigma}$. It refer to
this notion as _greedy_ since it assumes that a player deviates if she
improves her outcome in a single topology, disregarding the outcome in other
topologies.

######  Example 3.1 (CNE and GNE).

Recall the router game from Figure 1. The strategy profile where Player blue
repeatedly plays $(0,0,1,1)^{\omega}$ and red plays $(1,1,0,0)^{\omega}$ is a
CNE, since the set of winning topologies of this profile is $\\{1,2\\}$ for
both players. Thus, no deviation can win in strictly more topologies.

Note that the same strategy profile is also a GNE, since every set of winning
topologies is a subset of $\\{1,2\\}$.

######  Remark 3.2 (Additional notions of NE).

CNE and GNE are based on the $\subseteq$ preorder on the sets of topologies,
$2^{\mathsf{Top}}$. In Section 6 we discuss other notions of NE in MTGs.

###  3.3 Properties of CNE and GNE

We start by examining some properties and relationships between the notions of
CNE and GNE, as well as their relation to standard NE.

Consider an MTG
$\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\mathsf{Top},(\delta_{t})_{t\in\mathsf{Top}},(\alpha_{t,p})_{t\in\mathsf{Top},p\in\mathsf{Pla}}\rangle$.
The following observation is immediate from the definitions of GNE and CNE,
since if there is only a single topology, the MTG collapses into a concurrent
game. If $\mathsf{Top}=\\{t\\}$, i.e. there is only a single topology $t$,
then the definitions of NE in $\mathcal{G}_{t}$ coincides with that of CNE and
of GNE in $\mathcal{G}$.

Next, we observe that GNE is a stricter notion than CNE. Indeed, a beneficial
deviation in the conservative setting (namely increasing the set of winning
topologies) implies a beneficial deviation in the greedy setting (namely
winning in a previously-losing topology). Contrapositively, if there is no
greedy beneficial deviation, there is also no conservative beneficial
deviation. We thus have the following. Let $\mathcal{G}$ be an MTG. If
$\boldsymbol{\sigma}$ is a GNE in $\mathcal{G}$ then $\boldsymbol{\sigma}$ is
a CNE in $\mathcal{G}$. The following example shows that the implication of
Section 3.3 is strict. That is, there are MTGs with a CNE but without a GNE.

$s_{0}$start$s_{1}$$s_{2}$12 (a) $t_{1}$

$s_{0}$start$s_{1}$$s_{2}$21 (b) $t_{2}$

Figure 2: A single player MTG with two topologies, $t_{1}$ and $t_{2}$. In
both topologies, the objective of the player is to reach $s_{1}$ (it is easy
to capture this using a parity objective).

######  Example 3.3 (CNE without GNE).

Consider the single-player game depicted in Figure 2. The outcome of the game
depends only on the first action that the player takes and the topology that
the game is played in. If the player takes action 1, then the set of winning
topologies is $\\{t_{1}\\}$. If the player takes action 2, then the set of
winning topologies is $\\{t_{2}\\}$. Since
$\\{t_{1}\\}\not\subseteq\\{t_{2}\\}$ and
$\\{t_{2}\\}\not\subseteq\\{t_{1}\\}$, there is no GNE in the game, as the
player can switch strategies from $t_{1}$ to $t_{2}$ and vice versa to win in
a previously-losing topology.

However, since there is no strategy for the player such that the set of
winning topologies is $\\{t_{1},t_{2}\\}$ (the only strict superset of
$\\{t_{1}\\}$ and $\\{t_{2}\\}$), then every strategy is a CNE.

######  Remark 3.4 (Best-response dynamics in GNE).

Example 3.3 demonstrates that, in stark contrast to NE, an MTG might not have
a GNE even when there is only a single player. This has to do, in particular,
with the notion of _best-response dynamics_ : in standard games, one can
approach an NE by starting from some profile, and repeatedly letting players
deviate to their best-response strategy, until this process converges. While
this does not always converge, it does so for a large class of games (e.g.,
_finite-potential games_ [22]).

Thus, Example 3.3 shows that best-response does not converge even for a single
player in MTGs, whereas it does converge for a single player both for standard
NE, as well as in CNE for MTGs. Indeed, the best-response of a single player
in the conservative setting will increase her set of winning topologies to the
maximum, and from there she will no longer have incentive to deviate.

Remark 3.4 reflects the intuition that a GNE must be stable in each topology
separately. That is, it captures the notion “NE on all topologies”, in the
following sense. A GNE $\boldsymbol{\sigma}$ is also an NE in
$\mathcal{G}_{t}$ for every $t\in\mathsf{Top}$. Indeed, if
$\boldsymbol{\sigma}$ was not an NE in $\mathcal{G}_{t}$ for some
$t\in\mathsf{Top}$, then a player that deviates from $\boldsymbol{\sigma}$ in
$\mathcal{G}_{t}$ would similarly deviate from $\boldsymbol{\sigma}$ in
$\mathcal{G}$, greedily winning in the previously-losing topology $t$.

In contrast, we now show that CNE is a more intricate notion, and might hold
even when there is no NE in the separate topologies.

$s_{0}$start$s_{1}$$s_{2}$00,1101,10 (a) $t_{1}$

$s_{0}$start$s_{1}$$s_{2}$00,1101,10 (b) $t_{2}$

Figure 3: Symmetric XOR game. The players are blue and red. In topology
$t_{1}$, the objective of blue is to reach $s_{1}$, and the objective of red
is to reach $s_{2}$. In topology $t_{2}$ the objectives of the players are
swapped. The game starts from $s_{0}$. If both players take the same action,
then the game transitions to state $s_{1}$ and gets stuck there. If the
players take different actions then the game transitions to $s_{2}$ and gets
stuck there.

######  Example 3.5 (CNE without NE).

Consider the Symmetric XOR game $\mathcal{G}$ depicted in Figure 3. Note that
neither $\mathcal{G}_{t_{1}}$ nor $\mathcal{G}_{t_{2}}$ have a NE, since if a
strategy for a single player is fixed, the other player can respond to it and
win.

On the other hand, any strategy profile is a CNE, since every player always
wins in exactly one topology. Thus, there is no way for a player to deviate
and get strict superset of winning topologies.

There are MTGs without CNE. For example, every concurrent game $\mathcal{G}$
without an NE can be viewed as an MTG with a single topology $t_{1}$. Since
there is no NE in $\mathcal{G}$, then for every profile $\boldsymbol{\sigma}$
there exists a player $p$ that loses with $\boldsymbol{\sigma}$, which
corresponds to
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=\emptyset$ but $p$
can deviate and win $\mathcal{G}$, which corresponds to
$\mathrm{WinTop}_{\mathcal{G}}^{p}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})=\\{t_{1}\\}$.
Since $\emptyset\subsetneq\\{t_{1}\\}$, then $\boldsymbol{\sigma}$ is not a
CNE.

##  4 Existence of Conservative NE is Decidable

We now turn to our main technical contribution – showing that the existence of
a CNE is a decidable property.

######  Theorem 4.1.

The problem of deciding, given an MTG $\mathcal{G}$, whether there exists a
CNE in $\mathcal{G}$ is in 2-EXPTIME.

The remainder of the section is devoted to proving Theorem 4.1. Our solution
is based on a reduction to the problem of solving a restricted form of
partial-information game. We then employ a result from [10], and obtain the
complexity result by a careful analysis of the construction. The rest of the
section is organized as follows. In Section 4.1 we present the model of
partial-information games and the result of [10]. In Section 4.2 we give an
overview of the reduction and in Section 4.3 we describe and analyze the
reduction from our setting.

###  4.1 Partial-Information Games

Partial-information games (also known as _games with incomplete information_)
are a ubiquitous model for settings where the players cannot fully observe the
state of the game due to e.g., private/hidden variables, unknown parameters or
abstractions of part of the system.

Formally, a _partial-information game_ is a tuple
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\delta,(\mathcal{O}_{p})_{p\in\mathsf{Pla}}\rangle$
where $\mathsf{Pla}$, $\mathsf{S}$, $s_{0}$, $\mathsf{Act}$ and $\delta$ are
the same as in concurrent games. For every player $p\in\mathsf{Pla}$, the set
of _observations_ $\mathcal{O}_{p}\subseteq 2^{\mathsf{S}}$ is a partition of
$\mathsf{S}$. We omit the acceptance condition, and we will include it
explicitly in Theorem 4.2 below.

Intuitively, when the play of $\mathcal{G}$ is at state $s\in\mathsf{S}$,
Player $p$ can only observe $o\in\mathcal{O}_{p}$ such that $s\in o$, and
needs to select an action according to $o$. Thus, we distinguish between
_state histories_ , $\mathsf{S}^{+}$ and _observation histories (of Player
$p$)_, $(\mathcal{O}_{p})^{+}$. For $s\in\mathsf{S}$ we define
$\mathrm{obs}_{p}(s)=o\in\mathcal{O}_{p}$ to be the unique observation of
Player $p$ such that $s\in o$. We extend $\mathrm{obs}_{p}$ to histories: let
$h=s_{0}s_{1}...s_{k}\in\mathsf{S}^{+}$ be a state history, we define
$\mathrm{obs}_{p}(h)=\mathrm{obs}_{p}(s_{0})\mathrm{obs}_{p}(s_{1}),\ldots,\mathrm{obs}_{p}(s_{k})\in(\mathcal{O}_{p})^{+}$
to be the corresponding observation history.

Strategies are _observation based_ , that is, a _strategy_ for Player $p$ is a
function $\sigma_{p}:\mathcal{O}_{p}^{+}\to\mathsf{Act}$. Since different
players may have different observation sets, we denote by
$\Sigma^{p}_{\mathcal{G}}$ the set of all strategies for Player $p$. We denote
by $\Sigma^{\mathsf{Pla}}_{\mathcal{G}}$ the set of all strategy profiles.

Similarly to concurrent games, a strategy profile $\boldsymbol{\sigma}$ can be
thought of as a function that maps histories to action profiles
$\boldsymbol{\sigma}(h)=(\sigma_{p}(\mathrm{obs}_{p}(h)))_{p\in\mathsf{Pla}}\in\mathsf{Act}^{\mathsf{Pla}}$,
and we define
$\mathrm{out}_{\mathcal{G}}({\boldsymbol{\sigma}})\in\mathsf{S}^{\omega}$
similarly to concurrent games.

We say that Player $p\in\mathsf{Pla}$ has _perfect information_ if
$\mathcal{O}_{p}=\\{\\{s\\}\mid s\in\mathsf{S}\\}$. That is, Player $p$ can
observe the exact state of the game. If all players have perfect information
then the game is a _perfect information game_ , and coincides with our
definition of concurrent games. We say that _Player $i$ is less informed than
Player $j$_ if $\mathcal{O}_{j}$ is a refinement of $\mathcal{O}_{i}$. That
is, for every $o_{j}\in\mathcal{O}_{j}$ there exists $o_{i}\in\mathcal{O}_{i}$
such that $o_{j}\subseteq o_{i}$.

Finally, consider an objective $\alpha\subseteq\mathsf{S}^{\omega}$, we say
that $\alpha$ is _visible to Player $p$_ if for every
$\rho,\rho^{\prime}\in\mathsf{S}^{\omega}$ such that
$\mathrm{obs}_{p}(\rho)=\mathrm{obs}_{p}(\rho^{\prime})$ we have that
$\rho\in\alpha$ if and only if $\rho^{\prime}\in\alpha$. That is, the
objective can be defined according to observation sequences rather than plays.

The following theorem is a result from [10] that will serve as the target of
our reduction.

######  Theorem 4.2.

Let
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\delta,(\mathcal{O}_{p})_{p\in\mathsf{Pla}}\rangle$
be a partial information game, with $\mathsf{Pla}=\\{1,2,3\\}$ where Player 1
less informed than Player 2. Let $\alpha\subseteq\mathsf{S}^{\omega}$ be
parity objective over $\mathsf{S}$. The problem of deciding whether
$\exists\sigma_{1}\in\Sigma^{1}_{\mathcal{G}}\
\forall\sigma_{2}\in\Sigma^{2}_{\mathcal{G}}\
\exists\sigma_{3}\in\Sigma^{3}_{\mathcal{G}}\
\mathrm{out}_{\mathcal{G}}({\sigma_{1},\sigma_{2},\sigma_{3}})\in\alpha$ is
2-EXPTIME complete.

###  4.2 Overview of the Reduction

We now turn to describe a reduction from the CNE existence problem to the
setting of Theorem 4.2. We start with a high-level description. Consider an
MTG $\mathcal{G}$. Instead of asking directly whether $\mathcal{G}$ admits a
CNE, we first fix a set of “intended” winning topologies
$T_{p}\subseteq\mathsf{Top}$ for each player $p\in\mathsf{Pla}$. Then, we ask
whether $\mathcal{G}$ admits a CNE $\boldsymbol{\sigma}$ in which
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=T_{p}$ for every
$p\in\mathsf{Pla}$. If we are able to answer the latter problem, we can
iterate over every possible tuple $(T_{p})_{p\in\mathsf{Pla}}$ (or
nondeterministically guess a set) and conclude whether $\mathcal{G}$ admits a
CNE. We remark that this approach is reminiscent of the technique in [6],
where the existence of an NE in a game is decided by first guessing a
“witness” path.

Once the set of intended topologies is fixed, we construct a 3-player partial-
information game whose players are $\mathtt{Eve},\mathtt{Adam}$ and
$\mathtt{Snake}$, with the following roles:

  * •

$\mathtt{Eve}$ controls the coalition of all players, and suggests a strategy
profile $\boldsymbol{\sigma}$ by selecting the actions for all the players at
each step.

  * •

$\mathtt{Adam}$ selects a deviating player $p$, and the deviating strategy
$\sigma^{\prime}_{p}$ for that player. In addition, $\mathtt{Adam}$ selects a
set $T\subseteq\mathsf{Top}$ in which Player $p$ tries to win when playing
$\sigma^{\prime}_{p}$.

  * •

$\mathtt{Snake}$ helps222It is arguable whether this matches the biblical
interpretation. This work makes no theological claims. $\mathtt{Eve}$ by
selecting a concrete topology $t$ from the set $T$ picked by $\mathtt{Adam}$.

The game starts with $\mathtt{Adam}$ and $\mathtt{Snake}$ choosing $p$, $T$
and $t\in T$. It then proceeds with $\mathtt{Eve}$ and $\mathtt{Adam}$
choosing $\boldsymbol{\sigma}$ and $\sigma^{\prime}_{p}$, respectively, while
playing on $\mathcal{G}_{t}$. The observation sets of the players are such
that both $\mathtt{Eve}$ and $\mathtt{Adam}$ can only observe the current
state of the game, so $\mathtt{Eve}$ is ignorant of $p$, $T$ and $t$, and
$\mathtt{Adam}$ is ignorant of $t$ (except knowing that $t\in T$).

The objective of $\mathtt{Eve}$ and $\mathtt{Snake}$ is then composed of three
conditions:

  1. 1.

$\mathtt{Snake}$ must choose a topology $t\in T$.

  2. 2.

If the strategy $\sigma^{\prime}_{p}$ proposed by $\mathtt{Adam}$ does not in
fact deviate from the profile $\boldsymbol{\sigma}$ proposed by $\mathtt{Eve}$
(dubbed “$\mathtt{Adam}$ _obeys_ $\mathtt{Eve}$”), and if $t\in T_{p}$, i.e.,
$p$ was intended to win in $t$, then the outcome must be winning for Player
$p$.

  3. 3.

If $\mathtt{Adam}$ selected $T$ to contain a topology not in $T_{p}$ (i.e.,
Player $p$ potentially tries to win in a superset of $T_{p}$), then the
outcome must be losing for Player $p$.

The overall idea is that if $\mathtt{Eve}$ can find a strategy for all the
players, from which any deviation choice of $\mathtt{Adam}$ can be shown to be
non-beneficial by an appropriate choice by $\mathtt{Snake}$, then there is a
CNE with the intended winning topologies, and vice-versa.

There are, however, some caveats: first, in order to allow $\mathtt{Adam}$ to
choose any set of topologies, the size of the game would be exponential, which
is undesirable. Second, it is not immediate that the conjunction of conditions
above can be captured by a small parity objective (since the parity condition
does not allow conjunction without a change of state space [4]). Third, we
need to separate the cases where $\mathtt{Adam}$ obeys $\mathtt{Eve}$. In the
following we give the complete construction, which overcomes these caveats.

###  4.3 Reduction to Partial Information Game

Consider an MTG
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\mathsf{Top},(\delta_{t})_{t\in\mathsf{Top}},(\alpha_{t,p})_{t\in\mathsf{Top},p\in\mathsf{Pla}}\rangle$.
For every Player $p\in\mathsf{Pla}$, fix $T_{p}\subseteq\mathsf{Top}$ to be
the intended set of winning topologies.

#### Game construction

We construct a 3-player partial-information game $\mathcal{H}$ with the
following components. The players are $\mathtt{Eve}$, $\mathtt{Adam}$ and
$\mathtt{Snake}$. The states of $\mathcal{H}$ are
$Q_{\mathcal{H}}=\\{q_{0}\\}\cup Q$, where $q_{0}$ is a designated initial
state and $Q\subseteq\mathsf{S}\times\mathsf{Pla}\times
2^{\mathsf{Top}}\times\mathsf{Top}\times\\{\mathtt{true},\mathtt{false}\\}$ is
described in the following. A state $(s,p,T,t,b)\in Q$ comprises
$s\in\mathsf{S}$ which tracks the state of $\mathcal{G}$, a player
$p\in\mathsf{Pla}$ that is controlled by $\mathtt{Adam}$, a set
$T\subseteq\mathsf{Top}$ of topologies that $\mathtt{Adam}$ picks,
$t\in\mathsf{Top}$ is a topology picked by $\mathtt{Snake}$ and determines the
topology $\mathcal{G}$ is played in, and a bit
$b\in\\{\mathtt{true},\mathtt{false}\\}$ which tracks whether $\mathtt{Adam}$
obeys $\mathtt{Eve}$.

In order to restrict the state space to a polynomial size in $|\mathcal{G}|$,
i.e. reduce the $2^{\mathsf{Top}}$ component, we define
$\mathcal{T}_{p}=\\{T_{p}\cup\\{t\\}\mid t\in\mathsf{Top}\\}\subseteq
2^{\mathsf{Top}}$ and
$\mathcal{T}=(\bigcup_{p\in\mathsf{Pla}}\mathcal{T}_{p})\cup\\{\\{t\\}\mid
t\in\mathsf{Top}\\}$. Note that
$|\mathcal{T}|\leq(|\mathsf{Pla}|+1)\cdot|\mathsf{Top}|\leq
2\cdot|\mathsf{Pla}|\cdot|\mathsf{Top}|$. We now define
$Q=\mathsf{S}\times\mathsf{Pla}\times\mathcal{T}\times\mathsf{Top}\times\\{\mathtt{true},\mathtt{false}\\}$.
Intuitively, the restriction of $2^{\mathsf{Top}}$ to $\mathcal{T}$ is sound,
since if a Player $p$ is able to deviate and increase her winning topologies
from $T_{p}$ to some $T$, then she can also increase her winning topologies by
just one topology, and thus we can assume $T\in\mathcal{T}_{p}$.

We now turn to define the transitions in $\mathcal{H}$. The actions are
defined implicitly by the transitions.333In the model we describe, actions are
identical for all players. However, the model of [10] allows different actions
as well as enabled and disabled actions in each state, so it is easy to
accommodate our actions. From $q_{0}$, $\mathtt{Adam}$ selects a player
$p\in\mathsf{Pla}$ and a set of topologies $T\in\mathcal{T}_{p}$. As explained
in Section 4.2, $\mathtt{Adam}$ controls Player $p$ and attempts to show that
$p$ wins in $T$. Still in $q_{0}$, $\mathtt{Snake}$ selects a topology
$t\in\mathsf{Top}$ that $\mathcal{G}$ will be played in. Then, $\mathcal{H}$
transitions to state $(s_{0},p,T,t,\mathtt{true})\in Q$.

Henceforth, $p,T$ and $t$ remain fixed throughout the play, and
$\mathtt{Snake}$ has no further effect on the play. From state $(s,p,T,t,b)\in
Q$, $\mathtt{Eve}$ chooses an action profile
$\boldsymbol{a}\in\mathsf{Act}^{\mathsf{Pla}}$ and $\mathtt{Adam}$ selects an
action $a^{\prime}_{p}\in\mathsf{Act}$. Then, the game transitions to state
$(s^{\prime},p,T,t,b^{\prime})\in Q$ such that
$s^{\prime}=\delta_{t}(s,{\boldsymbol{a}}[{p}\mapsto{a^{\prime}_{p}}])$, and
$b^{\prime}=b\land a_{p}=a^{\prime}_{p}$. That is, $\mathtt{Eve}$ chooses an
action profile, $\mathtt{Adam}$ chooses a possible deviation, and the game
proceeds according to $\mathcal{G}_{t}$. If $\mathtt{Adam}$ actually deviates,
the bit $b$ becomes $\mathtt{false}$ and remains so throughout the play.
Adding $\\{\\{t\\}\mid t\in\mathcal{T}\\}$ to $\mathcal{T}$ is to make sure
that if Player $p$ is supposed to win in topology $t$ (that is, $t\in T_{p}$),
then, the profile suggested by $\mathtt{Eve}$ must lead to player $p$ winning
in topology $t$. If not, $\mathtt{Adam}$ can choose $\\{t\\}$ and Player $p$
at the start of the game, and obey $\mathtt{Eve}$, falsifying one of
$\mathtt{Eve}$’s winning conditions ($\psi_{2}$).

Next, we define the observation sets of $\mathcal{H}$. For a state
$q=(s,p,T,t,b)\in Q$ we define the _projection_ of $q$ on $\mathcal{G}$ to be
$\mathrm{proj}(q)=s$. For every state $s\in\mathsf{S}$ of $\mathcal{G}$, let
$o_{s}=\\{q\in Q\mid\mathrm{proj}(q)=s\\}\subseteq Q$. The observation sets in
$\mathcal{H}$ are
$\mathcal{O}_{\mathtt{Adam}}=\mathcal{O}_{\mathtt{Eve}}=\mathcal{O}=\\{\\{q_{0}\\}\\}\cup\\{o_{s}\mid
s\in\mathsf{S}\\}$. That is, $\mathtt{Adam}$ and $\mathtt{Eve}$ can observe
the initial state $q_{0}$, and for every $q\in Q$ they can only observe
$\mathrm{proj}(q)$. $\mathtt{Snake}$ has perfect information.

This completes the construction of the game $\mathcal{H}$ (recall that
$\mathcal{H}$ does not have an objective). We proceed to formalize the
connection between $\mathcal{G}$ and $\mathcal{H}$.

#### Correspondence between $\mathcal{H}$ and $\mathcal{G}$

We lift the definition of projection to plays: for a play
$\rho=q_{0}q_{1}q_{2}...\in q_{0}\cdot Q^{\omega}$ of $\mathcal{H}$ define
$\mathrm{proj}(\rho)=\mathrm{proj}(q_{1})\mathrm{proj}(q_{2})...$ (note that
we skip the initial state $q_{0}$). We also define the predicate
$\mathrm{obey}(\rho)=\bigwedge_{i\geq 1}b_{i}$, where $b_{i}$ is the
$\mathtt{true}/\mathtt{false}$ bit of $q_{i}$. That is, $\mathrm{obey}(\rho)$
is true if and only if $\mathtt{Adam}$ always takes the actions suggested by
$\mathtt{Eve}$. When $\mathrm{obey}(\rho)$ is true, we say that
_$\mathtt{Adam}$ obeys $\mathtt{Eve}$_.

Since the observation of $\mathtt{Eve}$ and $\mathtt{Adam}$ correspond to
states of $\mathcal{G}$, there is a correspondence between plays, observation-
histories and strategies in $\mathcal{H}$ to plays, histories and strategies
in $\mathcal{G}$. We make this precise in the following. Consider the function
$\gamma_{\mathrm{obs}}:\\{q_{0}\\}\cdot\mathcal{O}^{\omega}\to\mathsf{S}^{\omega}$
defined
$\gamma_{\mathrm{obs}}(\\{q_{0}\\},o_{s_{0}},o_{s_{1}},\ldots)=s_{0},s_{1},\ldots$.
Since $o_{s}=\\{q\mid\mathrm{proj}(q)=s\\}$ for every $s\in\mathsf{S}$, we
have that $\gamma_{\mathrm{obs}}$ is a bijection between observation-plays of
$\mathtt{Eve}$ and $\mathtt{Adam}$ in $\mathcal{H}$, and plays of
$\mathcal{G}$. By looking at finite sequences, namely histories, we can refer
to $\gamma_{\mathrm{obs}}$ as a bijection between observation-histories of
$\mathtt{Adam}$ and $\mathtt{Eve}$ in $\mathcal{H}$, and histories in
$\mathcal{G}$. Moreover, since strategies in $\mathcal{H}$ are observation
based, the following functions are also bijective:

  * •

$\gamma_{\mathtt{Eve}}:\Sigma^{\mathtt{Eve}}_{\mathcal{H}}\to\Sigma_{\mathcal{G}}$
defined by
$\gamma_{\mathtt{Eve}}(\sigma_{\mathtt{Eve}})=\sigma_{\mathtt{Eve}}\circ\gamma_{\mathrm{obs}}^{-1}$.

  * •

$\gamma_{\mathtt{Adam}}:\Sigma^{\mathtt{Adam}}_{\mathcal{H}}\to\bigcup_{p\in\mathsf{Pla}}\\{p\\}\times\mathcal{T}_{p}\times\Sigma^{p}_{\mathcal{G}}$
defined
$\gamma_{\mathtt{Adam}}(\sigma_{\mathtt{Adam}})=(p,T,\sigma_{p}^{\prime})$
such that $\sigma_{\mathtt{Adam}}(q_{0})=(p,T)$ are the player and the set of
topologies selected by $\mathtt{Adam}$ in state $q_{0}$, and
$\sigma_{p}^{\prime}=\sigma_{\mathtt{Adam}}\circ\gamma_{\mathrm{obs}}^{-1}$ is
the deviating strategy in $\mathcal{G}$ induced by the deviation proposed in
$\sigma_{\mathtt{Adam}}$ in $\mathcal{H}$.

  * •

$\gamma_{\mathtt{Snake}}:\Sigma^{\mathtt{Snake}}_{\mathcal{H}}\to\mathsf{Top}$
defined by
$\gamma_{\mathtt{Snake}}(\sigma_{\mathtt{Snake}})=\sigma_{\mathtt{Snake}}(q_{0})$
(recall that $\mathtt{Snake}$ only acts in $q_{0}$).

For readability, we omit the the subscript and write $\gamma$ instead of
$\gamma_{\mathrm{obs}},\gamma_{\mathtt{Adam}},\gamma_{\mathtt{Eve}},\gamma_{\mathtt{Snake}}$.
The correct subscript can be resolved from context. Intuitively, $\gamma$ is
the correspondence from strategies/histories/plays in $\mathcal{H}$ to their
counterpart in $\mathcal{G}$.

The connection between strategies and outcomes in $\mathcal{H}$ and
$\mathcal{G}$ is formalized in the following lemma (see Section A.1 for the
proof).

######  Lemma 4.3.

Consider strategies
$\sigma_{\mathtt{Eve}}\in\Sigma^{\mathtt{Eve}}_{\mathcal{H}}$,
$\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$ and
$\sigma_{\mathtt{Snake}}\in\Sigma^{\mathtt{Snake}}_{\mathcal{H}}$. Let
$\boldsymbol{\sigma}=\gamma(\sigma_{\mathtt{Eve}})$,
$(p,T,\sigma_{p}^{\prime})=\gamma(\sigma_{\mathtt{Adam}})$ and
$t=\gamma(\sigma_{\mathtt{Snake}})$. Let
$\rho=\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}},\sigma_{\mathtt{Snake}}})$,
$\pi^{\prime}=\mathrm{out}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})$,
and $\pi=\mathrm{out}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})$. Then
$\mathrm{proj}(\rho)=\pi^{\prime}$. Furthermore, if $\mathtt{Adam}$ obeys
$\mathtt{Eve}$ on $\rho$ then $\mathrm{proj}(\rho)=\pi=\pi^{\prime}$.

#### Objective for $\mathcal{H}$

As sketched in Section 4.2, the objective $\alpha$ in $\mathcal{H}$ is
constructed so that $\mathtt{Eve}$ and $\mathtt{Snake}$ can win if and only if
there is a CNE in $\mathcal{G}$ with winning topologies
$(T_{p})_{p\in\mathsf{Pla}}$.

We define $\alpha$ as a conjunction of three conditions $\alpha=\\{\rho\in
q_{0}\cdot
Q^{\omega}\mid\psi_{1}(\rho)\land\psi_{2}(\rho)\land\psi_{3}(\rho)\\}$, where
the conditions are defined as follows. Consider a play
$\rho=q_{0},(s_{0},p,T,t,b_{0}),(s_{1},p,T,t,b_{1}),\ldots$ of $\mathcal{H}$.

  * •

$\psi_{1}(\rho):=t\in T$. That is, $\psi_{1}$ forces $\mathtt{Snake}$ to
choose a topology from the set of topologies selected by $\mathtt{Adam}$.

  * •

$\psi_{2}(\rho):=(\mathrm{obey}(\rho)\land t\in
T_{p})\to\mathrm{proj}(\rho)\in\alpha_{t,p}$. That is, $\psi_{2}$ is satisfied
if whenever $\mathtt{Adam}$ obeys $\mathtt{Eve}$ then Player $p$ wins in any
topology $t\in T_{p}$ selected by $\mathtt{Snake}$.

  * •

$\psi_{3}(\rho):=T_{p}\subsetneq T\to\mathrm{proj}(\rho)\notin\alpha_{t,p}$.
That is, $\psi_{3}$ is satisfied if whenever $\mathtt{Adam}$ tries to win in a
strict superset of $T_{p}$, then Player $p$ loses in the topology selected by
$\mathtt{Snake}$.

As mentioned in Section 4.2, it is not clear that $\alpha$ can be expressed as
a single parity objective over $Q_{\mathcal{H}}$. Nonetheless, we prove that
this is possible. The key observation is that the “postconditions” of
$\psi_{2}$ and $\psi_{3}$ contradict, hence one of them must hold vacuously.
This allows us to decouple the parity conditions for each of them and obtain a
single parity objective that captures both, as follows.

For each objective $\alpha_{t,p}$ in $\mathcal{G}$ we write
$\alpha_{t,p}=\mathrm{Parity}(\Omega_{t,p})$ such that
$\Omega_{t,p}:\mathsf{S}\to\\{0,\ldots,d\\}$ is the parity ranking function,
where $d\in{\rm Nature}$. We define a new ranking function
$\Omega:Q_{\mathcal{H}}\to\\{0,...,d+1\\}$, and show that
$\alpha=\mathrm{Parity}(\Omega)$.

First, observe that $q_{0}$ occurs only once in each play, so its parity rank
has no effect. We arbitrarily set $\Omega(q_{0})=0$. Let $\rho\in q_{0}\cdot
Q^{\omega}$ be a play of $\mathcal{H}$ and
$(s,p,T,t,b),(s^{\prime},p^{\prime},T^{\prime},t^{\prime},b^{\prime})\in\mathrm{Inf}(\rho)$.
It must be that $p=p^{\prime}$, $T=T^{\prime}$ and $t=t^{\prime}$ since those
are constant throughout the play, and $b=b^{\prime}$ since it is either always
$\mathtt{true}$ or from some point in $\rho$ it turns into $\mathtt{false}$
and stays that way to the rest of the play.

Let $q=(s,p,T,t,b)\in Q$. We define $\Omega(q)$ by cases according to
$p,T,t,b$, and show that in each case, $\rho\in\alpha$ if and only if
$\rho\in\mathrm{Parity}(\Omega)$, concluding that
$\alpha=\mathrm{Parity}(\Omega)$. For a formula of the form
$\psi=\varphi_{1}\to\varphi_{2}$, we refer to $\varphi_{1}$ as the
_precondition_ of $\psi$, and $\varphi_{2}$ as the _postcondition_ of $\psi$.

  * •

$t\notin T$: In this case, if $q\in\mathrm{Inf}(\rho)$ then $\rho$ does not
satisfy $\psi_{1}$, thus, $\rho\notin\alpha$. We set $\Omega(q)=1$ to get
$\rho\notin\mathrm{Parity}(\Omega)$.

  * •

$t\in T$, $b=\mathtt{true}$, $t\in T_{p}$ and $T_{p}\subsetneq T$: In this
case, if $q\in\mathrm{Inf}(\rho)$ then $\rho$ satisfies the preconditions of
both $\psi_{2}$ and $\psi_{3}$, but the postconditions of $\psi_{2}$ and
$\psi_{3}$ contradict, thus, $\rho\notin\alpha$. We set $\Omega(q)=1$ to get
$\rho\notin\mathrm{Parity}(\Omega)$.

  * •

$t\in T$, $b=\mathtt{true}\land t\in T_{p}$ and $\neg(T_{p}\subsetneq T)$: In
this case, if $q\in\mathrm{Inf}(\rho)$, then
$\rho\in\alpha\iff\mathrm{proj}(\rho)\in\alpha_{t,p}$. So we set
$\Omega(q)=\Omega_{t,p}(s)$, to apply the objective $\alpha_{t,p}$ over
$\mathrm{proj}(\rho)$.

  * •

$t\in T$, $\neg(b=\mathtt{true}\land t\in T_{p})$ and $T_{p}\subsetneq T$: In
this case, if $q\in\mathrm{Inf}(\rho)$, then
$\rho\in\alpha\iff\mathrm{proj}(\rho)\notin\alpha_{t,p}$. So we set
$\Omega(q)=\Omega_{t,p}(s)+1$, to apply the complement of the objective
$\alpha_{t,p}$ over $\mathrm{proj}(\rho)$.

  * •

$t\in T$, $\neg(b=\mathtt{true}\land t\in T_{p})$ and $\neg(T_{p}\subsetneq
T)$: In this case, if $q\in\mathrm{Inf}(\rho)$ then $\psi_{2}$ and $\psi_{3}$
are vacuously satisfied, and $\rho\in\alpha$. So we set $\Omega(q)=0$ to get
that $\rho\in\mathrm{Parity}(\Omega)$.

We are now ready to characterize the existence of a CNE in $\mathcal{G}$ by
winning strategies in $\mathcal{H}$.

######  Lemma 4.4.

Consider an MTG
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\mathsf{Top},(\delta_{t})_{t\in\mathsf{Top}},(\alpha_{t,p})_{t\in\mathsf{Top},p\in\mathsf{Pla}}\rangle$.
Let $(T_{p})_{p\in\mathsf{Pla}}$ be sets of topologies for each player and let
$\mathcal{H}$ be the corresponding partial-information game. There exists a
strategy profile $\boldsymbol{\sigma}$ in $\mathcal{G}$ such that
$\boldsymbol{\sigma}$ is a CNE and for every $p\in\mathsf{Pla}$ we have
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=T_{p}$ if and only
if the follwing holds:

$\exists\sigma_{\mathtt{Eve}}\in\Sigma^{\mathtt{Eve}}_{\mathcal{H}}\
\forall\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}\
\exists\sigma_{\mathtt{Snake}}\in\Sigma^{\mathtt{Snake}}_{\mathcal{H}}\
\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}},\sigma_{\mathtt{Snake}}})\in\alpha.$

######  Proof 4.5.

Assume $\boldsymbol{\sigma}$ is a CNE in $\mathcal{G}$ such that for every
$p\in\mathsf{Pla}$, $\mathrm{WinTop}_{\mathcal{G}}^{p}({\sigma})=T_{p}$, and
fix $\sigma_{\mathtt{Eve}}=\gamma^{-1}(\boldsymbol{\sigma})$ to be the
corresponding strategy for $\mathtt{Eve}$ in $\mathcal{H}$. Consider a
strategy $\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$ for
$\mathtt{Adam}$, and let
$(p,T,\sigma_{p}^{\prime})=\gamma(\sigma_{\mathtt{Adam}})$. We show that there
exists a strategy
$\sigma_{\mathtt{Snake}}\in\Sigma^{\mathtt{Snake}}_{\mathcal{H}}$ so that the
outcome satisfies $\alpha$. Recall that a strategy for $\mathtt{Snake}$
amounts to choosing a topology. We divide to cases according to the choice of
$T$ by $\mathtt{Adam}$.

  * •

If $\neg(T_{p}\subsetneq T)$, then $\psi_{3}$ is satisfied vacuously. Choose
$t\in T$ for $\mathtt{Snake}$, then $\psi_{1}$ is satisfied. If
$\mathtt{Adam}$ does not obey $\mathtt{Eve}$ or $t\notin T_{p}$ then
$\psi_{2}$ is vacuously satisfied. Otherwise, if $\mathtt{Adam}$ obeys
$\mathtt{Eve}$ and $t\in T_{p}$, let
$\rho=\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}},\sigma_{\mathtt{Snake}}})$.
In order to show that $\psi_{2}$ is satisfied we need to show that
$\mathrm{proj}(\rho)\in\alpha_{t,p}$. Let
$\pi=\mathrm{out}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})$. Since
$T_{p}=\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})$ and $t\in
T_{p}$ we have that $\pi\in\alpha_{t,p}$. From Lemma 4.3 we have that
$\mathrm{proj}(\rho)=\pi$, so we get that
$\mathrm{proj}(\rho)\in\alpha_{t,p}$, as required.

  * •

If $T_{p}\subsetneq T$, denote
$T^{\prime}=\mathrm{WinTop}_{\mathcal{G}}^{p}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})$.
Since $\boldsymbol{\sigma}$ is a CNE, we have that $\neg(T_{p}\subsetneq
T^{\prime})$, so $T\setminus T^{\prime}\neq\emptyset$, as otherwise we would
have that $T_{p}\subsetneq T\subseteq T^{\prime}$. Choose $t\in T\setminus
T^{\prime}$ for $\mathtt{Snake}$, then $\psi_{1}$ is satisfied. Let
$\rho=\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}},\sigma_{\mathtt{Snake}}})$,
$\pi^{\prime}=\mathrm{out}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})$
and $\pi=\mathrm{out}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})$. From Lemma
4.3 we have that $\mathrm{proj}(\rho)=\pi^{\prime}$ and if $\mathtt{Adam}$
obeys $\mathtt{Eve}$ then we have $\mathrm{proj}(\rho)=\pi=\pi^{\prime}$. Note
that since $t\notin
T^{\prime}=\mathrm{WinTop}_{\mathcal{G}}^{p}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})$
then $\pi^{\prime}\notin\alpha_{t,p}$, so $\psi_{3}$ is satisfied. Finally,
$\psi_{2}$ is satisfied vacuously since we cannot have $t\in T_{p}$ and that
$\mathtt{Adam}$ obeys $\mathtt{Eve}$ simultaneously, as this would yield
$T^{\prime}=T_{p}=\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})$,
but $t\notin T^{\prime}$.

We conclude that in all cases $\rho\in\alpha$, as required.

Conversely, assume that
$\sigma_{\mathtt{Eve}}\in\Sigma^{\mathtt{Eve}}_{\mathcal{H}}$ is such that for
every $\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$ there
exists $\sigma_{\mathtt{Snake}}\in\Sigma^{\mathtt{Snake}}_{\mathcal{H}}$ such
that
$\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}},\sigma_{\mathtt{Snake}}})\in\alpha$.
Let $\boldsymbol{\sigma}=\gamma(\sigma_{\mathtt{Eve}})$. We start by showing
that for every $p\in\mathsf{Pla}$ it holds that
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=T_{p}$. Indeed, let
$p\in\mathsf{Pla}$ and $t\in\mathsf{Top}$.

If $t\in T_{p}$, take
$\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$ that selects
player $p$ and $T=\\{t\\}$, and obeys $\mathtt{Eve}$. The only strategy
$\sigma_{\mathtt{Snake}}$ for $\mathtt{Snake}$ that satisfies $\psi_{1}$ is to
select $t$. Let
$\rho=\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}},\sigma_{\mathtt{Snake}}})$.
From $\psi_{2}$ we get that $\mathrm{proj}(\rho)\in\alpha_{t,p}$, and by Lemma
4.3 we have
$\mathrm{proj}(\rho)=\mathrm{out}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})$.
Thus, $t\in\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})$.

If $t\notin T_{p}$, take
$\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$ that selects
Player $p$ and $T=T_{p}\cup\\{t\\}$, and obeys $\mathtt{Eve}$. Since
$\mathtt{Adam}$ obeys $\mathtt{Eve}$, in order for $\psi_{1}$, $\psi_{2}$ and
$\psi_{3}$ to be satisfied, $\mathtt{Snake}$ must choose $t$, otherwise both
preconditions of $\psi_{2}$ and $\psi_{3}$ hold, which means that in order to
win we must have both $\mathrm{proj}(\rho)\in\alpha_{t,p}$ (by $\psi_{2}$) and
$\mathrm{proj}(\rho)\notin\alpha_{t,p}$ (by $\psi_{3}$), which cannot hold.
Thus, $\mathtt{Snake}$ chooses $t$, and from Lemma 4.3 we have
$\mathrm{proj}(\rho)=\mathrm{out}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})$.
By $\psi_{3}$ we have $\mathrm{proj}(\rho)\notin\alpha_{t,p}$, so
$\mathrm{out}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})\notin\alpha_{t,p}$.
Thus $t\notin\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})$.
Therefore, $\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=T_{p}$.

It remains to show that $\boldsymbol{\sigma}$ is a CNE. Assume by way of
contradiction that there exists a player $p\in\mathsf{Pla}$ with a beneficial
deviation $\sigma_{p}^{\prime}\in\Sigma^{p}_{\mathcal{G}}$. That is,
$T^{\prime}=\mathrm{WinTop}_{\mathcal{G}}^{p}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})$
satisfies $T_{p}\subsetneq T^{\prime}$. We will construct a strategy of
$\mathtt{Adam}$ such that every strategy of $\mathtt{Snake}$ is losing,
thereby reaching a contradiction. Let $T=T_{p}\cup\\{t^{\prime}\\}$ for some
$t^{\prime}\in T\setminus T_{p}$ and fix
$\sigma_{\mathtt{Adam}}=\gamma^{-1}(p,T,\sigma_{p}^{\prime})$. Consider a
strategy $\sigma_{\mathtt{Snake}}$, denote $t=\gamma(\sigma_{\mathtt{Snake}})$
and let
$\rho=\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}},\sigma_{\mathtt{Snake}}})$.
By Lemma 4.3 we have
$\mathrm{proj}(\rho)=\mathrm{out}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})$,
and because $t\in
T\subseteq\mathrm{WinTop}_{\mathcal{G}}^{p}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})$
it holds that $\mathrm{proj}(\rho)\in\alpha_{t,p}$. However, $T_{p}\subsetneq
T$, so $\psi_{3}$ is violated, and $\rho\notin\alpha$, which is a
contradiction. We conclude that $\boldsymbol{\sigma}$ is a CNE.

Using Lemma 4.4 we can decide whether a given MTG $\mathcal{G}$ has a CNE, by
iterating over all possible sets of candidate winning topologies
$(T_{p})_{p\in\mathsf{Pla}}$, and repeatedly applying the reduction, and using
the decision procedure of Theorem 4.2. It remains to analyze the complexity of
this procedure.

To this end, observe that the size of $\mathcal{H}$ is polynomial in the size
of $\mathcal{G}$. Indeed,
$|Q|\leq|\mathsf{S}|\cdot|\mathsf{Pla}|\cdot|\mathcal{T}|\cdot|\mathsf{Top}|\cdot
2$ where $|\mathcal{T}|\leq 2|\mathsf{Pla}||\mathsf{Top}|$. and the
description of the actions is also polynomial in that of $\mathcal{G}$ (note
that $\mathtt{Eve}$ has exponentially more actions than each player in
$\mathcal{G}$, but the overall description of the transition table in
$\mathcal{G}$ is similarly exponential, cf. Remark 2.1).

Finally, by Theorem 4.2, solving $\mathcal{H}$ takes double-exponential time
in $|\mathcal{G}|$, and we have a single-exponential number of iterations, so
the overall complexity remains double-exponential time in $|\mathcal{G}|$.
This completes the proof of Theorem 4.1.

######  Remark 4.6 (Lower bounds and improving the upper bound).

We do not have a lower bound for the 2-EXPTIME complexity of Theorem 4.1.
Indeed, we suspect that this bound can be lowered. This is due in part to the
fact that game $\mathcal{H}$ we construct does not utilize the full scope of
Theorem 4.2 from [10]. Unfortunately, the decision procedure in [10] goes
through three nontrivial reductions, one of which involves Safra’s
determinization, that is notoriously difficult to analyze: The first reduction
[9, 10] transforms the objective to a visible objective for $\mathtt{Adam}$
which involves the determinization of a parity automaton. The second reduction
[10] reduces the three-player partial-information game into a two-player
partial-information game. The third reduction uses the results of [23] to
reduce the two-player partial-information game to a two-player perfect-
information game.

Therefore, it is likely that improving the bound (if indeed possible) will
involve devising an ad-hoc procedure, possibly using some key ideas from [9,
10, 23].

##  5 Existence of Greedy NE is Decidable

We now turn our attention to Greedy NE (GNE). Recall that a greedy beneficial
deviation is one that wins in a previously-losing topology, even at the cost
of losing in previously-winning topologies. That is, given an MTG
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\mathsf{Top},(\delta_{t})_{t\in\mathsf{Top}},(\alpha_{t,p})_{t\in\mathsf{Top},p\in\mathsf{Pla}}\rangle$,
a profile $\boldsymbol{\sigma}\in\Sigma^{\mathsf{Pla}}_{\mathcal{G}}$ is a GNE
if for every $p\in\mathsf{Pla}$, $\sigma_{p}^{\prime}\in\Sigma_{\mathcal{G}}$
and $t\in\mathsf{Top}$, if
$p\in\mathrm{Win}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma^{\prime}_{p}}]})$
then $p\in\mathrm{Win}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})$.

Intuitively, reasoning in the greedy approach is much less delicate than the
conservative approach, since a deviating player need not concern itself with
keeping the current winning topologies. As we show in the following, this
allows for an exponentially faster solution.

######  Theorem 5.1.

The problem of deciding, given an MTG $\mathcal{G}$, whether there exists a
GNE in $\mathcal{G}$ is in EXPTIME.

Similarly to Section 4, our approach is to reduce the problem at hand to
solving a partial-information game. In the greedy setting, however, it
suffices to use two-player games. Specifically, we employ the following result
from [9].

######  Theorem 5.2.

Let
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\delta,(\mathcal{O}_{p})_{p\in\mathsf{Pla}}\rangle$
with $\mathsf{Pla}=\\{1,2\\}$. Let $\alpha\subseteq\mathsf{S}^{\omega}$ be a
parity objective. The problem of deciding whether
$\exists\sigma_{1}\in\Sigma^{1}_{\mathcal{G}}\
\forall\sigma_{2}\in\Sigma^{2}_{\mathcal{G}}\
\mathrm{out}_{\mathcal{G}}({\sigma_{1},\sigma_{2}})\in\alpha$ is EXPTIME-
complete.

We sketch the proof of Theorem 5.1. The complete construction and analysis are
detailed in Appendix B.

######  Proof 5.3 (Proof sketch).

As in Section 4.3, we first fix a set of “intended” winning topologies
$T_{p}\subseteq\mathsf{Top}$ for each player $p\in\mathsf{Pla}$. Then, we ask
whether $\mathcal{G}$ admits a GNE $\boldsymbol{\sigma}$ in which
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=T_{p}$ for every
$p\in\mathsf{Pla}$. We then construct a 2-player partial-information game
whose players are $\mathtt{Eve},\mathtt{Adam}$, where $\mathtt{Eve}$ again
controls the coalition of all players.

The behaviour of $\mathtt{Adam}$ is different than in the conservative
setting. Here, $\mathtt{Adam}$ starts by choosing a deviating player
$p\in\mathsf{Pla}$ and a _single topology_ $t\in\mathsf{Top}$ where $p$
attempts to win. The topology $t$ is unobservable by $\mathtt{Eve}$. The
observations sets of $\mathtt{Eve}$ and $\mathtt{Adam}$ are again only the
current state of $\mathcal{G}$. Then, the game is played on topology $t$ with
$\mathtt{Eve}$ suggesting an action profile, and $\mathtt{Adam}$ possibly
deviating with Player $p$.

The objective for $\mathtt{Eve}$ now comprises two conditions:

  * •

$\psi_{1}$ requires that whenever $\mathtt{Adam}$ obeys $\mathtt{Eve}$ and
$t\in T_{p}$, the outcome is winning for Player $p$ in $\mathcal{G}_{t}$.

  * •

$\psi_{2}$ requires that if $t\notin T_{p}$, then Player $p$ loses in
$\mathcal{G}_{t}$.

Intuitively, $\mathtt{Adam}$ tries to cause Player $p$ to win in a new
topology $t$ in which Player $p$ is not intended to win, while $\mathtt{Eve}$
is trying to prevent Player $p$ from achieving this, provided that Player $p$
is actually deviating. Note that $\mathtt{Eve}$ must do this without knowing
which topology is chosen, nor which player deviates (if at all).

##  6 Discussion, Extensions and Future Work

We introduced MTGs and notions of NE pertaining to them, and showed that
deciding whether an MTG admits either notion is decidable (in 2-EXPTIME for
CNE and in EXPTIME for GNE). We have also explored the relationships and
properties of these notions of NE. We now turn to explore several extensions,
and remark about future research directions.

#### Social optimum

A standard solution concept for concurrent games, apart from NE, is _social
optimum_ , namely what is the maximum welfare the player can obtain by
cooperating. Since in MTGs the winning sets of topologies may be incomparable,
we formulate this as follows: given sets $(T_{p})_{p\in\mathsf{Pla}}$, is
there a strategy profile $\boldsymbol{\sigma}$ such that
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=T_{p}$ for every
$p\in\mathsf{Pla}$?

Fortunately, the techniques we developed enable us to readily solve this
problem. Indeed, we can modify the reduction used to decide the existence of
GNE (Section 5) so that $\mathtt{Adam}$ chooses a player and a topology, but
does not attempt to deviate and has no further effect on the game.
Intuitively, $\mathtt{Adam}$ “challenges” $\mathtt{Eve}$ to show that the
winning topologies for the players are exactly the intended ones. The
complexity of this approach remains EXPTIME.

#### Lower bounds

As discussed in Remark 4.6, we do not provide lower bounds for our results.
Trivial lower bounds on the existence of CNE and GNE can be obtained from
those of NE existence in concurrent games, namely
$\text{P}^{\text{NP}}_{||}$-hardness [6]. This, however, is unlikely to be
tight. A central open challenge is to determine the exact complexity of CNE
and GNE existence in MTGs.

#### Additional notions of equilibria

The notions we propose, namely CNE and GNE, lie on two extremities: in the
conservative setting a deviation is very strict, and in the greedy setting it
is very lax. Generally, one can obtain a notion of equilibrium using any
binary relation on $2^{\mathsf{Top}}$, which describes what the beneficial
deviations are for each player. Moreover, different players can have different
relations.

Of particular interest is a quantitative notion of NE, whereby a player
deviates if she can increase the _number_ of her winning topologies. This
notion is fundamentally different from CNE and GNE, as it is not based on set
containment, which is key to the correctness of our approach.

#### Succinct representation of topologies

A central motivation for MTGs, demonstrated in Example 1.1 and in Section 3.1
concerns process symmetry. There, from a game with $k$ players, we construct
an MTG with $k!$ topologies. However, these topologies can be succinctly
represented by computing them on-the-fly. An interesting direction for future
work is to determine whether we can devise a symbolic approach that is able to
handle such MTGs without incurring an exponential blowup.

#### Logic for partial information games

Another approach to solve the CNE and GNE existence problems is to formulate
those problems with a logic for partial information games [3, 17, 21]. In
Appendix C we delve into this approach. As it turns out, while this approach
can be described with a more straightforward formula than our solution, the
complexity bounds it gives are 3-EXPTIME for both GNE and CNE existence.
Moreover, writing the formula essentially requires an understanding of the
approach we take in the paper. It may be possible to imporove this
construction using a more elaborate analysis, but it is not clear what further
merit such an analysis will have.

## References

  * [1] Shaull Almagor.  Process symmetry in probabilistic transducers.  In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020.
  * [2] Shaull Almagor, Guy Avni, and Orna Kupferman.  Repairing multi-player games.  In 26th International Conference on Concurrency Theory (CONCUR 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.
  * [3] Raphaël Berthon, Bastien Maubert, Aniello Murano, Sasha Rubin, and Moshe Y Vardi.  Strategy logic with imperfect information.  ACM Transactions on Computational Logic (TOCL), 22(1):1–51, 2021\.
  * [4] Udi Boker.  Why these automata types?  In LPAR, volume 18, pages 143–163, 2018.
  * [5] Patricia Bouyer, Nicolas Markey, and Steen Vester.  Nash equilibria in symmetric graph games with partial observation.  Information and Computation, 254:238–258, 2017.
  * [6] Patricia P Bouyer, Romain Brenguier, and Nicolas N Markey.  Pure nash equilibria in concurrent games.  Logical methods in computer science, 2015.
  * [7] Felix Brandt, Felix Fischer, and Markus Holzer.  Equilibria of graphical games with symmetries.  Theoretical Computer Science, 412(8-10):675–685, 2011.
  * [8] Romain Brenguier, Arno Pauly, Jean-François Raskin, and Ocan Sankur.  Admissibility in games with imperfect information.  In CONCUR 2017-28th International Conference on Concurrency Theory, volume 85, pages 2–1. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017.
  * [9] Krishnendu Chatterjee and Laurent Doyen.  The complexity of partial-observation parity games.  In International Conference on Logic for Programming Artificial Intelligence and Reasoning, pages 1–14. Springer, 2010.
  * [10] Krishnendu Chatterjee and Laurent Doyen.  Games with a weak adversary.  In International Colloquium on Automata, Languages, and Programming, pages 110–121. Springer, 2014.
  * [11] Krishnendu Chatterjee, Thomas A Henzinger, and Nir Piterman.  Strategy logic.  Information and Computation, 208(6):677–693, 2010.
  * [12] Edmund M. Clarke, Reinhard Enders, Thomas Filkorn, and Somesh Jha.  Exploiting symmetry in temporal logic model checking.  Formal methods in system design, 9(1):77–104, 1996.
  * [13] Luca De Alfaro, Thomas A Henzinger, and Orna Kupferman.  Concurrent reachability games.  Theoretical computer science, 386(3):188–217, 2007.
  * [14] Aldric Degorre, Laurent Doyen, Raffaella Gentilini, Jean-François Raskin, and Szymon Toruńczyk.  Energy and mean-payoff games with imperfect information.  In International Workshop on Computer Science Logic, pages 260–274. Springer, 2010.
  * [15] E Allen Emerson and A Prasad Sistla.  Symmetry and model checking.  Formal methods in system design, 9(1):105–131, 1996.
  * [16] Emmanuel Filiot, Raffaella Gentilini, and Jean-François Raskin.  Rational synthesis under imperfect information.  In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 422–431, 2018.
  * [17] Bernd Finkbeiner and Sven Schewe.  Coordination logic.  In International Workshop on Computer Science Logic, pages 305–319. Springer, 2010.
  * [18] Nicholas Ham.  Notions of anonymity, fairness and symmetry for finite strategic-form games.  arXiv preprint arXiv:1311.4766, 2013.
  * [19] C Norris Ip and David L Dill.  Better verification through symmetry.  In Computer Hardware Description Languages and their Applications, pages 97–111. Elsevier, 1993.
  * [20] Anthony W Lin, Truong Khanh Nguyen, Philipp Rümmer, and Jun Sun.  Regular symmetry patterns.  In International Conference on Verification, Model Checking, and Abstract Interpretation, pages 455–475. Springer, 2016.
  * [21] Bastien Maubert.  Logical foundations of games with imperfect information: uniform strategies.  PhD thesis, Université Rennes 1, 2014.
  * [22] Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani, editors.  Algorithmic Game Theory.  Cambridge University Press, 2007.  doi:10.1017/CBO9780511800481.
  * [23] Jean-François Raskin, Thomas A Henzinger, Laurent Doyen, and Krishnendu Chatterjee.  Algorithms for omega-regular games with imperfect information.  Logical Methods in Computer Science, 3, 2007.
  * [24] Noah Daniel Stein.  Exchangeable equilibria.  PhD thesis, Massachusetts Institute of Technology, 2011.
  * [25] Fernando A Tohmé and Ignacio D Viglizzo.  Structural relations of symmetry among players in strategic games.  International Journal of General Systems, 48(4):443–461, 2019.
  * [26] M Ummels and DK Wojtczak.  The complexity of nash equilibria in stochastic multiplayer games.  Logical Methods in Computer Science, 2010.
  * [27] Steen Vester.  Symmetric Nash Equilibria.  PhD thesis, Master’s thesis, ENS Cachan, 2012.

##  Appendix A Proofs

###  A.1 Proof of Lemma 4.3

We prove by induction that for every $k\geq 1$, $\mathrm{proj}(\rho_{\leq
k+1})=\pi^{\prime}_{\leq k}$, and if $\mathtt{Adam}$ obeys $\mathtt{Eve}$ then
$\mathrm{proj}(\rho_{\leq k+1})=\pi^{\prime}_{\leq k}=\pi_{\leq k}$. For
$k=1$, $\rho_{\leq 2}=q_{0},(s_{0},p,t,T,b_{0})$ and $\pi^{\prime}_{\leq
1}=\pi_{\leq 1}=s_{0}$ and we have that $\mathrm{proj}(\rho_{\leq
k+1})=\pi^{\prime}_{\leq k}$. Assuming that $\mathrm{proj}(\rho_{\leq
k+1})=\pi^{\prime}_{\leq k}$ for $k\geq 1$, the next state of
$\mathrm{proj}(\rho)$ will depend on the transition function $\delta_{t}$ and
action profile
${\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}](\pi^{\prime}_{\leq
k})$ from the way $\gamma$ and the transitions of $\mathcal{H}$ are defined,
and the next state in $\pi^{\prime}$ will also depend on the same transition
function and action profile. Thus, it holds that $\mathrm{proj}(\rho_{\leq
k+2})=\pi^{\prime}_{\leq k+1}$. Farther more, if $\mathtt{Adam}$ obeys
$\mathtt{Eve}$ then in every step the action that $\mathtt{Adam}$ takes is
identical to the action that $\mathtt{Eve}$ suggests for Player $p$, so we
have that
${\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}](\pi^{\prime}_{\leq
k})=\boldsymbol{\sigma}(\pi^{\prime}_{\leq k})$, and $\pi_{\leq
k+1}=\pi^{\prime}_{\leq k+1}$, thus, $\mathrm{proj}(\rho_{\leq k+2})=\pi_{\leq
k+1}=\pi^{\prime}_{\leq k+1}$. ∎

##  Appendix B Proof of Theorem 5.1

Consider an MTG
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\mathsf{Top},(\delta_{t})_{t\in\mathsf{Top}},(\alpha_{t,p})_{t\in\mathsf{Top},p\in\mathsf{Pla}}\rangle$.
For every Player $p\in\mathsf{Pla}$ fix $T_{p}\subseteq\mathsf{Top}$ to be the
intended set of winning topologies.

#### Game construction

We construct a two-player partial-information game $\mathcal{H}$ with the
following components. The players are $\mathtt{Eve}$ and $\mathtt{Adam}$. The
states of $\mathcal{H}$ are $Q_{\mathcal{H}}=\\{q_{0}\\}\cup Q$ such that
$q_{0}$ is a designated initial state and
$Q=\mathsf{S}\times\mathsf{Pla}\times\mathsf{Top}\times\\{\mathtt{true},\mathtt{false}\\}$
is described in the following. A state $(s,p,t,b)\in Q$ comprises of
$s\in\mathsf{S}$ which tracks the state of $\mathcal{G}$, a player
$p\in\mathsf{Pla}$ that is controlled by $\mathtt{Adam}$, a topology
$t\in\mathsf{Top}$ that $\mathtt{Adam}$ picks, and a bit
$b\in\\{\mathtt{true},\mathtt{false}\\}$ which tracks whether $\mathtt{Adam}$
obeys $\mathtt{Eve}$.

We now turn to define the transitions of $\mathcal{H}$. The actions are
defined implicitly by the transitions. From state $q_{0}$, $\mathtt{Adam}$
selects a player $p\in\mathsf{Pla}$ to control and a topology
$t\in\mathsf{Top}$ that $\mathcal{G}$ will be played in. Then, $\mathcal{H}$
transitions to state $(s_{0},p,t,\mathtt{true})\in Q$. Henceforth, $p$ and $t$
remain fixed throughout the play. From state $(s,p,t,b)\in Q$, $\mathtt{Eve}$
chooses an action profile $\boldsymbol{a}\in\mathsf{Act}^{\mathsf{Pla}}$, and
$\mathtt{Adam}$ selects an action $a^{\prime}_{p}\in\mathsf{Act}$ and
$\mathcal{H}$ transitions to state $(s^{\prime},p,t,b^{\prime})\in Q$ such
that $s^{\prime}=\delta_{t}(s,{\boldsymbol{a}}[{p}\mapsto{a^{\prime}_{p}}])$,
and $b^{\prime}=b\land(a^{\prime}_{p}=a_{p})$.

The observation sets for the players, $\mathrm{proj}$ and $\mathrm{obey}$ are
defined similarly as Section 4.3. Correspondence between $\mathcal{H}$ and
$\mathcal{G}$, $\gamma_{\mathrm{obs}},\gamma_{\mathtt{Eve}}$ is defined in the
same way as in Section 4.3, and
$\gamma_{\mathtt{Adam}}:\Sigma^{\mathtt{Adam}}_{\mathcal{H}}\to\bigcup_{p\in\mathsf{Pla}}\\{p\\}\times\mathsf{Top}\times\Sigma^{p}_{\mathcal{H}}$
is defined for $\gamma(\sigma_{\mathtt{Adam}})=(p,t,\sigma_{p}^{\prime})$ such
that $(p,t)$ are the player and topology selected by $\sigma_{\mathtt{Adam}}$
in state $q_{0}$ and
$\sigma_{p}^{\prime}=\sigma_{\mathtt{Adam}}\circ\gamma_{\mathrm{obs}}^{-1}$.

The connection between strategies and outcomes in $\mathcal{H}$ and
$\mathcal{G}$ is formalized in the following lemma whose proof is similar to
that of Lemma 4.3.

######  Lemma B.1.

Consider strategies
$\sigma_{\mathtt{Eve}}\in\Sigma^{\mathtt{Eve}}_{\mathcal{H}}$ and
$\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$. Let
$\boldsymbol{\sigma}=\gamma(\sigma_{\mathtt{Eve}})$ and
$(p,t,\sigma_{p}^{\prime})=\gamma(\sigma_{\mathtt{Adam}})$. Let
$\rho=\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}}})$
$\pi^{\prime}=\mathrm{out}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})$
and $\pi=\mathrm{out}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})$. Then,
$\mathrm{proj}(\rho)=\pi^{\prime}$. Furthermore, if $\mathtt{Adam}$ obeys
$\mathtt{Eve}$ on $\rho$ then $\mathrm{proj}(\rho)=\pi=\pi^{\prime}$.

#### Objective for $\mathcal{H}$

Let $\rho=q_{0}\cdot(s_{0},p,t,b_{0})\cdot(s_{1},p,t,b_{1})\cdot...$ be a play
in $\mathcal{H}$. The objective $\alpha$ is such that
$\rho\in\alpha\iff\psi_{1}(\rho)\land\psi_{2}(\rho)$, where

  * •

$\psi_{1}(\rho):=(\mathrm{obey}(\rho)\land t\in
T_{p})\to\mathrm{proj}(\rho)\in\alpha_{t,p}$.

  * •

$\psi_{2}(\rho):=t\notin T_{p}\to\mathrm{proj}(\rho)\notin\alpha_{t,p}$.

$\alpha$ can be expressed as a parity objective as follows. For every
$t\in\mathsf{Top}$, $p\in\mathsf{Pla}$, let
$\Omega_{t,p}:\mathsf{S}\to\\{0,...,d_{t,p}\\}$ be the priority function for
the parity objective $\alpha_{t,p}$ in $\mathcal{G}$. We construct a priority
function $\Omega:Q_{\mathcal{H}}\to\\{0,...,d\\}$ such that
$d=\max\\{d_{t,p}+1\mid t\in\mathsf{Top},p\in\mathsf{Pla}\\}$. We set
$\Omega(q_{0})=0$ and for state $q=(s,p,t,b)\in Q$ we have

$\Omega(q)=\begin{cases}\Omega_{t,p}(s)+1&t\notin T_{p}\\\
\Omega_{t,p}(s)&b\land t\in T_{p}\\\ \Omega(q)=0&\neg b\land t\in
T_{p}\end{cases}$

If $t\notin T_{p}$, then, according to $\alpha$, $\rho\in\alpha$ if and only
if $\mathrm{proj}(\rho)\notin\alpha_{t,p}$. This is achieved by adding 1 to
$\Omega_{t,p}$ which gives us the complement of $\alpha_{t,p}$. The case where
$\mathtt{Adam}$ obeys $\mathtt{Eve}$ and $t\in T_{p}$ is captured in the
second case, where $\rho\in\alpha$ if and only if
$\mathrm{proj}(\rho)\in\alpha_{t,p}$. This is achieved by setting $\Omega$ to
be the same as $\Omega_{t,p}$. In the last case, non of the preconditions of
$\psi_{1}$ and $\psi_{2}$ hold, so $\rho\in\alpha$. This is achieved by
setting $\Omega$ to 0, such that every such play will satisfy the objective.

######  Lemma B.2.

There exists a GNE $\boldsymbol{\sigma}\in\Sigma_{\mathcal{G}}$ in
$\mathcal{G}$ with
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=T_{p}$ for every
$p\in\mathsf{Pla}$, if and only if
$\exists\sigma_{\mathtt{Eve}}\in\Sigma^{\mathtt{Eve}}_{\mathcal{H}}\
\forall\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}\
\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}}})\in\alpha$.

######  Proof B.3.

Let $\boldsymbol{\sigma}\in\Sigma_{\mathcal{G}}$ be a GNE with
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=T_{p}$ for every
$p\in\mathsf{Pla}$. Let
$\sigma_{\mathtt{Eve}}\in\Sigma^{\mathtt{Eve}}_{\mathcal{H}}$ be the
corresponding strategy for $\boldsymbol{\sigma}$, and let
$\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$ be some
strategy for $\mathtt{Adam}$ that corresponds to $(p,t,\sigma_{p}^{\prime})$.
Let
$\rho=\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}}})$.
If $\mathrm{obey}(\rho)\land t\in T_{p}$, then from Lemma B.1 we have that
$\mathrm{proj}(\rho)=\mathrm{out}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})$,
and since $t\in
T_{p}=\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})$ then
$\mathrm{out}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})\in\alpha_{t,p}$. Thus,
$\psi_{1}$ is satisfied by $\rho$. If $t\notin T_{p}$ then from Lemma B.1 we
have that
$\mathrm{proj}(\rho)=\mathrm{out}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})$
and since Player $p$ is losing in $t$ when $\mathcal{G}$ is played with
$\boldsymbol{\sigma}$ and $\boldsymbol{\sigma}$ is a GNE, then
$\mathrm{out}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})\notin\alpha_{t,p}$.
Thus, $\psi_{2}$ is satisfied and $\rho\in\alpha$.

Conversely, let $\sigma_{\mathtt{Eve}}\in\Sigma^{\mathtt{Eve}}_{\mathcal{H}}$
be such that for any
$\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$ we have
$\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}}})\in\alpha$.
Let $\boldsymbol{\sigma}\in\Sigma_{\mathcal{G}}$ correspond to
$\sigma_{\mathtt{Eve}}$. We show that $\boldsymbol{\sigma}$ is a GNE. First,
we show that for every $p\in\mathsf{Pla}$,
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})=T_{p}$. Let
$t\in\mathsf{Top}$ and $p\in\mathsf{Pla}$. Take
$\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$ that
corresponds to $(p,t,\sigma_{p})$ where $\sigma_{p}$ is the strategy assigned
to $p$ in $\boldsymbol{\sigma}$. Let
$\rho_{t}=\mathrm{out}_{\mathcal{G}_{t}}({\boldsymbol{\sigma}})$ and
$\rho=\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}}})$.
We have that $\rho\in\alpha$. Since $\mathtt{Adam}$ obeys $\mathtt{Eve}$ on
$\rho$, from Lemma B.1 we have that $\mathrm{proj}(\rho)=\rho_{t}$. If $t\in
T_{p}$ then from $\psi_{1}$ we get that
$\rho_{t}=\mathrm{proj}(\rho)\in\alpha_{t,p}$, thus,
$t\in\mathrm{WinTop}_{\mathcal{G}}^{p}({\boldsymbol{\sigma}})$. If $t\notin
T_{p}$ then from $\psi_{2}$ we get that
$\rho_{t}=\mathrm{proj}(\rho)\notin\alpha_{t,p}$, thus,
$t\notin\mathrm{WinTop}_{\mathcal{G}}^{p}({\sigma})$. So we get that
$\mathrm{WinTop}_{\mathcal{G}}^{p}({\sigma})=T_{p}$. Now, we show that
$\boldsymbol{\sigma}$ is a GNE. Let $p\in\mathsf{Pla}$,
$\sigma_{p}^{\prime}\in\Sigma^{p}_{\mathcal{G}}$ and $t\in\mathsf{Top}$ such
that $t\notin T_{p}$. Let
$\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$ correspond to
$(p,t,\sigma_{p}^{\prime})$, and let
$\rho=\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}}})$.
We have that $\rho\in\alpha$, thus, since $t\notin T_{p}$ then
$\mathrm{proj}(\rho)\notin\alpha_{t,p}$. From Lemma B.1 we have that
$\rho^{\prime}_{t}=\mathrm{out}_{\mathcal{G}_{t}}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})=\mathrm{proj}(\rho)\notin\alpha_{t,p}$,
thus,
$t\notin\mathrm{WinTop}_{\mathcal{G}_{t}}^{p}({{\boldsymbol{\sigma}}[{p}\mapsto{\sigma_{p}^{\prime}}]})=T_{p}$,
so $\boldsymbol{\sigma}$ is a GNE.

The algorithm for solving the GNE existence problem is, for each
$(T_{p})_{p\in\mathsf{Pla}}\in(2^{\mathsf{Top}})^{\mathsf{Pla}}$ we construct
$\mathcal{H}$ from $\mathcal{G}$ and $(T_{p})_{p\in\mathsf{Pla}}$, and check
if there exists $\sigma_{\mathtt{Eve}}\in\Sigma^{\mathtt{Eve}}_{\mathcal{H}}$
such that for every
$\sigma_{\mathtt{Adam}}\in\Sigma^{\mathtt{Adam}}_{\mathcal{H}}$,
$\mathrm{out}_{\mathcal{H}}({\sigma_{\mathtt{Eve}},\sigma_{\mathtt{Adam}}})\in\alpha$,
if there exists such $\sigma_{\mathtt{Eve}}$, then according to Lemma B.2 is
corresponding strategy profile is a GNE, then we return it. If we went through
all $(T_{p})_{p\in\mathsf{Pla}}\in(2^{\mathsf{Top}})^{\mathsf{Pla}}$, then
return that there does not exist a GNE in $\mathcal{G}$.

The size of $\mathcal{H}$ is polynomial in the size of $\mathcal{G}$. We copy
each $s\in\mathsf{S}$ for every combination of $p\in\mathsf{Pla}$,
$t\in\mathsf{Top}$, $b\in\\{\mathtt{true},\mathtt{false}\\}$, so we get
$|Q_{\mathcal{H}}|=2\cdot|S|\cdot|\mathsf{Pla}|\cdot|\mathsf{Top}|+1$, which
is polynomial in the size of $\mathcal{G}$. The number of actions in
$\mathcal{H}$ is also polynomial in the number of enabled actions in
$\mathcal{G}$ (similarly to the analysis in Section 4.3).

The algorithm performs at most $2^{|\mathsf{Top}|\cdot|\mathsf{Pla}|}$
iterations, which is exponential in $|\mathcal{G}|$. In each iteration we
solve $\mathcal{H}$ with size that is polynomial in $|\mathcal{G}|$, so
according to Theorem 5.2 this takes exponential time in $|\mathcal{G}|$, so
the GNE existence problem is in EXPTIME.

##  Appendix C Strategy Logic with Imperfect Information

In this section we discuss solving the GNE and CNE existence problems using
_strategy logic with imperfect information_ , $\mathsf{SL_{ii}}$, introduced
in [3]. $\mathsf{SL_{ii}}$ is an expressive logic that is generally
undecidable, but a decidable fragment, called _hierarchical instances_ , can
capture the GNE and CNE existence problems. The complexity of
$\mathsf{SL_{ii}}$ model-checking for hierarchical instances depends on a
parameter called the _simulation depth_. $\mathsf{SL_{ii}}$ model-checking for
formulas with simulation depth up to $k$ is $(k+1)$-EXPTIME-complete, and the
procedure suggested in [3] is $(k+1)$-EXPTIME. Our formulation of the GNE and
CNE existence problems with $\mathsf{SL_{ii}}$, has a simulation depth of 2
for both problems, resulting in 3-EXPTIME procedure for solving those. It
might be possible that there is a different formulation with a lower
simulation depth, lowering the complexity of this approach.

The section is organized as follows. In Section C.1 we give a short overview
of $\mathsf{SL_{ii}}$. In Section C.2 we discuss how to convert a multi-
topology game to a model called _concurrent game structure with imperfect
information_ that $\mathsf{SL_{ii}}$ is interpreted over. Then, in Section C.3
we formalize the GNE existence problem with $\mathsf{SL_{ii}}$ and compute
it’s simulation depth. In Section C.4 we do the same for the CNE existence
problem.

###  C.1 Overview of $\mathsf{SL_{ii}}$

$\mathsf{SL_{ii}}$ formulas are defined over a number of fixed parameters – a
set of _atomic propositions_ $\mathsf{AP}$, a set of _players_ (or _agents_)
$\mathsf{Ag}$, a set of _strategy variables_ $\mathsf{Var}$ and a set of
_observation symbols_ $\mathsf{Obs}$. $\mathsf{SL_{ii}}$ formulas are
interpreted over _Concurrent Game Structure with Imperfect Information_ ,
abbreviated $\mathsf{CGS_{ii}}$. A $\mathsf{CGS_{ii}}$ is a tuple
$\mathcal{G}=\langle\mathsf{Ac},\mathsf{V},\mathsf{E},\mathcal{L},v_{0},\mathcal{O}\rangle$
such that $\mathsf{Ac}$ is a set of _actions_ , $\mathsf{V}$ is a set of
_states_ , $\mathsf{E}:\mathsf{V}\times\mathsf{Ac}^{\mathsf{Ag}}\to\mathsf{V}$
is a _transition function_ , $\mathcal{L}:\mathsf{V}\to 2^{\mathsf{AP}}$ is a
_labelling function_ , $v_{0}\in\mathsf{V}$ is an _initial state_ and
$\mathcal{O}:\mathsf{Obs}\to 2^{\mathsf{V}\times\mathsf{V}}$ is an
_observation interpretation_ , which maps each observation symbol
$o\in\mathsf{Obs}$ to an equivalence relation over the states
$\mathcal{O}(o)\subseteq\mathsf{V}\times\mathsf{V}$. $\mathsf{SL_{ii}}$ has
the following _syntax_ :

$\displaystyle\varphi$
$\displaystyle:=p\mid\neg\varphi\mid\varphi\lor\varphi\mid\llangle{x}\rrangle^{o}\varphi\mid({a},{x})\varphi\mid({a},?)\varphi\mid\mathrm{E}\psi;\
p\in\mathsf{AP},x\in\mathsf{Var},a\in$ $\displaystyle\psi$
$\displaystyle:=\varphi\mid\neg\psi\mid\psi\lor\psi\mid\mathrm{X}\psi\mid\psi\mathrm{U}\psi;$

Formulas of type $\varphi$ are called _state formulas_ and formulas of type
$\psi$ are called _path formulas_. The boolean and temporal operators
$\neg,\lor,\mathrm{X},\mathrm{U}$ have their usual semantics. The syntax is
extended with the boolean and temporal operators
$\land,\to,\mathrm{F},\mathrm{G}$ that can be expressed with the operators
already in the syntax. The _existential strategy quantifier_
$\llangle{x}\rrangle^{o}\varphi$ means, “there exists a strategy $x$ over the
observations $\mathcal{O}(o)$ that satisfies $\varphi$”. The syntax is
extended with a _universal strategy quantifier_ defined
$\lsem{x}\rsem^{o}\varphi:=\neg\llangle{x}\rrangle^{o}\neg\varphi$. The
_binding operator_ $({a},{x})$ binds strategy $x$ to player $a$ and the
_unbinding operator_ $({a},?)$ unbinds player $a$ from it’s current strategy.
The _existential outcome quantifier_ $\mathrm{E}\psi$ means “there exists an
outcome of the current strategy assignment that satisfies $\psi$”. The syntax
is extended with a _universal outcome quantifier_ defined
$\mathrm{A}\psi:=\neg\mathrm{E}\neg\psi$. For a full description of the
semantics of $\mathsf{SL_{ii}}$ we refer readers to [3].

An $\mathsf{SL_{ii}}$ _instance_ is a pair $(\mathcal{G},\Phi)$ where
$\mathcal{G}$ is a $\mathsf{CGS_{ii}}$ and $\Phi$ is an $\mathsf{SL_{ii}}$
state formula. In general, $\mathsf{SL_{ii}}$ is undecidable. But, a fragment
called _hierarchical instances_ is decidable. An _hierarchical instance_ is
such that as we go down the syntax tree of the formula, observations only get
finer.

The complexity of the model-checking problem for an hierarchical
$\mathsf{SL_{ii}}$ instance $(\mathcal{G},\Phi)$ depends on the _simulation
depth_ of $(\mathcal{G},\Phi)$. The simulation depth is computed recursively
on the formula’s structure. The complexity of the model-checking procedure for
an instance with simulation depth $k$ is $(k+1)$-EXPTIME. For a description of
how to compute the simulation depth we refer readers to [3].

###  C.2 MTG to $\mathsf{CGS_{ii}}$

In this section we show how to translate an MTG to a $\mathsf{CGS_{ii}}$ and a
set of formulas that describe the players winning conditions.

Let
$\mathcal{G}=\langle\mathsf{Pla},\mathsf{S},s_{0},\mathsf{Act},\mathsf{Top},(\delta_{t})_{t\in\mathsf{Top}},(\alpha_{t,p})_{t\in\mathsf{Top},p\in\mathsf{Pla}}\rangle$
be an MTG. We denote the players $\mathsf{Pla}=\\{p_{1}\ldots p_{n}\\}$.
First, we fix the parameters over which the $\mathsf{SL_{ii}}$ formulas are
defined, $\mathsf{AP}$, $\mathsf{Ag}$, $\mathsf{Var}$ and $\mathsf{Obs}$. The
set of atomic propositions is such that we can encode each state and each
topology with a unique label (a subset of $\mathsf{AP}$). This will enable us
to write the LTL formula $\psi_{t,p}$ for every $t\in\mathsf{Top}$ and
$p\in\mathsf{Pla}$ which means that the topology $t$ is played and $p$’s
objective is satisfied. The set of agents is
$\mathsf{Ag}=\mathsf{Pla}\cup\\{T\\}$ where $T$ is the _topology player_ that
selects the topology. The set of strategy variables is
$\mathsf{Var}=\\{\sigma_{p}\mid
p\in\mathsf{Pla}\\}\cup\\{\sigma_{p}^{\prime}\mid p\in\mathsf{Pla}\\}$. Since
all players have the same observation sets (i.e., can observe the state, but
not the topology), we only need a single observation symbol $o$. Note that
every $\mathsf{SL_{ii}}$ instance with a single observation symbol is
inherently hierarchical.

The $\mathsf{CGS_{ii}}$ that we use is
$\mathcal{H}=\langle\mathsf{Ac},\mathsf{V},\mathsf{E},\mathcal{L},v_{0},\mathcal{O}\rangle$.
The actions in $\mathcal{H}$ are the actions in $\mathcal{G}$ together with
actions for $T$ that enable him to select the topology in the first turn of
the game. The states of $\mathcal{H}$ are
$\mathsf{V}=(\mathsf{S}\times\mathsf{Top})\cup\\{v_{0}\\}$, where $v_{0}$ is
the initial state where $T$ selects the topology. The transition function
corresponds to the transition function of $\mathcal{G}$, and allowing $T$ to
select the topology from the initial state $v_{0}$. The observation symbol $o$
is interpreted such that $v_{0}$ is distinguishable from all other states and
$((s,t),(s^{\prime},t^{\prime}))\in\mathcal{O}(o)$ (that is, $(s,t)$ and
$(s^{\prime},t^{\prime})$ are indistinguishable) if and only if
$s=s^{\prime}$.

###  C.3 Expressing GNE Existence Problem with $\mathsf{SL_{ii}}$

The following formula expresses the GNE existence problem in
$\mathsf{SL_{ii}}$:

$\llangle{\boldsymbol{\sigma}}\rrangle^{o}({\mathsf{Pla}},{\boldsymbol{\sigma}})\bigwedge_{p\in\mathsf{Pla}}\left[\lsem{\sigma_{p}^{\prime}}\rsem^{o}\left(\bigwedge_{t\in\mathsf{Top}}\left(\mathrm{E}\psi_{t,p}\lor\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)\right)\right]$

Where
$\llangle{\boldsymbol{\sigma}}\rrangle^{o}:=\llangle{\sigma_{p_{1}}}\rrangle^{o}\ldots\llangle{\sigma_{p_{n}}}\rrangle^{o}$
is a shorthand way of writing “there exists a strategy profile”. Similarly,
$({\mathsf{Pla}},{\boldsymbol{\sigma}}):=({p_{1}},{\sigma_{p_{1}}})\ldots({p_{n}},{\sigma_{p_{n}}})$
is binding the strategy profile to the players. When all players except for
the topology player $T$ are bound to a strategy, the formula
$\mathrm{E}\psi_{p,t}$ means that player $p$ wins in topology $t$ under the
given strategy assignment. After we quantify over strategy profiles, we
require that for every player $p$ in $\mathcal{G}$, every strategy
$\sigma_{p}^{\prime}$ and every topology $t$, either player $p$ wins topology
$t$ when players are assigned strategy profile $\boldsymbol{\sigma}$ or player
$p$ loses topology $t$ when she changes her strategy to $\sigma_{p}^{\prime}$.

#### Simulation depth

Now, we compute the simulation depth of the instance. The computation involves
two parameters – first is the current simulation depth $k\in{\rm Nature}$ and
the second is a parameter that can be either $\mathtt{nd}$ or $\mathtt{alt}$.
The computation is performed according to Section 5.2 in [3]. Quantifying an
LTL formula with $\mathrm{E}$ gives the simulation depth $(0,\mathtt{nd})$.
Thus, $sd\left(\mathrm{E}\psi_{t,p}\right)=(0,\mathtt{nd})$. Binding a
strategy to a player does not change the simulation depth, so we have
$sd\left(({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)=(0,\mathtt{nd})$.
Negating a formula keeps the current simulation depth the same and sets the
second parameter to $\mathtt{alt}$. Thus,
$sd\left(\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)=(0,\mathtt{alt})$.
Taking a disjunction between two formulas results in the maximum of each
parameter of the subformulas (where $\mathtt{nd}<\mathtt{alt}$), thus,
$sd\left(\mathrm{E}\psi_{t,p}\lor\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)=(0,\mathtt{alt})$.
The conjunction over all the topologies translates into a negation,
disjunction and another negation. Since each subformula $\varphi$ has
$sd\left(\varphi\right)=(0,\mathtt{alt})$, we have that:

$sd\left(\bigwedge_{t\in\mathsf{Top}}\left(\mathrm{E}\psi_{t,p}\lor\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)\right)=(0,\mathtt{alt})$

The universal strategy quantifier translates into a negation that does not
change the simulation depth, an existential strategy quantifier that increases
the first parameter by 1 and sets the second parameter to $\mathtt{nd}$ and
another negation that sets the second parameter to $\mathtt{alt}$. So we have
that

$sd\left(\lsem{\sigma_{p}^{\prime}}\rsem^{o}\left(\bigwedge_{t\in\mathsf{Top}}\left(\mathrm{E}\psi_{t,p}\lor\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)\right)\right)=(1,\mathtt{alt})$

Binding the strategy profile to the players has no effect and the universal
strategy quantifier increases the first parameter by 1 and sets the second to
$\mathtt{nd}$, thus,

$sd\left(\llangle{\boldsymbol{\sigma}}\rrangle^{o}({\mathsf{Pla}},{\boldsymbol{\sigma}})\bigwedge_{p\in\mathsf{Pla}}\left[\lsem{\sigma_{p}^{\prime}}\rsem^{o}\left(\bigwedge_{t\in\mathsf{Top}}\left(\mathrm{E}\psi_{t,p}\lor\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)\right)\right]\right)=(2,\mathtt{nd})$

Making model-checking complexity of the instance to be 3-EXPTIME.

###  C.4 Expressing CNE Existence Problem with $\mathsf{SL_{ii}}$

The following formula expresses the CNE existence problem in
$\mathsf{SL_{ii}}$:

$\llangle{\boldsymbol{\sigma}}\rrangle^{o}({\mathsf{Pla}},{\boldsymbol{\sigma}})\bigwedge_{p\in\mathsf{Pla}}\left[\lsem{\sigma_{p}^{\prime}}\rsem^{o}\left(\left(\bigwedge_{t\in\mathsf{Top}}\left(\mathrm{E}\psi_{t,p}\lor\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)\right)\lor\left(\bigvee_{t\in\mathsf{Top}}\left(\mathrm{E}\psi_{t,p}\land\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)\right)\right)\right]$

The formula for CNE is similar to the formula for GNE. We change the
subformula
$\bigwedge_{t\in\mathsf{Top}}\left(\mathrm{E}\psi_{t,p}\lor\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)$,
which means that for every topology $t$, player $p$ does not improve her
outcome by switching to strategy $\sigma_{p}^{\prime}$, by taking a
disjunction with
$\bigvee_{t\in\mathsf{Top}}\left(\mathrm{E}\psi_{t,p}\land\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)$,
which means that there exists a topology where player $p$ wins, and loses if
she changes her strategy to $\sigma_{p}^{\prime}$.

#### Simulation depth

The simulation depth of the two subformulas
$\bigwedge_{t\in\mathsf{Top}}\left(\mathrm{E}\psi_{t,p}\lor\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)$
and
$\bigvee_{t\in\mathsf{Top}}\left(\mathrm{E}\psi_{t,p}\land\neg({p},{\sigma_{p}^{\prime}})\mathrm{E}\psi_{t,p}\right)$
is the same and is equal to $(0,\mathtt{alt})$. Thus, the conjunction of the
two results in a formula with simulation depth $(0,\mathtt{alt})$. The next
steps in the computation of the simulation depth are identical to the
computations for GNE, making the simulation depth be $(2,\mathtt{nd})$ and the
model-checking complexity to be 3-EXPTIME.