Abstract
We propose a new notion of farsighted pairwise stability for dynamic network formation which includes two notable features: consideration of intermediate payoffs and cautiousness. This differs from existing concepts which typically consider either only immediate or final payoffs, and which often require that players are optimistic in any environment without full communication and commitment. For arbitrary (and possibly heterogeneous) preferences over the process of network formation, a nonempty cautious path stable set of networks always exists. Furthermore, some general relationships exist between cautious path stability and other farsighted concepts.
This is a preview of subscription content, access via your institution.
Notes
 1.
Pairwise stable network, PWS (Jackson and Wolinsky 1996), pairwise myopically stable set, PWMS (Herings et al. 2009) and their refinements (Jackson and Van den Nouweland 2005). Also, see Demuynck et al. (2019) for a concept of myopic stable set that generalizes stability concepts in various applications of coalition formation.
 2.
Von Neumann–Morgenstern pairwise farsightedly stable set, vNMFS, largest pairwise consistent set, LPWC (von Neumann and Morgenstern 1944; Chwe 1994; Herings et al. 2009), pairwise farsightedly stable set, PWFS (Herings et al. 2009) and largest farsightedly consistent set, LFC (Page et al. 2005). In addition, Dutta et al. (2005) studies a network formation game where players’ preferences are defined by exponentially discounted infinite payoff streams. But their approach to modeling network formation is very different from our cooperative pairwise approach: it is closer in spirit to noncooperative game theoretic models and imposes much greater structure on the process of network formation. In fact, the paper focuses on the existence and properties of the process of network formation, rather than the outcome, and does not allow for arbitrary and heterogeneous preferences.
 3.
 4.
Two alternative approaches are explicitly modeling a network formation game and using noncooperative equilibrium concepts, or considering deviating coalitions of more than two players. Examples of the former include Myerson (1991), Bloch (1996), Bala and Goyal (2000), Jackson and Watts (2002b), Hojman and Szeidl (2008), Granot and Hanany (2016). Examples of the latter, with considerations of farsightedness, include Aumann and Myerson (1988), Chwe (1994), Xue (1998), Herings et al. (2004), Mauleon and Vannetelbosch (2004), Page et al. (2005), Page and Wooders (2009), Ray and Vohra (2015), Bloch and van den Nouweland (2017), Ray and Vohra (2019). See Ray and Vohra (2014) for a survey.
 5.
Similarly, on the farsighted improving path defined by Herings et al. (2009) (and underlying the concepts of PWFS, vNMFS, LPWC) players compare the payoff in the final network of the path with the payoff in the current network.
 6.
From the discussion at the beginning of Sect. 3.4 it follows that even if the last network of a surely improving path does not belong to G, players that make changes on the path do, in fact, take into account all possible improving continuations of this path that lead to G.
 7.
This brings our approach closer to earlier definitions of farsighted improving paths (or farsighted objection paths) underlying the concepts of PWFS, vNMFS, LPWC: by comparing the current and terminal networks of a path, they implicitly assume that the status quo network remains in place forever if a player decides to stay, and the final network of the path is going to last indefinitely if everyone along the path moves.
 8.
Given the difficulty of constructing an absolutely maximal process in their environment, Ray and Vohra (2019) formulate two sufficient conditions for a farsighted set to be absolutely maximal. It is an interesting question for future research to evaluate whether and how these conditions can be adjusted for the setting with path payoffs.
 9.
Dutta et al. (2005), that is briefly discussed in the introduction, is an application of this paper to networks.
 10.
While this does not mean that our concept addresses the issue of “inconsistent expectations” recently raised by Ray and Vohra (2014) and Dutta and Vohra (2017)—players may not share the same expectation about future play in our setting—we claim that this is not critical in a model where there is no specific protocol prescribing which player or pair of players will actually get to make a move in each network, and no possibility for players to fully communicate and commit to that exact player/pair of players making a move. In such case, if multiple players can make an improving change at the same network, and everyone is cautious/pessimistic, then it is reasonable that any player making a change at an earlier step expects that the future active player will be the one that delivers her worst possible outcome. This would give rise to different expectations.
 11.
The proof of Lemma 2 is included in the proof of Lemma 1 and is, therefore, omitted. Indeed, in order to show that \(P^{\prime \prime }\) is a surely improving path in Lemma 1, one needs to verify, in particular, that it is an improving path, and this requires only that the first of the two improving paths is surely improving.
 12.
The definitions of these concepts are provided in Supplementary Appendix D and Table 2.
 13.
Note that while an additional condition of internal stability works in the direction of reducing the set of networks in G, a milder condition that it is a minimal set for which both conditions are satisfied (and not just external stability), tends to increase this set.
 14.
Note that network \(g^{\prime }\) outside G may itself be a part of some other cautious path stable set. However, by simply adding it to set G or replacing g with \(g^{\prime }\), we won’t (or won’t necessarily) obtain a stable set as some of its key properties would be lost: the former would violate minimality of the cautious path stable set, and both the former and the latter may violate internal and external stability.
 15.
In all four games network payoff allocation across players is anonymous, that is, payoffs depend only on players’ positions in the network, and not on their label.
 16.
It is easy to show that the same stability predictions result from path payoffs that are consistent with staying in the last network indefinitely: the sum of exponentially discounted network payoffs when \(\frac{1}{9}\le \delta <1\) (so that \(\frac{22}{1\delta }\ge 24+\frac{6\delta }{1\delta }\)), or payoffs as in examples (a)–(c) of Sect. 3.3, where only \(k\ge 2\) first networks matter (and \(0<\alpha \le 8/9\) in (c) so that \(22\ge 24\alpha +6(1\alpha )\)).
 17.
The stability of 2link networks according to the LPWC set but not according to our concept bears on the fact that payoffs in intermediate networks on a path matter for players in our setting but not in the definition of the LPWC set. A more detailed explanation is provided in the Supplementary Appendix where the concept of the LPWC set is defined.
 18.
A recent paper by Herings et al. (2017) allows for the interaction between myopic and farsighted players in onetoone matching problems.
 19.
For formal definitions of these concepts see Supplementary Appendix D.
 20.
More formally, by definition of the PWFS set, being in a network inside G means that players do not have incentives to deviate to a network outside G as after such a deviation, there exists a farsighted improving path that leads back to G and makes these players worse off or equally well off. On the other hand, being in a network outside G means that there exists some farsighted improving path that leads to G.
 21.
Such minimal subset of G exists as otherwise we could construct an infinite declining sequence of subsets of G, all satisfying conditions (i) and (ii). This, however, contradicts the fact that G has a finite cardinality.
 22.
We use the notation \(\left( Y_i(g^{\prime }), Y_j(g^{\prime })\right) >\left( Y_i(g), Y_j(g)\right) \) for \(Y_i(g^{\prime })\ge Y_i(g)\) and \(Y_j(g^{\prime })\ge Y_j(g)\) with at least one inequality being strict.
References
Aumann R, Myerson R (1988) Endogenous formation of links between players and coalitions: an application of the Shapley value. The Shapley Value, pp 175–191
Bala V, Goyal S (2000) A noncooperative model of network formation. Econometrica 68(5):1181–1229
Bloch F (1996) Sequential formation of coalitions in games with externalities and fixed payoff division. Games Econ Behav 14(1):90–123
Bloch F, van den Nouweland A (2017) Farsighted stability with heterogeneous expectations. FEEM Working Papers
CalvóArmengol A, Zenou Y (2004) Social networks and crime decisions: the role of social structure in facilitating delinquent behavior*. Int Econ Rev 45(3):939–958
Chwe MSY (1994) Farsighted coalitional stability. J Econ Theory 63(2):299–325
Demuynck T, Herings PJJ, Saulle RD, Seel C (2019) The myopic stable set for social environments. Econometrica 87(1):111–138
Dutta B, Vohra R (2017) Rational expectations and farsighted stability. Theor Econ 12(3):1191–1227
Dutta B, Ghosal S, Ray D (2005) Farsighted network formation. J Econ Theory 122(2):143–164
Ethier WJ (1998) Reciprocity, nondiscrimination, and a multilateral world. University of Pennsylvania, Mimeo
Goyal S, Joshi S (2006) Bilateralism and free trade. Int Econ Rev 47(3):749–778
Granot D, Hanany E (2016) Subgame perfect farsighted stability. mimeo
Herings P, Mauleon A, Vannetelbosch VJ (2004) Rationalizability for social environments. Games Econ Behav 49(1):135–156
Herings P, Mauleon A, Vannetelbosch V (2009) Farsightedly stable networks. Games Econ Behav 67(2):526–541
Herings P, Mauleon A, Vannetelbosch VJ (2014) Stability of networks under levelk farsightedness
Herings PJJ, Mauleon A, Vannetelbosch V (2017) Matching with myopic and farsighted players. Research Memorandum 011, Maastricht University, Graduate School of Business and Economics (GSBE)
Hojman DA, Szeidl A (2008) Core and periphery in networks. J Econ Theory 139(1):295–309
Jackson MO, Van den Nouweland A (2005) Strongly stable networks. Games Econ Behav 51(2):420–444
Jackson MO, Watts A (2002a) The evolution of social and economic networks. J Econ Theory 106(2):265–295
Jackson MO, Watts A (2002b) On the formation of interaction networks in social coordination games. Games Econ Behav 41(2):265–291
Jackson MO, Wolinsky A (1996) A strategic model of social and economic networks. J Econ Theory 71(1):44–74
Jordan JS (2006) Pillage and property. J Econ Theory 131(1):26–44
Karos D, Kasper L (2018) Farsighted rationality. mimeo
Konishi H, Ray D (2003) Coalition formation as a dynamic process. J Econ Theory 110(1):1–41
Mauleon A, Vannetelbosch V (2004) Farsightedness and cautiousness in coalition formation games with positive spillovers. Theory Decis 56(3):291–324
Morbitzer D, Buskens V, Rosenkranz S, Raub W (2014) How farsightedness affects network formation. Analyse Kritik 36(1):103–134
Murnighan JK, Roth AE, Schoumaker F (1988) Risk aversion in bargaining: an experimental study. J Risk Uncertain 1(1):101–124
Myerson RB (1991) Game theory: analysis of conflict. Harvard University
Page FH Jr, Wooders M (2009) Strategic basins of attraction, the path dominance core, and network formation games. Games Econ Behav 66(1):462–487
Page FH Jr, Wooders MH, Kamat S (2005) Networks and farsighted stability. J Econ Theory 120(2):257–269
Ray D, Vohra R (2014) Coalition formation. Handb Game Theory 4:239–326
Ray D, Vohra R (2015) The farsighted stable set. Econometrica 83(3):977–1011
Ray D, Vohra R (2019) Maximality in the farsighted stable set. Econometrica 87(5):1763–1779
Teteryatnikova M, Tremewan J (2019) Myopic and farsighted stability in network formation games: an experimental study. Econ Theory
Tremewan J, Vanberg C (2016) The dynamics of coalition formationa multilateral bargaining experiment with free timing of moves. J Econ Behav Organ 130:33–46
von Neumann J, Morgenstern O (1944) Theory of games and economic behavior. Princeton University Press, Princeton
Xue L (1998) Coalitional stability under perfect foresight. Econ Theory 11(3):603–627
Funding
This study was funded by the Russian Science Foundation (Grant Project No. 184805007).
Author information
Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The author declares that she has no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This paper emerged from a joint project with James Tremewan, “Myopic and Farsighted Stability in Network Formation Games: An Experimental Study”. It would not be possible without James’ feedback and suggestions. I also thank the Associate Editor and anonymous referees, as well as Karl Schlag, Maarten Janssen, Nikita Roketskiy, JeanJacques Herings, Ana Mauleon, Philippe Bich, Xavier Venel, Emily Tanimura, Jacob Goeree, Antonio Cabrales, Martin Cripps, Konrad Mierendorff, Philippe Jehiel, Antonio Guarino, Aniol LlorenteSaguer, Asen Ivanov and participants of the Second Annual NSF Conference on Network Science in Economics (Stanford), Workshop on Networks and Social Norms (Vienna), SAET 2017 (Faro) and seminars at the University of Vienna, University College London, Queen Mary University of London, Higher School of Economics (Moscow) and University of Paris 1 PanthéonSorbonne for helpful comments and suggestions. The research is conducted using the grant from the Russian Science Foundation (Grant Project No. 184805007)
Supplementary Information
Below is the link to the electronic supplementary material.
Appendix
Appendix
Appendix A: Brief description of network stability concepts
See Table 2.
Appendix B: Proofs
Proof of Lemma 1
Suppose \(P=(g_1,..,g_K)\) and \(P^{\prime }=(g_K,..,g_{K+N})\), where \(g_1=g\), \(g_K=g^{\prime }\) and \(g_{K+N}=g^{\prime \prime }\). Let \(P\in P^{SI}(g_1,G)\) and \(P^{\prime }\in P^{SI}(g_K,G^{\prime })\), where \(G\cap G^{\prime }\ne \emptyset \) and \(g_{K+N}\in G\). Consider \(P^{\prime \prime }=P\oplus P_2^{\prime }=(g_1,..,g_K,g_{K+1},..,g_{K+N})\). Below we will show recursively that for any k in the decreasing sequence \(K1, K2,..,1\), the continuation of path \(P^{\prime \prime }\) from step k, \(P^{\prime \prime }_k\), is a surely improving path relative to set \(G^{\prime \prime }\), where \(G^{\prime \prime }\) is any subset of \(G\cap G^{\prime }\). Then, as \(P^{\prime \prime }_1=P^{\prime \prime }\), the last step of the argument will complete the proof.
Consider \(P^{\prime \prime }_{K1}=(g_{K1},g_K,g_{K+1},..,g_{K+N})=(g_{K1})\oplus P^{\prime }\). Suppose that i and j are the players involved in the firststep change on this path, from \(g_{K1}\) to \(g_K\), i.e., \(g_K=g_{K1}+ij\) or \(g_K=g_{K1}ij\). To show that \(P^{\prime \prime }_{K1}\in P^{SI}(g_{K1}, G^{\prime \prime })\), let us first verify that \(P^{\prime \prime }_{K1}\in P^{I}(g_{K1})\). This follows from the fact that \(P^{\prime }\in P^{I}(g_{K})\) by definition, and players i, j prefer path \(P^{\prime }\) to staying in \(g_{K1}\) for \(P^{\prime }\) steps. The latter is an immediate implication of the fact that P is a surely improving path relative to G, so that by definition, for any \({\widetilde{P}}\in P^{I}(g_K)\) leading to G, including the path \(P^{\prime }\), the following inequalities hold: (a) \(\pi _i({\widetilde{P}})\ge \pi _i(g_{K1}^{{\widetilde{P}}})\) and \(\pi _j({\widetilde{P}})\ge \pi _j(g_{K1}^{{\widetilde{P}}})\), with at least one inequality being strict, if \(g_K=g_{K1}+ij\), or (b) \(\pi _i({\widetilde{P}})>\pi _i(g_{K1}^{{\widetilde{P}}})\) if \(g_K=g_{K1}ij\). Now, given that \(P^{\prime }\) is a surely improving path relative to \(G^{\prime }\) and hence, also relative to \(G^{\prime \prime }\subseteq G^{\prime }\), that is, \(P^{\prime }\in P^{SI}(g_K, G^{\prime \prime })\), and inequalities (a), (b) hold for any \({\widetilde{P}}\in P^{I}(g_K)\) that leads to G and hence, also for any improving path that leads to \(G^{\prime \prime }\subseteq G\), it follows that conditions (i) and (ii) of the definition of a surely improving path relative to \(G^{\prime \prime }\) are satisfied for all steps on the path \(P^{\prime \prime }_{K1}=(g_{K1})\oplus P^{\prime }\). Thus, \(P^{\prime \prime }_{K1}\in P^{SI}(g_{K1}, G^{\prime \prime })\).
Next, consider \(P^{\prime \prime }_{K2}=(g_{K2},g_K,g_{K1},g_K,..,g_{K+N})=(g_{K2})\oplus P^{\prime \prime }_{K1}\). By the same argument as before, \(P^{\prime \prime }_{K2}\in P^{SI}(g_{K2},G^{\prime \prime })\). Then by analogy, we can construct a sequence of surely improving paths \(P^{\prime \prime }_{K1}\), \(P^{\prime \prime }_{K2}\), \(P^{\prime \prime }_{K3},..,P^{\prime \prime }_{2}\), \(P^{\prime \prime }\). Thus, \(P^{\prime \prime }\in P^{SI}(g_{1})\), where \(g_1=g\). \(\square \)
Proof of Proposition 2
\((\Rightarrow )\): Suppose that set G is cautious path stable. Then by definition it is a minimal set that satisfies condition (1), and it only remains to verify that it also satisfies condition (2). Suppose that this is not the case, and there exists a pair of networks \(g, g^{\prime }\in G\) such that there is a surely improving path relative to G leading from g to \(g^{\prime }\). Denote this path by P. Below we show that a smaller set \(G^{\prime }=G\setminus \{g\}\) satisfies condition (1). This will contradict the assumption of minimality of set G and thus, complete the proof.
Note that since path P from g to \(g^{\prime }\) is surely improving relative to G, it is also surely improving relative to the smaller set \(G^{\prime }\). The same is true about surely improving paths from other networks outside G, which by condition (1) have at least one surely improving path leading to G. If for some of these other networks, say, network \(g^{\prime \prime }\), a surely improving path to G does not lead to \(G^{\prime }\), then it must be that it leads to g. Denote this path by \({\widetilde{P}}\). So, there exist two surely improving paths relative to \(G^{\prime }\): \({\widetilde{P}}\) that leads from \(g^{\prime \prime }\) to g and P that leads from g to \(g^{\prime }\). Then by Lemma 1, path \({\widetilde{P}}\oplus P_2\) is surely improving relative to \(G^{\prime }\) and it leads to \(G^{\prime }\). Thus, set \(G^{\prime }\) satisfies condition (1) and we arrive at the desired contradiction.
\((\Leftarrow )\): Suppose that set G satisfies the conditions of external stability (1), internal stability (2) and it is also a minimal set that satisfies these both conditions (3). We need to verify that set G is, in fact, a minimal set that satisfies condition (1) alone. Suppose, on the contrary, that there exists a proper subset \(G^{\prime }\subsetneq G\) which also satisfies (1). Below we argue that such smaller set \(G^{\prime }\) either satisfies (2) or contains another proper subset that satisfies both conditions, (1) and (2). In either case, this will contradict the assumed minimality of set G and thus, conclude the proof.
Suppose that \(G^{\prime }\) does not satisfy (2), so that there exists a network \(g^{\prime }\in G^{\prime }\) and path \(P\in P^{SI}(g^{\prime },G^{\prime })\) such that P leads to \(G^{\prime }\setminus \{g^{\prime }\}\). The following algorithm constructs a proper subset of \(G^{\prime }\) that satisfies both, (1) and (2).
Consider \(G_1=G^{\prime }\setminus \{g^{\prime }\}\). \(G_1\) satisfies condition (1). Indeed, from \(g^{\prime }\) there exists a path P leading to \(G_1\) that is surely improving relative to \(G_1\). Similarly, from any other network outside \(G^{\prime }\), which by condition (1) has at least one surely improving path leading to \(G^{\prime }\), this path is also surely improving relative to \(G_1\) and it leads either to \(G_1\) or to \(g^{\prime }\). When the latter is true, so that for some network \(g^{\prime \prime }\) outside \(G_1\) the surely improving path from \(g^{\prime \prime }\) to \(G^{\prime }\) ends at \(g^{\prime }\), then denote this path by \({\widetilde{P}}\) and consider a longer path \({\widetilde{P}}\oplus P_2\). By Lemma 1, this path is surely improving relative to \(G_1\) and it leads to \(G_1\). Thus, \(G_1\) satisfies condition (1).
If \(G_1\) also satisfies condition (2), then we obtain the desired contradiction. If condition (2) is not satisfied, then we reduce the set further by constructing \(G_2=G_1\setminus \{g_1\}\), where \(g_1\) is such a network in \(G_1\) from which there exists a surely improving path relative to \(G_1\) leading to \(G_1\setminus \{g_1\}\). Iterating this reasoning, we can build a decreasing sequence \(\{G_k\}_{k\ge 1}\) of proper subsets of \(G^{\prime }\), satisfying condition (1). As \(G^{\prime }\) has a finite cardinality, and as a set consisting of a single network trivially satisfies condition (2), there exists \(K\ge 1\) such that \(G_K\ne \emptyset \) and satisfies both conditions, (1) and (2). The existence of such set \(G_K\) establishes the desired contradiction. \(\square \)
Proof of Proposition 6
Throughout this proof we will employ the alternative definition of a CFNS, established by Proposition 2, in terms of three conditions: external stability (1), internal stability (2) and minimality with respect to these first two conditions (3).
\((\Rightarrow )\): Let G be CFNS set. Let us verify that conditions (i), (ii) and (iii) of Proposition 6 hold. In fact, it is enough to verify that conditions (i) and (ii) hold, as then (iii) is satisfied, too. Indeed, if (iii) is not satisfied, then there exists a proper subset of G, \(G^{\prime }\subsetneq G\), such that (i) and (ii) hold for \(G^{\prime }\). Consider a minimal among such subsets, i.e., \(G^{\prime }\subsetneq G\) that satisfies all three conditions, (i), (ii) and (iii).^{Footnote 21} But then from the proof of sufficiency \((\Leftarrow )\) it follows that \(G^{\prime }\) must satisfy conditions (1) and (2) of a CFNS set, which contradicts the minimality of the CFNS set G.
So, let us focus on conditions (i) and (ii). Clearly, condition (ii) follows immediately from the definition of a CFNS set. Also, condition (i) is trivially satisfied when G is a singleton, i.e., \(G=\{g\}\). Now, suppose that G contains at least two networks, and condition (i) does not hold. This means that at least one of the two statements, (a) or (b), is true:

(a)
\(\exists g\in G\) and \(ij\notin g\) such that \(g+ij\notin G\), and \(\forall g^{\prime }\in F^{I}(g+ij)\bigcap G\) it holds that \(\left( Y_i(g^{\prime }), Y_j(g^{\prime })\right) >\left( Y_i(g), Y_j(g)\right) \);^{Footnote 22}

(b)
\(\exists g\in G\) and \(ij\in g\) such that \(gij\notin G\), and \(\forall g^{\prime }\in F^{I}(gij)\bigcap G\) it holds that \(Y_i(g^{\prime })>Y_i(g)\).
If (a) is true, then the inequality \(\left( Y_i(g^{\prime }), Y_j(g^{\prime })\right) >\left( Y_i(g), Y_j(g)\right) \) holds, in particular, for \(g^{\prime }={\widetilde{g}}\in F^{SI}(g+ij, G)\bigcap G\). Such network \({\widetilde{g}}\) exists, as \(F^{SI}(g+ij,G)\bigcap G\ne \emptyset \) due to condition (1) of the definition of a CFNS set. Then, as \(\left( Y_i(g^{\prime }), Y_j(g^{\prime })\right) >\left( Y_i(g), Y_j(g)\right) \) holds for any \(g^{\prime }\in F^{I}(g+ij)\bigcap G\), we obtain that a path from g to \(gij\) (one step) and further—along the surely improving path to \({\widetilde{g}}\) is surely improving altogether, that is, \(F^{SI}(g,G)\bigcap G\ne \emptyset \). However, this contradicts the internal stability condition (2) of a CFNS set.
Similarly, if (b) is true, then the inequality \(Y_i(g^{\prime })>Y_i(g)\) holds, in particular, for \({\widetilde{g}}\in F^{SI}(gij,G)\bigcap G\). As before, such network \({\widetilde{g}}\) exists due to condition (1) of the definition of a CFNS set. This, together with the fact that \(Y_i(g^{\prime })>Y_i(g)\) for any \(g^{\prime }\in F^{I}(gij)\bigcap G\), means that \(F^{SI}(g,G)\bigcap G\ne \emptyset \). However, this contradicts the internal stability condition (2) of a CFNS set.
Thus, neither (a) or (b) holds, hence, condition (i) is satisfied.
\((\Leftarrow )\): Suppose that set G is such that conditions (i), (ii) and (iii) of Proposition 6 hold. Let us verify that G is a CFNS set, that is, satisfies conditions (1), (2) and (3). In fact, it is enough to verify conditions (1) and (2), as then (3) follows. Indeed, if not, then there must exist a proper subset of G, \(G^{\prime }\subsetneq G\), such that \(G^{\prime }\) satisfies (1) and (2). But from the proof of necessity \((\Rightarrow )\) we know that conditions (1) and (2) imply (i) and (ii), that is, a proper subset of G, \(G^{\prime }\), must satisfy (i) and (ii). This, however, contradicts the minimality of set G established by condition (iii).
Let us focus on conditions (1) and (2). Condition (1) is trivially satisfied, as it is identical to (ii). If condition (2) is also satisfied, then the proof is completed. Note that this is trivially the case when G is a singleton. Suppose now that set G contains at least two networks, i.e., \(G\ge 2\), and condition (2) is not satisfied. This means that there exists a pair of networks \(g,g^{\prime }\in G\) such that there is a surely improving path relative to G that leads from g to \(g^{\prime }\). We claim that this violates condition (iii) of minimality in Proposition 6.
Claim: There exists \(G^{\prime }\subsetneq G\) that satisfies conditions (i) and (ii).
Let us construct this set \(G^{\prime }\). Consider \(G_1=G\setminus \{g\}\). Note that \(G_1\ge 1\) as \(G\ge 2\). \(G_1\) satisfies condition (ii). Indeed, a path from g to \(g^{\prime }\in G_1\) that is surely improving relative to G is also surely improving relative to the subset \(G_1\). Also, surely improving paths from other networks outside G leading to G are surely improving relative to \(G_1\). Note that such surely improving paths from other networks outside G exist since set G satisfies condition (ii). If for some of these other networks, say, network \(g^{\prime \prime }\), a surely improving path to G does not lead to \(G_1\), then it must be that it leads to g. Thus, we have two surely improving paths relative to \(G_1\): one that leads from \(g^{\prime \prime }\) to g and another that leads from g to \(g^{\prime }\). By Lemma 1, the concatenation of these two paths produces a surely improving path path relative to \(G_1\), and it leads to \(G_1\). Thus, \(G_1\) satisfies (ii).
Now, if \(G_1\) also satisfies (i), then the proof is completed. Note that this is trivially the case when \(G_1\) is a singleton. So, suppose that \(G_1\ge 2\), and condition (i) is not satisfied. This means that at least one of the two statements, (a) or (b), is true:

(a)
\(\exists g_1\in G_1\) and \(ij\notin g_1\) such that \(g_1+ij\notin G_1\), and \(\forall g_1^{\prime }\in F^{I}(g_1+ij)\bigcap G_1\) it holds that \(\left( Y_i(g_1^{\prime }), Y_j(g_1^{\prime })\right) >\left( Y_i(g_1), Y_j(g_1)\right) \);

(b)
\(\exists g_1\in G_1\) and \(ij\in g_1\) such that \(g_1ij\notin G_1\), and \(\forall g_1^{\prime }\in F^{I}(g_1ij)\bigcap G_1\) it holds that \(Y_i(g_1^{\prime })>Y_i(g_1)\).
In particular, the above is true for \(g_1^{\prime }={\widetilde{g}}\in F^{SI}(g_1\pm ij,G_1)\bigcap G_1\), where \(g_1\) satisfies either (a) or (b). Such network \({\widetilde{g}}\) exists due to the fact that \(G_1\) satisfies (ii). This, together with the fact that the payoffs of i and j improve at any \(g_1^{\prime }\in F^{I}(g_1\pm ij)\bigcap G_1\) (i.e., the step from \(g_1\) to \(g_1\pm ij\) is surely improving), means that there is a surely improving path relative to \(G_1\) from \(g_1\) to \({\widetilde{g}}\): \(F^{SI}(g_1,G_1)\bigcap G_1\ne \emptyset \).
Let us define \(G_2=G_1\setminus \{g_1\}\). \(G_2\ge 1\) as \(G_1\ge 2\). Repeating the same argument as before, but with respect to \(G_2\) instead of \(G_1\), we can show that \(G_2\) satisfies condition (ii). If it also satisfies condition (i), then the proof is completed; otherwise, we construct \(G_3\), etc. Iterating this reasoning, we can construct a decreasing sequence \(\{G_k\}_{k\ge 1}\) of proper subsets of G, each satisfying condition (ii). As G has a finite cardinality, and as a set consisting of a single network trivially satisfies condition (i), there exists \(K\ge 1\) such that \(G_K\ne \emptyset \) and satisfies both conditions, (i) and (ii). Denoting this set \(G_K\) by \(G^{\prime }\), we complete the proof of the claim, and of the proposition. \(\square \)
Proof of Proposition 7
Below we prove each of the two statements in turn.

1.
To start with, observe that for any vNMFS set G and any \(g\in G\), there are no surely improving paths relative to G that start at g (and lead anywhere in \({\mathbb {G}}\)), i.e., \(F^{SI}(g,G)=\emptyset \). Clearly, no surely improving path exists from g to any other network in G, and if there existed a surely improving path from g to some network \(g^{\prime }\) outside G, then by Lemma 2 we would obtain a contradiction to the internal stability of a vNMFS set: by definition of vNMFS set, from any network outside G there exists an improving path to G, and thus, the concatenation of a surely improving path from g to \(g^{\prime }\) and an improving path from \(g^{\prime }\) to G would give an improving path between two networks in G.
We now construct a CFNS set to which a given vNMFS set belongs. Observe that the whole network space \({\mathbb {G}}\) trivially satisfies the external stability condition (1) of Definition 4. If it is also the minimal set that satisfies this condition, then \({\mathbb {G}}\) is CFNS, and the proof is completed. Otherwise, there must exist a network \(g_1 \in {\mathbb {G}}\) from which a surely improving path leads to some other network in \({\mathbb {G}}\): \(F^{SI}(g_1,{\mathbb {G}})\ne \emptyset \). Note that this network \(g_1\) lies outside the vNMFS set G, as for any \(g\in G\), \(F^{SI}(g,{\mathbb {G}})\subseteq F^{SI}(g,G)=\emptyset \).
The smaller set \(G_1={\mathbb {G}}\setminus \{g_1\}\) trivially satisfies the external stability condition. If it is also the minimal set that satisfies this condition, then \(G_1\) is CFNS, and the proof is completed. Otherwise, we reduce the set further by constructing \(G_2=G_1 \setminus \{g_2\}\), where \(g_2\) is such a network in \(G_1\) from which there exists a surely improving path relative to \(G_1\) leading to some other network in \(G_1\): \(F^{SI}(g_2,G_1)\bigcap G_2\ne \emptyset \). Note again, that \(g_2\) does not belong to the vNMFS set G, as for any \(g\in G\), \(F^{SI}(g,G_1)\subseteq F^{SI}(g,G)=\emptyset \). The smaller set \(G_2\) satisfies external stability: a path from \(g_2\) to \(G_2\) that is surely improving relative to \(G_1\) is also surely improving relative to the subset \(G_2\). The same is true about surely improving paths from other networks outside \(G_1\), which at this step is just one network \(g_1\), that was withdrawn first. Note that a surely improving path from that network to \(G_2\) exists: it either leads to \(G_2\) directly or via network \(g_2\), as in the latter case, the concatenation of two surely improving paths—from \(g_1\) to \(g_2\) and from \(g_2\) to \(G_2\)—is surely improving (Lemma 1). If set \(G_2\) is also the minimal set that satisfies external stability, then \(G_2\) is CFNS. Otherwise, we construct a set \(G_3=G_2\setminus \{g_3\}\), etc. Iterating this reasoning, we can build a decreasing sequence \(\{G_k\}_{k\ge 1}\) of proper subsets of \({\mathbb {G}}\) that (a) satisfy the external stability condition (1) of Definition 4, and (b) contain the vNMFS set G (as the networks withdrawn at each step lie outside the vNMFS set G). As \({\mathbb {G}}\) has a finite cardinality, and as the vNMFS set G cannot be reduced further, there exists \(K\ge 1\) such that \(G_K\) is CFNS and \(G\subseteq G_K\). This proves the first part of the first statement.
The second part follows from the observation that the existence of a CFNS set \(G^{**}\) such that \(G^{**} \subset G\) would imply that \(G^{**}\) is a strict subset of another CFNS set that contains G. This is however a contradiction to the minimality of a CFNS set.

2.
For the second statement, observe that any CFNS set \(G^{*}\) satisfies conditions (i) and (ii) in the definition of the PWFS set, as condition (i) is identical to the one of Proposition 6 and condition (ii) is weaker than the corresponding external stability condition of Proposition 6. If \(G^{*}\) also satisfies the minimality condition (iii) of PWFS, then it is PWFS. Otherwise, there exists a proper subset of \(G^{*}\) that satisfies all three conditions and is thus PWFS. Indeed, as the cardinality of \(G^{*}\) is finite, the sequence of nested subsets of \(G^{*}\), each satisfying (i) and (ii), is finite, and the last, “smallest” subset in this sequence is minimal.
To prove that no PWFS set contains a CFNS set as a strict subset, observe that the existence of such PWFS set, say \(G^{\prime }\), would imply that \(G\subset G^{\prime }\), where set G is also PWFS. However, this is ruled out by minimality of a PWFS set.
\(\square \)
Proof of Proposition 8
First, from the external stability of a CFNS set it follows that \(\forall \) \(g^{\prime }\in {\mathbb {G}}\setminus G\) \(F^{I}(g^{\prime })\bigcap G\ne \emptyset \). This, together with the fact that \(\forall g\in G\) \(F^{I}(g)\bigcap G=\emptyset \), implies that G is a vNMFS set by definition and a PWFS set by Theorem 3 of Herings et al. (2009).
If in addition \(F^{I}(g)=\emptyset \), then the external stability condition in the definition of all concepts (CFNS, PWFS and vNMFS) implies that G must be a subset of any stable set. Then by minimality, also present in each definition, G is the unique CFNS, PWFS and vNMFS set. \(\square \)
Proof of Proposition 9
Suppose that \(G^{*}\) is a CFNS set. Below we show that \(G^{*}\) satisfies the definition of a pairwise consistent set (see Definition 5 in the Supplementary Appendix), i.e., \(\forall g\in G^{*}\), both external and internal pairwise deviations are deterred. The deterrence of external deviations is already established by condition (i) of Proposition 6. Now, we verify that \(\forall g\in G^{*}\) an internal deviation to a network \(g\pm ij\in G^{*}\) is also deterred as it results in lower or equal payoff(s) either immediately or at the end of some credible improving path starting at \(g\pm ij\).
Suppose that this is not the case and there exist \(g\in G^{*}\) and an internal deviation to \(g\pm ij\in G^{*}\) such that both, immediate payoff(s) and payoff(s) at the end of all credible improving paths from \(g\pm ij\) (if any) improve. Formally this means that at least one of the conditions holds:

(a)
\(\exists ij\notin g\) such that for \(g^{\prime }=g+ij\in G\) and \(\forall g^{\prime }\in F^{I}(g+ij)\bigcap G^{*}\) it holds that \(\left( Y_i(g^{\prime }), Y_j(g^{\prime })\right) >\left( Y_i(g), Y_j(g)\right) \);

(b)
\(\exists ij\in g\) such that for \(g^{\prime }=gij\in G\) and \(\forall g^{\prime }\in F^{I}(gij)\bigcap G^{*}\) it holds that \(Y_i(g^{\prime })>Y_i(g)\).
We obtain that a onestep path from g to \(g+ ij\) in case (a) and from g to \(gij\) in case (b) is surely improving relative to \(G^{*}\). But this contradicts the internal stability of a CFNS set. \(\square \)
Rights and permissions
About this article
Cite this article
Teteryatnikova, M. Cautious farsighted stability in network formation games with streams of payoffs. Int J Game Theory (2021). https://doi.org/10.1007/s00182021007713
Accepted:
Published:
Keywords
 Network stability
 Farsighted and cautious players
 Improving paths
 Heterogeneous preferences
JEL Classification
 D85
 A14
 C71