We introduce and study pawn games, a class of two-player zero-sum turn-based graph games. A turn-based graph game proceeds by placing a token on an initial vertex, and whoever controls the vertex on which the token is located, chooses its next location. This leads to a path in the graph, which determines the winner. Traditionally, the control of vertices is predetermined and fixed.
The novelty of pawn games is that control of vertices changes dynamically throughout the game as follows.
Each vertex of a pawn game is owned by a pawn. In each turn, the pawns are partitioned between the two players, and the player who controls the pawn that owns the vertex on which the token is located, chooses the next location of the token.
Control of pawns changes dynamically throughout the game according to a fixed mechanism.
Specifically, we define several grabbing-based mechanisms in which control of at most one pawn transfers at the end of each turn. We study the complexity of solving pawn games, where we focus on reachability objectives and parameterize the problem by the mechanism that is being used and by restrictions on pawn ownership of vertices.
On the positive side, even though pawn games are exponentially-succinct turn-based games, we identify several natural classes that can be solved in PTIME.
On the negative side, we identify several $\EXP$-complete classes, where our hardness proofs are based on a new class of games called games, which may be of independent interest.

We consider two-player zero-sum graph games. In a turn-based game, the vertices are partitioned between the two players. The game proceeds by placing a token on an initial vertex, and whoever controls the vertex on which the token is located, chooses its next location. Traditionally, the control of vertices is predetermined and fixed.
We introduce and study pawn games, in which vertex control changes dynamically throughout the game as follows.
Each vertex of a pawn game is owned by a pawn. In each turn, the pawns are partitioned between the two players, and the player who controls the pawn that owns the vertex on which the token is located, chooses the next location of the token.
Control of pawns changes dynamically throughout the game according to a fixed mechanism.

Specifically, we define several grabbing-based mechanisms in which control of at most one pawn transfers at the end of each turn. We focus on reachability games. We study the complexity of solving pawn games, where we parameterize the problem by the mechanism that is being used and by restrictions on pawn ownership of vertices.
On the positive side, even though pawn games are exponentially-succinct turn-based games, we identify several natural classes that can be solved in PTIME.
On the negative side, we identify several $\EXP$-complete classes, where our hardness proofs are based on a new class of games called games, which may be of independent interest.

We consider pawn games that are two-player turn-based zero-sum games played between and in which the control of the vertices changes dynamically throughout the game.
Pawn games are motivated naturally in settings where a set of pawns owning resources are controlled by different players in different rounds of the turn-based game.
A game consists of a set of pawns and each pawn owns a set of non-empty vertices.
In any round of the game, controls a set of pawns while controls the rest.
The pawns are transferred from one player to another based on based on transfer rules called mechanisms.
We consider several mechanisms for transferring pawns from one player to the other.
We study reachability objective and show that different mechanisms may result into solving the games with different complexity ranging from $\PTIME$ to $\EXP$-complete.
We also show that complexity results vary based on whether a pawn owns a single vertex or multiple vertices or whether a vertex can be owned by multiple pawns.
Our $\EXP$-hardness results are based on a class of games which we call games which can be of independent interest for studying game on graphs in general.

§ INTRODUCTION

Two-player zero-sum graph games constitute a fundamental class of games <cit.> with applications, e.g., in reactive synthesis <cit.>, multi-agent systems <cit.>, a deep connections to foundations of logic <cit.>, and more.
A graph game is played on a directed graph $\zug{V, E}$, where $V = V_1 \cup V_2$ is a fixed partition of the vertices.
The game proceeds as follows. A token is initially placed on some vertex. When the token is placed on $v \in V_i$, for $i \in \set{1,2}$, chooses $u$ with $\zug{v, u} \in E$ to move the token to.

The outcome of the game is an infinite path, called a play. We focus on reachability games: wins a play iff it visits a set of target vertices $T \subseteq V$.

In this paper, we introduce pawn games, which are graph games in which the control of vertices changes dynamically throughout the game as follows.
The arena consists of $d$ pawns. For $1 \leq j \leq d$, Pawn $j$ owns a set of vertices $V_j$. Throughout the game, the pawns are distributed between the two players, and in each turn, the control of pawns determines which player moves the token. Pawn control may be updated after moving the token by running a predetermined mechanism.
Formally, a configuration of a pawn game is a pair $\zug{v, P}$, where $v$ denotes the position of the token and $P$ the set of pawns that controls. The player who moves the token is determined according to $P$: if controls a pawn that owns $v$, then moves. Specifically, when each vertex is owned by a unique pawn, i.e., $V_1,\ldots, V_d$ partitions $V$, then moves iff he controls the pawn that owns $v$.

We consider the following mechanisms for exchanging control of pawns.
For $i \in \set{1,2}$, we denote by $\ni= 3-i$ the “other player”.

* Optional grabbing. For $i \in \set{1,2}$, following a move, has the option to grab one of 's pawns; namely, transfer one of the pawns that to his control.

* Always grabbing. For $i \in \set{1,2}$, following every move, grabs one of 's pawns.

* Always grabbing or giving. Following a move, either grabs one of 's pawns or gives her one of his pawns.

* $k$-grabbing.

For $k \in \Nat$, can grab at most $k$ pawns from throughout the game.
In each round, after moving the token, has the option of grabbing one of the pawns that is controlled by .
A grabbed pawn stays in the control of for the remainder of the game.

Note the asymmetry: only grabs pawns.

Note that players in pawn games have two types of actions: moving the token and transferring control of pawns. We illustrate the model and some interesting properties of it.

Consider the game $\G_1$ in Fig. <ref>(left). We consider optional-grabbing and the same reasoning applies for always-grabbing.
Each vertex is owned by a unique pawn, and 's target is $t$. Note that wins if the game reaches $s$. We claim that $\G_1$ is non-monotonic: increasing the set of pawns that initially controls is “harmful” for him. Formally, wins from configuration $\zug{v_0, \emptyset}$, i.e., when he initially does not control any pawns,
but loses from $\zug{v_0, \set{v_0}}$, i.e., when controlling $v_0$. Indeed, from $\zug{v_0, \emptyset}$, initially moves the token from $v_0$ to $v_1$, then uses his option to grab $v_1$, and wins by proceeding to $t$. Second, from $\zug{v_0, \set{v_0}}$, makes the first move and thus cannot grab $v_1$. Since controls $v_1$, she wins by proceeding to $s$.
In Thm. <ref> and <ref>, we generalize this observation and show, somewhat surprisingly, that if a player wins from the current vertex $v$, then he wins from $v$ with fewer pawns as long as if he controlled $v$ previously, then he maintains control of $v$.

Consider the game $\G_2$ in Fig. <ref> (right). We consider optional-grabbing, each vertex is owned by a unique pawn, and 's target is $t$. We claim that wins from configuration $\zug{v_0, \set{v_0, v_2}}$ and can force the game to visit $v_1$ twice. This differs from turn-based games in which if wins, he can force winning while visiting each vertex at most once. To illustrate, consider the following outcome. makes the first move, so he cannot grab $v_1$. avoids losing by moving to $v_2$. will not grab, move to $v_3$, moves to $v_1$, then grabs $v_1$ and proceeds to $t$.
We point out that no loop is closed in the explicit configuration graph that corresponds to $\G_2$.

Consider the game $\G_2$, depicted in Fig. <ref>. We consider always-grabbing, each vertex is owned by a unique pawn, and 's target is $t$. We claim that wins from configuration $\zug{v_0, \set{v_0, v_2}}$ and can force the game to visit $v_1$ twice. This differs from turn-based games in which there exists a winning strategy that guarantees that each vertex is visited at most once. We describe an outcome of the game. makes the first move, so he cannot grab $v_1$.
grabs either $v_0$ or $v_2$ and avoids losing by moving to $v_2$.
grabs $v_1$ in both cases.
moves from $v_2$ if grabbed $v_2$ in the previous step, otherwise moves from $v_2$.
In both cases, has a strategy such that he never grabs $v_3$ and thus moves from $v_3$.
Even if $\PO$ moved from $v_2$ and $\PT$ grabbed $v_1$ back from $\PO$, following 's move from $v_3$, can grab $v_1$ and move to $t$.
It is not hard to see that is playing according to a winning strategy and that he cannot force reaching $t$ without visiting $v_1$ twice. We point out that no loop is closed in the explicit configuration graph that corresponds to $\G_2$.

@xc/pgf/inner xsep
@x by 2@xc
@xb/pgf/minimum width

@y by
@yc/pgf/inner ysep
@y by 2@yc
@yb/pgf/minimum height

@x by.5
@xa/pgf/outer xsep
@x by#1@xa
@y by-.5
@y by.5
@ya/pgf/outer ysep
@y by#1@ya

in east,west in north,mid,base,south

in east,west,north,mid,base,south,center,text

[node distance=8mm,initial text = ,main/.style = draw, circle, text=black, inner sep=1pt]
[main,initial] (1) $v_0$;
[main] (2) [right of=1] $v_1$;
[main] (3) [right of=2] $s$;
[main,accepting] (4) [right of=3] $t$;
[->] (1) – (2);
[->] (2) – (3);
[->] (2) to [out=320,in=240,looseness=1] (4);

[node distance=8mm,initial text = ,main/.style = draw, circle, text=black, inner sep=1pt,gain/.style = draw, square, text=black, inner sep=1pt]
[main,initial] (1) $v_0$;
[gain] (2) [right of=1] $v_1$;
[main,accepting] (3) [right of=2] $t$;

[main] (5) [below left of=2] $v_2$;
[gain] (6) [below right of=2] $v_3$;
[->] (1) – (2);
[->] (2) – (5);
[->] (5) – (6);
[->] (6) – (2);
[->] (2) – (3);

Left: The pawn game $\G_1$; a non-monotonic game under optional-grabbing. Right: The pawn game $\G_2$ in which wins from $\zug{v_0, \set{v_0, v_1}}$, but must visit $v_1$ twice.

[node distance=8mm,initial text = ,main/.style = draw, circle, text=black, inner sep=1pt]
[main,initial] (1) $v_0$;
[main] (2) [right of=1] $v_1$;
[main,accepting] (3) [right of=2] $t$;

[main] (4) [above of=2] $v_4$;
[main] (5) [below left of=2] $v_2$;
[main] (6) [below right of=2] $v_3$;
[->] (1) – (2);
[->] (2) – (5);
[->] (5) – (6);
[->] (6) – (2);
[->] (2) – (3);
[->] (4) – (3);
[->] (4) – (2);

The pawn game $\G_1$; a non-monotonic game under optional-grabbing.

Pawn games model multi-agent settings in which the agent who acts in each turn is not predetermined. We argue that such settings arise naturally.

Quantitative shield synthesis.
It is common practice to model an environment as a Kripke structure (e.g. <cit.>), which for sake of simplicity, we will think of as a graph in which vertices model environment states and edges model actions. A policy chooses an outgoing edge from each vertex. A popular technique to obtain policies is reinforcement learning (RL) <cit.> whose main drawback is lack of worst-case guarantees <cit.>. In order to regain safety at runtime, a shield <cit.> is placed as a proxy: in each point in time, it can alter the action of a policy. The goal in shield synthesis is to synthesize a shield offline that ensures safety at runtime while minimizing interventions. We suggest a procedure to synthesize shields based on $k$-grabbing pawn games. models an unknown policy.

We set his goal to reaching an unsafe state.
(the shield) ensures safety by grabbing at most $k$ times. Grabbing is associated with a shield intervention. Note that once the shield intervenes in a vertex $v$, it will choose the action at $v$ in subsequent turns.
An optimal shield is obtained by finding the minimal $k$ for which has a winning strategy.

We describe other examples that can be captured by a $k$-grabbing pawn game in which, as in the shield application, models an “authority” that has the “upper hand”, and aims to maximize freedom of action for while using grabs to ensure safety. Consider a concurrent system in which models a scheduler and can force synchronization, e.g., by means of “locks” or “fences” in order to maintain correctness (see <cit.>). Synchronization is minimized in order to maximize parallelism and speed. As another example, might model an operating system that allows freedom to an application and blocks only unsafe actions.

As a final example, in <cit.>, synthesis for a safety specification was enriched with “advice” given by an external policy for optimizing a soft quantitative objective. Again, the challenge is how to maximize accepting advice while maintaining safety.

Pawn games naturally model ongoing decision-making setting in which resources are transferable. We describe several concrete examples.

A controller is a strategy to interact with a plant. At each point in time, the plant outputs its state and in response, the controller issues an action.
One popular technique to obtain controllers is reinforcement learning (RL) <cit.> whose main drawback is lack of worst-case guarantees <cit.>.

In order to regain safety, a shield <cit.> is placed as a runtime monitor that can alter a controller's unsafe actions. A challenge in shield synthesis is to synthesize a shield offline which ensures that a given safety specification $\phi$ is satisfied while minimizing its interventions on the controller policy.
We suggest a procedure for shield synthesis based on pawn games. Each vertex of the game represents a plant state, each edge represents an action, and the safety objective is obtained from $\phi$. models the trained controller. Each vertex is owned by a unique pawn and initially controls all pawns. is allowed to grab $k$ times. A winning strategy corresponds to a shield; namely, grabbing a vertex $v$ is associated with choosing the action in the corresponding state, thereby modifying the controller action.

In order to obtain an optimal shield, we find the minimal $k$ for which has a winning strategy that ensures safety while intervening in at most $k$ states no matter how the trained controller behaves.

Modelling crashes.
A sabotage game <cit.> is a two-player game which is played on a graph. (the Runner) moves a token throughout the graph with the goal of reaching a target set. In each round, (the Saboteur) crashes an edge from the graph with the goal of preventing from reaching his target.

Crashes are a simple type of fault that restrict 's actions. A malicious fault (called byzantine faults <cit.>) actively tries to harm the network, e.g., by moving away from the target.
Pawn games can model sabotage games with byzantine faults: each vertex (router) is owned by a unique pawn, all pawns are initially owned by , and a grab corresponds to a byzantine fault.

Several grabbing mechanisms are appealing in this context: $k$-grabbing restricts the number of faults and optional- and always-grabbing accommodate  repairs of routers.

*Our results
We distinguish between three types of ownership of vertices. Let $V = V_1 \cup \ldots \cup V_d$ be a set of vertices, where for $j \in \set{1,\ldots, d}$, Pawn $j$ owns the vertices in $V_j$.
In one vertex per pawn (OVPP) games, each pawn owns exactly one vertex, thus $V_j$ is a singleton, for all $j \in \set{1,\ldots, d}$. In multiple vertices per pawn (MVPP) games, $V_1,\ldots,V_d$ consists of a partition of $V$, where the sets might contain more than one vertex. In overlapping multiple vertices per pawn (OMVPP) games, the sets might overlap. For example, in the shield synthesis application above, the type of ownership translates to dependencies between interventions: OVPP models no dependencies, MVPP models cases in which interventions come in “batches”, e.g., grabbing control in all states labeled by some predicate, and OMVPP models the case when the batches overlap.
We define that moves the token from a vertex $v$ iff he controls at least one of the pawns that owns $v$. Clearly, OMVPP generalizes MVPP, which in turn generalizes OVPP.

We consider the problem of deciding whether wins a reachability pawn game from an initial configuration of the game. Our results are summarized below.

Mechanisms     OVPP     MVPP     OMVPP

$k$-grabbing     c]@l@PTIME (Thm. <ref>)

NP-hard (Thm. <ref>)     PSPACE-C (Thm. <ref>)

Optional-grabbing     PTIME (Thm. <ref>)     EXPTIME-C (Thm. <ref>)     EXPTIME-C (Thm. <ref>)

Always     c]@l@PTIME
(grab or give; Thm. <ref>)      c]@l@PTIME (grab or give; Thm. <ref>)
EXPTIME-C (grab; Thm. <ref>)     EXPTIME-C (grab; Thm. <ref>)

Pawn games are succinctly-represented turn-based games. A naive algorithm to solve a pawn game constructs and solves an explicit turn-based game on its configuration graph leading to membership in $\EXP$.
We thus find the positive results to be pleasantly surprising; we identify classes of succinctly-represented games that can be solved in PTIME. Each of these algorithms is obtained by a careful and tailored modification to the attractor-computation algorithm for turn-based reachability games. For OMVPP $k$-grabbing, the PSPACE upper bound is obtained by observing that grabs in a winning strategy must be spaced by at most $|V|$ turns, implying that a game ends within polynomial-many rounds (Lem. <ref>).

Our $\EXP$-hardness proofs are based on a new class of games called  games and may be of independent interest. A game is a turn-based game that is enriched with a set of locks, where each lock is associated with a key.
Each edge is labeled by a subset of locks and keys. A lock can either be closed or open. An edge that is labeled with a closed lock cannot be crossed. A lock changes state once an edge labeled by its key is traversed.
We show two reductions. The first shows that deciding the winner in games is $\EXP$-hardness. Second, we reduce games to MVPP optional-grabbing pawn games. The core of the reduction consists of gadgets that simulate the operation of locks and keys using pawns. Then, we carefully analyze the pawn games that result from applying both reductions one after the other, and show that the guarantees are maintained when using always grabbing instead of optional grabbing.
The main difficulty in constructing a winning strategy under always-grabbing from a winning strategy under optional-grabbing is to ensure that throughout the game, both players have sufficient and the correct pawns to grab (Lem. <ref>).

(DRAFT) Pawn games capture the dynamics in which the pawns control specific resources that may be useful for the players, and throughout the game, a  resource may change hands, that is, at different points in time, a particular resource may be controlled by different players.
The various mechanisms described in the paper also capture inter-dependencies among the resources in the sense that acquiring some resources at some time may prevent a player from acquiring certain other resources in future.

*Related work
The semantics of pawn games is inspired by the seminal paper <cit.>.
There, the goal is, given a game, an objective $O$, and a set $C$ of pawns (called “players” there), to decide whether (called a “coalition” there) can ensure $O$ when he controls the pawns in $C$.
A key distinction from pawn games is that the set $C$ that is controlled by is fixed. The paper introduced
a logic called alternating time temporal logic, which was later significantly extended and generalized to strategy logic <cit.>.

Multi-player games with rational players have been widely studied; e.g., finding Nash equilibrium <cit.> or subgame perfect equilibrium <cit.>, and rational synthesis <cit.>.
A key distinction from pawn games is that, in pawn games, as the name suggests, the owners of the resources (pawns) have no individual goals and act as pawns in the control of the players. Changes to multi-player graph games in order to guarantee existence or improve the quality of an equilibrium
have been studied <cit.>. The key difference from our approach is that there, changes occur offline, before the game starts, whereas in pawn games, the transfer of vertex ownership occurs online.
In bidding games <cit.> (see in particular, discrete-bidding games <cit.>) control of vertices changes online: players have budgets, and in each turn, a bidding determines which player moves the token.
Bidding games are technically very different from pawn games. While pawn games allow varied and fine-grained mechanisms for transfer of control, bidding games only consider strict auction-based mechanisms, which lead to specialized proof techniques that cannot be applied to pawn games. For example, bidding games are monotonic – more budget cannot harm a player – whereas pawn games are not (see Ex. <ref>).

In order to express the coalitions and their goals Alternating Temporal Logic (ATL) was defined. To illustrate, the formula $\langle \langle C \rangle \rangle \phi$ denotes the property that the coalition of pawns $C$ can ensure that the LTL formula $\phi$ is satisfied in any play that arises from an interaction with the coalition of pawns not in $C$.

Here we draw an analogy between pawn games and alternating time temporal logic (ATL).
ATL considers multiple players where a subset of them forms a coalition and the players in the subset play against the other players in order to satisfy an objective.
For a coalition $A$, the formula $\langle \langle A \rangle \rangle \phi$ denotes the property that the players in $A$ can ensure $\phi$ no matter how the rest of the players behave.
Note that in ATL, a coalition is decided in the beginning of a play, and remains fixed throughout the play.
Thus ATL can be considered as a pawn game with a mechanism in which the pawns are not allowed to switch sides once the initial set of pawns belonging to Player $1$ is fixed.

Strategy logic:

Non-zero-sum graph games: in rational synthesis <cit.>, is a designated player who represents the synthesized controller and the rest of the players, each with their own objective represents a “rational” environment. Rational verification has also been well studied <cit.>. This leads to a non-zero-game, and an appropriate solution concept needs to be chosen. Nash equilibrium is most commonly used, and it was studied in turn-based games <cit.> as well as concurrent games <cit.>. More recently, subgame perfect equilibrium has been considered in graph games <cit.>, which eliminates a key drawback of Nash equilibrium, non-credible threats.

§ PRELIMINARIES

For $k \in \Nat$, we use $[k]$ to denote the set $\set{1, \dots, k}$.

For $i \in \set{1,2}$, we use $\ni = 3-i$ to refer to the “other player”.

*Turn-based games
Throughout this paper we consider reachability objectives. For general graph games, see for example <cit.>.
A turn-based game is $\G = \zug{V, E, T}$, where $V = V_1 \cup V_2$ is a set of vertices that is partitioned among the players, $E \subseteq V \times V$ is a set of directed edges, and $T \subseteq V$ is a set of target vertices for . 's goal is to reach $T$ and 's goal is to avoid $T$. For $v \in V$, we denote the neighbors of $v$ by $N(v) = \set{u \in V: E(v,u)}$.

Intuitively, a strategy is a recipe for playing a game: in each vertex it prescribes a neighbor to move the token to.
Formally, for $i \in \set{1, 2}$, a strategy for is a function $f: V_i \rightarrow V$ such that for every $v \in V_i$, we have $f(v) \in N(v)$.[We restrict to memoryless strategies since these suffice for reachability objectives.]
An initial vertex $v_0 \in V$ together with two strategies $f_1$ and $f_2$ for the players, give rise to a unique play, denoted $\pi(v_0,f_1,f_2)$, which is a finite or infinite path in $\G$ and is defined inductively as follows. The first vertex is $v_0$. For $j \geq 0$, assuming $v_0,\ldots, v_j$ has been defined, then $v_{j+1} = f_i(v_j)$, where $v_j \in V_i$, for $i \in \set{1,2}$. A strategy $f_1$ is winning from $v_0 \in V$ if for every strategy $f_2$, the play $\play(v_0, f_1, f_2)$ ends in $T$. Dually, a strategy $f_2$ is winning from $v_0 \in V$ if for every strategy $f_1$, the play $\play(v_0, f_1, f_2)$ does not visit $T$.

The game proceeds as follows. A token is placed on a designated initial vertex $v_0$. When the token is placed on $v \in V_i$ for $i \in \set{1,2}$, then chooses a neighbor $u \in N(v)$ to move the token to.
The outcome of the game is a play, which is a finite or infinite path in $\G$.
wins plays that end in $T$, and wins plays that do not visit $T$.
A history is a finite sequence of vertices $h = v_0,v_1,\ldots, v_n \in V^*$. Let $\last(h)$ denote the vertex $v_n$.

For $i \in \set{1,2}$, a strategy for is a function $f_i: V^*\cdot V_i \rightarrow V$, where for every history $h$ with $\last(h) \in V_i$, we require that $f_i(h) \in N(\last(h))$.

We say that $f_i$ is memoryless if it only depends on the last location of the history; namely, for every pair of histories $h$ and $h'$ such that $\last(h)=\last(h')$, we have $f_i(h)=f_i(h')$.
A game $\G = \zug{V, E,T}$, a starting vertex $v_0$, and a pair of strategies $f_1$ and $f_2$ for the two players, give rise to a unique play denoted by $\pi(v_0,f_1,f_2)$.
A strategy $f_1$ is winning for from $v_0 \in V$ if for every strategy $f_2$, the play $\play(v, f_1, f_2)$ is winning for , and the definition for is dual.
We say that wins from $v_0$ if he has a winning strategy from $v_0$. The following is a standard result on reachability turn-based games (e.g., <cit.>).

<cit.> Turn based games are determined: from each vertex, one of the players has a (memoryless) winning strategy.  Deciding the winner of a game is in PTIME.

For completeness, we briefly describe the classic attractor-computation algorithm. Consider a game $\zug{V, E, T}$. Let $W_0 = T$. For $i \geq 1$, let $W_i = W_{i-1} \cup \set{v \in V_1: N(v) \cap W_i \neq \emptyset} \cup \set{v \in V_2: N(v) \subseteq W_i}$. One can prove by induction that $W_i$ consists of the vertices from which can force reaching $T$ within $i$ turns. The sequence necessarily reaches a fixed point $W^1 = \bigcup_{i \geq 1} W_i$, which can be computed in linear time. Finally, one can show that has a winning strategy from each $v \notin W^1$.

*Pawn games
A pawn game with $d \in \Nat$ pawns is $\P = \zug{V, E, T, \M}$, where $V = V_1 \cup \ldots \cup V_d$ and for $j \in [d]$, $V_j$ denotes the vertices that Pawn $j$ owns, $E$ and $T$ are as in turn-based games, and $\M$ is a mechanism for exchanging pawns as we elaborate later. wins a play if it reaches $T$. We stress that  the set of pawns that he controls when reaching $T$ is irrelevant. We omit $\M$ when it is clear from the context.

We distinguish between classes of pawn games based on the type of ownership of vertices:

* One Vertex Per Pawn (OVPP). There is a one-to-one correspondence between pawns and vertices; namely, $|V| = d$ and each $V_j$ is singleton, for $j \in [d]$. For $j \in [d]$ and $\set{v_j} = V_j$, we sometimes abuse notation by referring to Pawn $j$ as $v_j$.

* Multiple Vertices Per Pawn (MVPP). Each vertex is owned by a unique pawn but a pawn can own multiple vertices, thus $V_1, \ldots, V_d$ is a partition of $V$.

* Overlapping Multiple Vertices Per Pawn (OMVPP). Each pawn can own multiple vertices and a vertex can be owned by multiple pawns, i.e., we allow $V_i \cap V_j \neq \emptyset$, for $i \neq j$.

Clearly OMVPP generalizes MVPP, which generalizes OVPP.
In MVPP too, we sometimes abuse notation and refer to a pawn by a vertex that it owns.

A configuration of a pawn game is $\zug{v, P}$, meaning that the token is placed on a vertex $v \in V$ and $P \subseteq [d]$ is the set of pawns that  controls. Implicitly, controls the complement set $\overline{P}= [d] \setminus P$. moves the token from $\zug{v, P}$ iff he controls at least one pawn that owns $v$. Note that in OVPP and MVPP, let $j \in [d]$ with $v \in V_j$, then moves iff $i \in P$. Once the token moves, we update the control of the pawns by applying $\M$.

*From pawn games to turn-based games
We describe the formal semantics of pawn games together with the pawn-exchanging mechanisms by describing the explicit turn-based game that corresponds to a pawn game. For a pawn game $\G = \zug{V, E, T, \M}$, we construct the turn-based game $\G' = \zug{V', E', T'}$. For $i \in \set{1,2}$, denote by $V'_i$ 's vertices in $\G'$.
The vertices of $\G'$ consist of two types of vertices: configuration vertices $C = V \times 2^{[d]}$, and intermediate vertices $V \times C$. When $\M$ is $k$-grabbing, configuration vertices include the remaining number of pawns that can grab, as we elaborate below. The target vertices are $T' = \set{\zug{v, P}: v \in T}$. We describe $E'$ next.
For a configuration vertex $c = \zug{v, P}$, we define $c \in V'_1$ iff there exists $j \in P$ such that $v \in V_j$. That is, moves from $c$ in $\G'$ iff he moves from $c$ in $\G$. We define the neighbors of $c$ to be the intermediate vertices $\set{\zug{v', c}: v' \in N(v)}$. That is, moving the token in $\G'$ from $c$ to $\zug{v', c}$ corresponds to moving the token from $v$ to $v'$ in $\G$. Moves from intermediate vertices represent an application of $\M$. We consider the following mechanisms.

Optional grabbing. For $i \in \set{1,2}$, following a move, has the option to grab one of 's pawns.
Formally, for a configuration vertex $c = \zug{v, P} \in V'_1$, we have $N(c) \subseteq V'_2$. From $\zug{v', c} \in N(c)$, has two options: (1) do not grab and proceed to $\zug{v', P}$, or (2) grab $j \in P$, and proceed to $\zug{v', P \setminus \set{j}}$. The definition for is dual.

Always grabbing. For $i \in \set{1,2}$, following a move, always has to grab one of 's pawns. The formal definition is similar to optional grabbing with the difference that option (1) of not grabbing is not available to the players. We point out that grabs only after has moved, which in particular implies that controls at least one pawn that can grab.

Always grabbing or giving. Following a move, must either grab one of 's pawns or give her a pawn. The formal definition is similar to always grabbing with the difference that, for an intermediate vertex $\zug{v', \zug{v, P}}$, there are both neighbors of the form $\zug{v', P \setminus \set{j}}$, for $j \in P$, and neighbors of the form $\zug{v', P \cup \set{j}}$, for $j \notin P$.

$k$-grabbing. After each round, has the option of grabbing a pawn from , and at most $k$ grabs are allowed in a play.

A configuration vertex in $k$-grabbing is $c = \zug{v, P, r}$, where $r \in [k] \cup \set{0}$ denotes the number of grabs remaining.
Intermediate vertices are vertices. Let $\zug{v', c} \in V'_1$.
has two options: (1) do not grab and proceed to the configuration vertex $\zug{v', P, r}$, or (2) grab $j \notin P$, and proceed to $\zug{v', P \cup \set{j}, r-1}$ when $r > 0$.
Note that grabs are not allowed when $r=0$ and that Pawn $j$ stays at the control of for the remainder of the game.

Since pawn games are succinctly-represented turn-based games, Thm. <ref> implies determinacy; namely, one of the players wins from each initial configuration. We study the problem of determining the winner of a pawn game, formally defined as follows.

Let $\alpha \in \set{\text{OVPP, MVPP, OMVPP}}$ and $\beta$ be a pawn-grabbing mechanism.

The problem $\alpha$ $\beta$ PAWN-GAMES takes as input an $\alpha$ $\beta$ pawn game $\G$ and an initial configuration $c$, and the goal is to decide whether wins from $c$ in $\G$.

A naive algorithm to solve a pawn game applies attractor computation on the explicit turn-based game, which implies the following theorem.

$\alpha$ $\beta$ PAWN-GAMES is in EXPTIME, for all values of $\alpha$ and $\beta$.

§ OPTIONAL-GRABBING PAWN GAMES

Before describing our complexity results, we identify a somewhat unexpected property of MVPP optional-grabbing games.
Consider a vertex $v$ and two sets of pawns $P$ and $P'$ having $P' \subseteq P$. Intuitively, it is tempting to believe that “prefers” configuration $c = \zug{v, P}$ over $c' = \zug{v, P'}$ since he controls more pawns in $c$. Somewhat surprisingly, the following theorem shows that the reverse holds (see also Ex. <ref>). More formally, the theorem states that if wins from $c$, then he also wins from $c'$, under the restriction that if he makes the first move at $c$ (i.e., he controls $v$ in $c$), then he also makes the first move in $c'$ (i.e., he controls $v$ in $c'$).

Consider a configuration $\zug{v, P}$ of an MVPP optional-grabbing pawn game $\G$. Let $j \in [d]$ such that $v \in V_j$ and $P' \subseteq P$. Assuming that $j \in P$ implies $j \in P'$, if wins from $\zug{v, P}$, he wins from $\zug{v, P'}$. Assuming that $j \in \overline{P'}$ implies $j \in \overline{P}$, if wins from $\zug{v, P'}$, she wins from $\zug{v, P}$.

Consider an optional-grabbing game $\G = \zug{V, E, T}$, a configuration $c = \zug{v, P}$ with $v \in V_j$ where $j \in [d]$, and let $i \in \set{1,2}$. Consider a configuration $c' = \zug{v, P'}$ with $P' \subseteq P$ under the restriction that if $j \in P$, then $j \in P'$, that is, if controls Pawn $j$ in $c$, then he also controls Pawn $j$ in $c'$.
If wins from $c$, then wins from $c'$.

We prove for and the proof for follows from determinacy.
Let $\G$, $P$, $P'$, $c = \zug{v, P}$, and $c' = \zug{v, P'}$ be as in the theorem statement.

Let $\G'$ be the turn-based game corresponding to $\G$. For $i \geq 0$, let $W_i$ be the set of vertices in $\G'$ from which can win in at most $i$ rounds (see Thm. <ref>).

The following claim clearly implies the theorem.
Its proof proceeds by a careful induction.

Let $W_i$ be the set of vertices in $\G'$ from which can win in at most $i$ rounds (see Thm. <ref>).

* Configuration vertices: If $\zug{v,P}\in W_i$, then $\zug{v,P'}\in W_i$.

* Intermediate vertices: If $\zug{u,c}\in W_i$, then $\zug{u,c'}\in W_i$.

Claim: Configuration vertices: for $i \geq 0$, if $\zug{v,P}\in W_i$, then $\zug{v,P'}\in W_i$.

Intermediate vertices: for $i \geq 1$ and every vertex $u \in N(v)$, if $\zug{u,c}\in W_{i-1}$, then $\zug{u,c'}\in W_{i-1}$.

For the base case, we prove for both $i=0$ and $i=1$. Recall that the target set of $\G'$, which coincides with $W_0$, consists of configuration vertices whose $V$ component is in $T$. Thus, for the first part of the claim, since $c \in W_0$, then $v \in T$, and thus $\zug{v, P'} \in W_0$. Recall that an intermediate vertex is of the form $\zug{u, b}$, where $u$ denotes the “next” location of the token and $b$ denotes the “previous” configuration. In the case of $W_1$, since wins in one turn, each vertex in $W_1$ is of the form $\zug{u, b}$, where $u \in T$. Thus, for $\zug{u,c}\in W_1$, we clearly have $\zug{u,c'}\in W_1$.

For the induction hypothesis, assume that the claim holds for $i=n$, and we prove for $i=n+1$.
We start with configuration vertices.
Assume $c=\zug{v,P}\in W_{n+1}$.
We will show that $c'=\zug{v,P'}\in W_{n+1}$.
Recall that $N(c)$ consist of intermediate vertices of the form $\zug{u, c}$, where $u \in N(v)$, thus $\zug{u, c} \in N(c)$ iff $\zug{u, c'} \in N(c')$. Note that if $\zug{u, c} \in N(c)$ is winning for , i.e., $\zug{u, c} \in W_n$, then by the induction hypothesis, $\zug{u, c'} \in W_n$. We distinguish between two cases.
In the first case, controls $c$, i.e., $j\in P$ and $c$ is a vertex. In this case, our assumption is that $c'$ is also a vertex. Since $c \in W_{n+1}$, there must exist a neighbor $\zug{u, c}$ of $c$ having $\zug{u,c} \in W_n$. By the above, $\zug{u, c'} \in (N(c') \cap W_n)$, thus $c' \in W_{n+1}$. In the second case, controls $c$, thus $j\notin P$. Recall that $P' \subseteq P$, thus controls $c'$ as well. Note that $c \in W_{n+1}$ implies that wins from all of its neighbors

of the form $\zug{u,c}$.
Now consider the contrapositive of the assumption that states that $j \notin P'$ implies that $j \notin P$ which holds here and since $\zug{u,c} \in W_n$, by induction hypothesis, it follows that $\zug{u,c'} \in W_n$.
Thus, wins from all the neighbors of $c'$, thus $c' \in W_{n+1}$.

We turn to the second part of the claim that addresses intermediate vertices.
We again distinguish between two cases: $j \in P$ and $j \notin P$.
Consider an intermediate vertex $\zug{u, c} \in W_{n+1}$.
We will show that $\zug{u, c'} \in W_{n+1}$.
We denote by $\ell$, the pawn that owns $u$.

First consider the case $j \in P$.
Recall that in optional grabbing, has the option of grabbing after moves, thus $\zug{u, c}$ is a vertex.
Since the claim requires that if $j \in P$, then $j \in P'$, we conclude that $\zug{u, c'}$ is also a vertex.
Consider a neighbor of $\zug{u, c'}$, a configuration vertex $\zug{u,Q'}$.
Note that either does not use the option to grab, then $Q'=P'$, or she grabs a pawn $r$ from , then $Q'=P' \setminus \set{r}$.
Note that in order to apply the induction hypothesis on $\zug{u, Q'}$, we need to find a neighbor $\zug{u, Q}$ of $\zug{u, c}$ such that if $\ell \notin Q'$, then $\ell \notin Q$.
Note that at $\zug{u, c}$, has the option of not grabbing as well as of grabbing $\ell$, thus both $\zug{u, P}$ and $\zug{u, P\setminus \set{\ell}}$ are neighbors of $\zug{u, c}$. Note that $P = P \setminus \set{\ell}$ when $\ell \notin P$. That is, cannot grab $\ell$ when she already owns it. Since $\zug{u, c} \in W_{n+1}$ and it is a vertex, both $\zug{u, P} \in W_n$ and $\zug{u, P\setminus \set{\ell}}
\in W_n$.
Finally, if $\ell \in Q'$, define $Q := P$, and if $\ell \notin Q'$, define $Q := P \setminus \set{\ell}$.
In both cases, since $Q' \subseteq P'$ and $P' \subseteq P$, we have $Q' \subseteq Q$ and meets the requirement in the claim on $\ell$.
Thus, since $\zug{u, Q} \in W_n$, by the induction hypothesis, $\zug{u, Q'} \in W_n$.
Since $\zug{u, Q'}$ is any arbitrary neighbour of the vertex $\zug{u,c'}$, we have that $\zug{u,c'} \in W_{n+1}$.

In the second case $j\notin P$. That is, makes the move in $\zug{v, P}$, and thus $\zug{u, c}$ is a vertex. Since $P' \subseteq P$, we have $j \notin P'$, thus $\zug{u, c'}$ is also a vertex. Since $\zug{u, c} \in W_{n+1}$, it has a neighbor $\zug{u, Q} \in W_n$.
Note that since either grabs or does not grab in $\zug{u, c}$, we have $P \subseteq Q$. We find a neighbor $\zug{u, Q'}$ of $\zug{u, c'}$ to apply the induction hypothesis on.
Note that has the option to grab at $\zug{u, c'}$, and, among his choices, he can choose not to grab or to grab $\ell$.
If $\ell \in Q$, then we choose $Q' := P' \cup \set{\ell}$, and if $\ell \notin Q$, we choose $Q' := P'$. In both cases, $Q' \subseteq Q$ and meets the requirement in the claim.
Thus, since $\zug{u,Q} \in W_n$, by the induction hypothesis, we have $\zug{u, Q'} \in W_n$, and hence $\zug{u,c'} \in W_{n+1}$.

The following corollary of Thm. <ref> shows that we can restrict attention to “locally-grabbing” strategies that only grab the pawn that owns the vertex on which the token is placed. In other words, a locally-grabbing strategy will not grab a pawn if the token is not placed on the vertex that it owns.

Consider an MVPP optional-grabbing game. Suppose that controls $P \subseteq [d]$, and that moves the token to a vertex $v$ owned by Pawn $j$, i.e., $v \in V_j$. has the option to grab. If can win by grabbing a pawn $j' \neq j$, i.e., a pawn that does not own the next vertex, he can win by not grabbing at all. Formally, if wins from $\zug{v, P \cup \set{j'}}$, he also wins from $\zug{v, P}$. And dually for .

We point out that Thm. <ref> and Cor. <ref> do not hold for OMVPP optional-grabbing games.

It follows from Thm. <ref> that we can restrict attention to strategies that, when grabbing, only grab the  vertex to which the token is moving. Formally, we have the following.

Suppose that moves the token to vertex $v$ and controls $P \subseteq [d]$. Following 's move, has the option to grab a pawn.
Let $j \in [d]$ such that $v \notin V_j$. If wins by grabbing $j \in [d]$, i.e., from configuration $\zug{v, P \cup \set{j}}$, then he wins by not grabbing at all, i.e., from configuration $\zug{v, P}$. And dually for .

§.§ OVPP: A PTIME algorithm

We turn to study complexity results, and start with the following positive result.

OVPP optional-grabbing PAWN-GAMES is in PTIME.

We describe the intuition of the algorithm, the pseudo-code can be found in Alg. <ref>.

Recall that in turn-based games (see Thm. <ref>), the attractor computation iteratively “grows” the set of states from which wins: initially $W_0=T$, and in each iteration, a vertex $u$ is added to $W_i$ if (1) $u$ belongs to and all its neighbors belong to $W_i$ or (2) $u$ belongs to and it has a neighbor in $W_i$.
In optional-grabbing games, applying attractor computation is intricate since vertex ownership is dynamic.
Note that the reasoning behind (1) above holds; namely, if $N(u) \subseteq W_i$, no matter who controls $u$, necessarily $W_i$ is reached in the next turn.
However, the reasoning behind (2) fails.
Consider a vertex $u$ that has two neighbors $v_1 \in W_i$ and $v_2 \notin W_i$. While $u$ would be in $W_{i+1}$ according to (2), under optional-grabbing, when makes the move into $u$, can avoid $W_i$ by grabbing $u$ and proceeding to $v_2$.

In order to overcome this, our algorithm operates as follows. Vertices that satisfy (1) are added independent of their owner (Line $4$). The counterpart of (2) can be seen as two careful steps of attractor computation. First, let $B$ denote the border of $W_i$, namely the vertices who have a neighbor in $W_i$ (Line $6$).
Second, a vertex $u$ is in $W_{i+1}$ in one of two cases. (i) $u \in B$ and all of its neighbors are in $B \cup W_i$ (Line $10$). Indeed, if controls $u$ he wins by proceeding to $W_i$ and if owns $u$, she can avoid $W_i$ by moving to $B$, then grabs and proceeds to $W_i$. (ii) controls $u$ in the initial configuration and all of its neighbors are in $B$ (Line $12$). Indeed, cannot avoid proceeding into $B$, and following 's move, grabs and proceeds to $W_i$.

More formally, consider an input OVPP optional-grabbing game $\G = \zug{V, E, T}$ and an initial configuration $\zug{v_0,P_0}$. Correctness of the algorithm follows from the two following claims. First, we show soundness; namely, whenever the algorithm returns that wins, he does indeed have a winning strategy from $\zug{v_0, P_0}$.

For $i \geq 0$, wins from every vertex $v \in W_i$ no matter who makes the last step into $v$.

The proof is by induction on $i$. The base case is trivial since $W_0 = T$. For the inductive step, suppose that the claim holds for $W_i$ and we show that it holds in all ways that it can be extended.

Case 1 – Line $4$: for a vertex $u$ having $N(u) \subseteq W_i$, wins no matter who controls $u$ since in the next turn, $W_i$ is necessarily reached.

Case 2 – Line $10$: We claim that wins from $u \in B'$ no matter who controls $u$. Indeed, if controls $u$, he wins by proceeding to $W_i$. If controls $u$ and avoids $W_i$, then the next vertex is necessarily in $B$. grabs and proceeds to $W_i$.

Case 3 – Line $12$: Let $v\in R\setminus P_0$.
can always ensure that controls $v$ by never grabbing $v$.
Also in OVPP optional-grabbing, does not need to grab $v$ in order to reach $v$.
Thus if has a strategy such that the token reaches $v$, then he can ensure that the token reaches $v$ and is controlled by .

Hence, once $v$ is reached, since it is controlled by , she is forced to move from $v$ to a vertex $v'$ in $B$.
then grabs $v'$ unless he already controls it and moves the token to $W_i$.

We turn to prove completeness.

Suppose that the algorithm terminates at iteration $i$ in Lines $7$ or $13$. Then, has a winning strategy from $\zug{v_0, P_0}$.

We first consider the case of terminating in Line $7$. Thus, every vertex not in $W_i$, including $v_0$, does not have a path to $W_i$. Clearly wins.

Second, suppose that the algorithm terminates in Line $13$. We describe a winning strategy from $\zug{v_0, P_0}$ that avoids $W_i$.
Whenever moves the token, she moves it to an arbitrary vertex not in $W_i \cup B$. When the token reaches $u \in B$, it is following a move, and grabs $u$, and moves to $W_i \cup B$.

We claim that wins when the game starts from $\zug{v_0, P_0}$. Assume towards contradiction that $W_i$ is reached. Since $v_0 \notin W_i$, a visit to $W_i$ must first visit a vertex $u \in B$. We claim that (i) $u$ is in the control of and that (ii) she can move away from $W_i$. Combining (i) and (ii) we reach a contradicting to the assumption that $W_i$ is reached. We conclude the proof by showing that (i) and (ii) hold.
For (ii), note that $u$ has a neighbor not in $W_i \cup B$ otherwise $u$ would have been added to $W_{i+1}$ in Line $4$ or Line $12$.
We turn to prove (i). Suppose first that $u=v_0$.
If controls $v_0$, then the algorithm terminates in Line $8$.
Since it does not terminate there, controls $u$.
Next we consider the case that $u \neq v_0$, thus $u$ has a predecessor $u'$ in the play.
We distinguish between two cases.
If $u' \in R$, then $u' \in P_0$ otherwise it would have been added to $W_{i+1}$ in Line $12$.
Thus, makes the move from $u'$ to $u$, and grabs $u$ following 's move (if she does not control it already).
The second case is when $u' \notin R$.
Recall that a vertex is in $R$ if all of its neighbors lead to $B$, thus $u' \notin R$ implies that it has at least one neighbor not in $B$.
Note that if $u'$ was in the control of , her strategy would have dictated to proceed to a vertex not in $B$.
Thus, if makes the move from $u'$ to $u$, and grabs $u$ following 's move.

Finally, note that the algorithm terminates once a fixed point is reached, thus it runs for at most $|V|$ iterations.

This concludes the proof of the theorem.

[1]
$W_0 = T$, $i=0$
$v_0\in W_i$ Player 1
$W_{i+1} = W_i \cup \set{u: N(u) \subseteq W_i}$
$W_i \neq W_{i+1}$ $i:=i+1$; Continue $B := \set{u: N(u) \cap W_i \neq \emptyset}$
$B=\emptyset$ Player 2 $v_0\in B$ and $v_0\in P_0$ Player 1 $B' := \set{u \in B: N(u) \subseteq B \cup W_i}$
$B'\neq \emptyset$ $W_{i+1} := W_i \cup B'$; $i:=i+1$; Continue $R = \set{u: N(u) \subseteq B}$
$R \setminus P_0 \neq \emptyset$ $W_{i+1} = W_i \cup (R\setminus P_0)$; $i:=i+1$
Player 2

Given an OVPP optional-grabbing pawn game $\G = \zug{V, E, T}$ and an initial configuration $c = \zug{v, P_0}$, determines which player wins $\G$ from $c$.

[1]
winner$\zug{V, E, T},\zug{v_0,P_0}$
$v_0\in T$ Player 1
$T' = T \cup \set{u: N(u) \subseteq T}$
$T'\neq T$ WINNER($\zug{V, E, T'},\zug{v_0,P_0}$)
$B := \set{u: N(u) \cap T \neq \emptyset}$
$B=\emptyset$ Player 2
$v_0\in B$ and $v_0\in P_0$ Player 1
$B' = \set{u \in B: N(u) \subseteq B \cup T}$
$B'\neq \emptyset$ WINNER($\zug{V, E, T\cup B'},\zug{v_0,P_0}$)
$R = \set{u: N(u) \subseteq B}$
$R \setminus P_0 \neq \emptyset$ WINNER($\zug{V, E, T\cup R\setminus P_0},\zug{v_0,P_0}$)
Player 2

Algorithm for OVPP Optional Grabbing Pawn Games

OVPP optional-grabbing game $\G = \zug{V, E, T}$ and an initial configuration $\zug{v_0,P_0}$.

$\zug{V, E, T},\zug{v_0,P_0}$

$v_0\in T$

$T' = T \cup \set{u: N(u) \subseteq T}$

$T'\neq T$
$\zug{V, E, T'},\zug{v_0,P_0}$

$B := \set{u: N(u) \cap T \neq \emptyset}$

$v_0\in B$ and $v_0\in P_0$

$B' = \set{u \in B: N(u) \subseteq B \cup T}$

$B'\neq \emptyset$
$\zug{V, E, T\cup B'},\zug{v_0,P_0}$
$R = \set{u: N(u) \subseteq B}$

$R \setminus P_0 \neq \emptyset$$\zug{V, E, T\cup R\setminus P_0},\zug{v_0,P_0}$

Algorithm for OVPP Optional Grabbing Pawn Games

Guy: In it's current length, this doesn't fit in the body of the paper. Shibashis, please shrink this to at most a quarter of a page.

Shibashis: I will try to shrink. We have 3 more pages above STACS.

§.§ MVPP: EXPTIME-hardness via games

We prove hardness of MVPP optional-grabbing pawn games by reduction through a class of games that we introduce and call  games, and may be of independent interest.
A game is $\G = \zug{V, E, T, L, K, \lambda, \kappa}$, where $\zug{V, E, T}$ is a turn-based game, $L = \set{\lock_1,\ldots, \lock_n}$ is a set of locks $K = \set{k_1,\ldots, k_n}$ is a set of keys, each $\lock_j$ is associated to key $\key_j \in K$ for $j \in [n]$, and each edge is labeled by a set of locks and keys respectively given by $\lambda: E \rightarrow 2^L$ and $\kappa: E \rightarrow 2^K$. Note that a lock and a key can appear on multiple edges.

Intuitively, a game is a turn-based game, only that the locks impose restrictions on the edges that a player is allowed to cross. Formally, a configuration of a game is $c = \zug{v, A} \in V \times 2^L$, meaning that the token is placed on $v$ and each lock in $A$ is closed (all other locks are open). When $v \in V_i$, for $i \in \set{1,2}$, then moves the token as in turn-based games with the restriction that he cannot choose an edge that is labeled by a closed lock, thus $e = \zug{v, u} \in E$ is a legal move at $c$ when $\lambda(e) \subseteq (L \setminus A)$. Crossing $e$ updates the configuration of the locks by “turning” all keys that $e$ is labeled with. Formally, let $\zug{u, A'}$ be the configuration after crossing $e$. For $k_j \in \kappa(e)$ (“key $k_j$ is turned”), we have $\ell_j \in A$ iff $\ell_j \notin A'$. For $k_j \notin \kappa(e)$ (“key $k_j$ is unchanged”), we have $\ell_j \in A$ iff $\ell_j \in A'$.

Note that, similar to pawn games, each game corresponds to an exponentially sized two-player turn-based game. Thus, membership in $\EXP$ is immediate. For the lower bound, we show a reduction for the problem of deciding whether an alternating polynomial-space Turing machine (ATM) accepts a given word.

Given a game $\G$ and an initial configuration $c$, deciding whether wins from $c$ in $\G$ is $\EXP$-complete.

We briefly describe the syntax and semantics of ATMs, see for example <cit.>,
for more details.
An ATM is $\A = \zug{Q, \Gamma, \delta, q_0, q_{acc}, q_{rej}}$, where $Q$ is a collection of states that is partitioned into $Q = Q_1 \cup Q_2$ owned by and respectively, $\Gamma$ is a tape alphabet, $\delta: Q \times \Gamma \rightarrow 2^{Q \times \Gamma \times \set{{\sf L}, {\sf R}}}$ is a transition function, $q_0, q_{acc}, q_{rej} \in Q$ are respectively an initial, accepting, and rejecting states. A configuration of $\A$ is $c = \zug{q, \pos, \zug{\gamma_1,\ldots, \gamma_m}}$, meaning that the control state is $q$, the head position is $\pos$, and $\zug{\gamma_1,\ldots, \gamma_m}$ is the tape content, where $m$ is polynomial in the length of the input word $w$. In order to determine whether $\A$ accepts $w$ we construct a (succinctly-represented) turn-based game over the possible configurations of $\A$, the neighbors of a configuration are determined according to $\delta$, and, for $i \in \set{1,2}$, moves from states in $Q_i$. We say that $\A$ accepts $w$ iff has a winning strategy from the initial configuration for the target state $q_{acc}$.

Given $\A$ and $w$,

we construct a game $\G = \zug{V, E, T, L, K, \lambda, \kappa}$ and an initial configuration $\zug{v_0, A}$ such that wins from $\zug{v, A}$ in $\G$ iff $w$ is accepted by $\A$. The vertices of $\G$ consist of main and intermediate vertices. Consider a configuration $c = \zug{q, \pos, \zug{\gamma_1,\ldots, \gamma_m}}$ of $\A$. We simulate $c$ in $\G$ using $c' = \zug{v, A}$ as follows. First, the main vertices are $Q \times \set{1,\ldots,m} \times \Gamma$ and keep track of the control state and position on the tape. The main vertex that simulates $c = \zug{q, \pos, \zug{\gamma_1,\ldots, \gamma_m}}$ is $v = \zug{q, \pos, \gamma_\pos}$. We define $v \in V_i$ iff $q \in Q_i$. Second, we use locks to keep track of the tape contents. For each $1 \leq i \leq m$ and $\gamma \in \Gamma$, we introduce a lock $\lock_{i, \gamma}$. Then, in the configuration $c' = \zug{v, A}$ that simulates $c$,
the only locks that are open are $\lock_{i, \gamma_i}$, for $i \in \set{1,\ldots,m}$.
Next, we describe the transitions, where intermediate vertices are used for book-keeping.
The neighbors of a main vertex $v$ are the intermediate vertices $\set{\zug{v, t}: t \in \delta(q, \gamma)}$, where a transition of $\A$ is $t = \zug{q', \gamma', B}$, meaning that the next control state is $q'$, the tape head moves to $\pos+1$ if $B = R$ and to $\pos-1$ if $B=L$, and the $\pos$-th tape content changes from $\gamma$ to $\gamma'$. We update the state of the locks so that they reflect the tape contents: for the edge $\zug{v, \zug{v, t}}$, we have $\kappa(\zug{v, \zug{v, t}}) = \{k_{i, \gamma}, k_{i, \gamma'}\}$. That is, traversing the edge turn the keys to close  $\lock_{\pos, \gamma}$ and open $\lock_{\pos, \gamma'}$.
The neighbors of $\zug{v, t}$ are main vertices having control state $q'$ and head position $\pos'$. Recall that the third component of a main vertex is the tape content at the current position. We use the locks' state to prevent moving to main vertices with incorrect tape content: outgoing edges from $\zug{v,t}$ are of the form $\zug{\zug{v, t}, \zug{q', \pos', \gamma''}}$ and is labeled by the lock $\lock_{\pos', \gamma''}$. That is, the edge can only be traversed when the $\pos'$-th tape position is $\gamma''$.

It is not hard to verify that there is a one-to-one correspondence between runs of $\A$ and plays of $\G$.
Thus, forces $\A$ to reach a configuration with control state $q_{acc}$ iff forces to reach a main vertex with control state $q_{acc}$.
Note that the construction is clearly polynomial since $\G$ has $|Q| \cdot m \cdot |\Gamma|$ main vertices.

Given $\A$ and $w$,

we construct a game $\G = \zug{V, E, L, K, \ell, k, T}$ and an initial configuration $\zug{v_0, A}$ such that wins from $\zug{v, A}$ in $\G$ iff $w$ is accepted by $\A$.

We simulate configurations using locks.
For each $1 \leq i \leq m$ and $\gamma \in \Gamma$, we introduce a lock $\lock_{i, \gamma}$. In the configuration in $\G$ that simulates $c$,
the only locks that are open are $\lock_{i, \gamma_i}$, for $i \in \set{1,\ldots,m}$.
We describe the vertices and edges in $\G$. The main vertices form the set $Q \times \set{1,\ldots,m} \times \Gamma$.
When the token is placed on $v = \zug{q, \pos, \gamma}$, then the configuration in $\A$ agrees with $v$ in that the control state is $q$, the head position is $\pos$, and the tape content at position $\pos$ is $\gamma$. The owner of $v$ in $\G$ coincides with the owner of $q$ in $\A$. We add intermediate vertices and edges between main vertices.
Outgoing edges from a main vertex $v$ leads to vertices associated with transitions

of the form $\zug{v, t}$, for each $t \in \delta(q, \gamma)$.

Let $t = \zug{q', \gamma', B}$.
Then, the next control state is $q'$, the tape head moves to $\pos+1$ if $B = R$ and to $\pos-1$ if $B=L$, and the $\pos$-th tape content changes from $\gamma$ to $\gamma'$.
For the edge $\zug{v, \zug{v, t}}$, we have $\kappa(\zug{v, \zug{v, t}}) = \{k_{i, \gamma}, k_{i, \gamma'}\}$, and we turn the keys to close  $\lock_{\pos, \gamma}$ and open $\lock_{\pos, \gamma'}$.
Outgoing edges from $\zug{v, t}$ lead to main vertices having control state $q'$ and head position $\pos'$.
Let the tape content of $\pos'$-th position be $\gamma''$ in the respective configuration of $\A$.
The edge $\zug{\zug{v, t}, \zug{q', \pos', \gamma''}}$ is labeled by the lock $\lock_{\pos', \gamma''}$ which is open.
The next main vertex of $\G$ is thus $\zug{q', i', \gamma''}$.

Note that only $\lock_{\pos', \gamma''}$ is open, while all locks $\lock_{\pos', \widehat{\gamma}}$ for $\widehat{\gamma} \neq \gamma''$ are closed.

Hence, it is not hard to verify that there is a one-to-one correspondence between runs of $\A$ and plays of $\G$.
Thus forces $\A$ to reach a configuration with control state $q_{acc}$ iff forces to reach a main vertex with control state $q_{acc}$.

Note that $\G$ has $|Q| \cdot m \cdot |\Gamma|$ main vertices.

The construction is clearly polynomial.

Each intermediate vertex $\zug{v, t}$ leads to an intermediate vertex $u$. Let $t = \zug{q', \gamma', B}$ and let $\pos'$ be the next position as defined above by $\pos$ and $B$. On the edge $\zug{\zug{v, t}, u}$ we turn the keys to close  $\lock_{\pos, \gamma}$ and open $\lock_{\pos, \gamma'}$. Outgoing edges from $u$ lead to main vertices having control state $q'$ and head position $\pos'$. The edge $\zug{u, \zug{q', \pos', \gamma''}}$ is labeled by the lock $\lock_{\pos', \gamma''}$. Since only one lock is open for each position, only one of these edges is enabled.

@xc/pgf/inner xsep
@x by 2@xc
@xb/pgf/minimum width

@y by
@yc/pgf/inner ysep
@y by 2@yc
@yb/pgf/minimum height

@x by.5
@xa/pgf/outer xsep
@x by#1@xa
@y by-.5
@y by.5
@ya/pgf/outer ysep
@y by#1@ya

in east,west in north,mid,base,south

in east,west,north,mid,base,south,center,text

§.§.§ From games to optional-grabbing pawn games

Throughout this section, fix a game $\G$ and an initial configuration $c$. We construct an optional-grabbing pawn game $\G'$ over a set of pawns $[d]$, and identify an initial configuration $c'$ such that wins in $\G$ from $c$ iff wins from $c'$ in $\G'$.

*From turn-based games to optional-grabbing games

[node distance=8mm,initial text = ,main/.style = draw, circle, text=black, inner sep=1pt,gain/.style = draw, square, text=black, inner sep=1pt]

[main,initial] (2) $v'_1$;
[gain,initial] (8) [left of=2, xshift=-2cm] $v_1$;
[main] (9) [right of=8] $v_2$;

[gain] (3) [right of=2] $v_1$;
[gain] (4) [right of=3] $v'_2$;
[main] (5) [right of=4] $v_2$;

[main] (7) [right of=5] $s$;
[main,accepting] (6) [right of=7] $t$;
[->] (8) – (9);
[->] (3) – (4);
[->] (2) – (3);
[->] (4) – (5);
[->] (5) – (7);

(3) edge[bend right] node [left]  (6);

From turn-based to optional-grabbing games.

In this section, we consider the case in which $\G$ has no keys or locks, thus $\G$ is a turn-based game.

The reduction is depicted in Fig. <ref>.
Denote the turn-based game $\G = \zug{V, E, T}$ with $V = V_1 \cup V_2$ and initial vertex $v_0$. We construct an OVPP optional-grabbing $\G' = \zug{V', E', T'}$, where $V' = V \cup \set{v': v \in V} \cup \set{s,t}$. We add edges to ensure that the player who owns a vertex $v \in V$ is the player who moves from $v$ in $\G'$: we have $\zug{v', v} \in E'$, and if $v \in V_1$, then $\zug{v, s} \in E'$, and if $v \in V_2$, then $\zug{v, t} \in E'$.

We redirect each edge $\zug{u,v}$ in $\G$ to $\zug{u, v'}$ in $\G'$. Intuitively, for $v \in V_1$, a winning strategy will guarantee that $v'$ is always in the control of , and following her move at $v'$, must grab $v$ otherwise wins and choose the next location. And dually for $v \in V_2$. Let $V'_1 = V_1 \cup \set{v': v \in V_2}$, the initial configuration of $\G'$ is $\zug{v_0, V'_1}$, that is controls $V_2 \cup \set{v': v \in V_1}$.

We thus have the following:

For a turn-based game $\G$, wins $\G$ from a vertex $v_0 \in V$ iff wins the optional-grabbing game $\G'$ from configuration $\zug{v_0, {V'_1}}$.

Let $f$ be a winning strategy in $\G$. We describe a winning strategy $f'$ in $\G'$. The proof is dual when wins in $\G$. 's strategy $f'$ simulates the execution of $f$ on $\G$ so that when the token is placed on $v \in V$ in $\G'$ it is also placed on $v$ in $\G$. Moreover, if $v \in V_1$ in $\G$, then controls $v$ in $\G'$.

Initially, the invariant clearly holds. Suppose that is playing $\G'$ according to some strategy $g'$. We show that either $f'$ wins by reaching $t$, or that the invariant is maintained. Suppose that the token is placed on $v \in V$. We distinguish between three cases. (1) If $v \in V_2$ and owns $v$ in $\G'$, then he moves to $t$ to win the game. (2) Suppose that $v \in V_2$, that owns $v$, and that she moves to $u'$.
The simulation in $\G$ proceeds to vertex $u$.
In order to maintain the second part of the invariant, does not grab $u'$ but grabs $u$ when $u \in V_1$, which is possible because in such a case we define $u' \in V'_2$. (3) When $v \in V_1$, the invariant implies that controls $v$ in $\G'$. then copies the move of $f$ in $\G$; namely, let $u = f(v)$, then $u' = f'(v)$. The move from $u'$ is as in case (2).

Let $v_0, v_1,\ldots$ be the play in $\G$. Clearly, if case (1) occurs at some point, wins $\G'$. Assume that it does not occur. Then, the invariant implies that the play in $\G'$ is $v_0, v'_1, v_1, v'_2, v_2,\ldots$. Since $f$ is winning in $\G$, there is an $i \geq 0$ such that $v_i = t$, thus the play is winning in $\G'$ as well.

*Gadgets for simulating locks and keys
The core of the reduction is to construct gadgets that simulate locks and keys. Let $\G'$ denote the optional-grabbing pawn game that we construct, and let $[d]$ denote its set of pawns.
For each lock $\ell \in L$ and its corresponding key $k \in K$, we construct gadgets $\G_\ell$ and $\G_k$ that simulate the operations of $\ell$ and $k$ in $\G'$.
The gadgets in two states are depicted in Fig. <ref>. We highlight three pawns colored blue, green, and red, respectively owning, $\set{v_1^\ell, v_1^k}$, $\set{v_2^\ell, v_2^k, v_7^k, v_8^k}$, and $\set{v_{\text{in}}^k, v_4^k, v_5^k, v_6^k}$. Each of the other vertices (colored white) is owned by a fresh pawn.
Intuitively, for each lock $\ell$, we identify two sets $\P^\ell_O, \P^\ell_C \subseteq 2^{[d]}$, respectively representing an open and closed state of $\ell$.
We will ensure that when entering and exiting a gadget, the configuration is in one of these sets.
When the set of pawns that controls is in $\P^\ell_O$ and $\P^\ell_C$, we respectively say that $\G_\ell$ is in open and closed state, and similarly for $\G_k$ as stated below.
We define $\P^\ell_O = \set{P \in 2^{[d]}: v^\ell_1 \notin P \wedge v^\ell_2 \in P}$ and $\P^\ell_C = \set{P \in 2^{[d]}: v^\ell_1 \in P \wedge v^\ell_2 \notin P}$.
Formally, we define $\P^\ell_O = \set{P \in 2^{[d]}: v^\ell_1 \notin P \wedge v^\ell_2 \in P}$ and $\P^\ell_C = \set{P \in 2^{[d]}: v^\ell_1 \in P \wedge v^\ell_2 \notin P}$.

The core of the reduction is to construct gadgets that simulate locks and keys. Let $\G'$ denote the optional-grabbing pawn game that we construct, and let $[d]$ denote its set of pawns. For each lock $\ell \in L$ and its corresponding key $k \in K$, we construct gadgets $\G_\ell$ and $\G_k$ that simulate the operations of $\ell$ and $k$ in $\G'$. We describe the idea. For each lock $\ell$, we identify two sets $\P^\ell_O, \P^\ell_C \subseteq 2^{[d]}$.
A configuration in $\P^\ell_O$ and $\P^\ell_C$ respectively represent an open and closed $\ell$. We will ensure that when entering and exiting a gadget, the configuration is in one of these sets. We say that $\G_\ell$ is entered or exited in $\P^\ell_O$ or $\P^\ell_C$, when the set of pawns that controls is in the respective set, and similarly for $\G_k$ as stated below.
We define $\P^\ell_O = \set{P \in 2^{[d]}: v^\ell_1 \notin P \wedge v^\ell_2 \in P}$ and $\P^\ell_C = \set{P \in 2^{[d]}: v^\ell_1 \in P \wedge v^\ell_2 \notin P}$.
The two gadgets are depicted in Fig. <ref>, where both closed and open configurations for the two are shown. We assign colors to the pawns that have a crucial role in the operation of the gadgets. We start by describing how $\G_\ell$ simulates an open lock.

Let $i \in \set{1,2}$.
An open lock stays open: If enters $\G_\ell$ in $\P^\ell_O$, then he has a strategy that guarantees that either he wins $\G'$ or $\G_\ell$ is exited  in $\P^\ell_O$. A closed lock cannot be crossed: If enters $\G_\ell$ in $\P^\ell_C$, then has a strategy that guarantees that loses $\G'$.

We prove for and the proof is dual for . First, suppose enters $\G_\ell$ in $\P^\ell_O$.

may or may not grab $v^\ell_{\text{in}}$, and the game can proceed to either $v^\ell_1$ or $v^\ell_2$.
We argue that if the game proceeds to $v^\ell_1$, then will not grab $v^\ell_1$.
We can also similarly show that if the game proceeds to $v^\ell_2$, then will not grab $v^\ell_2$.
controls $v^\ell_1$. We claim that if grabs $v^\ell_1$, he will lose the game. Indeed, following 's move in $v^\ell_1$, will grab $v^\ell_3$ and move the token to the sink vertex $s$ to win the game.
Thus, does not grab $v^\ell_1$ and keeps it in the control of . Following 's move in $v^\ell_1$, grabs $v^\ell_3$ and proceeds to exit $\G_\ell$.
Note that when $\G_\ell$ is exited, maintains control of $v^\ell_2$ and maintains control of $v^\ell_1$, thus the configuration is in $\P^\ell_O$. Second, suppose that enters $\G_\ell$ in $\P^\ell_C$. Then, grabs $v^\ell_{\text{in}}$ and moves the token to $v^\ell_1$. Since controls $v^\ell_1$ he must make the next move. then grabs $v^\ell_3$ and moves the token to $s$ to win the game.

Next, we present the gadget $\G_k$ for simulating the operation of a key $k$ (see Fig. <ref>). Intuitively, we maintain that $\G_k$ is in open state iff $\G_\ell$ is in open state, and traversing $\G_k$ swaps the state of both.
We define sets of configurations $\P^k_O = \set{P \in 2^{[d]}: \set{v^k_{\text{in}}, v^k_1, v^k_4, v^k_5, v^k_6} \cap P = \emptyset \wedge \set{v^k_2, v^k_7, v^k_8} \subseteq P}$ and $\P^k_C = \set{P \in 2^{[d]}: \set{v^k_{\text{in}}, v^k_1, v^k_4, v^k_5, v^k_6} \subseteq P \wedge \set{v^k_2, v^k_7, v^k_8} \cap P = \emptyset}$ (see Fig. <ref>).

Note that $\P^k_O \subseteq \P^\ell_O$ and $\P^k_C \subseteq \P^\ell_C$ since $v_i^k$ and $v_i^\ell$ are owned by the same pawn for $i \in [2]$.

Next, we present the gadget $\G_k$ for simulating the operation of a key $k$ (see Fig. <ref>). Intuitively, we maintain that $\G_k$ is in open state iff $\G_\ell$ is in open state, and traversing $\G_k$ swaps the state of both.
Let $\P^k_O = \set{P \in 2^\P: \set{v^k_{\text{in}}, v^k_1, v^k_4, v^k_5, v^k_6} \cap P = \emptyset \wedge \set{v^k_2, v^k_7, v^k_8} \subseteq P}$ and $\P^k_C = \set{P \in 2^\P: \set{v^k_{\text{in}}, v^k_1, v^k_4, v^k_5, v^k_6} \subseteq P \wedge \set{v^k_2, v^k_7, v^k_8} \cap P = \emptyset}$. Note that $\P^k_O \subseteq \P^\ell_O$ and $\P^k_C \subseteq \P^\ell_C$.

Turning $k$ closes an open $\ell$: Let $i \in \set{1,2}$. If enters $\G_k$ in $\P^k_O$, then he has a strategy that ensures that either wins $\G'$ or $\G_k$ is exited in $\P^k_C$.
Turning $k$ opens a closed $\ell$: when enters $\G_k$ in $\P^k_C$, ensures that either he wins $\G'$ or $\G_k$ is exited in $\P^k_O$.

We depict $\G_k$ in two configurations in Fig. <ref>. The vertices $v^k_3$ and $v^k_{\text{out}}$ are controlled by one-vertex pawns. The rest of the vertices in $\G_k$, not including targets, are controlled by three pawns and are depicted using colors. Vertex $v^k_1$ is controlled by a “blue” pawn, who also owns $v^\ell_1$. Vertices $v^k_2$, $v^k_7$, and $v^k_8$ are all owned by a “green” pawn who also controls $v^\ell_2$. The other vertices are owned by a “red” pawn.

We simulate the properties of a key using the configurations, where we prove the claim for an entry configuration in $\P^k_C$ and the proof for $\P^k_O$ is dual. We claim that for $i \in \set{1,2}$, if the token lands on $v^k_2$ when controls that vertex, then loses.
Indeed, following 's move at $v^k_2$, grabs $v^k_3$ and directs the token to the winning vertex.
It follows that

does not grab $v^k_{\text{in}}$ upon entry to $\G_k$ and allows to move. Following 's move at $v^k_{\text{in}}$, grabs $v^k_1$, and proceeds to $v^k_4$.
Since moves and $v^k_4$ is in the control of , no change of pawns occurs. We claim that

now proceeds to $v^k_5$. Indeed, if she proceeds to $v^k_6$, will grab $v^k_6$ and win by moving to $t$.
Observe that grabs the red pawn since it controls $v_5^k$ following 's move from $v^k_4$ to $v^k_5$.
Indeed, otherwise proceeds to $s$ to win the game.
Finally, following 's move from $v^k_5$, must grab the green pawn since it grabs $v_7^k$, otherwise moves from $v^k_7$ to $t$ to win the game.
To conclude, if the token exits $\G_k$, has grabbed the blue and red pawns and has grabbed the green pawn. The configuration upon exiting $\G_k$ is thus in $\P^k_O$, and we are done.

For each lock $\ell \in L$ and corresponding key $k \in K$, we construct gadgets $\G_\ell$ and $\G_k$ that simulate the operation of $\ell$ and $k$. We describe the high-level idea. Suppose that $\G$ is in a configuration $\zug{v, A}$, thus the token is placed on $v$ and each lock in $A$ is closed.
The corresponding configuration in $\G'$ is $\zug{v, P}$, where, as in the proof of Lemma <ref>, controls $v$ if $v \in V_1$ in $\G$Is this about controlling initially since there is ownership of a vertex directly by ., and $P \subseteq \P$ is a set of pawns that owns and has the following properties.
For each lock $\ell$, we identify  two sets $\P^\ell_O, \P^\ell_C \subseteq 2^\P$Notation: $\P$ is a set of pawns, but $\P^\ell_O, \P^\ell_C$ are set of sets of pawns!! such that if $\ell \in A$ is closed, then $P \in \P^\ell_C$, and if $\ell \notin A$ is open, then $P \in \P^\ell_O$.
We construct $\G_\ell$ to have the following properties.
Intuitively, if $\G_\ell$ is entered when the lock is in “open state”, i.e., $P \in \P^\ell_O$, then the lock stays open, thus both players can force the gadget to be exited and upon exit, the set of pawns that owns is in $\P^\ell_O$. On the other hand, suppose that enters $\G_\ell$ in a “closed state”, i.e., $P \in \P^\ell_C$.
Then, has a strategy that guarantees that the gadget is never exited and 's objective is violated, thus winsor loses? $\G'$.
Finally, we construct $\G_k$ to simulate the turning of the key: when the gadget is entered in a configuration in $\P^\ell_O$, both players can force the gadget to be exited, and the configuration upon exiting is in $\P^\ell_C$, and vice versa.

We start by describing the lock gadget $\G_\ell$, for $\ell \in L$. We depict $\G_\ell$ in two configurations in Figures <ref> and <ref>. All vertices apart from $v^\ell_1$ and $v^\ell_2$ are controlled by one-vertex pawnsdefine?. The pawns that control $v^\ell_1$ and $v^\ell_2$ also control other vertices in $\G_k$. The vertices $v^\ell_s$ and $v^\ell_t$Check these. are respectively losing and winning vertices for .
The lock is open when controls the vertex $v^\ell_1$ and controls the vertex $v^\ell_2$, and it is closed when controls $v^\ell_2$ and controls $v^\ell_1$.Check this!
Formally, we define $\P^\ell_O = \set{P \in 2^\P: v^\ell_1 \notin P \wedge v^\ell_2 \in P}$ and $\P^\ell_C = \set{P \in 2^\P: v^\ell_1 \in P \wedge v^\ell_2 \notin P}$. When constructing the pawn game $\G'$, we will use multiple copies of the gadgets and connections between them. We are interested in the last move into a gadgetNot clear! and the set of pawns that owns when entering a gadget. For $i \in \set{1,2}$, if makes this last move, we say that  enters the gadget.

We define the two gadgets as follows and the construction is depicted in Figures <ref> and <ref>.
We start by describing lock gadget, game graph is as shown in the Figure <ref> $v_{\ell_{in}}$ and $v_{\ell_{out}}$ are enter and exit vertices respectively. Vertex set $V^\ell_O=\{v_{\ell_2}\}$ and $V^\ell_C=\{v_{\ell_1}\}$.
Game graph of game $\G_k$ is as shown in the Figure <ref>, here $v_{k_{in}}$ and $v_{k_{out}}$ are in and out vertices respectively. $V^k_O=v_{k_2},v_{k_{7}},v_{k_{8}}$ and $V^k_C=\{v_{k_{in}},v_{k_1},v_{k_4},v_{k_5},v_{k_6}\}$
Now consider three pawns corresponding to a lock and key gadgets $P_x$ for $x\in\{Red,Blue,Green\}$.
$P_{Red}=\{v_{k_{in}},v_{k_4},v_{k_5},v_{k_6}\}$,$P_{Blue}=\{v_{\ell_1},v_{k_1}\}$,$P_{Green}=\{v_{\ell_2},v_{k_2},v_{k_{7}},v_{k_{8}}\}$. Note this sets are based on one lock and one key configuration but we can simply add vertices to synchronize different same locks and keys.

[node distance=8mm, main/.style = draw,circle, text=black, inner sep=1pt,main1/.style = draw,circle, blue, left color=blue!20, text=black, inner sep=1pt,main2/.style = draw,circle, red, left color=red!20, text=black, inner sep=1pt,main3/.style = draw,circle, green, left color=green!20, text=black, inner sep=1pt,gain1/.style = draw,square, blue, left color=blue!20, text=black, inner sep=1pt,gain2/.style = draw,square, red, left color=red!20, text=black, inner sep=1pt,gain3/.style = draw,square, green, left color=green!20, text=black, inner sep=1pt] ]
[main] (1) $v^\ell_{\text{in}}$;
[gain1] (2) [above right of=1] $v^\ell_1$;
[main3] (3) [below right of=1] $v^\ell_2$;
[main] (4) [right of=2] $v^\ell_3$;
[main] (5) [right of=3] $v^\ell_4$;
[main] (6) [below right of=4] $v^\ell_{\text{out}}$;
[main] (7) [right of=4] $s$;
[main,accepting] (8) [right of=5] $t$;
[main] (9) [right of=6]$v^\ell_{\text{in}}$;
[main1] (10) [above right of=9] $v^\ell_1$;
[main] (12) [right of=10] $v^\ell_3$;
[main] (13) [below right of=12] $v^\ell_{\text{out}}$;
[main] (14) [below left of=13] $v^\ell_4$;
[main] (15) [right of=12] $s$;
[main,accepting] (16) [right of=14] $t$;
[gain3] (17) [left of=14] $v^\ell_2$;
[->] (1) – (2);
[->] (1) – (3);
[->] (2) – (4);
[->] (3) – (5);
[->] (4) – (6);
[->] (5) – (6);
[->] (4) – (7);
[->] (5) – (8);
[->] (9) – (10);
[->] (9) – (17);
[->] (10) – (12);
[->] (12) – (15);
[->] (12) – (13);
[->] (14) – (13);
[->] (14) – (16);
[->] (17) – (14);

[node distance=8mm, main/.style = draw,circle, text=black, inner sep=1pt,main1/.style = draw,circle, blue, left color=blue!20, text=black, inner sep=1pt,main2/.style = draw,circle, red, left color=red!20, text=black, inner sep=1pt,main3/.style = draw,circle, green, left color=green!20, text=black, inner sep=1pt,gain1/.style = draw,square, blue, left color=blue!20, text=black, inner sep=1pt,gain2/.style = draw,square, red, left color=red!20, text=black, inner sep=1pt,gain3/.style = draw,square, green, left color=green!20, text=black, inner sep=1pt] ]
[main] (1) $v^\ell_{\text{in}}$;
[main1] (2) [above right of=1] $v^\ell_1$;
[gain3] (3) [below right of=1] $v^\ell_2$;
[main] (4) [right of=2] $v^\ell_3$;
[main] (5) [right of=3] $v^\ell_4$;
[main] (6) [below right of=4] $v^\ell_{\text{out}}$;
[main] (7) [right of=4] $s$;
[main,accepting] (8) [right of=5] $t$;
[->] (1) – (2);
[->] (1) – (3);
[->] (2) – (4);
[->] (3) – (5);
[->] (4) – (6);
[->] (5) – (6);
[->] (4) – (7);
[->] (5) – (8);

[node distance=8mm, main/.style = draw,circle, text=black, inner sep=1pt,main1/.style = draw,circle, blue, left color=blue!20, text=black, inner sep=1pt,main2/.style = draw,circle, red, left color=red!20, text=black, inner sep=1pt,main3/.style = draw,circle, green, left color=green!20, text=black, inner sep=1pt,gain1/.style = draw,square, blue, left color=blue!20, text=black, inner sep=1pt,gain2/.style = draw,square, red, left color=red!20, text=black, inner sep=1pt,gain3/.style = draw,square, green, left color=green!20, text=black, inner sep=1pt] ]
[main] (1) $v^\ell_{\text{in}}$;
[main1] (2) [above right of=1] $v^\ell_1$;
[gain3] (3) [below right of=1] $v^\ell_2$;
[main] (4) [right of=2] $v^\ell_3$;
[main] (5) [right of=3] $v^\ell_4$;
[main] (6) [below right of=4] $v^\ell_{\text{out}}$;
[main] (7) [right of=4] $s$;
[main,accepting] (8) [right of=5] $t$;
[->] (1) – (2);
[->] (1) – (3);
[->] (2) – (4);
[->] (3) – (5);
[->] (4) – (6);
[->] (5) – (6);
[->] (4) – (7);
[->] (5) – (8);

[node distance=8.8mm, main/.style = draw,circle, text=black, inner sep=0.5pt,main1/.style = draw,circle, blue, left color=blue!20, text=black, inner sep=0.5pt,main2/.style = draw,circle, red, left color=red!20, text=black, inner sep=0.5pt,main3/.style = draw,circle, green, left color=green!20, text=black, inner sep=0.5pt,gain1/.style = draw,square, blue, left color=blue!20, text=black, inner sep=0.5pt,gain2/.style = draw,square, red, left color=red!20, text=black, inner sep=0.5pt,gain3/.style = draw,square, green, left color=green!20, text=black, inner sep=0.5pt] ]
[gain2] (1) $v^k_{\text{in}}$;
[gain1] (2) [right of=1] $v^k_1$;
[main3] (3) [below of=2] $v^k_2$;
[main] (4) [left of=3] $v^k_3$;
[main] (5) [below right of=4] $s$;
[accepting,main] (6) [below of=4] $t$;

[gain2] (7) [below right of=2] $v^k_4$;
[gain2] (8) [above right of=7] $v^k_5$;
[gain2] (9) [below right of=7] $v^k_6$;
[main3] (10) [right of=8] $v^k_7$;
[main3] (11) [right of=9] $v^k_8$;
[main] (12) [below right of=10] $v^k_{\text{out}}$;
[accepting,main] (13) [right of=10] $t$;
[main] (14) [right of=11] $s$;
[main] (15) [left of=8] $s$;
[accepting,main] (16) [left of=9] $t$;
[->] (1) – (2);
[->] (2) – (3);
[->] (3) – (4);
[->] (4) – (5);
[->] (4) – (6);
[->] (2) – (7);
[->] (7) – (8);
[->] (7) – (9);
[->] (8) – (10);
[->] (9) – (11);
[->] (10) – (12);
[->] (11) – (12);
[->] (10) – (13);
[->] (11) – (14);
[->] (8) – (15);
[->] (9) – (16);

[node distance=8.8mm, main/.style = draw,circle, text=black, inner sep=1pt,main1/.style = draw,circle, blue, left color=blue!20, text=black, inner sep=1pt,main2/.style = draw,circle, red, left color=red!20, text=black, inner sep=1pt,main3/.style = draw,circle, green, left color=green!20, text=black, inner sep=1pt,gain1/.style = draw,square, blue, left color=blue!20, text=black, inner sep=1pt,gain2/.style = draw,square, red, left color=red!20, text=black, inner sep=1pt,gain3/.style = draw,square, green, left color=green!20, text=black, inner sep=1pt,gain4/.style = text=black] ]
[main2] (1) $v^k_{\text{in}}$;
[main1] (2) [right of=1] $v^k_1$;
[gain3] (3) [below of=2] $v^k_2$;
[main] (4) [left of=3] $v^k_3$;
[main] (5) [below right of=4] $s$;
[accepting,main] (6) [below of=4] $t$;
[main2] (7) [below right of=2] $v^k_4$;
[main2] (8) [above right of=7] $v^k_5$;
[main2] (9) [below right of=7] $v^k_6$;
[gain3] (10) [right of=8] $v^k_7$;
[gain3] (11) [right of=9] $v^k_8$;
[main] (12) [below right of=10] $v^k_{\text{out}}$;
[accepting,main] (13) [right of=10] $t$;
[main] (14) [right of=11] $s$;
[main] (15) [left of=8] $s$;
[accepting,main] (16) [left of=9] $t$;
[->] (1) – (2);
[->] (2) – (3);
[->] (3) – (4);
[->] (4) – (5);
[->] (4) – (6);
[->] (2) – (7);
[->] (7) – (8);
[->] (7) – (9);
[->] (8) – (10);
[->] (9) – (11);
[->] (10) – (12);
[->] (11) – (12);
[->] (10) – (13);
[->] (11) – (14);
[->] (8) – (15);
[->] (9) – (16);

From left to right: $\G_\ell$ in open and closed state and $\G_k$ in open and closed state.

We start by showing how the gadget $\G_\ell$ simulates an open lock.

For $i \in \set{1,2}$, if enters $\G_\ell$ in a configuration in $\P^\ell_O$, then he has a strategy such that no matter how responds, either 's objective is satisfied or the game exits $\G_\ell$ in a configurationNot a configuration! in $\P^\ell_O$. That is, the lock $\ell$ is open and stays open after it is traversed.

Suppose that enters $\G_\ell$ in a configuration in $\P^\ell_O$. We describe dominant strategies for the two players that guarantee that both players do not lose and that the gadget is exited. We show that the configuration upon exiting $\G_\ell$ is in $\P^\ell_O$.
The case when enters $\G_\ell$ is dual.

Since enters $\G_\ell$, can grab, and she uses the possibility to grabSimplify: she grabs? $v^\ell_{\text{in}}$ and proceeds to $v^\ell_1$. It is not hard to see that these two actions dominate any other actions.  controls $v^\ell_1$. We claim that if grabs $v^\ell_1$, he will lose the game. Indeed, following 's move in $v^\ell_1$, will grab $v^\ell_3$ and move the token to the sink vertex $s$ to win the game. Thus, it is dominant for not to grab $v^\ell_1$ and keep it in the control of . Following 's move in $v^\ell_1$, grabs $v^\ell_3$ and proceeds to exit $\G_\ell$.
Note that when $\G_\ell$ is exited, maintains control of $v^\ell_2$ and maintains control of $v^\ell_1$, thus the configuration is in $\P^\ell_O$.

Next, we show how $\G_\ell$ simulates a closed lock.

For $i \in \set{1,2}$, if enters $\G_\ell$ in a configurationNot a configuration! in $\P^\ell_C$, then has a strategy that guarantees that 's objective is violated. That is, $\ell$ is closed.

Suppose that enters $\G_\ell$ in a configuration in $\P^\ell_C$. We describe a winning strategy. grabs $v^\ell_{\text{in}}$ and moves the token to $v^\ell_1$. Since controls $v^\ell_1$ he must make the next move. then grabs $v^\ell_3$ and moves the token to $s$ to win the game.

Similarly, we can show a winning strategy for if enters $\G_\ell$ in closed state.

We proceed to describe the gadget $\G_k$ that simulates the key $k \in K$ that corresponds to the lock $\ell$.
We depict $\G_k$ in two configurations in Figures <ref> and <ref>. The vertices $v^k_3$ and $v^k_{\text{out}}$ are controlled by one-vertex pawns. The rest of the vertices in $\G_k$, not including targets, are controlled by three pawns and are depicted using colors. Vertex $v^k_1$ is controlled by a “blue” pawn, who also controls $v^\ell_1$. Vertices $v^k_2$, $v^k_7$, and $v^k_8$ are all controlled by a “green” pawn who also controls $v^\ell_2$. The other vertices are controlled by a “red” pawn. Again, we simulate the properties of a key using the configurations. Let $\P^k_O = \set{P \in 2^\P: \set{v^k_{\text{in}}, v^k_1, v^k_4, v^k_5, v^k_6} \cap P = \emptyset \wedge \set{v^k_2, v^k_7, v^k_8} \subseteq P}$ (see Fig. <ref>). Let $\P^k_C = \set{P \in 2^\P: \set{v^k_{\text{in}}, v^k_1, v^k_4, v^k_5, v^k_6} \subseteq P \wedge \set{v^k_2, v^k_7, v^k_8} \cap P = \emptyset}$ (see Fig. <ref>). Note that $\P^k_O \subseteq \P^\ell_O$ and $\P^k_C \subseteq \P^\ell_O$.

We show how $\G_k$ simulates a key; namely, crossing the gadget turns the key and changes the state of $\ell$.

For $i \in \set{1,2}$, if enters $\G_k$ in a configuration in $\P^k_O$, then he has a strategy such that for all strategies, either 's objective is satisfied or $\G_k$ is exited in a configuration in $\P^k_C$. DuallyI prefer 'similarly'., when enters $\G_k$ in a configuration in $\P^k_C$, for all strategies, either 's objective is satisfied or $\G_k$ is exited in a configuration in $\P^k_O$.

We prove for an entry configuration in $\P^k_C$ and the proof for $\P^k_O$ is dual.

We claim that for $i \in \set{1,2}$, if the token lands on $v^k_2$ when controls that vertex, then loses. Indeed, following 's move at $v^k_2$, grabs $v^k_3$ and directs the token to the winning vertex.
It follows that it is a dominantDefine, or may be even better describe intuitively instead of using the word 'dominant'. strategy for not to grab $v^k_{\text{in}}$ upon entry to $\G_k$ and to allow to move. Following 's move at $v^k_{\text{in}}$, grabs $v^k_1$, and proceeds to $v^k_4$.

Since moves and $v^k_4$ is in the control of , no change of pawns occurs. We claim that it is dominant move for to proceed to $v^k_5$. Indeed, if she proceeds to $v^k_6$, will grab $v^k_6$ and win by moving to $t$. Observe that it is a dominant strategy for to grab the red pawn since it controls $v_5^k$ following 's move from $v^k_4$ to $v^k_5$. Indeed, otherwise proceeds to $s$ to win the game. Finally, following 's move at $v^k_5$, must grab the green pawn since it grabs $v_7^k$, otherwise moves from $v^k_7$ to $t$ to win the game.

To conclude, if the token exists $\G_k$, has grabbed the blue and red pawns and has grabbed the green pawn. The configuration upon exiting $\G_k$ is thus in $\P^k_O$, and we are done.

Now suppose Player i enters the vertex $v_{k_{in}}$ when owns pawn $P_{Green}$ and owns pawn's $P_{Red},P_{Blue}$. would want to control $\G_{k_{in}}$ because if he controls it, then in the next round can control $v_{k_1}$ and move the token to $v_{k_2}$ now this is controlled by thus will have to move the token to $v_3^k$ which can then be controlled by and move the token to sink, which violates objective of . Thus does not grab Pawn $P_{Red}$. Now when moves the token to $v_{k_1}$ is forced to grab $P_{Blue}$ in order to control vertex $v_{k_1}$, he then moves the token to $v_{k_4}$. now moves the token to $v_{k_5}$, note that she can move it to $v_{k_6}$ but then can control $v_{k_6}$ and reach target vertex $v_{k_{t2}}$. Now is forced to grab $P_{Red}$ in order to control $v_{k_5}$ because if he dose not can move the token to sink $v_{k_{s2}}$. Now moves the token to $v_{k_{7}}$ in this round is forced to grab $P_{Green}$ in order to control vertex $v_{k_{7}}$ because can move the token to the target vertex $v_{k_{t1}}$. Hence controls $v_{k_{7}}$ and moves the token to out-vertex $v_{k_{out}}$. Note that now owns Pawns $P_{Red}$,$P_{Blue}$ and owns Pawn $P_{Green}$. similarly we can verify the other direction.

*Putting it all together
We describe the construction of a pawn game $\G'$ from a game $\G$. We assume w.l.o.g. that each edge $\zug{u, v}$ in $\G$ is labeled by at most one lock or key since an edge that is labeled by multiple locks or keys can be split into a chain of edges, each labeled by a single lock or a key.
We describe the construction of $\G'$.
We first apply the construction for turn-based games on $\G$ while “ignoring” the locks and keys. Recall that the construction introduces fresh vertices so that an edge $e = \zug{u,v}$ in $\G$ is mapped to an edge $e' = \zug{u', v}$ in $\G'$. We re-introduce the locks and keys so that the labeling of $e'$ coincides with the labeling of $e$. Next, we replace an edge $e'$ that is labeled by a lock $\ell$, by a copy of $\G_\ell$, and if $e$ is labeled by a key $k$, we replace $e'$ by a copy of $\G_k$. Note that multiple edges could be labeled by the same lock $\ell$. In such a case we use fresh vertices in each copy of $\G_\ell$, but crucially, all gadgets share the same pawns so that they share the same state. And similarly for keys. For an illustration of this construction, see Fig. <ref>, which applies the construction on a game that is output from the reduction in Thm. <ref>.

Finally, given an initial configuration $c = \zug{v, A}$ of $\G$ we define an initial configuration $c' = \zug{v, P}$ of $\G'$. Note that the initial vertex is the entry point of the gadget that simulates $v$ in $\G'$. For each lock $\ell$ and corresponding key $k$, if $\ell$ is open according to $A$, then $P \in \P^\ell_O$, i.e., both $\G_\ell$ and $\G_k$ are initially in open state. And similarly when $\ell$ is closed according to $A$.
Combining the properties in Lemmas <ref>, <ref>, and <ref> implies that wins $\G$ from $c$ iff wins $\G'$ from   $c'$. Thus, by Thm. <ref>, we have the following.

Consider a game $\G$ and configuration $c = \zug{v, A}$ as obtained in Thm. <ref> by a reduction from alternating polynomial space Turing machine.I took care of some changes now; otherwise it may take long to understand all details and correct for someone else.This is not any arbitrary game that is used to show the hardness but the one obtained from the reduction from APSPACE TM. In fact, we refer to Fig. <ref> which is that specific optional-grabbing pawn game.
We assume w.l.o.g. that each edge $\zug{u, v}$ in $\G$ is labeled by at most one lock or key since an edge with multiple locks and keys can be simulated by a sequence of edges, each having a single lock or a single key.
We first apply the construction for turn-based games on $\G$ by “ignoring” the locks and keys to obtain $\G'$.
Recall that for each edge $e = \zug{u,v}$ in $\G$, we have an edge $e' = \zug{u, v'}$ and an edge $e'' = \zug{v', v}$ in $\G'$.
If $e$ is labeled by a lock $\ell$, we replace $e'$ with a copy of $\G_\ell$, and if $e$ is labeled by a key $k$, we replace $e'$ by a copy of $\G_k$.
Fig. <ref>

depicts connection between gadgets and the main vertices of $\G'$.The reference to Fig. <ref> does not suggest how it works. Neither the description of Fig. 4 in  Appendix <ref> is sufficient to show why this specific connection works. Guy: I need to read in depth. I will do it in my pass. Shibashis: I made the changes. It should look better now.

We stress that copies of gadgets use fresh vertices but share the same pawns.
The figure has a closed key $k_j$ followed by an open key $k_i$ and an open lock $\ell_r$ such that $r \neq i$.
Such a sequence of gadgets simulates a transition of the alternating polynomial space Turing machine used in the reduction in Thm. <ref>.
We call this sequence of gadgets a $\delta$-path.

The ownership of the diamond vertices is not fixed; they can be either controlled by or .

An open key represents that the corresponding lock is currently open, and going through this key closes the lock and also the state of the key changes from open to closed.
Similarly, a closed key represents that the corresponding lock is currently closed, and going through this key opens the lock and also the state of the key changes from closed to open.
Recall from the proof of Thm <ref>, that we go through the closed key for lock $\ell_{i, \gamma'}$ to open this lock and the open key for lock $\ell_{i, \gamma}$ to close this lock and finally, the open lock $\ell_{i', \gamma''}$ to simulate a transition of the TM where the tape content in the $i^{th}$ cell changes from $\gamma$ to $\gamma'$ and the tape head moves from cell $i$ to cell $i'$, the latter has $\gamma''$ written in it.
For simplicity of notation, here, we refer to the keys corresponding to the locks $\ell_{i, \gamma'}$ and $\ell_{i, \gamma}$ as $k_i$ and $k_j$ respectively, while we denote by $\ell_r$ the lock $\ell_{i', \gamma''}$.

that the gadget for Key $k_m$ and Lock $\ell_m$ mainly have vertices owned by three pawns $p_{Red_m},p_{Blue_m},p_{Green_m}$.
The pawn $p_{Red_m}$ owns vertices $\{v_{in}^{k_m},v_{4}^{k_m},v_{5}^{k_m},v_{6}^{k_m}\}$, pawn  $p_{Blue_m}$ owns $\{v_{1}^{k_m},v_{1}^{l_m}\}$, and pawn $p_{Green_m}$ owns $\{v_{2}^{k_m},v_{7}^{k_m},v_{8}^{k_m},v_{2}^{l_m}\}$.
In this $\delta$-path we have pawns $p_{Red_m},p_{Blue_m},p_{Green_m}$ for $m=i,j,r$(The pawns $p_{Blue_i},p_{Blue_j},p_{Blue_r}$ are different pawns even though the vertices owned by them have the same colour in a $\delta$-path and the same holds for vertices belonging to pawns $p_{Red}$ and $p_{Green}$.).

MVPP optional-grabbing PAWN-GAMES is EXPTIME-complete.

every edge graph game can be simulated on a optional-grabbing game of poly-size.

Let given edge graph game be $\G$ whose arena is $\zug{V,V_1,V_2,E}$ with initial vertex $v_i$ and target set $T$.
Now consider optional-grabbing game $\G'$ where each pawn controls exactly one vertex whose arena is $\zug{V\cup V',V_1\cup V_1',V_2\cup V_2',E'}$ with initial vertex $v_i$ and target set $T$.
Here $V'=\{v'\ |\ \forall v\in V\}$,$V_1'=\{v'\ |\ \forall v\in V_2\}$,$V_2'=\{v'\ |\ \forall v\in V_1\}$,$E'=\{(v,v')\ |\ \forall v\in V\}\cup \{(u,v')\ |\ \forall (u,v)\in E\}$.

Game $\G$ and $\G'$ are equivalent.
wlog let Player i have a winning strategy in $\G$ then Player i has a winning strategy in $\G'$.
observation to make is that token at $v$ always comes from $v'$. another important observation to make here is that if Player i controls the vertex $v\in V_i$ every time the token is at $v_i$ then Player i has a winning strategy. Now the question is how do we ensure this so the strategy here for Player i is to never grab $V_{-i}'$ vertices from Player -i. thus it will be Player -i who would be getting token to $v\in V_i$ and now in this round Player can grab v.
Hence showed.

§ ALWAYS-GRABBING PAWN GAMES

Consider an always-grabbing game $\G = \zug{V, E, T}$, a configuration $c = \zug{v, P}$ with $v \in V_j$, and let $i \in \set{1,2}$. Consider a configuration $c' = \zug{v, P'}$ with $P' \subseteq P$ under the restriction that if $j \in P$, then $j \in P'$, thus if controls Pawn $j$ in $c$, then he also controls Pawn $j$ in $c'$. If wins from $c$, then wins from $c'$.

Note that the proof of theorem 12 does not use the fact that the grabbing is optional and thus theorem 12 can be extended to always-grabbing game and the proof follows the proof of theorem 12.

In this section, we study always-grabbing pawn games and show that MVPP always-grabbing pawn-games are $\EXP$-complete. The main challenge is proving the lower bound. We proceed as follows.

Let $\M$ be an ATM. Apply the reduction in Thm <ref> and the one in Thm. <ref> to obtain pairs $\zug{\G, c}$ and $\zug{\G', c'}$, where $\G$ and $\G'$ are respectively and optional-grabbing games with initial configurations $c$ and $c'$ respectively.
We devise a construction that takes $\zug{\G', c'}$ and produces an always-grabbing game $\G''$ and a configuration $c''$ such that wins from $c''$ in $\G''$ iff he wins from $c$ in $\G$.

[node distance=9mm, main/.style = draw,circle, text=black, inner sep=1pt,gain/.style = draw,square, text=black, inner sep=1pt,main1/.style = draw,circle, blue, left color=blue!20, text=black, inner sep=1pt,main2/.style = draw,circle, red, left color=red!20, text=black, inner sep=1pt,main3/.style = draw,circle, green, left color=green!20, text=black, inner sep=1pt,gain1/.style = draw,square, blue, left color=blue!20, text=black, inner sep=1pt,gain2/.style = draw,square, red, left color=red!20, text=black, inner sep=1pt,gain3/.style = draw,square, green, left color=green!20, text=black, inner sep=1pt,gain/.style = draw,square, text=black, inner sep=1pt,pain/.style = draw,diamond, text=black, inner sep=1pt]
[main2] (1) $v^{k_i}_{\text{in}}$;
[main1] (2) [right of=1] $v^{k_i}_1$;
[gain3] (3) [below of=2] $v^{k_i}_2$;
[pain] (4) [left of=3] $v^{k_i}_3$;
[pain] (5) [below right of=4] $s$;
[accepting,pain] (6) [below left of=4] $t$;
[main2] (7) [right of=2] $v^{k_i}_4$;
[main2] (8) [above right of=7] $v^{k_i}_5$;
[main2] (9) [below right of=7] $v^{k_i}_6$;
[gain3] (10) [right of=8] $v^{k_i}_7$;
[gain3] (11) [right of=9] $v^{k_i}_8$;
[pain] (12) [below right of=10] $v^{k_i}_{\text{out}}$;
[accepting,pain] (13) [right of=10] $t$;
[pain] (14) [right of=11] $s$;
[pain] (15) [left of=8] $s$;
[accepting,pain] (16) [left of=9] $t$;
[gain2] (111) [right of=12]$v^{k_j}_{\text{in}}$;
[gain1] (112) [right of=111] $v^{k_j}_1$;
[main3] (113) [below of=112] $v^{k_j}_2$;
[pain] (114) [left of=113] $v^{k_j}_3$;
[pain] (115) [below right of=114] $s$;
[accepting,pain] (116) [below left of=114] $t$;
[gain2] (117) [right of=112] $v^{k_j}_4$;
[gain2] (118) [above right of=117] $v^{k_j}_5$;
[gain2] (119) [below right of=117] $v^{k_j}_6$;
[main3] (1110) [right of=118] $v^{k_j}_7$;
[main3] (1111) [right of=119] $v^{k_j}_8$;
[pain] (1112) [below right of=1110] $v^{k_j}_{\text{out}}$;
[accepting,pain] (1113) [right of=1110] $t$;
[pain] (1114) [right of=1111] $s$;
[pain] (1115) [left of=118] $s$;
[accepting,pain] (1116) [left of=119] $t$;
[pain] (20) [right of=1112] $u$;
[pain] (31) [left of=1] $v$;
[pain] (32) [left of=31] $v'$;

[pain] (21) [right of=20]$v^{\ell_r}_{\text{in}}$;
[gain1] (22) [above right of=21] $v^{\ell_r}_1$;
[main3] (23) [below right of=21] $v^{\ell_r}_2$;
[pain] (24) [right of=22] $v^{\ell_r}_3$;
[pain] (25) [right of=23] $v^{\ell_r}_4$;
[pain] (26) [below right of=24] $v^{\ell_r}_{\text{out}}$;
[main] (27) [right of=24] $s$;
[main,accepting] (28) [right of=25] $t$;
[pain] (30) [right of=26] $u'$;
[pain] (33) [right of=30] $v_2'$;
[->] (30) – (33);
[->] (20) – (21);
[->] (26) – (30);
[->] (21) – (22);
[->] (21) – (23);
[->] (22) – (24);
[->] (23) – (25);
[->] (24) – (26);
[->] (25) – (26);
[->] (24) – (27);
[->] (25) – (28);
[->] (1112) – (20);
[->] (12) – (111);
[->] (31) – (1);
[->] (32) – (31);
[->] (111) – (112);
[->] (112) – (113);
[->] (113) – (114);
[->] (114) – (115);
[->] (114) – (116);
[->] (112) – (117);
[->] (117) – (118);
[->] (117) – (119);
[->] (118) – (1110);
[->] (119) – (1111);
[->] (1110) – (1112);
[->] (1111) – (1112);
[->] (1110) – (1113);
[->] (1111) – (1114);
[->] (118) – (1115);
[->] (119) – (1116);
[->] (1) – (2);
[->] (2) – (3);
[->] (3) – (4);
[->] (4) – (5);
[->] (4) – (6);
[->] (2) – (7);
[->] (7) – (8);
[->] (7) – (9);
[->] (8) – (10);
[->] (9) – (11);
[->] (10) – (12);
[->] (11) – (12);
[->] (10) – (13);
[->] (11) – (14);
[->] (8) – (15);
[->] (9) – (16);

A $\delta$-path is a path between two primed main vertices in an optional- or always-grabbing game, and it crosses two key gadgets and one lock gadget.

Our analysis heavily depends on the special structure of $\G'$. The construction in Thm. <ref> outputs a game $\G$ with main vertices of the form $\zug{q,i,\gamma}$ ($q$ is a state, $i$ is a tape position, and $\gamma$ is a letter in the tape alphabet). A play of $\G$ can be partitioned into paths between main vertices.
Each such path corresponds to one transition of the Turing machine and traverses two keys and a lock before again reaching a main vertex.
Recall that when constructing $\G'$ from $\G$, we replace locks and keys with their respective gadgets, and for every vertex $v$ that belongs to $\G$, we add a new primed vertex $v'$ such that if $v$ is controlled by then $v'$ is controlled by .
We call a path in $\G'$ that corresponds to a path in $\G$ between two successive main vertices, say $v$ and $v'$, a $\delta$-path. Fig. <ref>

depicts a $\delta$-path.
The $\delta$-path shown here is along a closed key $k_i$, an open key $k_j$ and an open lock $\ell_r$ such that $r\neq i$.
An open key represents that the corresponding lock is currently open, and going through this key closes the lock and also the state of the key changes from open to closed.
Similarly, a closed key represents that the corresponding lock is currently closed, and going through this key opens the lock and also the state of the key changes from closed to open.
Recall from the proof of Thm <ref>, that we go through the open key for lock $\ell_{i, \gamma'}$ and the closed key for lock $\ell_{i, \gamma}$ and finally, the open lock $\ell_{i', \gamma''}$.
For simplicity of notation, here, we refer to the keys corresponding to the locks $\ell_{i, \gamma'}$ and $\ell_{i, \gamma}$ as $k_i$ and $k_j$ respectively, while we denote by $\ell_r$ the lock $\ell_{i', \gamma''}$.
Recall from Section <ref> that the gadget for Key $k_m$ and Lock $\ell_m$ mainly have vertices owned by three pawns $p_{Red_m},p_{Blue_m},p_{Green_m}$.
$p_{Red_m}$ owns vertices $\{v_{in}^{k_m},v_{4}^{k_m},v_{5}^{k_m},v_{6}^{k_m}\}$, pawn  $p_{Blue_m}$ owns $\{v_{1}^{k_m},v_{1}^{l_m}\}$, and pawn $p_{Green_m}$ owns $\{v_{2}^{k_m},v_{7}^{k_m},v_{8}^{k_m},v_{2}^{l_m}\}$.
In this $\delta$-path we have pawns $p_{Red_m},p_{Blue_m},p_{Green_m}$ for $m=i,j,r$ (The pawns $p_{Blue_i},p_{Blue_j},p_{Blue_r}$ are different pawns even though the vertices owned by them have the same colour in a $\delta$-path and the same holds for vertices belonging to pawns $p_{Red}$ and $p_{Green}$.).
The ownership of the diamond vertices is not fixed; they can be either controlled by or .

An important property of the specific optional-grabbing game $\G'$ that is constructed in Thm <ref> from an ATM is that every play of $\G'$ consists of a sequence of $\delta$-paths.

The following observation can easily be verified:

A $\delta$-path from $v'$ to $v_2'$ consists of 20 turns.

The following lemma is crucial for the construction of

The proof of this lemma is obtained by proving several claims made below.

For $i \in \set{1,2}$, if has a strategy in the optional-grabbing game $\G'$ to cross a $\delta$-path from $v'$ to $v_2'$, then has a strategy that moves the token in at least $10$ rounds and moves the token in at most 10 rounds in the $\delta$-path.

We will prove this lemma for $i=1$ that is for .
The proof for is similar.
This follows from the fact that in Figure <ref>, the vertices controlled initially by in Key $k_i$ have their corresponding vertices in Key $k_j$ that are initially controlled by .
Further, the gadget for the Lock $\ell_r$ is symmetric for both players.

In order to prove the lemma we first prove some claims.
Note that in all these claims, we talk about a particular player controlling a vertex, for example, in Claim <ref>, we say that controls $v_{1}^{l_r}$, because can ensure that the game reaches such configuration from vertex $v'$.

We can indeed show that has a strategy such that in the $\delta$-path, controls vertex $v_{1}^{l_r}$ when the token reaches this vertex.
Refer to Figure <ref> in the following claims.

If controls vertex $v_{1}^{l_r}$ then has a strategy from $v_{1}^{l_r}$ to reach $v_2'$ which ensures that out of the 4 rounds that moves the token to $v_2'$, he moves the token in at least 2 rounds.

Suppose the token is at vertex $v_{1}^{l_r}$ and controls $v_{1}^{l_r}$.
Then moves the token from $v_{1}^{l_r}$ to $v_{3}^{l_r}$.
can now grab a pawn.
If controls vertex  $v_{3}^{l_r}$, grabs the pawn owning this vertex else he chooses to not grab a pawn.
Note that under both the cases by the end of this round controls vertex $v_{3}^{l_r}$. He now moves the token to $v_{out}^{l_r}$.
Note that till now has moved the token in one round.
Now by the end of this round there are two possible cases:

*  controls $v_{out}^{l_r}$. In this case moves the token to $u'$, and thus it has moved the token in two rounds, and hence regardless of what happens in next round the claim holds.

*  controls $v_{out}^{l_r}$. In this case moves the token to $u'$ and now can control $u'$ and move the token to $v_2'$, which will be his second instance of moving the token and thus the claim holds.

Hence showed.

If controls vertex $v_{2}^{l_r}$ then he has a strategy from $v_{2}^{l_r}$ to reach $v_2'$ which ensures that, out of the 4 rounds that moves the token from $v_2^{l_r}$ to $v_2'$, he moves the token in at least 2 rounds.

Suppose the token is at vertex $v_{2}^{l_r}$ and controls $v_{2}^{l_r}$.
Then moves the token from $v_{2}^{l_r}$ to $v_{4}^{l_r}$.
Now if has the pawn owning vertex $v_{4}^{l_r}$, then is forced to grab this pawn in this round. Thus by the end of this round controls $v_{4}^{l_r}$.
Now moves the token from $v_{4}^{l_r}$ to $v_{out}^{l_r}$.
now can grab a pawn. If controls vertex  $v_{out}^{l_r}$, grabs the pawn owning this vertex else he chooses to not grab a pawn.
Note under both the cases by the end of this round controls vertex $v_{out}^{l_r}$. He now moves the token to $u'$, which will be his second instance of moving the token and thus the claim holds.

If controls vertex $v_{out}^{k_j}$ then he has a strategy from $v_{out}^{k_j}$ to reach $v_2'$ which ensures that, out of the 7 rounds that moves the token from $v_{out}^{k_j}$ to $v_2'$ he moves the token in at least 4 rounds.

Suppose the token is at vertex $v_{out}^{k_j}$ and controls $v_{out}^{k_j}$.
Then moves the token from $v_{out}^{k_j}$ to $u$.
Now by the end of this round there are two possible cases:

*  controls $u$. In this case moves the token to $v_{in}^{l_r}$.
Note that till now has moved the token in two rounds. Now again by the end of this round there are two possible cases:

*  controls $v_{in}^{l_r}$. In this case moves the token to $v_1^{l_r}$. Now note that the token is at vertex $v_1^{l_r}$ and controls $v_1^{l_r}$. Thus by Claim <ref> we know that from here moves the token in at least 2 rounds before reaching $v_2'$.
As till now when the token is at $v_1^{l_r}$ has moved the token in three rounds, thus overall under this case moves the token in at least 5 rounds.

*  controls $v_{in}^{l_r}$. In this case either moves the token to the vertex $v_{1}^{l_r}$ in which case chooses to not grab.
Now note that the token is at vertex $v_1^{l_r}$ and controls $v_1^{l_r}$. Thus by Claim <ref> we know that from here moves the token in at least 2 rounds before reaching $v_2'$.
Otherwise suppose from $v_{in}^{l_r}$ moves the token to vertex $v_{2}^{l_r}$, in which case chooses to not grab.
Now note that here the token is at vertex $v_2^{l_r}$ and controls $v_2^{l_r}$. Thus by Claim <ref> we know that from here moves the token in at least 2 rounds before reaching $v_2'$.
Thus in this case from $v_{in}^{l_r}$ moves the token in at least two rounds.
As till reaching $v_{in}^{l_r}$ has moved the token in two rounds, thus overall under this case moves the token in at least 4 rounds as the token reaches $v_2'$.

*  controls $u$. In this case moves the token to $v_{in}^{l_r}$.
now can grab a pawn. If controls the vertex  $v_{in}^{l_r}$, grabs the pawn owning this vertex else he choose to not grab a pawn.
Note under both the cases by the end of this round controls vertex $v_{in}^{l_r}$.
He now moves the token to $v_1^{l_r}$. Now note that the token is at vertex $v_1^{l_r}$ and controls $v_1^{l_r}$ thus by Claim <ref> we know that from here moves the token in at least two rounds before reaching $v_2'$.
As till reaching $v_1^{l_r}$ has moved the token in two rounds, thus overall under this case moves the token in at least 4 rounds.

Hence showed.

If controls vertex $v_{in}^{k_j}$, then has a strategy from $v_{in}^{k_j}$ to reach $v_2'$ which ensures that, out of the 12 rounds that moves the token from $v_{in}^{k_j}$ to $v_2'$ he moves the token in at least 6 rounds.

Suppose the token is at vertex $v_{in}^{k_j}$ and controls $v_{in}^{k_j}$.
Then moves the token from $v_{in}^{k_j}$ to $v_1^{k_j}$. In this round grabs pawn $p_{Blue_j}$ inorder to control $v_1^{k_j}$.
Now controls $v_1^{k_j}$, he moves the token to vertex $v^{k_j}_4$.
In the next round moves the token from $v^{k_j}_4$ to $v^{k_j}_5$. in this round grabs $p_{Red_j}$ inorder to control $v^{k_j}_5$. Now moves the token from $v^{k_j}_5$ to $v^{k_j}_7$. Here grabs $p_{Green_j}$ inorder to control $v^{k_j}_7$. Now moves the token from $v^{k_j}_7$ to $v^{k_j}_{out}$. now can grab a pawn. If controls vertex  $v^{k_j}_{out}$, grabs the pawn owning this vertex else he choose to not grab a pawn.
Note under both the cases by the end of this round controls vertex $v_{out}^{k_j}$.
Now note that the token is at vertex $v_{out}^{k_j}$ and controls $v_{out}^{k_j}$. Thus by Claim <ref> we know that from here moves the token in at least 4 rounds before reaching $v_2'$.
As till reaching $v_{out}^{k_j}$ has moved the token in two rounds, thus overall under this case moves the token in at least 6 rounds.

If controls vertex $v_{in}^{k_i}$, then he has a strategy from $v_{in}^{k_i}$ to reach $v_2'$ which ensures that, out of the 18 rounds that moves the token to $v_2'$ he moves the token in at least 9 rounds.

controls vertex $v_{in}^{k_i}$, he moves the token to $v_1^{k_i}$, now grabs $p_{Blue_i}$ in order to control $v_1^{k_i}$.
In the next round moves the token to $v_4^{k_i}$. In this round does not grab a pawn.
Now since $p_{Red_i}$ belongs to and $p_{Red_i}$ owns $v_4^{k_i}$, moves the token to $v_6^{k_i}$.
In this round is forced to grab $p_{Red_i}$ in order to control $v_6^{k_i}$.
Now since here controls $v_6^{k_i}$, she moves the token to $v_8^{k_i}$. Now grabs $p_{Green_i}$ and controls $v_8^{k_i}$.
In the next round moves the token to $v_{out}^{k_i}$.
Now observe that till now has moved the token in three rounds.
Now by the end of this round there two possible cases:

*  controls $v_{out}^{k_i}$. In this case moves the token to $v_{in}^{k_j}$, here chooses to not grab a pawn.
Now observe that the token is at vertex $v_{in}^{k_j}$ and controls vertex $v_{in}^{k_j}$ thus by claim <ref> we know that from here moves the token in at least 6 rounds before reaching $v_2'$.
As until reaching $v_{in}^{k_j}$ has moved the token in three rounds, thus overall under this case moves the token in at least 9 rounds.

*  controls $v_{out}^{k_i}$. In this case moves the token to $v_{in}^{k_j}$. Now note that controls $v_{in}^{k_j}$.
Thus the token is at the vertex $v_{in}^{k_j}$ and controls vertex $v_{in}^{k_j}$.
Now by Claim <ref>, we know that from here moves the token in at least 6 rounds before reaching $v_2'$.
As until reaching $v_{in}^{k_j}$ has moved the token in four rounds, thus overall under this case moves the token in at least 10 rounds.

Hence showed.

Now let us prove the lemma.
So the token is at vertex $v'$.
There are two possible cases:

*  controls $v'$. In this case moves the token to  $v$. Now regardless of who controls, $v$ the token reaches $v_{in}^{k_i}$ with controlling vertex $v_{in}^{k_i}$. Note that will not control $v_{in}^{k_i}$ as he would like to control $v_{1}^{k_i}$. As till reaching $v_{in}^{k_i}$ moved the token in atleast one round and by Claim <ref> we know that from here moves the token in at least 9 rounds before reaching $v_2'$, thus overall moves in at least 10 rounds before reaching $v_2'$.

*  control $v'$. In this case moves the token to $v$.
now can grab a pawn.
If controls vertex  $v$, grabs the pawn owning vertex $v$ else he chooses to not grab a pawn.
Note under both the cases by the end of this round controls the vertex $v'$. He now moves the token to $v_{in}^{k_i}$. Again note that will not control $v_{in}^{k_i}$ as he would like to control $v_{1}^{k_i}$.
As until reaching $v_{in}^{k_i}$ moved the token in one round and by Claim <ref> we know that from here moves the token in at least 9 rounds before reaching $v_2'$. Thus overall moves in at least 10 rounds before reaching $v_2'$.

This concludes the proof of the lemma.

First, we show the EXPTIME-hardness by directly simulating an alternating PSPACE Turing machine.
Let $\M$ be an alternating PSPACE Turing machine.
Let $G$ be the Lock & Key game as defined in Theorem 2 that simulates $\Aa$.
Let $G'$ be the optional-grabbing game reduced from $G$ following the construction described in Section 6.2.
In this section we will show a reduction from the optional-grabbing game $G'$ to an always-grabbing game $G''$.
Note that since $G'$ simulates alternating PSPACE Turing machine, $G''$ also simulates alternating PSPACE Turing machine. This concludes that always-grabbing game are EXPTIME-hard.

So our objective now is to show the reduction from an optional-grabbing game $G'$ to an always-grabbing game.
Let us first recall the game arena of $G'$.
Recall from the proof of Theorem 6.2 that in Lock & Key game $G$, we have main vertices of the form $\zug{q,i,\gamma}$ where $q$ is a state, $i$ is a tape position, and $\gamma$ is a letter in the tape alphabet.
From every main vertex, the token passes through two keys and a lock to come back again to a main vertex.
Now recall the construction of the optional-grabbing game $G'$ from the Lock & Key game, defined in Section 6.2.correct the reference.
We replace edges with locks and keys with their respective gadgets, and for every vertex $v$ that belongs to the Lock & Key game $G$, we add a new primed vertex $v'$ such that if $v$ is controlled by then $v'$ is controlled by .Shorten.
We call such a path with two key gadgets and a lock gadget a $\delta$-path. Formally,

($\delta$-path) A $\delta$-path is a path that starts at a primed main vertex, goes to the corresponding main vertex, then goes along two gadgets corresponding to two keys (one open and other closed) and finally along the gadget corresponding to an open lock to a primed main vertex.

Figure <ref> in Appendix <ref> shows the structure of $\delta$-path.
We will use the fact that the length of a $\delta$-path from a primed main vertex $v$ to another primed main vertex $v'$ is $20$.

The following lemma is crucial for the construction of an always-grabbing game from an optional-grabbing game.
It suggests that if has a strategy to move along the $\delta$-path, then he also makes a move along the $\delta$-path for at least $10$ times.
This allows to grab at least $10$ times.
The lemma would imply that whenever does not grab a pawn in the optional-grabbing game, in the always-grabbing game, would be in possession of a pawn that can grab.
Further, we show that if has a winning strategy in the optional-grabbing game, then he also has one in the always-grabbing game.

For $i \in \set{1,2}$, if has a strategy in an optional-grabbing game to reach $v_2'$ from $v'$ then has a strategy such that along every $\delta$-path out of the 20 rounds, moves the token in at least 10 rounds before reaching $v_2'$, and thus moves the token in at most 10 rounds in a $\delta$-path.

Let $\G' = \zug{V', E', T'}$ with $d$ pawns. The game $\G''$ is constructed from $\G'$ by adding $2(d+10)$ fresh isolated vertices each owned by a fresh unique pawn. Formally, $\G'' = \zug{V'', E', T'}$, where $V'' = V' \cup \{v_1,v_2,\dots,v_{2(d+10)}\}$ such that $v_j \notin V'$, for $j \in [2(d+10)]$. Consider a configuration $c' = \zug{v, P}$ in $\G'$. Let $c'' = \zug{v, P \cup \set{1,2,\ldots,d+10}}$ be a configuration in $\G''$.
Note that Lemma <ref> also applies to the always-grabbing game $\G''$, and we get the following.

For $i \in \set{1,2}$, if has a strategy in the always-grabbing game $\G''$ to cross a $\delta$-path from $v'$ to $v_2'$, then has a strategy such that out of the $20$ rounds in the $\delta$-path, the following hold.

* grabs a pawn in at least $10$ rounds, and

* grabs a pawn in at most $10$ rounds.

Corollary <ref> follows directly from Lemma <ref> since in an always-grabbing game, the number of times grabs equals the number of times moves.

In the remaining part of this section, we show that wins $\G'$ from $c'$ iff wins $\G''$ from the configuration $c''$ described above.

Now recall from Section <ref>, that in $G'$, the initial vertex can be considered to be a primed main vertex, and the target set can be considered to be the set of the corresponding primed main vertices.
Now note that from every primed main vertex in $G'$, a $\delta$-path in a play starts from a primed main vertex and returns to a primed main vertex.
Also note that, the game $G'$ starts at a primed main vertex and if the play that simulates an alternating PSPACE Turning machine is finite, then the game ends in a primed main vertex.
Thus an important property of optional-grabbing game $G'$ is that every play on the game arena of $G'$ that simulates the alternating PSPACE Turing machine consists of a sequence of $\delta$-paths.

So we have the initialized optional-grabbing game $G'$.
Let $\Aa' = (V',(V'_1, \dots, V'_k),E')$ be the arena of $G'$, let $v_i$ be the initial vertex, let $P_1$ be the set of pawns belonging to initially, and let $\phi'$ be the objective of ,

and let $k$ be the total number of pawns in game $G'$.
Now we construct a new pawn game $G''$ and show that has a winning strategy for the always-grabbing mechanism in $G''$ if and only if has a winning strategy for the optional-grabbing mechanism in $G'$.
The game $G''$ has an arena $\Aa'' = (V'',(V'_1, \dots, V'_{k'}),E')$ where $\Aa''$ consists of $\Aa'$ and $2(k+10)$ new isolated vertices owned by $2(k+10)$ new pawns.
Formally, $V'' = V' \cup \{v_1,v_2,\dots,v_{2k+10}\}$ such that $v_i \notin V'$ for $i \in [2(k+10)]$, and $k'=k+2(k+10)$ such that each of the newly added vertices is owned by a new pawn.
The initial vertex is the same as that of $G'$ and the initial pawn set is $P_{1}\cup \{k+1,\dots, k+10\}$, i.e. half of the newly added pawns in $G''$ are initially owned by while the remaining half are owned by .

We show that for $i \in \set{1,2}$, we have that wins the optional-grabbing game $G'$ iff wins the always-grabbing game $G''$ with the initial set of pawns as described above.
First let us prove one direction.

For $i \in \set{1,2}$, if wins the optional-grabbing game $\G'$ from $c'$, then he wins the always-grabbing game $\G''$ from $c''$.

We consider the case for , and the case for is analogous.
Assume that has a winning strategy $f'$ in $\G'$. follows a strategy $f''$ in $\G''$ that mimics $f'$ with the following difference. Whenever $f'$ chooses not to grab, in order to follow the rules of the always-grabbing mechanism, $f''$ grabs an isolated pawn. This is possible since we show we maintain the invariant that at the beginning of a $\delta$-path, has at least $10$ isolated pawns. Note that the invariant holds initially due to the definition of $c''$. We show that it is maintained. By Lem. <ref>, moves in at least $10$ rounds. Thus, moves in at most $10$ rounds, and during each such round, grabs a pawn. Hence, grabs at most $10$ times. In Appendix <ref>, we show that $f''$ is a winning strategy.

We consider the case for .
The case for is analogous.
Assume that has a winning strategy in the optional-grabbing game.
Note that in the always-grabbing game, starts with an initial set of $10$ isolated pawns, and every time the game is at the beginning of a $\delta$-path, has at least $10$ isolated pawns.
Now by Lemma <ref>, moves in at least $10$ rounds, and hence moves in at most $10$ rounds, and during each such round, grabs a pawn.
Thus grabs at most $10$ times.
uses a strategy in the always-grabbing game such that whenever he does not grab a pawn in the optional-grabbing game, he grabs a pawn controlling an isolated vertex from in the always-grabbing game.
Moreover, in Appendix <ref>, we show that cannot win the always-grabbing game when uses such a strategy.

Note that since Lemma <ref> holds for both players, the converse follows from determinacy of pawn games (Thm. <ref>).

wins from $c'$ in the optional-grabbing game $\G'$ iff he wins from $c''$ in the always-grabbing game $\G''$.

For $i \in \set{1,2}$, wins from $c'$ in the optional-grabbing game $\G'$ iff he wins from $c''$ in the always-grabbing game $\G''$.

We first give an outline of the proof before proceeding to proving the lemma formally.
We prove that if has a winning strategy $f'$ in $\G'$ from $c'$, then he has a winning strategy $f''$ from $c''$ in $\G''$.
The case for is analogous and the other direction follows from determinacy (Thm. <ref>.

We construct $f''$ to mimic $f'$ with the following difference.
Whenever $f'$ chooses not to grab, in order to follow the rules of the always-grabbing mechanism, $f''$ grabs a pawn owning an isolated vertex.
This is possible since we show that we maintain the invariant that along a play in $\G''$ that consists of sequences of $\delta$-paths, at the beginning of each $\delta$-path, has at least $10$ isolated pawns.
Note that the invariant holds initially due to the definition of $c''$.
We show that it is maintained.
Recall from the proof of Theorem <ref> that crossing a $\delta$-path simulates a transition in the Turing machine.
Since $\PO$ has a winning strategy in $\G'$, in a winning play, the strategy enables her to cross the $\delta$-path.
Thus, by Lem. <ref>, moves in at least $10$ rounds.
Thus, moves in at most $10$ rounds, and during each such round, grabs a pawn.
Hence, grabs at most $10$ times which thus maintains the invariant.

We show that $f''$ is a winning strategy.

We now formally prove each of the claims stated above.
Now since for , grabbing an isolated pawn serves no extra purpose than grabbing nothing, the action of not grabbing in the optional-grabbing game can be replaced with grabbing a pawn owning an isolated vertex in the always-grabbing game $\G''$.

Now assuming that has a winning strategy $f'$ in the optional-grabbing game $\G'$, consider a winning play $\pi'$ for in $\G'$.
Now assume that in every round in which does not grab a pawn in $\G'$ can be replaced with grabbing a pawn owning an isolated vertex in the always-grabbing game $\G''$.
Thus consider a strategy $f''$ of and a strategy of such that in the resulting play grabs a pawn owning an isolated vertex from if in the corresponding round in the optional-grabbing game he does not grab anything, otherwise, $f''$ follows the moves of $f'$.

Now consider that chooses strategy $f''$.
Recall that $f'$ is winning for in $\G'$.
We argue that cannot win in $\G''$ against the strategy $f''$ of .
Suppose uses a strategy and grabs some pawns owning non-isolated vertices while playing against strategy $f''$  of $\PO$ in rounds other than those rounds in $G'$ i which he grabs the pawns owning non-isolated vertices while playing against strategy $f'$ of .
Then the resulting play in the always-grabbing game will still be losing for , since otherwise, could have followed the same order of grabbing the non-isolated pawns in the optional-grabbing game $\G'$ and would have won the optional-grabbing game.
This contradicts that $f'$ is winning for in the optional-grabbing game.
This implies that if has a winning strategy in the optional-grabbing game $\G'$ from the configuration $\zug{v,P}$, then he has a winning strategy in the always-grabbing game $\G''$ from the configuration $\zug{v, P \cup \{1, \dots, d+10\}}$.

We now only need to show that in every round in $G''$ where moves the token, has an isolated pawn for to grab.
We consider the following claim.

In the always-grabbing game $G''$, for strategy $f''$ of and some strategy of , every time the token is at a primed main vertex, that is, at the beginning of a $\delta$-path, owns at least $10$ pawns owning the isolated vertices.

Consider the case in which at a primed main vertex $v$, has $r$ pawns and the token is at $v$.
Now suppose that the token is moved along a $\delta$-path to the next primed main vertex $v'$.
Note that at this next primed vertex $v'$, has at least $r$ pawns.
This clearly holds since by

Corollary <ref>, along the $\delta$-path, $\PO$ grabs at most $10$ pawns and grabs at least 10 pawns.
Thus, after traversing a $\delta$-path, the number of pawns that controls does not decrease.
Now, in a play, every time the token is at a primed main vertex in $\G''$, it goes along a $\delta$-path to reach the next primed main vertex again.
Now the initial vertex is a primed main vertex and has $(d- |P|)+(d+10)$ pawns at the beginning.
Here $P$ is the initial set of pawns owned by in optional-grabbing game $\G'$.
Thus, every time the token reaches a primed main vertex afterwards, $\PT$ has at least $(d- |P|)+(d+10)$ pawns.
Now since there are exactly $d$ non-isolated pawns, and $(d- |P|)+(d+10)\geq (d+10)$, we have that out of the pawns that has at a primed main vertex, at least $10$ are isolated pawns.
Hence proved.

Now to prove Lemma <ref>, since by Corollary <ref>, we know that has a strategy in the always-grabbing game such that from a primed main vertex to reach the next primed main vertex, he needs to grab in at most 10 rounds, and since by Claim <ref>, has at least $10$ pawns owning isolated vertices, whenever the token is at primed main vertex, in every round between primed main vertices where needs to grab, has an isolated pawn that can grab.
Hence by the argument above, if has a winning strategy in the optional-grabbing game $\G'$, we have that also has a winning strategy in the always-grabbing game $\G''$.

Note that the proof of this direction is also analogous for .
We show that if has a winning strategy in $\G'$, then she also has a winning strategy in $\G''$.
In particular, from Corollary <ref>, along a $\delta$-path, grabs in at least $10$ rounds and grabs in at most $10$ rounds.
Also, similar to Claim <ref>, we can show that every time the token is at a primed main vertex, owns at least $10$ pawns owning isolated vertices.
This is because initially, controls $|P|+d+10$ vertices and this invariant is maintained throughout the play whenever the token reaches a primed main vertex.
Now $|P|+d+10 \geq d+10$, and hence, at the beginning of a $\delta$-path, controls at least $10$ pawns owning isolated vertices.

For the converse direction in Lemma <ref>, we use the determinacy argument as follows.
Again, we show the proof for that if wins in the always-grabbing game $\G''$, then he also wins the optional-grabbing game $\G'$.
The proof for is analogous.

Let has a winning strategy in $\G''$.
Then, by determinacy, loses in $\G''$.
Now from Lemma <ref>, by taking the contrapositive for , we have that also loses $\G'$.
Hence, again by determinacy of pawn games, we have that wins $\G'$.

We now state the following theorem.
While the lower bound follows from Thm. <ref> and Lem. <ref>, the upper bound follows from Thm. <ref>.

MVPP always-grabbing PAWN-GAMES is $\EXP$-complete.

We conclude this section by adapting Thm. <ref> to always-grabbing. Namely, we show that adding pawns to a player is never beneficial in MVPP always-grabbing games (with the exception of the pawn that owns the current vertex).

Consider a configuration $\zug{v, P}$ of an MVPP always-grabbing pawn game $\G$. Let $j \in [d]$ such that $v \in V_j$ and $P' \subseteq P$. Assuming that $j \in P$ implies $j \in P'$, if wins from $\zug{v, P}$, he wins from $\zug{v, P'}$. Assuming that $j \in \overline{P'}$ implies $j \in \overline{P}$, if wins from $\zug{v, P'}$, she wins from $\zug{v, P}$.

We show the case when has a winning strategy.
The case for having a winning strategy is analogous.
Recall from the proof of Thm. <ref> that the cases were argued for both configuration vertices and intermediate vertices.
For configuration vertices, The proof of this theorem is exactly the same as in the proof of Thm. <ref>.
We detail below the case for intermediate vertices in the case of always-grabbing games.
We use the same notations as in the proof of Thm. <ref>.

As in the proof of Thm. <ref>, we again distinguish between two cases: $j \in P$ and $j \notin P$.
Consider an intermediate vertex $\zug{u, c} \in W_{n+1}$.
We will show that $\zug{u, c'} \in W_{n+1}$.
We denote by $\ell$, the pawn that owns $u$.

First consider $j \in P$, thus controls $c$.
We have as in the proof of Thm. <ref> that both $\zug{u, c}$ and $\zug{u, c'}$ are vertices.
Consider a neighbor of $\zug{u, c'}$, a configuration vertex $\zug{u,Q'}$.
Note that in always-grabbing has to grab a pawn $r$ from , thus $Q'=P' \setminus \set{r}$.
There are two cases, either $\ell \in Q'$ or $\ell \notin Q'$.
Recall that in order to apply the induction hypothesis on $\zug{u, Q'}$, we need to find a neighbor $\zug{u, Q}$ of $\zug{u, c}$ such that if $\ell \notin Q'$, then $\ell \notin Q$.
If $\ell \notin Q'$, then we set $Q = P \setminus \{\ell\}$ if $\ell \in P$ and we set $Q = P \setminus \{r\}$ when $\ell \notin P$.
If $\ell \in Q'$, we set $Q = P \setminus \{r\}$.

The rest of the argument is as in the proof of Theorem <ref>.

Next consider the case when $j \notin P$.
In this case, both $\zug{u, c}$ and $\zug{u, c'}$ are vertices.
In always-grabbing, grabs a pawn $r$ in $\zug{u, c}$, thus we have $Q = P \cup \{r\} \supsetneq P$.
We find a neighbor $\zug{u, Q'}$ of $\zug{u, c'}$ to apply the induction hypothesis on.
If $\ell \in P$ and $\ell \in P'$, then we set $Q' = P' \cup \{r\}$.
If $\ell \in P$ and $\ell \notin P'$, then we set $Q' = P' \cup \{\ell\}$.
If $\ell \notin P$ and $\ell \notin P'$, then we set $Q' = P' \cup \{r\}$.
Again, the remaining argument is as in the proof of Theorem <ref> and we are done.

Further, we note that Thm. <ref> also holds true when we consider always-grabbing games instead of optional-grabbing games.
The proof of  result

appears in App. <ref>.

§ ALWAYS GRABBING-OR-GIVING PAWN GAMES

In this section, we show that MVPP always grabbing or giving games are in PTIME. Consider an always grabbing of giving game $\G = \zug{V, E, T}$. Our algorithm is based on the following observation. Suppose that has moved from $u$ to $v$ in $\G$, for $i \in \set{1,2}$. Then, 's choices reduce to two options: (1) decide how to move the token from $v$ by grabbing control of $v$, or (2) allow to move from $v$, and in exchange decides who moves in the following round, by giving control of $v$. Crucially, moves do not depend on the whole set of pawns that a player controls.