Games with $\omega$-Automatic Preference Relations

Our contributions center on using $\omega$-automatic relations on infinite words [41], as introduced in [23], to define a general framework for preference relations over paths in game graphs, thereby establishing a generic method to compare executions for players in non-zero-sum games. These relations are specified by deterministic parity automata that read pairs $(x,y)$ of words synchronously and accept them whenever $y$ is preferred to $x$.

Our main contributions focus on the computational complexity of four key problems related to NEs in non-zero-sum games [36] with $\omega$-automatic preference relations. First, we study the problem of verifying whether a given strategy profile, specified by Mealy machines, one per strategy, constitutes an NE in the given game. We prove that this problem is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete (Theorem 3). Second, we examine whether a lasso-shaped path (i.e., a regular path) is the outcome of an NE, showing that this problem is in $\mathrm{𝖭𝖯}$ $\cap$ $\mathrm{𝖼𝗈𝖭𝖯}$ and $\mathrm{𝖯𝖺𝗋𝗂𝗍𝗒}$-hard (Theorem 4). Third, we establish the existence of games without any NE, motivating the fundamental problem of determining whether a given game admits at least one NE. This problem turned out to be particularly challenging, and we reduce it to a three-player zero-sum game with imperfect information. We provide an algorithm for solving this problem with exponential complexity in the size of the graph, the parity automata defining the preference relation, and the number of their priorities, and doubly exponential complexity in the number of players. However, since the number of players is a natural parameter that tends to be small in practical scenarios,¹¹1In robotic systems or in security protocols, the number of agents is usually limited to a few. For example, in a security protocol, the players are Alice and Bob who exchange messages, the trusted third party, and a fourth player for the network (see, e.g., [19, 29]) we refine this result by proving that for a fixed number of players, the problem lies in $\mathrm{𝖤𝖷𝖯𝖳𝖨𝖬𝖤}$ and is $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard (Theorem 5). In addition, our approach has the advantage of being modular and therefore easily adapts to question the existence of a constrained NE. When we attach one constraint to each player given as a lasso-shaped path and ask for an NE whose outcome is preferred to any of those constraints, the adapted algorithm keeps the same complexity except that it becomes doubly exponential in the number of priorities of the parity conditions. Yet the number of priorities is often small²²2important classes of objectives such as Büchi, co-Büchi, reachability, and safety require at most three priorities and when we fix it and the number of players, the algorithm remains in $\mathrm{𝖤𝖷𝖯𝖳𝖨𝖬𝖤}$ and $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hard (Theorem 6). Note that our approach allows to show that when there exists an (constrained) NE, there exists one composed of finite-memory strategies.

Additionally, we analyze the algorithmic complexity of verifying whether an $\omega$-automatic relation satisfies the axioms of a strict partial order (irreflexivity and transitivity) or of a preorder (reflexivity and transitivity) which are two classical requirements for a relation to model preferences. We show that these problems are $\mathrm{𝖭𝖫}$-complete (Proposition 9). Finally, we show that when the $\omega$-automatic preference relations are all $\omega$-recognizable (a strict subclass of $\omega$-automatic relations where the two input words can be processed independently) and preorders, the existence of at least one NE is always guaranteed (Theorem 11).

A well-established hierarchy of rational relations holds for both finite and infinite words [17, 40]. The $\omega$-automatic relations – also called synchronized $\omega$-rational relations – were first studied in [23]. Some decision problems about $\omega$-automatic and $\omega$-recognizable relations were solved in [35] and improved in [3]. The study of automatic structures has also led to results involving rational relations, notably within first-order logic (see, e.g., [5, 25, 31, 39]).

The problems we study in this paper were widely investigated in the literature for specific reward functions, including functions that mix different objectives, see, e.g., [6, 28, 42, 43]. There are also works that study these problems across large classes of reward functions rather than individual ones, or that consider general notions of preference relations. For instance, in [12], the authors prove the existence of finite-memory NEs for all cost-semi-linear reward functions. In [7], a complete methodology is developed to solve the (constrained) NE existence problem, thanks to the concept of suspect game, encompassing all reward functions definable by a class of monotone circuits over the set of states that appear (finitely or infinitely often) along paths in a game graph. The preference relations studied in [7] are all $\omega$-automatic. In [20], the authors study NEs for games with a reward function that, given a finite set $X$ of objectives of the same type, associates an integer with each subset of satisfied objectives of $X$. Again, if the objectives of $X$ are $\omega$-regular, the reward functions of [20] lead to $\omega$-automatic preference relations. The existence of NEs is guaranteed within a broad setting, both in [27] and [34], without relying on an automata-based approach, however with no complexity result about the constrained NE existence problem. In case of games with $\omega$-recognizable preference relations, our proof that NEs always exist relies on the technique developed in [27].

The results we obtain with games with $\omega$-recognizable preference relations cover a large part of the games studied classically. In addition, our setting allows any combinations of objectives as soon as they are expressible by automata. However, it does not cover games with mean-payoff or energy objectives. Indeed, in the first case, it is proved in [2] that the related preference relation is not $\omega$-automatic; and in the second case, the constrained NE existence problem is undecidable [11]. Note that the general concepts of $\omega$-automatic and $\omega$-recognizable relations have also been used to study imperfect information in games in [4, 8] and formal verification of quantitative systems in [2].

Let $\mathrm{\Sigma }$ be a fixed finite alphabet. We consider binary relations $R\subseteq {\mathrm{\Sigma }}^{\omega }\times {\mathrm{\Sigma }}^{\omega }$ on infinite words over $\mathrm{\Sigma }$. The relation $R$ is $\omega$-automatic if it is accepted by a deterministic finite parity automaton over the alphabet $\mathrm{\Sigma }\times \mathrm{\Sigma }$, that is, $R$ is an $\omega$-regular language over $\mathrm{\Sigma }\times \mathrm{\Sigma }$. The automaton reads pairs of letters by advancing synchronously on the two words. This behavior is illustrated in Figure 1 below. A relation $R$ is $\omega$-recognizable if it is equal to ${\cup }_{i=1}^{\mathrm{\ell }}{X}_i\times Y_i$ where $X_i,Y_i\subseteq {\mathrm{\Sigma }}^{\omega }$ are $\omega$-regular languages over $\mathrm{\Sigma }$ [35]. Any $\omega$-recognizable relation is $\omega$-automatic [40].

We suppose that the reader is familiar with the usual notion of deterministic parity automaton (DPA) used to accept $\omega$-automatic relations [35]. A run is accepting if the maximum priority seen infinitely often is even. In this paper, we also use other classical notions of automata: deterministic Büchi automata (DBA) and Rabin automata. See, e.g., [26] for general definitions, or [1, 32] for deeper details. We also need the concept of generalized parity automaton which is an automaton with a positive³³3The negation is not allowed in the Boolean combination. Boolean combination of parity conditions. Given an automaton $𝒜$, its size $|𝒜|$ is its number of states.

An arena is a tuple $A=(V,E,𝒫,{(V_i)}_{i\in 𝒫})$ where $V$ is a finite set of vertices, $E\subseteq V\times V$ is a set of edges, $𝒫$ is a finite set of players, and ${(V_i)}_{i\in 𝒫}$ is a partition of $V$, where $V_i$ is the set of vertices owned by player $i$. We assume, w.l.o.g., that each $v\in V$ has at least one successor, i.e., there exists $v^{\prime }\in V$ such that $(v,v^{\prime })\in E$. We define a play $\pi \in V^{\omega }$ (resp. a history $h\in V^{\ast }$) as an infinite (resp. finite) sequence of vertices ${\pi }_0{\pi }_1\mathrm{\dots }$ such that $({\pi }_k,{\pi }_{k+1})\in E$ for any two consecutive vertices ${\pi }_k,{\pi }_{k+1}$. The set of all plays of an arena $A$ is denoted ${\mathrm{𝖯𝗅𝖺𝗒𝗌}}_A\subseteq V^{\omega }$, and we write $\mathrm{𝖯𝗅𝖺𝗒𝗌}$ when the context is clear. The length $|h|$ of a history $h$ is the number of its vertices. The empty history is denoted $\epsilon$.

A game $𝒢=(A,{(R_i)}_{i\in 𝒫})$ is an arena equipped with $\omega$-automatic relations $R_i$ over the alphabet $V$, one for each player $i$, called his preference relation. For any two plays $\pi ,{\pi }^{\prime }$, player $i$ prefers ${\pi }^{\prime }$ to $\pi$ if $(\pi ,{\pi }^{\prime })\in R_i$. In the sequel, we write ${\prec }_i$ instead of $R_i$ and for all $x,y\in V^{\omega }$, $x{\prec }_{i}y$, or $y{\succ }_{i}x$, instead of $(x,y)\in R_i$. We also say that $x$ is maximal (resp. minimal) for ${\prec }_i$ if for all $y\in V^{\omega }$, we have $x{\nprec }_{i}y$ (resp. $y{\nprec }_{i}x$). Below we give various examples of games whose preference relations are all strict partial orders. At this stage, ${\prec }_i$ is just an $\omega$-automatic relation without any additional hypotheses. Such hypotheses will be discussed in Section 6.

Given a play $\pi$ and an index $k$, we write ${\pi }_{\ge k}$ the suffix ${\pi }_k{\pi }_{k+1}\mathrm{\dots }$ of $\pi$. We denote the first vertex of $\pi$ by $\mathrm{𝖿𝗂𝗋𝗌𝗍}(\pi )$. These notations are naturally adapted to histories. We also write $\mathrm{𝗅𝖺𝗌𝗍}(h)$ for the last vertex of a history $h\ne \epsilon$. We can concatenate two non-empty histories $h_1$ and $h_2$ into a single one, denoted $h_1\cdot h_2$ or $h_1{h}_2$ if $(\mathrm{𝗅𝖺𝗌𝗍}(h_1),\mathrm{𝖿𝗂𝗋𝗌𝗍}(h_2))\in E$. When a history can be concatenated to itself, we call it cycle. A play $\pi =\mu \nu \nu \mathrm{\cdots }=\mu {(\nu )}^{\omega }$, where $\mu \nu$ is a history and $\nu$ a cycle, is called a lasso. The length of $\pi$ is then the length of $\mu \nu$, denoted $|\pi |$.⁴⁴4To have a well-defined length for a lasso $\pi$, we assume that $\pi =\mu {(\nu )}^{\omega }$ with $\mu \nu$ of minimal length.

Let $A$ be an arena. A strategy ${\sigma }_i:V^{\ast }{V}_i\to V$ for player $i$ maps any history $h\in V^{\ast }{V}_i$ to a successor $v$ of $\mathrm{𝗅𝖺𝗌𝗍}(h)$, which is the next vertex that player $i$ chooses to move after reaching the last vertex in $h$. A play $\pi ={\pi }_0{\pi }_1\mathrm{\dots }$ is consistent with ${\sigma }_i$ if ${\pi }_{k+1}={\sigma }_i({\pi }_0\mathrm{\dots }{\pi }_k)$ for all $k\in \mathbb{N}$ such that ${\pi }_k\in V_i$. Consistency is naturally extended to histories. A tuple of strategies $\sigma ={({\sigma }_i)}_{i\in 𝒫}$ with ${\sigma }_i$ a strategy for player $i$, is called a strategy profile. The play $\pi$ starting from an initial vertex $v_0$ and consistent with each ${\sigma }_i$ is denoted by ${⟨\sigma ⟩}_{v_0}$ and called outcome.

A strategy ${\sigma }_i$ for player $i$ is finite-memory [26] if it can be encoded by a Mealy machine $ℳ=(M,m_0,{\alpha }_U,{\alpha }_N)$ where $M$ is the finite set of memory states, $m_0\in M$ is the initial memory state, ${\alpha }_U:M\times V\to M$ is the update function, and ${\alpha }_N:M\times V_i\to V$ is the next-move function. Such a machine defines the strategy ${\sigma }_i$ such that ${\sigma }_i(hv)={\alpha }_N({\widehat{\alpha }}_U(m_0,h),v)$ for all histories $hv\in V^{\ast }{V}_i$, where ${\widehat{\alpha }}_U$ extends ${\alpha }_U$ to histories as expected. A strategy ${\sigma }_i$ is memoryless if it is encoded by a Mealy machine with only one state.

We suppose that the reader is familiar with the concepts of two-player zero-sum games with $\omega$-regular objectives and of winning strategy [21, 26].

Let us show that the above notion of game $𝒢=(A,{({\prec }_i)}_{i\in 𝒫})$ encompasses many cases of classic games and more. We begin with games where each player $i$ has an $\omega$-regular objective ${\mathrm{\Omega }}_i\subseteq V^{\omega }$, such as a reachability or a Büchi objective [21, 26]. In this case, the preference relation ${\prec }_i\subseteq V^{\omega }\times V^{\omega }$ is defined by $x{\prec }_{i}y$ if and only if , where ${\mathrm{\Omega }}_i$ is seen as a function ${\mathrm{\Omega }}_i:V^{\omega }\to \{0,1\}$. As ${\mathrm{\Omega }}_i$ is $\omega$-regular, it follows that ${\prec }_i$ is $\omega$-automatic. For instance, given a target set $T\subseteq V$, the first DPA of Figure 1 accepts ${\prec }_i$ when ${\mathrm{\Omega }}_i$ is a reachability objective $\{x=x_0{x}_1\mathrm{\dots }\in V^{\omega }\mid \exists k,x_k\in T\}$; the second DPA accepts ${\prec }_i$ when ${\mathrm{\Omega }}_i$ is a Büchi objective $\{x\in V^{\omega }\mid \mathrm{𝖨𝗇𝖿}(x)\cap T\ne \mathrm{\varnothing }\}$, where $\mathrm{𝖨𝗇𝖿}(x)$ is the set of vertices seen infinitely many times in $x$.

More general preference relations can be defined from several $\omega$-regular objectives ${({\mathrm{\Omega }}_i^j)}_{1\le j\le n}$ for player $i$. With each $x\in V^{\omega }$ is associated the payoff vector ${\overline{\mathrm{\Omega }}}_i(x)=({\mathrm{\Omega }}_i^1(x),\mathrm{\dots },{\mathrm{\Omega }}_i^n(x))\in {\{0,1\}}^n$. Given a strict partial order on these payoff vectors, we define a preference relation ${\prec }_i$ such that $x{\prec }_{i}y$ if and only if  [7]. There exist several strict partial orders on the payoff vectors, like, for example, the lexicographic order, or the counting order, i.e., if and only if . One can check that all preference relations studied in [7] are $\omega$-automatic.

Let us move on to classical quantitative objectives, such as quantitative reachability, limsup or discounted-sum objectives [21, 26]. In this case, an objective for player $i$ is now a function ${\mathrm{\Omega }}_i:V^{\omega }\to \mathbb{Q}\cup \{\pm \mathrm{\infty }\}$.⁵⁵5It can also be a function $\mathrm{\Omega }:E^{\omega }\to \mathbb{Q}\cup \{\pm \mathrm{\infty }\}$. We then define a preference relation ${\prec }_i$ such that $x{\prec }_{i}y$ if and only if . Bansal et al. showed in [2] that such a relation is $\omega$-automatic for a limsup objective and for a discounted-sum objective with an integer discount factor. They also proved that ${\prec }_i$ is not $\omega$-automatic for a mean-payoff objective. The first DPA of Figure 1 where the label on the loop on the vertex with priority $0$ is replaced by $(\ast ,\ast )$, accepts a preference relation ${\prec }_i$ defined from a min-cost-reachability objective as follows: $x{\prec }_{i}y$ if and only if there exists $\mathrm{\ell }$ such that $y_{\mathrm{\ell }}\in T$ and, for all $k$, (player $i$ prefers plays with fewer steps to reach the target set $T$). The variant where player $i$ prefers to maximize the number of steps to reach $T$,⁶⁶6as each step corresponds to a reward. called max-reward-reachability, is accepted by the third DPA in Figure 1.

Hence, there are many ways to envision $\omega$-automatic relations. Note that in our framework, the preference relations ${\prec }_i$ of a game $𝒢$ can vary from one player to another, where each relation ${\prec }_i$ can be defined from a combination of several objectives (see Example 1 below).

A Nash Equilibrium (NE) from an initial vertex $v_0$ is a strategy profile ${({\sigma }_i)}_{i\in 𝒫}$ such that for all players $i$ and all strategies ${\tau }_i$ of player $i$, we have ${⟨\sigma ⟩}_{v_0}{\nprec }_i{⟨{\tau }_i,{\sigma }_{-i}⟩}_{v_0}$, where ${\sigma }_{-i}$ denotes ${({\sigma }_j)}_{j\in 𝒫\setminus \{i\}}$. So, NEs are strategy profiles where no single-player has an incentive to unilaterally deviate from his strategy. When there exists a strategy ${\tau }_i$ such that ${⟨\sigma ⟩}_{v_0}{\prec }_i{⟨{\tau }_i,{\sigma }_{-i}⟩}_{v_0}$, we say that ${\tau }_i$ (or, by notation abuse, ${⟨{\tau }_i,{\sigma }_{-i}⟩}_{v_0}$) is a profitable deviation for player $i$. The set of players $𝒫\setminus \{i\}$ is called coalition $-i$, sometimes seen as one player opposed to player $i$.

In this paper, we investigate the following problems.

Let us state our main results. We consider games $𝒢=(A,{({\prec }_i)}_{i\in 𝒫})$ on the arena $A=(V,E,𝒫,{(V_i)}_{i\in 𝒫})$, where each preference relation ${\prec }_i\subseteq V^{\omega }\times V^{\omega }$ is $\omega$-automatic. We denote by ${𝒜}_i$ the DPA accepting ${\prec }_i$ and by $\{0,1,\mathrm{\dots },d_i\}$ its set of priorities. We say that a problem $L$ is $\mathrm{𝖯𝖺𝗋𝗂𝗍𝗒}$-hard if there exists a polynomial reduction from the problem of deciding the winner of a two-player zero-sum parity game to $L$.

The proofs of these theorems are detailed in the next two sections. In Section 7, we reconsider the studied problems in the special case of games with $\omega$-recognizable relations.

We begin with the membership result. Given the Mealy machines ${ℳ}_i=(M_i,m_0^j,{\alpha }_U^i,{\alpha }_N^i)$, $i\in 𝒫$, and the strategies ${\sigma }_i$ they define, we have to check whether $\sigma ={({\sigma }_i)}_{i\in 𝒫}$ is an NE from a given initial vertex $v_0$. Equivalently, we have to check whether there exists a strategy ${\tau }_i$ for some player $i$ such that ${⟨\sigma ⟩}_{v_0}{\prec }_i{⟨{\tau }_i,{\sigma }_{-i}⟩}_{v_0}$ (in which case $\sigma$ is not an NE). That is, whether there exists $i$ such that the language

is non-empty. We are going to describe a generalized DPA ${ℬ}_i$, with a conjunction of three parity conditions, that accepts $L_i$. We proceed as follows.

1. 1.

   The set $\{(x,y)\in V^{\omega }\times V^{\omega }\mid x{\prec }_{i}y\}$ is accepted by the given DPA ${𝒜}_i$ that accepts ${\prec }_i$.

2. 2.

   The outcome ${⟨\sigma ⟩}_{v_0}$ is a lasso obtained from the product of the arena $A$ and all ${ℳ}_j$. We can define a DPA, of size exponential in the number of players, that only accepts ${⟨\sigma ⟩}_{v_0}$.

3. 3.

   Finally, consider the product $A^{\prime }$ of the arena $A$ with all ${ℳ}_j$, with $j\ne i$. We denote by $V^{\prime }$ the set of vertices of $A^{\prime }$, where each vertex is of the form $(v,{(m_j)}_{j\ne i})$, with $v\in V$ and $m_j$ a memory state of ${ℳ}_j$. The set of plays $y$ consistent with ${\sigma }_{-i}$ and starting at $v_0$ is accepted by a DPA whose set of states is $V^{\prime }\cup \{s_0\}$ with $s_0$, a new state, its initial state, all those states with priority $0$, and whose transition function $\delta$ is such that $\delta ((v,{(m_j)}_{j\ne i}),v^{\prime })=(v^{\prime },{(m_j^{\prime })}_{j\ne i})$ for ${\alpha }_U^j(m_j,v)=m_j^{\prime }$, and $\delta (s_0,v_0)=(v_0,{(m_0^j)}_{j\ne i})$. Note that $\delta$ is a function as each ${ℳ}_j$ is deterministic and that this DPA is of exponential size in the number of players.

The announced automaton ${ℬ}_i$ is the product of the automata defined in the previous steps. It has exponential size and can be constructed on the fly, hence leading to a $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ algorithm. Indeed, to check whether $L_i$ is non-empty, we guess a lasso $\mu {(\nu )}^{\omega }$ and its exponential length, and check whether the guessed lasso is accepted by ${ℬ}_i$. This only requires a polynomial space as the lasso is guessed on the fly, state by state, while computing the maximum priority occurring in $\nu$ for each priority function, and the length $|\mu \nu |$ is stored in binary. Finally, we repeat this procedure for each automaton ${ℬ}_i$, $i\in 𝒫$.

For the $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-hardness, we use a reduction from the membership problem for linear bounded deterministic Turing machines (LBTMs), known to be $\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$-complete [24], to the complement of the NE checking problem. Recall that an LBTM $T$ has a limited memory such that the tape head must remain in the $n$ cells that contain the input word $w$.

We give only a sketch of proof. First, let us show how we encode any configuration of the LBTM. For the current word written on the tape, we associate one player per cell, and we say that the letter in the $i$-th cell, $i\in \{1,\mathrm{\dots },n\}$, is the current memory state of the Mealy machine ${ℳ}_i$ of player $i$. Then we define an arena where each vertex is of the form $(q,i)$, for a state $q$ of $T$ and the current position $i$ of the tape head, and such that player $i$ owns all the vertices $(q,i)$. Second, we simulate transitions of the LBTM with the Mealy machines: ${ℳ}_i$ can describe the next vertex according to its memory state. For example, from vertex $(q,i)$ and memory state $a$ for player $i$, ${ℳ}_i$ moves to vertex $(q^{\prime },i+1)$ and updates its memory state to $a^{\prime }$ if the LBTM says that from state $q$ and letter $a$, the tape head must write $a^{\prime }$ and go right, and that the next state is $q^{\prime }$.

This construction allows us to completely simulate the LBTM with an arena, described in Figure 3. We add an extra player $n+1$ who decides whether to let the other players follow their Mealy machine to simulate the LBTM on the given word, or go to a sink state $\mathrm{\#}$. With his preference relation ${\prec }_{n+1}$, player $n+1$ prefers a play visiting a vertex $(q_{accept},i)$, for any $i$, to any other play. His Mealy machine goes from $v_{init}$ to $\mathrm{\#}$. Thus, the strategy profile given by all Mealy machines is not an NE if and only if it is profitable for player $n+1$ to let the other players simulate the LBTM on $w$, i.e., this simulation visits $q_{accept}$. $◀$

Let us now prove Theorem 4 stating the complexity of the NE outcome checking problem.

Let us begin with the membership result. Given a lasso $\pi$ starting at $v_0$, checking whether $\pi$ is an NE outcome amounts to finding a strategy profile $\sigma ={({\sigma }_i)}_{i\in 𝒫}$ with outcome $\pi$ such that for all $i\in 𝒫$ and all strategies ${\tau }_i$, we have $\pi {\nprec }_i{⟨{\tau }_i,{\sigma }_{-i}⟩}_{v_0}$. In other words, given $\sigma$ a strategy profile partially defined such that $\pi ={⟨\sigma ⟩}_{v_0}$, our goal is to check whether, for all $i$, there exists ${\sigma }_{-i}$ that extends this partially defined profile such that for all ${\tau }_i$, $\pi {\nprec }_i{⟨{\tau }_i,{\sigma }_{-i}⟩}_{v_0}$. For this purpose, we explain the algorithm in $\mathrm{𝖭𝖯}$ $\cap$ $\mathrm{𝖼𝗈𝖭𝖯}$ for one given player $i\in 𝒫$, and then repeat it for the other players.

Let us consider $L_i=\{x\in V^{\omega }\mid \pi {\nprec }_{i}x\}$. This set is accepted by a DPA ${ℬ}_i$ constructed as the product of the complement of ${𝒜}_i$ and the lasso $\pi$. Clearly, the size of ${ℬ}_i$ is polynomially bounded in the sizes of ${𝒜}_i$ and $\pi$. So, $L_i$ contains all the deviations that are not profitable for player $i$ compared to $\pi$. Now, it suffices to decide whether the coalition $-i$ has a strategy ${\sigma }_{-i}$ against player $i$ to ensure that every play consistent with ${\sigma }_{-i}$ lies in $L_i$. As $L_i$ is accepted by the DPA ${ℬ}_i$, this amounts to solving a zero-sum parity game ${\mathscr{H}}_i$ (of polynomial size) defined directly from ${ℬ}_i$. The details are as follows.

Suppose that ${ℬ}_i$ has a set $Q$ of states, an initial state $q_0$, and a transition function ${\delta }_{{ℬ}_i}:Q\times V\to Q$. Let us define the game ${\mathscr{H}}_i$, where the two players are $A$ and $B$. Its set of vertices is the Cartesian product $V\times Q$, such that player $A$ (resp. player $B$) controls the vertices $(v,q)$ with $v\in V_i$ (resp. $v\notin V_i$). In other words, $A$ has the role of player $i$ while $B$ has the role of the coalition $-i$. As ${ℬ}_i$ is deterministic, it is seen as an observer, and its states are information added to the vertices of $V$. Hence, the edges of ${\mathscr{H}}_i$ are of the form $((v,q),(v^{\prime },q^{\prime }))$ such that $(v,v^{\prime })\in E$ and $q^{\prime }={\delta }_{{ℬ}_i}(q,v)$. We define a parity objective for player $B$ as follows: the priority of each vertex $(v,q)$ of ${\mathscr{H}}_i$ is equal to the priority of $q$ in ${ℬ}_i$. Consequently, a play in ${\mathscr{H}}_i$ is won by player $B$ if and only if the projection on its first component belongs to $L_i$. For the constructed game ${\mathscr{H}}_i$, from every vertex $(v,q)$, we can decide in $\mathrm{𝖭𝖯}$ $\cap$ $\mathrm{𝖼𝗈𝖭𝖯}$ which player wins in ${\mathscr{H}}_i$ together with a memoryless winning strategy for that player [26].

To obtain an algorithm in $\mathrm{𝖭𝖯}$, it remains to check whether $\pi$, seen as a lasso in ${\mathscr{H}}_i$, only crosses vertices $(v,q)$ that are winning for player $B$ whenever $v\in V_i$. Indeed, in this case, we can deduce from a winning strategy ${\tau }_B$ from $(v,q)$ for player $B$, a strategy ${\sigma }_{-i}$ for the coalition $-i$ such that for all ${\tau }_i$, $\pi {\nprec }_i{⟨{\tau }_i,{\sigma }_{-i}⟩}_{v_0}$. Similarly, to obtain an algorithm in $\mathrm{𝖼𝗈𝖭𝖯}$, we check whether $\pi$ in ${\mathscr{H}}_i$ crosses at least one vertex $(v,q)$ that is winning for player $A$ and deduce a winning strategy for player $i$.

We continue with the hardness result, with a reduction from the problem of deciding whether player $1$ has a winning strategy in a zero-sum parity game. We reduce this problem to the complement of the NE outcome checking problem, to establish its $\mathrm{𝗉𝖺𝗋𝗂𝗍𝗒}$-hardness. Let $\mathscr{H}$ be a parity game with players $1$ and $2$, an arena $A$ with $V$ as set of vertices, an initial vertex $v_0$, and a priority function $\alpha :V\to \{0,\mathrm{\dots },d\}$. We construct a new game $𝒢=(A^{\prime },{\prec }_1,{\prec }_2)$ with the same players, whose arena $A^{\prime }$ is a copy of $A$ with an additional vertex $v_0^{\prime }$ owned by player $1$, with $v_0$ and itself as successors (see Figure 5). Given $V^{\prime }=V\cup \{v_0^{\prime }\}$, the preference relation ${\prec }_2$ is empty, accepted by a one-state DPA, while the preference relation ${\prec }_1$ is defined as follows: $x{\prec }_{1}y$ if and only if $x={(v_0^{\prime })}^{\omega }$ and $y={(v_0^{\prime })}^m{y}^{\prime }$, with $m\ge 0$ and $y^{\prime }$ is a play in $\mathscr{H}$ starting at $v_0$ and satisfying the parity condition $\alpha$. A DPA ${𝒜}_1$ accepting ${\prec }_1$ is depicted in Figure 5, it is constructed with a copy of the arena $A$ and a new state $q_0$ with priority 1.

The proposed reduction is correct. Indeed, suppose that $\pi ={(v_0^{\prime })}^{\omega }$ is not an NE outcome. As ${\prec }_2$ is empty, there cannot be profitable deviations for player $2$. This means that for each strategy profile $\sigma =({\sigma }_1,{\sigma }_2)$ with outcome $\pi$, there exists a deviating strategy ${\tau }_1$ of player $1$ such that $\pi {\prec }_1\rho$ with $\rho ={⟨{\tau }_1,{\sigma }_2⟩}_{v_0^{\prime }}$. Thus, by definition of ${\prec }_1$, $\rho$ is equal to ${(v_0^{\prime })}^m{\rho }^{\prime }$ with ${\rho }^{\prime }$ a winning play in $\mathscr{H}$. Hence, transferred to $\mathscr{H}$, we get that for each strategy ${\sigma }_2^{\prime }$ of player $2$, there exists a strategy ${\tau }_1^{\prime }$ of player $1$ such that ${⟨{\tau }_1^{\prime },{\sigma }_2^{\prime }⟩}_{v_0}$ is winning. By determinacy, player $1$ has thus a winning strategy in $\mathscr{H}$ from $v_0$. The other direction is proved similarly, if player $1$ has a winning strategy in $\mathscr{H}$, then transferring this strategy to $𝒢$ gives a profitable deviation from a strategy with outcome $\pi$. $◀$

By Theorem 7, deciding whether there exists an NE from $v_0$ in $𝒢$ reduces to deciding whether there exists an observation-based strategy ${\tau }_{{\mathbb{P}}_1}$ of ${\mathbb{P}}_1$ in ${\mathbb{P}}_1ℂ{\mathbb{P}}_2(𝒢)$ such that for all strategies ${\tau }_{ℂ}$ of $ℂ$, there is a strategy ${\tau }_{{\mathbb{P}}_2}$ of ${\mathbb{P}}_2$ such that ${⟨{\tau }_{{\mathbb{P}}_1},{\tau }_{ℂ},{\tau }_{{\mathbb{P}}_2}⟩}_{s_0}\in W_{{\mathbb{P}}_1{\mathbb{P}}_2}$. In [16], the authors solve the problem they study by solving a similar three-player game with imperfect information. They proceed at follows: (i) the winning condition is translated into a Rabin condition¹²¹²12Recall that a Rabin condition uses a finite set of pairs ${(E_j,F_j)}_{j\in J}$ in a way to accept plays $\pi$ such that there exists $j\in J$ with $\mathrm{𝖨𝗇𝖿}(\pi )\cap E_j=\mathrm{\varnothing }$ and $\mathrm{𝖨𝗇𝖿}(\pi )\cap F_j\ne \mathrm{\varnothing }$. on the arena of the ${\mathbb{P}}_1$$ℂ$${\mathbb{P}}_2$ game, (ii) the three-player game is transformed into a two-player zero-sum Rabin game with imperfect information, and finally (iii) classical techniques to remove imperfect information are used to obtain a two-player zero-sum parity game with perfect information.

In this sketch of proof, we only explain the first step, i.e., how to translate $W_{{\mathbb{P}}_1{\mathbb{P}}_2}=W_{acc}\cup W_{dev}$ into a Rabin condition, as the second and third steps heavily use the arguments of [16]. To translate $W_{acc}$, we use one pair $(E_1,F_1)$ such that $E_1=\mathrm{\varnothing }$ and $F_1=\{s\in S\mid \mathrm{𝖽𝖾𝗏}(s)=\perp \}$. To translate $W_{dev}$, notice that $\mathrm{𝖽𝖾𝗏}(\pi )=j$ is equivalent to $\mathrm{𝖽𝖾𝗏}(\pi )\notin \{\perp \}\cup 𝒫\setminus \{j\}$, and thus $W_{dev}={\cup }_{j\in 𝒫}\{\pi \in \mathrm{𝖯𝗅𝖺𝗒𝗌}({\mathbb{P}}_1ℂ{\mathbb{P}}_2(𝒢))\mid \mathrm{𝖽𝖾𝗏}(\pi )\notin \{\perp \}\cup 𝒫\setminus \{j\}\text{ and }{\mathrm{𝗉𝗋𝗈𝗃}}_{V,1}(\pi ){\nprec }_j{\mathrm{𝗉𝗋𝗈𝗃}}_{V,2}(\pi )\}$. Recall that each relation ${\prec }_j$ is accepted by the DPA ${𝒜}_j$ with the priority function ${\alpha }_j:Q_j\to \{0,1,\mathrm{\dots }{d}_j\}$, thus also ${\nprec }_j$ with the modified priority function ${\alpha }_j+1$. Therefore, $W_{dev}$ can be translated into a Rabin condition on the vertices of $S$ with ${\mathrm{\Sigma }}_{j\in 𝒫}{d}_j$ Rabin pairs [32]. Steps (ii) and (iii) are detailed in the long version [15], leading to the announced complexity: the NE existence problem is exponential in $|V|$, ${\mathrm{\Pi }}_{i\in 𝒫}|{𝒜}_i|$, and ${\mathrm{\Sigma }}_{{}_{i\in 𝒫}}{d}_i$. $◀$

Let us finally comment on Theorem 6 stating the complexity class of the constrained NE existence problem. The detailed proof is presented in the long version of this paper [15]. The approach to proving membership is very similar to that of the NE existence problem, as we only need to modify $W_{acc}$ in a way to include the constraints imposed on the NE outcome. A constraint imposed by a lasso ${\pi }_i$ can be represented by a DPA ${𝒜}_i^{\prime }$ accepting the language $\{\rho \in V^{\omega }\mid {\pi }_i{\prec }_i\rho \}$, with a polynomial size $|{𝒜}_i|\cdot |{\pi }_i|$. Then it suffices to extend the arena the ${\mathbb{P}}_1$$ℂ$${\mathbb{P}}_2$ game with the states of each ${𝒜}_i^{\prime }$. The hardness result is obtained by a reduction from the NE existence problem, already for one-player games.

Note that by steps (i)-(iii), solving the (constrained) NE existence problem is equivalent to solving a zero-sum parity game with memoryless winning strategies for both players. Therefore, we get the following property:

There is a great interest in using the concept of ${\mathbb{P}}_1$$ℂ$${\mathbb{P}}_2$ game, as it provides a unified approach to solve the NE existence problem and its constrained variant. With this approach, we could also decide the existence of an NE whose outcome $\rho$ satisfies various combinations of constraints, such as, e.g., ${\pi }_i{\prec }_i\rho {\prec }_i{\pi }_i^{\prime }$ for one or several players $i$. The chosen constraints only impact the winning condition $W_{{\mathbb{P}}_1{\mathbb{P}}_2}$ and thus its translation into a Rabin condition.

Given a relation $R\subseteq {\mathrm{\Sigma }}^{\omega }\times {\mathrm{\Sigma }}^{\omega }$, it is:

• $\mathrm{■}$

  reflexive (resp. irreflexive) if for all $x\in {\mathrm{\Sigma }}^{\omega }$, we have $(x,x)\in R$ (resp. $(x,x)\notin R$),

• $\mathrm{■}$

  transitive (resp. $\neg$-transitive) if for all $x,y,z\in {\mathrm{\Sigma }}^{\omega }$, we have $(x,y)\in R\wedge (y,z)\in R\Rightarrow (x,z)\in R$ (resp. $(x,y)\notin R\wedge (y,z)\notin R\Rightarrow (x,z)\notin R$),

• $\mathrm{■}$

  total if for all $x,y\in {\mathrm{\Sigma }}^{\omega }$, we have $(x,y)\in R\vee (y,x)\in R$,

A reflexive and transitive relation is a preorder. An irreflexive and transitive relation is a strict partial order. When, in addition, a strict partial order $R$ is $\neg$-transitive, it is a strict weak order. The next proposition states that all the relevant properties mentioned above can be efficiently verified on the DPA accepting the relation $R$. It is proved in the long version [15].

Let us first observe that all the lower bounds established for the decision problems about NEs remain valid even when the players’ preference relations $R_i$ are assumed to be strict partial orders.¹³¹³13The upper bounds do not need more than the $\omega$-automaticity of each $R_i$ This implies that taking this additional property into account does not yield any important advantage in terms of complexity class.

We now consider an alternative setting in which each relation $R_i$ is not a strict preference, but rather a preorder (where some plays are declared equivalent). To discuss this further, let us recall the relationship between strict partial orders and preorders. From a strict partial order $\prec$, one can obtain a preorder $\precsim$ by taking its reflexive closure, i.e., $x\precsim y$ if $x\prec y$ or $x=y$. When $\prec$ is a strict weak order, another preorder which is total, is obtained by defining $x\precsim y$ if $y\nprec x$. In both cases, if $\prec$ is $\omega$-automatic, $\precsim$ is also $\omega$-automatic (resp. by a generalized DPA with a disjunction of two parity conditions, or by a DPA). Conversely, from any preorder $\precsim$, we can define a strict partial order $\prec$ such that $x\prec y$ if $x\precsim y\wedge y\precsim ̸x$. Every strict partial order can be constructed this way. Moreover, if $\precsim$ is total, then $\prec$ is a strict weak order. We can also define the equivalence relation $\sim$ such that $x\sim y$ if $x\precsim y\wedge y\precsim x$. The equivalence class of $x$ is denoted $[x]$. Again, if $\precsim$ is $\omega$-automatic, then $\prec$ and $\sim$ are both $\omega$-automatic (by a generalized DPA with a conjunction of two parity conditions).