Coalition formation under power relations

Razin, Ronny; Piccione, Michele Article Coalition formation under power relations Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Razin, Ronny; Piccione, Michele (2009) : Coalition formation under power relations, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New York, NY, Vol. 4, Iss. 1, pp. 1-15 This Version is available at: https://hdl.handle.net/10419/150122 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/3.0 Theoretical Economics 4 (2009), 1–15 1555-7561/20090001 Coalition formation under power relations M P Department of Economics, London School of Economics R R Department of Economics, London School of Economics We analyze the structure of a society driven by power relations. Our model has an exogenous power relation over the set of coalitions of agents. Agents determine the social order by forming coalitions. The power relations determine the ranking of agents in society for any social order. We study a cooperative game in partition function form and introduce a solution concept, the stable social order, which exists and includes the core. We investigate a refinement, the strongly stable social order, which incorporates a notion of robustness to variable power relations. We provide a complete characterization of strongly stable social orders. K. Power, coalition formation, stability. JEL . D0, D7. 1. I Power relations are a fundamental component of human interaction. In social environments, two types of power shape a significant number of human relations: individual power and group power. Individual power manifests itself in one-to-one relations and generally originates from material or psychological strength. Group power manifests itself in interactions between sets of individuals or in one-to-one interactions between individuals belonging to different sets. The objective of this paper is to study theoretically the joint influence of individual and group power in the determination of social arrangements. Although the term “individual” usually refers to “one person,” in this paper “individuals” can be entities such as families, factions, or other groupings, the unity of which is solid and based on exogenous, non-strategic factors such as blood, loyalty, or friendship. Henceforth, such individuals or families are referred to as “agents.” We are interested in analyzing the structure of a society driven by power relations. Our model has the following basic ingredients. Power is represented by an exogenous binary relation over coalitions. Agents determine the social order by forming coalitions. Michele Piccione: [email protected] Ronny Razin: [email protected] We wish to thank John Moore, Neeve Park, Ariel Rubinstein, and especially Martin Osborne and three referees who provided several valuable and constructive suggestions. We are grateful to William Lauderdale and Iddo Tuvnel for their support. Copyright c2009 Michele Piccione and Ronny Razin. Licensed under the Creative Commons AttributionNonCommercial License 3.0. Available at http://econtheory.org. 2Piccione and Razin Theoretical Economics 4 (2009) The power relation and the structure of the social order determine the ranking of agents in society. Coalitions, in our model, are held together only by strategic considerations. We assume that the objective of each agent is to maximize his/her position in the societal ranking. We study a cooperative game in partition function form and introduce a solution concept, the stable social order. We show that for any power relation, the set of stable social orders is not empty and contains the core. We investigate a refinement, the strongly stable social order, which requires that a social order be stable for all power relations. We provide a complete characterization (Theorem 1) of strongly stable social orders. Our framework is too abstract to fit specific historical examples. However, several implications of our results are broadly consistent with stylized historical and political anecdotes. In particular, in a strongly stable social order: 1. Powerful coalitions are large and each coalition is immune from the threat of a unified challenge coming from all less powerful coalitions. 2. Leaders are critical. The elimination of society’s most powerful member causes a regime switch: almost all the members of the coalition in power divide into smaller coalitions and significantly drop in status. As we shall see, the robustness criterion implicit in strongly stable social orders is rather demanding. Hence, we conclude the paper by focusing on social orders that are stable (not necessarily strongly stable) for special power relations. 1.1 A simple example As an illustration of our model and of stable social orders, consider a special case in which the power of individual agents and coalitions is modeled as follows. Each agent iis represented by a number q(i); agent iis more powerful than agent jif and only if q(i)>q(j). When comparing disjoint coalitions of individuals, the power relation is determined additively, i.e., coalition Ais more powerful than coalition Bwhenever Pi∈Aq(i)>Pi∈Bq(i). Suppose that the numbers q(i)are decreasing in i; that is, agent 1 is the most powerful, agent 2 is the second most powerful, and so on. Also suppose that all numbers q(i)are approximately the same; that is, a coalition of magents is more powerful than any coalition with fewer than magents, and that no two coalitions have the same power. The agents care only about their social ranking, which is determined by their own individual power and by the power of the coalitions to which they belong. Suppose, for example, that the set of agents is I={1,2,3,4,5,6,7}, and consider the partition (social order) ˆ Σ = {{1,3,5,7},{2,6},{4}}. Given the above power relation, the most powerful coalition is {1,3,5,7}and the second most powerful coalition is {2,6}. The social ranking of agents in ˆ Σis derived as follows. First, agents in a more powerful coalition are ranked higher than agents in a less Theoretical Economics 4 (2009) Coalition formation under power relations 3 powerful one. Second, within a coalition, a more powerful agent is ranked higher than a less powerful one. Thus, agent 1 is ranked first as he is in the most powerful coalition and is the most powerful individual in this coalition. Agent 3 is ranked second, agent 2 is ranked fifth and so on. We analyze the stability of partitions such as ˆ Σ. One possible stability notion is the core. We say that a social order is in the core if there does not exist a subset of agents who can strictly improve their social rank by forming a new coalition. The above social order is not in the core. If agents 3, 5, and 7 form a new coalition C0dropping agent 1, they strictly improve their social rank in the resulting social order ˆ Σ0={{3,5,7},{2,6},{1},{4}}. Piccione and Rubinstein (2004) show, for the above power relation, that the core is empty when N>6. In this paper, we provide a solution concept for which existence is not problematic and that offers interesting insights into coalition formation in the presence of power relations. We follow the traditional route of reducing the set of profitable deviations by allowing counter-deviations. In particular, our stable social order incorporates two features: (i) A recursive definition of “durable” deviations and counter-deviations. (ii) A sequential notion of counter-deviations: members of a deviating coalition do not participate in any immediately subsequent counter-deviation. The social order ˆ Σis stable according to our definition. In particular, (all) members of the coalition C0={3,5,7}in ˆ Σ0are made worse off by the “durable” counter-deviation C00 ={1,2,4,6}. Although the formal definition of durable counter-deviations is recursive, for the moment it is sufficient to note that C00 is durable in that agents 1, 2, 4, and 6 are better off than they are in ˆ Σ0and cannot subsequently be made worse off by any coalition of agents who are not in C00. As we shall see, the social order ˆ Σis also strongly stable. That is, it is stable for any selection of the numbers q(i)that are decreasing in i; irrespective of the cardinal properties of q, the agents in C0are made worse off by the counter-deviation C00 and the agents in C00 cannot be made worse off. 1.2 Related literature This paper is obviously part of the vast literature on cooperative games, solution concepts, and coalition formation. We refer the reader to Ray (2007) for a detailed and insightful overview. Games in partition function form are studied in Thrall and Lucas (1963), Myerson (1977), and Ray and Vohra (1999). Our solution concept is related to the notion of the “Bargaining Set” of Aumann and Maschler (1964) and, in particular, to a modification due to Dutta et al. (1989); for other notions of stability see Chwe (1994), Ray and Vohra (1997), Greenberg (1990), and Diamantoudi and Xue (2007). Formal models of power relations are analysed in Jordan (2006a,b), Piccione and Rubinstein (2007), and 4Piccione and Razin Theoretical Economics 4 (2009) Acemoglu et al. (2008). Jordan (2006a) considers a model in which power is endogenous and is affected by the wealth that is appropriated from other agents through the exercise of power. Jordan (2006b) incorporates dynamic factors such as histories into the notion of stability, thus introducing a notion of “legitimacy” into the appropriation process. Piccione and Rubinstein (2007) study a model in which the allocation of resources is driven by exogenous power. In this paper, we report a result from Piccione and Rubinstein (2004) that is omitted from Piccione and Rubinstein (2007). Acemoglu et al. (2008) also assume that power is exogenous and study the formation of coalitions under an allocation rule for which the winning coalition takes all. 2. T  The set of agents is I={1,...,N}. Although the term “agent” is commonly associated with “one person”, in our model an agent can be a clan, a family, or any group of people held together by non-strategic factors. The agents are ordered by an exogenous power relation. We define a “coalitional” power relation over sets of agents as a binary relation Pbetween subsets (coalitions) of agents A,B⊂Isuch that A∩B=∅. The relation Pis asymmetric, acyclic,1and such that either A P B or B P A. The statement A P B is interpreted as “coalition Ais more powerful than coalition B.” We assume that A P ∅whenever A⊂Iis non-empty. Note that two disjoint coalitions cannot be equally powerful. Without loss of generality we assume that Pagrees with the naming of agents {1,...,N}. That is, {1}P{2},{2}P{3}, ..., {N−1}P{N}. In what follows, quantifiers such as “for any power relation P” should be interpreted as “for any power relation Pfor which {1}P{2},{2}P{3},...,{N−1}P{N}.” With some abuse of notation we sometimes replace {i}P{j}with i P j . We define a social order as a partition of the set of agents. We often denote a social order by Σand adopt the convention that in the social order {C1,...,CK},CiP Cjif and only if i<j. The power relation Pis separable if, for any subsets of agents A1,A2,A3, and A4such that Ai∩Aj=∅for i6=j,A1P A3and A2P A4implies that (A1∪A2)P(A3∪A4) Consider two coalitions of agents A,B⊂Isuch that A∩B=∅. Coalition A dominates coalition Bif there exists a subset C⊂Aand a one-to-one mapping σ:B−→ Csuch that i P σ−1(i)for any i∈σ(B). The next lemmas are useful later. L 1.Suppose P is separable. If A P B and C ⊂B, then A P C. P. Suppose not. A contradiction is obtained by defining A1=C,A2=B\C,A3=A, and A4=∅. 1The relation Pis acyclic if, given any collection Θof subsets of agents, there exists A∈Θsuch that B P A for no B∈Θ. Theoretical Economics 4 (2009) Coalition formation under power relations 5 L 2.Suppose P is separable. Then A P B whenever A dominates B. This result follows from a simple application of separability. The power relation Pis monotonic if for any two subsets of agents A1and A2such that A1∩A2=∅,A1P A2implies that ((A1∪{i})\{j})P((A2∪{j})\{i}) whenever i∈A2and i P j . L 3.If P is separable, then P is monotonic. P. Consider two subsets of agents A1and A2such that A1∩A2=∅and A1P A2. Take i∈A2and any jsuch that i P j . First suppose that (A2\{i})P(A1\{j}). Then, by separability, ((A2\{i})∪{i})P((A1\{j})∪{j}). Since A1⊂(A1\{j})∪{j}, a contradiction is obtained by Lemma 1. Hence (A1\{j})P (A2\{i}). The claim follows by separability.  In the remainder of the paper, we assume that power relations are separable. Finally, we define the social ranking that is induced by a social order. Given a power relation P and a social order Σ = {C1,...,CK}, let VP i(Σ) denote agent i’s position in the ranking induced by Σ. That is, VP i(Σ) = 1 indicates that agent iis ranked the highest, VP i(Σ) = 5 indicates that agent iis ranked fifth, and so on. Formally, VP i(Σ) assigns to each agent i an integer in {1,2,...,N}and satisfies VP i(Σ) <VP j(Σ) if and only if either i,j∈Ckfor some kand i P j or i∈Ck,j∈Ck0, and CkP Ck0. (*) We say that agent iis ranked “higher” in Σthan in Σ0whenever VP i(Σ) <VP i(Σ0). We assume that each agent’s preferences over social orders are determined by the induced social rankings. In particular, each agent strictly prefers to be ranked higher in the social ranking to being ranked lower. That is, each agent istrictly prefers the social order Σ to the social order Σ0if and only if VP i(Σ) <VP i(Σ0). We also say, given Σ = {C1,...,CK}, that Ckis ranked kth and that Ckis ranked higher than Ck0whenever k<k0(recall that CkP Ck0by convention). 3. S We introduce a cooperative solution concept for social orders that we call stable social order. For any subset Cof agents who deviate from a social order Σ = {C1,...,CK}, with some abuse of the conventional notation let ΣüCbe the partition {C1\C,C2\C,..., CK\C,C}. We say that a deviation by Cfrom Σis profitable if VP i(Σ üC)<VP i(Σ) for any i∈C. 6Piccione and Razin Theoretical Economics 4 (2009) Our stability notion is based on the durability of deviations by coalitions of agents. Two criteria need to be satisfied by a durable deviation. First, all members in the deviating coalition are better off. Second, there does not exist a durable counter-deviation that makes some member in the original deviating coalition worse off than in the social order prior to the deviation. It should be noted that members of the deviating coalition are excluded from the counter-deviating coalition. We now define durable deviations. Let Ξbe the set of social orders and Ibe the set of all possible subsets of I. Define the correspondence SP:Ξ =⇒ I such that C∈ S P(Σ) if and only if (a) Cis a profitable deviation from Σ (b) there does not exist C0∈ S P(Σ üC)such that (i) C∩C0=∅ (ii) VP i((Σ üC)üC0)) >VP i(Σ) for some i∈C. A deviation Cfrom a social order Σis durable if C∈ S P(Σ). The following proposition shows that the mapping SP:Ξ =⇒ I exists and is unique, notwithstanding its self-referential nature. P 1.There exists a unique correspondence SP:Ξ =⇒ I that satisfies (a) and (b). P. Given a social order Σand a coalition Cwith a profitable deviation from Σ, let ˜ S(Σ,C) = {C0⊂I: (i) C∩C0=∅ (ii) C0is a profitable deviation from ΣüC. (iii) VP i((Σ üC)üC0)) >VP i(Σ) for some i∈C}. Consider all finite sequences {Bt}τ t=0of subsets of agents such that •B0=C •Σ0= Σ,Σt+1= ΣtüBt •Bt∈˜ S(Σt−1,Bt−1),Bt∩Bt−1=∅for t>0 •either ˜ S(Σt−1,Bt−1)6=∅for any t≤τand ˜ S(Στ,Bτ) = ∅, or ˜ S(Σt−1,Bt−1)6=∅ for any tand τ=∞. Note that, by (ii) and (iii) in the definition of ˜ S, each member of Btis better off in Στ+1than in Στand that at least one member of Btis worse off in Στ+2than in Στ. Hence, BtP Bt−1for every t>0. Thus, by acyclicity, there exists a finite bound for τthat is common to all sequences {Bt}τ t=0. Since ˜ S(Στ,Bτ) = ∅, if B∈ S P(ΣτüBτ) then B∩Bτ6=∅. Hence, Bτ∈ S P(Στ)and Bτ−1/∈ S P(Στ−1). Consider now a directed graph in which each Btis a node and a directed edge links Btto Bt+1if and only if Bt Theoretical Economics 4 (2009) Coalition formation under power relations 7 immediately precedes Bt+1in the same sequence. If none of the immediate successors of Btis in SP(ΣtüBt), then Bt∈ S P(Σt). If at least one immediate successor of Btis in SP(ΣtüBt), then Bt/∈ S P(Σt). Proceeding by backward induction in this fashion, we determine uniquely whether C∈ S P(Σ). The example in Section 1.1 clarifies the intuition behind this result. The coalition C00 is a durable deviation from ˆ Σ0since the agents in C00 cannot be made worse off by any coalition of agents who are not in C00. Working backwards, one deduces that the coalition C0is not a durable deviation from ˆ Σ. We are now ready to define the stability of a social order. D 1.A social order Σ = {C1,...,CK}is stable for a power relation Pif SP(Σ) = ∅. One can refine the stability notion by requiring that social orders are stable for any power relation. D 2.A social order Σ = {C1,...,CK}is strongly stable if SP(Σ) = ∅for any power relation P. The requirements for a strongly stable social order are severe but can be partially justified on robustness grounds. It is natural to think of the power of coalitions as more variable and harder to assess than the power of individuals.2The aggregate strength of a group can depend on characteristics of social interaction that are unobservable and difficult to evaluate. 4. T   In this section, we introduce and prove our main result. First we introduce some special social orders. The social order Σ∗is constructed according to a simple procedure. First, select the odd-indexed agents to form the strongest coalition. Re-index the remaining agents so that the most powerful agent is indexed as agent 10, the second most powerful is indexed as agent 20and so on. Select the odd indexed agents from this set to form the second strongest coalition. Repeat this procedure until no agents are left. For example, when N=8, Σ∗={{1,3,5,7},{2,6},{4},{8}}. Formally, given a set of numbers Q={a,b,c,d,...}and a number δ, let δQdenote the set {δa,δb,δc,δd,...}. Let O+be the set of the positive odd integers. Define the social order Σ∗as the social order {C∗ 1,...,C∗ K}such that C∗ k=I∩2k−1O+, where Kis the largest kfor which C∗ k=I∩2k−1O+is non-empty. Consider the class Fof social orders derived by modifying Σ∗recursively in the following fashion. A social order Σ = {C1,...,CK}is in Fif and only if 1. C1=C∗ 1or C1=C∗ 1∪{N} 2. for k≥2, Ck={C∗ k\∪k−1 j=1Cj}or Ck={C∗ k\∪k−1 j=1Cj}∪{max(I\∪k−1 j=1Cj)}. 2Recall that 1P2P···P N for any Pin the definition of strongly stable social orders. 8Piccione and Razin Theoretical Economics 4 (2009) For N=8, the social order {{1,3,5,7,8},{2,6},{4}} is in Fas it is obtained by adding agent 8 to C∗ 1. It is worth noting two features common to the social orders in F. First, the coalitions are highly differentiated in that agents who are contiguous in power generally belong to different coalitions: with the possible exception of the two least powerful agents, for any two agents xand yin any coalition Cfor whom x P y , there exists an agent znot in Csuch that x P z and z P y . Second, any coalition Cdominates the union of all coalitions that are less powerful than C. T 1.A social order Σis a strongly stable social order if and only if Σ∈ F. The proof of this result is constructive. We first prove that Σ∗is stable for any P(the proof that any Σ∈ F is stable for any Pis analogous and thus omitted). We then prove that any strongly stable social order must be in F. P  T .We first establish some preliminary results. C 1.For any j , C∗ jP(∪K i=j+1C∗ i). This result is proved by construction. C 2.Fix some partition Σsuch that C∗ 1∈Σand 2∈C2. For any C such that C∗ 1∩C6=∅ and V P i(Σ üC)<VP i(Σ) for each i ∈C , there exists C0with C 0∩C=∅such that (i) C0is a profitable deviation from Σ∗üC (ii) V P i((Σ∗üC)üC0)) >VP i(Σ∗)for some i ∈C (iii) C0P((I\C)\C0). P. Denote C∗ 1={y1,...,yL}and C={x1,...,xM}. Construct C0={z1,...,zL}by first letting z1=y1=1. Suppose we have defined zifor all i⩽jfor some j⩾1. Define zj+1as the smallest isuch that (i) i/∈C, (ii) i6=z1,...,zj, (iii) VP i(ΣüC)>j+1, and (iv) i≤yj+1. We now show that this algorithm is well defined. We consider several cases. Case 1: In ΣüC,Cis ranked first and C∗ 1\Cis ranked second. First note that either z2=2, or 2 ∈Cand therefore 3 /∈Cimplying z2=3. Therefore, z2⩽y2. Now consider zj,j>2, given that z1,...,zj−1have been selected using the algorithm. Let Gjbe the set of agents smaller than or equal to yj=2j−1. By hypothesis, j−1 agents in Gjhave already been allocated to C0. We now show that the set Hj={r∈Gj\ {z1,...,zj−1}:r/∈Cand VP r(Σ üC)>j}is not empty. Since #Gj\ {z1,...,zj−1}=j, it is impossible that all agents in Gj\ {z1,...,zj−1} are in C. If so, agent 2j−1 would also be in Cbut ranked at or lower than the jth position in ΣüC, contradicting the definition of C. Therefore, there must exist at least one agent i∈Gj\{z1,...,zj−1}such that i/∈C. Consider then the agent r∗in Gj\{z1,...,zj−1}who is ranked lowest in ΣüC. Agent r∗is not in Cas otherwise Gj\ {z1,...,zj−1} ⊂ C. Since C∗ 1\Cis ranked second, agent r∗must be ranked lower than agent 1 in ΣüC. Since agent 1 is not in Gj\ {z1,...,zj−1}and #Gj\{z1,...,zj−1}=j,VP r∗(ΣüC)>j. Hence, Hjis not empty. Define zj=minHj. Theoretical Economics 4 (2009) Coalition formation under power relations 15 Ray, Debraj and Rajiv Vohra (1997), “Equilibrium binding agreements.” Journal of Economic Theory, 73, 30–78. [3] Ray, Debraj and Rajiv Vohra (1999), “A theory of endogenous coalition structures.” Games and Economic Behavior, 26, 286–336. [3] Thrall, Robert M. and William F. Lucas (1963), “n-person games in partition function form.” Naval Research Logistics Quarterly, 10, 281–298. [3] Submitted 2008-4-1. Final version accepted 2008-10-17. Available online 2008-10-17.