Values of Non-Atomic Games

by Robert J. Aumann, Lloyd S. Shapley

Overview

The "Shapley value" of a finite multi- person game associates to each player the amount he should be willing to pay to participate. This book extends the value concept to certain classes of non-atomic games, which are infinite-person games in which no individual player has significance. It is primarily a book of mathematics—a study of non-additive set functions and associated linear operators.

Originally published in 1974.

The Princeton Legacy Library uses the latest print-on-demand technology to again make available previously out-of-print books from the distinguished backlist of Princeton University Press. These editions preserve the original texts of these important books while presenting them in durable paperback and hardcover editions. The goal of the Princeton Legacy Library is to vastly increase access to the rich scholarly heritage found in the thousands of books published by Princeton University Press since its founding in 1905.

Product Details

ISBN-13:	9780691618463
Publisher:	Princeton University Press
Publication date:	03/08/2015
Series:	Princeton Legacy Library , #1770
Pages:	348
Product dimensions:	6.90(w) x 9.90(h) x 3.10(d)

Read an Excerpt

Values of Non-Atomic Games

---

By Robert J. Aumann, Lloyd S. Shapley

PRINCETON UNIVERSITY PRESS

Copyright © 1974 The Rand Corporation
All rights reserved.
ISBN: 978-0-691-08103-8

---

CHAPTER 1

The Axiomatic Approach

1. Preliminaries

The symbol [parallel] [parallel] for norm is used in many different senses throughout the book; but it is never used in two different senses on the same space, so no confusion can result. In particular, when x is in a euclidean space of finite dimension (i.e. it is a finite-dimensional vector), then [parallel] x [parallel] will always mean the maximum norm, i.e.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is important to distinguish notationally between functions and their values. For example, if μ is a measure, then [parallel] μ [parallel] is its total variation, whereas [parallel] μ(S) [parallel] is simply the absolute value of the real number μ(S).

Occasionally it will be necessary to use more than one norm on a given space; in that case, the norms will be distinguished in various ways, for example, by subscript, as in [parallel] [parallel]1.

Closure will be denoted by a bar; thus [bar.A] is the closure of A.

Composition will usually be denoted by the symbol ο; thus if f is defined on the range of μ, then the function whose value at S is f(μ(S)) will be denoted f ο μ. When no confusion can result, especially in the case of compositions of linear operators, the symbol ο will occasionally be omitted.

The origin of any linear space (including, of course, the real line) will be denoted 0; no confusion can result. In euclidean n-space En, x · y will denote the scalar product of two vectors x and y, ei will denote the i-th unit vector (0, ..., 0, 1, 0, ..., 0), and e will denote the vector (1, ..., 1).

The symbol [subset] will be used for inclusion that is not necessarily strict. Set-theoretic subtraction will be denoted by \, whereas — will be reserved for algebraic subtraction. f|A will mean "f restricted to A." The cardinality of a set A is denoted [absolute value of A].

Closed and open intervals are denoted [a, b] and (a, b) respectively; [a, b) and (a, b] denote half-open intervals.

W.l.o.g. means "without loss of generality." W.r.t. means "with respect to."

A measurable space is a pair (I, C) where I is a set and C is a σ-field of subsets of I; the members of 6 are called measurable sets. When no confusion can result, we shall sometimes denote the measurable space (I, C) simply by I. A function f from one measurable space (I, C) into another one (I, D) is called measurable if T [member of] D implies f-1 (T) [member of] C. Two measurable spaces are called isomorphic if there is a one-one function from one onto the other that is measurable in both directions; the mapping is called an isomorphism. The measurable space consisting of the closed unit interval with its Borel subsets will be denoted ([0,1], (B); Lebesgue measure on this space will be denoted λ.

Proposition 1.1. Any uncountable Borel subset of any euclidean space, and indeed of any complete separable metric space, when considered as a measurable space, is isomorphic to ([0, 1], B).

For a proof, see Mackey (1957), or Parthasarathy (1967), Theorems 2.8 and 2.12, pp. 12 and 14.

Proposition 1.2. Let f be a one-one measurable function from a Borel subset of [0, 1] into the real line, both considered as measurable spaces. Then the range off is a Borel set.

For a proof, see Mackey (1957), p. 139, Theorem 3.2, or Parthasarathy (1967), Theorem 3a, p. 21.

Unless otherwise specified, the word "measure" in this book refers to countably additive totally finite signed scalar measures. Recall that a measure [xi] on a measurable space (I, C) is non-atomic if for all S in C with [xi](S) ≠ 0, there is a T [subset] S with [xi](S) ≠ [xi](T) ≠ 0. A vector measure is an n-tuple μ = (μ1, ..., μn) of measures μι with n finite; if the μi are non-atomic then also μ is called non-atomic. The range of μ is the set μ(S): S [member of] C}; it is a subset of En. The following proposition will be used repeatedly throughout the book:

Proposition 1.3 (Lyapunov's Theorem). The range of a non-atomic vector measure is convex and compact.

Since the original proof of Lyapunov (1940), this theorem has been reproved many times. For an elementary proof, the reader is referred to Halmos (1948), and for a quick, though deeper proof, to Lindenstrauss (1966).

NOTES

1. If (I, C) is isomorphic to ([0, 1], (B), then it may be verified that a measure [xi] is non-atomic if and only if [xi]({s}) = 0 for all s in I.

2. Definitions of Game and Value

At the beginning of the section we shall concentrate on the formal basic definitions of "game" and "value," interpolating only a minimum of discussion and illustration. These basic definitions — which form a self-contained unit — will be slightly indented, in order to set them off from the discussion. In the second part of the section we will interpret and motivate the definitions from the game-theoretic point of view.

Let (I, C) be a measurable space; it will be fixed throughout and will be referred to as the underlying space. The term set function will always mean a real-valued function v on C such that v(Ø) = 0.

In most of this book (until Chapter VIII) we will make the following

(2.1) Standardness Assumption: The underlying space (I, C) is isomorphic to ([0, 1], (B).

Because of Proposition 1.1, this assumption is not as drastic as it seems. We add that for much of the material of this book, (2.1) is not needed; see Section 47.

In the interpretation, a set function is a game, I is the player space, and the members of C are coalitions. The number v(S), for S [member of] C, is interpreted as the total payoff that the coalition S, if it forms, can obtain for its members; it will be called the worth of S. This way of representing a game is an obvious generalization of the standard representation in "characteristic function" (or "coalitional") form of a game with finitely many players (cf. von Neumann and Morgenstern, 1953, or Appendix A, below). Sometimes the phrase "game with a continuum of players" is used to distinguish these games from the finite ones. It should be stressed, however, that our treatment is measure-theoretic; the player space is a measurable, not a topological space.

By a carrier of a game (or set function) u, we mean a coalition I' such that v(S) = v(S [intersection] I') for all S [member of C; the complement of a carrier is said to be null. An atom of v is a non-null coalition S such that for every coalition TC [subset, either T or S\T is null. If v has no atoms, v is called non-atomic; this agrees with the above definition of "non-atomic" if v happens to be a measure. Though we will have little further technical use in this book for the notion of a general non-atomic game, most of the games to be considered here will in fact be non-atomic, and their non-atomicity is more or less the crux of the matter.

A set function v; is said to be monotonic if S [contains] T implies v(S) [??] v(T). The difference between two monotonic set functions is said to be of bounded variation. The set of all set functions of bounded variation forms a linear space over the field of real numbers, which will be called BV.

An example of an element of BV is any set function of the form

v(S) = f(μ(S))

where μ is a finite non-negative measure and f is a function of bounded variation on the real interval [0, μ(I)] with f(0) = 0. Our investigations will focus on the space BV and certain of its subspaces.

The subspace of BV consisting of all bounded, finitely additive set functions, i.e. the bounded, finitely additive, signed measures on ((I, C), will be denoted FA. Note that an element μ of FA is monotonic if and only if μ(S) [??] 0 for all S [member of] C.

Let Q be any subspace of BV. The set of monotonic set functions in Q will be denoted Q+. A mapping of Q into BV is called positive if it maps Q+ into BV+, i.e. if it transforms monotonic set functions into monotonic set functions. It may of course happen that Q has no monotonic elements other than 0; in that case all linear mappings ofQ into BV are positive.

Let G denote the group of automorphisms of the underlying space (I, C), that is, isomorphisms of that space onto itself. Each Θ in G induces a linear mapping Θ* of BV onto itself, defined by

(Θ* V)(S) = u(ΘS).

A subspace Q of BV is called symmetric if Θ*Q = Q for all Θ in G.

We come at last to the definition of "value." Let Q be a symmetric subspace of BV. A value on Q is a positive linear mapping φ from Q into FA, such that for all Θ in G and v in Q we have

(2.2) φ Θ* = Θ*φ

and

(2.3) (φv)(I) = v(I).

We shall refer to φv as the value of the game v, and to φv)(S) as the value of the coalition S.

Essentially, the "symmetry" condition (2.2) says that the value does not depend on how the players are named, and the "efficiency" condition (2.3) says that it distributes to the players the entire amount available to the all-player set. The positivity condition says that in monotonic games all coalitions have non-negative values; this is plausible because no coalition has negative worth itself, nor can it decrease the worth of another coalition when joining it. There is a close correspondence between this definition of value and the axiomatization (cf. Shapley, 1953a, or Appendix A, below) of the value for finite games; this will be explored further below.

Another reasonable condition that we might wish to impose on φ is continuity; but before that can be done, we must define a topology on BV. This will be done in Section 3. It will turn out that there is a close relationship between positivity and continuity and that little would be changed if we replaced the positivity condition in the definition of value by an appropriate continuity condition.

Still another likely condition, plausible but unneeded at present, is that of "invariance under strategic equivalence" (cf. von Neumann and Morgenstern, 1953, p. 245), i.e. if v [member of] Q and a [member of] FA [intersection] Q, then φ(v + a) = φfv + a. With linearity, this amounts to saying that φ is a projection on FA, i.e. for any v [member of] FA [intersection] Q we have φv = v. (In the usual terminology, a game v [member of] FA would be called "inessential.") Some discussion of the use of a projection axiom, in connection with the relaxation of assumption (2.1), will be found near the end of Section 48.

A slightly different approach to the axiomatization of value is as follows: One speaks only of monotonic games v; the value φv is always a nonnegative measure (finitely additive); and the linearity condition is replaced by the condition φ(αv + βw) = α φw + βφw, where α and β are non-negative real numbers. Conditions (2.2) and (2.3) remain unchanged. This approach is entirely equivalent to the one we have adopted.

A non-atomic game is meant to represent a game with many players, each of whom is individually insignificant. Examples are economies with many economic agents (see Chapter VI), elections with many voters, and so on. In such a game, it is sometimes useful to think of an individual player not as a single point s in I, but as an "infinitesimal subset" ds of I; see Section 29 for a discussion of this viewpoint.

In a finite game with player space N, a payoff vector is simply a member x of EN, i.e. a function from N to the reals (see Appendix A). When we are thinking in terms of coalitions rather than individuals, it is convenient to think of the payoff vector x as a measure on N, defined for all S [subset] N by

x(S) = [summation over (ι [member of] S]] x(i);

here x(S) signifies the total payoff to S under the outcome x. The measures on N are of course in natural one-one correspondence with the points in EN. Thinking of a payoff vector as a measure is especially useful in connection with non-atomic games, or more generally with arbitrary games on (I, C). In such games a payoff vector may often be represented by a non-atomic measure μ; this means that the individual player ds gets the infinitesimal payoff μ(ds), whereas the total payoff to a coalition is often a positive number. For the sake of generality, we define a payoff vector of a game on (I, C) to be any member of FA.

Just as the games v defined here generalize the games with finite player sets, so the value defined here generalizes the value on finite games (cf. Shapley, 1953a, or Appendix A, below). The parallelism is indeed very close. In both cases the value assigns to each game a payoff vector, is a linear operator, and satisfies symmetry ((2.2) or (A.2)) and efficiency ((2.3) or (A.3)) conditions. The positivity condition does not appear explicitly in the finite treatment, but only because, in that context, it follows from the other axioms. Similarly, the dummy axiom (A.4) does not appear explicitly in this section, but only because, for non-atomic games obeying (2.1), it follows from the other conditions (see Note 4).

Two basic assumptions about the nature of a game are implicit in the use of a real-valued set function to describe it, namely the assumptions of unrestricted side payments and fixed threats. These are well known in the literature2 for the case of finite player sets, and they are not essentially different when there is a continuum of players. It is perhaps worthwhile, however, simply to restate the side payment condition in the continuum case. This says that not only can each coalition S obtain for its members a total of v(S), but it can also distribute this total among its members in any way it pleases. Thus, if v is any member of FA with v(S) = v(S), then S can act so that each T [subset] S will obtain v(T), or in other words, so that each "member" ds of S will obtain v(ds).

(Continues...)

---

Excerpted from Values of Non-Atomic Games by Robert J. Aumann, Lloyd S. Shapley. Copyright © 1974 The Rand Corporation. Excerpted by permission of PRINCETON UNIVERSITY PRESS.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---

Table of Contents

• Frontmatter, pg. i
• Contents, pg. vii
• Preface, pg. ix
• Introduction, pg. 1
• Chapter I. The Axiomatic Approach, pg. 11
• Chapter II. The Random Order Approach, pg. 93
• Chapter III. The Asymptotic Approach, pg. 126
• Chapter IV. Values and Derivatives, pg. 141
• Chapter V. The Value and the Core, pg. 167
• Chapter VI. An Application to Economic Equilibrium, pg. 175
• Chapter VII. The Diagonal Property, pg. 252
• Chapter VIII. Removal of the Standardness Assumption, pg. 281
• Appendix A. Finite Games and Their Values, pg. 295
• Appendix B. e-Monotonicity, pg. 301
• Appendix C. The Mixing Value of Absolutely Continuous Set Functions, pg. 304
• References, pg. 315
• Index of Special Spaces and Sets, pg. 321
• Index, pg. 323