Farsighted rationality in hedonic games

Demeze-Jouatsa, Ghislain-Herman; Karos, Dominik Working Paper Farsighted rationality in hedonic games Center for Mathematical Economics Working Papers, No. 654 Provided in Cooperation with: Center for Mathematical Economics (IMW), Bielefeld University Suggested Citation: Demeze-Jouatsa, Ghislain-Herman; Karos, Dominik (2021) : Farsighted rationality in hedonic games, Center for Mathematical Economics Working Papers, No. 654, Bielefeld University, Center for Mathematical Economics (IMW), Bielefeld, https://nbn-resolving.de/urn:nbn:de:0070-pub-29579246 This Version is available at: https://hdl.handle.net/10419/249877 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/4.0/ 654 October 2021 Farsighted Rationality in Hedonic Games G.-Herman Demeze-Jouatsa and Dominik Karos Center for Mathematical Economics (IMW) Bielefeld University Universit¨atsstraße 25 D-33615 Bielefeld ·Germany e-mail: [email protected] uni-bielefeld.de/zwe/imw/research/working-papers ISSN: 0931-6558 Unless otherwise noted, this work is licensed under a Creative Commons Attribution 4.0 International (CC BY) license. Further information: https://creativecommons.org/licenses/by/4.0/deed.en https://creativecommons.org/licenses/by/4.0/legalcode.en Farsighted Rationality in Hedonic Games G.-Herman Demeze-Jouatsa1and Dominik Karos∗2 1Bielefeld University, Center for Mathematical Economics 2Bielefeld University, Center for Mathematical Economics, Chair of Economic Theory October 5, 2021 Abstract We consider a hedonic coalition formation game in which at each possible partition any new coalition can decide the probability with which to form and leave the current partition. These probabilities are commonly known so that farsighted players can decide whether or not to support a coalition’s move: they know which future partition, and hence payoffs, will be reached with what probability. We show that if coalitions make mistakes with positive probability, i.e., if they choose probabilities that are always above some ε > 0, then there is a behavior profile in which no coalition has a profitable one-shot deviation. Keywords: abstract games, hedonic games, farsighted stability, coalition stable equilibrium JEL: C71, C72 1 Introduction An abstract game consists of a set of states (or outcomes), agents’ payoffs in each state, and an effectivity correspondence that describes for any two state what coalitions are able to implement a move from the former to the latter. Because of their generality, abstract games can be used to model a great variety of games; in particular, games with non-transferable utilities: there, a state comprises a partition of players into coalitions and a payoff for each player. The class of games that will be interesting in this paper are hedonic games, which were introduced by Dr`eze and Greenberg (1980). Here the idea is that whenever some coalition Sforms, each player’s payoff ∗corresponding author. dominik.k[email protected] 1 π1(4, a, 0) π2(0,4, a)π3(a, 0,4) {1,2} {2,3} {1,3} Figure 1: The roommate problem is predetermined. That is, while coalitions might be in competition with each other, there is no intra-coalition competition about resources or payoffs. Among others these games include matching problems or network formation games. One very well known example of a hedonic game is the ‘roommate problem’ that is depicted in Figure 1. There are three players who have to decide about who will be moving in together, i.e., about how to form a partition. Denote by π1, π2, and π3the partition in which players 1 and 2, 2 and 3, or 1 and 3, respectively are roommates, while the remaining player is excluded. From Figure 1 we observe that for a∈(0,4) preferences are as follows: 1 prefers to move in with 2 over moving in with 3 over staying alone; 2 prefers moving in with 3 over moving in with 1 over staying alone; and 3 prefers moving in with 1 over moving in with 2 over staying alone. Once a partition has formed, there is no more negotiating about payoffs, but everything is fixed. Unfortunately, despite their rather simple structure, hedonic games are not easily solved. Bogomolnaia and Jackson (2002) and Banerjee et al. (2001) provide sufficient conditions for the nonemptiness of the core; Iehl´e (2007) provides a condition which is both necessary and sufficient and very similar to the balancedness condition by Shapley (1967) and Bondareva (1963). The game in Figure 1, however, does not obtain a core stable partition. More recently, other solutions to cooperative games in general, and to hedonic games in particular, have gained some attention: namely, farsighted solutions that first emerged from Harsanyi (1974) and Chwe (1994) and were applied to hedonic games for instance by Diamantoudi and Xue (2003). The general idea behind farsighted solutions is that coalitions do presume to remain in the state they deviate to but acknowledge and expect other coalitions to react and immediately leave the new state. When using farsighted solutions in the context of coalition formation games there are some structural obstacles to overcome: first, unlike in the myopic case, it is essential if and how players react who have been left behind by a moving coalition as 2 this will affect future moves. Second, when deciding whether or not to leave a state coalitions should not only consider the long-term effect of their moving, but also the long-term effect of their not moving. The first point was taken up by Ray and Vohra (2015) who proposed conditions on the structure of an effectivity correspondence that emerges from a coalition formation game; the second point was the topic of Karos and Robles (2021) who provided a solution based on expectation functions (cf. Dutta and Vohra, 2017) that allowed coalitions to form expectations about the future in case they remain in the status quo. While these expectation functions have clear axiomatic and non-cooperative foundations, their big disadvantage is that they may not exist for some games. For instance, they do not exist for the roommate problem depicted in Figure 1. In this paper we shall consider hedonic games and extend the idea of Karos and Robles (2021) by using their non-cooperative foundation and allow coalitions to play mixed strategies. The idea is simple enough: provided that payoffs are sufficiently well-behaved we might hope for the existence an equilibrium in mixed strategies. And we will indeed find some positive result. Mathematically speaking we proceed as follows: we define for each coalition at each partition a probability distribution over states it might move to, a so called mixed coalition behavior. These strategy profiles define transition probabilities among states, and if we restrict ourselves to strictly positive distributions, i.e., completely mixed behaviors, then these transition probabilities define an irreducible Markov process. As our state space consists only of partitions of the player set (recall that in hedonic games players’ payoffs are uniquely determined for every partition), the Markov process is recurrent as well, which means that it obtains a unique stationary distribution. This distribution describes how much time the process will (in average) spend in each state, i.e., how long each partition will hold, so that we can define a player’s utility as the expected utility over all partitions weighted by the stationary distribution. Thus, we define a coalitional game that specifies for each (completely mixed) strategy profile a payoff vector. We then turn to deviations and make the following observation, which is our technical main result: for any two irreducible finite space Markov processes whose transition matrices are identical everywhere but in one row, the stationary distribution of any convex combination of the two is a convex combination of the two stationary distributions of those processes. Observing that in hedonic games a coalition has only two options at any state, namely to form or not to form, and that a change of strategy at only one 3 partition leads to a new Markov process that differs only in one row, reveals that for any fixed strategy profile of their opponents the feasible utility vectors of a coalition form a (bounded) line. In particular, when moving along this line players’ payoffs will either increase or decrease, so that either all players agree that one end point of the line is better than the other, or no two points can be Pareto-ranked. This allows us to conclude that the set of best-responses that a coalition has (in the sense that they are not Pareto-dominated) is a convex set. From here, the rest is pretty straightforward: we show that the best response correspondence satisfies the conditions of Kakutani’s fixed point theorem and, thus, has a fixed point. Hence, there is a mixed strategy profile from which no coalition has a profitable one-shot deviation. For the roommate problem above Karos and Robles (2021) show that such a profile exists. The remainder of the paper is structured as follows: In Section 2 we introduce the necessary notation, define probabilistic expectation functions, and derive expected utilities using some well-known results from the literature on Markov processes. In Section 3 we introduce hedonic games and provide a formulation in terms of effectivity correspondences. Section 4 introduces the non-cooperative setup in which we endow coalitions with strategies, and in Section 5 we show that for any slightly perturbed game (meaning that all strategies are played with small but positive probability) there is an equilibrium. The paper concludes in Section 6 with a brief discussion. 2 Preliminaries 2.1 Abstract Games Let Nbe a finite set of players with |N| ≥ 3. Subsets S⊆Nare called coalitions. For S⊆Nwrite 2Sfor the set of subsets of S, and P(S) for the set of nonempty subsets. A partition is a collection π={S1, . . . , Sm}of nonempty coalitions such that Sm k=1 Sk=Nand Sk∩Sl=∅for all k6=l. For i∈Nand a partition πwe write π(i) for the unique element of πthat contains i. The set of all partitions is denoted by Π. Let Xbe a finite set of states. An abstract game is a tupel N, X, E, (Ui(·))i∈N, where Ui:X→Ris player i’s utility function over states and E:X×X⇒2Nis an effectivity correspondence: for two states x, y ∈Xthe (possibly empty) set E(x, y) comprises all coalitions that are effective for a move from xto y, i.e., that can replace 4 xwith y. We assume that E(x, x) = 2N, that is, each coalition can decide not to change the status quo; and ∅ ∈ E(x, y) if and only if x=y. A lottery over Xis a probability measure over X, the set of all lotteries over X is denoted by ∆(X). Players in the abstract game are expected utility maximizers, that is for any lottery λ∈∆(X) their utility is given by ui(λ) = Px∈Xλ(x)Ui(x). 2.2 Probabilistic Expectation Functions Let N, X, E, (Ui(·))i∈Nbe an abstract game. One way to deal with farsighted deviations is by endowing coalitions with expectations about who is deviating where. This is the path we shall pursue. A deterministic expectation function1is a map Fthat assigns to each x∈Xan ordered list F1(x), . . . , Fk(x)(x)such that Fl(x) = fl(x), Sl(x)∈X×2Nwith Sl(x)∈Ex, fl(x)for all l= 1, . . . , k(x), Sl(x)6=Sl0(x) for all l6=l0,fl(x)6=xfor all l6=k(x), and Sk(x)(x) = ∅. The idea of a deterministic expectation function is that at any state x, there are some coalitions Sl(x) who would replace state xby state fl(x). However, only S1(x) is allowed to actually do so. The remaining pairs in the list allow coalitions to make “rational” decisions: each coalition Sl(x) knows that if they do not move to fl(x), then coalition Sl+1(x) will move to fl+1(x). We assume that all players have the same expectation, represented by F, about how the abstract game unfolds, i.e., they are perfectly farsighted and have common expectations.2In particular, they can compare the consequences of any potential move to the consequences of not moving. What is new in this paper is that we allow expectations to be non-deterministic. That is, each coalition might not move to a fixed new state, but can use a random device in order to decide where to move. A probabilistic expectation function is a map Φ that assigns to each x∈Xan ordered list Φl(x)2|N| l=1 such that Φl(x) = φl(x), Sl(x)∈∆(X)×2Nwith: (i) Sl(x)6=Sl0(x) for all l6=l0, (ii) for all l= 1,...,2|N|,Sl(x)∈E(x, y) for all y∈Supp φl(x), 1Karos and Robles (2021) call this an extended expectation function to distinguish it from the expectation function in Dutta and Vohra (2017). The latter will play no role in this paper, so we only distinguish between deterministic and probabilistic expectation functions. 2For a model of heterogeneous expectations in abstract games refer to Bloch and van den Nouweland (2020). 5 (iii) S2|N|(x) = ∅. Observe that this list contains all coalitions, the empty set being the last one, but, by the first condition, no coalition appears twice. The second condition ensures that any coalition Slcan only move to those states ywith positive probability for which it is effective. We write φl(y|x) for the probability with which coalition Sl(x) implements a move from xto y. By the last condition and since the empty set is never effective for a move out of any x, it holds that φ2|N|(x|x) = 1, i.e., φ2|N|=δx. 2.3 Expected Payoffs Let Φ be a probabilistic expectation function. Then at each x∈X, the probability that coalition Sl(x) will implement a move to y∈X\ {x}is given by φl(y|x)Qh<l φh(x|x). Thus, the probability of a move from xto yby any coalition, i.e., the transition probability from xto y, is p(y|x) =   P2|N|−1 l=1 φl(y|x)Qh<l φh(x|x) if y6=x, Q2|N|−1 l=1 φl(x|x) if y=x. (1) Let P∈[0,1]X×Xbe the matrix with entries Px,y =p(y|x). Lemma 2.1. The matrix Pis row-stochastic, i.e., Px,y ≥0for all x, y ∈Xand Py∈XPx,y = 1 for all x∈X. The proof of Lemma 2.1, as any other proof of this paper, can be found in the appendix. As Pis row-stochastic, it is the transition matrix of a Markov process with state space X. Such a Markov process is called irreducible if for any two states x, y there is n∈Nsuch that (Pn)x,y >0, i.e., if the probability of a transition from x to yafter nsteps is strictly positive. The following proposition comprises well-known results about irreducible Markov processes with finite state space that we will need later. We do not provide a proof but refer the reader to the standard literature, e.g. Stokey and Lucas (1999). Proposition 2.2. Let Pbe the transition matrix of an irreducible Markov process with finite state space X. Then there is a unique probability distribution µ∈∆(X) 6 such that for all x∈X µ(x) = lim n→∞ n X m=1 (Pm)y,x ey(2) for all y∈X, where eyis the unit vector with entry 1in the y-th coordinate. In particular, µ(x)>0for all x∈X, and µsatisfies (µ(x))T x∈X= (µ(x))T x∈XP, i.e., µ is the unique (left) eigenvector of Pto eigenvalue 1. Observe that µdoes not depend on the choice of yon the right hand side of (2). The distribution µis referred to as the stationary distribution of the Markov process. It determines for every x∈Xthe (average) share of time that the process will spend in x. In particular, this amount is independent of the state yin which the process starts. To keep notation simple, we shall write µTPfor the matrix product (µ(x))T x∈XP. If the expectation function Φ is such that the corresponding Markov process is irreducible, we denote the corresponding stationary distribution by µΦ. In this case, using the interpretation of µΦ(x) as the amount of time that the process spends in x, player iwill obtain the average payoff ui(Φ) = X x∈X µΦ(x)Ui(x).(3) Before we move on, we should note that the expectation functions that are investigated in the remainder of the paper will induce irreducible Markov processes; in particular, the average payoff in (3) is well-defined. 3 Hedonic Games Ahedonic game is a map vthat maps each nonempty coalition Sto some v(S)∈RS. That is, a hedonic game is a cooperative game such that each player’s payoff in each coalition is predetermined: there is no negotiation over payoffs within coalitions whatsoever.3For any hedonic game vwe define the map V: Π →RNby Vi(π) = vi(π(i)). That is, V(π)∈RNis the payoff vector for Nif partition πforms. In a hedonic game coalitions can freely form and dissolve. Thus, taking Π as the set of states, we can translate a hedonic game vinto an abstract game (N, Π, E, V ) with 3Thus, a hedonic game is an NTU-game in which no transfers among players is possible. 7 theorem to prove the existence of a fixed point of this correspondence, which, by definition, is a weak ε-equilibrium. 5.1 Convexity of the Set of Best Responses Most coalition formation problems with similar structure are accompanied by the intrinsic difficulty that the best responses as defined above do not form a convex set. One problem is that two different best replies will lead to two different Markov processes, say with transition matrices Pand Q, which in turn have stationary distributions λand µ. While a convex combination of the two best replies will lead to a Markov process with a transition matrix that is a convex combination of Pand Q, there is little that can be said about the stationary distribution of this process. In particular, it is not clear whether the emerging payoff vector will be a convex combination of the first two payoff vectors. Our first main result is that we can say something about convex combinations of two Markov processes whose transistion matrices are identical everywhere but in one row. Theorem 5.1. Let Xbe a finite set, and let P, Q ∈[0,1]X×Xbe transition matrices of irreducible Markov processes over X, so that there is x∗with Px,y =Qx,y for all y∈Xand all x6=x∗. Let λand µbe the (unique) stationary distributions of Pand Q, respectively. Let r∈[0,1] and define t=rµ (x∗) rµ (x∗) + (1 −r)λ(x∗)(6) Then rP + (1 −r)Qis the transition matrix of an irreducible Markov process, and ν=tλ + (1 −t)µis the unique stationary distribution of this process. Consider a (completely mixed) strategy profile β, and fix a partition πand a coalition ∅ 6=S⊆N. Then, for any two strategies β1 Sand β2 Sthat coincide with βSeverywhere but in πthe transition matrices of the corresponding Markov processes differ only in row π. That is, they satisfy the condition of Theorem 5.1. Formally, we obtain the following result. Theorem 5.2. Let vbe a hedonic game, and let Ebe an effectivity correspondence that satisfies H1–H4, let ρ= (ρπ)π∈Πbe a collection of bijections between 1,...,2N−1and P(N), and let ε > 0. Let S∈P(N),β∈QT⊆N∆ε(BT), 14 and π∗∈Π, and let βS,¯ βSbe such that βS(π) = ¯ βS(π) = βSfor all π6=π∗, and βS(π∗|π∗) = 1 and ¯ βS(π∗|π∗)=0. Let r=βS(π∗|π∗). Then ui(β) = tuiβS, β−S+ (1 −t)ui¯ βS, β−S for all i∈N, where tis defined as in (6). This solves the issue outlined above: as long as we focus on a coalition’s one-shot deviations from a fixed partition π, the payoff vector associated with a convex combination of two one-shot deviations is a convex combination of the two payoff vectors associated with either one. However, this still does not guarantee that a the mixture of two best responses is still a best response. The reason is the following: suppose coalition {1,2}can move from state wwith payoff u(w) = (0,0) to three different states, x, y, z with payoffs U(x) = (4,0), u(y) = (0,4), and u(z) = (3,3). Then any behavior is a best response as these states cannot be Pareto ranked. However, the behavior that assigns probability 1 2to both xand yis not a best response as moving to zwould be a better response. The crucial feature in this little illustration is that there are three potential states that the coalition can move to. If it can only decide between two options, then the argument does not work: either all players will prefer one of the two options, or there is a conflict of interest, which means that no probability distributions over the two is Pareto dominated. This is good news for us: as we have seen in Corollary 4.2 all mixed behaviors β1 Sand β2 Sthat coincide everywhere except some π∗must lie on a line. Thus, we obtain the following result. Proposition 5.3. Let vbe a hedonic game, let Ebe an effectivity correspondence that satisfies H1–H4, let ρ= (ρπ)π∈Πbe a collection of bijections between 1,...,2N−1 and P(N), and let ε > 0. Let S∈P(N),β∈QT∆ε(BT), and π∗∈Π. Then Rε S,π∗(β)is convex. The proof of Proposition 5.3 shows actually more. Namely, for any S∈P(N), β∈QT⊆N∆ε(BT), and π∗∈Π, the set Rε S,π∗(β) must have one of three forms: either it contains only the mixed behavior with βS(π∗|π∗) = ε, or it contains only the mixed behavior with βS(π∗|π∗)=1−ε, or it contains every mixture of the two. 15 5.2 Existence of Weak ε-equilibria Recall that coalition behavior profile βis a weak ε-equilibrium if β∈Rε S,π (β) for all ∅ 6=S⊆Nand all π∈Π. Thus, in order to prove the existence of such equilibrium, it is sufficient to show that the correspondence that maps each coalition behavior profile βto Q(S,π∗)Rε S,π∗(β) has a fixed point. We have already seen that this correspondence maps each βto a nonempty, compact, convex set. In order to apply Kakutani’s fixed point theorem it is, therefore, sufficient to show that it is upper hemicontinuous.8 Proposition 5.4. Let vbe a hedonic game, and let Ebe an effectivity correspondence that satisfies H1–H4, let ρ= (ρπ)π∈Πbe a collection of bijections between 1,...,2N−1and P(N), and let ε > 0. The correspondence R:QS⊆N∆ε(BS)⇒ QS⊆N∆ε(BS)with β7→ Q(S,π∗)Rε S,π∗(β)is upper hemicontinuous. The properties of the correspondence Rthat we have proved in Propositions 4.5, 5.3, and 5.4 allow us to apply Kakutani’s fixed point theorem, so that we obtain our main result. Theorem 5.5. Let vbe a hedonic game, and let Ebe an effectivity correspondence that satisfies H1–H4, let ρ= (ρπ)π∈Πbe a collection of bijections between 1,...,2N−1and P(N), and let ε > 0. The associated coalition formation game N, QS∆ε(BS),(ui)i∈Nobtains a weak ε-equilibrium. 6 Discussion 6.1 Better Responses versus Weak Better Responses We have seen that the definition of weak ε-equilibria ensures stability against oneshot deviation, but not necessarily against deviations at more than one state. So, the coalition formation games that we have defined in Section 4 lack some kind of “one-shot-principle”. We shall provide an example here where a coalition does not have a one-shot deviation, i.e., is playing a weak best response, but can find a better response by changing its behavior at two states. 8Recall that a compact-valued correspondence R:β7→ R(β) is upper hemicontinuous if for each converging sequence (βn)n∈Nwith limn→∞ βn=β, and each sequence (γn)n∈Nwith γn∈R(βn) there is a converging subsequence (γnk)k∈Nwith γ= limk→∞ γnk∈R(β). 16 Let N={1,2,3}and vbe the hedonic game given by v({1}) = 20, v({2}) = 0, v({3}) = 0, v({1,2}) = (17,14), v({1,3}) = (17,5), v({2,3}) = (15,10) and v(N) = (1,18,0). Let Ebe the unique effectivity correspondence that is defined by the residual map γin Example 3.1. Define three biljections ρ1, ρ2, ρ3:{1,· · · ,7} → P(N) by (ρ1(1), ρ1(2), ρ1(3), ρ1(4), ρ1(5), ρ1(6), ρ1(7)) = ({1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}), (ρ2(1), ρ2(2), ρ2(3), ρ2(4), ρ2(5), ρ2(6), ρ2(7)) = ({1,2,3},{2,3},{1,3},{1,2},{3},{2},{1}), (ρ3(1), ρ3(2), ρ3(3), ρ3(4), ρ3(5), ρ3(6), ρ3(7)) = ({1,2},{1,3},{2,3},{1,2,3},{1},{2},{3}). Let the set of partitions by Π = {π1, π2, π3, π4, π5}, where π1={{1},{2},{3}}, π2={{1,2},{3},π3={{2},{1,3}},π4={{1},{2,3}}, and π5={N}. Define the collection (ρπ)π∈Πby ρπ1=ρπ3=ρπ5=ρ1,ρπ2=ρ2and ρπ4=ρ3. Let S0={1,2}, which is the coalition for which we shall find a profitable deviation which is not one-shot. Define for all T6=S0the behavior βTby βT(π) =    πif T∈π 19 20π+1 20π0if T /∈πand T∈E(π, π0). Recall that this uniquely defines βTas for each T∈P(N) and each πwith T /∈π there is exactly one π0with T∈E(π, π0). Behavior βprescribes for any T6=S0at any πwith T6∈ πto form and deviate from πto π0with probability 1 20 and to remain at πwith probability 19 20. We define the behavior of S0by the probabilities with which they stay at each state. Surely, coalition S0leave πif and only if π6=π2. So, let ε > 0, let p= (p1, . . . , p5) with pk∈[ε, 1−ε] for k= 1,3,4,5, and p2= 1, and define behavior βp S0 by βp S0(πk|πk) = pkfor k= 1,...,5. Then βp S0is uniquely determined by p. The transition matrix of the Markov process associated with profile βp S0, β−S0is P=         0.857375p11−p10.05p10.0475p10.045125p1 0.0835940625 0.7737809375 0.045125 0.0475 0.05 0.0975 0.9025 (1 −p2) 0.81450625p20.045125p20.04286875p2 0.08799375p31−p30.05p30.81450625p30.0475p3 0.142625 0.857375 (1 −p4) 0.04286875p40.0407253125p40.7737809375p4         . The stationary distribution of P,µ, is given by µ(πk) = ¯µ(πk) Pk l=1 ¯µ(πl), where ¯µ(π1) = 2.493644800 1022 −1.929915474 1022p2−1.907014861 1022p3 17 −1.779404668 1022p4+ 1.475886395 1022p2p3+ 1.377081367 1022p2p4 −1.052956848 1022p2p3p4+ 1.360599508 1022p3p4 µ(π2) = 2.621440000 1023 −2.277208106 1023p1−2.135179264 1023p2 −2.135179264 1023p3−2.028420301 1023p4+ 1.137161257 1023p1p2p3p4 + 1.843589840 1023p1p2+ 1.733202232 1023p2p3+ 1.647343515 1023p2p4 −1.487493405 1023p1p2p3−1.412391146 1023p1p2p4−1.333534269 1023p2p3p4 −1.411324821 1023p1p3p4+ 1.748510978 1023p1p4+ 1.647089962 1023p3p4 + 1.842392792 1023p1p3 µ(π3) = 1.182924800 1022 −9.029079172 1021p1−9.012404428 1021p3 −8.591357328 1021p4−4.997785432 1021p1p3p4+ 6.560586496 1021p1p4 + 6.545126296 1021p3p4+ 6.878677184 1021p1p3 µ(π4) = 1.245184000 1022 −9.632257218 1021p1−9.608306688 1021p2 −9.101201612 1021p4+ 7.432904694 1021p1p2+ 7.023069492 1021p2p4 −5.434523952 1021p1p2p4+ 7.042336316 1021p1p4 µ(π5) = 1.310720000 1022 −1.026078331 1022p1−1.016879124 1022p2 −1.008443392 1022p3+ 7.960009508 1021p1p2+ 7.823266076 1021p2p3 −6.123530024 1021p1p2p3+ 7.893891288 1021p1p3. The payoffs of players 1 and 2 are u1βp S0, β−S0= 20(µP(π1) + µP(π4)) + 17(µP(π2) + µP(π3)) + µP(π5) u2βp S0, β−S0= 14µP(π2) + 10µP(π4) + 18µP(π5). Let now ε=1 20 and define p∗by p∗ k= 1 −εfor k= 1,3,4,5 and p∗ 2= 1. Then d dp∗ 1 u1βp∗ S0, β−S0>0d dp∗ 1 u2βp∗ S0, β−S0<0 d dp∗ 3 u1βp∗ S0, β−S0>0d dp∗ 3 u2βp∗ S0, β−S0<0 d dp∗ 4 u1βp∗ S0, β−S0>0d dp∗ 4 u2βp∗ S0, β−S0<0 d dp∗ 5 u1βp∗ S0, β−S0<0d dp∗ 5 u2βp∗ S0, β−S0>0. 18 That is, any change in any p∗ kmakes exactly one player better off and one player worse off. Thus, p∗induces as weak best response. Finally, let ε=1 20 and define ˆpby ˆp1= ˆp4= 1 −εand ˆp3= ˆp5=ε. Then u1βˆp S0, β−S0= 17.72703770896 >16.2479670393 = u1βp∗ S0, β−S0 u2βˆp S0, β−S0= 9.19781147654 >7.4664207782 = u2βp∗ S0, β−S0 That is, by changing their behavior both at π3and at π5both members of S0can strictly improve their payoffs. 6.2 Conclusion We have shown that for the class of hedonic games there is a farsighted solution which is closely related to the rational expectation functions of Karos and Robles (2021) and Dutta and Vohra (2017). This solution incorporates the expectation of arbitrarily small but positive probabilities of making mistakes on the side of coalitions. The mathematical backbone lies in Theorem 5.1 where we show that the stationary distribution of a convex combination of irreducible Markov processes whose transition matrices differ in at most one row is a convex combination of the respective stationary distributions. This observation can also be applied to other strategic games in which the Markov process depends on mixed strategy profiles and one is interested in oneshot deviations. A Proofs Proof of Lemma 2.1.Surely, Px,y ≥0 for all x, y ∈X. Moreover, X y∈X Px,y =X y∈X p(y|x) =X y6=x 2|N|−1 X l=1 φl(y|x)Y h<l φh(x|x) + 2|N|−1 Y l=1 φh(x|x) = 2|N|−1 X l=1 Y h<l φh(x|x)X y6=x φl(y|x) + 2|N|−1 Y l=1 φh(x|x) 19 = 2|N|−1 X l=1 Y h<l φh(x|x)1−φl(x|x)+ 2|N|−1 Y l=1 φh(x|x) = 2|N|−1 X l=1 l−1 Y h=1 φh(x|x)− l Y h=1 φh(x|x)!+ 2|N|−1 Y l=1 φh(x|x) = 1 − 2|N|−1 Y l=1 φh(x|x) + 2|N|−1 Y l=1 φh(x|x) = 1, as required.  Proof of Lemma 3.2.Let πbe a partition and Sbe a coalition. If S=∅or S∈π, then π0=πby H1 and H2. So, let S6=∅and S /∈π. Then, by H2 and H4, S∈E(π, π0) only if π0={τ(i|π, S)}i∈π(S)∪ {T∈π:T∩S=∅} .(7) By H3, there is some π0with S∈E(π, π0). Thus, S∈E(π, π0) if and only if π0 satisfies (7). This proves the second part of the lemma. Eis now uniquely defined as E(π, π0) = (S∈π0:π(i)∈π0for all i∈N\π(S) = ∅ and π0(i) = τ(i|π, S) for all i∈π(S)),(8) which completes the proof.  Proof of Lemma 3.3.Let π∗={{i}}i∈N. It is sufficient to show that the claim is true for any πand π=π∗, as well as for any πand π=π∗. To see the first case, observe that for any i, j ∈Nand any partition πwith {j} ∈ π, there is π0 with {i} ∈ π0and {i} ∈ E(π, π0) by H3. Moreover, {i} ∈ π0by H1 and {j} ∈ π0 by H2. Thus, the successive deviation of singletons will lead from πto π∗. On the other hand, let π={P1, . . . , Pm}, and let πl=nP1, . . . , Pl,{{i}}i∈∪m h=l+1Phofor all l= 1, . . . , m. Then P1∈E(π∗, π1) and Pl∈Eπl−1, πlfor l= 1, . . . , m by H2. As π=πm, the proof is complete.  Proof of Lemma 4.3.We first show that the Markov process associated with Φβ is irreducible. To this end note that 0 < φl β(π|π)<1 for all π∈Π and all 20 l= 1,...,2N. That is, at each partition πand for each coalition S, there is a positive chance that all coalitions preceding Swill stay at x, so that Swill be able to implement its move. In particular, there is a strictly positive chance that Swill actually implement its move out of π. This is, particularly, true for the singletons and the coalitions in the proof of Lemma 3.3. Thus, for any π, π0∈Π, there is a positive chance of a move from πto π0, that is, (Pm)π,π0>0 for some m∈N. Hence, the process associated with Φβis irreducible. By construction of β0the transition matrices of the processes Φβand Φβ0 S,β−Sdiffer at most in π. Since |N| ≥ 3 there are at every partition π0at least two coalitions that can deviate: if πis the grand coalition, every singleton can deviate; if πcontains only singletons, then at least all pairs can deviate; and if πneither consists only of singletons nor the grand coalition, then the grand coalition and at least one singleton can deviate. As the order in which the deviations of singletons and the coalitions in the proof of Lemma 3.3 is irrelevant, one can always find a path from πto ¯πthat does not involve a deviation by Sat π. Hence, this path will occur with possible probability, which makes Φβ0 S,β−S irreducible.  Proof of Proposition 4.4.By (3) it is sufficient to show that the map β7→ µΦβ is continuous. By Theorem 12.13 in Stokey and Lucas (1999), and since the state space Π is finite and the Markov process associated with the expectation function Φβ is irreducible, it is sufficient to show that the map β7→ PΦβis continuous, where PΦβ is the corresponding transition matrix. But this is clear, since by (1) and (4) it holds that PΦβ π,π0=  P2|N|−1 l=1 βρπ(l)(π0|π)Qh<l βρπ(h)(π|π) if π06=π, Q2|N|−1 l=1 βρπ(l)(π|π) if π0=π, which is continuous in βfor all π, π0∈Π.  Proof of Proposition 4.5.Let S∈P(N), let β∈QT⊆N∆ε(BT), and π∈Π be fixed but arbitrary. Let i∈Sand recall from Proposition 4.4 that uiis continuous on QT⊆N∆ε(BT). For t∈[ε, 1−ε] let βt S(π0|π0) =    tif π0=π βS(π0|π0) otherwise 21 and recall from Corollary 4.1 that βt Sis uniquely determined by t. As βt Scontinuously depends on t, it holds that ˆui(t) = ui(βt S, β−S) continuously depends on t; and as [ε, 1−ε] is compact, ˆuiobtains its maximum at some t∗. By construction, there is no better response than βt∗ Sagainst β−Sat πas there is no behavior that would provide a higher payoff to i. Hence, βt∗ S∈Rε S,π (β), and the latter is nonempty. For compactness it is sufficient to show closeness as ∆ε(BS) is compact. For this purpose, let (βn S)n∈Nbe a converging sequence in Rε S,π (β) with limit β∗ S. Assume that β∗ S/∈Rε S,π (β), i.e., assume that there is βS∈∆ε(BS) such that βS(π0) = β∗ S(π0) for all π06=πand ui(βS, β−S)> ui(β∗ S, β−S) for all i∈S. Let δ= mini∈Sui(βS, β−S)− ui(β∗ S, β−S)>0. By the continuity of uithere is c > 0 such that for all β0 S∈ ∆ε(BS) with kβ∗ S−β0 Sk< c it holds that |ui(β∗ S, β−S)−ui(β0 S, β−S)|<1 2δfor all i∈S. As (βn S) is converging, there is msuch that kβ∗ S−βn Sk< c for all n≥m, so that |ui(β∗ S, β−S)−ui(βn S, β−S)|<1 2δfor all n≥mand all i∈S. In particular, ui(βn S, β−S)< ui(β∗ S, β−S)+ 1 2δ≤ui(βS, β−S)−1 2δfor all i∈S. But this is impossible since βn S∈Rε S,π (β). Thus, β∗ S∈Rε S,π (β).  Proof of Theorem 5.1.Surely, the new Markov with transition matrix rP+(1 −r)Q is irreducible. Thus, by Proposition 2.2 it has a unique stationary distribution, and the stationary distribution is the unique normalized left eigenvevtor to eigenvalue 1. So, it is sufficient to show that νis a normalized left eigenvevtor to eigenvalue 1. By construction, Px∈Xν(x) = 1 and ν(x)>0 for all x∈X. In particular, since rµ (x∗) + (1 −r)λ(x∗) = ν(x∗)>0, we have (1 −r)tλ (x∗)−r(1 −t)µ(x∗) =(1 −r)tλ (x∗)−r(1 −t)µ(x∗) rµ (x∗) + (1 −r)λ(x∗)(rµ (x∗) + (1 −r)λ(x∗)) = ((1 −t)t−t(1 −t)) (rµ (x∗) + (1 −r)λ(x∗)) = 0. Thus, νT(rP + (1 −r)Q)y=X x∈X (tλ(x) + (1 −t)µ(x)) (rPx,y + (1 −r)Qx,y) =rtλ(y) + (1 −r) (1 −t)µ(y) 22 + (1 −r)tX x∈X λ(x)Qx,y +r(1 −t)X x∈X µ(x)Px,y =ν(y) + (1 −r)tX x∈X λ(x) (Qx,y −Px,y) +r(1 −t)X x∈X µ(x) (Px,y −Qx,y) =ν(y) + (1 −r)tλ (x∗) (Qx∗,y −Px∗,y) −r(1 −t)µ(x∗) (Qx∗,y −Px∗,y) =ν(y)+(Qx∗,y −Px∗,y) ((1 −r)tλ (x∗)−r(1 −t)µ(x∗)) =ν(y), which proves that νis the stationary distribution of αP + (1 −α)Q. Proof of Theorem 5.2.Let P=PΦ(βS,β−S), let P=PΦ(¯ βS,β−S), and observe that the corresponding Markov processes are irreducible by Lemma 4.3. Moreover, Pπ,π0= Pπ,π0for all π0∈Π and all π6=π∗. By construction we have βS=rβS+ (1 −r)¯ βS, and thus, for the transition probability of the Markov process that emerges from Φβ we find for all π0∈Π and all π6=π∗ PΦβ π,π0=Pπ,π0=rPπ,π0+ (1 −r)Pπ,π0. Let l∗be such that ρπ∗(l∗) = S. Then PΦβ π∗,π∗=rβS(π∗|π∗) + (1 −r)¯ βS(π∗, π∗)2|N|−1 Y l6=l∗ βρ(l)(π∗|π∗) =rPπ∗,π∗+ (1 −r)Pπ∗,π∗. Moreover, for π6=π∗we have PΦβ π∗,π =X l<l∗ βρ(l)(π|π∗)Y h<l βρ(h)(π∗|π∗) +rβρ(l∗)(π|π∗) + (1 −r)¯ βρ(l∗)(π|π∗)Y h<l∗ βρ(l)(π∗|π∗) +X l>l∗ βρ(l)(π|π∗)Y h<l,h6=l∗ βρ(h)(π∗|π∗) 23