GAMES AND ECONOMIC BEHAVIOR12,42–53(1996)
ARTICLE NO.0003
The Owen Value Applied to Games with
Graph-Restricted Communication*
M ARGARITA V AZQUEZ-B RAGE
Department of Statistics and OR,Uni v ersity of Vigo,36271Vigo(Ponte v edra),Spain
I GNACIO G ARCIA-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,
08走向海洋
222Terrassa(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 t 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
Copyright1996by Academic Press,Inc.
All rights of reproduction in any form rerved.
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(e,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 l蓝铃花的花语
ink of which indicates
direct cooperative communication between the players reprented by the
nodes at each end.Since then,games with graph-restricted communication
have been widely studied;for a review e Borm et al.(1991).In political
situations,the communication links can be viewed as political affinities
between players.
In this paper we propo 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
4),both affect the bargaining positions of the players and hence thefinal
allocation of utility among them.
The paper is organized as follows.In Section2we announce notation
and preliminary definitions and state Owen’s(1977)theorem,in Section3
we prent two ts 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 t of players and v,the characteristic
function,is a real function on2N{SSN}with v()0.We denote by G(N)the t of TU games with player t N,identify(N,v)G(N)
with its characteristic function v when no confusion will be caud,and for
every vG(N)write⌽(v)for its Shapley value.
An undirected graph without loops on N is a(possibly empty)t B of
unordered pairs of distinct elements of N.We c那一刻我长大了作文500字
all the pairs(i,j)B links.
We denote by g(N)the t of all undirected graphs without loops on N
and by B N the complete graph on N defined by B N{(i,j)iN,jN, ij}.For any SN and any Bg(N)we say that i,jS 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 t of connecte土豆长芽了还能吃吗
d components of S determined by B ,i.e.,the t of maximal subts of elements connected in S by B .S /B is a partition of S .For any t T ,we denote by P (T )the t of partitions of T .
A TU game with a system of unions and t of players N is a pair (v ,P ),where v G (N )and P P (N ).We denote by U (N )the t 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 ⌿e 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 t 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)TS/B v(T),᭙SN.
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 vG(N) and all PP(N);and(v,B,P)⌽(v B)(the Myerson value of(v,B)) if P{N}or P{{1},...,{n}},for all vG(N)and all Bg(N).Hence can be considered as generalizing the Owen and Myerson values.
Given P{P1,...,P m}P(N),P k,P sP,iP k and Bg(N),we define PiP(N)by Pi{P1,...,P k1,P k{i},P k1,...,P m,{i}};Big(N)by Bi{(j,k)Bji,ki};and B(P k,P s)g(N)by B(P k, P s)B{(i,j)BiP k,jP s}.
We asrt thathas the followi每日晨读
ng properties for all(v,B,P)S(N).
1.Component Efficiency(CE):for all TN/B,
i(v,B,P)v(T);
iT
<,the total worth of every connected component in N is distributed among its members.
2.Balanced Contributions for the Graph(BCG):for all P kP and all i,jP k,
i(v,B,P)i(v,Bj,P)j(v,B,P)j(v,Bi,P);
<,if i and j are in same union,each los(or gains)the same amount if the other i狗一直叫
s isolated.A similar property holds for the Myerson value(Myer-son,1980;van den Nouweland,1993).
46VAZQUEZ-BRAGE,GARCIA-JURADO,AND CARRERAS
3.Balanced Contributions for the Unions(BCU):for all P kP and all i,jP k,
i(v,B,P)i(v,B,Pj)j(v,B,P)j(v,B,Pi);
<,if i and j are in same union,each los(or gains)the same amount if the other leaves the union.
4.Fairness in the Quotient(FQ):for all P教师奉献精神
k,P sP,
i(v,B,P)iP ki(v,B(P k,P s),P)
iP k
iP si(v,B,P)iP si(v,B(P k,P s),P);
<,each of two unions los(or gains)the same amount as the other when all the links joining them are vered.
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 Aragon,one of the Spain’s venteen 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 reprentation is unity for any party or coalition summing34members,and zero for the rest.Following elections in1991, the parliament was compod of30members of the socialist party PSOE, 17members of the conrvative 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 the parties can quite plausibly be reprented 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 the coalitions are connected under the
affinities graph.
