GAMES AND ECONOMIC BEHAVIOR12,42–53(1996)
ARTICLE NO.0003
The Owen Value Applied to Games with
Graph-Restricted Communication*
M ARGARITA V A´ZQUEZ-B RAGE
Department of Statistics and OR,Uni v ersity of Vigo,36271Vigo(Ponte v edra),Spain
I GNACIO G ARCI´A-J URADO
Department of Statistics and OR,Uni v ersity of Santiago,
15771Santiago de Compostela,Spain
AND
F RANCESC C ARRERAS
Department of Applied Mathematics,Polytechnic Uni v ersity of Catalunya,
采访麦克风
08222Terrassa(Barcelona),Spain
Received May4,1993
We introduce an allocation rule for transferable utility games with graph-restricted
communication and a priori unions,provide two characterizations of this rule,and
apply it to the analysis of a real political example.Journal of Economic Literature
Classification Numbers:000,020,026.©1996Academic Press,Inc.
1.I NTRODUCTION
The Owen value was introduced by Owen(1977)as a modification of the Shapley value(Shapley,1953)for n-person cooperative games with transferable utility(TU games)with systems of unions,a system of unions being a partition of the set of players which describes its a priori cooperation structure.The Owen value allocates the total utility among the unions as *We thank the
University of Santiago and the Xunta de Galicia forfinancial support through Projects60902.25064(5060),XUGA20701B91,and XUGA20702B93.
42
0899-8256/96$12.00
Copyright©1996by Academic Press,Inc.
All rights of reproduction in any form reserved.
OWEN VALUE IN GRAPH-RESTRICTED GAMES43 the Shapley value of the induced TU game played by the unions and within
each union allocates its allotted utility among its members taking into
account their possibilities of entering other unions.The formation of politi-
cal coalitions has been analyzed by comparing the Owen values resulting
from various possible union structures(see,for instance,Carreras and
Owen,1988and1991).
The Myerson value(Myerson,1977)can be interpreted as a modification
of the Shapley value for TU games in which communication among the
players is restricted by an undirected graph,each link of which indicates
direct cooperative communication between the players represented by the
nodes at each end.Since then,games with graph-restricted communication
have been widely studied;for a review see Borm et al.(1991).In political
situations,the communication links can be viewed as political affinities
between players.
In this paper we propose an allocation rule for TU games with both
graph-restricted communication and systems of unions.The partition given
by the system of unions and the partition defined by the connected compo-
nents of the communication graph,which can both appear naturally in
many political and economic situations(we show an example in Section
gcr15
热处理工艺4),both affect the bargaining positions of the players and hence thefinal
allocation of utility among them.flash测试
The paper is organized as follows.In Section2we announce notation
and preliminary definitions and state Owen’s(1977)theorem,in Section3
we present two sets of fairness and efficiency conditions characterizing our
allocation rule,in Section4we apply our rule to a real political situation
by considering its outcome for two plausible union structures on a given
graph of political affinities,and in Section5we prove the results stated in
Section3.
2.P RELIMINARIES
An n-person cooperati v e game with transferable utility(a TU game)is a
pair(N,v),where Nϭ{1,...,n}is the set of players and v,the characteristic
function,is a real function on2Nϭ{S͉SʚN}with v(л)ϭ0.We denote by G(N)the set of TU games with player set N,identify(N,v)ʦG(N)
with its characteristic function v when no confusion will be caused,and for
every vʦG(N)write⌽(v)for its Shapley value.
An undirected graph without loops on N is a(possibly empty)set B of
unordered pairs of distinct elements of N.We call the pairs(i,j)ʦB links.
We denote by g(N)the set of all undirected graphs without loops on N
and by B N the complete graph on N defined by B Nϭ{(i,j)͉iʦN,jʦN, i϶j}.For any SʚN and any Bʦg(N)we say that i,jʦS are connected
44VA
´ZQUEZ-BRAGE,GARCI ´A-JURADO,AND CARRERAS in S by B if B contains a path in S connecting i and j ,and we denote by S /B the set of connected components of S determined by B ,i.e.,the set of maximal subsets of elements connected in S by B .S /B is a partition of S .For any set T ,we denote by P (T )the set of partitions of T .
A TU game with a system of unions and set of players N is a pair (v ,P ),where v ʦG (N )and P ʦP (N ).We denote by U (N )the set of all such pairs.If (v ,P )ʦU (N ),with P ϭ{P i ͉i ʦM ϭ{1,...,m }},the quotient game v P is the TU game in G (M )defined by
v P (R )ϭv (ʜk ʦR P k ),
᭙R ʚM .It is the TU game played by the unions.
T HEOREM 1(Owen,1977).There exists a unique map ⌿:U (N )Ǟޒn with the following properties .
1.The Carrier Property (CP ):for all (v ,P )ʦU (N ),if T is a carrier of v (i.e.,if v (S )ϭv (S ʝT ),᭙S ʚN ),then ͚i ʦT ⌿i (v ,P )ϭv (T ).
2.Symmetry in the Unions (SU):for all (v ,P )ʦU (N ),all P k ʦP ,and all i ,j ʦP k ,if v (S ʜi )ϭv (S ʜj )for all S ʚN گ{i ,j },then ⌿i (v ,P )ϭ⌿j (v ,P ).
3.Symmetry in the Quotient (SQ ):for all (v ,P )ʦU (N )and all P k ,P s ʦP ϭ{P 1,...,P m },if v P (R ʜk )ϭv P (R ʜs )for all R ʚM گ{k ,s },then ͚i ʦP k ⌿i (v ,P )ϭ͚i ʦP s ⌿i (v ,P ).
4.Additi v ity (A ):for all (v ,P ),(w ,P )ʦU (N ),⌿(v ϩw ,P )ϭ⌿(v ,P )ϩ⌿(w ,P ).
This unique map is gi v en by the formula
⌿i (v ,P )
ϭR ʚM گ{k }
T ʚP k گ{i }
t !(p k Ϫt Ϫ1)!r !(m Ϫr Ϫ1)!p k !m !(v (Q ʜT ʜi )Ϫv (Q ʜT )),(1)where P k ʦP is the union containing i ,Q ϭʜr ʦR P r ,and p k ,t ,and r are the cardinalities of P k ,T ,and R ,respecti v ely .
We call ⌿i (v ,P )the Owen value of i in (v ,P ).For other characterizations of ⌿see Winter (1992).
A graph-restricted n-person TU game with a system of unions is a triplet (v ,
B ,P ),where v ʦG (N ),B ʦg (N ),and P ʦP (N ).The graph B describes fixed interplayer communication possibilities,the partition P ϭ{P 1,...,
OWEN VALUE IN GRAPH-RESTRICTED GAMES45 P m}a union structure.We denote by S(N)the set of all such triplets(for afixed N).Given(v,B,P)ʦS(N),the graph-restricted game v B is defined by
v B(S)ϭTʦS/B v(T),᭙SʚN.
An allocation rule for graph-restricted games with systems of unions is a map:S(N)Ǟޒn.
智能美甲3.A N A LLOCATION R ULE FOR G RAPH-R ESTRICTED G AMES WITH
S YSTEMS OF U NIONS
Given(v,B,P)ʦS(N),we define(v,B,P)as the Owen value of the graph-restricted game v B:包边角钢
(v,B,P)ϭ⌿(v B,P),᭙(v,B,P)ʦS(N).
Note that,as one might expect,(v,B N,P)ϭ⌿(v,P),for all vʦG(N) and all PʦP(N);and(v,B,P)ϭ⌽(v B)(the Myerson value of(v,B)) if Pϭ{N}or Pϭ{{1},...,{n}},for all vʦG(N)and all Bʦg(N).Hence can be considered as generalizing the Owen and Myerson values.
Given Pϭ{P1,...,P m}ʦP(N),P k,P sʦP,iʦP k and Bʦg(N),we define PϪiʦP(N)by PϪiϭ{P1,...,P kϪ1,P kگ{i},P kϩ1,...,P m,{i}};BϪiʦg(N)by BϪiϭ{(j,k)ʦB͉j϶i,k϶i};and Bگ(P k,P s)ʦg(N)by Bگ(P k, P s)ϭBگ{(i,j)ʦB͉iʦP k,jʦP s}.
We assert thathas the following properties for all(v,B,P)ʦS(N).
1.Component Efficiency(CE):for all TʦN/B,
i(v,B,P)ϭv(T);
iʦT
<,the total worth of every connected component in N is distributed among its members.
2.Balanced Contributions for the Graph(BCG):for all P kʦP and all i,jʦP k,
i(v,B,P)Ϫi(v,BϪj,P)ϭj(v,B,P)Ϫj(v,BϪi,P);
<,if i and j are in same union,each loses(or gains)the same amount if the other is isolated.A similar property holds for the Myerson value(Myer-son,1980;van den Nouweland,1993).
46VA´ZQUEZ-BRAGE,GARCI´A-JURADO,AND CARRERAS
3.Balanced Contributions for the Unions(BCU):for all P kʦP and all i,jʦP k,
i(v,B,P)Ϫi(v,B,PϪj)ϭj(v,B,P)Ϫj(v,B,PϪi);
<,if i and j are in same union,each loses(or gains)the same amount if the other leaves the union.
4.Fairness in the Quotient(FQ):for all P k,P sʦP,
i(v,B,P)ϪiʦP ki(v,Bگ(P k,P s),P)
iʦP k
ϭiʦP si(v,B,P)ϪiʦP si(v,Bگ(P k,P s),P);
<,each of two unions loses(or gains)the same amount as the other when all the links joining them are severed.
仿真人T HEOREM2.There is a unique allocation rule satisfying CE,BCG,and FQ,and it is.
T HEOREM3.There is a unique allocation rule satisfying CE,BCU,and FQ,and it also is.
4.A P OLITICAL E XAMPLE
The Parliament of Arago´n,one of the Spain’s seventeen autonomous communities,is constituted by67members.Since most decisions are taken by majority rule,the characteristic function of the game played by the parties with parliamentary representation is unity for any party or coalition summing34members,and zero for the rest.Following elections in1991, the parliament was composed of30members of the socialist party PSOE, 17members of the conservative PP,17members of the middle-of-the-road regionalist party PAR,and3members of IU,a coalition of communists and other left-wing parties.The affinities among these parties can quite plausibly be represented by a graph B consisting of just three links:(PP, PAR),(PAR,PSOE),and(PSOE,IU).Given the election results,there were just three minimal coalitions of nonzero ,with enough elected deputies to be able to govern:{PP,PAR},{PAR,PSOE},and{PP, PSOE}.Only two of these coalitions are connected under the
affinities graph.
