--- title: "Computational Aspects of the Preference Cores of Supermodular Two-Scenario Cooperative Games" authors: - "Daisuke Hatano" - "Yuichi Yoshida" doi: "10.24963/ijcai.2018/43" url: "https://ijcai.org/proceedings/2018/43" pdf: "https://ijcai.org/proceedings/2018/0043.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "310-316" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Algorithmic Game Theory" - "Agent-based and Multi-agent Systems: Cooperative Games" --- # Computational Aspects of the Preference Cores of Supermodular Two-Scenario Cooperative Games Daisuke Hatano, Yuichi Yoshida *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 310-316. DOI: [10.24963/ijcai.2018/43](https://doi.org/10.24963/ijcai.2018/43) ## Abstract In a cooperative game, the utility of a coalition of players is given by the characteristic function, and the goal is to find a stable value division of the total utility to the players. In real-world applications, however, multiple scenarios could exist, each of which determines a characteristic function, and which scenario is more important is unknown. To handle such situations, the notion of multi-scenario cooperative games and several solution concepts have been proposed. However, computing the value divisions in those solution concepts is intractable in general. To resolve this issue, we focus on supermodular two-scenario cooperative games in which the number of scenarios is two and the characteristic functions are supermodular and study the computational aspects of a major solution concept called the preference core. First, we show that we can compute the value division in the preference core of a supermodular two-scenario game in polynomial time. Then, we reveal the relations among preference cores with different parameters. Finally, we provide more efficient algorithms for deciding the non-emptiness of the preference core for several specific supermodular two-scenario cooperative games such as the airport game, multicast tree game, and a special case of the generalized induced subgraph game. ## Full text ## 1 Introduction Cooperative games are useful frameworks for analyzing cooperation among individuals or players. A popular such model is a characteristic function game in which the utility of a coalition among players is specified by a function called a characteristic function and the division of total utility by the grand coalition among the players is called a value division. Given a set of players and a characteristic function, the typical goal of such games is to find the value division in the core [Gillies, 1959]; in other words, no individual or group can receive larger utility by deviating from the grand coalition. Unfortunately, it is NP-hard to decide the non-emptiness of the core of a cooperative game. However, for supermodular (or convex) cooperative games in which the characteristic functions are supermodular, the cores are known to always be non-empty [Shapley, 1971]. Moreover, the value division called the Shapley value is always in the core, and in some classes of supermodular games we can compute this in polynomial time [Shapley, 1967]. There has been research interest in extending the conventional notion of a cooperative game to more general ones that can be applied to real-world problems that involve two or more characteristic functions. Therefore, in this study, we focus on multiple scenario cooperative games [Hinojosa et al., 2005; Borrero et al., 2016]. Such games are suitable when the costs, or the negative utilities, of coalitions are uncertain and the players have to pay the cost in advance before this uncertainty dissipates. For example, suppose that some cities jointly apply for a service on their roads such as a road cleaning, waste collection, and patrolling. Although the service provider is determined by a competitive bidding process and the actual cost of each city is influenced by the route chosen by the service provider, the cities must pay their fees in advance. This situation can be represented by introducing several characteristic functions, each of which corresponds to a potential route (scenario). As the notion of a core is tailored to conventional cooperative games, some generalizations of the core for multiscenario cooperative games have been proposed, including the preference core, dominance core, and generalized least core [Hinojosa et al., 2005]. Unfortunately, however, computing a value division in these cores requires exponential time in the number of players in general. ## 1.1 Our Contributions To resolve the above-mentioned issue, in this work, we focus on a supermodular two-scenario cooperative game in which the number of scenarios is two and each characteristic function is supermodular to examine the computational aspects of the notion of the preference (ϵ1, ϵ2)-core [Hinojosa et al., 2005]. Supermodular two-scenario cooperative games have several important applications. For example, suppose that a company has a research department and a development department, and the manager of the company is planning to reward employees based on the proceeds they earn. The tasks for earning proceeds can be categorized into research and development ones, and employees are involved in several tasks from both categories. Then, the manager wants to distribute the proceeds based on the amount of research and development to which every employee or group of employees committed. This problem can be represented by extending a supermodular cooperative game called the induced subgraph game [Deng and Papadimitriou, 1994] to the two-scenario case, where one scenario represents the research tasks and the other represents the development tasks. The preference (ϵ1, ϵ2)-core is parameterized by two nonnegative real values ϵ1 and ϵ2, which represent slackness in the two scenarios. Intuitively speaking, the value division is in the preference (ϵ1, ϵ2)-core if it violates the condition of the core up to the additive error of ϵ1 and ϵ2 for the first and second scenarios, respectively. Our contributions can be summarized as follows: First, we show that we can compute a value division in the preference (ϵ1, ϵ2)-core in polynomial time by exploiting the submodular intersection problem. Then, we show that the preference (ϵ1, ϵ2)-core is non-empty if and only if ϵ1+ϵ2 is no less than some threshold, which we call the preference core value of the game. Finally, we provide efficient algorithms for computing the preference core values for several specific supermodular two-scenario games such as the induced subgraph game generalized to hypergraphs, airport game, and multicast tree game. ## 2 Related work ## 2.1 Supermodular Games Supermodular games are a well-studied class of cooperative games. Examples of supermodular games include the airport game [Littlechild and Owen, 1973], public good game [Oishi and Nakayama, 2009], bidder collusion game [Graham et al., 1990], multicast tree game [Feigenbaum et al., 2001], and bankruptcy game [O'Neill, 1982], and a special case of the induced subgraph game [Deng and Papadimitriou, 1994]. Each of these games can be extended to the two-scenario setting, and our characterization of the least core value can be applied. Although computing the value division in the core of a cooperative game is intractable in general, it becomes polynomial-time tractable if the characteristic function of the game admits supermodularity. Recently, [Hatano and Yoshida, 2017] extended this result to strong and weak least cores, which were originally introduced to study games with empty cores [Shapley and Shubik, 1966]. ## 2.2 Generalizations of Cooperative Games To handle real-world applications with multiple objectives, conventional cooperative games have been extended in several directions. Multi-scenario cooperative games, on which we focus in this study, are one such extension. This notion is introduced in [Nishizaki and Sakawa, 2001], who studied extensions to the least core and nucleolus for multi-scenario cooperative games. In [Hinojosa et al., 2005], the notions of the preference core, dominance core, generalized least core, and generalized nucleolus for multi-scenario cooperative games were introduced. The preference core and dominance core are value divisions for which no player deviates from the grand coalition in any scenario and the coalition in at least one scenario, respectively. We note that the preference core coincides with the preference (ϵ1, ϵ2)-core with ϵ1 = ϵ2 = 0. Those notions are reduced to the core in conventional cooperative games. The generalized least core is a set of value divisions in which a value division provides a minimum loss of vectors corresponding to scenarios and any two value divisions are non-dominated with respect to the minimum loss. Recently, core solutions have been presented for multi-scenario cooperative games with partial information that represent the relative importance or probability of occurrences of scenarios [Borrero et al., 2016]. In a multi-attribute coalitional game [Ieong and Shoham, 2006], the value of the characteristic function of a coalition is determined by an attribute matrix A ∈ Rm×n , where n is the number of players and m is the number of attributes and aggregation functions. The computational complexities of the Shapley value and core have also been studied. The difference frommulti-scenario cooperative games is that each player obtains a single value. A multi-criteria cooperative game [J¨ornsten et al., 1997] has several criteria (i.e., several characteristic functions). In this game, we compute a value division for each criterion and regard it as the value division in a multi-criteria cooperative game. Some solution concepts, such as the generalized core [J¨ornsten et al., 1997], dominance core, and preference core [Fern´andez et al., 2004], have been defined for multi-criteria cooperative games. However, in multi-scenario cooperative games, we only provide a single value division. ## 3 Preliminaries For an integer k, we denote the set {1, 2, . . . , k} by [k]. The set of non-negative real values is denoted by R+. We use bold symbols such as x to denote the vectors. Let N be a finite set. For a vector x ∈ RN or a function x : N → R and a set S ⊆ N, we denote by x(S) the value ∑ v∈S x(v). For a set S ⊆ N, we denote by χS ∈ RN the characteristic vector of S, that is, χS(v) = 1 for v ∈ S and χS(v) = 0 for v ∈ N \ S. ## 3.1 Submodular Functions A function f : 2N → R is called submodular (resp., supermodular) if for all S, T ⊆ N. We say that a function f : 2N → R is normalized if f(∅) = 0. The submodular polyhedron and base polyhedron of a submodular function f : 2N → R are defined as respectively. It is known that f(S) = max{〈w,χS〉 | w ∈ B(f)}, where 〈·, ·〉 denotes inner product. (See, e.g., [Fujishige, 2005].) In the submodular intersection problem, we are given two submodular functions f1, f2 : 2N → R, and the goal is to maximize x(N) subject to x ∈ P(f1) ∩ P(f2). For this problem, the following min-max theorem is well known. Theorem 1 ([Edmonds, 2003]). Let f1, f2 : 2N → R be normalized submodular functions. Then, we have Moreover, we can compute an optimal solution to (1) (and hence that of (2)) in polynomial time in |N|. ## 3.2 Cooperative Games We now briefly describe the framework of cooperative games. For more details, readers are referred to [Chalkiadakis et al., 2011] and the references therein. A cooperative game G is a pair (N, ν), where N is a set of players and ν : 2N → R+ is a function called the characteristic function of G. We can regard ν(S) as the utility when the players in S form a coalition. We always assume that ν(∅) = 0. We say that a vector x ∈ RN is a value division if x(N) = ν(N); in other words, the value division is a distribution of the total utility to the players. Suppose that a value division x ∈ RN satisfies x(S) < ν(S) for some S ⊆ N. In such a case, the players in S will form a coalition and leave N. We say that a value division is in the core if such an S does not exist. More formally, a value division x ∈ RN is in the core if x(S) ≥ ν(S) for every S ⊆ N. In general, the core of a cooperative game may be empty. To handle such a case, the notion of ϵ-core has been studied, where ϵ ∈ R+ is a parameter. We say that the value division is in the ϵ-core if x(S) ≥ ν(S) - ϵ for every S ⊆ N. Note that the 0-core coincides with the standard core. The least core value of a game G, denoted by lcv(G), is the minimum ϵ ∈ R+ for which the ϵ-core is non-empty. We note that the least core value of a cooperative game can be computed by solving the following linear program (LP): We say that a cooperative game (N, ν) is supermodular if ν is supermodular. Supermodular games are sometimes called convex games in the literature. The core of a supermodular cooperative game is non-empty; in particular, a value division called the Shapley value is always in the core [Shapley, 1967]. Hence, the optimal value of (3) for a supermodular cooperative game is always 0. ## 3.3 Two-Scenario Cooperative Games An instance of a two-scenario cooperative game G is a tuple (N, ν1, ν2, T ), where N is a set of players, ν1, ν2 : 2N → R+ are characteristic functions, and T ∈ R+ is the total utility to be distributed. We say that a two-scenario cooperative game is supermodular if both ν1 and ν2 are supermodular. For twoscenario cooperative games, we say that a vector x ∈ RN is a value division if x(N) = T. We always assume νi(N) ≤ T (i ∈ {1, 2}) so that there is a valid value division for the game (N, νi) for each i ∈ {1, 2}. Let G = (N, ν1, ν2, T) be a supermodular two-scenario game. Although both games (N, ν1) and (N, ν2) have nonempty cores, they do not intersect in general. To find a value division satisfiable in both scenarios, we define a variant of the least core for two-scenario games. Definition 2. For ϵ1, ϵ2 ∈ R+, we say that a value division x ∈ RN is in the preference (ϵ1, ϵ2)-core (or, simply (ϵ1, ϵ2)- core) of G if x(S) ≥ ν1(S) - ϵ1 and x(S) ≥ ν2(S) - ϵ2 for every S ⊆ N. ## 4 Preference Cores of Supermodular Two-Scenario Games In this section, we study the computational aspects of the (ϵ1, ϵ2)-cores of supermodular two-scenario games. First, we provide a polynomial-time algorithm for finding a value division in the (ϵ1, ϵ2)-core for fixed ϵ1 and ϵ2 (if exists). Then, we see that the non-emptiness is determined solely by the sum ϵ1 + ϵ2, rather than the pair (ϵ1, ϵ2). Finally, we show the relations among (ϵ1, ϵ2)-cores with ϵ1 + ϵ2 being fixed. ## 4.1 Non-Emptiness of a Preference Core Fix a supermodular two-scenario game G = (N, ν1, ν2, T) and parameters ϵ1, ϵ2 ∈ R+. Here, we characterize the nonemptiness of the (ϵ1, ϵ2)-core of G. From the definition, the non-emptiness of the (ϵ1, ϵ2)-core can be checked by solving the following feasibility problem: To rephrase the problem (4), we define fi : 2N → R as follows: We can easily confirm that fi is normalized submodular. Then, by replacing x with -x and using fi, the problem (4) can be rephrased as the following submodular intersection First, we start with the following simple observation: Theorem 3. We can find a value division in the (ϵ1, ϵ2)-core of G in polynomial time in |N| if it is non-empty. The following theorem states that the feasibility of the problem (6) is determined by the sum ϵ1 + ϵ2 rather than the pair (ϵ1, ϵ2). Theorem 4. The (ϵ1, ϵ2)-core of G is non-empty if and only if ϵ1 + ϵ2 ≥ ϵ∗ , where ϵ∗ is Moreover, we can compute ϵ∗ in polynomial time in |N|. Proof. From Theorem 1, the (ϵ1, ϵ2)-core of G is non-empty if and only if for every ∅ ⊆ S ⊆ N. When S = ∅ or S = N, (8) trivially holds from the assumption νi(N) ≤ T (i ∈ {1, 2}). For ∅ ⊊ S ⊊ V , we have f1(S) + f2(N \ S) = -ν1(S) - ν2(N \ S) + ϵ1 + ϵ2. Then, the (ϵ1, ϵ2)-core is non-empty if and only if and hence the first claim holds. We can compute ϵ∗ by solving (7), which can be done in polynomial in |N| by applying Theorem 1 on normalized submodular functions -ν1 and -ν2. Theorem 4 suggests to define the preference core value of a game G as max{ϵ∗ , 0} in Theorem 4, and which we denote by pcv(G). Here, we took the maximum with 0 to emphasize the constraint ϵ1, ϵ2 ≥ 0. ## 4.2 Relations among the Preference Cores In this section, we reveal interesting relations among the (ϵ1, ϵ2)-cores with ϵ1+ϵ2 = pcv(G) for a supermodular twoscenario game G = (N, ν1, ν2, T ). Theorem 5. Let x1 ∈ RN and x2 ∈ RN be solutions to (6) with (ϵ1, ϵ2) = (pcv(G), 0) and (ϵ1, ϵ2) = (0, pcv(G)), respectively. Then, for any α ∈ [0, 1], x = αx1 +(1-α)x2 is a solution to (6) with (ϵ1, ϵ2) = (α · pcv(G), (1-α) · pcv(G)). Proof. First, Next, for any ∅ ⊊ S ⊆ N, we have Similarly, for any ∅ ⊊ S ⊆ N, we have Hence, the theorem holds. Theorem 5 implies that, once we obtain value divisions in the (pcv(G), 0)-core and the (0, pcv(G))-core, we can construct a value division in the (ϵ1, ϵ2)-core with ϵ1 + ϵ2 = pcv(G) by linear interpolation. ## 5 Induced Subgraph Games In this section, we analyze the preference (ϵ1, ϵ2)-cores of two-scenario induced subgraph games [Deng and Papadimitriou, 1994] generalized to hypergraphs with nonnegative weights of hyperedges(see, e.g., [Hatano and Yoshida, 2017] for this generalization). This generalization can be viewed as cooperative games represented by a (basic) MC-net [Ieong and Shoham, 2005] under the condition that the utility of every rule is nonnegative. ## 5.1 Definition First, we define the induced subgraph game. Let G = (N,E,w) be a hypergraph, where N is a set of vertices, E is a set of hyperedges, and w : E → R+ is a non-negative weight function on the edges. We often regard a hyperedge e ∈ E as a subset of N. The induced subgraph game associated with G is a cooperative game G = (N, ν), where ν : 2V → R+ is the total weight of the hyperedges e ∈ E with e ⊆ S. Note that ν is supermodular because of the nonnegativity of w. A cut weight of S in G is the total weight of hyperedges which intersect S and N \ S. ## 5.2 Characterization of the Preference Core Value Let G1 = (V,E1,w1) and G2 = (V,E2,w2) be two hypergraphs on the same vertex set N. Then, we consider a supermodular two-scenario game G = (N, ν1, ν2, T), where ν1 and ν2 are the supermodular functions associated with G1 and G2, respectively, and T ∈ R+ is the total utility to be distributed. Here, we characterize the preference core value of G. The preference core value of G is obtained by solving (7). We now show that this problem can be further reduced to a minimum cut problem on a hypergraph. To this end, we construct a hypergraph G′ = (N ′ ,E′ ,w′ ) from G1 and G2. Here, N ′ = N ∪ {s, t}, where s and t are new vertices. We construct E′ by adding a hyperedge e ∪ {s} for each hyperedge e ∈ E1 and adding a hyperedge e ∪ {t} for each hyperedge e ∈ E2. Their weights are set to be the same as their original hyperedges. Figure 1 shows an example. For ∅ ⊆ S ⊆ N, let c(S) denote the cut weight of S ∪ {s} in G′ . Then, we can characterize the preference core value by using the minimum cut in G′ . Theorem 6. We have Proof. We have Hence, from Theorem 4, the preference core value is equal to The minimum s-t cut of a hypergraph can be computed in polynomial time by using the algorithm proposed by [Pistorius and Minoux, 2003]. Hence, we can compute the preference core value of G in polynomial time. Figure 1: Construction of G′ from two graphs G1 and G2. Here, each square in G′ denotes a hyperedge and is connected to the vertices belonging to the hyperedge. ![Image](https://ijcai.org/proceedings/2018/fulltext/43/image_000000_7b36272d3a475a8e50405c2f3f964f0bda97dc656d25194d123f120089a19e37.png) From Theorem 6, for fixed ν1(N), ν2(N), and T , the preference core value becomes large when c(S) is small for some ∅ ⊆ S ⊆ N. This means that most hyperedges in G1 are within S and most hyperedges in G2 are within N \ S. To avoid deviation, we should give a large utility to players in S and in N \ S in the first and second games, respectively. As these demands are conflicting, the preference core value becomes large. ## 6 Airport Games In this section, we analyze the preference (ϵ1, ϵ2)-cores of two-scenario airport games [Littlechild and Owen, 1973]. ## 6.1 Definition Let I = (c1 , . . . , cn ) be a tuple, where c1 , . . . , cn ∈ R+ satisfy c1 ≤ c2 ≤ · · · ≤ cn . Then, the airport game associated with I is the cooperative game G = (N, ν), where N = [n] and ν(S) = -maxi∈S ci for every S ⊆ N. Here, we regard ν(∅) = 0. ## 6.2 Characterization of the Preference Core Value Fix a tuple I1 = (c11 , . . . , cn1 ) with c11 ≤ · · · ≤ cn1 and a tuple I2 = (cπ1 2 , . . . , cπn 2 ) with cπ1 2 ≤ · · · ≤ cπn 2 for some ordering π1, . . . , πn of [n], that is, π1, . . . , πn is an element of the permutation of [n]. Then, we consider the twoscenario airport game G = (N, ν1, ν2, T), where N = [n], ν1 : S ↦→ -maxi∈S ci1 and ν2 : S ↦→ -maxi∈S cπi 2 are the supermodular functions associated with I1 and I2, respectively, and T ∈ R is the total utility to be distributed. Note that T is not necessarily but is supposed to be negative in this problem. We first analyze the preference core value of G. Theorem 7. We have Proof. From Theorem 4, we have From the assumption that ν1(N) ≤ T and ν2(N) ≤ T, the inner maximum is which implies the claim. Although (9) is hard to interpret, it becomes trivial when πn = n: Corollary 8. When πn = n, we have Proof. The first term in the outer maximum of (9) is where we used the assumption that ν2(N) ≤ T in the last inequality. Hence, the claim holds. When πn = n, it is easy to compute a value division in the (0, 0)-core: Theorem 9. When πn = n, the value division x ∈ RN below belongs to the (0, 0)-core of G. Proof. First, we have x(N) = T. Now, we want to check x(S) ≥ ν1(S) and x(S) ≥ ν2(S) for every S ⊆ N. Let S ⊆ N be a set with n ̸∈ S. Then, we have x(S) = 0 and hence we have x(S) ≥ ν1(S) and x(S) ≥ ν2(S). Let S ⊆ N be a set with n ∈ S. Then, we have x(S) = T and hence we have x(S) ≥ ν1(N) = ν1(S) and x(S) ≥ ν2(N) = ν2(S). ## 7 Multicast Tree Games In this section, we analyze the preference (ϵ1, ϵ2)-cores of two-scenario multicast tree games [Feigenbaum et al., 2001]. ## 7.1 Definition First, we define multicast tree games. A multicast tree game is parameterized by a tuple (N,E,w, r, p). Here, (N,E,w) is a rooted (directed) tree, where N is a vertex set, E is an arc set, w : E → R+ is a weight function on the arcs, r ∈ N is the root vertex, and p : N → R+ is a utility function on the vertices. For a vertex v ∈ N, we define P(v) as the set of arcs on the unique directed path from r to v. For a vertex set S ⊆ N, we define P(S) = ⋃v∈S P(v). The multicast tree game associated with (N, E, w, r, p) is the cooperative game G = (N, ν), where ν : 2V → R+ is defined as That is, ν(S) is the total utility obtained by the vertices in S minus the total weight of the arcs needed for r to reach the vertices in S. It is easy to confirm that ν is supermodular. ## 7.2 Characterization of the Preference Core Value Let (N, E1, w1, r1, p1) and (N, E2, w2, r2, p2) be the two parameters for multicast tree games, and let ν1 : 2V → R and ν2 : 2V → R be the corresponding supermodular functions. Then, we let G = (N, ν1, ν2, T) be a two-scenario multicast tree game, where T is the total utility to be distributed. The preference core value of G is obtained by solving (7). This problem can be reduced to a min cut problem on a directed graph. To this end, we define an auxiliary directed graph G′ = (N ′ , E′ , w′ ) as follows. First, where s and t are newly introduced vertices. For each v ∈ N, we add the arcs (s, v) and (v, t) of weights p1(v) and p2(v), respectively, to G′ . For each v ∈ N \ {r1}, we add the arc (v, v1) of infinite weight, and for each v ∈ N \ {r2}, we add the arc (v2, v) of inifinite weight. For each arc e = (u, v) with u ̸= r1 in G1, where u is the parent of v, we add an arc (v1, u1) of infinite weight and an arc (v1, t) of weight w(e) to G′ . For each arc (u, v) with u ̸= r2 in G2, where u is the parent of v, we add an arc (u2, v2) of infinite weight to G′ and an arc (s, v2) of weight w2(e) to G′ . Figure 2 shows an example of the obtained directed graph. For a vertex set S ⊆ N, let c(S) be the minimum weight of a directed s-t cut for which S belongs to the s-side and N \ S belongs to the t-side, and let C(S) ⊆ N ′ be the vertex set that attains c(S). For i ∈ {1, 2} and a vertex set S ⊆ N, let Ai(S) be the ascendants of the vertices in S in Gi. Then, we have the following. Lemma 10. Let S ⊆ N be a set of vertices. Then, we have Proof. Because of the arcs of infinite weight, we are forced to have {v1 | v ∈ A1(S) \ {r1}} ⊆ C(S) and exclude {v2 | v ∈ A2(N \ S) \ {r2}} ⊆ N ′ \ C(S) from S. The other direction is easy to see. Indeed, adding one or more vertices of the form v1 for v ̸∈ A1(S) \ {r1} to C(S) only increases the cut weight. Moreover, adding one or more vertices of the form v2 for v ̸∈ A2(N \S)\{r2} to N ′ \C(S) only increases the cut weight. Figure 2: Construction of G′ from the two graphs G1 and G2. The bold red arrows denote the arcs of infinite weight. ![Image](https://ijcai.org/proceedings/2018/fulltext/43/image_000001_4e199d7ea3da845719cfe5904fb553f4acdc3a700687cd6d704bbbf205f6ed52.png) Theorem 11. We have Proof. From Lemma 10, we have Hence, from Theorem 4, the preference core value is equal to From Theorem 11, for fixed ν1(N), ν2(N), and T, the preference core value becomes large when c(S) is small for some ∅ ⊆ S ⊆ N. This means that there are only a few ascendants of S in G1 and a few ascendants of N \ S in G2, and the total utilities of S in G1 and N \ S in G2 are large. To avoid deviation, we should give a large utility to players in S and in N \ S in the first and second games, respectively. As these demands are conflicting, the preference core value becomes large. ## 8 Conclusions The contributions of this study can be summarized as follows. First, we showed that we can compute a value division of the (ϵ1, ϵ2)-core of supermodular two-scenario cooperative games in polynomial time in the number of players by exploiting the submodular intersection problem. Second, we showed that the non-emptiness of the (ϵ1, ϵ2)-core is determined by the sum ϵ1 + ϵ2, which we call the preference core value, rather than the pair (ϵ1, ϵ2). Finally, we characterized the preference core values of several specific supermodular two-scenario cooperative games such as the induced subgraph game, airport game, and multicast tree game. Whether we can obtain efficient algorithms tailored to the case of combining two different supermodular cooperative games (e.g., the induced subgraph game and multicast tree game) is an intriguing question. This remains to be addressed in future research. It is also interesting to extend our results to three-scenario (or more) cooperative games. An obstacle here is that it is NP-complete to decide whether the cores of three supermodular games have a non-empty intersection because finding a Hamiltonian path can be reduced to this problem. Hence, we need to introduce some approximation to efficiently handle this problem. ## References 1. [Borrero et al., 2016] Diego V. Borrero, Miguel A. Hinojosa, and Amparo M. Mármol. Stable solutions for multiple sce- nario cost allocation games with partial information. An- nals of Operations Research, 245(1):209-226, 2016. 2. [Chalkiadakis et al., 2011] Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge. Computational aspects of cooperative game theory. Synthesis Lectures on Artifi- cial Intelligence and Machine Learning, 5, 2011. 3. [Deng and Papadimitriou, 1994] Xiaotie Deng and Chris- tos H Papadimitriou. On the complexity of cooperative solution concepts. Mathematics of Operations Research, 19(2):257-266, 1994. 4. [Edmonds, 2003] Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Op- timization -Eureka, You Shrink!, pages 11-26. Springer, Berlin, Heidelberg, Berlin, Heidelberg, 2003. 5. [Feigenbaum et al., 2001] Joan Feigenbaum, Christos H Pa- padimitriou, and Scott Shenker. Sharing the cost of mul- ticast transmissions. Journal of computer and system sci- ences, 63(1):21-41, 2001. 6. [Fernández et al., 2004] Francisco R. Fernández, Miguel A. Hinojosa, and Justo Puerto. Set-valued TU-games. Euro- pean Journal of Operational Research, 159(1):181 -195, 2004. 7. [Fujishige, 2005] Satoru Fujishige. Submodular functions and optimization, volume 58 of Annals of Discrete Mathe- matics. Elsevier, 2nd edition, 2005. 8. [Gillies, 1959] Donald Brouce Gillies. Solutions to gen- eral non-zero-sum games. Contributions to the Theory of Games, 4:47-85, 1959. 9. [Graham et al., 1990] Daniel A Graham, Robert C Marshall, and Jean-Francois Richard. Differential payments within a bidder coalition and the Shapley value. The American Economic Review, 80:493-510, 1990. 10. [Hatano and Yoshida, 2017] Daisuke Hatano and Yuichi Yoshida. Computing least cores of supermodular cooper- ative games. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 551-557, 2017. 11. [Hinojosa et al., 2005] Miguel A. Hinojosa, Amparo M. Mármol, and Lyn C. Thomas. Core, least core and nucle- olus for multiple scenario cooperative games. European Journal of Operational Research, 164(1):225 -238, 2005. 12. [Ieong and Shoham, 2005] Samuel Ieong and Yoav Shoham. Marginal contribution nets: a compact representation scheme for coalitional games. In Proceedings 6th ACM Conference on Electronic Commerce, pages 193-202, 2005. 13. [Ieong and Shoham, 2006] Samuel Ieong and Yoav Shoham. Multi-attribute coalitional games. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 170- 179, 2006. 14. [Jörnsten et al., 1997] Kurt Jörnsten, M. Lind, and J. Tind. Stable payment schemes of TU-games with multiple crieria. Optimization, 40(1):57-78, 1997. 15. [Littlechild and Owen, 1973] S C Littlechild and G Owen. A simple expression for the Shapley value in a special case. Management Science, 20(3):370-372, 1973. 16. [Nishizaki and Sakawa, 2001] Ichiro Nishizaki and Masatoshi Sakawa. Fuzzy and Multiobjective Games for Conflict Resolution (Studies in Fuzziness and Soft Computing). Physica-Verlag, 2001. 17. [Oishi and Nakayama, 2009] Takayuki Oishi and Mikio Nakayama. Anti-dual of economic coalitional TU games. The Japanese Economic Review, 60(4):560-566, 2009. 18. [O'Neill, 1982] Barry O'Neill. A problem of rights arbi- tration from the Talmud. Mathematical Social Sciences, 2(4):345-371, 1982. 19. [Pistorius and Minoux, 2003] Joachim Pistorius and Michel Minoux. An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications. International Transactions in Operational Research, 10(1):1-11, 2003. 20. [Shapley and Shubik, 1966] Lloyd S. Shapley and Martin Shubik. Quasi-cores in a monetary economy with non- convex preferences. Econometrica, 34(4):805, 1966. 21. [Shapley, 1967] Lloyd S. Shapley. On balanced sets and cores. Naval research logistics quarterly, 14(4):453-460, 1967. 22. [Shapley, 1971] Lloyd S Shapley. Cores of convex games. International Journal of Game Theory, 1(1):11-26, 1971.