|
Article Excerpt
In cooperative game theory, a characterization of games with stable cores is known as one of the most notorious open problems. We study this problem for a special case of the minimum coloring games, introduced by Deng et al. [10], which arise from a cost allocation problem when the players are involved in conflict. In this paper, we show that the minimum coloring game on a perfect graph has a stable core if and only if every vertex of the graph belongs to a maximum clique. We also consider the problem on the core largeness, the extendability, and the exactness of minimum coloring games. As a consequence, we show that it is coNP-complete to decide whether a given game has a large core, is extendable, or is exact.
Key words: cooperative game; core; minimum coloring game; stable set
MSC2000 subject classification: Primary: 91A12, 90C27; secondary: 05C85, 05C15, 68R10
OR/MS subject classification: Primary: games/group decisions, cooperative; secondary: networks/graphs, theory
**********
1. Introduction. One of the scopes of cooperative game theory is to establish the criterion of how to distribute a given revenue or cost among the agents, when they work in cooperation, in a fair manner. Since the effect of cooperation is usually nonlinear and nonadditive, the proportional division might not be considered fair. Several criteria, called solutions, are proposed by many researchers. When game theory was founded, von Neumann and Morgenstern [31] proposed a solution called a stable set which turned out to be very useful for the analysis of alot of bargaining situations, but also turned out to be too difficult to reveal some fundamental properties. Much easier to investigate is the core, due to Gillies [15]. So, people are interested in when a stable set is unique and coincides with the core, namely when the core is stable. This question is known as one of the most notorious problems. So far, there are some necessary or sufficient conditions known (see, e.g., van Gellekom et al. [30]), but they are far from a characterization of cooperative games with stable cores. From the computational point of view, the problem around stable sets is also eccentric. Deng and Papadimitriou [9] pointed out that determining the existence of a stable set for a given cooperative game is not known to be computable, and it is still unsolved.
Since combinatorial optimization problems can be found in several real-world situations, naturally they also raise some revenue/cost allocation problems. A combinatorial optimization game is a cooperative game which arises from a combinatorial optimization problem. There are many kinds of combinatorial optimization games proposed and studied, according to the underlying combinatorial optimization problems (Curiel [8]). However, as far as the core stability is concerned, almost nothing is studied. The only exception is a work by Solymosi and Raghavan [29] who studied the core stability of an assignment game.
In this paper, we study core stability of minimum coloring games introduced by Deng et al. [10], which arise from cost allocation problems when the agents are involved in conflict (Okamoto [24]). For example, when a number of conflicting tasks with unit processing time have to be performed on identical parallel machines, we may model the tasks as vertices and the conflicts as edges of a graph, and the chromatic number corresponds to the minimum number of machines we need to process the tasks as fast as possible. Then, the minimum coloring game on this graph represents a cost allocation problem among these tasks. The reason that we restrict to perfect graphs is that it is NP-complete to decide whether a given graph yields a minimum coloring game with a nonempty core (Deng et al. [10]) (meaning that there seems no good characterization of minimum coloring games with nonempty cores), and a graph G is perfect if and only if the minimum coloring game on G is totally balanced (Deng et al. [11]), where the total balancedness is a quite nice property. We prove that the minimum coloring game on a perfect graph has a stable core if and only if every vertex belongs to a maximum clique. We also consider the problem on the extendability, the largeness, and the exactness of cores, which are concepts related to core stability. We prove that these three concepts are equivalent for the minimum coloring game on a perfect graph, and also equivalent in that every clique is contained in a maximum clique.
Armed with our characterizations, we also study algorithmic aspects of these properties. First, we give a polynomial-time algorithm to determine whether a given perfect graph yields a minimum coloring game with stable core or not. On the other hand, we prove that it is hard (or coNP-complete, technically speaking) to determine whether a given perfect graph yields a minimum coloring game which is extendable, exact, or with large core. To the best of our knowledge, this is the first computational intractability result for extendability, exactness, and core largeness of cooperative games.
2. Preliminaries.
2.1. Notation. Throughout the paper, for a vector [??] [member of] [[??].sup.N] and S [subset or equal to] N, we write [??](S) := [summation]{[x.sub.i] | i [member of] S}. When S = [empty set], set [??](S) := 0. For a subset S [subset or equal to] N of a finite set N, the characteristic vector of S is a vector [[??].sub.s] [member of] [{0, 1}.sup.N] defined as [([[??].sub.s]).sub.i] = 1 if i [member of] S and [([[??].sub.s]).sub.i] = otherwise. Note that for S, T [subset or equal to] N it holds that [[??].sub.s](T) = [summation]{[([[??].sub.s]).sub.i] | i [member of] T} = [absolute value of (S [intersection] T)]. We use the notation A C B to mean that "A is a proper subset of B."
2.2. Graphs. A graph G is a pair G = (V, E) of a finite set V and a set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of 2-element subsets of V. An element of V is called a vertex and V itself is called the vertex set of G; an element of E is called an edge and E itself is called the edge set of G. For U [subset or equal to] V, the subgraph of G induced by U is denoted by G[U], where the vertices of G[U] are the elements of U and the edges of G[U] are the edges of G which are also 2-element subsets of U. The complement of G = (V, E) is a graph with vertex set V and edge set the complement of E. We denote the complement of G by G.
A clique is a vertex subset inducing a graph with every pair of vertices being an edge (such a graph is called complete). A clique is maximal if none of its proper supersets is a clique. A clique is maximum if it has a maximum size among all cliques. The size of a maximum clique of G is denoted by [omega](G). An independent set is a vertex subset inducing a graph with no edge. A maximal independent set and a maximum independent set are defined analogously to a clique. Notice that a clique of a graph G is an independent set of the complement and vice versa. A coloring of G = (V, E) is a mapping c: V [right arrow] [??] such that c(u) [not equal to] c(v) for every {u, v} [member of] E. A minimum coloring of G is a coloring with minimum possible [absolute value of (c(V))]. The chromatic number of G is [absolute value of (c(V))] of a minimum coloring c of G and denoted by [chi](G). Conventionally, the chromatic number of a graph with no vertex is defined to be zero. A graph G = (V, E) is perfect if [omega](G[U]) = x(G[U]) for every U [subset or equal to] V. A prominent example of nonperfect graphs is a cycle with five vertices.
2.3. NP-completeness. Here, we briefly and informally review terminology in the theory of algorithms and computation. For formal definitions of the terms introduced here, the reader is referred to a textbook of theory of computation, e.g., by Garey and Johson [14].
A decision problem is a family of instances, where each instance consists of a pair of an input and a question about the input that can be answered by "Yes" or "No." The class NP is the family of decision problems which have the following property: If an instance should be answered by "Yes" (in this case, we call the instance a Yes instance), there exists an object which certifies the instance as a Yes instance and which can be verified in polynomial time (such an object is called a polynomial-time checkable certificate of the instance). The class coNP is a kind of complement of NP defined as follows: coNP is the family of decision problems in which if an instance should be answered by "No" (in this case, we call the instance a No instance), there exists a polynomial-time checkable certificate which certifies the instance as a No instance. A decision problem is NP-complete if it belongs to NP and all problems in NP can be reduced to it in polynomial time. Similarly, a decision problem is coNP-complete if it belongs to coNP and all problems in coNP can be reduced to it in polynomial time. It is not known that any NP-complete problems and coNP-complete problems can be solved in polynomial time, but it is known that if one of the NP-complete problems or the coNP-complete problems can be solved in polynomial time, then all problems in NP and in coNP can be solved in polynomial time.
2.4. Cooperative games. A cooperative game (or simply a game) is a pair (N, [gamma]) of a nonempty finite set N and a function [gamma]: [2.sup.N] [right arrow] [??] satisfying [gamma]([empty set]) = 0. An element of N is called a player of the game, and [gamma] is called the characteristic function of the game. Furthermore, each subset S [subset or equal to] N is called a coalition. Literally, for S [subset or equal to] N the value [gamma](S) is interpreted as the total profit (or the total cost) for the players in S when they work in cooperation. In particular, [gamma](N) represents the total profit (or cost)...
|
