See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/223216660
Egoist's dilemma: a DEA game Article in Omega · April 2006 DOI: 10.1016/j.omega.2004.08.003
CITATIONS
READS
27
131
2 authors, including: Kaoru Tone National Graduate Institute for Policy Studies 110 PUBLICATIONS 5,661 CITATIONS SEE PROFILE
Some of the authors of this publication are also working on these related projects:
Kaizen by SBM_Max View project
All content following this page was uploaded by Kaoru Tone on 11 February 2015. The user has requested enhancement of the downloaded file. All in-text references underlined in blue are added to the original document and are linked to publications on ResearchGate, letting you access and read them immediately.
Omega 34 (2006) 135 – 148 www.elsevier.com/locate/omega
Egoist’s dilemma: a DEA game Ken Nakabayashi, Kaoru Tone∗ National Graduate Institute for Policy Studies, 2-2 Wakamatsu-cho, Shinjuku-ku, Tokyo162-8677, Japan Received 19 June 2003; accepted 23 August 2004 Available online 30 September 2004
Abstract This paper deals with problems of consensus-making among individuals or organizations with multiple criteria for evaluating their performance when the players are supposed to be egoistic; in the sense that each player sticks to his superiority regarding the criteria. We analyze this situation within the framework or concept developed in data envelopment analysis (DEA). This leads to a dilemma called the ‘egoist’s dilemma’. We examine this dilemma using cooperative game theory and propose a solution. The scheme developed in this paper can also be applied to attaining fair cost allocations as well as benefit–cost distributions. 䉷 2004 Elsevier Ltd. All rights reserved. Keywords: Game theory; Cooperative game; DEA; Variable weight; Shapley value; Nucleolus; Assurance region method; Cost allocation
1. Introduction Let us suppose n players each have m criteria for evaluating their competency or ability, which is represented by a positive score for each criterion. As with usual classroom examinations, the higher the score for a criterion is, the better the player is judged to perform that criterion. For example, let the players be three students A, B and C, with three criteria, mathematics, literature and gymnastics. The scores are their records for the three subjects, measured by positive cardinal numbers. Now, we want to allocate a certain amount of fellowship grant funds to the three students in accordance with their scores in the three criteria. All players are supposed to be selfish or egoistic in the sense that they insist on their own advantage on the scores. However, they must reach a consensus in order to get the fellowship. Similar situations exist in many societal problems as discussed later. This paper proposes a new scheme for allocating or imputing the given benefit to the players under the framework ∗ Corresponding author. Tel.: +81-3-3341-0438;
fax: +81-3-3341-0220. E-mail address:
[email protected] (K. Tone). 0305-0483/$ - see front matter 䉷 2004 Elsevier Ltd. All rights reserved. doi:10.1016/j.omega.2004.08.003
of game theory and data envelopment analysis (DEA). This scheme can also be applied for attaining fair expense (cost) allocations, as well as benefit–cost (B–C) distributions. The rest of this paper unfolds as follows. Section 2 describes the basic model of the DEA game and its properties. In Section 3, we observe and propose several methods for imputation, including Shapley value and nucleolus. Also, we discuss the relationship between our DEA game with Owen’s [1] linear production game. Extensions to the basic model are discussed in Section 4. Section 5 presents several potential applications of this model. Finally, some concluding remarks follow in Section 6. 2. Basic models of the game We introduce the basic models and structures of the game and uncover its mathematical properties. 2.1. Selfish behavior and the egoist’s dilemma m×n Let X = (xij ) ∈ R+ be the score matrix, consisting of the record xij of player j to the criterion i. It is assumed that the higher the score for a criterion is, the better the
136
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
player is judged to perform as regard to that criterion. Each player k has a right to choose a set of nonnegative weights k ) to the criteria that are most preferable w k = (w1k , . . . , wm to the player. Using the weight wk , we define the relative score of player k to the total score as follows: m k i=1 wi xik . (1) m n k i=1 wi ( j =1 xij ) The denominator represents the total score of all players as measured by player k’s weight selection, while the numerator indicates player k’s self evaluation using the same weight selection. Hence, the expression (1) demonstrates player k’s relative importance (share) under the weight (or value) selection w k . We assume that the weighted scores are transferable. Player k wishes to maximize this ratio by selecting the most preferable weights, thus resulting in the following fractional program. m wik xik max m i=1 n k wk i=1 wi ( j =1 xij ) s.t.
wik 0(∀i).
(2)
The motivation behind this program is that player k aims to maximize his relative value as measured by the ratio: the weighted sum of his records vs. the weighted sum of all players’ records. This arbitrary weight selection is the fundamental concept underlying DEA initiated by Charnes et al. [2]. DEA terms this as ‘variable’ weight, in contrast to a priori ‘fixed’ one. Refer to Cooper et al. [3, pp. 12–13] for further explanation of this issue. Before continuing, we reformulate the problem as follows, without losing generality. We normalize the data set X so that it is row-wise normalized, i.e., n
xij = 1
j =1
For this purpose, we divide the row (xi1 , . . . , xin ) by the row-sum nj=1 xij for i = 1, . . . , m. The program (2) is not affected by this operation. Thus, using the Charnes–Cooper transformation scheme, the fractional program (2) can be expressed using a linear program as follows: c(k) = max s.t. wik 0
i=1 m i=1
wik xik
(k = 1, . . . , n).
(4)
The c(k) indicates the highest relative score for player k which is obtained by the optimal weight selecting behavior. k The optimal weight wi(k) may differ from one player to another. Proposition 1. n
c(k) 1.
(5)
k=1
Proof. Let the optimal weight for player k be wk∗ = ∗ , . . . , w ∗ ), i.e., w ∗ ∗ (w1k mk i(k)k = 1 and wik = 0(∀i = i(k)). Then we have n
c(k) =
k=1
m n k=1 i=1
∗x = wik ik
n k=1
xi(k)k
n
x1k = 1.
k=1
The inequality above follows from xi(k)k x1k and the last equality follows from the row-wise normalization. This proposition asserts that, if each player sticks to his egoistic sense of value and insists on getting the portion of the benefit as designated by c(k), the sum of shares usually exceeds 1 and hence c(k) cannot fulfill the role of division (imputation) of the benefit. If eventually the sum of c(k) turns out to be 1, all players will agree to accept the division c(k), since this is obtained by the player’s most preferable weight selection. The latter case will occur when all players have the same and common optimal weight selection. More concretely, we have the following proposition.
x1k = x2k = · · · = xmk
Proof. The ‘If’ part can be seen as follows. Since c(k)=x1k for all k, we have
k=1
(3)
Now, theproblem is to maximize the objective (3) on the k simplex m i=1 wi = 1. Apparently, the optimal solution is k for the criterion i(k) such that given by assigning 1 to wi(k) xi(k) =max{xik |i =1, . . . , m}, and assigning 0 to the weight
for k = 1, . . . , n.
That is, each player has the same score with respect to the m criteria.
n
wik = 1,
(∀i).
c(k) = xi(k)
Proposition 2. The equality nk=1 c(k) = 1 holds if and only if the score matrix satisfies the condition
(∀i).
m
of the remaining criteria. We denote this optimal value by c(k).
c(k) =
n
x1k = 1.
k=1
The ‘Only if’ part can be demonstrated as follows. Suppose x11 > x21 , then there must be a column h = 1 such that x1h < x2h , otherwise the second row sum can not attain 1. Thus, we have c(1) x11 , c(h) x2h > x1h c(j ) x1j (∀j = 1, h).
and
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
Proposition 3. The characteristic function c is sub-additive, i.e., for any S ⊂ N and T ⊂ N with S ∩ T = we have
Hence, it holds that n
n
c(k)
k=1
x1j + x2h >
j =1, =h
n
137
x1j = 1.
c(S ∪ T ) c(S) + c(T ).
j =1
This leads to a contradiction. Therefore, player 1 must have the same score in all criteria. The same relation must hold for the other players. In the above case, only one criterion is needed for describing the game and the division (imputation) proportional to this score is a fair division. However, such situations might occur n only in rare instances. In the majority of cases, we have k=1 c(k) > 1. We may call this the ‘egoist’s dilemma’ and, as we see later, many societal problems (conflicts) belong to this class. One might think that a benefit allocation proportional to {c(k)} is one possible solution. However, this allocation is by no means rational if we admit coalitions among players.
(8)
Proof. By renumbering the indexes, we can assume that S = {1, . . . , h}, T = {h + 1, . . . , k} and S ∪ T = {1, . . . , k}. For these sets, it holds that k
c(S ∪ T ) = max i
xij max i
j =1
+ max i
k
h
xij = c(S) + c(T ).
We also have the following proposition. Proposition 4. c(N) = 1.
In order to attain a fair division (imputation), we assume the following agreements among the players, although each ‘selfish’ player sticks to his most preferable weight selection behavior as expressed by the program (3).
2.4. Another expression of the game
We note here that our main objective is to find a fair division z = (z1 , . . . , zn ) by cooperative game theory and z is not always expressed as z = wX by a certain common weight w = (w1 , . . . , wm ). We discuss this subject in Section 3.6.
j =h+1
2.2. Assumption on the game and fair division
(A1) All players agree not to break off the game. (A2) All players are willing to negotiate with each other to attain a reasonable and fair division z = (z1 , . . . , zn ).
xij
j =1
Let us define another game (N, v) by v(S) = c(j ) − c(S).
(9)
j ∈S
(We use the notation c(j ) instead of c({j }) for brevity.) Proposition 5. (N, v) is super-additive, i.e., v(S) + v(T ) v(S ∪ T ) ∀S, T ⊂ N and S ∩ T = . Proof.
2.3. Coalition with additive property Let the coalition S be a subset of the player set N = (1, . . . , n). The record for the coalition S is defined by xi (S) =
j ∈S
xij
(i = 1, . . . , m).
(6)
j ∈S∪T
This coalition aims at obtaining the maximal outcome c(S): c(S) = max s.t.
v(S) + v(T ) c(j ) − c(S) + c(j ) − c(T ) = j ∈S j ∈T c(j ) − {c(S) + c(T )} =
m i=1 m
c(j ) − c(S ∪ T ) = v(S ∪ T ).
j ∈S∪T
wi xi (S) wi = 1, wi 0 (∀i).
We have v(j ) = 0(∀j ) and (7)
i=1
The c(S), with c() = 0, defines a characteristic function of the coalition S. Thus, we have a game in coalition form with transferable utility, as represented by (N, c).
v(N) =
n j =1
c(j ) − c(N) =
n
c(j ) − 1 > 0.
j =1
Hence the game (N, v) is 0-normalized. Let an imputation of the game (N, v) be y = (y1 , . . . , yn ), which
138
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
n satisfies yj v(j ) = 0(∀j ) and j =1 yj = v(N). Using y = (y1 , . . . , yn ), we can define a benefit allocation z = (z1 , . . . , zn ) by . . . , n). This zj = c(j )− yj (j = 1, allocation satisfies nj=1 zj = nj=1 c(j ) − nj=1 yj = 1. Hence, it is equivalent to defining our game by (N, c) or by (N, v). (N, v) (and (N, d)) are monotone games.
s.t.
i=1 m i=1
wik xik wik 0
(∀i).
(10)
Proposition 6.
n
i
xij i
n
xij + max i
j =h+1 n
xij + max
j =h+1
n
xij + max
j =h+1
= 1 − max
n
xij −
j =1
j =h+1
i
xij
j =h+1
n
xij
j =h+1 n
xij = 1.
j =h+1
Thus, we have Corollary 1. (N, c) and (N, d) are dual games.
Proposition 3 suggests that the DEA max game (N, c) might be a concave game, i.e., for any coalitions S and T , it holds that
k=1
Analogously to the max game case, for the coalition S ⊂ N , we define
s.t.
= min i
i
j =1
n
xij + max
2.6. Convex or concave game
d(k) 1.
d(S) = min
h
i
The optimal value d(k) assures the minimum division that player k can expect from the game. In this case, as a counterpart of Proposition 1, we have:
n
d(S) + c(N \S)
= min 1 −
wik = 1,
and
For these sets, it holds that
i
We observe here the opposite side of the egoist’s game (N, c). This is defined by replacing max in (3) by min as follows: d(k) = min
S = {1, . . . , h}, N = {1, . . . , n} N \S = {h + 1, . . . , n}.
= min
2.5. A DEA minimum game
m
Proof. By renumbering the indexes, we can assume that
m i=1 m
(14)
However, unfortunately this conjecture is not true. This is demonstrated by the counterexample below.
wi xi (S) wi = 1,
c(S ∪ T ) + c(S ∩ T ) c(S) + c(T ).
wi 0(∀i).
(11)
i=1
Apparently, it holds that d(N ) = 1. The DEA min game (N, d) is super-additive, i.e., we have d(S ∪ T ) d(S) + d(T ) ∀S, T ⊂ N with S ∩ T = .
(12)
Example 1. Table 1 exhibits a DEA game with four players and three criteria. The scores are row-wise normalized so that the sum of the row elements is equal to 1 for each row. Let S = {A, B}, T = {B, C}, S ∪ T = {A, B, C} and S ∩ T = {B}. Then we have: c(S) = 0.75, c(T ) = 0.5, c(S ∪ T ) = 0.95, c(S ∩ T ) = 0.375. Hence it holds that c(S) + c(T ) = 1.25 < 1.325 = c(S ∪ T ) + c(S ∩ T ), showing the non-concavity of this game.
Thus, this game starts from d(k) > 0(k = 1, . . . , n) and enlarges the gains by the coalitions until the grand coalition N with d(N) = 1 is reached. Between the games (N, c) and (N, d) we have the following proposition:
However, the concept of concavity is situation-specific and so we should check it case by case. In the case of S ∪ T = N , we have the following proposition.
Proposition 7.
Proposition 8.
d(S) + c(N \S) = 1
∀S ⊂ N.
=
(13)
1 + c(S ∩ T ) c(S) + c(T ) ∀S, T ⊂ N with S ∪ T = N.
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
139
Table 1 Example 1
Criterion 1 Criterion 2 Criterion 3
Player A
Player B
Player C
Player D
Row-sum
0.5 0.375 0.5
0.25 0.375 0.25
0.2 0.125 0.125
0.05 0.125 0.125
1 1 1
Proof. From the super-additivity of d(·), we have the following inequality: d({S\(S ∩ T )} ∪ {T \(S ∩ T )}) d(S\(S ∩ T )) + d(T \(S ∩ T )). From Proposition 7, it holds that d(S\(S ∩ T )) = 1 − c(T ), d(T \(S ∩T ))=1−c(S) and d({S\(S ∩T )}∪{T \(S ∩ T )}) = 1 − c(S ∩ T ). Hence we have,
Proof. Let the three players be i, j and k. Then we have, v(i, k) + v(j, k) = {c(i) + c(k) − c(i, k)} + {c(j ) + c(k) − c(j, k)} = c(i) + c(j ) + 2c(k) − {c(i, k) + c(j, k)} c(i) + c(j ) + 2c(k) − {c(i, j, k) + c(k)} = c(i) + c(j ) + c(k) − c(i, j, k) = v(i, j, k). (We note that the game (N, v) is 0-normalized.)
3. Imputations
1 − c(S ∩ T ) {1 − c(T )} + {1 − c(S)} 1 + c(S ∩ T ) c(S) + c(T ).
In this section, we observe the core, the Shapley value and nucleolus as the representative imputations of the cooperative game and discuss their mathematical properties associated with the DEA game. Since the DEA max and min games are dual, the Shapley value of the DEA max game is the same as that of the DEA min game. We then discuss the common weight problem. Finally, several computational issues are presented.
Similarly we have, for the game (N, d). Corollary 2. 1 + d(S ∩ T ) d(S) + d(T ) ∀S, T ⊂ N with S ∪ T = N. From Proposition 8, we have the following proposition in the case of three players. Proposition 9. The DEA game (N, c) with three players is concave. Proof. Let the three players be i, j and k. Then we have, from Proposition 8, the following inequality.
3.1. Conditions for imputation An imputation of the DEA min game (N, d) is a vector z = (z1 , . . . , zn ) that satisfies the following individual and grand coalition rationalities. Individual rationality: zj d(j ), Grand coalition rationality:
n
j = 1, . . . , n
zj = d(N) = 1.
j =1
c(j, k) + c(i, k) 1 + c(k) = c(i, j, k) + c(k). (We use the notation c(j, k) instead of c({j, k})).
Similarly we have the following proposition. Proposition 10. The DEA game (N, d) with three players is convex. Furthermore, the transformed game (N, v) in the threeplayer case has the convex structure. Proposition 11. The DEA game (N, v) with three players is convex.
Let an imputation of the transformed game (N, v) be y = (y1 , . . . , yn ), which satisfies yj v(j ) = 0(∀j ) and
n
yj = v(N).
j =1
A benefit allocation z=(z1 , . . . , z n )=(c(1)−y1 , . . . , c(n)− yn ) satisfies zj c(j )(∀j ) and nj=1 zj = 1. This is the induced imputation of the max game (N, c). 3.2. The core The core of the DEA min game (N, d) is the set of imputations that satisfies the following collective rationality, in
140
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
addition to the individual and grand coalition rationalities. zj d(S), ∀S ⊂ N. (15) Collective rationality: j ∈S
Since the core of a convex game is not void, the core of DEA games (N, d) and (N, v) with three players is not void by Propositions 10 and 11. More generally, Owen [1] introduced linear program games associated with an economic production process and demonstrated that they have a nonempty core. Comparing our DEA game with his case, we found that the DEA game can be interpreted as the dual of his linear program. Owen’s LP game has a coalition on the right-hand side vector of the constraints, whereas the coalition of the DEA game appears on the objective function vector. Since the optimal primal value that defines the characteristic function of a coalition is equal to the optimal dual value by the duality theorem, his Theorem 1 (that the LP game is balanced) is valid in our case, too. Thus, the DEA games are balanced. A game has a core if and only if it is balanced [4]. Therefore we have the following two propositions. Proposition 12. The DEA min game (N, d) is a balanced game. Hence its core is nonempty. Proof. Although this proposition is a direct consequence of Owen [1], we give another proof in a manner specific to the DEA game. Let an arbitrary 2n −2 dimensional nonnegative vector be = (S : S ⊂ N) which satisfies S:j ∈S ⊂ N S =
=
=
1(∀j ∈ N). If we can demonstrate that the following inequality holds for this vector, then the game (N, d) is a balanced game [4]. S d(S) d(N) = 1. S⊂ N
=
This inequality can be obtained as follows: S d(S) = S min xij S⊂ N
=
i
S⊂ N
=
j ∈S
Furthermore, Owen [1] developed a method for finding points in the core. Amazingly, following his method, we found that any row of the normalized score matrix X or any convex combination of rows of X is an imputation in the core. In other words, we have the following proposition. m in the Proposition 14. For any w = (w1 , . . . , wm ) ∈ R+ simplex w1 + · · · + wm = 1, the vector wX is an imputation in the core of the DEA game.
(See Appendix A for a proof.) However, the reverse is not always true, i.e., there are imputations in the core that cannot be expressed as wX. We will demonstrate this in Example 5. 3.3. The Shapley value The Shapley value i (d) of player i for the DEA min game (N, d) is defined by i (d) =
Proposition 15. The Shapley values of the DEA max and min games (N, c) and (N, d) are the same. Proof. Since the games (N, c) and (N, d) are dual games, they have the same Shapley value. This is clear from the following: For all i ∈ N, we have
min S xij i S⊂ N
=
j ∈N
= min i
j ∈N
S:j ∈S ⊂ N
xij = 1.
S:i∈S⊂N
S:i∈S⊂N
j ∈S
=
S
Similarly, we can demonstrate that the DEA game (N, v) is balanced. Proposition 13. The DEA game (N, v) is a balanced game. Hence its core is nonempty.
(s − 1)!(n − s)! [{1 − d(N \S)} n!
S:i∈S⊂N
× {d(N \S ∪ {i}) − d(N \S)}.
=
(s − 1)!(n − s)! {c(S) − c(S\{i})} n!
− {1 − d(N\S ∪ {i})}] (s − 1)!(n − s)! = n!
xij = min i
S:i∈S⊂N
(s − 1)!(n − s)! {d(S) − d(S\{i})}, (16) n
where s is the number of members of coalition S. This value is the mathematical expectation of the marginal contribution of player i when all orders of formation of the grand coalition are equi-probable. Regarding the DEA-games, we have the following remarkable property.
i (c) =
By replacing S = N\S ∪ {i} and defining s as the number of members in the coalition S , the last term turns out to: =
S : i∈S ⊂N
= i (d).
(s − 1)!(n − s ) {d(S ) − d(S \{i})} n!
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
Example 2. The Shapley values of the max and min games for the data set given in Table 1 are the same. Actually, the imputation is (0.44375, 0.30625, 0.15625, 0.09375). It has been proved that the Shapley value of a convex game belongs to the core of the game. Hence, by Proposition 10, the Shapley value of the DEA min game (N, d) for the three-player case belongs to the core. Although the DEA min game with four or more players is not necessarily convex, we can demonstrate that the Shapley value of the four-player case is included in the core. See Appendix B for a proof.
141
immediately implies that the Shapley allocation for A is at least as large as the Shapley allocation for B. It also implies (see e.g., [5]), that the nucleolus allocation to A is at least as large as that for B. Proposition 16. If player A dominates player B, then the Shapley allocation for A is not less than that for player B. Proposition 17. If player A dominates player B, then the nucleolus allocation for A is not less than that for player B. 3.6. On the common weight vector
3.4. The nucleolus Let an imputation of the DEA game (N, d) be z = (z1 , . . . , zn ). Then we define the excess of each coalition S as follows: zj . (17) e(S, z) = d(S) − j ∈S
In the DEA game, the excess measures the “degree of unhappiness” of coalition S when z expresses benefit, but measures the “degree of happiness” when z expresses cost. The nucleolus is the imputation that minimizes (lexicographically) the maximum excess. Let (z) be the vector (with 2n − 2 components) of the excesses of all coalitions S ⊂ N(S = , N), ordered by increasing magnitude, i.e., n (z) = (e(S 1 , z), . . . , e(S 2 −2 , z)), n e(S 1 , z) · · · e(S 2 −2 , z).
We introduce a lexicographic ordering of the vectors (z), i.e., (z)>L (y) if ∃k ∈ {1, . . . , 2n −2}, such that e(S i , z)= e(S i , y)(i = 1, . . . , k − 1) and e(S k , z) > e(S k , y). Let the entire imputation set of the DEA game (N, d) be Z, then the nucleolus of (N, d) is defined by (Z) = {z ∈ Z|(z) L (y),
∀y ∈ Z}.
If the core is non-empty, then the nucleolus is included in the core. The nucleolus of the DEA min game is not necessarily the same as that of the max game, in contrast to the Shapley value case. This is demonstrated by the next example. Example 3. The nucleolus of the data set in Table 1 is as follows. For the min game (N, d), it is (0.46, 0.29, 0.16, 0.09), whereas for the max game (N, c) it is (0.45, 0.3, 0.15, 0.1). 3.5. On the dominance relationship We say player A dominates player B if xiA xiB (∀i). If player A dominates B, then for every coalition S excluding A and B, d(S ∪ {A}) − d(S) d(S ∪ {B}) − d(S). This result
We began this paper by introducing the most preferable weight selection behavior of players. Now we return to this subject incorporating our knowledge of imputation z = (z1 . . . , zn ) induced by coalitions and allocations, e.g., the Shapley value and nucleolus. The weight w = (w1 , . . . , wm ) ∈ R m associates with the imputation z = (z1 , . . . , zn ) ∈ R n via wX ∈ R n . In an effort to determine w in a way that wX approximates z as close as possible, we formulate the following LP with variables w ∈ R m , s + ∈ R n , s − ∈ R n , p ∈ R. p wx j + sj+ − sj− = zj (j = 1, . . . , n), w1 + · · · + wm = 1, sj+ p, sj− p (j = 1, . . . , n),
min s.t.
wi 0 (i = 1, . . . , m), sj+ 0, sj− 0 (j = 1, . . . , n),
(18)
where xj denote the j th column vector of X. ∗ Let an optimal solution of this program be (p ∗ , w ∗ , s + , ∗ − s ). Then we have two cases. Case 1: p ∗ = 0. In this case, it holds that z = w ∗ X, and so the imputation z is explained by the common weight w∗ . All players will accept this solution since it represents the common value judgment corresponding to the cooperative game solution. We note that there still remains the uniqueness issue of w ∗ . Case 2: p ∗ > 0. In this case, we have no common weight w∗ which can express z as z = w ∗ X perfectly. Example 4. As Example 2 shows, the Shapley value of the DEA game for the data set in Example 1 is (0.44375, 0.30625, 0.15625, 0.09375). For this imputation, the optimal solution of the LP (18) satisfies p∗ = 0 and hence this game has a common weight w1∗ = 0.41667, w2∗ = 0.45, w3∗ = 0.13333 that explains the game solution completely. Example 5. Table 2 exhibits a DEA game with five players and three criteria.
142
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
Table 2 A five players and three criteria case
Criterion 1 Criterion 2 Criterion 3
Player A
Player B
Player C
Player D
Player E
Row-sum
0.4 0.4 0.001
0.4 0.3 0.001
0.1 0.125 0.01
0.05 0.05 0.5
0.05 0.125 0.488
1 1 1
Table 3 The Shapley value
Shapley
Player A
Player B
Player C
Player D
Player E
Total
0.2064667
0.190967
0.064217
0.26755
0.2708
1
The imputation by the Shapley value of this game is displayed in Table 3. The optimal objective value of LP (18) is p∗ =0.00264328 with the optimal weight w1∗ = 0.336314,
w2∗ = 0.185265,
w3∗ = 0.478421.
Hence this problem has no common weight for expressing the Shapley value. The optimal weight can approximate the Shapley value within the tolerance p ∗ = 0.00264328. Also, this example demonstrates a counterexample to the reverse of Proposition 14. We examined and confirmed that the Shapley value shown above belongs to the core. However, it cannot be expressed in the form wX, as evidenced by the above positive p ∗ = 0.00264328. The existence of the common weight vector w is not always guaranteed, as demonstrated by Example 5 above for the Shapley value. The same is true in the case of the nucleolus. Our view is that the imputation z is our main objective, which is the solution of the DEA game. In contrast, the common weight vector w is a (secondary) by-product induced by the imputation. In fact, if the inequality m>n holds for the data matrix X ∈ R m×n (the number of players is far larger than that of criteria), then the equation z = wX with w in the simplex can hardly have a (feasible) solution. Since the imputation z is obtained as a cooperative game solution, it has a complicated structure that cannot be expressed by the simple relationship z = wX. However, we must acknowledge that the weight w has an important role in decision-making. We discuss this subject in more detail in Section 4.2.
4.1. A benefit-cost (B–C) game So far we have dealt with a DEA game in which the score matrix X represents the superiority (benefits) of players. However, there are occasions where some criteria exhibit inferiority (costs). Thus, the merit of a player is evaluated by the difference (profit) between benefits and costs. Suppose that there are s criteria for representing benefits and m criteria for costs. Let yij (i = 1, . . . , s) and xij (i = 1, . . . , m) be the benefits and costs of player j (j =1, . . . , n), respectively. The merit of player j is evaluated by (u1 y1j + · · · + us ysj ) − (v1 x1j + · · · + vm xmj ), where u = (u1 , . . . , us ) and v = (v1 , . . . , vm ) are, respectively, the virtual weights for benefits and costs. Analogous to the expression (1), we define the relative score of player j to the total scores as follows: s ui yij − m ij i=1 vi x s i=1 . (19) n m n u ( y ) − v ( i ik i i=1 k=1 i=1 k=1 xik ) Player j wishes to maximize his score, subject to the condition that the merit of all players is nonnegative, i.e. s
ui yik −
i=1
In this section, we extend our basic model to a B–C game and discuss the zero weight and weight preference issues, along with computational procedures.
vi xik 0
(k = 1, . . . , n).
(20)
i=1
We can express this situation by the linear program below: max v,u
s.t. 4. Extensions
m
s i=1 s i=1
s i=1
ui yij − ui
m i=1
n
k=1
ui yik −
vi 0(∀i),
vi xij
yik − m
m
vi
i=1
vi xik 0
n
xik = 1
k=1
(k = 1, . . . , n)
i=1
ui 0(∀i).
(21)
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
Following the same scenario as the DEA game in the preceding sections, we can develop coalitions and imputations of this B–C game, although the row-wise normalization is not available in this game. That is, a characteristic function of the coalition S is defined by the linear program below: s
c(S) = max v,u
ui
j ∈S
i=1 s
s.t.
ui
i=1
−
m
vi
i=1
s
yij −
vi
j ∈S
i=1
n
xij
c(N \S) = max v,u
xik = 1
k=1 m
ui yik −
vi xik 0
= max v,u
(k = 1, . . . , n)
i=1
vi 0 (∀i),
ui 0 (∀i).
(22)
In the program (22), we keep the condition that the merit of all players is nonnegative. Since the constraints of program (22) are the same for all coalitions, we have the following proposition: Proposition 18. The B–C max game satisfies a sub-additive property. Proof. For any S ⊂ N and T ⊂ N with S ∩ T = , we have s m ui yij − vi c(S ∪ T ) = max v,u j ∈S∪T
i=1
i=1
j ∈S∪T
xij
s ui yij + yij = max v,u j ∈S
i=1
−
m
vi
j ∈T
xij +
j ∈S
i=1
xij
j ∈T
+
j ∈S
i=1
s
ui
i=1
j ∈T
j ∈S
i=1
yij −
m
vi
i=1
j ∈T
i=1
+ max v,u
s
j ∈S
ui
i=1
i=1
j ∈T
= c(S) + c(T ).
It also holds that c(N) = 1.
yij −
m i=1
j ∈S
vi
j ∈T
ui
i=1
j ∈N\S
s
ui
j ∈N
i=1
m
vi
vi
j ∈N\S
i=1
yij −
xij −
j ∈N
i=1
yij −
m
j ∈S
j ∈S
xij
yij
xij
s m ui yij − vi xij = max v,u −
j ∈N
i=1
s
ui
i=1
j ∈S
= max 1 − v,u
yij −
s
vi
i=1
ui
j ∈N
i=1
m
i=1
j ∈S
i=1
j ∈S
yij −
j ∈S m
xij
vi
i=1
j ∈S
xij
s m ui yij − vi xij = 1 − min v,u
i=1
j ∈S
From Proposition 19, the Shapley values of the B–C max and min games are the same, since they are dual games. Similarly we can confirm that the B–C min game is balanced and has a non-empty core, and that the B–C max and min games with three players are concave and convex respectively. 4.2. Avoiding occurrence of zero weight and setting preference on weights
xij
s m ui yij − vi xij max v,u
−
s
= 1 − d(S).
s m ui yij − vi xij = max v,u
Proposition 19. The B–C max game (N, c) and min game (N, d) are dual games, i.e., for any S ⊂ N , we have
Proof.
n
As with the basic models of the DEA game, we can define the B–C minimum game, which satisfies a super-additive property, and arrive at the following proposition:
d(S) + c(N \S) = 1.
yik
k=1
i=1
m
143
xij
In Section 3.6, we presented a scheme for determining the weight w through the program (18). Eventually, a certain weight may happen to be zero for all optimal solutions. This means that the corresponding criterion is not accounted for in the solution of the game at all, even though the criterion might be taken as an important factor at the beginning. More generally, let us suppose that all players agree to put preference on certain criteria. For example, Criterion 1 is more important than Criterion 2. In this case, we must add the following constraint to the original LP
144
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
Table 4 Three player and three criteria data
Criterion 1 Criterion 2 Criterion 3
Table 6 The Shapley value after weight constraints
Player A
Player B
Player C
Row-sum
0.2 0.5 0.6
0.4 0.2 0.2
0.4 0.3 0.2
1 1 1
Shapley
Table 5 The Shapley value of Example 6
Shapley
Player A
Player B
Player C
Sum
0.4
0.3
0.3
1
Player A
Player B
Player C
Sum
0.428929
0.271429
0.299642
1
Players B and C, even though Player C has a higher score (0.3) in Criterion 2 than Player B (0.2). Therefore, Criterion 2 is neglected in this imputation. In order to avoid this inconvenience, we set constraints on weights, for example, as follows: w 0.5 2 2, w1
w 0.5 3 2. w1
(24)
formulation (3). w 1 w2
or
w1 /w2 1.
This same constraint should be included in the coalition LP (7), too. The zero weight issue can thus be solved in this way. If all players agree to incorporate preference regarding criteria, we can apply the following “assurance region method,” originally developed in the DEA literature, e.g., [6,7]. Let the reference criterion be w1 , for example. We set constraints on the ratio w1 vs. wi (i = 2, . . . , m) as follows: Li
wi Ui , w1
(i = 2, . . . , m),
where Li and Ui denote the lower and upper bounds of the ratio wi /w1 , respectively. These bounds must be set by agreement among all players. The program (7) is now modified as: m
c(S) = max s.t.
i=1 m
wi xi (S) wi = 1
i=1
wi Ui w1 wi 0 (∀i). Li
(i = 2, . . . , m) (23)
Potentially, there are many other types of weight constraints in the DEA literature. Refer to [8]. Example 6. A data set with three players and three criteria is displayed in Table 4, along with its Shapley value in Table 5. By solving LP (18), we found p ∗ = 0 with the optimal weight (w1∗ = 0.5, w2∗ = 0, w3∗ = 0.5). Moreover, the optimal common weight is uniquely determined. Hence, in evaluating the Shapley value, Criterion 2 (w2∗ = 0) has no role at all. This is also reflected in the same Shapley score (0.3) of
We solved the corresponding program (23) after converting the fractional terms into linear inequalities. We found the Shapley value displayed in Table 6. Now, Player C is ranked higher than B in recognition of Criterion 2. The common weight for this Shapley value is obtained by solving LP (18) and we have (p∗ = 0, w1∗ = 0.357143, w2∗ = 0.282143, w3∗ = 0.360714) which satisfies all constraints in (24). 4.3. Computational issues Here we introduce a stepwise procedure for applying our DEA-game scheme. Step 1: To determine a score matrix. Players or experts list all criteria that they consider to be important in consensus-making and measure each player’s record for each criterion. In the assurance region (AR) case, they also determine the lower/upper bounds of the ratio of weights for criteria. Step 2: To determine the characteristic function values for all coalitions. In the basic model (7), after the row-wise normalization, a characteristic function value of each coalition is obtained simply by finding its maximum (or minimum) score as designated by (4) for the individual player case. In the benefit–cost game and the AR case, we need to solve the linear programs (22) or (23). Step 3: To determine an imputation. Using the characteristic function values of all coalitions, the Shapley or nucleolus allocation is calculated by the same approach as cooperative game theory. We have developed DEA game software which can directly calculate the Shapley and nucleolus allocation from a score matrix (with the lower/upper bounds in the AR case). This code can solve the DEA game with up to 20 players within reasonable CPU time on a PC. The CPU time increases exponentially with the number of players and linearly with that of criteria.
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
5. Applications We now present some of the potential applications of our DEA game. In the literature on cooperative game theory, there have been many applications to cost or benefit-sharing problems. The proposed DEA game models are in sharp contrast to them, in that we can deal with these problems under multi-criteria environments that are common to real conflicts in our society. 5.1. DEA max game This game can be applied for the purpose of allocating benefits to players. Typical examples include research grant allocation to applicants by a foundation. The multiple criteria are, among others: 1. 2. 3. 4.
Novelty of subject. Feasibility of research. Influence on advance of science. Past records of applicants.
Also, many resource distribution problems for R&D belong to this class. In this case, the multiple criteria are, among others, 1. Short term profitability. 2. Contributions to the future of the company. 3. Spillover effects on the existing technologies of the company.
5.2. DEA min game Typical potential applications of this model include cost allocation or burden sharing problems. Each player wishes to minimize his share, although the participants must pay a certain amount of cost in total. The UN, NATO and many other international organizations have this kind of problem. According to Kim and Hendry [9], in the NATO burdensharing case, they have pointed out the following items as the criteria for benefits. 1. Protection from external threat: The degree of reliance on USA (NATO) protection against an external threat. 2. Political benefits: The relative size of benefits accrued to NATO members by utilizing NATO as a policy tool in pursuing their foreign policy goals. 3. Receipt of economic and military aid: Amount of USA economic and military aid received. 4. Receipt of economic spin-offs (foreign exchange income): The number of USA troops stationed in a member nation. 5. Receipt of economic spin-offs (employment in defense industry): The number of workers employed in world’s top 100 defense contractors.
145
Kim and Hendry [9] analyzed this problem within the traditional DEA framework by incorporating other cost factors as outputs and benefit factors as inputs. Comparisons between the two approaches will present an interesting research task.
5.3. DEA benefit–cost game This model is applicable for the cases in which every player has both merits and demerits. As an example, we point to the trilateral relationship in security between Japan, South Korea and USA. The three countries have been playing crucial roles in security in the Far-East Asia since the end of the Second World War (1945). In fact, Japan and USA have been in alliance (as represented by the JapanUS Security Treaty, 1951-present). A similar alliance exists between South Korea and USA (the US-ROK Mutual Defense Treaty, 1954-present). Though Japan and Korea do not have a formal security treaty, potential military reciprocity through USA exists. Cha [10] called this relationship a ‘quasi-alliance.’ The three countries are tightening their cooperative relationships regarding security matters in the presence of a potential terrorism threat from North Korea. However, the trilateral cooperation demands measurements of weights that signify the importance of each country. Although Japan and South Korea have been protected under the nuclear umbrella of USA, the both countries have a certain geopolitical advantage in Far-East Asia. Therefore, this importance should be discussed in multi-criteria environments. This subject comes to the fore implicitly or explicitly whenever the bilateral or the trilateral cooperation demands burden-sharing for security maintenance. The burden includes government spending for military preparedness, basing, logistical support and others. In measuring the overall importance of each country in the bilateral or the trilateral relationship, it is absolutely essential to take into account multi-criteria regarding the relevant benefits and costs. The benefits include, among others: 1. Protection from external threat (North Korea). 2. Economic benefits achieved through the regional stability. 3. Political benefits. The costs include, among others: 1. 2. 3. 4.
Defense efforts. Supports for the US military presence. Military operational role (risk). Other duties and constraints associated with the alliance.
We can apply our DEA B–C game for this purpose, which is one of our intriguing future research subjects. As another example, we cite comparisons of cities by quality of life. The criteria for merits are represented by
146
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
such factors as: 1. 2. 3. 4. 5. 6.
Living space per householder. Educational expenses per student. Number of hospitals per population. Area of park per population. Number of libraries per population. Income per head.
5. Deletion of Assumption (A1) which leads to the Nash Bargaining problem. We hope this study contributes to opening a new field of research in game theory and data envelopment analysis, and provokes novel applications for resolution of social and political conflicts.
The criteria for demerits include:
Acknowledgements
1. 2. 3. 4.
We are grateful to the two anonymous referees and Professors Larry Seiford and Biresh Sahoo for their helpful comments and suggestions. This paper is supported by Grant-in-Aid for Scientific Research (C), Japan Society for Promotion of Science.
Pollution (emissions of CO2 and noise). Congestion (commuting time). Living expenses (level of prices). Crime (murder case per population).
Although many authors have analyzed this subject, e.g., the analytic hierarchy process approach by Saaty [11] and the DEA approach by Zhu [12], the DEA game approach will add a new dimension to this field.
6. Concluding remarks In this paper, we have introduced a societal dilemma called the ‘egoist’s dilemma’ and studied its properties by means of data envelopment analysis (DEA) and cooperative game theory. The DEA game thus defined has two variations, one the original selfish or bullish max game and the other the modest or bearish min game. As a special case of the linear production games of Owen [1], we also found that the DEA game has always a core. We have discussed imputations based on cooperative game theory, e.g., the Shapley value and the nucleolus. Specifically, we found that the Shapley value of the max game coincides with that of the min game. In Japan, a proverb says “Modesty (sympathy) is not merely for others’ sake,” reflecting wisdom of living. In this sense, the Shapley solution has a strong impact on consensus-making among participants in the game. Furthermore, we have studied the common weight issues that connect the game solution with the arbitrary weight selection behavior of the players. Regarding this subject, we have proposed a method for incorporating weight constraints to the game. Future research subjects include: 1. Studies on the relationship between the core and the Shapley value of the DEA game with five or more players. 2. The role of other imputations, e.g., the disruption nucleolus [13], the proportional nucleolus [14], the bargaining set [15] and the kernel [16]. 3. Types of coalition, e.g., partial coalition. 4. Introduction of the concept of economies of scale to the game, especially to the B–C game.
Appendix A. Proof of Proposition 14 We prove this proposition for the DEA min game case. Since the data matrix X is row-wise normalized, the grand coalition N has the program (11) as m
d(N) = min
i=1 m
s.t.
wi xi (N) =
m
wi
i=1
wi = 1,
wi 0(∀i).
(A.1)
i=1
Hence, d(N) = 1 for any w = (w1 , . . . , wm ) 0 with m i=1 wi = 1, i.e., any point in the simplex is optimal. For such a w, we define the vector z = (z1 , . . . , zn ) by zj = (wX)j =
m
wi xij
(j = 1, . . . , n).
(A.2)
i=1
For any coalition S, we have j ∈S
zj = =
m j ∈S i=1 m
wi xij =
wi xi (S).
m i=1
wi
j ∈S
xij (A.3)
i=1
Hence, it holds that zj = d(N) = 1.
(A.4)
j ∈N
Since d(S) is the minimum of the objective function in (11) and w is a feasible solution for (11), we have d(S)
m i=1
wi xi (S)
(A.5)
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
147
imputations m and mp() are defined respectively by (B.2) and (B.5) as follows:
and, by (A.3), zj d(S).
(A.6) m = (m1 , m2 , m3 , m4 ) = (d(1), d(1, 2) − d(1), d(1, 2, 3) − d(1, 2), 1 − d(1, 2, 3))
j ∈S
Thus, z(=wX) is an imputation in the core.
(B.7)
Appendix B.
and
Proposition B.1. The Shapley value of the DEA min game (N, d) with four players is included in the core.
mp() = (m1p() , m2p() , m3p() , m4p() ) = (d(1, 2) − d(2), d(2), 1 − d(1, 2, 4), d(1, 2, 4) − d(1, 2)). (B.8)
Proof. Let the four players be 1, 2, 3 and 4. Then we can define the Shapley value of the game (N, d) as follows: i (d) =
1 {d(S,i ∪ {i}) − d(S,i )} 4!
∈
(∀i ∈ {1, 2, 3, 4}),
(B.1)
where is the set of permutations of all players and S,i is the set of players preceding player i in the permutation. For a permutation, let mi be the marginal contribution of player i when the players form the grand coalition in the permutation, i.e., mi = d(S,i ∪ {i}) − d(S,i )
(∀i ∈ {1, 2, 3, 4}).
(B.2)
Let m be an imputation of the game (N, d) such that: m = (m1 , m2 , m3 , m4 ).
(B.3)
(m is an imputation because it satisfies the grand coalition rationality and also satisfies the individual rationality from the super-additivity of d(·).) Then we can define the Shapley value of the game (N, d) as follows: 1 (d) = (1 (d), 2 (d), 3 (d), 4 (d)) = m . (B.4) 4! ∈
Let p be a mapping such that: p: → ,
p() = p((1, 2, 3, 4)) = (2, 1, 4, 3).
(B.5)
Then obviously {} = {p()} = . Hence we can define the Shapley value of the game (N, d) as follows: (d) =
1 1 (m + mp() ). 2 4!
(B.6)
∈
If 21 (m +mp() )(∀ ∈ ) is included in the core, the Shapley value, which is a convex combination of 21 (m +mp() ), is included in the core because the core is also a convex set. The imputation 21 (m + mp() )(∀ ∈ ) satisfies the individual and grand coalition rationalities because both m and mp() satisfy them. For a permutation = (1, 2, 3, 4),
We can show that the imputation (1, 2, 3, 4)) satisfies the collective coalition as follows: Case B.1: The coalition {1, 2}
1 2 (m + mp() )( =
rationality for each
[m1 + m1p() ] + [m2 + m2p() ] = [d(1), d(1, 2) − d(2)] + [d(1, 2) − d(1) + d(2)] = 2d(1, 2). Case B.2: The coalition {1, 3} [m1 + m1p() ] + [m3 + m3p() ] = [d(1) + d(1, 2) − d(2)] + [d(1, 2, 3) − d(1, 2) + 1 − d(1, 2, 4)] = d(1) − d(1, 2, 4) + d(1, 2, 3) − d(2) + 1. From Corollary 2 and super-additivity of d(·), it holds that d(1)−d(1, 2, 4) d(1, 3)−1 and d(1, 2, 3)−d(2) d(1, 3), respectively. Hence we have [m1 + m1p() ] + [m3 + m3p() ] 2d(1, 3). For the three cases of the coalition {1, 4}, {2, 3} and {2, 4}, we can similarly confirm the collective rationality. Case B.3: The coalition {3, 4} [m3 + m3p() ] + [m4 + m4p() ] = [d(1, 2, 3) − d(1, 2) + 1 − d(1, 2, 4)] + [1 − d(1, 2, 3) + d(1, 2, 4) − d(1, 2)] = 2 − 2d(1, 2). From Proposition 7, it holds that 2 − 2d(1, 2) = 2c(3, 4). Hence we have [m3 + m3p() ] + [m4 + m4p() ] = 2c(3, 4) 2d(3, 4). Case B.4: The coalition {1, 2, 3} [m1 + m1p() ] + [m2 + m2p() ] + [m3 + m3p() ] = [d(1) + d(1, 2) − d(2)] + [d(1, 2) − d(1) + d(2)] + [d(1, 2, 3) − d(1, 2) + 1 − d(1, 2, 4)] = d(1, 2, 3) + d(1, 2) − d(1, 2, 4) + 1.
148
K. Nakabayashi, K. Tone / Omega 34 (2006) 135 – 148
From Corollary 2, it holds that d(1, 2) − d(1, 2, 4) d(1, 2, 3) − 1. Hence we have [m1 + m1p() ] + [m2 + m2p() ] + [m3 + m3p() ] 2d(1, 2, 3). For the case of the coalition {1, 2, 4}, we can similarly confirm the collective rationality. Case B.5: The coalition {1, 3, 4} [m1 + m1p() ] + [m3 + m3p() ] + [m4 + m4p() ] = [d(1) + d(1, 2) − d(2)] + [d(1, 2, 3) − d(1, 2) + 1 − d(1, 2, 4)] + [1 − d(1, 2, 3) + d(1, 2, 4) − d(1, 2)] = d(1) − d(1, 2) − d(2) + 2. From Corollary 2 and Proposition 7, it holds that d(1) − d(1, 2) d(1, 3, 4)−1 and d(2)=1−c(1, 3, 4), respectively. Hence we have [m1 + m1p() ] + [m3 + m3p() ] + [m4 + m4p() ] d(1, 3, 4) + c(1, 3, 4) 2d(1, 3, 4). For the case of the coalition {2, 3, 4}, we can similarly confirm the collective rationality. Thus, summing up, the imputation 21 (m + mp() )(∀ ∈ ) is included in the core because it satisfies the collective rationality in addition to the individual and grand coalition rationalities. Hence the Shapley value of the game (N, d) with four players is also included in the core.
References [1] Owen G. On the linear production games. Mathematical Programming 1975;9:358–70. [2] Charnes A, Cooper WW, Rhodes E. Measuring the efficiency of decision making units. European Journal of Operational Research 1978;2:429–44.
View publication stats
[3] Cooper WW, Seiford LM, Tone K. Data envelopment analysis—a comprehensive text with models, applications, references and DEA-solver software. Boston: Kluwer Academic Publishers; 1999. [4] Shapley LS. On balanced sets and cores. Naval Research Logistics Quarterly 1967;14:453–60. [5] Maschler M, Peleg B. The structure of the kernel of a cooperative game. SIAM Journal of Applied Mathematics 1967;15:569–604. [6] Thompson RG, Singleton Jr FD, Thrall RM, Smith BA. Comparative site evaluations for locating a high-energy physics lab in Texas. Interfaces 1986;16:35–49. [7] Dyson RG, Thanassoulis E. Reducing weight flexibility in data envelopment analysis. Journal of the Operational Research Society 1988;39:563–76. [8] Allen R, Athanassopoulas AD, Dyson RD, Thanassoulis E. Weights restrictions and value judgements in data envelopment analysis. Annals of Operations Research 1997;73:13–34. [9] Kim I, Hendry LC. Using DEA to assess NATO burden sharing. Journal of the Operational Research Society 1998;49:228–36. [10] Cha V. Alignment despite antagonism: the United States–Korea–Japan security triangle. Standford University Press; 1999. [11] Saaty TL. Absolute and relative measurement with the AHP. The most livable cities in the United States. Socio-Economic Planning Sciences 1986;20:327–31. [12] Zhu J. Multidimensional quality-of-life measure with an application to Fortune’s best cities. Socio-Economic Planning Sciences 2001;35:263–84. [13] Littlechild S, Vaidja K. The propensity to disrupt and disruption nucleolus of a characteristic function game. International Journal of Game Theory 1976;151–61. [14] Young H, Okada N, Hashimoto T. Cost allocation in water resources development. Water Resources Research 1981;18:463–75. [15] Aumann RJ, Maschler M. The bargaining set for cooperative games. In: Dresher M, Shapley LS, Tucker AW, editors. Advances in game theory, annals of mathematics studies series, vol. 39. Princeton, NJ: Princeton University Press; 1964. [16] Davis M, Maschler M. The kernel of the cooperative game. Naval Research Logistics Quarterly 1965;12:223–59.
