Nội dung

Yugoslav Journal of Operations Research 28 (2018), Number 2, 171-184 DOI: https://doi.org/10.2298/YJOR170918001L POWER ALLOCATION RULES UNDER MULTICRITERIA SITUATION Yu-Hsien LIAO Department of Applied Mathematics, National Pingtung University, Taiwan twincos@ms25.hinet.net Received: September 2017 / Accepted: January 2018 Abstract: Under multicriteria situations, we define a power mensuration rule and its efficient extension by applying maximal-utilities among level (decision) vectors. We also adopt some axiomatic results to present the rationalities for these two rules. Based on the notions of reduced game and excess function respectively, we introduce different formulation and dynamic results for the efficient extension. Keywords: Multicriteria Situation, Maximal-Utility, Reduced Game, Excess Function, Dynamic Process. MSC: 91A, 91B. 1. INTRODUCTION In the framework of transferable-utility (TU) games, the power indexes have been defined to measure the political power of each member of a voting system. A member in a voting system is, e.g., a party in a parliament or a country in a confederation. Each member will have a certain number of votes, and so its power will be different. Results of the power indexes may be found in, e.g., Dubey and Shapley [4], Haller [5], Lehrer [7], van den Brink and van der Laan [2] and so on. Banzhaf [1] defined a power index in the framework of voting games that was essentially identical to that given by Coleman [3]. This index was later on extended to arbitrary games by Owen [13, 14]. In this paper, we focus on the Banzhaf-Owen index. Briefly speaking, the Banzhaf-Owen index is a rule that gathers each member’s marginal contribution from all coalitions in which he/she/it has participated. Consistency is an important property among the axiomatic formulations for allocation rules. Consistency states the independence of a value with respect to 172 Y. H. Liao / Power Allocation Rules fixing some members with their assigned payoffs. It asserts that the recommendation made for any problem should always agree with the recommendation made in the subproblem that appears when the payoffs of some members are settled on. This property has been investigated in various problems by applying reduced games always. In addition to axiomatizations for an allocation rule, dynamic processes can be described that lead the members to that allocation rule, starting from an arbitrary efficient payoff vector. A multi-choice TU game could be regarded as a natural extension of a traditional TU game in which each member has various operational strategies (or decisions). By considering overall allocations for a given member on multi-choice TU games, Hwang and Liao [6], Liao [8, 9] and Nouweland et al. [12] proposed several extended allocations and related results for the core, the EANSC and the Shapley value [15], respectively. The above pre-existing results raise one motivation: • whether the power indexes could be extended under multi-choice behavior and multicriteria situation simultaneously. The paper is devoted to investigate the motivation. Different from the framework of multi-choice TU games, we consider the framework of multicriteria multi-choice TU games in Section 2. A power index and its efficient extension, the multichoice Banzhaf-Owen index and the multi-choice efficient Banzhaf-Owen index, are further proposed by applying maximal-utilities among level (decision) vectors on multicriteria multi-choice TU games. By applying an extended reduction, we propose some axiomatic results to present the rationalities for these two indexes in Section 3. In order to establish the dynamic processes, we present alternative formulation for the multi-choice efficient Banzhaf-Owen index in terms of excess functions. In Section 4, we adopt reduction and excess function to show that the multi-choice efficient Banzhaf-Owen index can be reached by members who start from an arbitrary efficient payoff vector. 2. PRELIMINARIES Let U be the universe of members. For i ∈ U and bi ∈ N, Bi = {0, 1, · · · , bi } could be treated as the level (decision) space of member i and B+i = Bi \ {0}, Q where 0 denotes no participation. Let BN = i∈N Bi be the product set of the level (decision) spaces of all members of N. For all T ⊆ N, we define θT ∈ BN is the vector with θTi = 1 if i ∈ T, and θTi = 0 if i ∈ N \ T. Denote 0N the zero vector in RN . For m ∈ N, let 0m be the zero vector in Rm and Nm = {1, · · · , m}. A multi-choice TU game is a triple (N, b, v), where N is a non-empty and finite set of members, b = (bi )i∈N is the vector that presents the highest levels for each member, and v : BN → R is a characteristic mapping with v(0N ) = 0 which assigns to each α = (αi )i∈N ∈ BN the worth that the members can gain when each member i participates at level αi . Given a multi-choice TU game (N, b, v) and α ∈ BN , we write A(α) = {i ∈ N| αi , 0} and αT to be the restriction of α at T for each T ⊆ N. Y. H. Liao / Power Allocation Rules 173 Further, we define v∗ (T) = maxα∈BN {v(α)|A(α) = T} is the maximal-utility among all action vector α with A(α) = T. A multicriteria multi-choice TU game is a triple (N, b, V m ), where m ∈ N, V m = (vt )t∈Nm and (N, b, vt ) is a multi-choice TU game for all t ∈ Nm . Denote the collection of all multicriteria multi-choice TU games by Γ. Let (N, b, V m ) ∈ Γ. A payoff vector of (N, b, V m ) is a vector x = (xt )t∈Nm and xt = (xti )i∈N ∈ RN , where xti denotes the payoff to member i in (N, b, vt ) for all t ∈ Nm and for all i ∈ N. A payoff vector x of (N, b, V m ) is multicriteria efficient if P t t i∈N xi = v∗ N for all t ∈ Nm . The collection of all multicriteria efficient vector of (N, b, V m ) is denoted by E(N, b, V m ). A solution is a map σ assigning to each (N, b, V m ) ∈ Γ an element      σ N, b, V m = σt N, b, V m , t∈Nm        where σt N, b, V m = σti N, b, V m ∈ RN and σti N, b, V m is the payoff of the i∈N   member i assigned by σ in N, b, vt . Next, we provide the multi-choice Banzhaf-Owen index and the multi-choice efficient Banzhaf-Owen index under multicriteria situation. Definition 1. The multi-choice Banzhaf-Owen index (MBOI), β, is defined by Xh i vt∗ (S) − vt∗ (S \ {i}) βti (N, b, V m ) = S⊆N i∈S for all (N, b, V ) ∈ Γ, for all t ∈ Nm and for all i ∈ N. Under the solution β, all members receive their marginal contributions related to maximal-utilities in each S ⊆ N respectively. m A solution σPsatisfies multicriteria efficiency (MEFF) if for all (N, b, V m ) ∈ Γ and for all t ∈ Nm , i∈N σi (N, b, V m ) = vt∗ (N). Property MEFF asserts that all members allocate all the utility completely. It is easy to check that the MBOI violates MEFF. Therefore, we consider an efficient normalization as follows. Definition 2. The multi-choice efficient Banzhaf-Owen index (MEBOI), β, is defined by βti (N, b, V m ) = βti (N, b, V m ) + X i 1 h t · v∗ (N) − βtk (N, b, V m ) |N| k∈N for all (N, b, V m ) ∈ Γ, for all t ∈ Nm and for all i ∈ N. Lemma 2.1. The MEBOI satisfies MEFF on Γ. From now on we consider bounded multi-choice TU games, defined as those games (N, b, v) such that, there exists Kv ∈ R such that v(α) ≤ Kv for all α ∈ BN . We adopt it to ensure that v∗ (T) is well-defined. Y. H. Liao / Power Allocation Rules 174 Proof. For all (N, b, V m ) ∈ Γ and for all t ∈ Nm , P = = = = βti (N, b, V m ) i∈N h ii h P t βk (N, b, V m ) · vt∗ (N) − i∈N k∈N i h P P t t βtk (N, b, V m ) · v (N) − βi (N, b, V m ) + |N| ∗ |N| i∈N P t P tk∈N βk (N, b, V m ) βi (N, b, V m ) + vt∗ (N) − P βti (N, b, V m ) + i∈N vt∗ (N). 1 |N| k∈N Thus, the MEBOI satisfies MEFF on Γ. Here we provide a brief application of multicriteria multi-choice TU games in the setting of “management”. This kind of problem can be formulated as follows. Let N = {1, 2, · · · , n} be a set of all members of a grand management system (N, b, V m ). The function vt could be treated as an utility function which assigns to each level vector α = (αi )i∈N ∈ BN the value that the members can obtain when each member i participates at operation strategy αi ∈ Bi in the sub-management system (N, b, vt ). Modeled in this way, the grand management system (N, b, V m ) could be considered as a multicriteria multi-choice TU game, with vt being each characteristic function and Bi being the set of all operation strategies of the member i. In the following sections, we show that the MBOI and the MEBOI could provide “optimal allocation mechanisms” among all members, in the sense that this organization can get payoff from each combination of operation strategies of all members under multi-choice behavior and multicriteria situation. 3. AXIOMATIZATIONS In this section, we show that there exists corresponding reduced games that could be adopted to analyze the MBOI and the MEBOI. Subsequently, we introduce a reduced game and the related consistency as follows. Let ψ be a solution, (N, b, V m ) ∈ Γ and S ⊆ N. The 1-reduced game 1,m 1,m (S, bS , VS,ψ ) is defined by VS,ψ = (v1,t ) and S,ψ t∈Nm  P i  P h  t t m  v A(α) ∪ Q − ψ (N, b, V ) otherwise,  ∗  i i∈Q Q⊆N\S v1,t (α) =   S,ψ  0 if α = 0S . 1,m ψ satisfies 1-consistency (1CON) if ψti (S, bS , VS,ψ ) = ψti (N, b, V m ) for all (N, b, V m ) ∈ Γ, for all S ⊆ N with |S| = 2, for all t ∈ Nm and for all i ∈ S. Further, ψ satisfies 1-standard for games (1SG) if ψ(N, b, V m ) = β(N, b, V m ) for all (N, b, V m ) ∈ Γ with |N| ≤ 2. Next, we characterize the MBOI by applying the properties of 1CON and 1SG. Y. H. Liao / Power Allocation Rules 175 Lemma 3.1. 1. The MBOI satisfies 1CON on Γ. 2. On Γ, the MBOI is the only solution satisfying 1SG and 1CON. Proof. To prove result 1, let (N, b, V m ) ∈ Γ and S ⊆ N. If |N| = 1, then the proof is completed. Assume that |N| ≥ 2 and S = {i, j} for some i, j ∈ N. For all t ∈ Nm and for all i ∈ S, i P h 1,t 1,m ) (T \ {i}) (vS,β )∗ (T) − (v1,t ) = βti (S, bS , VS,β ∗ S,β T⊆S i∈T = i P P h t v∗ (T ∪ Q) − vt∗ (T \ {i} ∪ Q) T⊆S i∈T = Q⊆N\S Ph v(K) − v(K \ {i}) i K⊆N i∈K = βti (N, b, V m ). Hence, β satisfies 1CON. By result 1, β satisfies 1CON on Γ. Clearly, β satisfies 1SG on Γ. To prove uniqueness of result 2, suppose ψ satisfies 1SG and 1CON. Let (N, b, v) ∈ Γ. If |N| ≤ 2, then ψ(N, b, v) = β(N, b, v) by 1SG. The case |N| > 2: Let i ∈ N and t ∈ Nm , and let S ⊂ N with |S| = 2 and i ∈ S. Then, ψti (N, b, V m ) 1,m ) = ψti (S, bS , VS,ψ = = = = 1,m βti (S, bS , VS,ψ ) i P h 1,t (vS,ψ )∗ (T) − (v1,t ) (T \ {i}) S,ψ ∗ T⊆S i∈T  P P [vt∗ (T ∪ Q) − vt∗ (T \ {i}) T⊆S Q⊆N\S i∈T P t v∗ (K) − vt∗ (K \ {i}) (by 1CON) (by 1SG)  ∪Q ] K⊆N i∈K = βti (N, b, V m ). Thus, ψ(N, b, V m ) = β(N, b, V m ). The following examples are to show that each of the axioms adopted in Lemma 2 is logically independent of the remaining axioms. Example 3.2. Define a solution ψ by for all (N, b, V m ) ∈ Γ, for all t ∈ Nm and for all i ∈ N, ψti (N, b, V m ) = 0. Clearly, ψ satisfies 1CON, but it violates 1SG. Example 3.3. Define a solution ψ by for all (N, b, V m ) ∈ Γ, for all t ∈ Nm and for all i ∈ N, ( t βi (N, b, V m ) if |N| ≤ 2, t m ψi (N, b, V ) = 0 otherwise. Y. H. Liao / Power Allocation Rules 176 On Γ, ψ satisfies 1SG, but it violates 1CON. It is easy to check that the index β violates 1CON. Therefore, we consider the 2-reduced game as follows. Let ψ be a solution, (N, b, V m ) ∈ Γ and S ⊆ N. The 2,m 2,m ) = (v2,t and ) is defined by VS,ψ 2-reduced game (S, bS , VS,ψ S,ψ t∈Nm   0 if α = 0S ,   P t  t m  v (N) − ψ (N, b, V ) if A(α) = S,  ∗  i (α) =  v2,t h i∈N\S   P i  S,ψ P    vt∗ A(α) ∪ Q − ψti (N, b, V m ) otherwise.   i∈Q Q⊆N\S 2,m ψ satisfies 2-consistency (2CON) if ψti (S, bS , VS,ψ ) = ψti (N, b, V m ) for all (N, b, V m ) ∈ Γ, for all S ⊆ N with |S| = 2, for all t ∈ Nm and for all i ∈ S. Further, ψ satisfies 2-standard for games (2SG) if ψ(N, b, V m ) = β(N, b, V m ) for all (N, b, V m ) ∈ Γ with |N| ≤ 2. Next, we characterize the MEBOI by applying the properties of 2CON and 2SG. In order to establish consistency of the MEBOI, it will be useful to present m alternative formulation for the MEBOI in terms of excess. Let P(N, b, V ) ∈ Γ, S ⊆ N and x be a payoff vector in (N, b, V m ). Define that xt (S) = i∈S xti for all t ∈ Nm . The excess of a coalition S ⊆ N at x is the real number e(S, V m , x) = (e(S, vt , xt ))t∈Nm and e(S, vt , xt ) = vt∗ (S) − xt (S). (1) The value e(S, vt , xt ) can be treated as the complaint of coalition S when all members receive their payoffs from xt in (N, b, vt ). Lemma 3.4. Let (N, b, V m ) ∈ Γ and x ∈ E(N, b, V m ). Then, for all i, j ∈ N and t ∈ Nm P P xt xt e(S ∪ {i}, vt , 2|N|−1 )= e(S ∪ { j}, vt , 2|N|−1 ) S⊆N\{i, j} S⊆N\{i, j} ⇐⇒ x = β(N, b, V m ). Proof. Let (N, b, V m ) ∈ Γ and x ∈ E(N, b, V m ). For all t ∈ Nm and for all i, j ∈ N, P P xt xt e(S ∪ {i}, vt , 2|N|−1 )= ) e(S ∪ { j}, vt , 2|N|−1 S⊆N\{i, j} S⊆N\{i, j}   i P h t P xt (S∪{j}) xt (S∪{i}) ⇐⇒ v∗ (S ∪ {i}) − 2|N|−1 = vt∗ (S ∪ { j}) − 2|N|−1 S⊆N\{i, j} S⊆N\{i, j}    (2) t  P    xt P  xi  t t  ⇐⇒  v∗ (S ∪ {i}) − 2 =  v∗ (S ∪ { j}) − 2j S⊆N\{i, j} S⊆N\{i, j} i P h t t t ⇐⇒ xi − x j = 2 · v∗ (S ∪ {i}) − vt∗ (S ∪ { j}) . S⊆N\{i, j} By definition of β, βti (N, b, V m ) − βtj (N, b, V m ) = 2 · P S⊆N\{i, j} h vt∗ (S ∪ {i}) − vt∗ (S ∪ { j}) i (3) Y. H. Liao / Power Allocation Rules 177 By equations (2) and (3), for all i, j ∈ N, xti − xtj = βti (N, b, V m ) − βtj (N, b, V m ). Hence, Xh i i Xh xti − xtj = βti (N, b, V m ) − βtj (N, b, V m ) . j∈N j∈N That is, |N| · xti − P j∈N xtj = |N| · βti (N, b, V m ) − P j∈N βtj (N, b, V m ). Since x ∈ E(N, b, V m ) and β satisfies MEFF, |N| · xti − vt∗ (N) = |N| · βti (N, b, V m ) − vt∗ (N). Therefore, xti = βti (N, b, V m ) for all t ∈ Nm and for all i ∈ N, i.e., x = β(N, b, V m ). Remark 1. It is easy to check that X e(S \ {i}, V m , β(N, b, V m )) = S⊆N\{i,j} X e(S \ { j}, V m , β(N, b, V m )) S⊆N\{i, j} for all (N, b, V m ) ∈ Γ and for all i, j ∈ N. Theorem 1. 1. The MEBOI satisfies 2CON on Γ. 2. If ψ satisfies 2SG and 2CON, then it also satisfies MEFF. 3. On Γ, the MEBOI is the only solution satisfying 2SG and 2CON. Proof. To verify result 1, let (N, b, V m ) ∈ Γ and S ⊆ N. If |N| = 1, then the proof is completed. Assume that|N| ≥ 2, x = β(N, b, V m ) and S = {i, j} for some i, j ∈ N. For all t ∈ Nm and for all l ∈ S, P  xtS  , e T ∪ {l}, v2,t |S|−1 S,x 2 T⊆S\{i,j}  t  x = e {l}, v2,t , S S,x 2 = = = = = = = = xt v2,t ({l}) − l  S,xP h 2 P t i xtl xk − 2 vt∗ ({l} ∪ Q) − Q⊆N\S k∈Q P h t P t xtl i v∗ ({l} ∪ Q) − xk − 2·2|N\S| Q⊆N\S k∈Q P h t P t xtl i v∗ ({l} ∪ Q) − xk − 2|N|−1 Q⊆N\S k∈Q P h t P t P xtk P xtk xtl i v∗ ({l} ∪ Q) − xk + − − |N|−1 |N|−1 |N|−1 2 2 2 Q⊆N\S k∈Q k∈Q k∈Q  t i P P h t P x 1 k v∗ ({l} ∪ Q) − 1 − 2|N|−1 xtk − 2|N|−1 Q⊆N\S k∈Q k∈Q∪{ł}  P  i P h x 1 e {l} ∪ Q, vt , 2|N|−1 − 1 − 2|N|−1 xtk Q⊆N\S  k∈Q   P P P 1 x e {l} ∪ Q, vt , 2|N|−1 − 1 − 2|N|−1 xtk . Q⊆N\S Q⊆N\S k∈Q (4) Y. H. Liao / Power Allocation Rules 178 ) by definition of 2-reduced game. In Since β satisfies MEFF, xtS ∈ E(S, bS , v2,t S,x addition, by equation (4) and Lemma 3,   e {i}, v2,t , xtS S,x   P  P P x 1 = e {i} ∪ Q, vt , 2|N|−1 1 − 2|N|−1 − xtk (by equation (4)) Q⊆N\S  Q⊆N\S k∈Q   P P P x 1 = e { j} ∪ Q, vt , 2|N|−1 1 − 2|N|−1 − xtk (by Lemma 3) Q⊆N\S Q⊆N\S k∈Q   t , x . (by equation (4)) = e { j}, v2,t S,x S So, xS = β(S, bS , V 2,m ). That is, β satisfies 2CON. S,β To prove result 2, suppose ψ satisfies 2SG and 2CON. Let (N, b, V m ) ∈ Γ and t ∈ Nm . If |N| ≤ 2, it is trivial that ψ satisfies MEFF by 2SG. The case |N| > 2: Assume, on the contrary, that there exists (N, b, V m ) ∈ Γ such that P t m t This means that there exist i ∈ N and j ∈ N such i∈N ψi (N, b, V P ) , v∗ (N). t that [v∗ (N) − k∈N\{i, j} ψtk (N, b, V m )] , [ψti (N, b, V m ) + ψtj (N, b, V m )]. By 2CON and ψ satisfies MEFF for two-person games, this contradicts with ψti (N, b, V m ) + ψtj (N, b, V m ) = ψti ({i, j}, b{i, j} , v2,t ) + ψtj ({i, j}, b{i,j} , v2,t ) {i, j},ψ {i, j},ψ P ψtk (N, b, V m ). = vt∗ (N) − k∈N\{i, j} Hence, ψ satisfies MEFF. To prove result 3, β satisfies 2CON by result 1. Clearly, β satisfies 2SG. To prove uniqueness, suppose ψ satisfies 2SG and 2CON, hence by result 2, ψ also satisfies MEFF. Let (N, b, V m ) ∈ Γ. If |N| ≤ 2, it is trivial that ψ(N, b, V m ) = β(N, b, V m ) by 2SG. The case |N| > 2: Let i ∈ N, t ∈ Nm and S = {i, j} for some j ∈ N \ {i}. Then = = = ψti (N, b, V m ) − βti (N, b, V m ) 2,m ψti (S, bS , VS,ψ ) − βti (S, bS , V 2,m ) S,β 2,m βti (S, bS , VS,ψ ) − βti (S, bS , V 2,m ) S,β i h 2,t 2,t 2,t 1 ) ({ j}) · (v ) (S) + (v ) ({i}) − (v ∗ ∗ ∗ 2 S,ψ S,ψ i h S,ψ − 21 · (v2,t )∗ (S) + (v2,t )∗ ({i}) − (v2,t )∗ ({j}) . S,β S,β S,β (by 2CON of ψ, β) (by 2SG of ψ, β) (5) By definitions of v2,t and v2,t , S,ψ S,β (v2,t ) ({i}) − (v2,t ) ({ j}) = S,ψ ∗ S,ψ ∗ 1 2|N\S| · i P h t v∗ ({i} ∪ Q) − vt∗ ({ j} ∪ Q) Q⊆N\S = (v2,t )∗ ({i}) − (v2,t )∗ ({ j}). S,β S,β (6) Y. H. Liao / Power Allocation Rules 179 By equation (6), equation (5) becomes = = ψti (N, b, V m ) − βti (N, b, V m )   2,t 2,t 1 2 · (vS,ψ )∗ (S) − (vS,βt )∗ (S)   1 t m t m m m t t 2 · ψi (N, b, V ) + ψ j (N, b, V ) − βi (N, b, V ) + β j (N, b, V ) . That is, ψti (N, b, V m ) − ψtj (N, b, V m ) = βti (N, b, V m ) − βtj (N, b, V m ) for all i, j ∈ N. By MEFF of ψ and β, |N| · ψti (N, b, V m ) − vt∗ (N) = |N| · βti (N, b, V m ) − vt∗ (N). Thus, ψti (N, b, V m ) = βti (N, b, V m ) for all i ∈ N, i.e., ψ(N, b, V m ) = β(N, b, V m ). The following examples are to show that each of the axioms adopted in Theorem 1 is logically independent of the remaining axioms. Example 3.5. Define a solution ψ by for all (N, b, V m ) ∈ Γ, for all t ∈ Nm and for all i ∈ N, ψti (N, b, V m ) = 0. Clearly, ψ satisfies 2CON, but it violates 2SG. Example 3.6. Define a solution ψ by for all (N, b, V m ) ∈ Γ, for all t ∈ Nm and for all i ∈ N, ( βti (N, b, V m ) if |N| ≤ 2, t m ψi (N, b, V ) = 0 otherwise. On Γ, ψ satisfies 2SG, but it violates 2CON. 4. DYNAMIC PROCESSES In this section, we adopt excess function and reduction to propose dynamic processes for the MEBOI. In order to establish the dynamic processes of the MEBOI, we firstly define correction function by means of excess functions. The correction function is based on the idea that each member shortens the complaint relating to his own and others’ nonparticipation, and adopts these regulations to correct the original payoff. Definition 3. Let (N, b, V m ) ∈ Γ and i ∈ N. The correction function is defined to be f = ( f t )t∈Nm , where f t = ( fit )i∈N and fit : E(N, b, V m ) → R is define by fit (x) = xti + w X X h j∈N\{i} Q⊆N\{i, j} e(Q \ { j}, vt , xt 2 ) − e(Q \ {i}, vt , |N|−1 xt i ) , 2|N|−1 Y. H. Liao / Power Allocation Rules 180 where w ∈ R is a fixed postive number, which reflects the assumption that member i does not ask for full correction (when w = 1) but only (usually) a fraction of it. Define [x]0 = x, [x]1 = f ([x]0 ), · · · , [x]q = f ([x]q−1 ) for all q ∈ N. Lemma 4.1. f (x) ∈ E(N, b, V m ) for all (N, b, V m ) ∈ Γ and for all x ∈ E(N, b, V m ). Proof. Let (N, b, V m ) ∈ Γ, t ∈ Nm , i, j ∈ N and x ∈ E(N, b, V m ). Similar to equation (2), i P P h xt xt ) − e(Q \ {i}, vt , 2|N|−1 ) e(Q \ { j}, vt , 2|N|−1 j∈N\{i} Q⊆N\{i, j} = P h j∈N\{i} P h i vt (Q \ { j}) − vt (Q \ {i}) − Q⊆N\{i, j} xti 2 + xtj i 2 . (7) By definition of β, βti (N, b, V m ) − βtj (N, b, V m ) = 2 X h i vt (Q \ { j}) − vt (Q \ {i}) . (8) Q⊆N\{i, j} By equations (7) and (8), = h i xt xt e(Q \ { j}, vt , 2|N|−1 ) − e(Q \ {i}, vt , 2|N|−1 ) j∈N\{i} Q⊆N\{i, j}  P  t 1 βi (N, b, V m ) − βtj (N, b, V m ) − xti + xtj 2 · j∈N\{i}   P t P t 1 · (|N| − 1) βti (N, b, V m ) − xti − β j (N, b, V m ) + xj 2 j∈N\{i} j∈N\{i}     1 m t t t t 2 · |N| βi (N, b, V ) − xi − v∗ (N) + v∗ (N) = |N| 2 P = = P (9) m  (by MEFF of β, x ∈ E(N, b, V )) · βti (N, b, V m ) − xti .  Moreover, = = = = h i e(Q \ { j}, vt , xt ) − e(Q \ {i}, vt , xt ) i∈N j∈N\{i} Q⊆N\{i, j}  P |N|  t m t 2 · βi (N, b, V ) − xi i∈N  P t P t |N| βi (N, b, V m ) − xi 2 · i∈N i∈N     |N| t t m 2 · v∗ (N) − v∗ (N) by MEFF of β, x ∈ E(N, b, V ) 0. P P P (10)