(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "A note on cooperative games with varying power"

UNIVERSITY OF 

ILLINOIS LIBRARY 

AT URBANA-CHAMPAIGN 

BOOKSTACKS 



Digitized by the Internet Archive 

in 2012 with funding from 

University of Illinois Urbana-Champaign 



http://www.archive.org/details/noteoncooperativ269roth 



Faculty Working Papers 



A NOTE ON COOPERATIVE GAMES 
WITH VARYING POWER 

Alvin E. Roth 



#269 



College of Commerce and Business Administration 

University of Illinois at Urbana-Champaign 



FACULTY WORKING PAPERS 
College of Commerce and Business Administration 
University of Illinois at Urbana-Champaign 
September 12, 1975 



A NOTE ON COOPERATIVE GAMES 
WITH VARYING POWER 

Alvin E. Roth 



//269 



This work was supported in part by a grant from the Illinois 
Business Associates. 



- 



A Note on Cooperative Games with Varying Power 



by 



Alvin E. Roth 



1. 

The purpose of this note is to consider some, properties of cooperative 
games in which the power of coalitions is dependent on their wealth. In par- 
ticular, we will want to investigate repeated play of such games, in which 
the outcome of earlier plays of the game determines the wealth, and thus the 
power, of coalitions in subsequent plays of the game. 

Non-cooperative games in which power is dependent on previous plays of 
the game have been introduced by Oskar Morgenstern (1972), and called power 
games . We shall use the same name in our discussion, it being understood 
that we speak here of cooperative games. 

Games in which power depends on wealth arise in a natural way - ordinary 
market games are of this type. In general, by a market game (with exchange 
and production) we will mean a set of players N « {1, ..., n}, with a set of 
initial (vector) endowments or, • .., ta , and a common production set Y. An 
outcome of the game is some distribution of wealth x ~ (x » ..., x ) such that 
Ex - Si) e Y. The characteristic function of each coalition ScN is customarily 
taken to be V(S) « {(x 1 , - x^JlgX 1 "i^g 1 * Y l 

This is normally interpreted to mean that each coalition has the power to 
dispose of its initial endowment in ar •? way it pleases. We say that a coalitio" 
S is affective for each allocation x in V(S) . 

The description of the game is completed by a preference ordering for each 
■player on the set of outcomes. If an outcome xgV(S) is preferred to an outeom; 
y by all members of some coalition, S c N then we say x dominates y. The set c" 
undominated outcomes is defined to be the core of the game. 

It is clear that the characteristics function, and consequently the core, 
are functions of the initial endowment t«. We shall denote the market resulting 
from the endowment ta by M{<«) , and the core by C(u>) . 

If a game is to be played only once, every outcome in the core can be consid- 
ered stable, since no coalition of players can redistribute their initial allo- 
cation in a way which they unanimously prefer to a given core allocation. However 



2. 
if a game is to be played more than once, the initial endowment of a given play 
is the allocation which results from the preceding play. 

Thus in allocation ^resulting from a market M(u>) gives rise to a new market 
M(x) . Therefore an allocation x in the core of the market M(to) can only be 
considered stable if x is in the core of the market M(x) . The following ex- 
ample shows that not all points in the core of a market game are necessarily 
stable. 

Example : The game consists of two players N«{1,2,}, and three commodities. 

' i i i j 
An allocation of goods to player i is denoted by x *(x, .x-.xJ , where super- 
scripts index players and subscripts index commodities. 

1 2 

The initial allocations of the players are tx> *(1,0,G) and <t> -(0,1,0). 

The production set permits any amount of the first commodity to be transformed 

into an equal amount of the third commodity? i,e, the production set is 

Y-{ (x ,x ) | X x~ ■ Z (xt + xh * Oj. The preferences of the two 

,i*l,2 l 1.-1,2 

players for outcomes jc"(xl,x*) are represented by the utility functions 

12 n 2 

u.(x) - x~ - 2x^ and u.(x) * x. + 2x^ . Thus the initial endowment u> 

gives each player a utility of aero. 

I 1 
The characteristic function of the market game M(y>) is V(l) » (x | x < u> ] 

2 2 
V(2) = (x f x <^m }; V(12) « [x ! (x s))« Y}. The core >f the game M(ta) contains 

1 2 
the allocation x - [x s x j « [(0,1,0); (1,0,0)] such that u (x) * u 2 <x) »1. 

In particular, the allocation y « [(0,1,0); (0,0,1) j with u (y) =-1 and 
u 2 (y) = 2 does not dominate x in the game J since player 2, who prefers y to 
x, is not effective for y.. However in the game M{x) player 2 _is effective for 
the allocation y, and thus x is not in the core of the gameM(x) The only 
stable allocation in this example is the allocation y. 

The example can perhaps be illuminated by a simple 'story'. The first 
two commodities are private goods j uranium and money. The third commodity, 
which can be produced from the first, is a public good which gives utility 
to player 2 and disutility to player 1 - atomic weapons. Player 1 initially 
holds all the uranium and player 2 holds all of the money. The allocation x 



3. 
represents the mutually profitable trade of uranium for money. The observa- 
tion that x is unstable simply reflects the fact that once player 2 is in 
possession of the uranium, he has the incentive to divert it to weapons prod- 
uction to the detriment -yer 1. Thus, the allocation x can only be con- 
sidered stable if the rules of the game provide for an enforceable agreement 
limiting the future use to which uranium can be put. Under the more usual 
(and realistic) assumption that agreements can only be enforced when the 
commodities in question remain under the physical control of the parties in- 
volved, we see that player 2 has both the power and the incentive to reallo- 

i 
cate the uranium for weapons production.* 

When utility is freely transferable it is often convenient to consider 

games with side payments. We define a- power game with side payments to be 

a collection (N,X,x°,V v ), where Nhfl, . . .,n} is the set of players, X is the 

x 

convex set of outcomes futility n-tuples) ; . x is the initial outcome, and 
V ^{v jxeX} is a set of real-valued characteristic functions v^ correspon- 
ding to each outcome xeX. Alternatively, view V-- as a function V„: X&Z* 1 — ^R.. 

A. 

Thus the power of each coalition, which is reflected by the characteristic 
function, is dependent on the utility of each player* 

The core of a characteristic function v is the set C(x) -fxeXJfor all 
S — ^ 'i§* x -~ v (*)}• ! ' m outcome x«X is stable if nnd only if xeC(x). A 
characteristic function v with a non-empty core C(x) is said to be balanced. 
The function V_. is said to be balanced if C(x) is non-empty for each xeX. 
Example 2: Consider the power game (N,X,x°,V Y ) in which N«{1,2}, X*{(x 1} x„) | 



/•. 



1>"2- 



x l +x 2 — *' x i ' x 2 ~ ^' x ~(^>°)» an & £° r each xeX 

v (1) - MIN [1, MAX (0 5 2x 1 -x 2 l] 



v x (2) * MIN [1, MAX (0,2x2^)] 



v (12) -I 

x 



Note that if x =x, then v (i) » x. and v (j) - x. for i«l,2 while if x>x, then 
i j x x x J 3 ' i j 



Similar phenonema have been observed by Rosenthal (1972) and Rofch & Postlewaite (1 



v (i) > x. and v (j)<x.. 

X 1 X j 

The dynamic behavior of this game is aptly expressed fay the proverb "the 
rich get richer and the poor get poorer/'* In particular, it can readily be 
verified that the only stable outcomes of this game are (%»%)', (1*0), and 
(0,1). 

In general, we can prove the following: 
Theorem: For every power game with side payments in which V is balanced and 
a continuous function of outcomes , the set or stable allocations is non-empty. 
Proof ; For every outcome xeX, the correspondence G(x) is a non-empty, closed, 
convex polyhedron. We want to show that C(x) is upper-semi continuous: i.e=, 
if x^'eX and. Urn x^ - x, and if y^'eCCx* 1 ') and V . ,"'-y than y € C(x). 

Suppose not,. then there exists a coalition SeH such that if (S) > -&V X . By 
continuity, there must be an Jr such that for all n > N, VJfiS(S)>X!e(y^ ) which 



if? 

contradicts the fact that y*" / «C(x v ' y ') . So C(x) is upper semi -continuous 



.<«>-«/_<»K 



Hence by Kakutanis fixed point theorem [.4.941] there exists an outcome x 
such that x«€(x )"! i.e. there exists a stable outcome. 



References 

Kakutani, S. (1941) "A Generalisation of Broker's Fixed Point Theorem", 

Duke Journal of Mathematics, vol. 8, pp. 457-459, 
Morgenstern, Oskar (1972) "Strategic Allocation and Integral Games" Dept. 

of Economics Working Paper #4, ISfew York University 
Rosenthal. Robert W, (1972) "Cooperative Games In Effectiveness Form" 

Journal of Economic Theory, vol. 5, pp. 88-101 
Roth, Alvin E. and Postlewaite, Andrew (1975) "Weak Versus Strong Domination 

in a Market With Indivisible Goods" Working Paper #240, College of 

Commerce and Business Administration, University of Illinois, Urbana- 

Champaign, Illinois. 



J 



'-94