A note on the core of TU-cooperative games with multiple membership externalities

Nax, Heinrich H. Article A note on the core of TU-cooperative games with multiple membership externalities Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Nax, Heinrich H. (2014) : A note on the core of TU-cooperative games with multiple membership externalities, Games, ISSN 2073-4336, MDPI, Basel, Vol. 5, Iss. 4, pp. 191-203, https://doi.org/10.3390/g5040191 This Version is available at: https://hdl.handle.net/10419/167929 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. http://creativecommons.org/licenses/by/4.0/ Games 2014,5, 191-203; doi:10.3390/g5040191 OPEN ACCESS games ISSN 2073-4336 www.mdpi.com/journal/games Article A Note on the Core of TU-cooperative Games with Multiple Membership Externalities Heinrich H. Nax Department of Social Sciences, ETH Zürich, Clausiusstrasse 37-C3, Zürich 8092, Switzerland; E-Mail: [email protected]; Tel.: +41-44-632-05-94; Fax: +41-44-632-17-67. External editor: Anke Berger Received: 3 August 2014; in revised form: 19 September 2014 / Accepted: 10 October 2014 / Published: 21 October 2014 Abstract: A generalization of transferable utility cooperative games from the functional forms introduced by von Neumann and Morgenstern (1944, Theory of Games and Economic Behavior) and Lucas and Thrall (1963, Naval Research Logistics Quarterly, 10, 281–298) is proposed to allow for multiple membership. The definition of the core is adapted analogously and the possibilities for the cross-cutting of contractual arrangements are illustrated and discussed. Keywords: cooperative games; core; externalities; multiple membership; stability 1. Introduction The coalitional game as defined by [1] associates a unique worth with each coalition. Such a characterization is restrictive for many applications as it may be reasonable to allow the worth of one coalition to depend on the formation of other coalitions. Consequently, in [2]’s definition of a cooperative game, the worth of coalitions depends on the partitions of the rest of society, thus allowing different worth to be associated with each possible coalition depending on what coalitions are formed in the rest of society (“externalities”). This representation is still restrictive in the sense that it “presumes that coalitions are mutually exclusive, but in reality, a player might belong to multiple coalitions that interact with one another (e.g., a country might belong to both the United Nations and the European Union)” [3]. (See [4–6] for an international relations perspective on issue linkage through multilateral agreements.) This note introduces a functional representation of a cooperative game where coalitions can form in multiple spheres of interaction simultaneously such that each coalition in each sphere is associated Games 2014,5192 with a worth that depends on the overall coalition structure. Inherent to the model, therefore, is a new type of “cross externality”: the effect of forming coalitions across spheres. Such a formulation is relevant for many applications because, with multiple membership in the underlying application, a compartmentalized approach to the study of each sphere in isolation may lead to wrong conclusions concerning the stability of coalitional agreements. In a multiple membership setting, different layers may imbalance or balance each other depending on the structure of total spillovers (within and across spheres). Coalitions that seemed stable (or unstable) from the compartmentalized single-sphere viewpoint may turn out to be destabilized (stabilized) by the multi-sphere game. To assess the stability of candidate agreements, we adapt definitions of the core [7,8] of the von Neumann–Morgenstern game [1] as done for the Lucas–Thrall game [2] in [9], using an analogous “conjecture/ expectation formation approach” [10] to recover the Bondareva–Shapley theorem [11,12]. To achieve this, the set of feasible deviations is restricted to a specific class. Further inspection of the resulting non-emptiness constraints reveals that different types of cross externalities create further opportunities for the cross-cutting of contractual arrangements. Our analysis builds on the work of [13] who identify conditions for when non-emptiness of the core is facilitated through combining additively separable von Neumann–Morgenstern games (the single-sphere and no externalities case). (Not our lead example but some of our later examples are borrowed and generalized from theirs. See also [16] on the additivity of the core.) Our work also complements [14]’s generalization of [15] value in an environment like ours. The rest of this note is structured as follows. Next, the model is motivated by means of a multimarket competition game. In Sections 3 and 4, we introduce the general game, define its core, and illustrate the core characteristics at hand of examples and observations. We conclude with some remarks. 2. A Worked Example To motivate our model, we consider a multimarket Cournot economy with mergers and spillovers. (See, for example, [10,17,18] for single-market Cournot competition games in this spirit.) Example 1: A population of firms, N={f1, ..., fn}, competes in a multimarket industry, K={1, ..., m}, by setting production quantities. Each firm fis described by a vector of specializations, sf={s1 f, ..., sm f}, where each sk fis a real number representing firm f’s constant marginal costs in market kwhen no merger occurs. In any market k, coalitions of firms S⊆Nmay merge and form a new firm. The resulting industry configuration, M, describes the partitions in each market, {ρ1, ..., ρm}. Given M, any firm S∈ρk produces quantity qk Sin market k∈Kat cost Ck S(qk S;M) = ck S(M)×qk S+xk S(M). Fixed costs of merger. xk S(M), the fixed cost of merging Sin market k, is a real-valued function that depends on Min the following way: xk S(M) =      0if |S|= 1 κif |S|>1and there exists k06=k:S∈ρk0 λif |S|>1and there does not exist k06=k:S∈ρk0 Games 2014,5193 Marginal costs of production. Given any merger S⊆Nin market k, the firms in Sselect the lowest marginal cost firm to be the only active firm amongst them in market k. Hence, the marginal cost of production of S,ck S, as a result of the merger is given by ck S= min{sk f}f∈S. Given merger S⊆Nin market k, the marginal cost of production of any coalition C,ck C, in any other market k06=kis affected in the following way. For any C∈ρk0, we write ck0 Cfor min{sk0 f}f∈C,i.e., for the marginal cost of the lowest marginal cost firm amongst Cin market k0. For all Csuch that C∩S=∅, ck0 C=ck0 C. For all Csuch that C∩S6=∅, given some α∈(0,1), ck0 C= min{ck0 C;α×ck0 S+ (1 −α)×ck0 C}. The motivation for this marginal cost effect across markets is that firms connected by merger in one market may learn something about each others’ production technologies and thus also improve (to some extent) their respective production technologies even in markets where they remain unmerged. Demands. The demand of any product is the same in all markets (normalized to be equal-sized). Products are neither substitutes nor complements, meaning that all markets can be described by identical and independent linear demands. (These markets could be countries for example.) For any market k, therefore, pk= 1 −Qkwhere Qk≡X f∈N qk f. 2.1. Oligopoly Externalities A merger in a multimarket Cournot situation as introduced here has three different externality effects on the other firms in the same market and across markets. First, due to market consolidation, if merger occurs, the resulting quantity and price competition will change in that market, since the merged firms will be represented by the firm with the lowest marginal cost amongst them. Second, due to technology/knowledge spillovers across markets, the resulting quantity and price competition will also change in the markets where the merger did not occur because of the potential reduction in marginal costs (by how much is described by parameter α). Third, due to sharing of fixed costs merger, if the same merger were to occur in more than one market, the fixed costs of merger per market would decline. Due to the independence of the demand markets, the firms’ optimization problems, given any industry configuration, can be solved for each market separately. The adjustments of equilibrium quantities and prices following mergers in any given market, however, have an effect in not only that same market because both the technology spillovers and the fixed cost effects may additionally influence the optimization problems in the other markets. A traditional representation of a cooperative game could not make these effects explicit. We shall illustrate these effects in more detail with a numerical illustration. 2.2. Two-firm, Two-market Numerical Illustration Take a symmetric two-firm, two-market case with s1 f1= 4/9,s2 f1= 5/9,s1 f2= 5/9, s2 f2= 4/9(firm f1is specialized in market 1and firm f2is specialized in market 2). Merger costs are Games 2014,5194 λ= 2/108 > κ = 1/81. Choosing equilibrium outputs given the decision to merge in none, one, or both of the markets yields four cases: the no merger case, two one merger cases, and the full merger case. The equilibrium profits of these four cases are obtained by solving for the firms’ profit-maximization problems. Table 1 summarizes the competition. (Writing (1),(2) means “no merger" in the underlying market and writing (1,2) means “merger”.) Table 1. Numerical illustration. Industry configuration Profits (scaled ×81) market 1 market 2 market 1 market 2 mergers: none (1),(2) (1),(2) 4, 1 1, 4 market 1 (1,2) (1),(2) 4.75 (1 + α×1.7),(4 −α×1.2) market 2 (1),(2) (1,2) (4 −α×1.2),(1 + α×1.7) 4.75 full merger (1,2) (1,2) 5.25 5.25 The direct effect of merger in market 1is negative: profits fall from 1 + 4 = 5 to 4.75 if market 2is not merged and from 2.7 + 2.7=5.5to 5.25 if market 2is merged. If market 2is merged, the overall cross effect on market 2is positive: total profits in market 2rise from 4.75 to 5.25. If market 2is not merged, the profits in market 2 change from 1 + 4 = 5 to 5 + α×0.5. If market 2 is not merged, the individual cross effect is negative on the strong firm in market 2 (profits fall from 4to 4−α×1.2), and positive on the weak firm (profits increase from 1to 1 + α×1.7). The net total of the merger effects is therefore always positive if α×0.5>0.25,i.e., when α > 0.45. Since, ceteris paribus, mergers always decrease the worth of the merging market due to the high direct costs of merger, a partial view of one market suggests that merger is not in the firms’ interests. When both markets are analyzed simultaneously, however, the cross-market effects of mergers are internalized. Since the cross effects are net positive if α > 0.45, these effects would already render a single merger worthwhile overall. When no merger takes place, each firm’s profits from both markets are 4 + 1 = 5 and the total profits are 10. When one merger takes place, the firms can agree on sharing the total payoffs of (5 + α×0.5) + 4.75 = 9.75 + α×0.5. Under full merger, contracts can share the total profits of 5.25 + 5.25 = 10.5. Therefore, no contracts can be written that Pareto-improve on contracts that result in full merger and share the total profits efficiently, paying each player at least 5(which are the profits that each firm can guarantee itself from no merger). Whether a single merger already has a net-positive effect depends on whether α > 0.45 or not. 3. The Model This section generalizes the example to a representation of a cooperative game. Let N={f1, f2, ..., fn}be the fixed population of agents. Write ρfor a partition of Nand ρ(S)for the partition of some S⊂N. Let P(N)be the set of partitions of Nand P(S)the set of partitions of S⊂N. Let K={1, ..., m}be the set of cooperative layers, that is, different spheres over which Games 2014,5195 cooperation amongst S⊆Nmay ensue. Write Mfor a society consisting of a partition of each layer, M={ρ1, ..., ρm}, and MS={ρ1(S), ..., ρm(S)}for a subsociety consisting of a partition of each layer of some S⊂N(in which case MSand MN\Sare “separable” subsocieties; i.e., there is no coalition that includes members from both subsocieties). Now, G(v, K, N)is a multiple membership game (MMG), defined by N,Kand v.vis the characteristic multiple membership function that assigns, for every layer k∈K, a worth in terms of transferable utility of vkto each C∈ρkgiven M: for any k∈K,vk(·;M) : ρk→Rfor all ρk∈P(N). Naturally, an MMG is a partition function game (PFG) as in [2] if Kconsists of only one layer (when no multiple membership exists). With only one layer, the MMG/PFG further reduces to a characteristic function game (CFG) as in [1] if, for any C⊆N,v(C;ρ)is constant for all ρ∈P(N) with C∈ρ. 3.1. Externalities When multiple membership exists, externalities come in various kinds. In these notes, an externality is said to be present if one instance of its effect is present so that a game may exhibit different kinds of externalities over different parts of the game. This allows to model interesting situations like the above Cournot model: merger in one market has both positive and negative effects on the other firms and on the other markets. The externalities will be defined using the notion of embedded coalitions. Given partition ρof N,C is an embedded coalition if C∈ρ. Partition ρembeds ρ0if, for all C0∈ρ0, there is some C∈ρsuch that C0⊆C. One externality is the “partition” externality, which is the externality known from PFGs: the intra-layer externality of an n(≥3)-player Cournot game, for example, where one firm’s payoff varies with the remaining firms’ decisions on whether to merge or not, is such an externality. Partition externality. G(v, k, N)exhibits a positive (or negative) partition externality if there exist M,M0such that M \ ρk=M0\ρ0 k,ρkembeds ρ0 kwith C∈ρk,C∈ρ0 k, and vk(C;M)>(or <)vk(C;M0). The other “cross” externality stems from the effects of the formation of coalitions in one layer on the payoffs of some coalition in another. This inter-layer effect is new and peculiar to multiple membership and cannot be expressed through existing cooperative game representations. In the multimarket Cournot example, the cross externality was the effect of merger in one product market on the firms’ profits in the other. Cross externality. G(v, k, N)exhibits a positive (or negative) cross externality if there exist M,M0 such that M \ ρk=M0\ρ0 kwith C∈ρk0,C∈ρ0 k0for some k06=k,ρkembeds ρ0 k, and vk0(C;M)>(or <)vk0(C;M0). A subclass of cross externalities are “partition-cross” (“partition externalities across layers”). They have elements of cross and of partition externalities: coalition formation of one set of players S1⊆Nin one layer affects the worth of coalitions of another S2⊆Nin another layer with S1∩S2=∅. This occurs when, for example, a merger of firms one and two in one market affects the profits of firm three in another. Games 2014,5196 Partition-cross externality. G(v, k, N)exhibits a positive (or negative) partition-cross externality if there exist M,M0such that M \ ρk=M0\ρ0 kwith C∈ρk0,C∈ρ0 k0for some k06=k,ρk embeds ρ0 kwhile being identical w.r.t. the coalitions that all members of Cjoin (i.e., for all fsuch that f∈C∈ρk0,(f∈S∈ρk)⇔(f∈S∈ρ0 k)with the same Sin both), and vk0(C;M)>(or <)vk0(C;M0). A partition-cross externality is a partition externality where partitions ρkiand ρ0 kiare identical w.r.t. the coalitions that all members of Cjoin: for all fsuch that f∈C∈ρkj,(f∈S∈ρki)⇔(f∈ S∈ρ0 ki)with the same Sin both. 3.2. Feasible Deviations In the absence of externalities and multiple membership (i.e., in characteristic function games, CFGs), a deviation by some S⊂Nwhen forming a coalition has a one-to-one association with a unique worth of S[1]. In the presence of externalities, however, further expectation conjectures (assumptions about how the rest of society, N\S, reacts to a coalitional deviation by S) are needed [1,19]. For partition function games (PFGs), that is, in the presence of externalities within a single sphere (no multiple membership), [20–23] propose definitions of the core dependent on different conjectures to evaluate the profitability of coalitional deviations. [10] provides an excellent discussion of these, also analyzing their axiomatic foundations.([9] provides additional results on the externality structure relevant for the corresponding non-emptiness results for several of these cores.) Suppose the partition was ρbefore S⊂Ndeviated and reorganized itself to form ρ(S), then these are the existing conjecture rules that have been proposed in PFG environments (see [10] for a detailed classification and an axiomatic analysis): 1. Max rule [10]: (N\S), taking ρ(S)as given, organizes itself to ρ(N\S)in order to maximize (N\S)’s total worth 2. Pessimistic [19,20]: (N\S)organizes and forms ρ(N\S)in order to minimize S’s total worth 3. Optimistic [23]: (N\S)organizes and forms ρ(N\S)in order to maximize S’s total worth 4. Singleton [21,22]: (N\S)breaks down into singletons 5. Collective [10]: (N\S)forms one joint coalition ([10] call this rule N-exogenous) 6. Disintegrative [1,20]: all C∈ρsuch that C∩S=∅remain organized in the same way, all other coalitions C0from which members in Sdeviated break up into singletons 7. Projective [20]: all C∈ρsuch that C∩S=∅remain organized in the same way, all other coalitions C0from which members in Sdeviated form coalitions amongst the remaining (C0\S) Note that conjecture rules 1–3 depend on ρ(S)and on the underlying PFG, but not on the original partition ρ. Rules 4–5 depend only on S. Rules 6–7 depend on Sand on the original partition ρ. With multiple membership, in addition to the need of specifying a conjecture, we must specify what kinds of deviations are deemed feasible. The feasibility of deviations needs to be interpreted here because, for example, starting with the grand coalition in some layer, each S⊂Nmay deviate in many ways: in some or all of the layers, forming different coalitions in each layer or the same coalition in all layers. If cooperation is compartmentalized without cross externalities in between the layers, Games 2014,5197 players may deviate in one layer but continue to form the grand coalition in another layer. When cross externalities are present, however, the worth of coalitions vary with the coalition constellations across layers and deviators need to endogenize the cross external effects of their deviations. If S⊂N deviates and forms Sin layer 1, for example, it cannot expect to form Nin another layer because S’s members need to cooperate with (N\S)to form this constellation. Therefore, this note only considers the following deviations: Feasible deviations. Any S⊆Ncan form any subsociety MS∈P(S)m(a partition of Sin every layer). MSand MN\Smust be separable. From the feasible set of subsocieties available to S, it aims to form subsociety d MS∈P(S)mthat maximizes its total payoffs. For that, each S⊂Nneeds to conjecture how the rest of the population responds to its deviation. The reason for restricting deviations in this way is to guarantee that society M after deviation by some S⊂Noccurs is separable into subsocieties MSand MN\S. If this is the case, then the above list of conjectures can be adapted directly. Suppose Zrepresents any of the above conjectures so that Z, for every MSdeviating from M, specifies a resulting subsociety Z((N\S); MS)∈P(N\S)mof (N\S)(a partition of (N\S)in every layer, but not necessarily the same one in all layers). Write d MS(N)for the resulting overall society {d MS,Z((N\S); d MS)}. Hence, Sforms the optimal subsociety d MSsuch that, given conjecture Z, X k∈KX C∈ρk(S) vk(C;d MS(N)) = max MS∈P(S)mX k∈KX C∈ρk(S) vk(C;{MS,Z((N\S); MS)}). The finiteness of possible coalition structures guarantees the existence of such a (not necessarily unique) subsociety for any S⊆N. We will now define a function summarizing their worth. Conjectured worth function. The conjectured worth function (CWF), z, summarizes the conjectured worth for all coalitions: given Z, for all C⊆N,z(·) : C→R. For any S⊆N,z(S)is the largest feasible sum of payoffs for Sunder conjecture Z: z(S) = X k∈KX C∈ d ρk(S) vk(C;d MS(N)) Note that zfilters the information in the MMG to obtain a CFG view of deviating demands. 3.3. Superadditivity When externalities exist, a detailed analysis of the effects of coalition formation may be needed to evaluate the global benefits of cooperation and a superadditivity assumption may be difficult to uphold. When one agent is able to take free ride on the coalition formed by others, for example, the grand coalition may no longer be the efficient coalition structure and it may indeed be insightful to work with a given coalition structure to analyze the effects of free ride. In the presence of multiple membership and externalities, coalition formation may be mutually beneficial in some layer but not necessarily globally as negative cross externalities may exist. Suitably defined, MMGs may conversely be globally superadditive if the overall effect of coalition formation, Games 2014,5198 which takes into account all external and direct effects, is positive for those that come together to cooperate even if coalition formation itself is not mutually beneficial in the separate layers. The numerical illustration of the multimarket Cournot game for the cases when α > 0.45, for instance, is superadditive because the total profits of the firms rise with every further merger: the no merger case has total payoffs of 10, compared with the 10 + (α−0.45) ×0.5of both one merger cases, and compared with the 10.5 of full merger. The below definition of MMG superadditivity embeds definitions of superadditivity for CFGs and PFGs and implies efficiency of forming the grand coalition in all layers. Superadditivity: An MMG is superadditive if, for all M,M0such that M \ ρk=M0\ρ0 k, and ρk embeds ρ0 kin layer k,X k∈KX C∈ρk vk(C;M)≥X k∈KX C∈ρ0 k vk(C;M0). Superadditivity implies the efficiency of the “grand coalition” by which we mean society {N}(the grand coalition) forms in all layers. When the game consists of a single layer without externalities (described by a CFG), the above definition implies the simple pairwise superadditivity that v(C∪C0)≥v(C) + v(C0)is to be satisfied for all (C, C0)⊂N:C∩C0=∅. (Note that the implied sense of superadditivity when there is only one layer has also been defined as full cohesiveness ([9], section 2.2 “Convexity”) in the contexts of PFGs, as opposed to a pairwise view of superadditivity ([9], section 2.1 “Superadditivity”). [9]’s pairwise view of superadditivity does not imply the efficiency of the grand coalition.) Note that the optimization problem underlying z, which is a CFG, entails that zis superadditive by definition, even if the MMG is not superadditive: for any S, S0⊆Nwith S∩S0=∅,z(S) + z(S0)≤z(S∪S0). 4. Coalitional Stability and the Core We now turn to the stability of an outcome. By outcome we mean (M, x); a coalition structure together with an allocation of the common gains. To assess its stability, we will use the conjectured worth function. For allocation x, we write x={xf1, ..., xfn}such that each allocated player payoff xf=Pk∈Kxk fsummarizes the payoffs to each f∈Nobtained in all layers. Consequently, for some S⊆N,x(S)is a vector of all-layer payoffs for the players in S. Naturally, an allocation must be feasible: given any M,Pf∈Nxf≤Pk∈KPC∈ρkv(C;M). Recall our numerical illustration of the multimarket Cournot game. Independent of α= (0,1), one unique conjectured worth function is derived, i.e.,zis such that z(f1) = z(f2) = 1 + 4 = 5 and z(f1, f2) = max{(5.25 + 5.25); (9.75 + α×0.5)}= 10.5. Note that no conjecture is needed for this assessment. It is easy to verify in this particular example that G(v, K, N)has a nonempty core: for an example of a core outcome, consider full merger with contract x= (5.25,5.25), paying both firms 5.25. This outcome is in the core because no firm can do better by deviating. In fact, any split of full merger paying each firm at least his individually rational payoff of 5 (what he gets from no merger) and the other the residual to 10.5 is a stable core allocation.