Arbitration and Stability in Cooperative Games with Overlapping Coalitions Yair Zick YAIRZICK @ CMU . EDU School of Computer Science Carnegie Mellon University, United States Evangelos Markakis MARKAKIS @ GMAIL . COM Department of Informatics Athens University of Economics and Business, Greece Edith Elkind ELKIND @ CS . OX . AC . UK Department of Computer Science University of Oxford, United Kingdom Abstract Overlapping Coalition Formation (OCF) games (Chalkiadakis, Elkind, Markakis, Polukarov, & Jennings, 2010) are cooperative games where players can simultaneously participate in several coalitions. Capturing the notion of stability in OCF games is a difficult task: deviating players may continue to contribute resources to joint projects with non-deviators, and the crucial question is what payoffs the deviators expect to receive from such projects. Chalkiadakis et al. (2010) introduce three stability concepts for OCF games—the conservative core, the refined core, and the optimistic core—that are based on different answers to this question. In this paper, we propose a unified framework for the study of stability in the OCF setting, which encompasses the stability concepts considered by Chalkiadakis et al. (2010) as well as a wide variety of alternative stability concepts. Our approach is based on the notion of arbitration functions, which determine the payoff obtained by the deviators, given their deviation and the current allocation of resources. We provide a characterization of stable outcomes under arbitration. Furthermore, we propose a criterion for an outcome to be in the refined or optimistic core, complementing the results of Chalkiadakis et al. (2010) for the conservative core, and answering questions left open by Chalkiadakis et al. (2010). We also introduce and study a new notion of the core, namely, the sensitive core, which lies between the conservative core and the refined core. Additionally, we put forward criteria for nonemptiness of the arbitrated cores that extend the classic Bondareva–Shapley theorem. Finally, we show that OCF games with the conservative arbitration function are essentially equivalent to nonOCF games, by relating the conservative core of an OCF game to the core of a non-overlapping cooperative game, and use this result to obtain a strictly weaker sufficient condition for conservative core non-emptiness than the one given by Chalkiadakis et al. (2010). 1. Introduction Consider a market exchange involving several agents, each owning a certain amount of some goods (say, oil, sugar and flour). The agents trade with each other, and each vendor may offer different prices to different buyers. Suppose that one of the vendors has 3 tons of sugar and has agreed to sell them to buyers 1 and 2 so that buyer 1 receives 1 ton of sugar and pays 500 dollars, whereas buyer 2 receives 2 tons of sugar and pays 900 dollars. The vendor then discovers that he can sell one ton of sugar to a third buyer for 700 dollars. He may decide that he is unhappy with the amount of money he receives from the transaction with buyer 1, and cancel the deal in favor of buyer 3. However, 1 buyer 2, upon hearing that the transaction with buyer 1 has been canceled, may no longer wish to work with this vendor, and cancel her agreement with him as well. Therefore, when deciding whether a deviation from an agreement is profitable, the vendor needs to predict how other parties he is trading with would react to his actions. If it is safe to assume that buyer 2 is willing to upkeep the interaction, then the deviation is profitable; if this is not true, then the seller has to forgo the better deal with buyer 3, or lose more than what the deviation is worth. This setting possesses several interesting characteristics. First, a vendor may allocate his goods to several buyers, and a buyer may also purchase goods from several vendors. In other words, agents may allocate fractions of their resources to several profit-generating tasks. Second, agents may withdraw some of their resources from some agreements, while keeping others unchanged. For example, an oil vendor may wish to sell less oil to some customer, but not change her interactions with other parties; similarly, a buyer may want to pay less to some vendors, but maintain the same payments to others. Finally, when trying to strategically change an agreement, agents must take into account the impact of their actions on the contracts they still maintain with other (possibly unaffected) parties. These features are typical of many multi-agent settings, where agents collaborate by allocating parts of their resources to working together in order to generate revenue, and then share the resulting profits. Profit sharing can be done directly, if the exchange of goods itself results in a profit, e.g., if the agents can make a new good using their resources and sell it; profit sharing can also be indirect, e.g., via setting a price for the good sold. In such settings, even if there are no external constraints on how the profits should be distributed, agents should account for individuals or groups of agents who are underpaid. A group of agents that can get more money by deviating from the proposed deal may destabilize the entire agreement, causing a cascade of deviations that results in a less desirable state. However, what constitutes a profitable deviation greatly depends on how the non-deviators respond to the deviating set. Modeling this system of incentives and reactions is a challenge in itself. Recently this challenge was addressed by Chalkiadakis et al. (2010), who propose a novel approach to modeling scenarios where agents can divide resources among several coalitions. They introduce overlapping coalition formation (OCF) games, which generalize the classic model of cooperative games (Peleg & Sudh¨olter, 2007). In the classic cooperative game theory model, there is a set of agents N ; each subset S of N can form a team and generate profit for its members. In transferable utility (TU) games, each subset of agents S ⊆ N is identified with a value v(S). This value can be thought of as the monetary payoff to the set S should its members agree to work together, and can be freely divided among the members of S. As argued above, a desirable property of a payoff distribution scheme is its stability against individual and group deviations, which is captured by the notion of the core (Gillies, 1953): a payoff division is said to be in the core if every subset of agents S ⊆ N receives a total payoff that is at least its value v(S). Classic cooperative game theory assumes that each agent may belong to at most one coalition at any given time. That is, agents form coalition structures by splitting into disjoint groups, with each group working on an individual task. Consequently, the classic approach is not well-suited to handle overlapping coalitions, and the intricacies of deviation in settings where each agent participates in several agreements. Indeed, in the classic cooperative game setting, a set of agents assesses the desirability of a payoff division against what it can make on its own: is the total payoff allotted to S at least v(S)? This is because the deviating agents break all ties with the non-deviators, 2 so they cannot expect the non-deviators to collaborate with them in any way. In contrast, when agents are allowed to split their resources among multiple coalitions, the very notion of a profitable deviation must be reexamined, since partial coalitions allow for partial deviations, which means that even though a set of agents decides to deviate from the group agreement, it remains involved in collaborative projects with non-deviators. These non-deviators then decide how much the deviators should receive from such projects. Hence, the deviators’ decision whether to withdraw from some tasks (and to what extent) depends on what they expect to receive from their collaboration with non-deviators. Chalkiadakis et al. (2010) propose a model where agents can split their resources among several coalitions, and study the effect of joint projects with non-deviators on the desirability of deviation in the overlapping coalition setting. They propose and discuss three notions of reaction to deviation. The first reaction, which they term conservative, gives the deviators no share of the profits from any coalitions they maintain with non-deviators. The second reaction, termed refined, allows the deviators to keep their payoffs from coalitions that were unaffected by the deviation. Finally, under the optimistic reaction the deviators may be able to receive some revenue from each coalition they are involved in, as long as the non-deviators in that coalition are guaranteed their pre-deviation payoffs. These reactions to deviation correspond to three notions of stability for OCF games, namely, the conservative core, the refined core, and the optimistic core. The non-deviators’ reaction to deviation can extend beyond these three notions. Many legal contracts (e.g., ones involving a service provider and its clients, or vendors and suppliers, or several companies working on a joint venture) are designed with the explicit aim of detailing the consequences of deviation to all parties. Typically, such contracts impose fines on parties that break the agreement. However, there are also other forms of punishment: for instance, a company that fails to uphold its contractual obligations may be blacklisted by some of its clients, or have its reputation tarnished by “bad press”. Alternatively, one may be actively rewarded for deviating, e.g., when an external party wishes to break a certain status-quo, or to encourage project diversification. By adopting the notion of partial deviation and the possible reactions to deviation, we can capture far more nuanced scenarios than those described by classic TU games. 1.1 Our Contribution Our main contribution is a broad generalization of the overlapping coalition formation (OCF) model proposed by Chalkiadakis et al. (2010). While Chalkiadakis et al. (2010) describe three ways in which non-deviators may react to a deviation, we propose a general framework for modeling such reactions. Our framework is based on the notion of arbitration function (Section 3). This is a function that, given a deviating group of players and its deviation, outputs, for every coalition containing the deviators, the amount that the deviators can expect to receive from this coalition post-deviation. Using arbitration functions, we present a class of solution concepts for OCF games that we call arbitrated cores (Section 4). We show that the three concepts of the core described by Chalkiadakis et al. (2010) are special cases of our model, and propose a new concept of the core, which we call the sensitive core. We propose a criterion for checking whether an outcome is in the arbitrated core, and characterize core outcomes under some important arbitration functions. We then focus on identifying sufficient and necessary conditions for the arbitrated core to be non-empty (Section 5). Building on the work of Chalkiadakis et al. (2010), who provide an LP-based criterion for the non-emptiness of the conservative core, we derive criteria for the sensitive and refined core to be 3 non-empty. We use this result to identify an interesting class of OCF games whose refined core is guaranteed to be non-empty. Finally, we show that OCF games with the conservative arbitration function are essentially equivalent to non-OCF games, by relating the conservative core of an OCF game G to the core of its discrete superadditive cover, which is a non-OCF game that is constructed from G in a natural way. In particular, this means that the conservative core of an OCF game G is non-empty when the discrete superadditive cover of G is supermodular. We demonstrate that this condition is strictly weaker than the convexity-based condition for conservative core non-emptiness given by Chalkiadakis et al. (2010). 1.2 Related Work The most direct precursor to our work is the work of Chalkiadakis et al. (2010): we generalize their model to capture a broader class of possible reactions to deviation, and solve some of the problem left open by their work. Incentives and optimization in collaborative multi-agent environments have received plenty of attention from the multiagent research community (Sims, Corkill, & Lesser, 2008; Airiau & Sen, 2009; Rahwan & Jennings, 2008; Dang, Dash, Rogers, & Jennings, 2006; Shehory & Kraus, 1996; Lin & Hu, 2007; Zhang, Jiang, Su, Qi, & Fang, 2010); see also the PhD thesis of Rahwan (2007) and the recent book of Chalkiadakis, Elkind, and Wooldridge (2011) for an overview. These studies often use cooperative game theory as the modeling framework. Several authors have considered the problem of optimal coalition structure generation in cooperative settings with overlapping coalitions. Shehory and Kraus (1996) have initiated this line of research; in their work, they describe a distributed coalition formation algorithm where agents may split their resources among several tasks in order to achieve better outcomes. Dang et al. (2006) consider overlapping coalitions in sensor networks, where the agents are sensors that are tasked with tracking objects. Lin and Hu (2007) provide a parallel algorithm for overlapping coalition formation. In all these papers, the underlying assumption is that agents are fully cooperative, i.e., they seek to maximize the social welfare rather than their own gains. In contrast, in our work we focus on game-theoretic aspects of strategic behavior in cooperative settings, taking agent incentives into account. Our model applies to settings where rational agents distribute their resources among several projects, receiving profits from each. This scenario occurs in a variety of applications. For example, multi-commodity network flows can be easily modeled within the overlapping coalition formation framework (see Markakis and Saberi (2005) for the analysis of the underlying non-OCF game). This is also the case for several other fractional optimization problems (Deng, Ibaraki, & Nagamochi, 1999). For example, a fractional matching problem can be thought of as an OCF game, where each partial coalition between a pair of agents describes the amount of resources that each of these agents assigns to the respective task. Another class of settings where overlapping coalitions arise are collaboration networks. Consider a social network where each agent is associated with a weighted node and derives some value from assigning a certain portion of its weight to collaborating with its neighbors. Such settings have received much attention in recent years (for a survey, see Jackson, 2003). For instance, Anshelevich and Hoefer (2010) discuss strategic aspects of network formation in settings where agents may participate in more than one coalition; however, in contrast with our work, the main focus of their analysis is individual rationality and pairwise equilibria in such networks, rather than group stabil4 ity. Fractional stable matchings were discussed by Aharoni and Fleiner (2003), in a non-transferable utility model. More recently, Ackerman and Brˆanzei (2014) have analyzed research collaboration using a graphical model, where authors devote some of their efforts to collaborative projects, and receive some credit for their work based on the authorship order model. Just as Anshelevich and Hoefer (2010), Ackerman and Brˆanzei (2014) are mainly interested in individually rational and pairwise stable outcomes. The overlapping coalition formation games, as proposed by Chalkiadakis et al. (2010), share some features with fuzzy games (Aubin, 1981). However, there are fundamental differences between the two models. Arguably, the most important difference is that Chalkiadakis et al. (2010) assume that several partial coalitions may form, whereas Aubin (1981) assumes that all agents pool their resources to work on a single task, and only considers partial coalitions in the context of potential deviations. Assuming the formation of a single coalition eliminates many of the subtleties that games with overlapping coalitions can capture, as was emphasized by Chalkiadakis et al. (2010). 2. Preliminaries Throughout the paper, we consider games with a finite set of players N = {1, . . . , n}. We use boldface lowercase letters to denote vectors and uppercase letters to denote sets. Given a set S ⊆ N , we write eS to denote the indicator vector Furthermore, given a vector x = (x1 , . . . , xn ) ∈ Rn P of S. i and a subset S ⊆ N , we set x(S) = i∈S x . 2.1 Classic TU Cooperative Games A transferable utility (TU) cooperative game is given by a set of players, or agents, N = {1, . . . , n} and a characteristic function u : 2N → R with u(∅) = 0; we write G = hN, ui. A payoff vector for a game G = hN, ui is a vector x ∈ Rn such that x(N ) = u(N ). A payoff vector x for a game G = hN, ui is said to be stable if x(S) ≥ u(S) for each S ⊆ N . The set of all stable payoff vectors for G is called the core of G. It is sometimes assumed that agents are allowed to form coalition structures; a coalition structure CS is simply a partition of N , and its value u(CS ) is the sum of the values of its constituent coalitions. If a coalition S is a part of some coalition structure CS , then the value of S, u(S), can be freely divided among all members of S, but transfers to agents that are not members of S are not allowed, i.e., x is a payoff vector for a coalition structure CS if and only if x(S) = u(S) for each S ∈ CS . The core of a game G = hN, ui with coalition structures is the set of all pairs (CS , x), where CS is a coalition structure, x is a payoff vector for CS , and x(S) ≥ u(S) for each S ⊆ N . Cooperative games with coalition structures have been first studied by Aumann and Dr`eze (1974), and have been the focus of a number of recent papers by the multiagent research community (see Chalkiadakis et al., 2011). 2.2 OCF Games Given a set of agents N = {1 . . . n}, a partial coalition of players in N is a vector c = (c1 , . . . , cn ) in [0, 1]n . The i-th coordinate of c indicates the fraction of player i’s resources contributed to c. In what follows, we will omit the word “partial”, and refer to vectors in [0, 1]n as coalitions. Of particular interest are the players who actively participate in c. These players may rightfully claim a share of c’s profits, and they are the ones who may potentially get hurt if some agent changes its 5 contribution to c. Formally, the support of the coalition c is the set supp(c) = {i ∈ N | ci > 0}. We now recall the formal definition of OCF games, given by Chalkiadakis et al. (2010). Definition 2.1. An OCF game G = hN, vi is given by a set of players N = {1, . . . , n} and a characteristic function v : [0, 1]n → R+ , which assigns a non-negative real value to each partial coalition; we require that v(0n ) = 0. The characteristic function of an OCF game can be quite general; we do not even require v to be monotone. The reasoning behind this apparent leniency is that, given v, the agents in N may form several coalitions in order to optimize their revenue, a process which results in a coalition structure. There is, however, one additional assumption on v that we would like to impose; to introduce it, we first need to formally define the concept of a coalition structure in an OCF game. P A coalition structure over N is a finite list of coalitions CS = (c1 , . . . , cm ) such that m j=1 cj ≤ n 1 . The coalition structure CS can be thought of as an n × m matrix whose rows sum to at most 1. The requirement that the rows sum to no more than 1 means that CS is a valid division of players’ resources, i.e., each player gives at most 100% of its resources to CS . For readability, we use set notation when referring to coalition structures: e.g., when referring to a coalition c that appears in CS , we write c ∈ CS , and when referring to a coalition structure CS 0 that is a sublist of CS , we write CS 0 ⊆ CS . Recall that a coalition structure in a classic cooperative game is a partition of the agent set, i.e., a collection of disjoint subsets of N whose union is N . In particular, no set of agents can appear twice in the same coalition structure. In contrast, in OCF games, it is possible for a coalition structure CS to have the same coalition appearing more than once. This simply means that the respective agents are completing two separate tasks, which require the same resources and generate the same revenue. Example 2.2. Consider a setting where two researchers collaborate. They can write a single long research paper, which will require all of their time, and will generate a revenue of $100000 (in, say, grant money or performance payment). Alternatively, if they split their time equally between two research projects, they will produce two shorter papers, which generate $70000 each. In this setting, it is in the agents’ best interest to split into two identical coalitions of the form ( .5 .5 ) rather than form a single coalition. P The total revenue generated by the coalition structure CS is simply c∈CS v(c), and is denoted by v(CS ). Given a set of agents S ⊆ N , we say that a coalition structure CS is over S if supp(c) ⊆ S for all c ∈ CS . We denote the set of all coalition structures over S by CS(S). The weight vector P of a coalition structure CS is w(CS ) = c∈CS c. The vector w(CS ) indicates the total amount of resources that each player in N invests in the coalition structure CS . Note that w(CS ) ∈ [0, 1]n , and if CS ∈ CS(S), then w(CS ) ≤ eS ; we say that a coalition structure CS over S is efficient if w(CS ) = eS . We also write wS (CS ) to denote the total weight of S in CS ; namely, the i-th coordinate of wS (CS ) equals the i-th coordinate of w(CS ) if i is in S, and is 0 otherwise. As shown in Example 2.2, agents may form coalition structures in order to increase their revenue. Such considerations naturally give rise to the following definition. The superadditive cover of v is defined as v ∗ (c) = sup{v(CS ) | CS ∈ CS(N ), w(CS ) ≤ c}. The value v ∗ (c) is the most that the players can make using the resources of c. Note that a similar notion of a superadditive cover exists for classic coalitional games (Aumann & Dr`eze, 1974): given 6 a function u : 2N → R, its superadditive cover is the function u∗ : 2N → R defined as X u∗ (S) = max{ v(T ) | P is a partition of S}. T ∈P Recall that a function f : Rn → R is called superadditive if for all c, d ∈ Rn we have f (c) + f (d) ≤ f (c + d); (1) if f is defined on a subdomain U of Rn , condition (1) is only imposed on vectors c, d such that c + d is still in U . This definition has the following discrete analogue: a function u : 2N → R is called superadditive if for all sets S, T ⊆ N such that S ∩ T = ∅ we have u(S) + u(T ) ≤ u(S ∪ T ). (2) These definitions explain the term “superadditive cover”: it is easy to see that v ∗ is the minimal superadditive function from [0, 1]n to R such that v ∗ (c) ≥ v(c) for every c ∈ [0, 1]n , and, similarly, u∗ is the minimal superadditive function from 2N to R such that u∗ (S) ≥ u(S) for every S ⊆ N . We are now ready to formulate the additional requirement that we wish to impose on v. Definition 2.3. A characteristic function v has the efficient coalition structure property if for every c ∈ [0, 1]n there exists a CS ∈ CS(N ) such that w(CS ) = c and v ∗ (c) = v(CS ). For characteristic functions that have the efficient coalition structure property, the sup in the definition of v ∗ can be replaced with max. In what follows, we limit our attention to OCF games whose characteristic functions enjoy this property. To see why the efficient coalition structure property is desirable in the OCF setting, consider the function f given by f (x) = α for all x ∈ [0, 1]n \ {0n }, where α is some positive constant. This function does not have the efficient coalition structure property and its superadditive cover is f ∗ (x) = ∞ for all x ∈ [0, 1]n \ {0n }. In particular, this means that no coalition structure is optimal for f : it is always possible to increase the social welfare by splitting some coalition into two non-zero coalitions. We remark that Chalkiadakis et al. (2010) impose a number of conditions on the characteristic function of an OCF game that, taken together, imply the efficient coalition structure property; we find it more convenient to state this property directly. To provide some intuition for the concepts introduced so far, we now describe a simple class of OCF games. It is often useful to think of the agents as using their resources to complete a given set of tasks. Chalkiadakis et al. (2010) describe a class of OCF games, which they call Threshold Task Games (TTGs), that are based on this idea. A TTG is specified by a finite list of tasks, T = {t1 , ..., tk }, where each task t` requires some weight ω(t` ) ≥ 0 for its completion and gives a certain payoff p(t` ) ≥ 0, and a list of players’ weights, denoted (w1 , . . . , wn ). Each player can allocate any fraction of its weight to the completion of any task. The worth of a coalition is v(c) = max{p(t` ) | ω(t` ) ≤ n X ci wi }; i=1 that is, the value of a coalition is simply the value of the highest-paying task that the agents can complete using their combined weight. Threshold Task Games are a natural extension of Weighted Voting Games (WVGs) (Chalkiadakis et al., 2011). Indeed, in a weighted voting game, each agent 7 i ∈ N has a non-negative weight wi , and the value of a set of players S ⊆ N is 1 if the combined weight of the members of S is at least some given non-negative quota q, and 0 otherwise. Thus, weighted voting games are simply threshold task games where there is a single task with weight q and payoff 1, and overlapping coalitions are not allowed. 2.3 Payoff Division Having split into coalitions and generated revenue, the agents have to decide how to divide this revenue amongst themselves in an agreeable manner. We will now formally describe payoff division in OCF games. An imputation for a coalition structure CS = (c1 , ..., cm ) ∈ CS(N ) is a list of vectors x = (x1 , ..., xm ); for each j = 1, . . . , m, xj is a vector in Rn that describes how much each agent in N receives from cj . Given a coalition c ∈ CS and an imputation x for CS , we refer to the way the value of c is divided as x(c); thus, the payoff to agent i from coalition c ∈ CS under x is x(c)i . In order for x to be a valid division of payoffs among the agents, it should satisfy the following conditions. P i ∗ {i} Individual Rationality: c∈CS x(c) ≥ v (e ) for all i ∈ N . P Payoff Distribution: for all c ∈ CS it holds that i∈N x(c)i ≤ v(c), and if ci = 0 then x(c)i = 0. We denote the set of all imputations for CS by I(CS ). Observe that our definition does not allow inter-coalitional transfers. That is, if an agent i ∈ N is not in the support of c, then i cannot expect to receive any payoff from c. We call a tuple (CS , x), where CS is a coalition structure and x ∈ I(CS ), a feasible outcome. Given a set S ⊆ N , we denote by F(S) the set of all feasible outcomes (CS , x) with CS ∈ CS(S). Thus, F(N ) refers to all possible ways that agents can form coalition structures and divide payoffs. Given a feasible outcome (CS , x) ∈ F(N ), we define the payoff to an agent i ∈ N as P pi (CS , x) = c∈CS x(c)i . This is the total payoff of i from all coalitions in CS . Observe that pi (CS , x) is uniquely defined: for any given outcome (CS , x), the total payoff to player i depends solely on the amount of payoff received from the coalitions in CS , which P is determined by x, and x alone. Similarly, the total payoff to a set S is given by pS (CS , x) = i∈S pi (CS , x). Definition 2.4. Given a set S ⊆ N and a coalition structure CS ∈ CS (N ), the coalition structure CS reduced to S is defined as CS |S = (c ∈ CS | supp(c) ⊆ S) . These are all coalitions that are comprised solely of members of S. The coalitions in CS |S are fully controlled by S. Hence, a deviation by the members of S would only affect non-deviators if S changes its contribution to coalitions outside of CS |S . We are now ready to formally define deviations in OCF games. Loosely speaking, a deviation by a set S ⊆ N from a coalition structure CS ∈ CS(N ) specifies the amount of resources that S will withdraw from coalitions not in CS |S . Definition 2.5. Suppose that CS \CS |S = (cj1 , . . . , cjk ). A coalition structure CS 0 = (d1 , . . . , dk ) is a deviation of S from CS if for all ` = 1, . . . , k it holds that d` ≤ cj` and d` ≤ eS . 8 The deviation CS 0 describes how a set S withdraws resources from coalitions in CS \ CS |S . The requirement that d` ≤ cj` captures the fact that S cannot withdraw more resources from the coalition cj` than it has invested in it. We also require that d` ≤ eS since the deviation CS 0 can involve members of S only. It will sometimes be convenient to think of a deviation as a function that, for each coalition c in CS \ CS |S , outputs how much agents in S withdraw from c. That is, given a coalition structure CS ∈ CS(N ), a set S ⊆ N , a deviation CS 0 of S from CS , and a coalition cj` ∈ CS \ CS |S , we write dCS 0 (cj` ) to refer to the coalition d` in CS 0 that corresponds to the deviation of S from cj` . Under this notation, (dCS 0 (cj` ))i specifies the amount of resources that agent i withdraws from the coalition cj` under CS 0 . When the deviation CS 0 is understood from the context, we omit the subscript CS 0 from dCS 0 (c) and refer to the deviation of S from c as d(c). Note that if S withdraws all of its resources from CS \ CS |S , then the total weight available to S is w(CS |S ) + wS (CS \ CS |S ) = wS (CS ). Example 2.6. Consider a three-player game described as follows. There are several types of tasks: • t12 requires 50% of player 1’s resources and all of player 2’s resources, and its payoff is 16; • t012 requires 40% of player 1’s resources and all of player 2’s resources, and its payoff is 10; • t13 requires 50% of player 1’s resources and all of player 3’s resources, and its payoff is 20; • t1 requires 10% of player 1’s resources and its payoff is 3. The optimal coalition structure in this case is 0.5 0.5 CS = c1 = 1 , c2 = 0 . 0 1 The coalitions c1 and c2 complete tasks t12 and t13 , respectively; thus, v(c1 ) = 16 and v(c2 ) = 20. A deviation of player 1 from CS would be a coalition structure β γ CS 1 = 0 , 0 0 0 such that β ≤ 0.5 and γ ≤ 0.5. If β = 0, then player 2 is unaffected by the deviation; if γ = 0 then player 3 is unaffected by the deviation. It is possible that player 1 deviates from c1 while not changing its contribution to c2 , or vice versa. Moreover, it is possible that a coalition from which resources were withdrawn can still generate some revenue. For instance, if player 1 withdraws 10% of its resources from c1 , what remains of c1 still generates a revenue of 10. This opens opportunities for more nuanced postdeviation behavior: player 3 may decide not to break its agreement with player 1 if γ = 0, and if β = .1 and player 2’s payment in the original coalition structure was less than 10, player 1 can hope to get some payment from its reduced collaboration with player 2. As Example 2.6 illustrates, deviations in OCF games may leave some of the non-deviators unaffected by the deviation. Moreover, it may be possible for deviators to ensure that the non-deviators still receive the payoff they were allocated prior to the deviation. If deviators agree to assume the marginal loss of their deviation, it is possible that the non-deviators will agree to maintain coalitions with them. These notions are formalized in Section 3. 9 3. The Arbitration Function In classic cooperative game theory, a set S that is unhappy with its payoffs and wants to deviate compares its current payoff with what it can earn on its own. However, as Example 2.6 shows, the complex structure of deviations in OCF games can lead to a variety of ways in which agents may react to a deviation. If a deviating set still keeps some resources invested in coalitions with non-deviators, it may be the case that it will continue to receive payments from these coalitions. To discuss stability in OCF games, we need to describe how the agents react if some set S ⊆ N deviates from (CS , x). One can think of this process in the following manner: given an outcome (CS , x) and a deviation CS 0 of S ⊆ N from CS , the set S may use all available resources in CS |S and CS 0 in order to generate revenue for itself. Moreover, each coalition c in CS \ CS |S needs to decide how much payoff it gives to the deviators; this behavior is specified by the arbitration function. Definition 3.1. Given an outcome (CS , x), a set S ⊆ N and a deviation CS 0 of S from CS , the arbitration function A is a mapping that assigns a real value αc (CS , x, S, CS 0 ) to each c ∈ CS \ CS |S . The value αc (CS , x, S, CS 0 ) represents the amount that the coalition c will pay to S, given the current outcome (CS , x), the identity of the deviators, and the nature of their deviation. 3.1 Properties of Arbitration Functions Clearly, we need to impose some restrictions on the amount that the deviators may expect to get from the non-deviators. For example, it would be unreasonable for a deviating set to expect a payoff that exceeds the post-deviation value of the respective coalition. Another natural restriction is that, for deviators to get any payoff from a given coalition, every non-deviator in that coalition should receive the same payoff as before the deviation, i.e., the non-deviators will never agree to pay the deviating set S at the expense of the non-deviating members. Formally, given an outcome (CS , x), a set S ⊆ N , a deviation CS 0 of S from CS , and an arbitration function A whose output on (CS , x, S, CS 0 ) is described by the list of values (αc )c∈CS \CS |S , we require A to have the following properties: P Accountability: αc (CS , x, S, CS 0 ) ≤ max{v(c − d(c)) − i∈N \S x(c)i , 0}. Deviation-Monotonicity: For every pair of subsets S, T ⊆ N such that S ⊆ T and their respective deviations CS 0 and CS 00 from CS such that dCS 0 (c) ≤ dCS 00 (c) for each c ∈ CS \ CS |S , it holds that αc (CS , x, S, CS 0 ) ≥ αc (CS , x, T, CS 00 ). The first condition states a general upper bound on the amount that a deviating set can expect to receive from a coalition: after the deviation, the coalition c can generate a profit of v(c − d(c)), so the most that a deviating set can expect to receive is v(c − d(c)), minus the original payments given to non-deviators under (CS , x). The second condition simply states that the punishment imposed by an arbitration function should be monotone in the size of the violation: if the deviators withdraw a smaller amount of resources from each coalition, they should receive at least as much payoff as they received under their original deviation. The rationale behind the first condition is strategic in nature; it stems from the assumption that a set of agents engaged in a task will not agree to pay deviating members if the deviators cannot ensure that each non-deviator is paid the same amount as 10 prior to the deviation. We do stress however, that accountability is not a necessary component in our proofs: our results still hold even if one does not assume accountability. The second condition, while sensible as well, is instrumental in proving Theorem 3.4, and is a necessary assumption. Finally, note that it is possible that a coalition imposes a fine on deviating members, that is, the value of αc need not be positive. The total revenue of a deviating set S given its deviation CS 0 from CS can be written as A(CS , x, S, CS 0 ) = v ∗ (w(CS |S ) + w(CS 0 )) + X αc (CS , x, S, CS ). c∈CS \CS |S Given an outcome (CS , x) and a set S ⊆ N , the most that S can get by deviating from (CS , x) is A∗ (CS , x, S) = sup{A(CS , x, S, CS 0 ) | CS 0 is a deviation of S from CS }. Now, in order for S to deem a deviation profitable, each of its members should stand to gain from it. The formal definition that captures this idea is somewhat complicated, as it has to describe how the deviators share the profit/loss allocated to them by the arbitration function. Definition 3.2. Given an outcome (CS , x) and a deviation CS 0 of S ⊆ N from CS , we say that CS 0 is an A-profitable deviation if we can construct 1. a coalition structure CS d such that w(CS d ) = w(CS |S ) + w(CS 0 ) together with an imputation xd ∈ I(CS d ), and 2. a collection of vectors y = (yc )c∈CS \CS |S , such that for every c ∈ CS \ CS |S it holds that (a) yc ∈ (R+ )n if αc (CS , x, S, CS 0 ) ≥ 0 and yc ∈ (R− )n otherwise, (b) (yc )i = 0 for i 6∈ S ∩ supp(c − d(c)), and Pn 0 i (c) i=1 (yc ) = αc (CS , x, S, CS ), P so that for every i ∈ S it holds that pi (CS d , xd ) + c∈CS \CS |S (yc )i > pi (CS , x). Simply put, given S’s deviation from (CS , x) and the arbitration function A, the agents in S have to agree on three things. First, they have to decide on a coalition structure to form with their post-deviation resources. Second, they have to come up with a way of dividing profits from that coalition structure. Third, they have to agree on a way of dividing the payoffs (or fines) assigned to them by the arbitration function. For the deviation to be profitable, these agreements should be such that all agents in S receive strictly more than what they had received under (CS , x). If no such agreement exists, S cannot A-profitably deviate. Given (CS d , xd ) and y, the total payoff of an agent i ∈ S from deviating is denoted q i (xd , y). A priori, it seems possible that, even when the total payoff to a deviating set is more than S p (CS , x), the members of S may be unable to divide the revenue from the deviation in a way that benefits them all due to coalitional restrictions. Chalkiadakis et al. (2010) show that for the conservative arbitration function (see Section 3.2) this is not the case: if there is a way for agents to jointly gain more by deviating, then they can divide the profits in a way that benefits them all. In Theorem 3.4, we will show how to extend this result to general arbitration functions. 11 Remark 3.3. It is possible to incorporate a freely divisible value into the arbitration function. This value is a payoff (or fine) assigned to the deviators by an external entity. Just as the payments from the coalitions in CS \ CS |S , this payment may depend on the original outcome, the identity of the deviating set, and the nature of its deviation. All results in this paper carry through with the addition of a freely divisible value. Intuitively, this value allows us to extend notions such as the ε-core (Maschler, Peleg, & Shapley, 1979) to OCF games. 3.2 Some Arbitration Functions We now present some arbitration functions and briefly discuss their properties. Three of these arbitration functions correspond to the three notions of the core introduced by Chalkiadakis et al. (2010) (the conservative core, the refined core and the optimistic core), and the names we use for these arbitration functions reflect this; in contrast, the sensitive arbitration function is based on a new idea. Conservative Arbitration Function The simplest assumption that one can make with respect to reaction to deviation is that the non-deviators will react by voiding all agreements with the deviators; that is, the deviators do not expect any payment from any of their coalitions with the non-deviators, regardless of their contribution. This reasoning gives rise to the conservative arbitration function; formally, it is defined by setting αc ≡ 0 for any given input. Under the conservative arbitration function, a deviating set is not rewarded in any way for continued interaction with the non-deviators; thus, the profit it can hope to gain by deviating is exactly what it can make on its own. Therefore, under the conservative arbitration function, denoted by Ac , we have A∗c (CS , x, S) = v ∗ (eS ) for every outcome (CS , x). Sensitive Arbitration Function When reasoning about agents’ reaction to deviation, a natural assumption to make is that the non-deviators do not care what the deviating set S does, as long as the deviation does not affect them. This approach is captured by the sensitive arbitration function. Under this function the payment that the deviators obtain from a coalition c ∈ CS \ CS |S is 0 if there is some c0 ∈ CS \ CS |S such that d(c0 ) 6= 0 and supp(c) ∩ supp(c0 ) ∩ N \ S 6= ∅; otherwise, the payment to S is the total payoff that the members of S were receiving from c prior to the deviation. Under the sensitive arbitration function, denoted by As , the most that a deviating set S can get can be computed as follows. First, it is clear that S does not benefit from investing resources into joint projects with non-deviating agents that will be hurt in any way by the deviation. Thus, S only needs to decide which agents it will keep collaborating with; as for all other agents, it can break all agreements with them. In order to describe payments under the sensitive arbitration function, we will employ the following notation. Given a set T ⊆ N , we let CS T be the set of all coalitions in CS that involve members of T ; that is CS T = (c ∈ CS | supp(c) ∩ T 6= ∅). Now, if a set S ⊆ N chooses to break agreements that involve members of T , it forgoes all payments from coalitions in CS T , but can use the resources it has invested in CS T in order to maximize its own profits. That is, we obtain A∗s (CS , x, S) = max v ∗ w(CS |S ) + wS (CS T ) + pS (CS \ (CS |S ∪ CS T ), x) | T ⊆ N \ S . 12 This definition can be extended as follows: instead of being completely self-interested, each agent i ∈ N has a set of players Si ⊆ N that it cares about. If any of the agents in Si are hurt by a deviation, agent i will not allow the deviating set to have any payoff from the coalitions that it is involved in. Refined Arbitration Function The sensitive arbitration function focuses on the impact of the deviation on individual agents; in contrast, the refined arbitration function makes its decisions based on the deviation’s impact on each coalition. Specifically, under this arbitration function a coalition c allows the deviators to keep their payoffs from c if and only if S has not withdrawn any resources from c. Formally, given a deviation CS 0 of S ⊆ N from CS in the outcome (CS , x), the refined arbitration function, denoted Ar , will let S keep its payoff from a coalition c ∈ CS \ CS |S if d(c) = 0, and allocate S no payoff from c otherwise. Note that the refined arbitration function is more generous to the deviators than the sensitive arbitration function: if a deviator i and a nondeviator j are both involved in coalitions c and c0 , and c0 is affected by the deviation while c is not, under the refined arbitration function i will receive its share of c’s payoffs, whereas under the sensitive arbitration function it will not. The most that a set S can expect to gain by deviating under the refined arbitration function can be computed as follows. First, note that given a coalition c in CS \ CS |S , S should either withdraw all resources from c or none at all. Thus, S needs to find the best set of coalitions in CS from which to fully withdraw resources. Formally, we have c )) + pS (CS \ CS c , x) | CS |S ⊆ CS c ⊆ CS }. A∗r (CS , x, S) = max{v ∗ (wS (CS Optimistic Arbitration Function A yet more lenient reaction to deviation is captured by the optimistic arbitration function, denoted Ao . Under this arbitration function a coalition is willing to pay the deviating set as long as the non-deviators receive their pre-deviation payoffs. Since we require arbitration functions to have the accountability property, this means that the optimistic arbitration function gives a deviating set the highest possible payoff it can receive under any arbitration function. Formally, given a set S, an outcome (CS , x) and P a deviation CS 0 of S from CS , the payoff i that S gets from a coalition c is max{0, v(c − d(c)) − i∈S / x(c) }. In order to compute the most that a set S can get by deviating under the optimistic arbitration function, we need to determine the amount of resources that S is going to withdraw from every coalition it is involved in. We obtain X c ) + w(CS 0 )) + c , x)}, A∗o (CS , x, S) = sup{v ∗ (wS (CS v(c − d(c)) − pN \S (CS \ CS c c∈CS \CS c such that CS |S ⊆ CS c ⊆ CS (intuwhere the supremum is taken over all coalition structures CS itively, these are the coalitions of CS from which the members of S withdraw all of their resources) c. and over all deviations CS 0 of S from CS \ CS 3.3 Redefining A-Profitable Deviations The definition of an A-profitable deviation is somewhat difficult to work with. To remedy this, we will now provide a simple sufficient condition for the existence of an A-profitable deviation. Chalkiadakis et al. (2010) prove a similar result for the conservative arbitration function, and we use some of their techniques (most notably, a coloring argument) in our proof. 13 Theorem 3.4. Consider an OCF game G = hN, vi, an outcome (CS , x) of G and an arbitration function A. If A∗ (CS , x, S) > pS (CS , x) for some S ⊆ N , then there is a subset of S that can A-profitably deviate from (CS , x). Proof. Consider a set S ⊆ N such that A∗ (CS , x, S) > pS (CS , x). First, note that the space of possible deviations of S from the coalition structure CS can be viewed as a subset of RD (for an appropriate value of D) that is bounded and can be described by finitely many non-strict linear inequalities. Therefore this space is compact. Thus, there exists a deviation of S from (CS , x) maximizing the total payoff that S can derive from deviating; let CS 0 be some such deviation. Since v has the efficient coalition structure property, there exists a coalition structure CS d such that v(CS d ) = v ∗ (w(CS |S ) + w(CS 0 )). For every c ∈ CS \ CS |S , let αc be the amount that S ∩ supp(c − d(c)) receives from c after the deviation. Our objective is to find an imputation xd ∈ I(CS d ) along with payoff divisions of (αc )c∈CS \CS |S that would witness that a subset of S has an A-profitable deviation from (CS , x). Given a coalition c ∈ CS \ CS |S , let Ic be the set of all possible ways that αc can be divided among the members of S ∩ supp(c − d(c)). Formally, if αc ≥ 0, then Ic = {yc ∈ (R+ )n | supp(yc ) ⊆ S ∩ supp(c − d(c)) and n X (yc )i = αc }; i=1 n if αc < 0, then IQ c is defined similarly, with all yc ∈ Ic being vectors in (R− ) . Given xd ∈ i I(CS d ) and y ∈ c∈CS \CS |S Ic , recall that q (xd , y) is the payoff of agent i from the deviation when the payoffs from CS d and the arbitration functionQ payoffs are divided according to xd and y, respectively. We now define a function TL : I(CS d ) × c∈CS \CS |S Ic → R as follows: TL(xd , y) = X min pi (CS , x) − q i (xd , y), 0 . i∈S The function TL measures the total loss incurred by the members of S who are hurt by the deviation; these are the members of S who, despite joining the deviators, Q do not enjoy a profit from deviating. Observe that TL is continuous, and that both I(CS d ) and c∈CS \CS |S Ic are compact sets; thus, TL attains its minimum value on its domain. Among all minimizers of this function, pick one for which the number of agents i with pi (CS , x) < q i (xd , y) is the largest; denote this point by (x0 , y0 ). Now, let us color the agents in S as follows: an agent i ∈ S is green if pi (CS , x) < q i (x0 , y0 ); red if pi (CS , x) > q i (x0 , y0 ) and white if pi (CS , x) = q i (x0 , y0 ). Green agents derive a strictly positive benefit from the proposed deviation, red agents suffer a loss, and white agents break even. Now, consider a green agent g, and suppose that g can legally transfer payoff to some agent i under x0 and y0 , i.e., (a) both g and i are in the support of a coalition c in CS d and g receives a positive payoff from c, or (b) both g and i are in the support of a coalition c − d(c) such that c ∈ CS \ CS |S , αc > 0, and g receives a positive payoff from c, or (c) both g and i are in the support of a coalition c − d(c) such that c ∈ CS \ CS |S , αc < 0, and i receives a negative payoff from c. If i is red, g can transfer a small positive payoff to i while remaining green, and the resulting payoff division would have a strictly lower value of TL than (x0 , y0 ), a contradiction. Similarly, if i is white, g can transfer a small amount to i, making it green as well, without changing the value of T L; this is a contradiction, since we chose (x0 , y0 ) so as to maximize the number of green 14 agents. Thus, if both g and i are in the support of some coalition after the deviation (i.e., either a coalition in CS d or a surviving coalition in CS \ CS |S ), then g cannot receive a positive payoff from that coalition. By the same argument, if a coalition in CS \ CS |S assigns a negative payoff to the deviating agents under A, then only the green agents incur a loss from that coalition. Let Sg be the set of green agents in S. We have argued that the agents in Sg receive no payoff from coalitions they form with non-green agents in S. It follows that Sg can A-profitably deviate from (CS , x). Indeed, suppose that the agents in S \ Sg do not deviate, and the agents in Sg deviate by only withdrawing resources they need for forming the coalitions among themselves in CS d ; the resources that Sg withdrew from CS in the deviation CS 0 in order to invest in coalitions with members of S \ Sg in CS d are kept as is. Since A is deviation-monotone, the payment that Sg receives from the arbitration function under this new deviation is weakly higher than under CS 0 . Furthermore, suppose that Sg forms the same coalitions as in CS d |Sg , divides payoffs from these coalitions according to x0 , and distributes the arbitration function payoffs according to y0 , with any surplus payments from the arbitration function shared arbitrarily. Then the payoffs of all members of Sg are at least as high as under CS 0 , x0 and y0 ; since these agents were green, each of them benefits from this new deviation. Finally, note that Sg 6= ∅, since pS (CS , x) < A∗ (CS , x, S). This concludes the proof. Simply put, Theorem 3.4 states that if the most that a set S can get by deviating from (CS , x) is strictly greater than its payoff from (CS , x), then there is a non-empty subset of S that can A-profitably deviate. Note that the distinction between coalitional value and the profitability of deviating exists in cooperative games with coalition structures as well. Example 3.5. Consider a modified version of the three player 2-majority game: the agent set is N = {1, 2, 3}, the value of any coalition S ⊆ N of size at least 2 is 6, and the value of each singleton is 1. Suppose that agents form the coalition N , and divide payoffs so that each agent receives 2. The set N can earn more by forming the coalition structure ({1, 2}, {3}), whose value is 7. However, there is no way to divide payoffs from this coalition structure so that every agent receives more than 2: agent 3 can only receive 1, so it is not better off. Thus, N cannot deviate as a whole, but the coalition {1, 2} or the singleton {3} (or both, depending on how the value of the grand coalition is distributed) have a profitable deviation. Theorem 3.4 provides us with a justification for using A∗ (CS , x, S) as a measure of the deviators’ satisfaction with the outcome. Indeed, if S can A-profitably deviate from (CS , x) via some deviation CS 0 , then clearly A∗ (CS , x, S) > pS (CS , x). On the other hand, if A∗ (CS , x, S) > pS (CS , x), then there is some T ⊆ S that can A-profitably deviate from (CS , x). 4. The Arbitrated Core Given an OCF game G = hN, vi and an arbitration function A, we say that an outcome (CS , x) is A-stable if there is no set S ⊆ N that can A-profitably deviate from (CS , x). The arbitrated core of G with respect to an arbitration function A, or the A-core of G (denoted Core(G, A)), is the set of all A-stable outcomes of G. Using Theorem 3.4, we obtain the following characterization of A-stable outcomes. Theorem 4.1. Let G = hN, vi be an OCF game. An outcome (CS , x) is in the A-core of G if and only if for every S ⊆ N we have pS (CS , x) ≥ A∗ (CS , x, S). 15 Proof. First, suppose that for every S ⊆ N we have pS (CS , x) ≥ A∗ (CS , x, S). Let CS 0 be an arbitrary deviation of S from CS . We have pS (CS , x) ≥ A(CS , x, S, CS 0 ). Thus, no matter how S divides the deviation payoffs, there would be at least one agent i ∈ S who gets no more than pi (CS , x). As this is true for an arbitrary deviation CS 0 , it follows that S cannot A-profitably deviate. Conversely, suppose that pS (CS , x) < A∗ (CS , x, S). By Theorem 3.4, there is a subset of S that can A-profitably deviate from (CS , x), thus (CS , x) is not A-stable. Let A and A¯ be two arbitration functions. Intuitively, it is clear that if A is more lenient than ¯ ¯ A, then the A-core is contained in the A-core. Indeed, if an outcome (CS , x) is stable with respect to A and A always pays more to the deviators than A¯ (thus making the deviation more tempting), ¯ then (CS , x) should be A-stable as well. To formalize this intuition, we use the following notation. ¯ we write A ≥ A¯ if for every set S ⊆ N and every Given two arbitration functions A and A, ∗ outcome (CS , x) it holds that A (CS , x, S) ≥ A¯∗ (CS , x, S). We can now state our observation as follows. ¯ Corollary 4.2. If A ≥ A¯ then Core(G, A) ⊆ Core(G, A). Proof. Suppose that (CS , x) is in Core(G, A). This means that for all S ⊆ N we have pS (CS , x) ≥ ¯ it follows that pS (CS , x) ≥ A¯∗ (CS , x) for all S ⊆ N as well, which A∗ (CS , x, S). Since A ≥ A, ¯ implies (CS , x) ∈ Core(G, A). The conservative, sensitive, refined and optimistic arbitration functions described in Section 3.2, denoted Ac , As , Ar and Ao , respectively, satisfy Ao ≥ Ar ≥ As ≥ Ac . Thus, Corollary 4.2 implies that the conservative core contains the sensitive core, which contains the refined core, which contains the optimistic core. These observations (with respect to the conservative, refined, and optimistic core only) have been made by Chalkiadakis et al. (2010) as well; in fact, Chalkiadakis et al. (2010) show that these containments can be strict, i.e., there are games for which the conservative core strictly contains the refined core, and there are games for which the refined core strictly contains the optimistic core. A similar separation can be shown for the sensitive core. 4.1 Some Arbitrated Cores Using the characterization result of Theorem 4.1, we now proceed to describe some arbitrated cores, namely, those corresponding to the arbitration functions introduced in Section 3.2. Conservative Core As argued in Section 3.2, for every outcome (CS , x) and every set S ⊆ N , the most that S can get under the conservative arbitration function is v ∗ (eS ). Thus, the conservative core is the set of all outcomes (CS , x) such that for every set S ⊆ N it holds that pS (CS , x) ≥ v ∗ (eS ). (3) Sensitive Core In order for an outcome (CS , x) to be stable under the sensitive arbitration function, for every set S ⊆ N and every T ⊆ N \ S it should hold that pS (CS , x) ≥ v ∗ (w(CS |S ) + wS (CS T )) + pS (CS \ (CS |S ∪ CS T ), x); recall that CS T is the set of all coalitions in CS that involve members of T . Subtracting payments associated with coalitions in CS \ (CS |S ∪ CS T ) from both sides of this inequality, we get pS (CS |S , x) + pS (CS T , x) ≥ v ∗ (w(CS |S ) + wS (CS T )). 16 Chalkiadakis et al. (2010) show that if CS is not an optimal coalition structure then (CS , x) is not in the conservative core and consequently it is not in the sensitive core either. Thus, we can assume that CS is an optimal coalition structure, and hence CS |S is optimal for any S ⊆ N , i.e., v(CS |S ) = v ∗ (w(CS |S )). We also have pS (CS |S , x) = v(CS |S ). This implies that, in order for (CS , x) to be in the sensitive core, it must be the case that CS is an optimal coalition structure and for every S ⊆ N and every T ⊆ N \ S it holds that pS (CS T , x) ≥ v ∗ (w(CS |S ) + wS (CS T )) − v ∗ (w(CS |S )), (4) i.e., the total payoff to S from CS T must be at least the marginal benefit of using the resources S has invested in CS T . Note that if we take T = N \ S, we obtain the conservative core condition. The Refined Core For the refined core, we have c )) + pS (CS \ CS c , x) | CS |S ⊆ CS c ⊆ CS }. A∗r (CS , x, S) = max{v ∗ (wS (CS Thus, an outcome (CS , x) is in the refined core if and only if for every S ⊆ N and for every c containing CS |S it holds that coalition structure CS c )) + pS (CS \ CS c , x). pS (CS , x) ≥ v ∗ (wS (CS c it holds that Consequently, (CS , x) is in the refined core if and only if for every such S and CS c , x) ≥ v ∗ (wS (CS c )). pS (CS (5) c containing CS |S should be at In other words, the payoff to S from every coalition structure CS c . Note that if we least as large as the most that S can get from the resources it has invested in CS c such that CS c = CS |S ∪ CS T for some T ⊆ N \ S, we limit ourselves to coalition structures CS obtain the sensitive core condition. The Optimistic Core For the optimistic arbitration function, Ao , we have shown that X c ) + w(CS 0 )) + c , x)}, A∗o (CS , x, S) = sup{v ∗ (wS (CS v(c − d(c)) − pN \S (CS \ CS c c∈CS \CS c such that CS |S ⊆ CS c ⊆ CS and over where the supremum is taken over all coalition structures CS 0 c . Thus, in order for an outcome (CS , x) to be in the optimistic all deviations CS of S from CS \ CS c ⊆ CS containing core, it must be the case that for every set S ⊆ N , every coalition structure CS 0 c it holds that CS |S and every deviation CS of S from CS \ CS X c ) + w(CS 0 )) + c , x). (6) pS (CS , x) ≥ v ∗ (wS (CS v(c − d(c)) − pN \S (CS \ CS c c∈CS \CS c , CS 0 ) denote the coalition structure formed by what remains of CS \ CS c after Let ∆(CS \ CS P 0 S has withdrawn resources from CS according to CS . We obtain c∈CS \CS c v(c − d(c)) = c , CS 0 )). Thus, subtracting pS (CS \ CS c , x) from both sides of inequality (6) and v(∆(CS \ CS c , x) = v(CS \ CS c ), we can rewrite inequality (6) as using the fact that pN (CS \ CS c , x) ≥ v ∗ (wS (CS c ) + w(CS 0 )) − v(CS \ CS c ) − v(∆(CS \ CS c , CS 0 )) . pS (CS (7) 17 The optimistic core stability condition is thus similar to the refined core stability condition; however, c if it is willing to assume the S is also allowed to withdraw resources from coalitions outside of CS marginal costs of this withdrawal. Example 4.3. Consider the following example. We have three players, N = {1, 2, 3}, and the following characteristic function: 0 0 1 1 1 1 v 4 = 1, v 2 = 40, v 41 = 20, 0 0 2 and v(c) = 0 for every other coalition c ∈ [0, 1]3 . First, we observe that the only optimal coalition structure (up to the order of coalitions) is CS = (c1 , c2 , c3 ), where 0 1 c1 = 1 2 , 1 4 1 2 c2 = 0 0 , c3 = 1 4 1 2 . In words, players 1 and 2 collaborate on one project (which requires 100% of player 1’s resources, and 50% of player 2’s resources), and generate a revenue of 40; players 2 and 3 work on two identical projects (each requiring 25% of player 2’s resources and 50% of player 3’s resources), generating a revenue of 40 in total as well. Now, suppose that payoffs are divided according to x = (x1 , x2 , x3 ), where 40 0 0 x1 = 0 , x2 = 0 , x3 = 4 . 0 20 16 Under the conservative arbitration function, this payoff division is stable: no subset of players receives less than the most it can make on its own. However, under the sensitive arbitration function, this is no longer the case: player 2 must receive a payoff of at least 2 from c1 , and a combined payoff of at least 2 from c2 and c3 . Now, let us suppose that the following payoff division is proposed instead: y = (y1 , y2 , y3 ), where 38 0 0 y1 = 2 , y2 = 0 , y3 = 2 . 0 20 18 The outcome (CS , y) is stable with respect to the sensitive arbitration function; however, it is not stable with respect to the refined arbitration function: player 2 can withdraw its contribution to c2 and earn strictly more. Thus, in order for an imputation to be r-stable, player 2 must receive at least 2 from c1 , and at least 1 from each of c2 and c3 . Example 4.3 illustrates an interesting phenomenon: more lenient arbitration functions force payments to be more spread out: player 2 receives the same payoff, but the payoff must be received in a more distributed manner when more lenient reactions to deviations are assumed. 5. Non-emptiness of Arbitrated Cores Core outcomes are highly desirable both in classic cooperative games and in OCF games. Thus, it is important to find conditions on the characteristic function of an OCF game that would guarantee non-emptiness of its arbitrated core, as well as to identify classes of OCF games whose arbitrated core is always non-empty, for natural arbitration functions. We note that both of these questions can 18 be—and have been—looked at through the lens of computational complexity. That is, one can ask whether there exist polynomial-time algorithms that decide whether the arbitrated core is non-empty or find an outcome in the arbitrated core, either for the general model or for specific classes of OCF games. While this question has been explored by Chalkiadakis et al. (2010) and Zick, Chalkiadakis, and Elkind (2012), in this paper we do not consider computational complexity issues and focus instead on characterization results. Our characterization results are similar in spirit to the celebrated Bondareva–Shapley condition for core non-emptiness in classic cooperative games (Bondareva, 1963; Shapley, 1967). We will now briefly state this condition. Given a set P N = {1, . . . , n}, a collection of weights (δS )S⊆N is called balanced if δS ≥ 0 for all S ⊆ N and S:i∈S δS = 1 for all i ∈ N . We can view a balanced collection of weights as a way for an agent i to partially participate in all sets that contain i, with its contribution specified by the respective weight. Given a cooperative game G = hN, ui where u : 2N → PR+ , we say that G is balanced if for every balanced collection of weights (δS )S⊆N it holds that S⊆N δS u(S) ≤ u(N ). Theorem 5.1 (Bondareva–Shapley Theorem). A cooperative game G = hN, ui with u : 2N → R+ has a non-empty core if and only if it is balanced. An important feature of this characterization is that it is stated in terms of the characteristic function itself, and does not explicitly refer to outcomes of the game. In what follows, we describe similar characterizations for OCF games, for the conservative, sensitive and refined arbitration functions.1 Specifically, for each of these arbitration functions, given an OCF game G = hN, vi and a coalition structure CS ∈ CS(N ), we characterize the set of imputations x ∈ I(CS ) such that (CS , x) is in the respective arbitrated core of G. We limit our attention to optimal coalition structures, i.e., we assume that v(CS ) = v ∗ (eN ): if CS is not optimal, then no outcome of the form (CS , x) can be in the arbitrated core of G for any of our arbitration functions, since the grand coalition itself can profitably deviate from (CS , x) (Chalkiadakis et al., 2010). 5.1 The Conservative Core Given an OCF game G = hN, vi and a coalition structure CS = (c1 , . . . , cm ), we say that a collection of non-negative weights {(rj )m j=1 ; (δS )S⊆N } is c-balanced with P respect to CS if for every i ∈ N and every coalition cj such that i ∈ supp(cj ) it holds that rj + S:i∈S δS = 1. Chalkiadakis et al. (2010) show the following result. Theorem 5.2 (Theorem 2, Chalkiadakis et al. (2010)). Given an OCF game G = hN, vi and an optimal coalition structure CS ∈ CS(N ), there exists an outcome x ∈ I(CS ) such that (CS , x) is in the conservative core of G if and only if for every collection of non-negative weights {(rj )m j=1 ; (δS )S⊆N } that is c-balanced with respect to CS it holds that m X j=1 rj v(cj ) + X δS v ∗ (eS ) ≤ v ∗ (eN ). S⊆N Our first observation is that the proof of Theorem 5.2, as given in (Chalkiadakis et al., 2010), has a gap. Appendix A contains a correction to the proof. 1. The case of the conservative arbitration function has been considered by Chalkiadakis et al. (2010); we reproduce their results for completeness and to facilitate the comparison with the other two cases. 19 We will now provide an alternative characterization of OCF games with non-empty conservative core, by establishing a connection between the conservative core of an OCF game and the core of a related classic cooperative game. Given an OCF game G = hN, vi, its discrete superadditive cover is a classic cooperative game ¯ G = hN, Uv i, where Uv (S) = v ∗ (eS ). Simply put, the value of a set S ⊆ N in G¯ is the most that it can make under the function v by forming a coalition structure. We will now show that the conservative core of G is non-empty if and only if the core of G¯ is non-empty. Theorem 5.3. The conservative core of an OCF-game G = hN, vi is non-empty if and only if the core of its discrete superadditive cover G¯ = hN, Uv i is non-empty. Proof. We have argued that if the conservative core of G is non-empty, then there exists an outcome (CS , x) such that for all S ⊆ N we have pS (CS , x) ≥ v ∗ (eS ). Note that CS is an optimal coalition structure for G, since v(CS ) = pN (CS , x) ≥ v ∗ (eN ). Consider the payoff vector p = (p1 , . . . , pn ) ¯ Indeed, since CS where pi = pi (CS , x) i ∈ N . It follows that p is in the core of G. Pnfor all i ∗ N is optimal, we have i=1 p = v(CS ) = v (e ) = Uv (N ), and for every S ⊆ N we have p(S) = pS (CS , x) ≥ v ∗ (eS ) = Uv (S). ¯ Fix a coalition structure Conversely, let p = (p1 , . . . , pn ) be a payoff vector in the core of G. ∗ N CS = (c1 , . . . , cm ) such that v(CS ) = v (e ). We will now use p to construct an imputation x ∈ I(CS ) such that (CS , x) is in the conservative core of G. Given an imputation z ∈ I(CS ), we color the agents in N as follows: i is green if pi (CS , z) > pi ; red if pi (CS , z) < pi and white if pi (CS , z) = pi . Green agents are better off under (CS , z) than under p, red agents are worse off under (CS , z) than under p, and white agents are indifferent. Now, suppose that there is some z ∈ I(CS ) such that no agent in the respective coloring is green. Since CS is optimal, this means that no agent is red either. Thus, all agents are white. This in turn implies that for all S ⊆ N we have pS (CS , z) = p(S) ≥ Uv (S) = v ∗ (eS ), so (CS , z) is in the conservative core. Thus, all we need to show is that there exists some z ∈ I(CS ) such that no agent in the respective coloring is green. Let F : I(CS ) → R be defined as follows: F (z) = n X max{0, pi − pi (CS , z)}. i=1 The function F measures the agents’ total unhappiness with the outcome (CS , z) as compared to p. F is a continuous function (it is the sum of the maxima of functions that are continuous in z), and I(CS ) is a compact set. Thus, there exists an imputation x ∈ I(CS ) that minimizes the value of F . We pick x ∈ arg min F (z) so as to minimize the number of white agents in the respective coloring of N . Now suppose that there exist a green agent g, a non-green agent i and a coalition c ∈ CS such that g, i ∈ supp(c) and x(c)g > 0. Then there is some ε > 0 such that setting x ¯(c)g = x(c)g − ε and x ¯(c)i = x(c)i + ε (i.e., transferring an amount of ε from g to i within the coalition c) results in a valid payoff division for CS and keeps g green. If i was white prior to this transfer, it now becomes green (and the value of F does not change). This is a contradiction to the fact that x minimizes the number of white agents. On the other hand, if i was red, the transfer decreases the contribution of i to F (while g’s contribution to F remains 0), which is a contradiction to the fact 20 that x ∈ arg min F (z). This means that green agents get zero payoff from coalitions with non-green agents. Let us denote the set of green agents by Sg . We have pSg (CS , x) = pSg (CS |Sg , x) ≤ v ∗ (eSg ). On the other hand, if Sg 6= ∅, since for each i ∈ Sg we have pi (CS , x) > pi , we obtain pSg (CS , x) > p(Sg ) ≥ Uv (Sg ) = v ∗ (eSg ). This contradiction shows that Sg = ∅, and we have argued that in this case all agents are white. This completes the proof. The following corollary is immediately implied by the proof of Theorem 5.3. Corollary 5.4. Consider an OCF game G = hN, vi. For every payoff vector p = (p1 , . . . , pn ) in the core of G¯ and every optimal coalition structure CS ∈ CS(N ), there exists an x ∈ I(CS ) such that pi = pi (CS , x) for all i ∈ N . Corollary 5.4 enables us to generalize the following well-known result for classic cooperative games. Aumann and Dr`eze (1974) show that if CS and CS 0 are optimal (non-overlapping) coalition structures for G = hN, ui and (CS , p) is in the core of G then (CS 0 , p) is also in the core of G. In other words, if CS opt is the set of all optimal coalition structures for G, and Istab is the set of all stable payoff divisions for G, then the set of core outcomes for G is CS opt × Istab . Using Corollary 5.4, we can extend this result to OCF games under the conservative arbitration function. Corollary 5.5. Consider an OCF game G = hN, vi. For every pair of optimal coalition structures CS , CS 0 ∈ CS(N ) and every imputation x ∈ I(CS ) such that (CS , x) is in the conservative core, there exists an imputation x0 ∈ I(CS 0 ) such that (CS 0 , x0 ) is in the conservative core of G and pi (CS , x) = pi (CS 0 , x0 ) for all i ∈ N . 5.1.1 C ONVEXITY IN OCF G AMES R EVISITED For classic cooperative games, convexity, or supermodularity, of the characteristic function is wellknown to be a sufficient condition for non-emptiness of the core (Shapley, 1971). In more detail, recall that a cooperative game G = hN, vi is said to be supermodular if for every pair of sets S, T such that S ⊆ T ⊆ N and every R ⊆ N \ T it holds that v(T ∪ R) − v(T ) ≥ v(S ∪ R) − v(S). Supermodular games are often referred to as convex games in the literature; however, to avoid confusion with other notions of convexity considered in this paper, we use the term “supermodularity”. Shapley (1971) proves the following result. Theorem 5.6. If a cooperative game G is supermodular, then its core is non-empty. In order to extend Theorem 5.6 to OCF games, Chalkiadakis et al. (2010) propose the following notion of convexity for OCF games. 21 Definition 5.7 (OCF convexity, (Chalkiadakis et al., 2010)). An OCF game is OCF-convex if for every pair of sets S, T such that S ⊆ T ⊆ N , every R ⊆ N \ T , every outcome (CS S , xS ) ∈ F(S), every outcome (CS T , xT ) ∈ F(T ), and every outcome (CS S∪R , xS∪R ) ∈ F(S ∪ R) the following condition holds: if pi (CS S , xS ) ≤ pi (CS S∪R , xS∪R ) for all i ∈ S then there is an outcome (CS T ∪R , xT ∪R ) ∈ F(T ∪ R) such that (1) pi (CS T , xT ) ≤ pi (CS T ∪R , xT ∪R ) for all i ∈ T ; (2) pi (CS S∪R , xS∪R ) ≤ pi (CS T ∪R , xT ∪R ) for all i ∈ S ∪ R. Intuitively, Definition 5.7 simply means that larger coalitions can offer more lucrative options to players who join them, compared to smaller coalitions. Chalkiadakis et al. (2010) then show that OCF convexity is a sufficient condition for nonemptiness of the conservative core. Theorem 5.8 (Theorem 3, Chalkiadakis et al. (2010)). If an OCF game G is OCF-convex, then its conservative core is non-empty. On the other hand, combining Theorem 5.3 with Theorem 5.6, we obtain the following sufficient condition for conservative core non-emptiness. Proposition 5.9. Consider an OCF game G. If G¯ = hN, Uv i is supermodular, then the conservative core of G is non-empty. We will now argue that Proposition 5.9 is strictly stronger than Theorem 5.8, by showing that supermodularity of G¯ is a strictly weaker condition than OCF-convexity of G. We will first show ¯ We then present an example of a game that OCF-convexity of G implies supermodularity of G. ¯ G = hN, vi such that G is supermodular, but G is not OCF-convex (Example 5.13). To implement the first step of this plan, we first establish the following crucial proposition, which may seem counterintuitive at first sight. Its proof is based on coloring arguments similar to the ones used in the proofs of Theorems 3.4 and 5.3. Proposition 5.10. For every pair of sets S, T such that S ⊆ T ⊆ N and every pair of optimal coalition structures CS S ∈ CS(S), CS T ∈ CS(T ), there exist imputations x ∈ I(CS S ) and y ∈ I(CS T ) such that pi (CS S , x) = pi (CS T , y) for all i ∈ S. Proof. Fix the sets S and T and optimal coalition structures CS S ∈ CS(S), CS T ∈ CS(T ). We will first establish that we can find imputations x0 ∈ I(CS S ) and y0 ∈ I(CS T ) with pi (CS S , x0 ) ≤ pi (CS T , y0 ) for all i ∈ S. We will then show how to use this fact to prove our original claim. Lemma 5.11. There exist imputations x0 ∈ I(CS S ) and y0 ∈ I(CS T ) such that pi (CS S , x0 ) ≤ pi (CS T , y0 ) for all i ∈ S. Proof. Given a pair of imputations x ∈ I(CS S ), y ∈ I(CS T ), we color the agents in T as follows: an agent i is green if i ∈ S and pi (CS T , y) > pi (CS S , x) or if i ∈ T \ S and pi (CS T , y) > 0; red if i ∈ S and pi (CS T , y) < pi (CS S , x); and white otherwise. We define a mapping D : I(CS S ) × I(CS T ) → R by setting X D(x, y) = max{0, pi (CS S , x) − pi (CS T , y)}. i∈S 22 The function D is continuous over a compact set, and thus attains its minimum value at some point (x, y) ∈ I(CS S ) × I(CS T ). Among all such points, pick one with the smallest number of white agents and denote it by (x0 , y0 ). Let q i = pi (CS T , y0 ) for i ∈ T , pi = pi (CS S , x0 ) for i ∈ S. We will now show that q i ≥ pi for all i ∈ S. Assume for the sake of contradiction that this is not the case. Then D(x0 , y0 ) > 0 and there is at least one red agent in T . Since v ∗ (T ) ≥ v ∗ (S), there is also a green agent in T . Now, consider a green agent g and a non-green agent i. Suppose that (a) there exists a coalition c ∈ CS T such that g, i ∈ supp(c) and y0 (c)g > 0, or (b) there exists a coalition c ∈ CS S such that g, i ∈ supp(c) and x0 (c)i > 0. In case (a) we can modify y0 by making g transfer a small amount of payoff to i, and in case (b) we can modify x0 by making i transfer a small amount of payoff to g; we choose the transfer to be small enough that g remains green. If i was white, it now becomes green, and if i was red, this lowers its contribution to D. In both cases, we get a contradiction with our choice of (x0 , y0 ). Thus, no such coalition c exists. Let Sg denote the set of all green agents in S, and let Sng = S \ Sg . Under x0 , every i ∈ Sng gets no payoff from coalitions in CS S whose support contains members of Sg . Similarly, under y0 green agents in T get no payoff from coalitions in CS T that contain members of Sng . Now, suppose that we modify CS T by having the agents in Sng abandon their existing coalitions and form the coalitions they form among themselves in CS S instead. Denote the resulting coalition structure by CS 0 . We define an imputation z0 for CS 0 as follows. The imputation z0 coincides with y0 for each c with supp(c) ∩ Sng = ∅, and it coincides with x0 for each coalition c0 that is formed by the members of Sng . The remaining coalitions in CS 0 involve both agents in Sng and agents in T \ Sng , and may have suffered a reduction in their value relative to CS T after Sng withdrew resources from them; for such coalitions z0 distributes their value arbitrarily among the members of Sng . As argued above, in (CS S , x0 ) the members of Sng only receive payoffs from coalitions that they fully control, so pi (CS 0 , z0 ) ≥ pi (CS S , x0 ) for all i ∈ Sng . Further, since at least one agent in S is red, we have pSng (CS S , x0 ) > pSng (CS T , y0 ). On the other hand, in (CS T , y0 ) the members of T \ Sng receive no payoff from coalitions with members of Sng , so letting Sng receive all of the payoffs from those coalitions does not affect the payoff that the members of T \ Sng receive, relative to what they received in (CS T , y0 ). Thus, for all i in T \ Sng it holds that pi (CS 0 , z0 ) = pi (CS T , y0 ). Hence, we obtain v(CS 0 ) = pT (CS 0 , z0 ) T \Sng = p > p T \Sng (8) 0 (CS , z0 ) + p Sng (CS T , y0 ) + p ∗ 0 (CS , z0 ) Sng (CS T , y0 ) T = v(CS T ) = v (e ). This contradiction shows that the set of red agents is empty and hence pi (CS T , y0 ) ≥ pi (CS S , x0 ) for all i ∈ S. We will now use Lemma 5.11 to complete the proof of Proposition 5.10. Define P (CS S , CS T ) = {(x, y) ∈ I(CS S ) × I(CS T ) | pi (CS T , y) ≥ pi (CS S , x) for all i ∈ S}. 23 Lemma 5.11 implies that P (CS S , CS T ) is not empty. Moreover, P (CS S , CS T ) is compact; thus, it contains a point (x, y) that minimizes the value pS (CS T , y) over P (CS S , CS T ). Let M (CS S , CS T ) be the set of points (x, y) in P (CS S , CS T ) that minimize pS (CS T , y); to complete the proof, we will identify a point (x1 , y1 ) in M (CS S , CS T ) such that pS (CS T , y1 ) = pS (CS S , x1 ) = v ∗ (eS ). Given a point (x, y) ∈ M (CS S , CS T ), we color the agents in T as follows: i is green if i ∈ S and pi (CS T , y) > pi (CS S , x), and white otherwise. Note that, since (x, y) ∈ P (CS S , CS T ), if S contains a white agent i, we have pi (CS T , y) = pi (CS S , x). Let (x1 , y1 ) be a point in M (CS S , CS T ) that maximizes the number of green agents in T . Now, consider a green agent g and a white agent i. Suppose that (a) g ∈ S, i ∈ T , and there is a coalition c ∈ CS T such that g, i ∈ supp(c) and y(c)g > 0, or (b) g, i ∈ S, and there is a coalition c ∈ CS S such that g, i ∈ supp(c) and x(c)i > 0. In case (a) we could transfer a small amount of payoff from g to i in CS T so as to either make i green and thereby increase the number of green vertices (if i ∈ S) or lower the total payoff of S in CS T (if i ∈ T \ S), and in case (b) we could transfer a small amount of payoff from i to g in CS S so as to make i green (again, we choose the transfer to be small enough that g remains green). In both cases, we get a contradiction with our choice of (x1 , y1 ). Let Sg be the set of all green agents in S, and let Sw = S \ Sg be the set of all white agents in S. We have shown that in (CS S , x1 ) the members of Sw do not receive payoffs from their joint coalitions with members of Sg , and in (CS T , y1 ) the members of Sg do not receive payoffs from their joint coalitions with members of Sw , so we have pSw (CS S , x1 ) ≤ v ∗ (eSw ) and pSg (CS T , y1 ) ≤ v ∗ (eSg ). Thus, if Sg 6= ∅, we have v ∗ (eS ) = pS (CS S , x1 ) Sg = p (CS S , x1 ) + p (9) Sw (CS S , x1 ) ∗ < p (CS T , y1 ) + v (eSw ) Sg ≤ v ∗ (eSg ) + v ∗ (eSw ). Thus, if Sg 6= ∅, then v ∗ (eS ) < v ∗ (eSg ) + v ∗ (eSw ), a contradiction with the superadditivity of v ∗ . We conclude that Sg = ∅, which implies that pi (CS S , x1 ) = pi (CS T , y1 ) for all i ∈ S. Armed with Proposition 5.10, we are now ready to prove the following theorem. Theorem 5.12. If G = hN, vi is OCF-convex then G¯ = hN, Uv i is supermodular. Proof. Consider sets S, T, R ⊆ N such that S ⊆ T and R ⊆ N \ T ; we will demonstrate that Uv (S ∪ R) − Uv (S) ≤ Uv (T ∪ R) − Uv (T ). Set S 0 = S ∪ R, T 0 = T ∪ R, and consider coalition 0 structures CS S ∈ CS(S), CS S 0 ∈ CS(S 0 ) such that v(CS S ) = v ∗ (eS ), v(CS S 0 ) = v ∗ (eS ). By Proposition 5.10, there exist imputations xS and xS 0 such that pi (CS S , xS ) = pi (CS S 0 , xS 0 ) for all i ∈ S; thus, the total payoff to R from (CS S 0 , xS 0 ) is v ∗ (eS∪R ) − v ∗ (eS ). Consider an outcome (CS T , xT ) ∈ FT such that v(CS T ) = v ∗ (eT ); since G is OCF-convex, there is an outcome (CS T 0 , xT 0 ) that is better for all members of S 0 than (CS S 0 , xS 0 ), and also pays T a total of at least v ∗ (eT ). The payoff to R under (CS T 0 , xT 0 ) is v(CS T 0 ) − pT (CS T 0 , xT 0 ). We have v(CS T 0 ) ≤ v ∗ (eT ∪R ) and pT (CS T 0 , xT 0 ) ≥ v ∗ (eT ), so the payoff to R in (CS T 0 , xT 0 ) is at 24 most v ∗ (eT ∪R ) − v ∗ (eT ). Finally, OCF convexity of G implies that the payoff to R in (CS T 0 , xT 0 ) is at least as large as its payoff in (CS S 0 , xS 0 ). Combining these inequalities, we get Uv (S ∪ R) − Uv (S) = v ∗ (eS∪R ) − v ∗ (eS ) = pR (CS S 0 , xS 0 ) ≤ pR (CS T 0 , xT 0 ) ≤ v ∗ (eT ∪R ) − v ∗ (eT ) = Uv (T ∪ R) − Uv (T ), which concludes the proof. Theorem 5.12 shows that if an OCF game is OCF-convex, then its discrete superadditive cover is supermodular. We will now show that the converse does not always hold, i.e., supermodularity is a strictly weaker property than OCF convexity. Example 5.13. Consider a game G = hN, vi where N = {1, 2, 3} and v is defined as follows: • v 1 = 1, v • v 1 = 6, v • v 1 = 4, v 0 0 .5 0 0 1 0 1 0 = 1; 0 .5 1 0 1 1 = 3; = 4; • v(c) = 0 for any other partial coalition c ∈ [0, 1]3 . We have • Uv ({1}) = Uv ({2}) = 1, Uv ({3}) = 0; • Uv ({1, 2}) = 6, Uv ({1, 3}) = Uv ({2, 3}) = 4; • Uv (N ) = 9. One can check that Uv is indeed supermodular. However, G is not Indeed, OCF-convex. set S = 0 0 1 0 0 1 {3}, T = {1, 3}, R = {2}, with CS S = , CS T = , CS S∪R = . Assume 1 1 1 that the players in T and S ∪ R share the payoffs according to xT = ((0, 0, 4)) and xS∪R = ((0, 4, 0)), respectively. For G to be OCF-convex, there has to exist a coalition structure CS where player 3 earns at least 4 and player 2 earns at least 4. However, this is impossible: if player 3 earns 0 1 0 at least 4, then CS contains either c = 0 or c = 1 . If c is formed, then player 2 can get at 1 1 most 1; if c0 is formed, then players 2 and 3 together can get at most 4. Thus, there is no way to satisfy all of the agents’ demands. 25 5.2 The Sensitive Core Recall that under the sensitive arbitration function, an agent will withhold payments from the deviators if any of the coalitions it participates in are hurt by the deviation. In Section 4.1, we obtained the following characterization of the sensitive core: an outcome (CS , x) is in the sensitive core if and only if CS is an optimal coalition structure, and for each set S ⊆ N it holds that for each T ⊆ N \ S the total payoff that S receives from investing its resources in coalitions involving T is at least as large as the marginal returns of investing the same resources in working on its own (see formula (4)). Let CS = (c1 , . . . , cm ) be an optimal coalition structure. Using the characterization above, we conclude that deciding whether the sensitive core contains an outcome of the form (CS , x) is equivalent to determining whether the value of the following linear program equals v ∗ (eN ). m P min P j=1 i∈supp(cj ) (10) xij ≥ v(cj ) P s.t. xij ∀cj ∈ CS i∈supp(cj ) pS (CS T , x) ≥ v ∗ (wS (CS |S ) + wS (CS T )) − v ∗ (wS (CS |S )) ∀S ⊆ N, ∀T ⊆ N \ S We note that in the linear program (10) we do not require that xij ≥ 0 for each cj ∈ CS and each i ∈ supp(cj ). This is because the argument presented in Appendix A shows that these constraints can be safely omitted. We will revisit this point in the proof of Theorem 5.15 in the context of the refined core. Consider the dual of this linear program. max m P rj v(cj ) + j=1 s.t. P P δS,T (v ∗ (wS (CS |S ) +wS (CS T )) − v ∗ (wS (CS |S ))) (11) S⊆N T ⊆N \S rj + P P S:i∈S T ⊆N \S: supp(cj )∩T 6=∅ δS,T = 1 rj ≥ 0 δS,T ≥ 0 ∀cj ∈ CS , ∀i ∈ supp(cj ) ∀cj ∈ CS ∀S ⊆ N, ∀T ⊆ N \ S m We say that a collection of non-negative P weights P {(rj )j=1 ; (δS,T )S⊆N ;T ⊆N \S } is s-balanced with respect to CS = (c1 , . . . , cm ) if rj + S:i∈S T ⊆N \S:supp(cj )∩T 6=∅ δS,T = 1 for all cj ∈ CS and all i ∈ supp(cj ). Applying linear programming duality to linear programs (10) and (11), we obtain the following theorem. Theorem 5.14. The sensitive core of a game G = hN, vi is not empty if and only if there exists a coalition structure CS = (c1 , . . . , cm ) with v(CS ) = v ∗ (eN ) such that for every collection of non-negative weights {(rj )m j=1 ; (δS,T )S⊆N ;T ⊆N \S } that is s-balanced with respect to CS it holds that m X j=1 rj v(cj ) + X X δS,T (v ∗ (wS (CS |S ) + wS (CS T )) − v ∗ (wS (CS |S ))) ≤ v ∗ (eN ). S⊆N T ⊆N \S 26 Theorem 5.14 is similar to Theorem 5.2, which presents a criterion for non-emptiness of the conservative core. The main difference is that Theorem 5.2 considers collections of weights that contain a single weight δS for each set S ⊆ N , whereas for the sensitive core we consider collections of weights that contain a weight δS,T for each pair of disjoint sets S, T ⊆ N . 5.3 The Refined Core Under the sensitive arbitration function, the deviating players only need to decide which of the nondeviating players they do not wish to work with any more. In contrast, under the refined arbitration function, the deviators have to look at the coalitions with the non-deviators one by one, and decide which of them are worth keeping. We will now provide a characterization of games with nonempty refined core that is similar to the characterizations of games with non-empty conservative and sensitive cores (Theorem 5.2 and Theorem 5.14, respectively). Employing this characterization, we then describe a class of OCF games with a non-empty refined core. In Section 4.1, we obtained the following characterization of outcomes in the refined core: given a coalition structure CS , there is an imputation x ∈ I(CS ) such that (CS , x) is in the refined core if and only if pS (CS 0 , x) ≥ v ∗ (wS (CS 0 )) for every S ⊆ N and every coalition structure CS 0 ⊆ CS containing CS |S . In what follows, given a subset of agents S ⊆ N and a coalition structure CS , we write [CS ]S = {CS 0 ⊆ CS | CS |S ⊆ CS 0 }. Also, given a coalition structure CS = (c1 , . . . , cm ), we say that a collection of non-negative weights {(rj )m j=1 ; (δS,CS 0 )S⊆N ;CS 0 ∈[CS ]S } is r-balanced with respect to CS if for each cj ∈ CS and each i ∈ supp(cj ) it holds that X X rj + δS,CS 0 = 1. S:i∈S CS 0 ∈[CS ]S : cj ∈CS 0 We are now ready to present our characterization. Theorem 5.15. The refined core of an OCF game G = hN, vi is non-empty if and only if there exists a coalition structure CS = (c1 , . . . , cm ) with v(CS ) = v ∗ (eN ) such that for every collection of weights {(rj )m j=1 ; (δS,CS 0 )S⊆N ;CS 0 ∈[CS ]S } that is r-balanced with respect to CS it holds that m X rj v(cj ) + X X δS,CS 0 v ∗ (wS (CS 0 )) ≤ v ∗ (eN ). S⊆N CS 0 ∈[CS ]S j=1 Proof. Fix a coalition structure CS = (c1 , . . . , cm ) with v(CS ) = v ∗ (eN ), and consider the following linear program. m P min P j=1 i∈supp(cj ) s.t. P xij (12) xij ≥ v(cj ) ∀cj ∈ CS i∈supp(cj ) pS (CS 0 , x) ≥ v ∗ (wS (CS 0 )) ∀S ⊆ N, ∀CS 0 ∈ [CS ]S We claim that the refined core of G contains an outcome of the form (CS , x) if and only if the value of this linear program is v ∗ (eN ). 27 To see why this is the case, it suffices to observe that, by the argument in Appendix A, we can omit constraints of the form xij ≥ 0 for each cj ∈ CS and each i ∈ supp(cj ). In fact, it turns out that for the refined core, a much simpler explanation holds: Non-negativity of xij is implied by the stability constraints. To see this, consider a coalition cj such that i ∈ supp(cj ). If supp(cj ) = {i}, xij = v(cj ) ≥ 0 and we are done. Otherwise, consider the coalition structure CS 0 = (CS |{i} , cj ). The total payoff to i from CS 0 is pi (CS 0 , x) = pi (CS |{i} , x)+xij = v(CS |{i} )+xij . The constraint that corresponds to S = {i} and CS 0 states that this payoff must be at least v ∗ (w{i} (CS 0 )), which is at least v(CS |{i} ), and hence xij ≥ 0. Consider now the dual of linear program (12). max m P P rj v(cj ) + j=1 P rj + s.t. δS,CS 0 v ∗ (wS (CS 0 )) (13) S⊆N CS 0 ∈[CS ]S δS,CS 0 = 1 ∀cj ∈ CS , ∀i ∈ supp(cj ) δS,CS 0 ≥ 0 ∀S ⊆ N, ∀CS 0 ∈ [CS ]S S:i∈S CS 0 ∈[CS ]S :cj ∈CS 0 rj ≥ 0 ∀cj ∈ CS Observe that the dual constraints in (13) are equalities since xij are unconstrained in (12). Note also that every feasible solution of (13) corresponds to a collection of non-negative weights that is r-balanced with respect to CS . Our claim now follows by the standard linear programming duality argument. Theorem 5.15 enables us to identify an interesting class of OCF games with non-empty refined core. Recall that a function f : Rn → R is homogeneous of degree k, or k-homogeneous, if f (αx) = αk f (x) for all α ∈ R+ . Intuitively, this means that f scales in a consistent manner: if all players invest twice as much resources in a coalition, they will get 2k times the profit. The returns to scale are positive if k ≥ 1 and negative if k < 1. Corollary 5.16. Consider an OCF game G = hN, vi. If v ∗ is homogeneous of degree k ≥ 1, then the refined core of G is non-empty. Proof. Consider a coalition structure CS = (c1 , . . . , cm ) with v(CS ) = v ∗ (eN ) and a collection of non-negative weights {(rj )m j=1 ; (δS,CS 0 )S⊆N ;CS 0 ∈[CS ]S } that is r-balanced with respect to CS . According to Theorem 5.15, it suffices to show that m X j=1 rj v(cj ) + X δS,CS 0 v ∗ (wS (CS 0 )) ≤ v ∗ (eN ). (14) S⊆N CS 0 ∈[CS ]S First, since v ∗ is k-homogeneous, we have X S⊆N CS 0 ∈[CS ]S δS,CS 0 v ∗ (wS (CS 0 )) ≤ v ∗ 28 X S⊆N CS 0 ∈[CS ]S δS,CS 0 wS (CS 0 ) . (15) δS,CS 0 wS (CS 0 ) by ω i . We have P Denote the i-th coordinate of S⊆N CS 0 ∈[CS ]S ωi = X X S:i∈S CS 0 ∈[CS ]S = m X cij j=1 X S:i∈S = cij cj ∈CS 0 X δS,CS 0 CS 0 ∈[CS ] cj ∈CS 0 m X X δS,CS 0 S: cij (1 − rj ), j=1 P where the first transition is derived from the fact that wi (CS 0 ) = cj ∈CS 0 cij if i ∈ S, and the second transition uses the fact that {(rj )m j=1 ; (δS,CS 0 )S⊆N ;CS 0 ∈[CS ]S } is r-balanced with respect to CS . We conclude that the right-hand side of equation (15) is upper-bounded by v∗( m X (1 − rj )cj ). j=1 We now consider the first summand in the left-hand side of (14). By k-homogeneity of v ∗ , we have m X rj v(cj ) ≤ j=1 m X m X rj v ∗ (cj ) ≤ v ∗ ( rj cj ). j=1 j=1 Using the superadditivity of v ∗ , we obtain that the left-hand side of (14) can be upper-bounded by m m m X X X v∗( rj cj + (1 − rj )cj ) = v ∗ ( cj ) = v ∗ (eN ). j=1 j=1 j=1 This concludes the proof. In fact, the proof of Corollary 5.16 shows a stronger claim: if v ∗ is k-homogeneous, then every optimal coalition structure CS admits an imputation x ∈ I(CS ) such that (CS , x) is in the refined core. This is not the case in general; there exist games where some optimal coalition structures cannot be stabilized under the refined arbitration function, while others can. This is illustrated by the following example. Example 5.17. Consider the following three-player game. There are four types of tasks: A task of type t1 can be completed by player 1 alone, requires all of its resources, and is worth 5. A task of type t12 requires 50% of both player 2 and player 1’s resources and is worth 10. A task of type T12 requires all of the resources of players 1 and 2 and is worth 20. Finally, a task of type t23 requires all of player 3’s resources and 50% of player 2’s resources, and is worth 9. Consider coalition structures CS = (c1 , c2 ) and CS 0 = (c01 ), where .5 .5 1 c1 = .5 , c2 = .5 , c01 = 1 . 0 0 29 0 It is easy to see that both CS and CS 0 are optimal for this game. Simply put, it is best for players 1 and 2 to work together and earn a total of 20 (by completing t12 twice or T12 once), while player 3 makes no profit. First, we claim that CS cannot be stabilized with respect to the refined arbitration function. The reason is that for an outcome (CS , x) to be in the refined core, it must be the case that player 2 gets at least 9 from each of the coalitions c1 and c2 . However, this means that player 1 gets at most 2 from working with player 2, while he can get 5 by working alone. On the other hand, let y be the imputation for CS 0 that splits the payoff from T12 evenly between players 1 and 2. Then (CS 0 , y) is in the refined core. Finally, we note that one cannot immediately employ an LP duality argument for characterizing OCF games with non-empty optimistic core. The difficulty is that under the optimistic arbitration function the number of possible deviations is infinite: a deviating set needs to specify the amount of resources it withdraws from each coalition with non-deviators. In other words, the linear program that describes the optimistic core has infinitely many constraints, so its dual has infinitely many variables. 6. Conclusions and Future Work The main contribution of our work is the concept of arbitration functions, and the analysis of the impact of arbitration on the stability of cooperative games with overlapping coalitions. This concept allows us to put the three notions of stability proposed by Chalkiadakis et al. (2010) in a broader context and to derive new notions of stability such as the sensitive core. Perhaps the most interesting of our results is the connection between OCF games with the conservative arbitration function and their discrete superadditive covers. In a sense, it shows that if the players are so pessimistic as to assume that their post-deviation payoffs will be given by the conservative arbitration function, there is little benefit to employing the OCF framework. In other words, the main value of the OCF approach lies in its ability to model non-trivial post-deviation interactions. Thus, the OCF framework is eminently suitable for settings where agents have a reason to expect that deviating from some of their collaborative projects will not cause other agents to boycott them. We believe that such settings are becoming increasingly more common in the modern interconnected society, where multitasking is the norm and collaboration is necessary to succeed. The reaction of non-deviators to deviation plays a decisive role in the analysis of many strategic interactions. For example, Ackerman and Brˆanzei (2014) use the concept of arbitration function in the analysis of Nash equilibrium and pairwise equilibrium. Also, Brˆanzei, Michalak, Rahwan, Larson, and Jennings (2013) study matchings with externalities; their model can be viewed as an application of the idea of arbitration functions to matching problems. In fact, in any strategic setting where a deviating set must still interact with the non-deviators one has to reason about the nondeviators’ behavior after a deviation occurs. While it is common to make the worst-case assumption, this is not always appropriate or realistic. Thus, a notion similar to arbitration functions may be useful beyond the setting of cooperative games. For instance, when players interact in a market, their behavior is governed by contracts (think of a wireless service provider and a consumer buying a new data plan), which clearly specify penalties for failing to fulfill one’s obligations (in the case of wireless service providers, it is typically the case that a withdrawal from an agreed-upon contract entails a monetary penalty, i.e. a worse-than-conservative reaction to deviation). Such contracts 30 can be viewed as arbitration functions. Thus, the concept of arbitration function may be useful for modeling market interactions under contracts. 6.1 Future Work In Section 5, we have provided criteria for core non-emptiness under several arbitration functions. For the conservative and refined core, we have also identified simple sufficient conditions for the core to be non-empty (supermodularity of the discrete superadditive cover and first-order homogeneity of v ∗ , respectively). It would be useful to obtain similar results for other natural notions of arbitration, such as the sensitive arbitration function and the optimistic arbitration function. Another interesting research direction is to consider the “inverse” of this problem: given an OCF game, what is the “most generous” arbitration function for which the arbitrated core of that game is not empty? More formally, given a game G, let us call an arbitration function A maxstable for G if Core(G, A) 6= ∅, and for all A0 such that A0 ≥ A we have Core(G, A0 ) = ∅. Simply put, the arbitration function A is max-stable if it provides the largest possible payoffs to the deviators without destabilizing G. It would be interesting to prove that some arbitration function is max-stable for a class of OCF games, or, more ambitiously, to completely characterize the set of max-stable arbitration functions. This line of enquiry is similar in spirit to the concepts of the least core (Maschler et al., 1979), the cost of stability (Bejan & G´omez, 2009; Bachrach, Elkind, Meir, Pasechnik, Zuckerman, Rothe, & Rosenschein, 2009), and taxation (Zick, Polukarov, & Jennings, 2013). We note that in our model deviators are allowed to withdraw resources from coalitions with nondeviators, but not to add resources to such coalitions. The implications of a more general definition, where deviators can both add and withdraw resources to their coalitions with non-deviators, are worth exploring as well. Our analysis focuses on the core of cooperative games with overlapping coalitions. This is, to an extent, a reflection of the state of the art in the study of classic cooperative games: the core and related notions (i.e., the ε-core and the least core) have been studied in greater detail than other cooperative solution concepts (barring, perhaps, the Shapley value). Further analysis of the various solution concepts for OCF games, such as the nucleolus, the kernel, and the bargaining set, and their relations to one another, would greatly improve our understanding of overlapping coalition formation. While some of these solution concepts for OCF games have been briefly discussed by Zick and Elkind (2011), their analysis is far from complete. Finally, it would be interesting to study models of dynamic coalition formation in cooperative games with overlapping coalitions. While such models have been explored for classic cooperative games (see, e.g., Arnold & Schwalbe, 2002; Lehrer & Scarsini, 2013), or for games with overlapping coalitions and fully cooperative agents (Shehory & Kraus, 1996), it is not immediately clear how to extend prior work to arbitrated OCF games. In such settings, arbitration functions can be used as a method of controlling the coalition formation process: If an outcome at some stage of the coalition formation process is stable with respect to the currently used arbitration function, more permissive reaction to deviation is allowed in future rounds; if the outcome is unstable, players can be assumed to be less tolerant towards deviators. Thus, by controlling the extent to which players are allowed to deviate, one can trade off the speed of the coalition formation process and the quality of the resulting outcome. 31 References Ackerman, M., & Brˆanzei, S. (2014). Research quality, fairness, and authorship order. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-14), pp. 1487–1488. Aharoni, R., & Fleiner, T. (2003). On a lemma of Scarf. Journal of Combinatorial Theory, Series B, 87, 72–80. Airiau, S., & Sen, S. (2009). A fair payoff distribution for myopic rational agents. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS09), pp. 1305–1306. Anshelevich, E., & Hoefer, M. (2010). Contribution games in social networks. In Proceedings of the 18th European Symposium on Algorithms (ESA-10), pp. 158–169. Arnold, T., & Schwalbe, U. (2002). Dynamic coalition formation and the core. Journal of Economic Behavior & Organization, 49(3), 363–380. Aubin, J. (1981). Cooperative fuzzy games. Mathematics of Operations Research, 6(1), 1–13. Aumann, R., & Dr`eze, J. (1974). Cooperative games with coalition structures. International Journal of Game Theory, 3, 217–237. Bachrach, Y., Elkind, E., Meir, R., Pasechnik, D., Zuckerman, M., Rothe, J., & Rosenschein, J. (2009). The cost of stability in coalitional games. In Proceedings of the 2nd International Symposium on Algorithmic Game Theory (SAGT-09), pp. 122–134. Bejan, C., & G´omez, J. C. (2009). Core extensions for non-balanced TU-games. International Journal of Game Theory, 38(1), 3–16. Bondareva, O. (1963). Some applications of linear programming methods to the theory of cooperative games. Problemy kibernetiki, 10, 119–139. Brˆanzei, S., Michalak, T., Rahwan, T., Larson, K., & Jennings, N. R. (2013). Matchings with externalities and attitudes. In Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-13), pp. 295–302. Chalkiadakis, G., Elkind, E., Markakis, E., Polukarov, M., & Jennings, N. (2010). Cooperative games with overlapping coalitions. Journal of Artificial Intelligence Research, 39, 179–216. Chalkiadakis, G., Elkind, E., & Wooldridge, M. (2011). Computational Aspects of Cooperative Game Theory. Morgan and Claypool. Dang, V. D., Dash, R. K., Rogers, A., & Jennings, N. R. (2006). Overlapping coalition formation for efficient data fusion in multi-sensor networks. In Proceedings of the 21st AAAI Conference on AI (AAAI-06), pp. 635–640. Deng, X., Ibaraki, T., & Nagamochi, H. (1999). Algorithmic aspects of the core of combinatorial optimization games. Mathematics of Operations Research, 24(3), 751–766. Gillies, D. (1953). Some Theorems on n-Person Games. Ph.D. thesis, Princeton University. Jackson, M. O. (2003). A survey of models of network formation—stability and efficiency. In Demange, G., & Wooders, M. (Eds.), Group Formation in Economics: Networks, Clubs and Coalitions, chap. 1. Cambridge University Press. 32 Lehrer, E., & Scarsini, M. (2013). On the core of dynamic cooperative games. Dynamic Games and Applications, 3(3), 359–373. Lin, C., & Hu, S. (2007). Multi-task overlapping coalition parallel formation algorithm. In Proceedings of the 6th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-07), p. 211. Markakis, E., & Saberi, A. (2005). On the core of the multicommodity flow game. Decision Support Systems, 39(1), 3–10. Maschler, M., Peleg, B., & Shapley, L. S. (1979). Geometric properties of the kernel, nucleolus, and related solution concepts. Mathematics of Operations Research, 4(4), 303–338. Peleg, B., & Sudh¨olter, P. (2007). Introduction to the Theory of Cooperative Games (Second edition)., Vol. 34 of Theory and Decision Library. Series C: Game Theory, Mathematical Programming and Operations Research. Springer, Berlin. Rahwan, T. (2007). Algorithms for Coalition Formation in Multi-Agent Systems. Ph.D. thesis, University of Southampton. Rahwan, T., & Jennings, N. (2008). An improved dynamic programming algorithm for coalition structure generation. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-08), pp. 1417–1420. Shapley, L. S. (1967). On balanced sets and cores. Naval Research Logistics Quarterly, 14(4), 453–460. Shapley, L. S. (1971). Cores of convex games. International Journal of Game Theory, 1, 11–26. Shehory, O., & Kraus, S. (1996). Formation of overlapping coalitions for precedence-ordered taskexecution among autonomous agents. In Proceedings of the 2nd International Conference on Multi-Agent Systems (ICMAS-96), pp. 330–337. Sims, M., Corkill, D., & Lesser, V. (2008). Automated organization design for multi-agent systems. Autonomous Agents and Multi-Agent Systems, 16, 151–185. Zhang, G., Jiang, J., Su, Z., Qi, M., & Fang, H. (2010). Searching for overlapping coalitions in multiple virtual organizations. Information Sciences, 180, 3140–3156. Zick, Y., Chalkiadakis, G., & Elkind, E. (2012). Overlapping coalition formation games: Charting the tractability frontier. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-12), pp. 787–794. Zick, Y., & Elkind, E. (2011). Arbitrators in overlapping coalition formation games. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-11), pp. 55–62. Zick, Y., Polukarov, M., & Jennings, N. R. (2013). Taxation and stability in cooperative games. In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-13), pp. 523–530. 33 Appendix A. A Note on the Characterization of the Conservative Core The purpose of this appendix is to fill a gap in the proof of the characterization of the conservative core that was given by Chalkiadakis et al. (2010) (see Theorem 5.2). Our argument also has implications for the characterization of the sensitive core (Section 5.2). The proof of Theorem 5.2 proceeds as follows. Given an optimal coalition structure CS = (c1 , . . . , cm ), consider the following linear program: Pm P i min j=1 i∈supp(cj ) xj P i s.t. ∀j ∈ {1, . . . , m} (16) i∈supp(cj ) xj ≥ v(cj ) P Pm i ∗ S i∈S j=1 xj ≥ v (e ) ∀S ⊆ N The dual of LP (16) is max s.t. Pm j=1 rj v(cj ) rj + + P P S⊆N S:i∈S δS δS v ∗ (eS ) =1 ∀j, ∀i ∈ supp(cj ) rj ≥ 0 ∀j ∈ {1, . . . , m} δS ≥ 0 ∀S ⊆ N (17) Chalkiadakis et al. (2010) P argue that iLP (16) describes the constraints of the conservative core, with the exception that i∈supp(cj ) xj is required to be at least v(cj ) rather than equal to v(cj ). ¯ ¯ ) is in the conservative core if and only Thus, solution to LP (16), then (CS , x Pmif x Pis an optimal i ∗ N if j=1 i∈supp(cj ) xj = v(CS ) = v (e ). LP duality then implies that the value of LP (17) is at most v ∗ (eN ) if and only if CS can be stabilized with respect to the conservative arbitration function. i The problem with this argument is that P xj to be nonPLP (16) does not require the variables negative, which allows us to have rj + S:i∈S δS = 1 rather than rj + S:i∈S δS ≤ 1 in the dual LP. However, if we allow the variables xij to take negative values, we are effectively breaking the payoff distribution requirement for imputations. We mention that, in contrast, in the Bondareva–Shapley theorem it is acceptable not to impose non-negativity constraints explicitly, since stability constraints imply pi ≥ u({i}) ≥ 0. However, for the conservative core we only get P i ∗ {i} i j:i∈supp(cj ) xj ≥ v (e ) for all i ∈ N , which does not imply that individual xj are non-negative. In other words, Chalkiadakis et al. (2010) show that every c-balanced OCF game and every optimal coalition structure CS = (c1 , . . . , cm ) for this game admit a pre-imputation x such that (CS , x) is in the conservative core (recall that x = (x1 , . . . , xm ) is a pre-imputation Pfor CS = (c1 , . . . , cm ) if for each j = 1, . . . , m it holds that xj is a vector in Rn such that ni=1 xij = v(cj ) and if cij = 0 then xij = 0, i.e., a preimputation satisfies the same conditions as an imputation, except for non-negativity). We will now argue that one can transform this pre-imputation into an imputation. Theorem A.1. If there exists a preimputation x that satisfies the constraints of LP (16), then there ¯ ∈ I(CS ) such that pi (CS , x) = pi (CS , x ¯ ) for all i ∈ N . exists an imputation x Proof. Let Ipre (CS ) denote the set of all pre-imputations for a coalition structure CS . Given a point x ∈ Ipre (CS ), we define a graph Γ(x) = hV, Ei as follows: the vertices of Γ(x) are V = {(j, i) | cj ∈ CS , i ∈ supp(cj )} , 34 and the set of edges is E = E1 ∪ E2 , where E1 = (i, j), (i, j 0 ) | i ∈ supp(cj ) ∩ supp(cj 0 ), j 6= j 0 , and E2 = (i, j), (i0 , j) | i, i0 ∈ supp(cj ), xij > 0 . That is, E1 consists of all pairs (i, j), (i, j 0 ) such that i is in both supp(cj ) and supp(cj 0 ), and E2 consists of all pairs (i, j), (i0 , j) such that i, i0 ∈ supp(cj ) for some cj ∈ CS and xij > 0. An edge in E2 means that i can transfer a small amount of payoff to i0 in the coalition cj , and still maintain a positive payoff from cj . Further, given a point x ∈ Ipre (CS ), set TN (x) = m X n X min{0, xij }. j=1 i=1 Fix an arbitrary point x ∈ Ipre (CS ), and consider the set Ipre (CS , x) = {y ∈ Ipre (CS ) | pi (CS , y) = pi (CS , x) for all i ∈ N and TN (y) ≥ TN (x)}. ¯ ∈ Ipre (CS , x) that The set Ipre (CS , x) is compact and TN is continuous, so there exists a point x maximizes TN over Ipre (CS , x). ∗ Suppose that there exists a coalition cj ∗ and an agent i∗ ∈ supp(cj ∗ ) such that x ¯ij ∗ < 0. Note that in Γ(¯ x) there must be an edge in E1 that leaves (i∗ , j ∗ ): otherwise, i∗ is only being paid by cj ∗ , in which case we would have ¯) = pi∗ (CS , x m X ∗ ∗ ∗ x ¯ij = x ¯ij ∗ < 0 ≤ v ∗ (e{i } ), j=1 violating the respective constraint of LP (16). Let C be a minimum-length directed cycle in Γ(¯ x) that contains an edge ((i∗ , j ∗ ), (i∗ , j0 )) for some cj0 ∈ CS as well as some edges from E2 . Note that C contains no path of the form (i, j1 ) → (i, j2 ) → (i, j3 ); this is because the edge ((i, j1 ), (i, j3 )) is in E1 , a contradiction to C being of minimum length. Moreover, C cannot contain a path of the form (i1 , j) → (i2 , j) → (i3 , j); indeed, if ((i1 , j), (i2 , j)) is in E2 , then agent i1 receives a positive payoff from cj , and hence the edge ((i1 , j), (i3 , j)) is also in E2 , a contradiction with our choice of C. We conclude that a minimum-length cycle that passes through (i∗ , j ∗ ) and intersects E2 must be of the form (i∗ , j ∗ ) → (i∗ , j0 ) → (i1 , j0 ) → (i1 , j1 ) → (i2 , j1 ) → · · · → (it , j ∗ ) → (i∗ , j ∗ ). This means that i∗ receives a positive payoff from cj0 , i1 receives a positive payoff from cj1 , i2 receives a positive payoff from cj2 and, in general, i` receives a positive payoff from the coalition cj` for all 1 ≤ ` ≤ t − 1. Finally, the player it receives a positive payoff from cj ∗ . 35 Now, pick an ε satsifying ∗ i ,x ¯ijt∗ }, ¯jt−1 0 < ε < min{¯ xij0 , x ¯ij11 , . . . , x t−1 ¯ by transferring a payoff of ε from and let y = (y1 , . . . , ym ) be the pre-imputation obtained from x 1, . . . , t − 1, and from it to i∗ in cj ∗ . We have i∗ to i1 in cj0 , from i` to i`+1 in cj` for ` = P P ¯ ) for all i ∈ N , and i∈supp(cj ) yji = pi (CS , y) = pi (CS , x ¯ij for all cj ∈ CS . i∈supp(cj ) x Therefore, y is an optimal solution to LP (16). However, TN (y) > TN (¯ x), a contradiction to our ¯ . We conclude that Γ(¯ choice of x x) contains no cycles that pass through (i∗ , j ∗ ) and intersect E2 . Let us define Np = {i ∈ N | there is a path from (i∗ , j ∗ ) to (i, j) for some cj }. Then for every i ∈ Np and every i0 ∈ N \Np , our graph contains no edge of the form ((i, j), (i0 , j)). Hence, if i, i0 ∈ supp(cj ) then x ¯ij ≤ 0. That is, in every coalition that involves both agents in Np and agents in N \ Np the payoffs are split so that the share of each agent in Np is non-positive. ¯ ) ≤ pNp (CS |Np , x ¯ ). Hence, pNp (CS , x Moreover, we will now argue that for cj ∗ the total share of the agents in Np is, in fact, negative, ∗ ¯ ) < pNp (CS |Np , x ¯ ). Indeed, recall that x and therefore pNp (CS , x ¯ij ∗ < 0. Suppose that x ¯ij ∗ > 0 for ∗ ∗ ∗ some i ∈ Np ; note that this implies that the edge e = ((i, j ), (i , j )) is in E2 . Consider a coalition cj such that the graph contains a path P from (i∗ , j ∗ ) to (i, j). If j = j ∗ , by adding e to P we obtain a cycle that passes through (i∗ , j ∗ ) and intersects E2 . Otherwise, the edge e0 = ((i, j), (i, j ∗ )) is in E1 , and adding e0 and e to P results in a cycle that passes through (i∗ , j ∗ ) and intersects E2 . In both cases, we get a contradiction, as we have argued that no such cycle exists. Thus, all players in Np get a non-positive payoff from cj ∗ , and i∗ gets a strictly negative payoff from this coalition. ¯ ) < pNp (CS |Np , x ¯ ). On the other hand, we have Consequently, we have pNp (CS , x ¯ ) = v(CS |Np ) ≤ v ∗ (eNp ); pNp (CS |Np , x ¯ ) < v ∗ (eNp ), which is a contradiction to combining the inequalities we obtain that pNp (CS , x ¯ ) satisfying the inequalities in LP (16). (CS , x ¯ is an imputation of CS such that pi (CS , x) = pi (CS , x ¯ ) for all i ∈ N and We conclude that x i xj ≥ 0 for all cj ∈ CS and all i ∈ supp(cj ), which concludes the proof. Example A.2. Suppose the players form the coalition structure CS = (c1 , c2 , c3 ) given by 0.6 0.3 0.1 c3 = 0.1 , c1 = 0.3 , c2 = 0.6 , 0.3 0 and use the imputation x = (x1 , x2 , x3 ), where 0 2 x1 = 2 , x2 = 2 , 3 0 0.7 x3 = 3 0 −1 . The resulting graph is shown in Figure 1, and the shortest cycle starting from (3, 3) including edges in E2 is (3, 3) → (3, 1) → (1, 1) → (1, 3) → (3, 3). That is, the negative payoff to player 3 from c3 can be reduced if player 3 transfers a small amount of payoff to player 1 under c1 , and player 1 transfers the same amount of payoff to player 3 under c3 ; for instance, moving 1 unit of payoff in this manner would result in a valid imputation. 36 1,1 1,2 1,3 2,1 2,2 2,3 3,1 3,3 Figure 1: The graph Γ(x) formed for the coalition structure and the imputation described in Example A.2. Theorem A.1 implies that even if we assume that xij are unconstrained, if there is a solution to LP (16) with a value of v ∗ (eN ), then there is a solution with no negative payoffs from coalitions and the same value, i.e., an optimal solution that is in I(CS ). In particular, this means that there is no loss of generality in assuming that the variables xij in LP (16) are unconstrained, and therefore Theorem 5.2 holds. 37

© Copyright 2018 ExploreDoc