{'fraction_non_alphanumeric': 0.038527615169254265, 'fraction_numerical': 0.007126495291422754, 'mean_word_length': 4.120215018732693, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the complexity of Nash dynamics and Sink Equilibria

Studying Nash dynamics is an important approach for analyzing the outcome of games with repeated selfish behavior of self-interested agents. Sink equilibria has been introduced by Goemans, Mirrokni, and Vetta for studying social cost on Nash dynamics over pure strategies in games. However, they do not address the complexity of sink equilibria in these games. Recently, Fabrikant and Papadimitriou initiated the study of the complexity of Nash dynamics in two classes of games. In order to completely understand the complexity of Nash dynamics in a variety of games, we study the following three questions for various games: (i) given a state in game, can we verify if this state is in a sink equilibrium or not? (ii) given an instance of a game, can we verify if there exists any sink equilibrium other than pure Nash equilibria? and (iii) given an instance of a game, can we verify if there exists a pure Nash equilibrium (i.e, a sink equilibrium with one state)? In this paper, we almost answer all of the above questions for a variety of classes of games with succinct representation, including anonymous games, player-specific and weighted congestion games, valid-utility games, and two-sided market games. In particular, for most of these problems, we show that (i) it is PSPACE-complete to verify if a given state is in a sink equilibrium, (ii) it is NP-hard to verify if there exists a pure Nash equilibrium in the game or not, (iii) it is PSPACE-complete to verify if there exists any sink equilibrium other than pure Nash equilibria. To solve these problems, we illustrate general techniques that could be used to answer similar questions in other classes of games.


Introduction
A standard approach in studying the outcome of a system involving self-interested behavior of agents is to investigate the Nash dynamics of the corresponding games. In Nash dynamics, agents repeatedly respond to the current state of the game by playing a best-response strategy. Studying such dynamics is very important for understanding the behavior of a system throughout time, and the outcome of the game after many repeated game play. Similar to the recent efforts in studying the complexity of game theoretic concepts such as mixed Nash equilibria [8,4], and pure NE [10,21], studying the complexity of Nash dynamics can help us better understand the outcome of a game.
In an attempt to study such dynamics for pure strategies, Goemans, Mirrokni, and Vetta [15] introduced the concept of sink equilibria in games: sink equilibria are strongly connected components of a strategy profile graph associated with the game with no outgoing edges. Equivalently, sink equilibria characterize all states for which the probability of reaching that state after a sufficiently large random best-response sequence is nonzero. Also any random best-response sequence will converge to a sink equilibrium with probability one. Moreover, sink equilibria generalize pure Nash equilibria in that a pure Nash equilibrium is a single-state sink equilibrium of the game.
Goemans et al. [15] studied sink equilibria for their social cost in two classes of games. However, they did not consider the complexity of sink equilibria or Nash dynamics in those games. Recently, Fabrikant and Papadimitriou [11] initiated the study of the complexity of sink equilibria. by studying the problem of verifying if a state is in a sink equilibria for two classes of games. Extending on these ideas, we formalize several questions related to Nash dynamics of various games and completely study the complexity of the Nash dynamics and sink equilibria in these games.
Sink equilibria characterize all strategy profiles in the game with a nonzero probability of reaching them after a long enough best-response walk. Therefore, given a strategy profile, in order to verify if there is a non-zero probability of reaching this state after a sufficiently long random best-response walk we need to verify if this state is in a sink equilibrium or not. This problem has been considered by Fabrikant and Papadimitriou [11] for two classes of games, and is as follows: In a Sink problem. Given an instance of a game and a strategy profile in this game, can we verify if this strategy profile belongs to any sink equilibria or not?
For a given state in a game, an interesting problem is to estimate the probability of reaching this state after a long random best-response walk. Note that a hardness result for in a sink problem implies that for a given state, even approximating this probability is a computationally hard problem, (since distinguishing the probability of zero and nonzero is hard). Fabrikant and Papadimitriou showed that in a sink problem is PSPACE-hard for graphical games and a BGP next-hop routing game [11]. We show that this problem is PSPACE-complete for weighted/player-specific congestion games, valid-utility games, two-sided market games, and anonymous games. The proofs for all the above games except anonymous games are similar and based on a reduction from halting problem of a space bounded Turing machine. The proof for anonymous games has unique features and is different from the rest.
Given an instance of a game, it is very helpful to know if the random repeated self-interested actions of the agents in the game can cycle forever or such dynamics will converge to a pure Nash equilibria with probability one. This problem is related to characterizing the structure of sink equilibria in a game, and in particular the existence of non-singleton sink equilibria. Having such a sink equilibrium indicates that even random Nash dynamics may also converge to an everlasting cycle. As a result, we formalize the following problem in games: Has a Non-singleton Sink problem. Given an instance of a game, can we verify if this game possesses a non-singleton sink equilibrium, i.e., sink equilibria other than pure Nash equilibria.
Pure Nash equilibria (if they exist) are local optima of the Nash dynamics. Other than the problem of computing a pure Nash equilibrium in various games, the problem of verifying if such equilibria exist has been studied for various classes of games. We complement the previous questions with the following problem: Has a Singleton Sink problem. Given an instance of a game, can we verify if this game possesses a pure Nash equilibrium (singleton sink equilibrium)?
Answering all the above questions for a game gives a thorough understanding of the complexity of Nash dynamics and the complexity of characterizing sink equilibria in that game. Our Results. We study the above four problems in a variety of games with succinct representation including player-specific and weighted congestion games, anonymous games, valid-utility games, and two-sided market games. All of these games are well-studied for their existence of pure Nash equilibria, complexity of mixed and pure NE, or/and their price of anarchy for different social functions [13,19,18,16,6]. To solve these problems, we illustrate general techniques that could be used as tools to answer similar questions for other classes of games.
Fabrikant and Papadimitriou showed that in a sink problem is PSPACE-hard for graphical games and a BGP next-hop routing game [11]. They posed this problem as an open question for weighted congestion games, and valid-utility games. We show that this problem is PSPACE-complete for weighted/player-specific congestion games, valid-utility games, two-sided market games, and anonymous games. The proofs for all the above games except anonymous games are similar and based on a reduction from halting problem of a space bounded Turing machine. The proof for anonymous games has unique features and is different from the rest. The hardness of the in a sink problem in anonymous games is despite the fact that approximate pure Nash equilibria can be computed in these games in polynomial time [?].
For Has a non-singleton sink problem, we prove that it is PSPACE-complete for weighted/playerspecific congestion games, valid-utility games, two-sided market games, and anonymous games. The reductions for Has a non-singleton sink problem extend the proofs for the in a sink problem.
Has a singleton sink problem has been well-studied for all games in this paper except for valid-utility games and two-sided market games. We show that has a singleton sink problem is NP-hard for these games as well. Our results for two-sided markets characterize the complexity of existence of a stable matching in many-to-one two-sided matching markets; an extensively studied problem in the economics literature [13,20,17]. Existing results for many-to-one two-sided markets give sufficient conditions for existence of stable matchings (or pure Nash equilibria) in different variants of the problem [13,20,17], but they have not explored the complexity of verifying the existence of stable matchings (or pure Nash equilibria) in these games. Related Work. Prior to this paper, the Has a non-singleton sink problem has not been studied for any of the above games. In a sink problem has been studied only for graphical games [11]. Has singleton Sink problem, however, has been studied extensively for all the above games except validutility games and two-sided market games. In fact, it has been shown that has a singleton sink problem is NP-hard for weighted congestion games and local-effect games [9], player-specific congestion games [2], graphical games [11], and action-graph games [16]. For anonymous games it has been shown that hat an approximate NE are computable in polynomial time [7] and that has a singleton sink is TC 0 -complete [3].
There has been a recent significant progress in understanding the complexity of equilibria in games. The complexity of mixed Nash equilibria is now well-understood by the recent results on PPAD-hardness of computing mixed NE [8,4], and even for computing approximate mixed NE [5]. The complexity of pure Nash equilibria in various games (especially congestion games) have also been well-studied by recent results on PLS-completeness of computing a pure Nash equilibrium [10,1], and even for computing an approximate pure NE [21].

General Definitions
Strategic games. A strategic game (or a normal-form game) Λ =< N, (Σ i ), (u i ) > has a finite set N = {1, . . . , n} of players. Player i ∈ N has a set Σ i of strategies (or strategies). The whole strategy set is Σ = Σ 1 ×· · ·×Σ n and a strategy profile S ∈ Σ is also called a profile or state. The utility function of player i is u i : Σ → R, which maps the joint strategy S ∈ Σ to a real number. Let S = (s 1 , . . . , s n ) denote the profile of strategies taken by the players, and let s −i = (s 1 , . . . , s i−1 , s i+1 , . . . , s n ) denote the profile of strategies taken by all players other than player i. Note that S = (s i , s −i ). An improvement move s i for a player i in a profile S is a move for which u i (s −i , s i ) ≥ u i (S). A best response move S i for a player i in a profile S is an improvement move that has the maximum utility. Note that in cost minimizing games, each player i wants to minimize the cost c i (S) = −u i (S) in strategy profile S. This type of games include congestion games with delay functions on edges which will be defined later. Nash equilibria (NE): A strategy profile S ∈ Σ is a pure Nash equilibrium if no player i ∈ N can benefit from unilaterally deviating from his strategy to another strategy, i.e., ∀i ∈ N ∀s i ∈ Σ i : We can also define α-Nash equilibria as follows.
State graph. Given any game Λ, the state graph G(Λ) is an arc-labeled directed graph as follows. Each vertex in the graph represents a joint strategy S. There is an arc from state S to state S with label i iff there exists player i and strategy s i ∈ Σ i such that S = (s −i , s i ), i.e., S is obtained from S by a move of a single player i that improves his utility from S to S . Nash dynamics. A Nash dynamics or best-response dynamics is equivalent to a walk in the state graph. Sink equilibria. Given any game Λ, a sink equilibrium is a subset of states T that form a strongly connected component of the state graph such that there is no outgoing edge from states in T to any state outside T . As a result, any pure Nash equilibrium of a game is a single-state sink equilibrium, and a game may have several sink equilibria.

Definition of games
is the strategy space of player i, and d e : N → Z is a delay function associated with resource e. For a strategy profile S = (s 1 , . . . , s n ), we define the congestion n e (S) on resource e by n e (S) = |{i|e ∈ s i }|, that is n e (S) is the number of players that selected an strategy containing resource e in S. The cost (or delay) In weighted congestion games, player i has weighted demand w i . In this game, the congestion (load) on resource e in a state S, denoted by by l e (S) is as follows l e (S) = i|e∈s i w i . The cost or delay of players is defined the same way as the congestion games. A player-specific congestion game is defined by a tuple < N, E, (Σ i ) i∈N , (d e,i ) e∈E,i∈N > where E and Σ i ⊆ 2 E are the same as congestion games, and d e,i : N → Z is a delay function associated with resource e and player i. The congestion n e (S) on resource e is defined the same as congestion games. The cost (delay) c i (S) of player i in a strategy profile S is c i (S) = −u i (S) = e∈s i d e,i (n e (S)).
Many-to-one Two-sided Markets. We model the many-to-one two-sided market (X , Y) between two sides of active agents X and passive agents Y as a game G(X , Y) among active agents x ∈ X . The strategy set of each active agent x ∈ X is a lower-ideal 1 family of subsets of passive agents F x where F x ⊆ 2 Y , i. e., an active agent x ∈ X can play a subset s x ∈ F x of passive agents. Each agent x ∈ X also has a preference (a.k.a social choice) over its strategies. This preference is capture by a utility function u x : 2 Y → R which assigns a utility, u x (T ), to each subset T ⊆ Y. Each agent y ∈ Y has a strict preference list over the set of agents x ∈ X that can play this set, i. e., x is preferred to x by y iff u y (x) > u y (x ). We assume that u y (x) = u y (x ) for any two agents x and x . Given a vector of strategies S = (s 1 , . . . , s n ) for active agents, agent y is matched to the best agent x ∈ X in the preference list of agent y such that y ∈ s x . In this case, we say that x is the winner of agent y, or equivalently, agent x wins agent y. The goal of each active agent x is to maximize the utility of the set of passive agents that she wins. Given a strategy profile S, let T x (S) ⊆ s x be the set of passive agents that agent x wins. The utility of player x in strategy profile S is equal to u x (T x (S)), the goal of x is to maximize this utility.
It is not see that pure Nash equilibria of the above game correspond to stable matchings for many-to-one two-sided markets as defined by ... Valid-utility Games. Here we briefly define the class of valid-utility games; see [22] for more details. In valid-utility games, for each player i, there exists a ground set of markets V i . We denote by V the union of ground sets of all players, i.e., V = ∪ i∈U V i . The feasible strategy set F i of player i is a subset of the power set, Then G is a valid-utility game if it satisfies the following properties: (1) The social function γ is submodular and non-decreasing, (2) The utility of a player is at least the difference in the social function when the player participates versus when it does not participate. and (3) For any strategy profile, the sum of the utilities of players should be less than or equal to the social function for that strategy profile.
This framework encompasses a wide range of games including the facility location games, traffic routing games, auctions [22], market sharing games [14], and distributed caching games [12]. In [22] it was shown that the price of anarchy (for mixed Nash equilibria) in valid-utility games is at most 2. Anonymous games. Anonymous game [6] are games in which players have the same strategy sets, but different utilities for the same strategies; however, these utilities do not depend on the identity of the other players, but only on the number of other players taking each action. An interesting subclass of these games is anonymous games with a constant-size strategy set in which the size of the strategy set of players is a fixed constant. Theorem 1. Has a singleton Sink is NP-hard for (i) uniform utility-based two-sided market games, (ii) many-to-one two-sided market games, and (iii) valid-utility games.
Proof. To prove NP-completeness, we give a reduction from the 3Sat problem. Given an instance of the 3Sat problem, we construct an instance of the utility-based two-sided market game as follows: for each variable x i , we put a player X i with a one and a zero strategy. For each clause c j , we put two players C j and K j each with a one and a zero strategy. We construct the game such that C j and K j have a cycle of best responses if and only if the clause is not satisfied. In other words, if the X-players choose a strategy profile that satisfies all clauses, all clause players eventually reach a stable solution.
The zero strategy of C j is {a j , b j } and the one strategy is {c j }. The zero strategy of K j is {a j } and the one strategy is {b j } ∪ {r j,i |for all variablesx i in clause c j }. The a-markets have utility 305 and prefer the K-players. The b-markets have utility 8 and prefer the C-players. The c-markets have utility 310. The r-markets have utility 100 and prefer the X-players. Note that there is a best response cycle of C j and K j if and only if none of the three r i,j -markets is allocated by an X-player.
The zero strategy of a player X i is The p-markets have utility 100. Note that both strategies have the same utility for a X-player independent of the strategy profile of other players. Furthermore, X i gets the utility from r i,j , if and only if it satisfies clause c j , The above theorem implies that given an instance of the many-to-one stable matching problem, the problem of verifying if this game has a stable matching or not is NP-hard. Known results in the economic literature for many-to-one two-sided markets discuss necessary and sufficient conditions for existence of stable matchings (or pure Nash equilibria) for different variants of two-sided markets [13,20,17], however, before our results, the known results have not addressed the complexity of verifying the existence of stable matchings (or pure Nash equilibria) given an instance of these markets.

Sink Equilibria and Weighted Congestion Games
In this section, we study the complexity of the In a Sink and Has a Sink problem for weighted congestion games. The interesting aspect of this proof is that we can use similar reductions for a variety of games with succinct representation. Applying this proof on many examples shows the strength of the proof technique. To complete the proof, we construct a congestion game G M that simulates Turing machine M . A strategy profile s which we define later is in a sink equilibrium if and only if M runs forever. The game consists of three types of configuration players, a transition player, a set of control players, and a clock player. The first type of configuration players is a state player with |Q| strategies. The second type of configuration players is a position player for the position of the head with t strategies; and the third type of configuration players is a set of cell players cell i for each tape cell 0 ≤ i ≤ t with the |Γ| strategies for the content of the tape cell i. There is a simple bijective mapping between the strategy profiles of the configuration players and the configurations of M .
The game is constructed in such a way that every sequence of improvement steps can be divided in rounds. At the end of a round i, let c i be the configuration obtained from the strategy profile of the configuration players. For every sequence of improvement steps, c 1 c 2 c 3 . . . denotes the run of M starting from c 1 .
We now describe our construction in more details. The strategies of the configuration players are described in Figure 1. Every strategy of a configuration player has two unique resources, an α resource and a β resource. The α resources have delay 0 if allocated by one player and delay 1 otherwise. The β resources have delay 0 if allocated by one player and delay M otherwise.  Figure 2: Strategies of the control players, for each q ∈ Q, 0 ≤ i ≤ n, i ∈ {i − 1, 1, i + 1}, and σ ∈ Γ Each control player has two strategies, Zero and One, which are constructed in the same manner like strategies of configuration players (see Figure 2). The transition player has the following strategies Wait, Done, Halt, and several strategies Read q,i,σ , Write q ,i ,i,σ , and Verify q ,i ,i,σ (for each i, i ∈ {1, . . . , t }, q, q ∈ Q, and σ, σ ∈ Σ). The details of theses strategies and the resources they contain are listed in Figure 3. The clock player has two strategies, Trigger and Wait. Trigger contains the two resources, TriggerMain and TriggerClock. The strategy Wait contains one resource with constant delay of 110.
Let us remark that each α-or β-resource is allocated by at most two players; the transition player and one of the configuration or control players. The general idea is that the improvement steps for the transition player is determined by the strategy profile of the configuration and control players. That is, the transition player never deviates to a strategy that contains a β-resource which is allocated by another player. On the other hand, the transition player determines the improvement steps for configuration and control players if he allocates α-resources. Note that each α-resource is associated with exactly one strategy of exactly one configuration or control player. Now, we are ready to describe the aforementioned sequence of improvement steps that corresponds to one round in more details. Consider any strategy profile in which the clock players are on Trigger, the transition player is on Wait and all control players except control D are on One. Let q be the strategy of the state player, i the strategy of the position player and σ 0 , . . . , σ t the strategies played Strategy Resources Delays Wait We now consider the problem Has a non-singleton Sink for weighted congestion games.

Theorem 3. Has a non-singleton Sink is PSPACE-hard for weighted congestion games.
This results follows from the proof of Theorem 2 and the following Lemma. The lemma implies that there is at most one unique sink equilibrium in the constructed game. (1) The transition player deviates from Wait to Read q,i,σ i . (2) Player control W,q ,i ,i,σ deviates to Zero. (3) The transition player deviates to Write q ,i ,i,σ . (4) The configuration players deviate to the new configuration and the player control V,q ,i ,i,σ deviates to Zero. (5) The transition player deviates to Verify q ,i ,i,σ .
The player control D deviates to One.
The transition player deviates to Done. (8) The clock player deviates to Wait and the controll players except control D deviate to Zero (9) The transition player deviates to Wait. (10) The clock player deviates to Trigger and the player control D deviates to Zero  Proof. If no player has delay M or greater, the game converges as described in Figure 4 and eventually reaches a strategy profile in which the clock player is on Trigger, the main player on Wait and all controll players on their Zero strategy. Note that no strategy profile with a player having delay M or greater is reachable. If players have delay of M or greater, there is a sequence of improvement steps such that no player has delay of M or more, e.g. each control or configuration player with delay of M changes to another strategy.
Thus, every sink equilibrium also contains the strategy profile that corresponds to the initial configuration of M . Therefore, there is a unique sink equilibrium if and only if M rejects x.

Sink Equilibria and Player-Specific Congestion Games
Theorem 5. In a Sink is PSPACE-hard for player-specific congestion games.
One can easily replace the clock player in the construction which is the only player with nonuniform weight by a player with weight 1 and modify the (player-specific) delay functions as follows. For the transition player the resource TriggerMain has delay 0 if one player allocates it and delay 100 otherwise. For the clock player the resource TriggerMain has always delay 100. The delay functions of the resource TriggerClock is identical for both players. It has delay 0 if one player allocates the resource and delay 20 for two or more players. For each strategy profile the delay for each player is identical to the delay in the previous example. Theorem 6. Has a non-singleton Sink is PSPACE-hard for player-specific congestion games.
Proof. This result follows by the same argument as for Theorem 3.

Sink Equilibria and Anonymous Games
Next, we consider anonymous games with constant-size strategy set and show that in a sink for this game is also PSPACE-complete.
Theorem 7. In a Sink is PSPACE-hard for anonymous games with constant-size strategy sets.
We give a reduction from the halting problem of a space bounded Turing machine M as defined in the proof of Theorem 2. Additionally, we assume that states of M are denoted by q 0 , . . . , q m where q m is the halting state. We construct an anonymous game with a constant number of strategies. Each player has a set of (allowed) strategies. Every strategy that is not allowed always has utility 0. The only other utility values in the game are 1 and 2. Given a strategy profile s = (s 1 , . . . , s k ), let |s i | denotes the number of players that play strategy s i .
The game consists of the three types of configuration players and five types of auxiliary players and two control players. The strategy choices of the configuration players can be mapped to configurations of the TM M . Every sequence of improvement steps can be partitioned into rounds. Each round simulates one step of M . At the end of a round i, let c i be the configuration obtained from the strategy profile of the configuration players. For every sequence of improvement steps, c 1 c 2 c 3 . . . equals the run of M starting from c 1 .
We first describe the configuration players before we describe the remaining players and the process that simulates one step of M . The first type of configuration players are |Q| identical state players that choose between the two actions state 1  There are five types of auxiliary players and two control players. All players and their allowed strategies are listed in Figure 5. The utility functions for each player are described in Appendix B.
The players tape 1 , . . . , tape t have identical payoff functions. They are used to evaluate symbol at the current position. The player symbol saves this symbol. The players new-sym, new-pos 1 , . . . , new-pos t , new-state 1 , . . . , new-state m calculate the changes to the configuration. The control players ensure that strategy changes happen in a certain order that corresponds to one step.
Lemma 8. Let c be a configuration of M and c the successor configuration. Every sequence of improvement steps from a strategy profile in which the configuration players play corresponding to c and the first control player is on init, reaches a strategy profile in which the configuration players play corresponding to c and the first control player is on init.
Proof. We now describe this sequence of improvement steps which we call a round. It is listed in Figure 1 in detail. One can easily check for each of the strategy profiles that the next one is essentially unique.
In a round, the first control player successively changes through his strategies (c.f. steps (2),(4),...). The second control player follows his choices in his corresponding strategies. By construction of the payoff function, this ensures that the control players only change their strategies in a certain order. Each of these steps of the first control player is interrupted by improvement steps of subsets of configuration or auxiliary players. The utility functions (cf. Figure 7) are designed in such a way that these improvement steps are possible if and only if the control player plays the corresponding strategy. Additionally, the control player may only continue with his next step after these other player have changed their strategies (cf. Figure 8) .
We now describe the improvement steps of the configuration and auxiliary players only. Consider any strategy profile of the configuration players and assume the first control player is on init (strategy profile (1) in Figure 1 in Appendix B. The t tape players change to a strategy profile in that the number of players on tape 0 , tape 1 , and tape b equals the number of players on cell 0 , cell 1 , and cell b (2). The player cell i with i = |position i | changes to his strategy to change (4).The symbol player changes to symbol 0 , symbol 1 , or symbol b depending on which strategy was left by the player cell i (6). This can be coded into the utility function by evaluating the difference of number of players in the cell and tape strategies. The player new-symbol changes to the strategy new-symbol σ where σ corresponds to the new symbol (8). This can be coded as a function as from number of players on symbol 0 , symbol 1 , symbol b , and state 1 . The player cell i changes to the strategy cell σ (10). Exactly i players choose new-pos 1 where i is the new position of M (12). The players position change their strategies such that |position 1 | = |new-pos 1 | = i (14). Exactly q players new-state choose new-state 1 where q q is the new state of M (16). The players state change their strategies such that |state 1 | = |new-state 1 | = q (18). The configuration players' strategy profile now corresponds to the new configuration after one step of M .
Theorem 9. Has a non-singleton Sink is PSPACE-hard for anonymous games.
Proof. By construction of M and the proof of Theorem 7, it suffices to show that every infinite sequence of improvement steps contains a strategy profile with player control1 on init, i.e. a profile listed in the first row of Table 1.
The strategy changes of control1 have to occur in the same order as listed in Table 1. Therefore, every sequence with infinite strategy changes of control1 contains a profile with control1 on init. We, therefore, show that there is no infinite sequence that contains no strategy change of control1. Thus, fix any strategy choice for player control1. Observe that the utility functions of the remaining players (cf. Figure 7) do not allow an infinite sequence.

Sink Equilibria in other Games
Theorem 10. In a Sink is PSPACE-hard for (i) uniform utility-based two-sided market games, (ii) many-to-one two-sided market games, and (iii) valid-utility games.
Theorem 11. Has a non-singleton Sink is PSPACE-hard for (i) uniform utility-based two-sided market games, (ii) many-to-one two-sided market games, and (iii) valid-utility games.
The proof is a rework of the proof for Theorem 2 and is shifted to Appendix A. The Nash dynamics of the uniform utility-based two-sided market game that we describe there is isomorphic to the Nash dynamics of the congestion game in the proof for Theorem 2.