UNIVERSITY OF
ILLINOIS LIBRARY
AT URBANA-CHAMPAIGN
BOOKSTACKS
Digitized by the Internet Archive
in 2011 with funding from
University of Illinois Urbana-Champaign
http://www.archive.org/details/nashsolutionutil364roth
,00
Faculty Working Papers
THE NASH SOLUTION
AND THE UTILITY OF BARGAINING
Alvin E. Roth
#364
College of Commerce and Business Administration
University of Illinois at Urbana-Champaign
FACULTY WORKING PAPERS
College of Connerce and Business Adininistration
University of Illinois at Urbana-Champaign
January 4, 1977
THE NASH SOLUTION
AND THE UTILITY OF BARGAINING
Alvin E. Roth
#364
THE NASH SOLUTION AND THE UTILITY OF BARGAINING
by
Alvin E. Roth
Assistant Professor, Business Administration
ABSTRACT
It has recently been shown that the utility of playing a game
with side payments depends on a parameter called strategic risk posture.
The Shapley value is the risk neutral utility function for games with
side payments.
In this paper, utility functions are derived for bargaining games
without side payments, and it is shown that these functions are also
determined by the strategic risk posture. The Nash solution is the risk
neutral utility function for ba.rgaining games without side payments.
THE NASH SOLUTION AND THE UTILITY OF BARGAINING
by
Alvin E. Roth
I. Introduction
Recent work has shown that the Shapley value for a game with
side payments is a cardinal utility function which reflects the desir-
ability of playing different positions in a game, or in different games
(cf. Shapley [14], Roth [9]). A player's utility for playing some
position in a game is determined in part by his assessment of the
payoff he will receive in a class of games with side payments called
bargaining games. Given a player's evaluation of these bargaining
games, his utility for playing a position in any game with side payments
can be determined (cf. Roth [11]).
It is desirable to extend these results to games without side
payments, since the assumption that side payments can be made is not
appropriate in many situations. In this paper we will derive a class
of utility functions for playing bargaining games without side payments.
Games of this sort are studied by Nash [7], who developed a solution to
bargaining games which is an extension of the Shapley value for games
with side payments. That is, the Nash solution coincides with the
Shapley value for bargaining games with side payments.
Somewhat surprisingly, the utility of playing a bargaining game
without side payments is determined by the same considerations which
determine the utility of playing a game with side payments. Given a
player's evaluation of bargaining games with side payments, his utility
for bargaining without side payments is determined.
II . utility Functions for Games with Side Payments
This section summarizes the development of utility functions for
games with side payments, as presented in [9] and [11]. We begin with
some necessary definitions.
2
A game with side payments consists of a set of positions
N = {l,...,n} and a superadditive function v from the subsets of N to
the real numbers such that v(0) = 0. The function v denotes the amount
of wealth which each coalition of players can obtain for itself, and
the model assumes that utility is linear in wealth, and that wealth is
freely transferable. The set of individually rational outcomes
(imputations) is thus the set
X
= {(x^,...,x )| 5!x^ = v(N), x^ ^ v(i)}
Since we shall be interested in comparing different games, we
take N to be the common set of positions for all games. Thus n is the
largest number of players who can take part in a game (e.g., n could be
the population of the world). In order to distinguish which positions
have an active role in a given game, define position i to be a dummy
in game v if, for all subsets S of N, v(S) = v(SUi) . The positions
which are not dummies are called the strategic positions of the game v.
If 7t is a permutation of N, denote the image under it of a subset
S of N by irS, and define the game nv by Trv(iiS) = v(S). To simplify the
exposition, we confine our attention to the class G of non-negative
games; i.e., games for which v(S) >_ 0.
For any subset R of N, it will be convenient to define a bar-
gaining game with side payments, v^^, by ^^^(S) = {^ Qt-^erwise ' ^^ ^^^^
game, all players in R are symmetric, and all players not in R are
dummies. Similarly, for each position i in N, denote by v. the game
v,(S) = IX , . .In this game all positions other than i are
i^ ^0 otherwise ^ ^
dummies. Denote by v the game v^(S) = 0 for all S, the game in which
all positions are dummies.
In order to make comparisons between positions in a game and in
different games, we shall consider a preference relation defined on the
set NxG of positions in a game. Write (i,v)P(j,w) to mean "it is pre-
fereable to play position i in game v than to play position j in game w."
3
The letter I will denote indifference, and W will denote weak preference.
We will consider preference relations which are also defined on
the mixture set M generated by NxG. That is, preferences are also
defined over lotteries whose outcomes are positions in a game. Denote
by [q(i,v) ; (1-q) (j,w) ] the lottery which with probability q has a
player take position i in game v, and with probability (1-q) take posi-
tion j in game w. We will henceforth only consider preference relations
which have the standard properties of continuity and substitutability
on M which insure the existence of an expected utility function unique
up to an affine transformation. Denote this function fay 6, and write
6^(v) = 9((i,v)), and e(v) = (G^(v) , . . . ,e^(v) ) .
The utility for a position in a game is given by
(v) = 8((i,v)) =
q^l,((i,v)) - q^^Cr^)
^ ' 'Jab^^l^ - '^ab^^O^
where a, b, r^ , and r are elements of M such that aW(i,v)Wbs and
J- u
aWr Pr„Wb, and the numbers q v (y) are probabilities defined for any y
in M such that aWyWb by yl[q , (y)a; (1-q (y))b] . The elements r^ and
r^^ determine the origin and scale, since 6(r^) = 1, and 9(^q) - O-
We assume that the preference relation obeys the following
three conditions:
(2.1) For all i e N, v e G, and for any permutation ti, ir(i,v)I(7Tl,iTv) .
(2.2) If i is a dummy in the game v, then (i,v) I(i,v„) . Also
(i,v.^)P(i,VQ), and for all (i,v) C NxG, (i,v)W(i,Vj^) .
(2.3) For any games v and w, and for any probability q,
(i, (qw+(l-q) v) ) I [q (i, w) ; (1-q) (i, v) ] .
Condition 2.1 says that the names of the positions don't influ-
ence their desirability. Condition 2.2 says that a strategic position
in a game is always at least as desirable as a dummy position, and that
it is equally undesirable to be a dummy in any game. Condition 2. 3
expresses indifference between playing position i in the game (qw+(l-q)v),
and playing position i in game w with probability q or in game v with
probability (1-q) .
Condition 2.2 also insures that we may choose the natural nor-
malization for the utility function 6. In what follows, we will con-
sider 9 to be normalized so that 8. (v.) = 1, and Q.iv^) = 0.
11 1 0
It has been shown [9], [11] that any utility function arising
from preferences obeying conditions 2.1, 2.2, and 2.3 has the following
properties:
Property 1. Symmetry: for any (i,v) e N^G, and for any permutation
TT, 9 .(-nv) = 9.(v).
ni 1
Property 2. Homogeneity: for any (i,v) c NxQ, and any non-negative
number c,- 9.. (cv) = c9 . (v) .
Property 3. Additivity: for any v,w e G, e(v + w) = 8(v) + 8 (w) .
The utility function fl can now be completely determined by
specifying the certain equivalent of playing a bargaining game v , as
K
one of r strategic players.
Let f(r) be a number such that
(2.4) (i,v^)I(i,f(r)v^) for i f, R.
This expresses indifference between receiving f(r) for certain (as the
only strategic player in the game f(r)v,) and being one of r strategic
players in the game v . Note that f(l) = 1. Using the terminology of
K
[9], we say that the preference is neutral to strategic risk if
f(r) = 1/r for r = l,...,n. The preference is strategic risk averse
if f(r) < 1/r, and strategic risk preferring if f (r) > 1/r
The utility 9 for playing an arbitrary game with side payments
can now be written in terms of the function f(r).
Theorem 1: 6 . (v) = J^ k(t) [v(T) - v(T-i)],
^ TCK
n _ _
where k(t) = V (-1)^ ^(^_pf(r).
r=t
Furthermore, if the prefereiice relation is neutral to strategic
risk, then the utility of playing a position in a game is equal to its
Shapley value.
Corollary 1: If f(r) = 1/r, then 9 (v) - T -^s-x; . v.n b, .^^^^^ _ ^(g.^j j
SCN ^'
III. Bargaining Games without S ide Payments, and Nash's Solution
An n-person bargaining game without side payments is defined by
a compact convex subset A of n-dimens:ional Euclidean space, and a point
s contained in A. Any point x - (x , ...,x ) contained in A represents
the von Neuioann-Korgenste? n utility available to each player as the
result of some feasible agreeiiient, and the set A represents the set of
all feasible utility payoffs. The point s = (s^,...,s ) i"epresents the
utility of the "status quo" — that is, s gives the utility level achieved
by each player in the absence of any agreement.
For simplicity, v*e will assume that the set A contains only
individually rational agreements: i.e., if x e A, then x ^ s. We will
also assume that the origin of the utility function for each player
(position) is equal to the status quo payoff; i.e., we assume s. = 0
for all i e N. Denote the class of all such bargaining games by H. An
element of H will be denoted by the feasible set A, with the status quo
being understood to be the origin.
As in the previous section, take N = {!,..., n} to be the common
set of positions for all bargalnir-g games. The- set R of strategic
positions in a bargaining game A is the set R={icNl SxcA such
that X. 7^ 0}. A position which is not in the set R is a dummy for the
game A.
A Nash solution to the bargaining problem is a function F,
defined on bargaining games, which associates with each bargaining game
A a single feasible outcome F(A) f A, and which obeys the following
four conditions:
(3.1) Linearity: For any bargaining garae A and positive real numbers
a, , . . . ,a , if B = { (a, x, , . . . ,a :;c ) | (x., , . . . ,x ) e A] then
1 n ixnnJ. n
F.(B) = a.F.(A) for i - l,...,fi.
(3.2) Independence of irrelevant alternatives: If A and B are bargain-
ing games and B contains A, and if F(B) e A, then F(B) = F(A) .
(3.3) Symmetry: Let R be the set of strategic positions in a game A,
and suppose that for every permutation it of N such that irR = R,
X € A implies that iix f A. Then F. (A) = F , (A) .
r TTi
h
for all strategic positions i e R, then F(A) "^ x.
(3.4) Pareto Optimality: If x and y are elements of A, and y. > x.
Nash [ 7 ] proved the following theorem.
Theorem 2: There is a unique function F which satisfies conditions
3.1-3.4. For a bargaining game A, F(A) is the unique
element x e A such that it x > IT y. for every y ^ x
iCR ieR ^
in A, where R is the set of strategic positions of the
game A.
Thus the Nash solution picks the point x in S which maximizes
the geometric average of the payoffs x. for ieR- Note that F(A) = 0
if and only if R is empty. It has recently been shown that this con-
dition can replace Pareto optimality in the characterization of the
9
Nash solution (Roth [10]). That is, we have the following theorem.
Theorem 3: The Nash solution is the unique function F which satisfies
conditions 3.1-3.3, and the condition that F(A) = 0 only
when R is empty.
8
IV. The Utility of Bargal7;ting
In this sectior we will consider the utility of bargaining, by
considering a preference relation ? defined on the set of positions in
bargaining games without side payx^ents. Specifically, take P to be a
preference relation defined on N^U, and on the mixture set M' generated
by NxH,
It will be convenient to define, for each set R contained in N, the
set A -■ {x| 1 X. ± 1, X. >_ 0 if i <r B., and x^ = 0 if j (^ R} , and to define
for each non-negative vector x, the set A to be the line joining x to
the origin, i. e. , A = {ax | 0 <^ a <^ 1} .
It is easy to see that a bargaining game with side payments is
actually a special case of a bargaining game without side payments. In
particular, the game v with side payments aiid the game A^ without side
payments present the same bargaining opportunities to the set R of stra-
tegic players (which is the same for both games). The set of outcomes
in which dummies receive a payoff of zero is the same in both games.
Similarly, the game v. can be associated with the game A. = A_ where
X. = 1, and X. = 0 for 'i r i, and the game v,, has the same outcome set
as the game A^, since neither game has any strategic positions.
As in Section II, we confine our attention to preferences P which
have the properties of continuity and substitutability necessary to
insure the existence of an expected utility function 9. Of course 8 is
unique only up to affine transformations, so we may set 6. (A.) = 1, and
8 . (A„) = 0, where we denote 9 . (A) = 6(1, A).
We also assume that the preference relation obeys the following
conditions .
(4.1) For all i e N, A e H, and every permutation v of N, (i,A) I(fri,TiA)
(4.2) For all i e N, A c H, (i,A)W(i,A(^) and (i,A)I(i,AQ) iff i is a
dumm' in A. Also, if x. > y. then (i,A )P{i,A ), and if R is a
1 ■ 1 X y
non-empty subset of N such that R =/ (i), then (i,A. )P(i,A ) .
(4.3) If B = {(a^x^ , . . . ,a x )! x c A; for a. > 0 for i = l,...,n, and
11 *nn j=" -■ ».»
if a^ > 1, then (i,A)I[ (I/a. ) (i, B) ; (l~l/a^)(i,A^^) ] .
(4.4) If A c B c C, and (i,A)I(i,C) then (i,A)I(i,B).
Condition 4.4 expresses indifference to irrelevant alternatives.
It says that if ^ player is indifferent between playing in a game A, or
in a game C with a larger set of Eeasibie alternatives, then he is also
indifferent between playing A or any game B which contains A and is con-
tained in C. Condition 4.3 simply says that, if the payoffs available
in a game are multiplied by positive constants, then a player is indif-
ferent between playing one game, or participating in the appropriate
lottery involving the new game. Conditions 4.1 and 4.2 are similar in
form and content to conditions 2.1 and 2.2.
If e is a utility function reflecting preferences which obey the
above conditions, then it has the follccjing properties.
Lemma 1: If i is a dummy in A, then 6 . (A) = 0, and if x. = y., then
Proof: This follows immediately from condition 4.2.
Lemma 2: If B = { (a^ x, , . . . ,a x )i x € A} where all a. > 0, then
i 1 n n ' 2
6 . (B) = a . 6 . (A) .
Proof: Suppose a, >^ 1. Then by condition 4.3, 9 . (A) =
e^[(l/a_j^)(i,B);(l-l/ap(i,AQ)] = (l/a^)e^(B) + (1-1/a^) 9^(Aq)
10
= (l/a.)6.(B). Suppose a. < 1. Vixen let b. = 1/a. for
1 1 X 3 J
i = 1, . . . ,n. ITien A = { (,b, y, , . . . ,b y ) ! y C B}, and b. > 1.
J ' ' linn' 1.
So e.(B) = (l/b.)6.(A) = a.e,(A).
Lemma 3: For any x, 6 . (A ) = x. .
IX 1
Proof: Let y be the vector such that y. = x. and y. = 0 for
i ?^ i. Then lemma 2 implies that 6 . (A ) = 9.(x.A.) = x.9.(A.)
■^ lyxxxiix
= X., and lemma 1 implies that 6 . (A ) = 9 . (A ).
X X X X y
As is the case for games with side payments, the function G will
be completely determined by the posture towards strategic risk. For
bargaining games with side payments, condition 2.4 stated (i,v_)I(i, f (r)v.)
for i e R. The equivalent condition for bargaining games without side
paymen ts is
(4.5) (i,A„)J(i,f(r)A.) for i f R.'
K X
This expresses indifference between playing a strategic position in the
game A^ (as one of r strategic players) or receiving the utility f(r)
for certain (as the only strategic player in the game A.)- By condition
4.2 we know that f(l) = 1, and 0 < f(r) < 1 for r > 1. As in the case
of games with side payments, we say the preference relation is neutral
to strategic risk if f(r) = 1/r, averse to strategic risk if f(r) < 1/r,
and strategic risk preferring if f(r) > 1/r. We will show that the Nash
solution is the utility function reflecting risk neutrality.
An immediate consequence of condition 4.5 is that e.(A^) = f(r).
More generally, we have the following result.
Lemma 4: If B„ = {y > 01 )' b.y. < 1, y. = 0 for i i! R} where b. > 0
xeR
11
for each i e R then 6 . (B„) = f(r)/b. for i € R.
1 R 1
Proof: B^ - {(a,x_,...,a x )j x c K.^ where a. = 1/b , for
R 11 n n ' K" ], 1
1 e R and a . = 1 for j ^ R. So leinma 2 implies that 8 . (B )
J 1 K
a.6.(V = nr)/b..
We can nov? specify the function 6 for an arbitrary bargaining
game A.
Theorem 4: If A is a bargaining game with R the set of strategic posi-
tions, then for k e R, G, (A) = x, , where x is the unique
element of A such that II x. > n y. for all y c A such
icR leR
that y ^ x, where q = (q^,...,q ) is any non-negative vector
such that q, = f ( r) and Y q. = 1.
xcR
The element x named in the theorem maximizes the geometric average
with weights q , ...,q over the set A. (Tlie weighted geometric average
is concave, so it has a unique maximum of A.) The statement of the
theorem implies that 6, (A) = x, depends only on q. . Explicitly, the
following technical proposition follows as a corollary of the theorem.
^i Pi
Proposition: If x maximizes n x. and y maximizes JT y. over the
ICR ^ i€R ^
set A, where q and p are non-negative vectors such that
I q i = I Pi = 1' then :<^ = y if q = p .
ieR "- ieR ^ R K ic K
Proof of theorem: Let A be a bargaining game without side payments, and
let R cr N be the set of strategic positions of A,
and let k e R. Let q = (q , ,..,q ) be a non-negative
12
vector such that T q. = J q. = 1, and q, = f(r) > 0.
Let X be the element of A which maximizes n x. . That
i(^R .^
q, q^
is, II X." = c > n y. for all y e A nuch that y t' x.
iCR ^ ieR ^
Let H = {yj II y. >^ c} = {y| 1 q. log y. >^ log c}.
iCR ^ IfR ^ ^
Tlien H and A are convex sets whose intersection is
the point x, and so there is a plane which separates H and
A. This plane is the tangent to H at x, i.e., the set
T = {zl z.n = x-n} where n = (q /x , ,..,q /x ) . So T =
{z] (q,/x,)z, + ... + (q /x )z = T q = 1}.
' ^1 1 i n n n .'-.^ i
Let B = {z\ (q /x )z + ... + (q /x )z £ D • Then
J_Ji„JL iLltLl
A cr B, since T separates A from H. Lemma 4 implies that
e^(B) = (Xj^/qj^)f(r) = (x^^/f(r))f(r) = x^. So (k,B)l(k,A^) ,
since 9 (A ) = 6, (B) = x, . Thus we have A c: A c: B, and
(k,A )I(k,B). By condition 4.4, this implies that
(k,A )I(k,A), and so 9 (A) = x . This completes the proof.
X K. K.
Corollary 2: When f (r) = 1/r, Q is equal to Nash's solution.
Proof: If A is a bargaining game with strategic positions
R, then for k e R, 9, (A) = x where x maximizes 11 x.
"^ ^ ieR ^
on A, for q, = f(r) = 1/r and ^ q, = 1. In particular,
■^ ICR "-
X maximizes II x. , and, since r > 0, x maximizes n x. .
iC R le R
Thus we have shown that the utility of playing a bargaining game
without side payments is determined by the posture towards strategic
13
risk. Since the Shapley value and the Nash solution agree on bargaining
games with side payments, it is natural to observe that they result from
the same risk posture.
The treatment presented here permits us to observe not only the
similarities between utility functions for games with and without side
pajrments, but the differences as well. The most significant difference
seems to be that, for bargaining games without side payments, there is
no parallel to condition 2.3 for games with side payments. Tliat is, if
A, B, and C are bargaining games without side payments, such that
11 111
C=yA + -T-B = {(2X + ^y)j xCA, ye B}, then the utility of a lottery
between A and B is not in general equal to the utility of C. That is
6.[y A;y B] = -rO . (A) + :r6 . (B) / 6.(C). A discussion of this phenomenon
in the context of the Nash solution is given by Harsanyi [2, pp. 330-
332].
Nash originally interpreted his solution as applying to players of
equal bargaining ability, but subsequently modified this interpretation
[7,8], Our results support Nash's original interpretation. The attitude
of neutrality to strategic risk, which gives rise to the Nash solution
as a utility function, simply expresses a player's belief that he will
receive the average reward in a bargaining situation. As we have seen,
any other risk posture gives rise to a utility function different from
the Nash solution.
FOOTNOTES
1. For related results, see Roth [12,13].
2. We speak of "positions" rather than the more customary "players"
since we are interested here only in the structural properties of
the game. We shall be concerned with the problem of evaluating
the different positions from the point of view of a player who
must choose among different positions.
3. So alb means neither aPb or bPa, and aWb means aPb or alb.
4. A mixture set has the properties that for all a,b e M
[la;Ob] = a, [qa;(l-q)b] = [(l-q)b;qa], and [q[pa; (l-p)b] ; (l-q)bi
= [pqa; (l-pq)b]. (Cf Herstein and Milnor [4].)
5. Cf Herstein and Milnor.
6. A utility function has the property that u(a) > u(b) if and only if
aPb. An expected utility function on a mixture space has the
property that u( [qa; (l-q)b]) = qu(£) + (l-q)u(b). That is, the
utility of a lottery is its expeci:ed utility.
7. Cf Herstein and Milnor.
8. The cardinality of sets R, S, T is denoted r, s, t.
9. This statement of the theorem makes use of the fact that we have
already assumed individual rationality.
0. Harsanyi and Selten [3, lemma 10. 1] and Kalai [5 J both show that
weighted geometric averages of this sort obey all of Nash's
conditions except symmetry.
15
11. For different approaches to the bargaining problem see Brito, et.
al. [1] or Kalai and Smorodinsky [6].
REFERENCES
1. Brito, D.L.; Buoncristiani, A.M., and Intriligator, M.D., "A New
Approach to the Nash Bargaining Problem," Econometrica, (to appear).
2. Harsanyi, J.C. "Games with Incomplete Information Played by
'Bayesian' Players Part II: Bayesian Equilibrium Points," Manage-
ment Science, vol. 14, no. 5, January 1968, pp. 320-334.
3. Harsanyi, J.C, and S el ten, R., "A Generalized Nash Solution for
Two Person Bargaining Games with Incomplete Information," Management
Science, vol. 18, no. 5, January Part 2, 1972, pp. 80-106.
4. Herstein, I.W. , and Milnor, J., "An Axiomatic Approach to Measurable
Utility," Econometrica, vol. 21, 1953, pp. 291-297.
5. Kalai, E., "Nonsyrcmetric Nash Solutions and Replications of 2-
Person Bargaining," International Journal of Game Theory (to appear).
6. Kalai, E., and Smorodinsky, M. , "Other Solutions to Nash's Bargaining
Problem," Econometrica, vol. 43, 1975, pp. 513-518.
7. Nash, J.F., "The Bargaining Problem," Econometrica, vol. 18, 1950,
pp. 155-162.
8. Nash, J.F., "Two Person Cooperative Games," Econometrica, vol. 21,
1953, pp. 128-140.
9. Roth, A.E., "The Shapley Value as a von Neumann Morgenstern Utility,"
Econometrica (to appear) .
10. Roth, A.E., "Individual Rationality and Nash's Solution to the Bar-
gaining Problem," Mathematics of Operations Research (to appear).
17
11. Roth, A.E., "Bargaining Ability, the Utility of Playing a Game,
and Models of Coalition Formation," mimeograph, 1976.
12. Roth, A.E., "Utility Functions for Simple Games," mimeograph, 1976.
13. Roth, A.E,, "A Note on Values and Multilinear Extensions," Naval
Research Logistics Quarterly (to appear).
14. Shapley, L.S., "A Value for n-Person Games," Annals of Mathematics
Study, vol. 28, 1953, pp. 307-317.