Computational Aspects of the Preference Cores of Supermodular Two-Scenario Cooperative Games

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.

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.

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.