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