Coalition formation and history dependence

Dutta, Bhaskar; Vartiainen, Hannu Article Coalition formation and history dependence Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Dutta, Bhaskar; Vartiainen, Hannu (2020) : Coalition formation and history dependence, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 15, Iss. 1, pp. 159-197, https://doi.org/10.3982/TE2947 This Version is available at: https://hdl.handle.net/10419/217084 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Theoretical Economics 15 (2020), 159–197 1555-7561/20200159 Coalition formation and history dependence Bhaskar Dutta Department of Economics, University of Warwick and Department of Economics, Ashoka University Hannu Vartiainen Faculty of Social Sciences, University of Helsinki and Helsinki Graduate School of Economics Farsighted formulations of coalitional formation, for instance, by Harsanyi and Ray and Vohra, have typically been based on the von Neumann–Morgenstern stable set. These farsighted stable sets use a notion of indirect dominance in which an outcome can be dominated by a chain of coalitional “moves” in which each coalition that is involved in the sequence eventually stands to gain. Dutta and Vohra point out that these solution concepts do not require coalitions to make optimal moves. Hence, these solution concepts can yield unreasonable predictions. Dutta and Vohra restricted coalitions to hold common, history-independent expectations that incorporate optimality regarding the continuation path. This paper extends the Dutta–Vohra analysis by allowing for history-dependent expectations. The paper provides characterization results for two solution concepts that correspond to two versions of optimality. It demonstrates the power of history dependence by establishing nonemptyness results for all finite games as well as transferable utility partition function games. The paper also provides partial comparisons of the solution concepts to other solutions. Keywords. Coalition formation, farsightedness, vNM stable set, history dependence, maximality. JEL classification. C71. 1. Introduction The von Neumann–Morgenstern (vNM) stable set has had a distinguished standing as a solution concept in cooperative game theory. It is based on the notion of coalitional dominance, with one social state ydominating state xif some coalition has the power or ability to change the state from xto yand all members of the coalition prefer yto x. von Neumann and Morgenstern identified a stable set as one that satisfies two properties: (i) internal stability, in the sense that no stable outcome dominates any other stable outcome, and (ii) external stability, in the sense that every outcome not in the staBhaskar Dutta: [email protected] Hannu Vartiainen: [email protected] The second author gratefully acknowledges the hospitality of Clare Hall and INET at the University of Cambridge. The paper has benefited from comments and discussions with Francis Bloch, Mert Kimya, Debraj Ray, Rajiv Vohra, Hamid Sabourian, and three anonymous referees, as well as comments from seminar participants at the University of Montreal, the Annual Coalitions and Networks Workshop at University of Glasgow, and the Paris School of Economics. ©2020 The Authors. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at http://econtheory.org.https://doi.org/10.3982/TE2947 160 Dutta and Vartiainen Theoretical Economics 15 (2020) ble set is dominated by some stable outcome. Of course, the core, the set of states that are not dominated by any other state, must be contained in any stable set. The predominant position of the vNM stable set is evident from the large literature on this solution concept.1 Both the core and the stable set are myopic solution concepts in the sense that a deviating coalition cares only about the immediate consequence of a deviation. But if coalition Sdecides to change xto ybecause the latter gives strictly higher payoffs to each member of S, it does not ask itself whether yitself is a stable outcome. Conversely, the implicit rationale of the vNM set is that if xis not dominated by any coalition, then xmust be in the solution set, since no coalition objects to it. Harsanyi (1974)criticized the underlying logic by pointing out the following situation. Suppose coalition Shas the power to enforce yfrom x. Suppose also that at least one member of Sdoes not gain from the move to y. Then myopic solution concepts would decree that Swill not, in fact, effect the move from xto y. But now suppose that some state zthat is deemed stable dominates yand all members of Sstrictly prefer zto x. Harsanyi argued that Sshould, in fact, move the state from xto y, expecting the “final” outcome to be z.Inotherwords, a nonmyopic or farsighted approach to coalitional stability negates the logic underlying solution concepts such as the vNM stable set. Following Harsanyi, there has been a large literature on solution concepts that are based on “farsighted” individuals who base their decisions on whether to deviate from the current status not on the immediate consequence of the deviation, but on how they will fare at the “final” outcome following further deviations by other coalitions.2Acommon feature in much of this literature is the absence of any extensive form that specifies the order in which players or coalitions move as well as any prespecified set of terminal states. So farsighted or forward-looking behavior cannot be captured through the use of any reasoning analogous to backward induction. Clearly this approach requires the specification of the final outcome of any sequence of coalitional deviations. Since prespecified terminal outcomes do not exist in this approach, the final outcome must be one from which no coalition wants to deviate. This suggests that the final outcome is one that is “stable.” Then farsightedness essentially requires that a coalition compares the payoffs of its members at the current status quo to what it expects will be their payoffs at the stable outcome that will be reached if the coalition does deviate. But this implies that deciding on the stability of a particular outcome against a sequence of moves requires us to know which other outcomes are stable. This makes the notion of stability circular and suggests the use of a solution concept based on the principles of internal and external stability that underlie the original vNM stable set. Indeed, Harsanyi (1974) and much of the literature in this area after him modified the stable set by allowing for sequences of coalitional moves, so that both internal and external stability are replaced by their farsighted counterparts. 1See Lucas (1992)forasurvey. 2See, for instance, Chwe (1994), Bloch (1996), Ray and Vohra (1997,1999,2015b), Xue (1998), Diamantoudi and Xue (2003), Konishi and Ray (2003), Herings et al. (2004,2009), Anesi (2010), Mauleon et al. (2011), Vartiainen (2011), Anesi and Seidmann (2014), Chander (2015), Kimya (2018), and Dutta and Vohra (2017). Aumann and Myerson (1988) also modeled farsighted behavior, but from a different perspective. Ray and Vohra (2015a) provide an insightful survey of this literature. Theoretical Economics 15 (2020) Coalition formation and history dependence 161 Ray and Vohra (2015a) raised an important issue with much of the literature. They pointed out that the Harsanyi stable set and other variants do not restrict coalitions to make optimal moves. That is, suppose xis the current status quo and coalition S is contemplating a deviation. Then if Shas two possible deviations, with one deviation Pareto-dominating the other, then it should not take the latter move. Moreover, all coalitions that have deviated before Sshould also assume that Swill only take Paretoundominated or maximal moves.3The following comments of Ray and Vohra (2015a) about the existing farsighted solution concepts are instructive: Stable outcomes can be modeled either with optimistic beliefs or conservative beliefs or perhaps some combination of the two. However, this is serious drawback of the blocking approach. They go on to add: A key requirement that is missing in the notion of farsighted blocking, is that of constraining objecting coalitions to make maximal moves (our emphasis) among their profitable alternatives. Dutta and Vohra (2017) (henceforth DV) also point out that farsighted objections as typically modeled also permit coalitions to hold different beliefs about the continuation path of coalitional moves. That is, xmay not be in the farsighted stable set because coalition S1replaces it with y, anticipating a second, and final, move to z. At the same time, another coalition S2may deviate from xto yin the belief that the next (and final move) will be to z(not z). That is, coalitions S1and S2hold different beliefs about the continuation from state y. DV refer to this issue as one of holding consistent beliefs, although they point out that such seemingly inconsistent beliefs may arise because coalitional moves are history-dependent.4 DV incorporated maximality and consistency (or history independence) of beliefs in the notion of farsighted stability. They use the tool of an expectation function,aconcept borrowed from Jordan (2006). In this framework, the expectation function describes the transition from one state to another, as well as the coalition that is supposed to effect the move. Thus, the expectation function represented the commonly held beliefs of all agents about the sequence of coalitional moves, if any, from every state.5The use of a single expectation function immediately incorporates consistency. Importantly, DV assumes that the transition from any state xto another state ydepends only on the current state. Together with the expectation function, each state is then identified with a terminal or stationary outcome that is eventually reached from this state. Using this correspondence, DV define the notion of maximality of an expectation: it is a move that a coalition cannot improve upon given the consequences of the deviation. DV defined two versions of maximality, one demanding that the move is 3See Examples 1and 2in Section 4. 4Notice that in this example, the state yis reached along different histories of past coalitional moves. 5Although there is no extensive form in our framework, the imposition of commonly held beliefs about continuation paths is analogous to that of such beliefs in noncooperative equilibria such as subgame perfection. For an alternative approach, see Bloch and van den Nouweland (2019), who allow individuals to hold different beliefs about the path of future actions. 162 Dutta and Vartiainen Theoretical Economics 15 (2020) maximal for the active coalition and the other that the move is maximal for any relevant coalition. The latter condition implies strong robustness, but may also lead to existence problems. The sets of stationary points of an expectation function that satisfy one or the other notion of maximality as well as farsighted versions of internal and external stability then gave two different solution concepts. DV showed that these solution concepts are very different from the ones defined earlier. The point of departure in this paper is to incorporate history dependence into the DV framework. Formally, this extension implies that a coalitional move may depend on the past history of coalitional moves and not only on the current state. So history dependence permits coalitions to remember which coalitions or individuals have been active and potentially condition their future behavior on past experiences. The dependence of coalitional moves on past history is intuitively appealing. For instance, we are more likely to join groups of individuals with whom we have had a pleasant experience in the past. Correspondingly, we are less likely to associate with individuals who have lost our trust. Allowing agents to have memory is also standard in noncooperative games. Notice that since history independence is a special case of history dependence, the DV solutions remain solutions in our framework. However, as is standard in the noncooperative framework, the introduction of history dependence expands the sets of stable outcomes quite dramatically. In particular, it allows us to prove powerful nonemptyness results: we show that the set of stable outcomes is nonempty in all finite games as well as in all transferable utility partition function games. What is more, the latter result is derived under the strong maximality property of an expectation, implying remarkable robustness of the solution. Apart from expectation functions, a key tool in the paper will be objection paths. An objection path is a finite sequence of coalitional deviations starting from an initial state and ending up in a terminal state, with the property that each coalition in the sequence strictly prefers the terminal state to the state from which it is deviating. In other words, it represents a farsighted objection. We characterize our solution concepts in terms of collections of such objection paths: the terminal states in the appropriate collection will constitute a solution in our framework. While these are not direct characterizations, since the necessary and sufficient conditions are not stated in terms of sets of states,6we show subsequently that even the indirect characterizations are remarkably useful; they are employed extensively in the proofs of the nonemptyness results as well in yielding a very transparent result on the structure of the solution(s). In particular, we show that our solution is always contained in Chwe’s largest consistent set. Since the largest consistent set is viewed as being too permissive, this inclusion result is of some interest. The plan of the paper is as follows. In the next section, we introduce some key concepts. In Section 3, we formally describe the framework introduced by DV and then go on to introduce our solution concepts. We discuss related solution concepts in Section 4. Section 5 contains our main characterization results in terms of objection paths, while 6We also provide an alternative characterization in terms of sets of states for the special class of simple games. Theoretical Economics 15 (2020) Coalition formation and history dependence 163 Section 6 contains the characterization for simple games. An important by-product of the analysis for simple games is that notions of maximality are rendered irrelevant, in a sense to be explained in Section 5. We present two applications of our solution concept in Section 7. These applications demonstrate the importance of history dependence. In Section 8, we discuss some properties of our solution concepts. We go on to present the nonemptyness results in Section 8.WeconcludeinSection 9. 2. The background We consider a general setting, described by an abstract game,(NXEui(·)),whereN is the set of players and Xis the set of outcomes or states. Let Ndenote the set of all nonempty subsets of N.Aneffectivity correspondence,E:X×X→N, specifies the coalitions that have the ability to replace a state with another state: for xy ∈X,E(xy) is the (possibly empty) set of coalitions that can replace xwith y. We sometimes use E(xS) to denote the set of states that coalition Scan induce from x. Finally, ui(x) is the utility of player iat state x. The set of outcomes as well as the effectivity correspondence depend on the specific model that is being studied. For instance, in a partition function game,(Nv), the function vwill specify a real number for each embedded coalition (Sπ),whereπdenotes the coalition structure with S∈πbeing one of the coalitions in the partition π. Feasibility implies that an embedded coalition (S π) can distribute at most v(Sπ) to individuals in S. A state for partition function games refers to a coalition structure πand a corresponding payoff allocation that is feasible and efficient for each embedded coalition corresponding to π. Much of traditional cooperative game theory has focused on the simpler but more restrictive transferable utility characteristic function games in which a coalition can assure itself of a minimum aggregate utility v(S). The dominant tradition in the literature has treated the set of states to be the set of imputations,i.e.thePareto efficient utility profiles in v(N), and implicitly assumed that S∈E(x;y) if and only if yS∈v(S).Ray and Vohra (2015b) provide a convincing critique of why this assumption is unsatisfactory for studying farsightedness. We return to this issue below. State ydominates xif there is S∈E(xy) such that uS(y) uS(x).7In this case we also say that (S y) is an objection to x. The core is the set of all states to which there is no objection. AsetK⊆Xis a vNM stable set if it satisfies the following conditions: •Internal stability.Foranyx∈K, there is no y∈Ksuch that ydominates x. •External stability.Foranyx/∈K,thereisy∈Ksuch that ydominates x. The core and vNM stable set are myopic solution concepts since they are based on single rounds of deviations. So as to introduce farsighted solutions, it is convenient to introduce the concept of objection paths. Definition 1. An objection path is a finite sequence (y0S1y1Smym)such that, for all k=1m,Sk∈E(yk−1yk)and uSk(ym)uSk(yk−1). 7We write uS(y) uS(x) if ui(y) > ui(x) for all i∈S. 164 Dutta and Vartiainen Theoretical Economics 15 (2020) Given the abstract game (NXEui(·)), we denote the set of all objection paths by P∗. We often use P⊆P∗to denote a subset of objection paths and use Pxto denote the set of objection paths in Pwith initial element x.Weusepxto denote a typical objection path in Pxand use μ(p) to denote the terminal state ymin the objection path p=(y0S1y1Smym). State yindirectly dominates xif there is an objection path pxsuch that y=μ(px). Farsighted or indirect domination takes into account forward-looking behavior because at each point in the objection path, the deviating coalition takes into account the utility profile not at the next state in the sequence but at the “final” state in the objection path. Of course, this leaves open the question of how the terminal state is determined. This is going to be a central issue of this paper. The relation of dominance or farsighted dominance depends on the specification of the effectivity function. Ray and Vohra (2015b) point out the importance of imposing appropriate restrictions on the effectivity function in the construction of farsighted solution concepts. In the context of characteristic games, the standard practice allowed a coalition Scomplete freedom to choose even the payoffs to individuals in the complementary coalition N−S. Notice that this does not matter for solution concepts like the core or the vNM stable set, since these are based on myopic deviations: the deviating coalition simply compares its own payoff allocations at the current state and the state following immediately after the deviation.8But why or how can coalition Sdictate either the payoffs accruing to the complementary coalition or how N−Sorganizes itself after S deviates? Of course, this does matter even in characteristic function games, since it may influence what coalitions form along the sequence. Ray and Vohra (2015b)demonstrate that this assumption can significantly alter the nature of the farsighted version of the vNM stable set. They show that imposing reasonable restrictions on the effectivity correspondence results in a farsighted stable set that is very different from that of Harsanyi (1974). We impose the appropriate restrictions on the effectivity function when we apply our solution concept to partition function games and simple games later on. 3. Rational expectations and farsighted solution concepts As we mentioned earlier, DV incorporate both maximality and common beliefs about continuation paths (of coalitional deviations) in their analysis. They use an expectations function to model the transition from one state to another as well as the coalition that is supposed to effect the move. The use of an expectation function to represent the transition from one state to another is adapted from Jordan (2006), who used such a function to represent commonly held beliefs about the transition from any state to the final outcome. The expectation function represents the commonly held beliefs of all agents about the sequence of coalitional moves, if any, from every state. One can then choose to impose restrictions on the expectation function so as to make the function reasonable. An obvious restriction is that the expectation function must be consistent with the under8Note that this aspect of the effectivity function is important even for myopic solution concepts of partition function games, since the deviating coalition has to “predict” what coalition structure will prevail immediately after the deviation, since its aggregate utility depends on what partition forms. Theoretical Economics 15 (2020) Coalition formation and history dependence 165 lying game and, hence, with the effectivity function associated with the game: it cannot specify a move from state xto state yby coalition Sif S/∈E(xy). Another restriction that is desirable is that the expectation function specify moves that are optimal. We describe below slightly different notions of degrees of optimality; each gives rise to a specific restriction on the expectation function. DV assumed that the process of transition is history-independent;thatis,iftheexpectation function specifies a transition from state xto state y,thenitmustdosoirrespective of how state xis reached.9The essential purpose of this paper is to show how the DV analysis can be extended to incorporate history dependence into this transition process. Allowing for history dependence obviously results in a more general framework in which future coalitional moves can, in principle, depend on the evolution of past coalitional moves. There are at least two reasons why this is an interesting exercise. We mentioned earlier that there are a variety of contexts where history does matter. Moreover, from a purely formal perspective, it is well known that history dependence enlarges the set of noncooperative equilibria. In principle, this logic may carry forward to the present context. Indeed, the applications later on illustrate the instrumental importance of history dependence. With this in mind, we define histories more formally. Let x0be an initial status quo. At period t=01, coalition Scan challenge the current state xtby demanding an outcome xt+1such that S∈E(xtxt+1).Insuchacase,xt+1becomes the new status quo at period t+1. If no coalition challenges some state xin period t, then the game terminates and xis implemented. A history is a sequence (x0S1x1Smxm)that specifies the past play path and coalitions that have been active until xmhas been reached. Let H represent the set of all (finite) histories, with a typical element h. For any history h=(x0S1x1Skxk),weuseμ(h) to denote the terminal state xkof h. Notice that all finite histories have well defined terminal states. We use the following notation on concatenation of path. For any history h,(hSx) is the history reached by adding to hthe state xthat is induced by coalition Sfrom the final state μ(h) of h. Note that S∈E(μ(h)x) for this to be valid. Expectation function An expectation is a function F:H→N×X, specifying the active coalition and its move for all possible current states and past histories. The expectation function “predicts” that one coalition is going to be active at any history, without describing any explicit protocol that chooses the active coalition.10 9Note that in our framework, we cannot interpret states as nodes of an extensive form game, since a state can be reached along several different objection paths. 10A referee questioned why only one coalition is assumed to move at any point. Consider an extensive form or game tree that represents a specific protocol that describes the player who moves at any particular node in the tree. The tree also describes the possible paths that may be followed from any given node. Here we have no explicit protocol. The expectation function is supposed to be a formalization of the commonly held beliefs of players about the continuation path from any given state, including the coalition that is supposed to move. Notice that this assumption is implicit in all solution concepts based on objection paths. However, the stronger version of optimality—Condition M* to be defined later—does allow for the possibility that a deviation can come from a coalition that is different from that specified by the expectation function. 166 Dutta and Vartiainen Theoretical Economics 15 (2020) Denote F(h)=(S(h)f(h)),wheref(h)is the state that is expected to follow at history hand S(h) is the coalition expected to induce the next state. If S(h) =∅,thenno coalition wants to change the state and the final state of the history hwill be implemented.11 As usual, history independence is a special case of history dependence. Consider any two histories hh∈H. Then the DV expectation function satisfies F(h) =F(h) whenever μ(h) =μ(h). So the continuation path once a state xis reached does not depend on whether the state was reached via history hor history h. Given an expectation F=(Sf),notethat(hS(h) f (h)) is also a history. We denote F0(h) =h,F1(h) =F(h) and, generally, Fk+1(h) =F(hF0(h)   Fk(h)) for all k=012. Similarly, denote by Sk(h) and fk(h) the first and second components of Fk(h), respectively, so that Fk(h) =(Sk(h) f k(h)) for any k. We say that history his stationary if S(h) =∅.Ifhis stationary, then we also denote by μ(h) the stationary point associated to h. An expectation Fis absorbing if, for every h∈H,thereexistsksuch that Sk(h) =∅. Ahistory(h S1y1Smym)is an indirect objection to hif μ(h)S1y1Smym∈Pμ(h) That is, the new history is formed from hby appending an objection path to it. For an absorbing F,thepathF(h) generated by Ffrom history h, i.e., F(h)=h F1(h) F2(h) has a finite length and μ(F(h)) is well defined for any h. Let F(H) =h∈H{F(h)}denote the sets of possible paths that are generated by an absorbing F, by varying the initial history, and μ(F(H)) the stationary states associated with these paths. Hence, assuming that expectation Fis played in the continuation game, μ(F(H)) is the set of states that can be eventually reached by starting from any initial history. So it makes sense to view μ(F(H)) as a farsighted solution when Fis the function describing the transition from state to state. We now turn to the issue of describing “reasonable” restrictions on F, keeping in mind that these translate into restrictions on μ(F(H)), the set of stationary points. We first describe two restrictions on the expectation Fthat are the farsighted analogues of internal and external stability. Condition I. If his a stationary history, then there does not exist y∈Xand S∈ E(μ(h)y) such that (μ(h) S y ¯ F(hSy))is an objection path. Condition E. If his a nonstationary history, then (μ(h) F(h)) is an objection path. If Condition I is not satisfied, then for some stationary state x, there is a coalition Sthat can deviate, anticipating that the resulting sequence of transitions according to Fwill lead to another stationary state that all members of Sprefer. Clearly, this is a violation of farsighted internal stability. Condition E states that if μ(h) is not a stationary state, then some farsighted objection will result in a stationary state; this is an obvious requirement of farsighted external stability. 11For history-dependent solutions in related contexts, see Vartiainen (2011,2014,2015). Theoretical Economics 15 (2020) Coalition formation and history dependence 173 an equilibrium story of coalition formation. Interestingly, Herings et al. (2004)construct an example in which the LCS excludes too much. Since HREFS is a subset of LCS, it too will exclude too much in this specific example. The solutions discussed so far are all history-independent. We close this section with a couple of examples that illustrate the role of history dependence. Example 4. We have (3,3,3) (0,0,0) (4,4,0) (4,0,4) (0,4,4) a b cde {1,2},{1,3},{2,3} {1,2} {1,3} {2,3} In this example, ais the surplus-maximizing outcome and, hence, the unique socially efficient outcome corresponding to the utilitarian rule. However, none of the history-independent solutions other than the LCS and LCCS can support aas an outcome. All the majority coalitions have profitable deviations from b. History independence means that which coalition moves is independent of previous movements. In particular, punishments are not possible. So whichever coalition(s) is expected to move at bwill also want to move from ato b. So the prediction must be that {cde}(the set of terminal outcomes) constitute the set of stable outcomes. Consider, however, how this prediction changes when history dependence is introduced. Suppose, for instance, that S={12}deviates from ato b. Then one of the players in S,say1, can be punished for the deviation by choosing the continuation path to be {23}moving to e. Clearly, any deviation from acan be punished in this way by making the continuation path from bdependent on the initial deviation from b. Hence, HSREFS and so HREFS will be {a c d e}. Remark 2. In this example, the LCS coincides with HREFS. However, the permissiveness of the LCS can easily be demonstrated by embedding this example in a bigger one as follows. Consider two new alternatives fwith utility vector (11−025)and gwith utility vector (11−05).Let{3}∈E(fb) and {12}∈E(bg).Then3will not deviate 174 Dutta and Vartiainen Theoretical Economics 15 (2020) from fto bunder the pessimistic expectation that {12}might move to gfrom b.However, this is a violation of maximality: the optimal move for {12}from bis to c,whichis better than ffor 3. Finally, history dependence also helps to establish existence of a nonempty solution set in situations where several history-dependent solutions will be empty. One example in which this is the case is the three-player NTU “roommate game” depicted below. Example 5. From every state there is one two-player coalition that gains by moving to another state. It is easy to see that this games possesses no vNM stable set, no farsighted stable set, no ECB, and no REFS. In Section 7 below, we describe two specific examples that illustrate the same general principles outlined here through abstract games. 5. Characterization In this section, we provide characterization results for HREFS and HSREFS of abstract games. Our characterization exercises are not directly in terms of sets of states,butin terms of the terminal states of sets of objection paths. That is, we provide necessary and sufficient conditions so that the terminal states corresponding to any set Pof objection paths will be HREFS (or HSREFS) if and only if Psatisfies these conditions. While we are aware that it may be difficult to check whether a specific subset of states satisfies the necessary and sufficient condition, it is very handy in proving general nonemptyness results: we provide constructive proofs of nonempty HREFS in all finite abstract games as well as a nonempty HSREFS in all superadditive partition function games. The characterization results also throw light on the logical structure of sets of HREFS, including the fact that a largest HREFS exists for all finite games. Finally, the characterization is employed when we analyze the relationship of HREFS and HSREFS to other solution concepts. In particular, the characterization proves useful in showing that every HREFS is a subset of the LCS. Recall that we use px,py, etc. to denote objection paths with initial state x,y.Similarly, given any set of objection paths P,weusePxto denote the subset of objection paths in Pwith initial state x. Definition 5. Let Pbe a collection of objection paths. Theoretical Economics 15 (2020) Coalition formation and history dependence 175 •An objection path p=(x0S1x1) is S1-dominated in Pvia yif S1∈E(x0y) and uS1(μ(py)) uS1(μ(px0)) for all py∈P. •An objection path (x) is S-dominated in Pvia yif S∈E(xy) and uS(μ(py))  uS(x) for all py∈P. That is, an objection path pis dominated via node yin the set Pof paths if the members of the first active coalition profit by directing the play to node yrather than continuing along the path pto the terminal state. Notice that the definition requires that once S1deviates to y, it takes into account the possibility that any objection path in Pwith y as the original state may be followed in the future. Clearly, if this condition is satisfied and S1believes that only the set of paths Pare “possible” paths that can be followed, then it cannot be optimal for S1to move to x1. Part (ii) stipulates that if xis not followed by any other state, i.e., is stationary, then any coalition can dominate it via some yif an analogous condition is satisfied. Definition 6. A collection of objection paths Pis coherent if it satisfies the following statements: (i) Collection Pxis nonempty for all x∈X. (ii) If (x0S1)∈P, then (xkSk+1)∈Pfor all k=01. (iii) If (x0S1)∈P, then (x0S1)is not S1-dominated in P(via any y). (iv) If (x) ∈P, then (x) is not S-dominated in P(via any y) by any S. Remark 3. Suppose μ(p) =xfor some p∈P,wherePis a coherent collection of paths. Then, by part (ii) of Definition 6,(x) ∈P. OurfirsttheoremshowsthatanyHREFSmustbethesetofterminalstatesofacoherent collection of objection paths.18 The first two conditions are obvious. The first condition requires that the set Pmust contain at least one objection path with initial state xfor every state. After all, we must be able to predict what happens starting from any initial state x. The second condition states that if an objection path pis in P, then any objection path that is a subpath of p must also be in P. Conditions (iii) and (iv) are in some sense the two crucial conditions. Suppose condition (iii) is not satisfied by some set P.ThenPmust include an objection path p=(x0S1x1) that is S1-dominated in Pvia some y. This would mean that S1can deviate to yand be assured that all paths in Pymake it strictly better off than following the path p. This implies that S1is not taking a maximal move if it moves from x0to x1. Condition (iv) requires that if (x) is in Pand, hence, xis a terminal state of a path in P, then not deviating from xmust be a maximal move for every coalition. We are going to show that the terminal states of paths in a coherent collection Pconstitute an HREFS. Condition (iv) is required to ensure that Condition I is satisfied. 18Path-based coalitional solutions include Xue (1998), Mariotti (1997), and Kimya (2018). However, as discussed in Section 4, they are based on assumptions that are, in general, not compatible with HREFS and, hence, not directly comparable to coherence. 176 Dutta and Vartiainen Theoretical Economics 15 (2020) Theorem 1. AsetY⊆Xis HREFS if and only if Y≡μ(P) for some coherent collection of objection paths P. The proof of the theorem follows from two lemmas. Lemma 1. Let Fbe a history-dependent, absorbing expectation function that satisfies Conditions I, E, and M. Then F(H) is a coherent collection of objection paths. Proof. Since Fis absorbing, Fconsists of finitely long paths. Moreover, for any nonstationary configuration (h),F(h) is an objection path by Condition E. We now check the defining conditions of a coherent collection of paths. Take any history hsuch that μ(h) =x. First, if S(h) =∅,thenF(h) =(x).IfS(h) = ∅, then, by Condition E, there is S∈ E(xy) such that uS(μ(F(hS y))) uS(x). By construction, F(hSy) ∈F(H).Thus, in all cases, F(h)∈F(H)xfor all x∈X. Second, since F(h)=(F(h)F(h F(h))) and (F(h)F(h F(h)) ∈F(H), it follows by induction that if (x0S1x1)∈F(H), then (xkSk+1)∈F(H) for all k=01. Next suppose that F(h) is S(h)-dominated in F(H) via y.ThenuS(h)(μ(F(hS(h) y))) uS(h)(μ(F(h))). But this violates Condition M. Finally, suppose that F(h) is S-dominated in F(H) via y.ThenuS(μ(F(hSy)))  uS(μ(h)) for some Ssuch that S∈E(μ(h)y). But this violates Condition I. This shows that F(H)satisfies all the four requirements that define a coherent set of objection paths. We now want to prove the converse result: if Pis a coherent collection of objection paths, then the terminal state associated with Pis HREFS. The proof of the claim is constructive: given any coherent set P, we specify an absorbing expectations function that satisfy Conditions I, E, and M. Lemma 2. If Pis any coherent collection of objection paths, then μ(P) is HREFS. Proof. Fix a coherent collection of objection paths Pfor the rest of the proof. Take any path px=(x S1) ∈Pand pair (Sy) such that S∈E(xy) with S=S1if px= (x). Define a function ξwith the property that ξ(px(Sy)) ∈Pand uS(μ(ξ(px(Sy))))  uS(μ(px)) Such a function ξmust exist for each such (px(Sy)) from conditions (iii) and (iv) of Definition 6. Given a coherent collection of objection paths P,wenowconstructahistorydependent and absorbing expectation function FPsuch that μ(F(H))=μ(P). Interpret Pas an index set and let {Hp}p∈Pbe a partition of the set of histories H.We construct FPthat is measurable with respect to this partition so that for each p∈Pand histories h h∈Hp,F(h)=F(h). So each element Hpof the partition of Hcontains all the relevant information concerning the past coalition actions. We specify the partition of Hrecursively. For each x∈μ(P),fromRemark 3, we know that (x) ∈P. For each such x,let(x) ∈H(x). Recursively, take any px0=(x0S1x1)∈ Theoretical Economics 15 (2020) Coalition formation and history dependence 177 Pand h∈Hpx0.LetS∈E(x0y)be such that S=S1if S1= ∅and let (hSy)∈H(x1S2) if (S y) =(S1x1) Hξ(px0(Sy)) if (S y) = (S1x1) Proceeding from the initial history ∅, each element in the set of histories His allocated into exactly one element of {H(x0S1)}(x0S1)∈P.Notethatifh∈H(x0S1),thenμ(h) = x0. Construct now an expectation FPsuch that, for any h∈H(x0S1), FP(h) =(S1x1)if S1= ∅ (∅x0)if S1=∅ First, we check that FPis absorbing. Take any (x0S1) ∈Pand any h∈H(x0S1).ThenFP(h) =F1(h) =(S1x1), FP(hFP(h)) =F2(h) =(S2x2),andsoon. ThusFPcontinues along the path (x0S1 x1S2)∈Puntil a stationary state is reached. Since any objection path is finitely long, Fis absorbing. We now verify the three properties of a rational expectation. Condition I. Suppose that his a terminal history. Then h∈H(μ(h)).Considery such that S∈E(μ(h)y).Then(hSy) ∈Hξ((μ(h)(Sy)). By the construction of FP, (y F1(hSy)F2(hSy))=ξ((μ(h)) (S y)). By the definition of ξ,uS(μ(ξ(μ(h) y)))  uS(μ(h)). Condition E. Suppose that his a nonterminal history. Find the path (x0S1)∈P such that h∈H(x0S1). By the construction of FP,(F1(h)F2(h)) =(S1x1S2). Since (x0S1x1S2) is a finitely long objection path, the continuation play leads to a terminal history (h F1(h)F2(h)) =(hx0S1), which is an indirect objection to h. Condition M. Suppose that his a nonterminal history. Find the path (x0S1)∈P such that h∈H(x0S1).Thenx0=μ(h).Takeanyysuch that S1∈E(x0y).Bytheconstruction of FP,(y F1(hSy)F2(hSy))=ξ((x0S1   ) (S y)). By the definition of ξ,uS1(μ(ξ((x0S1   ) (S y))))  uS1(μ((x0S1))). This completes the proof of the lemma. Lemmas 1and 2prove Theorem 1. Of course, neither the theorem nor the lemmas throws any light on the existence of a coherent collection of paths or how such a set can be identified if it exists. The following example demonstrates that the rudimentary structure of the abstract game does not itself guarantee the existence of a coherent collection of paths and, hence, a HREFS. 178 Dutta and Vartiainen Theoretical Economics 15 (2020) Consider a one agent N={1}decision problem with X=(−10),andwhere{1}∈ E(xy) if and only if y=x/2.Letu1(x) =xfor all x∈X. Now any (trivial) objection path (x) except (0)is dominated via x/2. Hence, the only candidate for the HREFS is {0}. But there is no finite objection path that initiates from any xand ends in 0.Hence, Definition 6(i) is violated by any collection of paths, and there cannot be any HREFS. Our objective is to prove the existence of HREFS in a large and natural class of games. We will, in fact, provide a sufficient condition for a stronger version of the solution, HSREFS. To this end, we define a stronger version of coherence. Definition 7. A collection of objection paths Pis strongly coherent if the following conditions are satisfied: (i) The collection Pxis nonempty for all x∈X. (ii) If (x0S1)∈P, then (xkSk+1)∈Pfor all k=01. (iii) If (x0S1)∈P, then (x0S1) is not S-dominated in P(via any y) for any S such that S1∩S= ∅. (iv) If (x) ∈P, then (x) is not S-dominated in P(via any y) for any S. So strong coherence strengthens Definition 6(iii), all other requirements being the same as for coherence. The strengthening involves ensuring that any coalition with a nonempty intersection with S1shouldnotwanttodeviate. Theorem 2. If Pis a strongly coherent collection of objection paths, then μ(P) is HSREFS. Proof.LetPbe some strongly coherent collection of objection paths. We construct an HSRE FPsuch that F(H)=P. Identify a function ξthat is defined for each pair ((x0S1 )(Sy)) such that (x0S1)∈Pand S∈E(x0y)with S1∩S= ∅if S1= ∅.Thenξis defined by the property that ξ((x0S1   ) (S y)) ∈Pyand uSμξ(x0S1   ) (S y) uSμ(x0S1) for any pair (x0S1)(Sy) Since Psatisfies Definition 7, such a function ξdoes exist. As before, interpret a strong coherent path structure Pas an index set and let {Hp}p∈Pbe a partition of the set of histories H.WeconstructFthat is measurable with respect to this partition. We specify the partition of Hrecursively. As before, let (x∅)∈Hxfor all x∈μ(P). For any history h, find (x0S1)∈Psuch that h∈H(x0S1).ForanySand ysuch that S∈E(x0y)and such that S1∩S= ∅,ifS1= ∅,let (hSy)∈H(x1S2) if (S y) =(S1x1) Hξ((x0S1)(Sy)) if (Sy) = (S1x1) Theoretical Economics 15 (2020) Coalition formation and history dependence 179 Then each element in the set of histories His allocated into exactly one component of the partition {Hp}p∈P. Note that, by construction, μ(h) =x0for all h∈H(x0S1). Construct now an expectation Fsuch that, for any h∈H(x0S1), FP(h) =(S1x1)if S1= ∅ (∅x0)if S1=∅ It suffices to verify Condition M*, since the rest of the proof is identical to that of Lemma 2. Suppose that his a nonstationary history. Find the path (x0S1) ∈P such that h∈H(x0S1).Thenx0=μ(h).TakeanySand ysuch that S∈E(x0y) and such that S1∩S= ∅. By the construction of FP,(y F1(hSy)F2(hSy))= ξ((x0S1 )(Sy)). By the definition of ξ,uS(μ(ξ((x0S1)(Sy))))  uS(μ((x0 S1))). We use these characterization theorems repeatedly in subsequent sections. In particular, we use Theorem 2 to construct nonempty HSREFS in all superadditive transferable utility partition games as well as nonempty HREFS in all finite games. 6. Simple games In this section, the focus is on the class of NTU simple games,whichweformalizebya nonempty set Wof winning coalitions and the set of states X.Von Neumann and Morgenstern (1944) described simple games by a characteristic function vsuch that v(S) =1 if S∈Wand v(S) =0otherwise.19 Of course, this assumes that utility is transferable and winning brings the same aggregate benefit to the winning coalition. We use a different formalization of simple games, motivated at least partly by the kind of contexts that are typically mentioned as potential applications of simple games. Consider, for instance, a legislature that has to choose whether to pass a bill along with a set of possible amendments. Alternatively, consider a committee voting on an up-or-down decision. In such cases, the rules of the legislature or the committee specify what groups of individuals are decisive (or winning) in the sense of being able to make decisions, and so the simple game structure in terms of winning coalitions seems appropriate. However, it is somewhat inappropriate to assume either that utility is transferable or that the final decision or outcome brings the same aggregate benefit to the group whose vote wins the day. Our formulation preserves the essential structure of simple games, so that winning coalitions can enforce any outcome, but drops the assumption that aggregate benefits are equal no matter the outcome that is chosen, and also transferability of utility. Our focus is on monotonic and proper simple games, such that (i) if S∈W,andS⊂T, then T∈W20 (ii) if S∈W, then N−S/∈Wfor all S⊆N. 19Farsightedness for this class of simple games was studied by both Ray and Vohra (2015b)aswellasDV (2017). 20So N∈W. 180 Dutta and Vartiainen Theoretical Economics 15 (2020) Given W, a coalition Bis a blocking coalition if N−Bis not a winning coalition. Let Bdenote the set of blocking coalitions. A coalition is a losing coalition if its complement in Nis a winning coalition. In this section, we explicitly assume that a state consists of an outcome afrom some feasible set A(for instance, the set of legislative bills) as well as a partition πof N.That is, any state xis a pair (a π) and X=A×. Of course, a winning coalition may not form. In such cases, we assume that the outcome will be a distinguished element a0(the status quo), which is also in A.WeuseX0to denote the set of “zero” states in which no winning coalition has formed, so that a typical element of X0will be x0=(a0π),with no element of πbeing in W. We assume that each individual ihas a utility function defined over Aand that ui(aπ) =ui(a) for all i∈N(aπ)∈X That is, individuals care only about the bill that is passed or the decision that is taken by the committee and not about the partition that represents the voting choices. In a simple game, a winning coalition has the power to choose any outcome in A, while a blocking coalition can ensure that the status quo a0is the resulting outcome. The only way in which a losing coalition Tcan change the utility allocation is if Tleaves a winning coalition Sand S−Tis not a winning coalition. So, for instance suppose |N|=5 and any coalition of three or more is a winning coalition. Let π={{123}{4}{5}}.Then any i∈{123}can leave the coalition and ensure that a zero state emerges. Alternatively, if π={{1234}{5}}, then no singleton has any power to change the outcome. This illustrates the limitations on the power of losing coalitions: if Lis a losing coalition that is a subset of a winning coalition S,thenLcan change the outcome to a0if and only if S−Lis not winning. So as to express these ideas formally, we use the following notation. For any partition πand coalition S⊂N,let(S πS)∈represent the partition where Sis an element of the partition and T∈πSif and only if T=R−Sfor some R∈π. That is, if a coalition Sforms and deviates from π, then the new partition consists of Sand all original elements of π without members of S.Wealsouse(S π−S)to denote the partition with Sas an element and some partition π−Sof N−S. The power of winning, blocking, and losing coalitions is captured in the following assumption, which describes two properties of an effectivity function for simple games. Assumption 1. The effectivity function Esatisfies the following statements: (i) For all S∈W, for all x=(a π) ∈X,S∈E(xy) if y=(b(SπS)) for any b∈A. (ii) For all B∈B,B∈E(xx0)for all x∈X. (iii) For all L⊂S∈W, for all x=(a (S π−S)) ∈X,(b (LS −Lπ−S)) ∈E(xL) if and only if a=bor [(b =a0)and S−L/∈W]. Part (i) of the assumption implies that a winning coalition is eligible to induce state (b(Sπ)) from any state (aπ). Part (ii) just says that a blocking coalition can always Theoretical Economics 15 (2020) Coalition formation and history dependence 181 induce a zero state. Part (iii) implies that a subcoalition Lof a winning coalition Sthat is not winning or blocking can change the outcome only if the residual coalition, i.e., S−L, ceases to be a winning coalition. In such a case, no winning coalition forms and so Lenforces the status quo. Given these restrictions on the power of coalitions and utility functions, the only relevant details of a state not in X0are given by the identity of the winning coalition S and the outcome chosen by S. We normalize utility functions so that ui(a0)=0, and make the following assumption. Assumption 2. For all S∈W,thereisa∈Asuch that ui(a) > 0for all i∈N. Assumption 2 ensures that every winning coalition has at least one alternative that its members strictly prefer to the status quo outcome. In this setting, we derive a transparent necessary and sufficient condition for HSREFS and HREFS in terms of sets of outcomes rather than sets of objection paths. As we mentioned earlier, the advantage of this more direct approach is that it is easier to check whether a given set of social states Ycan be supported as a solution. The intuitive reason why it is possible to derive this direct characterization is because of the special structure of simple games: the only “powerful” coalitions are winning coalitions or blocking coalitions that have the power to prevent the complementary coalition from winning. Importantly, we are also able to show that this stark distribution of power implies that any absorbing expectation function satisfying Conditions I and E is an HSRE. That is, neither version of maximality plays a role for NTU simple games in the presence of history dependence. For any x∈Xand S∈N,denoteDS(x) ={y∈X:uS(y) uS(x)}. Our characterization is in terms of the system of sets {DS(x)}S∈Nx∈X. Definition 8. A set Y⊆Xsatisfies Property C if for any y∈Y,foranyS∈N,z∈ E(yS),eitherz∈Y−DS(y) or there are B∈B,W∈Wand x∈Ysuch that x∈ Y∩DB(z) ∩(DW(x0)−DS(y)). Remark 4. Note that this definition allows for the possibility that B=W. This is the case if there is T∈Wand x∈Y∩DT(z) −DS(y). AsetYsatisfies Property C if the following is true. Take any yin Yand any Sthat can deviate to z. Suppose z∈Y, but all members of Sdo not strictly prefer zto y.Inthat case, one does not have to worry about the possibility of this deviation taking place. In all other cases, we have to ensure that this deviation is blocked. Property C states that if Sdoes deviate from yto z, then some blocking coalition Bcan precipitate the status quo and then some winning coalition Wcan make a further deviation to x∈Y.The state xhas the property that all members of Bstrictly prefer xto zand all members of Wstrictly prefer xto the status quo. Alternatively, someone in Sis not better off at x compared to y. So if the expectation is that there will be a move to xfollowingamoveto z, then the initial deviation will not take place. Our main result of this section follows. 182 Dutta and Vartiainen Theoretical Economics 15 (2020) Theorem 3. In all proper simple games, the following statements are equivalent for any set Y⊂X. (i) We have Y=μ( ¯ F),whereFis an absorbing expectation function satisfying Conditions I and E. (ii) The set Yis HSREFS. (iii) The set Ysatisfies Property C. Proof. Since (ii) obviously implies (i), it is sufficient to show that (iii) implies (ii) and (i) implies (iii). Step 1. We first show that (iii) implies (ii). Proof. Suppose Ysatisfies Property C. Pick any y∈Y, coalition S,andz∈E(Sy) such that z∈Y∩DS(y) or z∈X−Y. Define a function φsuch that, for any y∈Y,forany z∈(X −Y)∪(Y ∩DS(y)),andS∈E(yz), φ(ySz) =Bx0Wxs.t. B∈BW ∈Wand x∈Y∩DB(z) ∩DWx0−DS(y) Since Ysatisfies Property C, such a function φexists. By construction, (z φ(y Sz)) =(zBx0Wx)is an objection path for any such specified (ySz). We show that there is a strongly coherent collection of objection paths Pwith μ(P) =Y. Let P1={(zφ(ySz)):y∈YS ∈Nz ∈E(Sy)z ∈(X −Y)∪(Y ∩DS(y))}.Let P2={(x0Wx)|(zBx0Wx)∈P1}. Construct Pby P=(y)y∈Y∪P1∪P2 We show that Psatisfies parts (i)–(iv) of Definition 7. To check part (i) of the definition, note that (y) ∈Pfor each y∈Y.Takeanyx/∈Y. If x∈X0,thenB∈E(yx) for all y∈Yand B∈B. So choose some y∈Yand B∈B, and note that px=(xφ(yBx))∈P1.Ifx/∈X0,thenforsomeS∈Wand S∈E(yx), px=(xφ(ySx))∈P1. Part (ii) follows immediately since P2is a subset of P. To check part (iv), consider any path (y) ∈P.TakeanyS∈Nand z∈E(Sx).If z/∈(Y −DS(y)), then pz=(zφ(ySz))∈Pand μ(pz)∈Y−DS(y).So(y) is not Sdominated in Pvia z.Ifz∈(Y −DS(y)),thenagain(y) is not S-dominated in Psince (z) ∈P. For part (iii), consider any path py∈P. Suppose pyis S-dominated in Pvia some S. Identify μ(py)=x. Since pyis S-dominated in P,thereisz∈E(Sy) such that uSμ(pz)>u S(x) for all pz∈P (1) Suppose z=(bπ) /∈X0.ThenS∈W. Since Sis a winning coalition, S∈E(x(bπ)) for some πwith S∈π. Using (1), it follows that (x) is S-dominated in P.Thisisa contradiction since we have shown that part (iv) of strong consistency is satisfied. Theoretical Economics 15 (2020) Coalition formation and history dependence 189 the ultimate undominated set associated to the problem. So the ultimate undominated set is the limit set, obtained by recursively eliminating dominated objection paths. Notice that if Xis a finite set, then only finitely many elimination rounds are needed. The next lemma provides a condition under which UUD is a coherent collection. Lemma 4. Let P=UUD.IfPxis nonempty for all x,thenPis a coherent collection of paths. Proof. It is clear that Psatisfies Definition 6(ii)–(iv). So if Pxis nonempty for all x,then Pis a coherent collection of objection paths. Let Pbe any other coherent collection of objection paths. We show by induction that P⊆UDtfor all t=01. It is clear that P=ud(P) since no path in Pis dominated because of Definition 6(iii) and (iv). By assumption P⊆P∗=UC0.LetP⊆UDt.Then,byLemma 3,P=ud(P) ⊆ ud(UDt)=UDt+1.HenceUUDcontains all coherent collections and μ(P) is the largest HREFS. Given finiteness of X, the set of acyclic objection paths is finite. This implies that the ultimate undominated set is, at each elimination round t, nonempty and well defined. The difficult part is to show that UDtcontains a path pxwith initial state x,forarbitrary x∈X, as required by Coherence. The proof of the next lemma, which does this, is relegated to the Appendix. Lemma 5. Let Xbe finite. For all x∈X,thereispxsuch that px∈UUD. The proof of the next theorem follows immediately from Lemma 4 and Lemma 5. Theorem 4. If Xis finite, there is a nonempty HREFS. 9.2 Nonempty HSREFS for partition function games In this section, we prove an existence result for HSREFS for the large class of games represented by superadditive partition function games. In view of the demanding nature of HSREFS, this nonemptyness result demonstrates the power of history dependence. Let be the set of all partitions of N.Anembedded coalition is a pair (S π),where π∈and S∈π. With some abuse of notation, we use (N) to denote the embedded coalition (N {N}). ATU partition function game is a mapping vthat specifies a real number v(Sπ) for each embedded coalition (S π).Thatis,v(Sπ) is the sum of utilities that coalition S can achieve if the partition πforms. This formulation allows for externalities: what S can get depends on the entire coalition structure. For any coalition S⊆N,weletπSdenote a partition of S, while Sdenotes the set of all partitions of S.Also,−Sis the set of all partitions of N−S, with a typical element π−S. 190 Dutta and Vartiainen Theoretical Economics 15 (2020) For any πand ST ∈π,weuseπ−S∪Tto denote the partition of N−S∪Tobtained from π.Thatis,R∈π−S∪Tif and only if R∈πand R/∈{ST}. Henceforth, we assume that vsatisfies the following condition. Superadditivity. For all π∈,forallST ∈π,v(Sπ) +v(Tπ) ≤v(S ∪T{S∪ Tπ−S∪T}. Note that superadditivity ensures that for all π∈,v(N) ≥S∈πv(Sπ). Throughout, we also assume that the partition function vis 0-normalized so that v({i}π)=0for all i∈Nand all π∈with {i}∈π.27 We should specify the effectivity function associated with a partition function game. Take any initial state xand suppose some coalition Sdeviates from x. It makes sense to assume that Scan choose any partition of Sand that it cannot dictate how N−S chooses a partition in N−S. However, it is notationally complicated to explicitly formalize the effectivity function. Fortunately, for our purposes it suffices to consider only certain kinds of coalitional moves and so we do not need to describe the effectivity function in full detail. Let x0∈Xbe the zero state such that ui(x0)=0for all iand π(x0)={{1}{n}}. That is, the partition formed in the zero state is one in which each element of the partition of Nconsists of a single individual and all corresponding embedded coalitions get zero utility.28 We make the following assumption. Assumption 3. For all i∈N,N−{i}∈E(xx0)for all x∈X. This is straightforward since N−{i}can always decide to break up into singletons. We will use this assumption repeatedly in the proof of a crucial lemma. Definition 9. Player iis essential if and only if v(N) > v(N −{i}{N−{i}{i}}). So player iis essential if she adds positive value to coalition N−{i}.Let Z=x∈X: i∈N ui(x) =v(N)ui(x) > 0,ifiis essential Lemma 6. For all (xyk)∈Z×X×N,thereispysuch that uk(μ(py)) ≤uk(x). Proof. Choose any triple (xyk)∈Z×X×N. We consider two cases. Case 1. uk(y) > 0. Since y∈X, superadditivity implies that i∈Nui(y) ≤v(N).Sothere is y∈X(possibly y=y) such that i∈Nui(y)=v(N),ui(y)≥ui(y) for all i∈N. Suppose uk(x) > 0. Since uk(y)>0, this implies that there is z∈Xsuch that  i∈N ui(z) =v(N) 27This is without loss of generality. 28The latter follows since vis 0-normalized. Theoretical Economics 15 (2020) Coalition formation and history dependence 191 ui(z) > uiyfor all i= k uk(x) ≥uk(z) > 0 Then define py=(yN −{k}x0Nz). Clearly, pysatisfies all the requirements of the lemma. Next suppose uk(x) =0. Since x∈Z,iis not essential. So v(N −{k}{N−{k}{k}})= v(N). Clearly, this allows us to choose z∈Xsuch that z(π) ={N−{k}{k}},N−{k}∈ E(yz),and ui(z) > ui(y) for all i= k  i=k ui(z) =vN−{k}N−{k}{k}=v(N) uk(z) =0 Then let py=(y N −{k}z). Again, pysatisfies the requirements of the lemma. Case 2. uk(y) =0. Suppose kis essential, so that uk(x) > 0.Let{k}∈E(yw),where {k}∈π(w).Thenuk(w) =0. Note that we do not make any other assumption about π(w) or ui(w) for i= k. Since kis essential, i=kui(w) < v(N) Since uk(w) =0, we can choose z∈Xsuch that  i∈N ui(z) =v(N) ui(z) > ui(w) or all i∈N uk(x) ≥uk(w) Then py=(y {k}wNz)satisfies the requirements of the lemma. Suppose kis not essential. If y∈Z,thenpy=(y) satisfies the requirements of the lemma. If y/∈Z, then either (i) i∈Nui(y) < v(N) =v(N −{k}N −{k}{k}}) or (ii) i= kis essential, but ui(y) =0. If (i) holds, then let py=(yN −{k}z),wherei=kui(z) =v(N −{k}N−{k}{k})= v(N),andui(z) > ui(y) for all i= k,uk(z) =0Clearly, such z∈Zexists and so pysatisfies the requirements of the lemma. If (ii) holds, then let ibe essential and let ui(y) =0.Thenlet{i}∈E(yw),where{i}∈ π(w). Using the fact that j=iuj(w) < v(N), we can choose py=(y {i}wN −{k}z) such that  j=k uj(z) =vN−{k}N−{k}{k}=v(N) (since kis not essential) 192 Dutta and Vartiainen Theoretical Economics 15 (2020) uj(z) > uj(w) for all j= k uk(z) =0 This completes the proof of the lemma. Let PZis the collection of objection paths terminating in Z: PZ=p∈P∗:μ(p) ∈Z We will prove that Zis HSREFS by showing that PZconstitutes a strongly coherent collection of objection paths. Theorem 5. The set Zis an HSREFS. Proof.Takeanyy∈X. Choose arbitrary x∈Zand k∈N.Lemma 6 implies that there is py∈PZsuch that uk(μ(py)) ≤uk(x).Hence,Py∩PZis nonempty and Condition (i) of Definition 7 is satisfied. For any objection path in PZ, a subpath that begins from a state in the middle is also an objection path of blocking coalitions with a terminal element in Zand, hence, is a member of PZ. That is, Condition (ii) of Definition 7 is satisfied. Next take any pz∈PZwith x=μ(pz). Suppose that pzis S-covered via yfor some S. Choose some k∈S.ByLemma 6, there is an objection path py∈PZsuch that uk(μ(py)) ≤uk(x), contradicting the assumption that pzis S-covered via y.Hence, Condition (iii) of Definition 7 is satisfied. Now, take any (z) ∈PZ. Suppose that (z) is S-covered via yfor some S. Choose some k∈S.ByLemma 6, there is an objection path py∈PZsuch that uk(μ(py)) ≤uk(x), contradicting the assumption that (z) is S-covered via y. So Condition (iv) of Definition 7 is also satisfied and so PZis indeed strongly coherent. This shows that Zis HSREFS. HSREFS need not be unique. We leave it to the reader to check that W=w∈X: i∈N ui(x) ≤v(N)ui(x) > 0,ifiis essential is also HSREFS. Of course, Z⊆W.29 10. Concluding remarks This paper studies the consequences of memory on coalition formation. To this end, we extend the rational expectation stable set solution of Dutta and Vohra (2017) by allowing coalitions to condition their behavior on the history of blockings. The resulting solution satisfies the same stringent stability properties as the Dutta–Vohra solution, but has an extra degree of freedom because of history dependence. 29The proof that Wis HSREFS is almost identical. Theoretical Economics 15 (2020) Coalition formation and history dependence 193 History dependence turns out to have very powerful implications. We show that a history-dependent rational expectation solution exists under very general conditions, for example, whenever the set of states is finite. What is more, we demonstrate that even the more stringent version of the solution, which requires that the current coalitional move is optimal also for nonactive coalitions, exists and is nonempty in all superadditive partition function games. We are not aware of prior existence results in the literature with similar robustness and existence properties. Our results suggests that the introduction of history dependence in the study of coalition formation is a fruitful avenue for further research. Appendix In this Appendix, we prove Lemma 5:forallx∈X, UUD contains some objection path originating from x. Proof of Lemma 5 Since UD0=Pand, hence, contains objection paths originating from x,itsufficesto prove that for all x∈X, for all t=0,ifUDt x= ∅, then UDt+1 xis nonempty as well. Choose some set Pof objection paths. Find, for any xsuch that (x) /∈ud(P),acoalition S(x) such that (x) is S(x)-dominated in P. For any x, identify a set C(xP) such that C(xP) =y:(x) is S(x)-covered in Pvia y(2) Further, denote by C∗(x P) the subset of C(xP) that contains any ythat induces the maxmin payoff to coalition S(x) in C(xP).Thatis, C∗(xP) =y∈C(xP) :max z∈C(xP) min p∈Pz uS(x)μ[p) min p∈Py uS(x)μ[p)(3) Note that (x) ∈ud(P) if and only if C(xP) =C∗(x P) =∅. We say that (x0S(x0)xJ)is a C∗(·P)sequence that originates from xif x=x0 and xj+1∈C∗(xjP)for all j=0J−1. Denote by C∗(·P) the transitive closure of C∗(·P).30 Denote the set of maximal elements of C∗(·P)by V(P)={x∈X:y∈C∗(x P) implies x∈C∗(y P), for all y}. Lemma 7. Let y∈C∗(xP). Then, for any py∈Py, the sequence (xS(x)py)is an objection path and it is not dominated in Pif P⊆P. Proof. Since pyis a member of Pyand xis S(x) covered in Pvia y,(x S(x) py)is an objection path. If (xS(x)py)is dominated in Pand P⊆P, then there is zsuch that min pz∈Pz uS(x)μ[pz)≥min pz∈P z uS(x)μ[pz)uS(x)μ[p)uS(x)(x) 30That is, y∈C∗(x P) if and only if there is a C∗(·P)sequence originating from xand ending in y. 194 Dutta and Vartiainen Theoretical Economics 15 (2020) The third inequality, which implies that (x S(x) py)is an objection path, follows from the assumption that y∈C(xP). Thus the first inequality implies that also z∈C(xP). But together with (2), this contradicts the assumption that y∈C∗(x P). Lemma 8. For any t=01, for any x0∈X, let (x0S(x0) x1xJ)be a C∗(·UDt) sequence with (xJ)∈UDt+1.Then(x0S(x0) x1xJ)∈UDt+1. Proof.Ofcourse,UDt+1⊆UDtfor all τ.SoLemma 7 implies that the sequence (xjS(xj) xjxJ)is not dominated in UDtfor any j=01J −1. Since, in addition, (xJ)is not dominated in UDt,wehave(x0S(x0) x1xJ)∈UDt+1. Lemma 9. For any t=01, for any x∈X,thereisy∈C∗(x UDt)such that (y) ∈ UDt+1. Proof. Claim 1. For any t,ifx∈V(UD t)and (x) ∈UDt,then(x) ∈UDt+1. Proof. Suppose that (x) ∈UDt−UDt+1and x∈V(UD t). Since Xis a finite set, there is a C∗(·UDt)sequence (x0S(x0) x1xL)such that x=x0=xL.ByLemma 8, (x1S(x1) x2xL)∈UDt. But then, since xL=v0,x0is not dominated via x1in UDt, a contradiction to the hypothesis that x1∈C∗(x0UDt). Claim 2. For any t,C∗(xUDt)=C(xUDt)for all x∈V(UD t). Proof.Fixanyx∈V(UD t). It suffices to show the direction C(xUDt)⊆C∗(x UDt). If (x) ∈UDt+1, then C(xUDt)=C∗(x UDt)=∅. Suppose that (x) /∈UDt+1. Since x∈V(UD t),thereisaC∗(·UDt)sequence (x0S(x0) x1xL)such that x=x0=vL. Choose any x∈C(x0UDt).ByLemma 7, (x0S(x0) p)∈UDtfor any p∈UDt x. Iterating backward on j=L−1L−22,it follows that x1S(x1)xL−1S(xL−1) x0S(x0) p∈UDtfor any p∈UDt x Thus p∈UDt xμ[p) ⊆p∈UDt x1μ[p), implying, by (3), that x∈C∗(x0UDt). Since xis an arbitrary element of C(x0UDt), we conclude that C(x0UDt)=C∗(x0UDt). Claim 3. For any t, for any x∈V(UD t),thereisx∈C∗(x UDt)such that (x)∈UDt+1. Proof. Initial step: t=0.Then(x)∈UD0for all x∈X.ByClaim 1,(x)∈UD1for all x∈V(UD 0). Inductive step: t>0. Let the claim hold for t−1. We show that it holds for t.Bythe definition of V,C∗(x UDt)⊆V(UD t)for all x∈V(UD t).Thus,byClaim 2, CxUDt⊆VUDtfor all x∈VUDt(4) Theoretical Economics 15 (2020) Coalition formation and history dependence 195 By the maintained assumption, there is a x∈C∗(x UDt−1)such that (x)∈UDt. Since C∗(·UDt−1)⊆C(·UDt−1)⊆C(·UDt),alsov∈C(vUDt).By(4), v∈V(UD t). By Claim 1,(v)∈UDt+1. Claim 4. For any x∈X,thereisy∈C∗(x UDt)such that (y) ∈UDt+1. Proof.Ifx/∈V(UD t), then there is y∈C∗(x UDt)∩V(UD t).ByClaim 3,thereisz∈ C∗(y UDt)such that (z) ∈UDt+1. By transitivity, z∈C∗(x UDt). The next lemma now follows by Lemmas 8and 9. Lemma 10. For any t=01, for any x∈X,thereisaC∗(·UDt)sequence (x0S(x0) xJ)such that (x0S(x0)xJ)∈UDt+1 x. This completes the proof of Lemma 5. References Anesi, Vincent (2010), “Noncooperative foundations of stable sets in voting games.” Games and Economic Behavior, 70, 488–493. [160] Anesi, Vincent and Daniel J. Seidmann (2014), “Bargaining over an endogenous agenda.” Theoretical Economics, 9, 445–482. [160] Aumann, Robert J. and Roger B. Myerson (1988), “Endogenous formation of links between players and of coalitions, an application of the Shapley value.” In The Shapley Value: Essays in Honor of Lloyd Shapley (Alvin Roth, ed.), 175–191, Cambridge University Press, Cambridge. [160] Béal, Sylvain, Jacques Durieu, and Philippe Solal (2008), “Farsighted coalitional stability in TU games.” Mathematical Social Sciences, 56, 303–313. [168] Bhattacharya, Anindya and Victoria Brosi (2011), “An existence result for farsighted stable sets of games in characteristic function form.” International Journal of Game Theory, 40, 393–401. [169] Bloch, Francis (1996), “Sequential formation of coalitions in games with externalities and fixed payoff division.” Games and Economic Behavior, 14, 90–123. [160] Bloch, Francis and Anne van den Nouweland (2019), “Farsighted stability with heterogenous expectations.” Unpublished paper, SSRN 3400094. [161] Chander, Parkash (2015), “An infinitely farsighted stable set.” Unpublished paper, Department of Economics and Finance, Jindal Global University. [160] Chwe, Michael Suk-Young (1994), “Farsighted coalitional stability.” Journal of Economic Theory, 63, 299–325. [160,168] Diamantoudi, Effrosyni and Licun Xue (2003), “Farsighted stability in hedonic games.” Social Choice and Welfare, 21, 39–61. [160,169] 196 Dutta and Vartiainen Theoretical Economics 15 (2020) Diamantoudi, Effrosyni and Licun Xue (2007), “Coalitions, agreements and efficiency.” Journal of Economic Theory, 136, 105–125. [169] Dutta, Bhaskar and Rajiv Vohra (2017), “Rational expectations and farsighted stability.” Theoretical Economics, 12, 1191–1227. [160,161,172,179,192] Gomes, Armando and Philippe Jehiel (2005), “Dynamic processes of social and economic interactions: On the persistence of inefficiencies.” Journal of Political Economy, 113, 626–667. Granot, Daniel and Eran Hanany (2016), “Subgame perfect farsighted stability.” Unpublished paper, Faculty of Engineering, Tel Aviv University. [172] Greenberg, Joseph (1990), The Theory of Social Situations: An Alternative GameTheoretic Approach. Cambridge University Press, Cambridge, Massachusetts. [168] Harsanyi, John C. (1974), “An equilibrium-point interpretation of stable sets and a proposed alternative definition.” Management Science, 20, 1472–1495. [160,164,167] Herings, P. Jean-Jacques, Ana Mauleon, and Vincent Vannetelbosch (2009) Games and Economic Behavior, 67, 526–541. [160,169] Herings, P. Jean-Jacques, Ana Mauleon, and Vincent Vannetelbosch (2010), “Coalition formation among farsighted agents.” Games, 1, 286–298. [169] Herings, P. Jean-Jacques, Ana Mauleon, and Vincent J. Vannetelbosch (2004), “Rationalizability for social environments.” Games and Economic Behavior, 49, 135–156. [160,169,171,172,173] Jordan, James S. (2006), “Pillage and property.” Journal of Economic Theory, 131, 26–44. [161,164] Kimya, Mert (2018), “Equilibrium coalitional behavior.” Unpublished paper, Department of Economics, Koç University. [160,169,171,175] Konishi, Hideo and Debraj Ray (2003), “Coalition formation as a dynamic process.” Journal of Economic Theory, 110, 1–41. [160] Lucas, William F. (1992), “Von Neumann–Morgenstern stable sets.” In Handbook of Game Theory With Economic Applications, Volume 1 (Robert J. Aumann and Sergiu Hart, eds.), 543–590, North Holland Publishing, Amsterdam, The Netherlands. [160] Mariotti, Marco (1997), “A model of agreements in strategic form games.” Journal of Economic Theory, 74, 196–217. [172,175] Mauleon, Ana and Vincent Vannetelbosch (2004), “Farsightedness and cautiousness in coalition formation games with positive spillovers.” Theory and Decision, 56, 291–324. [170,171] Mauleon, Ana, Vincent J. Vannetelbosch, and Wouter Vergote (2011), “Von Neumann– Morgenstern farsighted stable sets in two-sided matching.” Theoretical Economics,6, 499–521. [160,169] Theoretical Economics 15 (2020) Coalition formation and history dependence 197 Moulin, Herve (1983), TheStrategyofSocialChoice. North Holland-Elsevier, New York, New York. [186] Mueller, Dennis (1978), “Voting by veto.” Journal of Public Economics, 10, 57–75. [186] Ray, Debraj and Rajiv Vohra (1997), “Equilibrium binding agreements.” Journal of Economic Theory, 73, 30–78. [160] Ray, Debraj and Rajiv Vohra (1999), “A theory of endogenous coalition structures.” Games and Economic Behavior, 26, 286–336. [160] Ray, Debraj and Rajiv Vohra (2015a), “Coalition formation.” In Handbook of Game Theory (Shmuel Zamir and Petyon Young, eds.), 239–326, North Holland-Elsevier. Chapter 5. [160,161] Ray, Debraj and Rajiv Vohra (2015b), “The farsighted stable set.” Econometrica, 83, 977– 1011. [160,163,164,171,179] Ray, Debraj and Rajiv Vohra (2019), “Maximality in the farsighted stable set.” Unpublished paper, SSRN 3113678. [183,188] Vartiainen, Hannu (2011), “Dynamic coalitional equilibrium.” Journal of Economic Theory, 146, 672–698. [160,166] Vartiainen, Hannu (2014), “Endogenous agenda formation processes with the onedeviation.” Theoretical Economics, 9, 187–216. [166] Vartiainen, Hannu (2015), “Dynamic stable set as a tournament solution.” Social Choice and Welfare, 45, 309–327. [166] Von Neumann, John and Oscar Morgenstern (1944), Theory of Games and Economic Behavior. Princeton University Press, Princeton. [179] Xue, Licun (1998), “Coalitional stability under perfect foresight.” Economic Theory, 11, 603–627. [160,169,171,175] Co-editor Dilip Mookherjee handled this manuscript. Manuscript received 24 July, 2017; final version accepted 15 May, 2019; available online 14 June, 2019.