Francis Bloch
email: francis.bloch@univ-paris1.fr.

Anne Van Den Nouweland
email: annev@uoregon.edu

Myopic and Farsighted Stable Sets in 2-player Strategic-Form Games

Keywords: JEL Classification Numbers: C71,C72,C79 Strategic-Form Game, Myopic Stable Set, Farsighted Stable Set, Core

Introduction

There are different ways to analyze strategic situations. One possibility is of course to study the optimal behavior of players and characterize strategy profiles for which both players choose their optimal strategy -the Nash equilibria of the game in strategic-form. Another possibility is to consider strategy profiles as social states, describe which moves are possible across states, and characterize stable outcomes of the process. In the latter approach, strategic situations are analyzed as a special instance of games in effectivity function form (Moulin and Peleg [START_REF] Moulin | Cores of effectivity functions and implementation theory[END_REF]), which have been successfully used to study voting, and coalition and network formation. The solution concept used to characterize stable situations, initially proposed by Von Neumann and Morgenstern [START_REF] Morgenstern | Theory of games and economic behavior[END_REF], is a set-based solution concept, named stable set, with the property that there is no admissible move between two elements in the set and there is an admissible move from any situation outside the set to a situation inside the set. 1 Attention was first restricted to one-step moves, resulting in the definition of myopic cores and stable sets. However, as pointed out by Harsanyi [START_REF] John | An equilibrium-point interpretation of stable sets and a proposed alternative definition[END_REF], the hypothesis of one-step moves is very restrictive. Harsanyi [START_REF] John | An equilibrium-point interpretation of stable sets and a proposed alternative definition[END_REF] proposed instead a multi-stage bargaining game which was later re-formalized by Chwe [START_REF] Michael | Farsighted coalitional stability[END_REF] to study the stable outcomes of dynamic processes involving farsighted players. 2 In this paper, we consider both myopic and farsighted behavior to characterize stable outcomes in generic 2-player strategic-form games where players receive different payoffs for different strategy profiles.

In the analysis of stable sets in strategic-form games, each player can engineer a move to a different social state by unilaterally changing their strategy. A social state dominates another social state if, in addition, players have a strict incentive to move from one state to another. The analysis of dominance relations in strategic-form games was pioneered by Greenberg in his book on the theory of social situations [START_REF] Greenberg | The theory of social situations: an alternative gametheoretic approach[END_REF] and Brams in his book on the theory of moves [START_REF] Brams | Theory of Moves[END_REF]. The core is the set of social states that no player wants to move away from; a stable set is a set of social states such that (i) no player can engineer a move from a state inside the set to another state inside the set and (ii) for any social state outside the set there exists a player who can engineer a move from that state to a social state inside the set. We distinguish between 1-step paths, which result in myopic cores and stable sets, and general paths, which result in farsighted cores and stable sets.

Our first results characterize myopic cores and stable sets. We first recall that the myopic core is equal to the set of pure-strategy Nash equilibria. 3More interestingly, we establish a connection between myopic stable sets and stable matchings of an auxiliary 2-sided matching problem, where the two sides correspond to the strategies of the two players, and "preferences" of a strategy of player i are computed according to player j's preference ranking over their strategies given the strategy of player i. Using this connection, we show that myopic stable sets always exist and contain as many elements as the minimal number of strategies of the two players. 4 In addition, for the player with the larger strategy set, the same strategies are represented in all stable sets. Also, there exists a myopic stable set that is "1-optimal" and one that is "2-optimal." We also use the connection to derive a sufficient condition for uniqueness of the myopic stable set.

We next turn to farsighted cores and stable sets. When paths of any length are allowed, it becomes easier for players to engineer moves. As a consequence, the farsighted core is a subset of the myopic core. We show that the farsighted core is either empty or a singleton. Examples suggest that the farsighted core is often empty, emphasizing the difference between myopic and farsighted stability. Our main result characterizes social states that are dominated by a fixed, Pareto undominated, strategy profile. We show that the strategy sets of the two players satisfy a "block partition property": they can be partitioned such that there exist farsighted paths to the strategy profile from each strategy profile in one of the blocks of strategies, while no farsighted paths exists from strategy profiles outside this block. With this result in hand, we characterize strategy profiles that form a singleton farsighted stable set as Pareto undominated strategy profiles for which the block of farsightedly dominated profiles encompasses the entire set of strategy profiles. This characterization is useful for two reasons. First, it suggests an efficient algorithm to check whether a strategy profile forms a singleton farsighted stable set. Second, it shows that any Pareto undominated purestrategy Nash equilibrium forms a singleton farsighted stable set.

We provide an exhaustive characterization of farsighted stable sets for all 2 × 2 strategic-form games. This characterization highlights the fact that the Prisoners' Dilemma is the only 2 × 2 game that does not admit a singleton farsighted stable set and also the only 2 × 2 game that admits a 2-element farsighted stable set. 5 All other 2 × 2 games admit a singleton farsighted stable set, sometimes multiple farsighted stable sets. 6 The existence of farsighted stable sets in all 2 × 2 games suggests that farsighted stable sets may exist for all 2-player games. We prove the existence of farsighted stable sets for 2 × n games. Existence for m × n games remains a conjecture.

We also analyze situations where both players can simultaneously change their strategies. On the one hand, allowing pairwise moves increases the number of possible moves, reducing the core. For example, with pairwise moves, pure-strategy Nash equilibria that are Pareto dominated are excluded from the myopic core. On the other hand, allowing pairwise moves makes it easier for a strategy profile to dominate all other profiles. Hence, singleton farsighted stable sets are easier to sustain, and we prove existence of singleton farsighted stable sets for all two-player strategic-form games. 7The remainder of the paper is organized as follows. Related literature is reviewed in Subsection 1.1. In Section 2, we introduce the notations and the definitions for strategic-form games, myopic and farsighted stability, and cores and stable sets. Section 3 is devoted to the analysis of myopic cores and stable sets. Section 4 contains the analysis of farsighted cores and stable sets. We discuss farsighted stability in 2 × 2 games in Section 5. Section 6 presents the analysis of stability when pairwise moves are allowed. Section 7 concludes. All proofs appear in Appendix A.

Related literature

The analysis of stability for strategic-form games can be traced back to Greenberg's "Theory of Social Situations" [START_REF] Greenberg | The theory of social situations: an alternative gametheoretic approach[END_REF] and Brams's "Theory of Moves" [START_REF] Brams | Theory of Moves[END_REF]. Greenberg [START_REF] Greenberg | The theory of social situations: an alternative gametheoretic approach[END_REF] characterizes the myopic stable set in the 2-player Prisoners' Dilemma and proves existence of the myopic stable set for any 2-player game with finite strategies, and any game with binary strategy space and a finite number of players (Theorems 7.4.5 and 7.4.6 pp. 100-101 in Greenberg [START_REF] Greenberg | The theory of social situations: an alternative gametheoretic approach[END_REF]). Okada [START_REF] Okada | The possibility of cooperation in an n-person prisoners' dilemma with institutional arrangements[END_REF] defines a family of n-player games that extends the 2-player Prisoners' Dilemma. Allowing coalitional deviations, he observes that a my-opic stable set does not exist in the 2-player Prisoners' Dilemma. Nakanishi [START_REF] Nakanishi | On the existence and efficiency of the von neumann-morgenstern stable set in a n-player prisoners' dilemma[END_REF] extends the study of myopic stable sets to mixed extensions of n-player Prisoners' Dilemma games. Iñarra, Larrea and Saracho characterize another set-based solution concept -the supercore -of normal-form games in [START_REF] Iñarra | The supercore for normal-form games[END_REF], and they study the myopic stable set of the mixed extensions of 2 × 2 games in [START_REF] Iñarra | The von neumann-morgenstern stable sets for the mixed extension of 2 × 2 games[END_REF].

The farsighted stable sets of strategic-form games were first studied by Muto in a working paper, [START_REF] Muto | Alternating-move preplays and vn-m stable sets in two person strategic form games[END_REF], in which it is shown that in the 2-player Prisoners' Dilemma the farsighted stable set is equal to the myopic stable set. Suzuki and Muto [START_REF] Suzuki | Farsighted stability in an n-person prisoner's dilemma[END_REF], allowing for coalitional deviations, characterize farsighted stable sets in the family of games studied in Okada [START_REF] Okada | The possibility of cooperation in an n-person prisoners' dilemma with institutional arrangements[END_REF]. Nakanishi [START_REF] Nakanishi | Noncooperative farsighted stable set in an n-player prisoners' dilemma[END_REF] conducts the analysis of farsighted stable sets in the same family of games, but only allowing for individual moves. Nakanishi [START_REF] Nakanishi | Reexamination of the international export quota game through the theory of social situations[END_REF] and Kawasaki et al. [START_REF] Kawasaki | Farsightedly stable tariffs[END_REF] analyze farsighted stable sets in two-country tariff games. In two recent papers, [START_REF] Hirai | The stable set of the social conflict game with commitments: existence, uniqueness, and efficiency[END_REF] and [START_REF] Hirai | Single-payoff farsighted stable sets in strategic games with dominant punishment strategies[END_REF], Hirai characterizes farsighted stable sets in two general classes of games encompassing Prisoners' Dilemma games (games of social conflict in [START_REF] Hirai | The stable set of the social conflict game with commitments: existence, uniqueness, and efficiency[END_REF] and games with dominant punishment strategies in [START_REF] Hirai | Single-payoff farsighted stable sets in strategic games with dominant punishment strategies[END_REF]).

Konishi and Ray [START_REF] Konishi | Coalition formation as a dynamic process[END_REF] introduce a dynamic coalition formation process and study its long-term behavior, offering an alternative solution concept to farsighted stable sets. In one subsection of the paper (Section 5.2), they apply their solution concept to games in strategic form, highlighting for example the variety of possible equilibria in the Prisoner's Dilemma.

In contrast to most of the existing literature characterizing myopic and farsighted stable sets in strategic-form games, we focus attention on 2-player games. However, we do not make any specific assumptions about the payoffs in the game, and hence our results apply generally. In that respect, Kawasaki [START_REF] Kawasaki | Maximin, minimax, and von neumann-morgenstern farsighted stable sets[END_REF] is the closest paper to our work. It studies existence of farsighted stable sets in a general class of 2-player games with pairwise deviations and proves that any individually rational and Pareto efficient strategy profile forms a singleton farsighted stable set under a mild restriction on payoffs. Note that our two main contributions -the full characterization of myopic stable sets using a connection with an auxiliary matching problem, and the characterization of indirectly dominated strategy profiles using block partitions -are new and depart from the existing literature on stable sets of strategic-form games.

Definitions and notations

Strategic-form games

We consider strategic-form games G = N ; S 1 , S 2 ; u 1 , u 2 with player set N = {1, 2}, a finite strategy set S i for each player i, and payoff functions u i :

S 1 × S 2 → . If |S 1 | = m and |S 2 | = n,
the game G is said to be an m × n game, and, without loss of generality, we assume throughout this paper that m ≤ n. The set of all possible strategy profiles is S := S 1 × S 2 with typical element s = (s 1 , s 2 ). We limit our analysis to generic games, i.e., games in which no player is indifferent between any two strategy profiles: For any two different strategy profiles s, t ∈ S and any player i ∈ N , it holds that u i (s) = u i (t) (or, said differently, if i ∈ N and s, t ∈ S are such that u i (s) = u i (t), then s = t).

A strategy profile s ∈ S is a Nash equilibrium iff each player is giving their best response, or s i = BR i (s j ) := arg max t i ∈S i u i (t i , s j ) for each i ∈ N and j ∈ N \ {i}. 8

Stable sets and cores

We consider stable sets and cores in strategic-form games. Both of these concepts are based on a dominance relation on the set of states S of all possible strategy profiles, i.e., a binary relation on S × S. For any two s, t ∈ S, if s t, we say that s dominates t or t is dominated by s.

The core is the set of all those strategy profiles that are not dominated by any other profile.

Definition 2.1 Core The core with respect to dominance relation is the set of all s ∈ S such that there is no t ∈ S with t s.

Following von Neumann and Morgenstern [START_REF] Morgenstern | Theory of games and economic behavior[END_REF], we define a stable set with respect to a dominance relation as those sets of states that satisfy both internal stability (no state in the set is dominated by another state in the set) and external stability (every state that is not in the set is dominated by some state in the set). The core always exists, but it may be the empty set. On the other hand, a stable set cannot be empty (because the empty set violates external stability), but existence of a stable set is not guaranteed.

Myopic and farsighted stability

We apply the concepts of myopic and farsighted stability to the set of strategy profiles in strategic-form games. For both of these stability concepts, the set of states is the set S of all possible strategy profiles and possible transitions (moves) between the states reflect that each player controls their own strategy. The preferences of a player i over the states are represented by the player's payoff function u i .

We first define the myopic dominance relation and the farsighted dominance relation. In a strategic-form game, each player can engineer a move from a strategy profile t to a strategy profile s by unilaterally switching their strategy. Hence the transition from state t to state s is defined by a change in the strategy from one of the two players. Formally, two strategy profiles s, t ∈ S are i-adjacent for player i ∈ N if s i = t i and s j = t j for player j ∈ N \ {i}. Two strategy profiles s, t ∈ S are adjacent if they are i-adjacent for some player i ∈ N . Definition 2.3 Myopic dominance Strategy profile s ∈ S myopically dominates strategy profile t ∈ S, denoted s t, if there exists a player i ∈ N such that the two profiles are i-adjacent, and u i (s) > u i (t). Thus, player i can unilaterally change the strategy profile from t to s and improves their payoff by doing so. Definition 2.4 Farsighted dominance A farsighted dominance path from s 1 to s k+1 is an alternating sequence of k + 1 strategy profiles and k moves s 1 → i 1 s 2 → i 2 s 3 . . . s k → i k s k+1 such that (1) s 1 , . . . , s k+1 ∈ S and i 1 , . . . , i k ∈ N , (2) strategy profiles s l and s l+1 are i l -adjacent for each l ∈ {1, . . . , k}, and (3) u i l (s l ) < u i l (s k+1 ) for each l ∈ {1, . . . , k}. The length of the path is equal to the number of its moves k.

A strategy profile s ∈ S farsightedly dominates a strategy profile t ∈ S, denoted s t, if there exists a farsighted dominance path from t to s.

Note that myopic dominance is farsighted dominance via paths of length 1. The two dominance relations each give rise to a core and stable sets.

Myopic cores and stable sets

In this section, we study myopic cores and stable sets of strategic-form games. As the following simple proposition shows, the definition of the core is closely related to the definition of Nash equilibrium. Proposition 3.1 The myopic core of a strategic-form game is equal to the set of pure-strategy Nash equilibrium profiles.

In fact, in addition to not being myopically dominated by any other strategy profile, a pure-strategy Nash equilibrium myopically dominates all adjacent strategy profiles.

Myopic stable sets of a strategic-form game are less obvious to characterize. We demonstrate that known results for stable matchings in 2sided matching problems can be used to find myopic stable sets in 2-player strategic-form games. We recall the definitions of matching problems, matchings, and stable matchings. In a stable matching, every agent is either single or matched to an agent in the other group whom they prefer to remaining single, and there is no "blocking pair" of agents who prefer to be matched to each other instead of to their current partners.

The connection between myopic stable sets and stable matchings arises from the following auxiliary matching problem. Let S 1 and S 2 , the strategy sets of the two players, play the role of the two sides of the matching market, M and W . The "preferences" of a strategy s i ∈ S i over all strategies s j ∈ S j are defined as follows: s j is preferred to t j by s i , s j s i t j if and only if u j (s i , s j ) > u j (s i , t j ). In particular, for any strategy s i , the most preferred strategy s j is player j's best response to s i , the next-best strategy t j is the strategy that gives player j the second highest payoff when player i plays s i , etc. In addition, assume that remaining single is worse than being matched to any strategy of the other player: s j s i s i for all s j ∈ S j . Of course, these "preferences" of strategies cannot be interpreted as preferences of the players, and are only introduced as an auxiliary tool to characterize myopic stable sets. The following example illustrates the construction of the auxiliary matching problem. In the auxiliary matching problem, S 1 = {R1, R2, R3}, S 2 = {C1, C2, C3, C4}, and preferences are given by

R1 R2 R3 C1 C2 C3 C2 C1 C1 C3 C4 C4 C4 C3 C2 R1 R2 R3 C1 C2 C3 C4 R2 R3 R1 R2 R1 R1 R3 R1 R3 R2 R2 R3 C1 C2 C3 C4
A matching µ associates with each strategy s i ∈ S i either s i or a strategy s j ∈ S j . We show that stable matchings of the auxiliary matching problem can be used to construct myopic stable sets of the strategic-form game. Theorem 3.6 Let G be a m × n game with m ≤ n. Then Σ ⊂ S 1 × S 2 is a myopic stable set if and only if there exists a stable matching µ such that

Σ = {(s 1 , µ(s 1 )) | s 1 ∈ S 1 }.
Theorem 3.6 establishes a correspondence between the myopic stable sets of a strategic-form game and the stable matchings of an auxiliary matching problem. Stable matchings in 2-sided markets have been extensively studied (see Roth and Sotomayor [START_REF] Roth | Two-sided Matching: a Study in Game-theoretic Modeling and Analysis[END_REF] for an excellent monograph) and the correspondence that we have established allows us to use known results for stable matchings to establish properties of myopic stable sets. Proposition 3.7 Let G be a m × n game with m ≤ n. Then the following hold for myopic stable sets of G.

1. There exists at least one myopic stable set in G.

Every myopic stable set Σ contains exactly m strategy profiles, and two

different elements of Σ have different strategies for both players.

3. The set of pure-strategy Nash equilibria is a subset of all myopic stable sets.

4. If a strategy of player 2 does not appear in any strategy profile in some myopic stable set, then it does not appear in any strategy profile in any myopic stable set.

5. There exists a myopic stable set Σ 2 that is "2-optimal" in the sense that for all myopic stable sets Σ it holds that for each strategy s 1 of player

1 we have u 2 (s 1 , s 2 ) ≥ u 2 (s 1 , s2 ) when (s 1 , s 2 ) ∈ Σ 2 and (s 1 , s2 ) ∈ Σ.
There also exists a myopic stable set Σ 1 that is "1-optimal" in the sense that for all myopic stable sets Σ it holds that for each strategy s 2 of player 2 that appears in all myopic stable sets (see item 4), we have

u 1 (s 1 , s 2 ) ≥ u 1 (s 1 , s 2 ) when (s 1 , s 2 ) ∈ Σ 1 and (s 1 , s 2 ) ∈ Σ.
Example 3.5 continued. Returning to Example 3.5, we observe that the auxiliary matching problem admits three stable matchings µ a , µ b ,and µ c where

µ a (R1) = C1, µ a (R2) = C2, µ a (R3) = C3, µ a (C4) = C4, µ b (R1) = C3, µ b (R2) = C1, µ b (R3) = C2, µ b (C4) = C4, µ c (R1) = C2, µ c (R2) = C1, µ c (R3) = C3, µ c (C4) = C4.
This implies that the strategic-form game G admits three myopic stable sets:

Σ a = {(R1, C1), (R2, C2), (R3, C3)}, Σ b = {(R1, C3), (R2, C1), (R3, C2)}, Σ c = {(R1, C2), (R2, C1), (R3, C3)}
Notice that each myopic stable set contains exactly three strategy profiles, that every strategy of player 1 appears in every myopic stable set and that all strategy profiles in a myopic stable set have distinct coordinates. The game G does not admit a pure-strategy Nash equilibrium, and hence the myopic core is empty and there is no strategy profile that is included in all myopic stable sets. Strategy C4 of player 2 does not appear in any myopic stable set. The myopic stable set Σ a is the "1-optimal" myopic stable set whereas Σ b is the "2-optimal" stable set.

The correspondence between the myopic stable sets of a strategic-form game and the stable matchings of an auxiliary matching problem in Theorem 3.6 can also be used to establish the existence of a unique myopic stable set under some circumstances. Proposition 3.8 Let G be a m × n game with m ≤ n. If the strategies in S 1 can be numbered s 1 1 , s 2 1 , . . . , s m 1 and the strategies in S 2 can be numbered

s 1 2 , s 2 2 , . . . , s n 2 in such a way that u 2 (s k 1 , s k 2 ) > u 2 (s k 1 , s l 2 )
for all k ∈ {1, 2 . . . , m} and all l > k, and also

u 1 (s k 1 , s k 2 ) > u 1 (s l 1 , s k 2 )
for all k ∈ {1, 2 . . . , m} and all l > k, then the game G has a unique myopic stable set, which is the singleton

Σ = {(s k 1 , s k 2 ) | k = 1, 2, . . . , m}.
Proposition 3.8 provides a sufficient condition for a m × n game G to have a unique myopic stable set. The proof of the proposition represents the auxiliary matching problem associated with G as a coalition formation game and exploits the results for coalition formation games in Banerjee et al. [START_REF] Banerjee | Core in a simple coalition formation game[END_REF]. The result in the proposition can also be obtained by using Eeckhout [START_REF] Eeckhout | On the uniqueness of stable marriage matchings[END_REF]'s sufficient condition for the uniqueness of a stable matching in the one-to-one matching model, but the scope would then need to be limited to m × m games.

Farsighted cores

Recall that the farsighted core contains all strategy profiles that are not farsightedly dominated. Whenever s myopically dominates t, s also farsightedly dominates t (with a farsighted dominance path of length 1) and thus the farsighted core is contained in the myopic core. Because all elements of the myopic core are pure-strategy Nash equilibria, we deduce that any element in the farsighted core must also be a pure-strategy Nash equilibrium. However, not all pure-strategy Nash equilibria belong to the farsighted core, as some may be dominated by farsighted dominance paths of length more than one. We establish that the core can have at most one element and can be non-empty only if the game has a Nash equilibrium that Pareto dominates all other Nash equilibria.

Proposition 4.1 Either the farsighted core is empty or it consists of a single strategy profile, which is a pure-strategy Nash equilibrium that Pareto dominates all other Nash equilibria.

The existence of a pure-strategy Nash equilibrium that Pareto dominates all other Nash equilibria is clearly a very strong condition. However, it is not a sufficient condition for non-emptiness of the farsighted core. Consider the game C1 C2 C3 R1 0, 5 2, 1 7,6 R2 1, 4 4, 7 6,8 R3 3, 3 8, 2 5,0 This game has a two pure-strategy Nash equilibria, (R1, C3) and (R3, C1), and (R1, C3) Pareto dominates (R3, C1). However, (R1, C3) → 2 (R1, C2) → 1 (R2, C2) is a farsighted dominance path that shows that (R2, C2) (R1, C3) and thus (R1, C3) is not in the farsighted core.

Farsighted stable sets

We next turn our attention to farsighted stable sets (FSS). The main result of this subsection establishes a structural property of the set of strategy profiles that are farsightedly dominated by a given, Pareto undominated strategy profile. We first state a useful simple Lemma. Lemma 4.2 Let s and t be strategy profiles such that s is Pareto dominated by t. Then s does not farsightedly dominate t. Property 4.3 Pareto undominated (PU) A strategy profile s ∈ S is Pareto undominated (PU) iff there is no strategy profile t ∈ S such that u 1 (t) > u 1 (s) and u 2 (t) > u 2 (s). 9Note that a Pareto undominated strategy profile always exists because the set of strategy profiles is finite. We will establish that for every Pareto undominated strategy profile s the set of all strategy profiles that are farsightedly dominated by s can be identified by considering a Cartesian product, as formalized in the block partition property. Property 4.4 Block partition property (BPP) Strategy profile s admits a block partition if there exist partitions of the sets of strategy profiles of the two players

S 1 = D 1 ∪ U 1 and S 2 = D 2 ∪ U 2 such that s 1 ∈ D 1 , s 2 ∈ D 2 ,
and all t ∈ D 1 × D 2 \ {s} are farsightedly dominated by s and no other strategy profiles are (i.e., when either t 1 ∈ U 1 or t 2 ∈ U 2 or both). 10Lemma 4.5 Let s be a strategy profile that admits a block partition. Then the block partition with respect to s is unique. Moreover, u 1 (t) > u 1 (s) for every t ∈ U 1 × D 2 , and u 2 (t) > u 2 (s) for every t ∈ D 1 × U 2 . Proposition 4.6 Let s be a Pareto undominated strategy profile. Then s admits a block partition.

The proof of Proposition 4.6 is established by identifying rows or columns in which none of the cells are farsightedly dominated by s and then considering the subgame when those rows or columns have been deleted, and repeating the process. As a result of this procedure, we are left with a subgame in which all strategy profiles other than s are farsightedly dominated by s. This procedure works because when rows or columns are "taken away," no new farsighted dominance paths can arise, and it is only possible that existing ones are disrupted by missing intermediate strategy profiles. We illustrate the proof with an example. To facilitate exposition, we provide a schematic representation of farsighted dominance paths and partitions. Consider the strategy profile s = (R1, C4). On a farsighted dominance path, player 1 can move vertically between 1-adjacent strategy profiles, and player 2 can move horizontally between 2-adjacent strategy profiles. As illustrated in the left panel of Figure 2, for every profile t = (t 1 , t 2 ) = s, put a vertical line | in the corresponding cell iff u 1 (t) < u 1 (s) and put a horizontal line -in the corresponding cell iff u 2 (t) < u 2 (s). The + in cell (R3, C1) symbolizes that in that cell, there is both | and -. The absence or presence of these lines indicates whether when at t, player 1 (2) is willing to change t 1 (t 2 ) with the goal of ending up in state s. Since s is Pareto undominated, every profile t = (t 1 , t 2 ) = s has a vertical line | or a horizontal line -(or both) in the corresponding cell.

| | -s | -| - + --- | --- • ↓ → s • → ↑ • • • • • • • • • Figure 2: Farsighted dominance paths to (R1, C4)
Determining if a strategy profile t is farsightedly dominated by s can now be established by figuring out if there is a path from t to s that in all strategy profiles along the way follows a line in the corresponding cell. The right panel of Figure 2 illustrates a farsighted dominance path (R1, C2)

→ 1 (R2, C2) → 2 (R2, C3) → 1 (R1, C3) → 2 (R1, C4) from t = (R1, C2) to s = (R1, C4).
The sequence of panels in Figure 3 illustrates the construction of the partitions of S 1 and S 2 . We use double lines to mark the separation between the strategies that have been added to U 1 (U 2 ), where those strategies added to U 1 (U 2 ) appear under (to the left of ) the double line. Thus, U 1 = U 2 = ∅ in the top-left panel, and the horizontal (vertical) double line moves up (to the right) as rows (columns) are added to We note that there is no farsighted dominance path from (R4, C1) to (R1, C4). Because u 1 (R4, C1) < u 1 (R1, C4) (there is a | in cell (R4,C1)), we put row C1 in U 2 , as illustrated in the second panel. In the subgame on {R1, R2, R3, R4} × {C2, C3, C4} that is above and to the right of the double lines now, there is no farsighted dominance path from (R4, C2) to (R1, C4), and because u 2 (R4, C2) < u 2 (R1, C4), we put row R4 in U 1 . In the subgame on {R1, R2, R3} × {C2, C3, C4} that is above and to the right of the double lines in the bottom-left panel, there is no farsighted dominance path from (R3, C2) to (R1, C4), and because u 2 (R3, C2) < u 2 (R1, C4), we put row R3 in U 1 . In the subgame on {R1, R2} × {C2, C3, C4} that is above and to the right of the double lines in the last panel, there is a farsighted dominance path from every remaining strategy profile to (R1, C4), and the procedure stops.

U 1 (U 2 ). | | -s | -| - + --- | --- | | -s | -| - + --- | --- | | -s | -| - + --- | --- | | -s | -| - + --- | ---
The use of vertical and horizontal double lines visually creates the block partition with respect to (R1, C4). The visualization as blocks makes it apparent that to get from the bottom-left block to the top-right block requires using at least one strategy profile in the top-left block or the bottom-right block as an intermediate. Thus, as can be seen in the last panel in Figure 3, when there is no -in any cell in the top-left block and no | in any cell in the bottom-right block, then there are no farsighted dominance paths to s from any of the strategy profiles that are not in the top-right block.

Proposition 4.6 is a useful tool to identify FSS, as it helps to characterize the set of strategies that are farsightedly dominated by a given strategy. In particular, it helps us characterize Singleton Farsighted Stable Sets (SFSS), which consist of one strategy profile that farsightedly dominates every other strategy profile. Theorem 4.8 A strategy profile s = (s 1 , s 2 ) ∈ S forms a SFSS if and only if it is Pareto undominated and the block partition with respect to s satisfies

U 1 = U 2 = ∅.
Theorem 4.8 suggests a method for identifying SFSS. Checking that s is a SFSS is equivalent to checking that there exists, in every row and every column, a strategy profile that is farsightedly dominated by s. 11 In practice, this means that, instead of checking that s farsightedly dominates all other m • n -1 strategy profiles, it is enough to check that s farsightedly dominates n strategy profiles (one per column, in such a way that all rows are covered). In Appendix B we show that, for some games, this reduces the complexity of searching for SFSS.

Theorem 4.8 also has some insightful corollaries, characterizing SFSS in some specific situations. 12 Corollary 4.9 Let s be a Nash equilibrium that is not Pareto dominated by any other strategy profile. Then {s} is a singleton farsighted stable set.

Corollary 4.10 Suppose that there exists a strategy profile s that Pareto dominates all other strategy profiles. Then {s} is a singleton farsighted stable set. Moreover, {s} is the unique farsighted stable set.

s 2 t 2 s 1 s st t 1 ts t
It turns out that the characterization of the farsighted stable sets is more transparent if one distinguishes between three types of games according to the number of pure-strategy Nash equilibria. A 2 × 2 game can either admit two pure-strategy Nash equilibria, one pure-strategy Nash equilibrium, or no pure-strategy Nash equilibrium. We now comment on the characterization of farsighted stable sets for each of the three types of games. First consider the case when G admits two pure-strategy Nash equilibria. When one Nash equilibrium Pareto dominates the other, the game has a unique farsighted stable set, which is a singleton farsighted stable set consisting of the Pareto dominant Nash equilibrium. If neither pure-strategy Nash equilibrium Pareto dominates the other, the game has two farsighted stable sets, each of which is a singleton farsighted stable set consisting of a Nash equilibrium.

When G admits a single pure-strategy Nash equilibrium, s, this equilibrium forms a singleton farsighted stable set if and only if it is not Pareto dominated. All other strategy profiles also can form singleton farsighted stable sets for some configurations of the parameters. The conditions derived in Proposition 5.1 allow for different singleton farsighted stable sets to co-exist. The only incompatibility is that {st} and {ts} cannot both be singleton farsighted stable sets for the same game G. The following example shows that the three farsighted stable sets {s}, {t} and {st} can co-exist for the same game.

Example 5.2 Consider the game G:

s 2 t 2 s 1 1, 3 3, 1 t 1 0, 0 2, 2
In this game, the sets {s}, {t} and {st} are singleton farsighted stable sets.

When G admits a single pure-strategy Nash equilibrium, Proposition 5.1 also provides conditions for the 2-element set {s, t} to be a farsighted stable set. These conditions are familiar -they describe a 2 × 2 game in which s is a dominant strategy equilibrium that is Pareto dominated by t, in other words a Prisoners' Dilemma. Proposition 5.1 shows that the Prisoners' Dilemma is a special game: It is the only 2 × 2 game that does not admit a singleton farsighted stable set and it is also the only 2×2 game that admits a 2-element farsighted stable set.

When G does not admit a pure-strategy Nash equilibrium, each of the four strategy profiles forms a singleton farsighted stable set for some parameter values, and all farsighted stable sets are singletons. The conditions in Proposition 5.1 show that at least one singleton farsighted stable set exists for all parameter values: If u 1 (st) > u 1 (ts), either {st} is a singleton farsighted stable set (when u 2 (st) > u 2 (t)) or {t} is a farsighted stable set (when u 2 (st) < u 2 (t)). If u 1 (ts) > u 1 (st), either {ts} is a singleton farsighted stable set (when u 2 (ts) > u 2 (s)) or {s} is a singleton farsighted stable set (when u 2 (ts) < u 2 (s)). The conditions for {st} and {ts} to be farsighted stable sets are mutually exclusive, as are the conditions for {s} and {t} to be farsighted stable sets. All other combinations of two singleton farsighted stable sets are compatible.

The exhaustive characterization in Proposition 5.1 shows that farsighted stable sets exist in all 2 × 2 games. With the exception of the Prisoners' Dilemma, all games admit singleton farsighted stable sets (with some games admitting multiple singleton farsighted stable sets). The Prisoners' Dilemma is the only 2 × 2 game that admits a 2-element farsighted stable set.

The existence result can be generalized to all games where one of the two players only has two strategies, as shown in the following proposition.

Theorem 5.3 Every generic 2 × n game has at least one farsighted stable set.

Pairwise moves

In this section, we allow both players to coordinate switching strategies simultaneously, so that the move from any strategy profile t to any other strategy profile s is feasible. This changes the definitions of the myopic dominance relation and the farsighted dominance relation as follows. Definition 6.1 Myopic dominance with pairwise moves Allowing pairwise moves, strategy profile s ∈ S myopically dominates strategy profile t ∈ S if either u 1 (s) > u 1 (t) and u 2 (s) > u 2 (t) (both players improve their payoffs by a coordinated change from t to s), or there exists a player i ∈ N such that the two profiles are i-adjacent, and u i (s) > u i (t) (player i can unilaterally change the strategy profile from t to s and improves their payoff by doing so). Definition 6.2 Farsighted dominance with pairwise moves Allowing pairwise moves, a strategy profile s ∈ S farsightedly dominates a strategy profile t ∈ S if there exists an alternating sequence of k + 1 strategy profiles and k moves t = s 1 → I 1 s 2 → I 2 s 3 . . . s k → I k s k+1 = s such that s 1 , . . . , s k+1 ∈ S, and for each l ∈ {1, . . . , k} either (a) I l = {1, 2}, u 1 (s l ) < u 1 (s), and u 2 (s l ) < u 2 (s), or (b) I l = {i l }, strategy profiles s l and s l+1 are i l -adjacent, and u i l (s l ) < u i l (s).

Myopic cores and stable sets with pairwise moves

Allowing for pairwise moves increases the number of myopic dominance relations. Hence the myopic core with pairwise moves is a subset of the myopic core without pairwise moves. More precisely, we obtain: Proposition 6.3 The myopic core with pairwise moves is equal to the set of Pareto-undominated pure-strategy Nash equilibria.

Allowing for pairwise moves also affects the myopic stable set. In fact, as opposed to the situation where only individual strategy switches are allowed, the myopic stable set may fail to exist as shown in the following example: Example 6.4 Consider again the Prisoners' Dilemma, whose myopic stable set with pairwise moves was first investigated by Okada [START_REF] Okada | The possibility of cooperation in an n-person prisoners' dilemma with institutional arrangements[END_REF]:

C1 C2 R1 2, 2 0, 3 R2 3, 0 1, 1
Allowing pairwise moves, all myopic dominance relations are: (R2, C1) m (R1, C1), (R2, C2) m (R1, C2), (R1, C2) m (R1, C1), (R2, C2) m (R2, C1) (through moves by one player), and (R1, C1) m (R2, C2) through a coordinated move by both players.

Note that any set that contains (R1, C1) violates internal stability if it also contains any of the other three strategy profiles. However, strategy profiles (R2, C1) and (R1, C2) are not myopically dominated by (R1, C1) and thus {(R1, C1)} is not a myopic stable set. We conclude that a myopic stable set cannot have (R1, C1) as an element. Thus, to satisfy external stability, a myopic stable set needs to include (R2, C1) and/or (R1, C2). Then, it cannot include (R2, C2) because that would violate internal stability. However, (R2, C2) is not myopically dominated by either (R2, C1) or (R1, C2) and thus external stability is violated when (R2, C2) is not included. We conclude that there is no myopic stable set.

Farsighted cores and stable sets with pairwise moves

As we saw in Subsection 4.1, even when only unilateral moves are allowed, the farsighted core contains at most a single element. Allowing for pairwise moves increases the opportunities for dominance, and thus further restricts the core, causing sufficient conditions for non-emptiness to become very strong.

Singleton farsighted stable sets are more likely to exist as a result of increased opportunities for dominance, because it is easier for a strategy profile to farsightedly dominate all other strategy profiles. Extending a result by Kawasaki [START_REF] Kawasaki | Maximin, minimax, and von neumann-morgenstern farsighted stable sets[END_REF], we establish existence of a singleton farsighted stable set for any game G. Proposition 6.5 When pairwise moves are allowed, there exists a singleton farsighted stable set for any m × n game G.

Our proof of Proposition 6.5 is constructive and identifies for each game a strategy profile that forms a singleton farsighted stable set. Kawasaki [START_REF] Kawasaki | Maximin, minimax, and von neumann-morgenstern farsighted stable sets[END_REF] instead characterizes all singleton farsighted stable sets in games in which there exists a strategy profile t such that u i (t) > min s j max s i u i (s i , s j ) for i = 1, 2. It is interesting to note that in games that do not satisfy this condition, when m ≤ n our proof uses the block partition property to identify the singleton farsighted stable set {t} where t is the strategy profile such that

u 2 (t) = min s 1 max s 2 u 2 (s 1 , s 2 ).
Note that a singleton farsighted stable set need not contain a Nash equilibrium, even when a pure-strategy Nash equilibrium exists and is unique: In the Prisoners' Dilemma, the unique singleton farsighted stable set is formed by the strategy profile in which each player plays their dominated strategy.

Conclusions

This paper revisits the analysis of stable sets in 2-player strategic-form games. Our two main contributions are (i) to establish a connection between myopic stable sets and the stable matchings of an auxiliary two-sided matching problem and (ii) to identify a structural property of 2-player games, "the block partition property," which helps identify the strategy profiles that are indirectly dominated by a fixed profile. By establishing a connection between myopic stable sets and stable matchings, we can apply results from matching theory to characterize the myopic stable sets. By using the block partition property, we are able to reduce the complexity of checking whether a strategy profile is a singleton farsighted stable set for some games, and also to prove that undominated pure-strategy Nash equilibria form singleton farsighted stable sets. Our analysis also generalizes and unifies existing results on myopic and farsighted stable sets in 2-player games.

The analysis in the paper relies strongly on the description of a strategic situation as elements of a finite set of social states, limiting us to pure strategy profiles and finite strategy sets. The extension of the results to continuous sets of social states, which would allow us to study mixed strategy profiles or pure strategy profiles in continuous strategy sets, is challenging and we leave it to further study.

The generalization of our two main results to games with more than two players poses serious difficulties. As the following example shows, with more than two players, one cannot draw a connection between the myopic stable set and stable matchings in an auxiliary multi-sided matching problem. This game has a unique myopic stable set consisting of four elements: (R1, C1, M 1), (R1, C2, M 2), (R2, C1, M 2), (R2, C2, M 1). Each of the strategies of the three players is associated to two different pairs of strategies of the other players. Hence one cannot construct a one-to-one matching between the strategies of the players to characterize the myopic stable set.

Furthermore, as the next example shows, there is no straightforward way to extend the "Block Partition Property" to games with more than two players. Consider strategy profile s = (R2, C2, M 2), resulting in the payoff vector [START_REF] Dutta | Rational expectations and farsighted stability[END_REF][START_REF] Demuynck | The myopic stable set for social environments[END_REF][START_REF] Demuynck | The myopic stable set for social environments[END_REF]. This strategy profile is Pareto undominated.

There is no farsighted dominance path to s = (R2, C2, M 2) from either t = (R1, C1, M 1) or v = (R2, C1, M 1) because both players 2 and 3 obtain higher payoffs in t and v than in s, and player 1 cannot move out of the first column or the first matrix. There is a farsighted dominance path from any other strategy profile to s because all players get a strictly higher payoff in s, and thus are willing to move to s, and can do so using paths that do not go through t or v. We conclude that the set of strategy profiles from which there is a farsighted dominance path to s and that in addition includes s is given by D = {(R1, C2, M 1), (R2, C2, M 1), (R1, C1, M 2), (R1, C2, M 2), (R2, C1, M 2), (R2, C2, M 2)}. It is clear that D cannot be written as a Cartesian product D = D 1 ×D 2 ×D 3 because the Cartesian products D 1 ×D 2 ×D 3 with |D i | ≤ 2 have cardinality 0, 1, 2, 4, or 8. Therefore, the block partition property cannot be extended to this 3-player game.

(s 1 , s 2 ). If (s 1 , s 2 ) is myopically dominated by a profile (s 1 , s2 ) ∈ Σ that is in the same row, then u 2 (s 1 , s2 ) > u 2 (s 1 , s 2 ) and also s2 = µ(s 1 ), and thus µ(s 1 ) s 1 s 2 . If (s 1 , s 2 ) is myopically dominated by a profile (s 1 , s 2 ) ∈ Σ that is in the same column, then u 1 (s 1 , s 2 ) > u 1 (s 1 , s 2 ) and also s1 = µ(s 2 ), and thus µ(s 2 ) s 2 s 1 . We conclude that (s 1 , s 2 ) is not a blocking pair, and more generally that there does not exist any blocking pair.

Sufficiency. Let Σ ⊂ S 1 ×S 2 and suppose that there is a stable matching

µ such that Σ = {(s 1 , µ(s 1 )) | s 1 ∈ S 1 }. Because (s 1 , µ(s 1 )) ∈ S 1 × S 2 ,
we know that µ(s 1 ) ∈ S 2 for each s 1 ∈ S 1 and thus Σ is a set of m strategy profiles including exactly one strategy profile in every row.

Because by definition of a matching, µ does not match the same column s 2 ∈ S 2 with different rows in S 1 , there is at most one strategy profile in Σ in each column. It follows that for any two (s 1 , s 2 ), (t 1 , t 2 ) ∈ Σ, it holds that s 1 = t 1 and s 2 = t 2 , meaning that the profiles are not adjacent. Thus, Σ satisfies internal stability.

It remains to show that Σ satisfies external stability. Consider a strategy profile (s 1 , s 2 ) ∈ S 1 × S 2 \ Σ. We will demonstrate that there exist a strategy profile in Σ that myopically dominates (s 1 , s 2 ). Note that there are only two possible strategy profiles in Σ that (s 1 , s 2 ) can be adjacent to, namely (s 1 , µ(s 1 )) and (µ(s 2 ), s 2 ). By definition, (s 1 , µ(s 1 )) ∈ Σ and (s 1 , s 2 ) is 2adjacent that strategy profile. However, it may be that µ(s 2 ) = s 2 and then there is no strategy profile in Σ that (s 1 , s 2 ) is 1-adjacent to. We distinguish between two cases. Case 1. If µ(s 2 ) = s 2 , then (s 1 , s 2 ) is 1adjacent to (µ(s 2 ), s 2 ) ∈ Σ. Because µ is a stable matching, (s 1 , s 2 ) is not a blocking pair, and µ(s 1 ) s 1 s 2 or µ(s 2 ) s 2 s 1 (or both) hold. Thus, u 2 (s 1 , µ(s 1 )) > u 2 (s 1 , s 2 ) and (s 1 , µ(s 1 )) (s 1 , s 2 ), or u 1 (µ(s 2 ), s 2 ) > u 1 (s 1 , s 2 ) and (µ(s 2 ), s 2 ) (s 1 , s 2 ). Case 2. If µ(s 2 ) = s 2 , then s 1 s 2 µ(s 2 ) by definition of the preferences in the auxiliary matching problem. Because (s 1 , s 2 ) is not a blocking pair, we then know that and µ(s 1 ) s 1 s 2 . Thus,

u 2 (s 1 , µ(s 1 )) > u 2 (s 1 , s 2 ) and (s 1 , µ(s 1 )) (s 1 , s 2 ).
Proof of Proposition 3.7. Each of the statements follows by using the correspondence that we established in Theorem 3.6 between myopic stable sets of G and stable matchings in the auxiliary matching problem, and known properties of stable matchings. 1. This follows from the fact that every 2sided matching problem admits a stable matching (Gale and Shapley [START_REF] Gale | College admissions and the stability of marriage[END_REF]). 2. By definition of a matching, every strategy s i ∈ S i is matched with a unique strategy in S j ∪ {s i }. In addition, m ≤ n and in the auxiliary matching problem all s 1 ∈ S 1 rank all s 2 ∈ S 2 above s 1 , and then a stable matching matches every s 1 ∈ S 1 to a s 2 ∈ S 2 . 3. Let (s 1 , s 2 ) be a pure-strategy sets of undominated rows and columns.

Induction step. Suppose that we have already defined U k 1 and U k 2 . Consider the subgame G k with strategy sets S 1 \ U k 1 for player 1 and S 2 \ U k 2 for player 2, and payoffs as in G. Consider farsighted dominance paths in G k , i.e., farsighted dominance paths that use only strategy profiles in

S 1 \ U k 1 × S 2 \ U k 2 . If in subgame G k all strategy profiles t ∈ S 1 \ U k 1 × S 2 \ U k 2
\ {s} are farsightedly dominated by s, then stop and define

U 1 = U k 1 , U 2 = U k 2 , D 1 = S 1 \ U k 1 , and D 2 = S 2 \ U k 2 . If there exists a strategy profile t = (t 1 , t 2 ) ∈ S 1 \ U k 1 × S 2 \ U k 2
\{s} that is not farsightedly dominated by s in the subgame G k , then consider such a t. Because s satisfies PU, we know that u 1 (t) < u 1 (s) or u 2 (t) < u 2 (s) or both hold.

Case 1. Suppose that u 2 (t) < u 2 (s). Then t 1 = s 1 because in that case (t 1 , t 2 ) → 2 (t 1 , s 2 ) = (s 1 , s 2 ) would be a farsighted dominance path from t to s in subgame G k . In addition, no strategy profile in row t 1 can be farsightedly dominated by s in subgame G k , because if there exists a t2 ∈ S 2 such that there is a farsighted dominance path (t 1 , t2 ) -→ (s 1 , s 2 ) from (t 1 , t2 ) to s using only strategy profiles in

S 1 \ U k 1 × S 2 \ U k 2 ,
then adding that farsighted dominance path following the move (t 1 , t 2 ) → 2 (t 1 , t2 ) creates a farsighted dominance path (t 1 , t 2 ) → 2 (t 1 , t2 ) -→ (s 1 , s 2 ) from t to s in subgame G k . We add the row t 1 = s 1 to U k 1 and define U k+1

1 = U k 1 ∪ {t 1 }. Case 2.
Suppose that u 1 (t) < u 1 (s). Then t 2 = s 2 because in that case (t 1 , t 2 ) → 1 (s 1 , t 2 ) = (s 1 , s 2 ) would be a farsighted dominance path from t to s in subgame G k . In addition, no strategy profile in column t 2 can be farsightedly dominated by s in subgame G k , because if there exists a t1 ∈ S 1 such that there is a farsighted dominance path ( t1 , t 2 ) -→ (s 1 , s 2 ) from ( t1 , t 2 ) to s using only strategy profiles in

S 1 \ U k 1 × S 2 \ U k 2 , then adding that farsighted dominance path following the move (t 1 , t 2 ) → 1 ( t1 , t 2 ) creates a farsighted dominance path (t 1 , t 2 ) → 1 ( t1 , t 2 ) -→ (s 1 , s 2 ) from t to s in subgame G k . We add the column t 2 = s 2 to U k 2 and define U k+1 2 = U k 2 ∪ {t 2 }.
Note that cases 1 and 2 are not mutually exclusive, and if both u 1 (t) < u 1 (s) and u 2 (t) < u 2 (s) hold, then we add t 1 to U k 1 and we add t 2 to U k 2 . After executing the induction step, if there existed a strategy profile that was not farsightedly dominated by s in the subgame G k , we have added at least one strategy to either U k 1 or U k 2 . Now, apply the induction step again, this time to the smaller subgame G k+1 with strategy sets

S 1 \ U k+1 1 and S 2 \ U k+1 2 .
Since we only add strategies to U k 1 and U k 2 , but never take them out, the inductive procedure ends after K steps, where 14 when in 14 The -2 comes from the fact that the strategies s 1 and s 2 are never put into

K ≤ |S 1 | + |S 2 | -2,
U k 1 or U k 2 .
the subgame G K all strategy profiles in S

1 \ U K 1 × S 2 \ U K 2
\ {s} are farsightedly dominated by s and we define

U 1 = U K 1 , U 2 = U K 2 , D 1 = S 1 \U K 1 , and D 2 = S 2 \ U K 2 .
We next demonstrate that U 1 , U 2 , D 1 , and D 2 so defined satisfy the requirements in BPP.

In each induction step k < K, one or two strategies are added to U k 1 and/or U k 2 and the subgame G k+1 has fewer strategy profiles than the game

G k . Because S 1 \ U k+1 1 × S 2 \ U k+1 2 ⊂ S 1 \ U k 1 × S 2 \ U k 2 , no new far- sighted dominance paths become possible in G k+1 . Thus, if a strategy profile t = (t 1 , t 2 ) ∈ S 1 \ U k+1 1 × S 2 \ U k+1 2 , t = s,
is farsightedly dominated by s in the subgame G k+1 , then it is also farsightedly dominated by s in G. Since by definition D 1 and D 2 are the strategy sets of players 1 and 2 in the subgame G K and all strategy profiles in (D 1 × D 2 ) \ {s} are farsightedly dominated by s in subgame G K , it follows that these profiles are also farsightedly dominated by s in the game G with strategy sets S 1 and S 2 . This demonstrates one part of BPP, namely that all t ∈ D 1 × D 2 \ {s} are farsightedly dominated by s in the game G.

We next demonstrate that none of the strategy profiles t ∈ (S 1 × S 2 ) \ (D 1 × D 2 ) are farsightedly dominated by s in the game G with strategy sets S 1 and S 2 . With each induction step k < K, strategies are added to U k 1 or U k 2 and the subgame G k+1 has fewer strategy profiles than the game G k . Thus, the possibilities for building farsighted dominance paths to s are restricted because some strategy profiles ( t1 , t2 ), where either t1 ∈ U k+1

1 \ U k 1 or t2 ∈ U k+1 2 \ U k
2 , can no longer be used as intermediate strategy profiles. However, we only add a row t1 to U k 1 when no strategy profile in row t1 is farsightedly dominated by s in the subgame G k , and then farsighted dominance paths to s cannot pass through profiles ( t1 , t2 ). Thus, if a strategy profile

t ∈ S 1 \ U k 1 ∪ { t1 } × S 2 \ U k 2
is not farsightedly dominated by s in the subgame G k+1 , then it is also not farsightedly dominated by s in the subgame G k . Similarly, we add a column t2 to U k 2 when no strategy profile in column t2 is farsightedly dominated by s in the subgame G k , and then farsighted dominance paths to s cannot have profiles ( t1 , t2 ) as intermediate nodes. Thus, if a strategy profile in

S 1 \ U k 1 × S 2 \ U k 2 ∪ { t2
} is not farsightedly dominated by s in the subgame G k+1 , then it is also not farsightedly dominated by s in the subgame G k . Applying this reasoning repeatedly, we thus obtain that in each induction step, if we add a row t1 to U k 1 then no strategy profile in row t1 is farsightedly dominated by s in the game G with strategy sets S 1 and S 2 , and if we add a column t2 to U k 2 then no strategy profile in column t2 is farsightedly dominated by s in the game G with strategy sets S 1 and S 2 . Thus, no strategy profile t = (t 1 , t 2 ) such that t 1 ∈ U 1 or t 2 ∈ U 2 (or both) is farsightedly dominated by s in the game sighted stable set with more than two elements, and there are only two candidate 2-element farsighted stable sets, {s, t} and {st, ts}.

Case 1: G admits two pure-strategy Nash equilibria, s and t. Notice that s st and s ts. If u 1 (s) > u 1 (t), then t → 1 st → 2 s is a farsighted dominance path and s t. If u 2 (s) > u 2 (t), then t → 2 ts → 1 s is a farsighted dominance path and again s t. Hence s farsightedly dominates all other strategy profiles whenever u 1 (s) > u 1 (t) or u 2 (s) > u 2 (t). If u 1 (s) < u 1 (t) and u 2 (s) < u 2 (t), then t Pareto dominates s and thus s does not farsightedly dominate t. We conclude that s forms a singleton farsighted stable set if and only if u 1 (s) > u 1 (t) or u 2 (s) > u 2 (t). A similar reasoning holds for t.

Because t st and s st, st does not farsightedly dominate any other strategy profile. Similarly, ts does not farsightedly dominate any other strategy profile. We conclude that neither st nor ts forms a singleton farsighted stable set.

We next rule out the two possible 2-element stable sets. The set {s, t} fails internal stability because either u 1 (s) > u 1 (t) and s farsightedly dominates t, or u 1 (t) > u 1 (s) and t farsightedly dominates s. The set {st, ts} fails external stability because neither s nor t are farsightedly dominated by st or ts.

Case 2. G admits a single pure-strategy Nash equilibrium, s. The same derivation as that demonstrated in Case 1 shows that s forms a singleton farsighted stable set if and only if u 1 (s) > u 1 (t) or u 2 (s) > u 2 (t).

Consider strategy profile st. Because s myopically dominates st, {st} is a farsighted stable set if and only if s → 1 ts → 2 t → 1 st is a farsighted dominance path. Necessary and sufficient conditions for that are u 1 (st) > u 1 (t), u 2 (st) > u 2 (ts), and u 1 (st) > u 1 (s). Similarly, {ts} is a farsighted stable set if and only if s → 2 st → 1 t → 2 ts is a farsighted dominance path. Necessary and sufficient conditions for that are u 2 (ts) > u 2 (t), u 1 (ts) > u 1 (st), and u 2 (ts) > u 2 (s).

Consider the strategy profile t. If (i) holds, the path st → 2 s → 1 ts → 2 t is a farsighted dominance path, and if (ii) holds, the path ts → 1 s → 2 st → 1 t is a farsighted dominance path. This shows that t farsightedly dominates all other strategy profiles whenever (i) or (ii) hold. Conversely, suppose that t farsightedly dominates all other strategy profiles. For t to farsightedly dominate s, one of the paths s → 1 ts → 2 t or s → 2 st → 1 t has to be a farsighted dominance path. If s → 1 ts → 2 t is a farsighted dominance path, u 2 (t) > u 2 (ts) and u 1 (t) > u 1 (s) hold and then u 1 (t) < u 1 (st) (because t is not a Nash equilibrium). Thus u 2 (t) > u 2 (st) has to hold for t to farsightedly dominate st (case (i)). If s → 2 st → 1 t is a farsighted dominance path, u 1 (t) > u 1 (st) and u 2 (t) > u 2 (s) hold and then u 2 (t) < u 2 (ts) (because t is not a Nash equilibrium). Thus u 1 (t) > u 1 (ts) has to hold for t to farsightedly dominate st (case (ii)).

We now consider the two possible 2-element stable sets. Because the Nash equilibrium s myopically dominates both st and ts, the two-element set {s, t} satisfies external stability. For the set to satisfy internal stability we need that s does not farsightedly dominate t, which holds if and only if u 1 (t) > u 1 (s) and u 2 (t) > u 2 (s). In addition, we also need that t does not farsightedly dominate s, which further requires u 1 (st) > u 1 (t) and u 2 (ts) > u 2 (t).

For the set {st, ts} to satisfy external stability, there has to exist a farsighted dominance path from s to either st or ts. Because s is a Nash equilibrium, s → 1 ts → 2 t → 1 st is the only possible farsighted dominance path from s to st, but then st also farsightedly dominates ts, and internal stability fails. By a similar argument, if ts farsightedly dominates s, it must also farsightedly dominate st, violating internal stability.

Case 3. G does not admit a pure-strategy Nash equilibrium. Because the game does not admit a pure-strategy Nash equilibrium, there exists a cycle among the four strategy profiles. There are two possibilities for the cycle. Without loss of generality, we (re-)name the strategies so that u 2 (st) > u 2 (s), u 1 (s) > u 1 (ts), u 2 (ts) > u 2 (t), and u 1 (t) > u 1 (st).

Consider strategy profile s. As u 2 (st) > u 2 (s), the only possible farsighted dominance path from st to s is st → 1 t → 2 ts → 1 s. This path is a farsighted dominance path if and only if, in addition to u 1 (s) > u 1 (ts), we also have u 2 (s) > u 2 (t) and u 1 (s) > u 1 (st). Note that this implies that if s farsightedly dominates st, then it also farsightedly dominates t and ts, and thus {s} is a farsighted stable set.

As all strategy profiles play a symmetric role, conditions under which {st}, {ts} and {t} are farsighted stable sets can be found using the same reasoning as we demonstrated for {s}.

We next rule out the two possible 2-element stable sets. Consider the set {s, t}. If u 2 (t) > u 2 (s), then s → 2 st → 1 t is a farsighted dominance path, and if u 2 (t) < u 2 (s), then t → 2 ts → 1 s is a farsighted dominance path. We conclude that {s, t} violates internal stability. Similar arguments demonstrate that the set {st, ts} also is not farsighted stable.

Proof of Theorem 5.3. Let G be an 2 × n game. Denote the two strategies of player by s 1 and t 1 and, without loss of generality, assume that u 2 (s 1 , BR 2 (s 1 )) > u 2 (t 1 , BR 2 (t 1 )) and define t = (t 1 , BR 2 (t 1 )). 15 Case 1. If t satisfies PU, then {t} is a SFSS. 15 We remind the reader that BR 2 denotes player 2's best responses.

We already noted that (s 1 , v 2 ) admits a block partition. Let D 1 , U 1 , D 2 , and U 2 be the strategy sets as in BPP for (s 1 , v 2 ): s 1 ∈ D 1 and v 2 ∈ D 2 , and all r ∈ D 1 × D 2 \ {(s 1 , v 2 )} are farsightedly dominated by (s 1 , v 2 ) and no other strategy profiles are (i.e., when either r 1 ∈ U 1 or r 2 ∈ U 2 or both). Because every strategy profile in which player 1 plays t 1 is farsightedly dominated by (s 1 , v 2 ), we know that D 1 = S 1 and D 2 = S 2 , and thus (s 1 , v 2 ) forms a singleton FSS.

Case 2.2. If there does not exist a strategy w 2 such that u

1 (t 1 , w 2 ) < u 1 (s 1 , v 2 ) and u 2 (s 1 , w 2 ) ≤ u 2 (s 1 , v 2 ), then {(t 1 , t 2 ), (s 1 , v 2 )} is a FSS.
Internal stability: Because (s 1 , v 2 ) Pareto dominates (t 1 , t 2 ), Lemma 4.2 tells us that (t 1 , t 2 ) does not farsightedly dominate (s 1 , v 2 ). To establish that the set of strategy profiles {(t 1 , t 2 ), (s 1 , v 2 )} satisfies internal stability, it remains to show that (s 1 , v 2 ) does not farsightedly dominate (t 1 , t 2 ). To show this, we demonstrate that any path from (t 1 , t 2 ) to (s 1 , v 2 ) violates the conditions of a farsighted dominance path. It suffices to consider paths in which players 1 and 2 alternate moving, because when the same player makes more than one consecutive move on a farsighted dominance path, then the intermediate moves can be skipped to obtain a shorter farsighted dominance path. So, consider a path from (t 1 , t 2 ) to (s 1 , v 2 ) in which players 1 and 2 alternate moving. Because u 1 (t 1 , w 2 ) < u 1 (s 1 , v 2 ) and u 2 (s 1 , w 2 ) ≤ u 2 (s 1 , v 2 ) do not both hold when w 2 = v 2 , we know that u 1 (t 1 , v 2 ) > u 1 (s 1 , v 2 ). Thus, if the last step on the path is (t 1 , v 2 ) → 1 (s 1 , v 2 ) then the path is not a farsighted dominance path. Thus, the last step on a farsighted dominance path must be (s 1 , w 2 ) → 2 (s 1 , v 2 ) for some w 2 = v 2 . Because players 1 and 2 alternate moving on the path, and because somewhere player 1 needs to change from t 1 to s 1 , we know that the one-but-last step on the path is (t

1 , w 2 ) → 1 (s 1 , w 2 ). Because u 1 (t 1 , w 2 ) < u 1 (s 1 , v 2 ) and u 2 (s 1 , w 2 ) ≤ u 2 (s 1 , v 2 ) cannot both hold, we know that (t 1 , w 2 ) → 1 (s 1 , w 2 ) → 2 (s 1 , v 2
) cannot be the last section of a farsighted dominance path. This establishes that there is no farsighted dominance path from (t 1 , t 2 ) to (s 1 , v 2 ).

External stability: We first show that (t 1 , t 2 ) is a Nash equilibrium. Because (s 1 , v 2 ) Pareto dominates (t 1 , t 2 ) and because u 1 (t 1 , w 2 ) < u 1 (s 1 , v 2 ) and u 2 (s 1 , w 2 ) ≤ u 2 (s 1 , v 2 ) do not both hold when w 2 = t 2 , we know that u 2 (s 1 , t 2 ) > u 2 (s 1 , v 2 ). By the definition of v 2 we then know that (s 1 , t 2 ) does not Pareto dominate (t 1 , t 2 ). Because u 2 (s 1 , t 2 ) > u 2 (s 1 , v 2 ) > u 2 (t 1 , t 2 ) (where the last inequality follows because (s 1 , v 2 ) Pareto dominates (t 1 , t 2 )), it must thus be the case that u 1 (s 1 , t 2 ) < u 1 (t 1 , t 2 ). Therefore, t 1 is player 1's best response to t 2 . Since t 2 is player 2's best response to t 1 by definition, we have now established that (t 1 , t 2 ) is a Nash equilibrium. Because t 2 is payer 2's best response to t 1 , every strategy profile in which player 1 plays t 1 is farsightedly dominated by (t 1 , t 2 ) via a one-step farsighted dominance path. Consider a strategy profile (s 1 , w 2 ), i.e., a strategy profile in which player 1 plays s 1 . We will prove that every such profile is either equal to (s 1 , v 2 ), or that it is farsightedly dominated by (s 1 , v 2 ) or (t 1 , t 2 ). This in turn establishes external stability of the set of strategy profiles {(t 1 , t 2 ), (s 1 , v 2 )}. For all w 2 , it is obviously either the case that (s 1 , w 2 ) Pareto dominates (t 1 , t 2 ) or that it does not Pareto dominate (t 1 , t 2 ). Case 2.2.1. If (s 1 , w 2 ) does not Pareto dominate the Nash equilibrium (t 1 , t 2 ), then either u 1 (s 1 , w 2 ) < u 1 (t 1 , t 2 ) and (s 1 , w 2 ) → 1 (t 1 , w 2 ) → 2 (t 1 , t 2 ) is a farsighted dominance path, or u 2 (s 1 , w 2 ) < u 2 (t 1 , t 2 ) and (s 1 , w 2 ) → 2 (s 1 , t 2 ) → 1 (t 1 , t 2 ) is a farsighted dominance path. Thus, (s 1 , w 2 ) is farsightedly dominated by (t 1 , t 2 ). (Note that w 2 = t 2 is included in this case.) Case 2.2.2. If (s 1 , w 2 ) Pareto dominates (t 1 , t 2 ), then because we choose (s 1 , v 2 ) such that it has the highest payoff for player 2 among all strategy profiles that Pareto dominate (t 1 , t 2 ), we know that player 2's payoff in (s 1 , w 2 ) is lower than or equal to that in (s 1 , v 2 ). Because we are only considering generic games, if player 2's payoff is equal in (s 1 , w 2 ) and (s 1 , v 2 ), then it must hold that w 2 = v 2 and the profile is equal to (s 1 , v 2 ). If u 2 (s 1 , w 2 ) < u 2 (s 1 , v 2 ), then (s 1 , v 2 ) farsightedly dominates (s 1 , w 2 ) via a one-step farsighted dominance path that has player 2 move from (s 1 , w 2 ) to (s 1 , v 2 ).

Proof of Proposition 6.3. Because the myopic core with pairwise moves is a subset of the myopic core, any element must be a pure-strategy Nash equilibrium. There exists a pairwise move out of a Nash equilibrium s that benefits both players if and only if there exists a strategy profile that Pareto dominates s.

Proof of Proposition 6.5: Let G be an m × n game with m ≤ n. We focus on player 2's best responses to player 1's strategies and define BR := {(s 1 , BR 2 (s 1 )) | s 1 ∈ S 1 }, the set of all strategy profiles in which player 2 is best responding to player 1's strategy. Let t = (t 1 , t 2 ) be the strategy profile in BR that gives player 2 the lowest payoff. We distinguish between two cases: Case 1. If t satisfies PU, then {t} is a SFSS.

Because t satisfies PU, it admits a block partition (Proposition 4.6). 16Let D 1 , U 1 , D 2 , and U 2 be the strategy sets as in BPP for t: t 1 ∈ D 1 and t 2 ∈ D 2 , and all r ∈ D 1 ×D 2 \{t} are farsightedly dominated by t and no other strategy profiles are (i.e., when either r 1 ∈ U 1 or r 2 ∈ U 2 or both). Now note that t 2 is player 2's best response to t 1 and thus every strategy profile (t 1 , v 2 ) is farsightedly dominated by t via the one-step path (t 1 , v 2 ) → 2 (t 1 , t 2 ). From this we know that D 2 = S 2 . Now, consider a strategy profile (s 1 , s 2 ) ∈ BR with s 1 = t 1 . By definition of t, we know that u 2 (s 1 , s 2 ) > u 2 (t 1 , t 2 ). Because t satisfies PU, this implies that u 1 (s 1 , s 2 ) < u 1 (t 1 , t 2 ). It thus follows from Lemma 4.5 that (s 1 , s 2 ) ∈ U 1 × D 2 . Because s 2 ∈ D 2 , we then know that s 1 ∈ D 1 . Because every strategy of player 1 is represented in BR, we can conclude that D 1 = S 1 .

We have now shown that D 1 = S 1 and D 2 = S 2 , and thus t forms a singleton FSS.

Case 2. If t does not satisfy PU, then pick among those strategy profiles that Pareto dominate (t 1 , t 2 ) the (s 1 , s 2 ) that gives player 1 the highest payoff. Then {(s 1 , s 2 )} is a SFSS.

Note that it is possible that s 2 = t 2 (namely when (t 1 , t 2 ) is Pareto dominated by a strategy profile that shares a column with (t 1 , t 2 )). However, because t 2 is player 2's best response to t 1 , it holds that (t 1 , t 2 ) can only be Pareto dominated by a strategy profile in which player 1 plays a strategy different from t 1 . Also note that (s 1 , s 2 ) satisfies PU because every strategy profile (v 1 , v 2 ) that gives player 1 a higher payoff cannot Pareto dominate (t 1 , t 2 ) and thus must give player 2 a lower payoff than (t 1 , t 2 ), so that u 2 (v 1 , v 2 ) < u 2 (t 1 , t 2 ) < u 2 (s 1 , s 2 ) (where the last step follows because (s 1 , s 2 ) Pareto dominates (t 1 , t 2 )). We will show that there is a farsighted dominance path to (s 1 , s 2 ) from any strategy profile (v 1 , v 2 ) = (s 1 , s 2 ). Consider an arbitrary strategy profile (v 1 , v 2 ) = (s 1 , s 2 ). Then either this profile is Pareto dominated by (s 1 , s 2 ), or it is not and then u 1 (v 1 , v 2 ) > u 1 (s 1 , s 2 ) or u 2 (v 1 , v 2 ) > u 2 (s 1 , s 2 ), but not both because (s 1 , s 2 ) satisfies PU. We distinguish between these 3 cases. Case 2.2. u 1 (v 1 , v 2 ) < u 1 (s 1 , s 2 ) and u 2 (v 1 , v 2 ) > u 2 (s 1 , s 2 ). Consider the path (v 1 , v 2 ) → 1 (t 1 , v 2 ) → 2 (t 1 , t 2 ) → {1,2} (s 1 , s 2 ) (with the obvious adjustments if v 1 = t 1 or v 2 = t 2 ). We check all three moves on this path to verify that it is a farsighted dominance path. Because (s 1 , s 2 ) Pareto dominates (t 1 , t 2 ), we know that u 1 (t 1 , t 2 ) < u 1 (s 1 , s 2 ) and u 2 (t 1 , t 2 ) < u 2 (s 1 , s 2 ), which explains the pairwise move (t 1 , t 2 ) → {1,2} (s 1 , s 2 ). Because t 2 = BR 2 (t 1 ) and (s 1 , s 2 ) Pareto dominates (t 1 , t 2 ), we know that vertices in row R1 are directly connected to (R1, C3), all remaining vertices in column C1 are connected at distance 2, and all other vertices at distance 3. This implies that the time complexity of checking that s is a mother vertex is of order O(n 3 ) in the DFS algorithm, and O(n 2 ) in the BFS algorithm, whereas checking that there is a path from s to every row and every column only has a time complexity O(n 2 ).

However, in other games, Theorem 4.8 does not reduce the complexity of checking that s is a SFSS, as illustrated in the next example.

Definition 3 . 2 A 2 -

 322 sided matching problem consists of two disjoint sets M and W , preferences m over the set W ∪ {m} for each agent m ∈ M , and preferences w over the set M ∪ {w} for each agent w ∈ W . Definition 3.3 A matching µ is a mapping from M ∪W into itself such that µ(m) ∈ W ∪ {m} for each m ∈ M , µ(w) ∈ M ∪ {w} for each w ∈ W , and for all m ∈ M and w ∈ W it holds that µ(m) = w if and only if µ(w) = m. Definition 3.4 A matching µ is stable if and only if (i) µ(m) m m if µ(m) = m, (ii) µ(w) w w if µ(w) = w, and (iii) there does not exist a pair (m, w) ∈ M × W such that w m µ(m) and m w µ(w).

Example 3 . 5

 35 Consider the following 3 × 4 game:

Lemma 4 .

 4 2 motivates us to consider strategy profiles that are not Pareto dominated.

Example 4 . 7 Figure 1 : 4 ×

 4714 Figure 1: 4 × 4 game G

Figure 3 :

 3 Figure 3: Illustration of the procedure to construct U 1 and U 2

Example 7 . 1

 71 Consider the following 3-player game where player 1 chooses rows, player 2 chooses columns and player 3 chooses matrices.

Example 7 . 2 1

 721 Consider the following 3-player game where player 1 chooses rows, player 2 chooses columns and player 3 chooses matrices. R2 0, 0, 0 7, 5, 5

Case 2 . 1 .

 21 (v 1 , v 2 ) is Pareto dominated by (s 1 , s 2 ). Then (v 1 , v 2 ) → {1,2} (s 1 , s 2 ) is a farsighted dominance path.

(Figure B. 3 :

 3 Figure B.3: Covering graph of (R1, C3) in game G1

Example B. 2 Figure B. 4 : 3 ×

 243 Figure B.4: 3 × 3 game G2

  Definition 2.5 Myopic Core The myopic core is the core with respect to the myopic dominance relation .

	Definition 2.6 Farsighted Core The farsighted core is the core with re-
	spect to the farsighted dominance relation .
	Definition 2.7 Myopic stable set A myopic stable set is a stable set with
	respect to the myopic dominance relation .
	Definition 2.8 Farsighted stable set A farsighted stable set is a stable
	set with respect to the farsighted dominance relation .

  Proposition 5.1 Let G be a 2 × 2 game. Renaming strategies if necessary, G has the following farsighted stable sets. 1. Suppose the game G admits two pure-strategy Nash equilibria, s and t. Then {s} is a farsighted stable set if and only if u Suppose the game G does not admit any pure-strategy Nash equilibrium, and the cycle that exists among the four strategy profiles is u 2 (st) > u 2 (s), u 1 (s) > u 1 (ts), u 2 (ts) > u 2 (t), and u 1 (t) > u 1 (st). Then {s} is a farsighted stable set if and only if u 1 (s) > u 1 (st) and u 2 (s) > u 2 (t), {st} is a farsighted stable set if and only if u 1 (st) > u 1 (ts) and u 2 (st) > u 2 (t), {t} is a farsighted stable set of and only if u 1 (t) > u 1 (ts) and u 2 (t) > u 2 (s), and {ts} is a farsighted stable set if and only if u 1 (ts) > u 1 (st) and u 2 (ts) > u 2 (s). There are no other farsighted stable sets.

1 (s) > u 1 (t) or u 2 (s) > u 2 (t), and {t} is a farsighted stable set if and only if u 1 (t) > u 1 (s) or u 2 (t) > u 2 (s). There are no other farsighted stable sets. 2. Suppose the game G admits a single pure-strategy Nash equilibrium, s. Then {s} is a farsighted stable set if and only if u 1 (s) > u 1 (t) or u 2 (s) > u 2 (t), {st} is a farsighted stable set if and only if u 1 (st) > max{u 1 (s), u 1 (t)} and u 2 (st) > u 2 (ts), {ts} is a farsighted stable set if and only if u 1 (ts) > u 1 (st) and u 2 (ts) > max{u 2 (s), u 2 (t)}, and {t} is a farsighted stable set if and only if either (i) u 1 (t) > u 1 (s) and u 2 (t) > max{u 2 (ts), u 2 (st)}, or (ii) u 1 (t) > max{u 1 (st), u 1 (ts)} and u 2 (t) > u 2 (s). The two-element set {s, t} is a farsighted stable set if and only if u 1 (s) < u 1 (t) < u 1 (st) and u 2 (s) < u 2 (t) < u 2 (ts). There are no other farsighted stable sets. 3.

This observation is initially due to Greenberg[START_REF] Greenberg | The theory of social situations: an alternative gametheoretic approach[END_REF] Observation 7.4.2 p. 99.

The existence of myopic stable sets in two-player strategic-form games was initially stated, without characterization, by Greenberg[START_REF] Greenberg | The theory of social situations: an alternative gametheoretic approach[END_REF] Theorem 7.4.5 p. 100.

This result appears as Example 7.4.4 p. 100 in Greenberg[START_REF] Greenberg | The theory of social situations: an alternative gametheoretic approach[END_REF].

The maximal number of singleton farsighted stable sets in 2 × 2 games is 3. We provide an exact list of incompatibilities, establishing when singleton farsighted stable sets can co-exist.

In games where there exists a strategy profile giving to both players higher payoffs than their minmax payoffs, Kawasaki[START_REF] Kawasaki | Maximin, minimax, and von neumann-morgenstern farsighted stable sets[END_REF] obtains a similar result.

Best responses are unique in generic games.

Farsighted cores and stable setsIn this section, we study cores and stable sets with respect to the farsighted dominance relation in strategic-form games.

Note that there is no distinction between weak Pareto dominance and strong Pareto dominance in generic games.

This explains the notation: D stands for "dominated" and U stands for "undominated".

Farsighted stable sets in 2 x 2 gamesIn this section, we provide an exhaustive account of all farsighted stable sets for games with two strategies for each player. Let the strategies be given by S 1 = {s 1 , t 1 }, S 2 = {s 2 , t 2 } and define the strategy profiles s = (s 1 , s 2 ), t = (t 1 , t 2 ), st = (s 1 , t 2 ), and ts = (t 1 , s 2 ). In matrix form, we have[START_REF] John | An equilibrium-point interpretation of stable sets and a proposed alternative definition[END_REF] In fact, this equivalence does not require the block partition property and can also be shown directly. Take any strategy profile t. If u 1 (s) > u 1 (t), construct a farsighted dominance path by first going from t to (u 1 , t 2 ) where (u 1 , t 2 ) is the strategy profile in column t 2 from which there is a farsighted dominance path to s. If u 2 (s) > u 1 (t), construct a farsighted dominance path by first going from t to (t 1 , u 2 ) where (t 1 , u 2 ) is the strategy profile in row t 1 from which there is a farsighted dominance path to s. We are grateful to an anonymous referee for this argument.[START_REF] Herings | Rationalizability for social environments[END_REF] In the proof of Corollary 4.9, we use Lemma 4.5 to establish that if a Nash equilibrium admits a block partition, then U 1 = U 2 = ∅.

A similar construction is used by Banerjee et al.[START_REF] Banerjee | Core in a simple coalition formation game[END_REF] in their Subsection 6.3.

The definition of block partitions and BPP, as well as the proofs of Lemmas 4.2 and 4.5, and Proposition 4.6 are all valid when we allow for pairwise moves.

We are grateful to an anonymous referee for suggesting that we study complexity of searching for SFSS.

Appendix A: Proofs

This appendix contains the proofs of our results.

Proof of Proposition 3.1: A strategy profile (s 1 , s 2 ) is not a Nash equilibrium if and only if it is myopically dominated by at least one adjacent strategy profile. Hence a strategy profile is in the myopic core if and only if it is a pure-strategy Nash equilibrium.

Proof of Theorem 3.6. Necessity. Let Σ ⊂ S 1 × S 2 be a myopic stable set. We first show that Σ cannot contain more than one strategy profile in each row or more than one strategy profile in each column. To see this, let s 1 ∈ S 1 and s 2 , t 2 ∈ S 2 distinct. Then either u 2 (s 1 , s 2 ) > u 2 (s 1 , t 2 ) and (s 1 , s 2 ) (s 1 , t 2 ), or u 2 (s 1 , s 2 ) < u 2 (s 1 , t 2 ) and (s 1 , t 2 ) (s 1 , s 2 ). Thus, including two strategy profiles in the same row violates internal stability. A similar reasoning demonstrates that including two strategy profiles in the same column violates internal stability.

Because Σ satisfies external stability, every strategy profile not in Σ has to be myopically dominated by an element in Σ. This implies that for every strategy profile (s 1 , s 2 ) ∈ S 1 × S 2 \ Σ there exists a profile (s 1 , s2 ) ∈ Σ in the same row or a profile (s 1 , s 2 ) ∈ Σ in the same column. Suppose there is a row s 1 ∈ S 1 in which there is no strategy profile that is in Σ, i.e., (s 1 , s 2 ) ∈ Σ for all s 2 ∈ S 2 . Then for every s 2 ∈ S 2 there must exist a s1 ∈ S 1 \{s 1 } such that (s 1 , s 2 ) ∈ Σ. This implies that |Σ| ≥ n and also, because |S 1 \ {s 1 }| = m -1 and m ≤ n, that there exist two different s 2 , t 2 ∈ S 2 for which the same s1 ∈ S 1 \ {s 1 } satisfies (s 1 , s 2 ) ∈ Σ and (s 1 , t 2 ) ∈ Σ. In other words, there is a row that contains at least two different strategy profiles in Σ. As we have already shown, this would violate internal stability. Thus, we have established that for every s 1 ∈ S 1 there exists a strategy s 2 ∈ S 2 such that (s 1 , s 2 ) ∈ Σ.

We conclude that Σ contains exactly one strategy profile in each row (and |Σ| = m), and no two strategy profiles in Σ are in the same column. We can thus construct a matching µ by matching the pairs (s 1 , s 2 ) ∈ Σ with each other, and matching to itself any s 2 ∈ S 2 that is not represented in Σ. Note that for the matching thus defined it holds that Σ = {(s 1 , µ(s 1 )) | s 1 ∈ S 1 }.

It remains to show that the matching µ is stable. Individual rationality (i.e., µ(s i ) s i s i if µ(s i ) = s i ) is satisfied because by construction remaining single is worse than being matched to any strategy of the other player. To show that there does not exist a blocking pair (i.e., (s 1 , s 2 ) ∈ S 1 ×S 2 such that s 2 s 1 µ(s 1 ) and s 1 s 2 µ(s 2 )), let (s 1 , s 2 ) ∈ S 1 ×S 2 \Σ. By external stability of Σ, there must exist a strategy profile in Σ that myopically dominates Nash equilibrium. Then s 2 s 1 s2 for all s2 ∈ S 2 \ {s 2 } and s 1 s 2 s1 for all s1 ∈ S 1 \{s 1 }. Thus, (s 1 , s 2 ) forms a blocking pair in any matching µ in which s 1 and s 2 are not matched to each other, and such a matching is therefore not stable. 4. This follows from the "Rural Hospital Theorem" (Roth [START_REF] Roth | On the allocation of residents to rural hospitals: a general property of two-sided matching markets[END_REF]). 5. This follows from the "Deferred Acceptance Algorithm" provided in Gale and Shapley [START_REF] Gale | College admissions and the stability of marriage[END_REF], which they show generates a stable matching that among all stable matchings is the best for all m ∈ M when proposals are made by the members of M , and a stable matching that among all stable matchings is the best for all w ∈ W when proposals are made by the members of W .

Proof of Proposition 3.8. We use the results in Banerjee et al. [START_REF] Banerjee | Core in a simple coalition formation game[END_REF] to derive that the auxiliary matching problem associated with G has a unique stable matching µ in which µ(s k 1 ) = s k 2 for each k ∈ {1, . . . , m}. The statement of the proposition then follows by using the correspondence that we established in Theorem 3.6 between myopic stable sets of G and stable matchings in the auxiliary matching problem.

The auxiliary matching problem can be represented as a coalition formation game by defining the "preferences" of a strategy s i ∈ S i over "coalitions" V ⊆ S 1 ∪ S 2 of strategies as follows: {s i , s j } s i {s i , t j } if and only if u j (s i , s j ) > u j (s i , t j ) (j = i), {s i , s j } s i {s i } for all s j ∈ S j (j = i), and {s i } s i V for all for all V ⊆ S 1 ∪ S 2 that contain s i and at least one other strategy, but do not consist of s i and one strategy s j , j = i, (so, all remaining coalitions containing s i ). 13 Banerjee et al. [START_REF] Banerjee | Core in a simple coalition formation game[END_REF] study core partitions, and each core partition of the associated coalition formation game corresponds to a stable matching in the auxiliary matching problem, and vice versa.

Given a non-empty set of strategies

1 to s 1 2 and take these two strategies out of the pool of potential matches.

and take these two strategies also out of the pool of potential matches. Then

, and so on. This procedure stops when the last possible match is made because

The procedure that we have just described mimics the construction in the proof of Banerjee et al. [START_REF] Banerjee | Core in a simple coalition formation game[END_REF]'s Theorem 2 and their proof establishes that the coalition formation game associated with the auxiliary matching problem has a unique core partition. Our proof is completed by noting that core partitions in this coalition formation game correspond to stable matchings in the auxiliary matching problem.

Proof of Proposition 4.1. Because the farsighted core is a subset of the myopic core, by Proposition 3.1, any element of the farsighted core is a purestrategy Nash equilibrium.

We next demonstrate that a Nash equilibrium farsightedly dominates any strategy profile that does not Pareto dominate it. Let (s 1 , s 2 ) be a Nash equilibrium and (t 1 , t 2 ) a strategy profile that does not Pareto dominate it. Then, without loss of generality,

) is a farsighted dominance path, where the validity of the last move follows because (s 1 , s 2 ) is a Nash equilibrium.

We conclude that a Nash equilibrium is farsightedly dominated and is thus not an element of the farsighted core whenever it does not Pareto dominate all other Nash equilibria. Because there can be at most one Nash equilibrium that Pareto dominates all other Nash equilibria, we conclude that the farsighted core cannot contain more than one Nash equilibrium.

Proof of Lemma 4.2.

There is no farsighted dominance path from t to s because u 1 (t) > u 1 (s) and u 2 (t) > u 2 (s) and thus neither player 1 nor player 2 will make the first move away from t with the objective to end up in s.

Proof of Lemma 4.5. Let D 1 , U 1 , D 2 , and U 2 be strategy sets as in BPP for s: s 1 ∈ D 1 and s 2 ∈ D 2 , and all t ∈ D 1 × D 2 \ {s} are farsightedly dominated by s and no other strategy profiles are (i.e., when either t 1 ∈ U 1 or t 2 ∈ U 2 or both).

Because s ∈ D 1 × D 2 and D 1 × D 2 \ {s} consists of exactly those strategy profiles that are farsightedly dominated by s, D 1 and D 2 are uniquely determined. Then U 1 = S 1 \ D 1 and U 2 = S 2 \ D 2 are also uniquely determined, and the block partition with respect to s is unique.

and thus there exists a farsighted dominance path (s 1 , t 2 ) -→ (s 1 , s 2 ). If u 1 (t) < u 1 (s), this path can be used to construct a farsighted dominance path (t 1 , t 2 ) → 1 (s 1 , t 2 ) -→ (s 1 , s 2 ) from t to s, contradicting that s does not farsightedly dominate t.

and thus there exists a farsighted dominance path (t 1 , s 2 ) -→ (s 1 , s 2 ). If u 2 (t) < u 2 (s), this path can be used to construct a farsighted dominance path (t 1 , t 2 ) → 2 (t 1 , s 2 ) -→ (s 1 , s 2 ) from t to s, contradicting that s does not farsightedly dominate t.

Proof of Proposition 4.6. We start with U 0 1 = U 0 2 = ∅ and use the following inductive procedure to identify rows and columns to add to the G.

Proof of Theorem 4.8: Sufficiency. Assume that s is Pareto undominated and the block partition with respect to s, which exists (Proposition 4.6) and is unique (Lemma 4.5), satisfies

and all t ∈ S 1 × S 2 \ {s} are farsightedly dominated by s. Thus {s} is a SFSS.

Necessity. Assume that {s} is a singleton farsighted stable set, i.e., s t for all t ∈ S \ {s}. Then it follows from Lemma 4.2 that no t ∈ S can Pareto dominate s. Thus, s is Pareto undominated. By Proposition 4.6, s admits a block partition. Let S 1 = D 1 ∪ U 1 and S 2 = D 2 ∪ U 2 be partitions of the sets of strategy profiles of the two players as in BPP. Suppose t

. Then a farsighted dominance path from t to s, which is in D 1 × D 2 , needs to include at least one move by player 1 from U 1 × D 2 to D 1 × D 2 or one move by player 2 from D 1 × U 2 to D 1 × D 2 . However, such moves cannot be part of a farsighted dominance path ending at s because, by Lemma 4.5, u 1 (t) > u 1 (s) for all (t 1 , t 2 ) ∈ U 1 × D 2 , and u 2 (t) > u 2 (s) for all (t 1 , t 2 ) ∈ D 1 × U 2 . Thus, s does not farsightedly dominate t. Because s t for all t ∈ S \ {s}, it follows that (D

Proof of Corollary 4.9. Since s is Pareto undominated, it admits a block partition (Proposition 4.6). Let S 1 = D 1 ∪ U 1 and S 2 = D 2 ∪ U 2 be partitions of the sets of strategy profiles of the two players as in BPP. Because s is a Nash equilibrium, for every s1 ∈ S 1 \ {s 1 } it holds that u 1 (s 1 , s 2 ) < u 1 (s 1 , s 2 ). In addition, for every s2 ∈ S 2 \{s 2 } it holds that u 2 (s 1 , s2 ) < u 2 (s 1 , s 2 ). Because

Proof of Corollary 4.10. Because s Pareto dominates all other strategy profiles, it is a Nash equilibrium and it is not itself Pareto dominated. By Corollary 4.9 {s} is then a SFSS.

Because s Pareto dominates every other strategy profile, by Lemma 4.2, s is not farsighted dominated by any of those other strategy profile. This means that every farsighted stable set has to include s, but then to satisfy internal stability the set cannot include any other strategy profiles. Thus, {s} is the unique farsighted stable set Proof of Proposition 5.1. First observe that there cannot be a farsighted stable set containing two adjacent strategy profiles. Hence, there is no far-Because t satisfies PU, it admits a block partition (Proposition 4.6). Let D 1 , U 1 , D 2 , and U 2 be the strategy sets as in BPP for t: t 1 ∈ D 1 and t 2 ∈ D 2 , and all r ∈ D 1 × D 2 \ {t} are farsightedly dominated by t and no other strategy profiles are (i.e., when either r 1 ∈ U 1 or r 2 ∈ U 2 or both). Now note that t 2 is player 2's best response to t 1 and thus every strategy profile (t 1 , v 2 ) is farsightedly dominated by t via the one-step path (t 1 , v 2 ) → 2 (t 1 , t 2 ). From this we know that D 2 = S 2 . Now, consider the strategy profile (s 1 , s 2 ) = (s 1 , BR 2 (s 1 )). Because t satisfies PU and u 2 (s 1 , s 2 ) > u 2 (t 1 , t 2 ), we know that u 1 (s 1 , s 2 ) < u 1 (t 1 , t 2 ). It thus follows from Lemma 4.5 that (s 1 , s 2 ) ∈ U 1 × D 2 . Because s 2 ∈ D 2 , we then know that s 1 ∈ D 1 . We have now shown that D 1 = S 1 and D 2 = S 2 , and thus t forms a singleton FSS.

Case 2. Suppose t does not satisfy PU.

Note that because t 2 is player 2's best response to t 1 , it holds that (t 1 , t 2 ) can only be Pareto dominated by a strategy profile in which player 1 plays a strategy different from t 1 . Pick among those strategy profiles that Pareto dominate (t 1 , t 2 ) the (s 1 , v 2 ) that gives player 2 the highest payoff. Note that it is possible that v 2 = t 2 (namely when (s 1 , t 2 ) Pareto dominates (t 1 , t 2 )). Note also that (s 1 , v 2 ) satisfies PU because every strategy profile (s 1 , w 2 ) that gives player 2 a higher payoff cannot Pareto dominate (t 1 , t 2 ) and thus must give player 1 a lower payoff than (t 1 , t 2 ), so that u 1 (s 1 , w 2 ) < u 1 (t 1 , t 2 ) < u 1 (s 1 , v 2 ) (where the last step follows because (s 1 , v 2 ) Pareto dominates (t 1 , t 2 )). Because (s 1 , v 2 ) satisfies PU, it admits a block partition (Proposition 4.6).

Case 2.1. If there exists a strategy w 2 such that u

Because in a generic game we can only have equality when the strategy profiles are identical, u 2 (s 1 , w 2 ) = u 2 (s 1 , v 2 ) captures the case when w 2 = v 2 , and u 1 (t 1 , w 2 ) = u 1 (s 1 , v 2 ) holds for all w 2 . Let w 2 be a strategy such that

We will first show that there is a farsighted dominance path to (s 1 , v 2 ) from any strategy profile (t 1 , r 2 ) in row t 1 . Let r 2 be an arbitrary strategy for player 2 and consider the path (t

We check all three moves on this path to verify that it is a farsighted dominance path. Because of the choice of w 2 , we know that u 2 (s 1 , w 2 ) ≤ u 2 (s 1 , v 2 ) (with strict inequality when w 2 = v 2 ) and u 1 (t 1 , w 2 ) < u 1 (s 1 , v 2 ). Further, because (s 1 , v 2 ) Pareto dominates (t 1 , t 2 ), we know that u 2 (t 1 , t 2 ) < u 2 (s 1 , v 2 ), and by definition of (t 1 , t 2 ) we know that u 2 (t 1 , r 2 ) ≤ u 2 (t 1 , t 2 ) (with strict inequality when r 2 = t 2 ). Thus, u 2 (t 1 , r 2 ) < u 2 (s 1 , v 2 ).

Appendix B: Complexity of checking SFSS

This appendix discusses the complexity of checking that a strategy profile s is a SFSS. 17 To measure the complexity, we construct a directed graph, called the covering graph of s, as follows. Let the vertices be the strategy profiles (t 1 , t 2 ). We first draw an edge from (t 1 , t 2 ) to (v 1 , t 2 ) whenever u 1 (s) > u 1 (t 1 , t 2 ) and an edge from (t 1 , t 2 ) to (t 1 , v 2 ) whenever u 2 (s) > u 2 (t 1 , t 2 ). These edges correspond to possible steps on indirect dominance paths leading to the strategy profile s. Next, reverse the direction of the edges to construct instead the set of indirect covering paths starting from the strategy profile s.

Checking that s is a SFSS reduces to checking that s is a mother vertex of the covering graph, namely that any other strategy profile can be covered by s. Checking that there exists, in every row and every column, a strategy profile that is farsightedly dominated by s, reduces to checking that s covers a strategy profile in every row and every column in the covering graph. In order to compute the time complexity of the two problems, we compute the number of steps needed to search the graphs in the worst case scenario using a Depth First Search (DFS) or Breadth First Search (BFS) algorithm. For some games, the complexity of checking that s is a SFSS can be vastly reduced, as illustrated in the following example. We consider the Pareto undominated strategy profile s = (R1, C3). This profile is not a Nash equilibrium and it also does not Pareto dominate all other strategy profiles. We use the schematic representation that we introduced in Example 4.7: For every profile t = (t 1 , t 2 ) = s, put a vertical line | in the corresponding cell iff u 1 (t) < u 1 (s) and put a horizontal line -in the corresponding cell iff u 2 (t) < u 2 (s). We obtain ,C3). In the worst case scenario, the DFS algorithm needs to check 16 edges and store 9 vertices (25 steps) to prove that (R1, C3) is a mother vertex. The BFS algorithm needs to check 14 edges and store 9 vertices (23 steps) in the worst case scenario. On the other hand, in order to prove that there is a path from (R1, C3) to any row and any column, it suffices to check that there is a path from (R1, C3) to (R1, C1), (R1, C2), (R2, C1) and (R3, C1). Using the BFS or DFS algorithm, this requires, in the worst case scenario, to check 6 edges and store 5 vertices (11 steps), which is a much lower number.

The example can easily be extended to square n × n games by considering games for which vertical lines appear in column (C1), and horizontal lines in every other column. Every vertex will be connected on average to n edges: all ) in game G2. In the worst case scenario, both the DFS and BFS algorithms need to check 13 edges and store 9 vertices (22 steps) to prove that (R1, C3) is a mother vertex. In order to prove that there is a path from (R1, C3) to any row and any column, one needs to establish the existence of a path from (R1, C3) to a strategy profile in the first column, which requires to check at worst 8 edges and store 7 variables (15 steps) both with BFS and DFS.

The example can be extended to square n×n games, by considering games for which row R1 contains only vertical lines; each row Rk = R2, .., R(n -1) contains vertical lines for all vertices except (Rk, C(n-k+1)), which contains a horizontal line; and row Rn contains horizontal lines for all vertices except (Rn, C2), which contains a vertical line. In this game, the distance between s and the vertices in column C1 is at least as large as the distance to any other vertex. The time complexity of checking that s is a mother vertex is the same as the time complexity of checking that there is a path from s to any vertex in the first column, and is equal to O(n 3 ) for both search algorithms.