BRICS RS-96-47 A. Peke� c: Meaningful and Meaningless Solutions for Cooperative N-person Games

BRICS

Basic Research in Computer Science

Meaningful and Meaningless Solutions for Cooperative N-person Games

Aleksandar Peke� c

BRICS Report Series RS-96-47 ISSN 0909-0878 December 1996 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1996, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through World Wide Web and anonymous FTP:

http://www.brics.dk/
ftp://ftp.brics.dk/pub/BRICS

This document in subdirectory RS/96/47/

Meaningful and Meaningless Solutions for Cooperative N-person Games

Aleksandar Pekeč

BRICS^{∗}

Department of Computer Science University of Aarhus Ny Munkegade DK-8000 Aarhus C, Denmark

                  http://www.brics.dk/∼pekec/

Abstract

Game values often represent data that can be measured in more than one acceptable way (e.g., monetary amounts). We point out that in such a case a statement about cooperative n-person game model might be “meaningless” in the sense that its truth or falsity depends on the choice of an acceptable way to measure game values. In particular we analyze statements about solution concepts such as the core, stable sets, the nucleolus, the Shapley value (and its generalizations).

Keywords: Cooperative n-person Games, Measurement, Sensitivity Analysis.

∗ Basic Research in Computer Science, Centre of the Danish National Research Foundation.

1 Introduction

The mathematical theory of cooperative n-person games and related solution concepts aims to model and analyze problems arising in various disciplines from operations research, management science, decision analysis, to economics, sociology and political science. (For example, cost–allocation, voting power. For a detailed discussion of applications of n-person games see [12].) We will consider games in characteristic function form. In other words, a cooperative n-person game is a function v : 2^{N} → R such that v(∅) = 0. (N is a finite set of n > 1 elements and 2^{N} denotes the set of all subsets of N. Throughout we will identify N with [n] = {1, 2, …, n}.) Elements of N are called players and a nonempty S ⊆ N is called a coalition. v(S) is a worth (value) of coalition S. Coalition N is also called the grand coalition, and v(N) is the total value of the game v. Real numbers v(S), ∅ ≠ S ⊆ N, are called game values (or values of the game v). Note that v(∅) = 0 is not considered a game value (since it is defined to be zero for every game). A solution to a cooperative game v should present a “fair allocation” of the total value of the game, v(N), among the players. A vector x = (x_{1}, …, x_{n}) such that ∑_{i=1}^{n} x_{i} = v(N) (the condition known as Pareto-optimality) is a solution for the game v. There are various solution concepts proposing a “fair” solution(s) to the game.

In many applications, game values represent data measured on some scale of measurement (for example, the amount of money can be expressed in dollars, German marks, or any other monetary unit). In this paper we will analyze how the choice of an acceptable way to measure game values effects the conclusions that can be drawn from the cooperative n-person game models. In particular, we consider statements about several widely used solution concepts such as the core, stable sets, the nucleolus, the Shapley value (and some of its generalizations), and analyze whether the truth or falsity (i.e., the truth value) of these statements is independent of the (acceptable) choice of the scale of measurement of the game values.

Let us give a simple example to illustrate the type of questions that will be discussed in this paper:

Example 1 Suppose that two companies X and Y consider a merger. It is estimated that company X is worth $1 million and company Y is worth $2 million. Analysts estimate the value of the possible corporation XY resulting from merging X and Y as $5 million. Owners of both companies need to decide on their share in the possible corporation XY. Obviously, the owners of X would not agree to any deal giving them less than one fifth of the ownership of XY (because their company X alone is worth $1 million, which is one fifth of the estimated value of XY). Similarly, the owners of Y would not agree to any deal giving them less than two fifths of the ownership of XY. Hence, any agreement giving P % ownership of XY to the owners of X might be viewed acceptable as long as 20 ≤ P ≤ 60. (Note that this conclusion is independent of the choice of the monetary unit representing values of X, Y and XY.) Suppose that, by the merger agreement, the owners of X were given 30% of the ownership of XY.

What if the government is about to deregulate the industry and any company doing business (X, Y, or XY) would not need to pay flat licence fee K anymore? For example, suppose that the licence fee was K = $1 million. Then the value of X, Y, and XY are 2, 3, and 6 million dollars, respectively. In such a case, any agreement giving P % ownership of XY to the owners of X might be viewed acceptable as long as 33.˙3 ≤ P ≤ 50. Suddenly, the deal giving only 30% of the ownership of XY to the owners of X becomes totally unacceptable. Hence, if the new licence fee is not known in advance, any agreement on the number P might be ill fated.

The situation like this might be represented as a cooperative n-person game (in this case n = 2) defined by v : {{X}, {Y }, {X, Y }} → R (where the game value v(S) denotes the estimated value of the company merging all companies from the set S). As this example demonstrates, one might question whether any solution concept might be used if the game values depend on K as described.

In Section 2 we briefly introduce the language of the measurement theory, introduce “ratio”, “interval” and “ordinal” scales, and define the concept of “meaningfulness” which will play the central role throughout the paper. Informally, a statement about the game v is meaningful if its truth value does not depend on the choice of an acceptable way to measure game values v(S), S ⊆ N, S ≠ ∅. In Section 3 we first recall definitions of the solution concepts that will be considered and define some additional terminology. We also show that, whenever the game values are measured on a “ratio scale”, the conclusions about solution concepts are meaningful. As demonstrated in Section 4, when game values are measured on “interval scales”, “positive” statements about solution concepts are almost exclusively meaningless. In other words, in the case of interval scales, a statement that an allocation of v(N) among the players is “fair” (according to a solution concept that is considered) is meaningful only if the statement is false. In Section 5 we demonstrate that there is no hope for a solution concept which would yield “positive” statements in the case where game values are measured on an “ordinal scale”. Finally, in Section 6 we discuss the results presented. For example, we argue that the Shapley value (and its generalizations), in some sense, is a more robust solution concept than the core, stable sets, or the nucleolus. As an attempt to simplify the exposition and spare the casual reader of technical details, all the proofs are excluded from the main body of the paper and can be found in the Appendix.

2 Scales of Measurement, Admissible Transformations, Meaningfulness

In this section we briefly (and informally) introduce the language of measurement theory. There exists an extensive literature on this subject (for example , [3, 14, 4, 5, 6]), and we will follow [8]. A scale of measurement is a mapping which assigns real numbers to objects being measured in such a way that certain empirical relations are preserved. An admissible transformation of scale is a transformation Φ of scale values which leads to another acceptable mapping, i.e., one which again preserves the empirical relations. For example, all exchange rates are of the form Φ(x) = αx, α > 0. Similarly, we can measure mass in pounds or kilograms and here we have Φ(x) = 2.2x where x is the amount in kg. and Φ(x) is the amount in lb. The set of all admissible transformations of a particular scale of measurement defines a scale type. In this paper we will consider the scales types that often arise in practice:

• Ratio Scales. If the set of all admissible transformations of the scale of measurement is {Φ(x) = αx : α > 0} we are talking about a ratio scale (“objects are measured on a ratio scale”). In the case of ratio scales everything is defined up to the choice of the unit of measurement. Measurement of mass, currency amounts, time (seconds, minutes, hours) are examples of ratio scales. In many applications, game values v(S) represent the amount of money (or some other measure of cardinal utility) that coalition S can get (or would need to pay). In such a case, game values represent data measured on a ratio scale and one can express game values in terms of any monetary unit. For example, if the game values v(S) represent the amount of money in dollars, then the values Φ(v(S)), where Φ(t) = 1.5t, represent the amount of money in German marks (provided that the exchange rate is 1.5 German marks for one dollar). Hence, instead of analyzing game v, one might want to analyze game Φ(v) whose game values are Φ(v(S)), S ⊆ N, S ≠ ∅.

• Interval Scales. An interval scale is a scale where the set of the admissible transformations is {Φ(x) = αx + β : α > 0, β ∈ R} (there is a choice of the unit and the zero point of measurement). For example, temperature is measured on an interval scale: Φ(x) = \frac{9}{5}x + 32 is a transformation from ^{o}F to ^{o}C. If the game values represent monetary amounts, and if these values also depend on an unknown flat fee (which is the same for all game values; e.g., government licence fee, fixed start-up costs), then this is the same as to say that the game values are measured on an interval scale. (Note that Φ(t) = α(t + K) = αt + αK is an admissible transformation of game values for any α > 0 and any K. K represents the flat fee, and α is the exchange rate).

• Ordinal Scales. In many instances very precise data is not available and the most that is given is a relationship among data. For example, we can only have ordering or a preference list of all the game values. (In other words, for any two coalitions S and T we can only say whether the worth of the coalition S is greater or equal than the worth of T, i.e., whether v(S) ≥ v(T) does or does not hold.) In such a case any increasing function Φ is an admissible transformation. If only the relative ordering among the data is known, then {Φ : Φ is increasing} is the set of the admissible transformations and we say that data is measured on an ordinal scale.

In many situations, the problem data must be nonnegative (positive) numbers. For example, if the game values v(S) represent the time that is needed to serve all players from S (note that v(S) might not be known precisely but, say, just as an ordinal scale data, e.g. it might only be known that more time is needed to serve players from T than to serve players from S), and in such a case v(S) must be positive (nonnegative) numbers. Whenever data is restricted to positive (nonnegative) numbers, we have related scale types: positive (nonnegative) ratio scale (the set of the admissible transformations is {Φ(x) = αx : α > 0}), positive (nonnegative) interval scale (the set of the admissible transformations for a game v whose values are measured on a positive (nonnegative) interval scale is {f(x) = αx+β : α > 0, αv(S)+β is positive(nonnegative) for every coalition S}), and positive (nonnegative) ordinal scale (the set of the admissible transformations is the set of all increasing functions on the set of all positive (nonnegative) real numbers.

The central measurement theory concept that will be used in this paper is that of meaningfulness. We say that a statement involving scales of measurement is meaningful if its truth value is unchanged after applying admissible transformations to all scales in the statement. Therefore, meaningful statements are unambiguous in their interpretation and they say something about fundamental relations among the objects being measured. Statements which are not meaningful are meaningless. Obviously, we cannot put much weight behind such statements since their truth value is an accident of the choice of an (acceptable) way to measure the objects in question.

It should be noted that the importance of the meaningfulness of the conclusions that can be drawn from mathematical models for various problems of operations research was first pointed out by Roberts [9]

In the rest of this section, we define meaningfulness of the statements about games. We first introduce additional notation:

For a game v : 2^{[n]} → R and a function Φ : R → R, a game Φ(v), Φ(v) = Φ ∘ v : 2^{[n]} → R, is defined in a natural way:

Φ(v)(S) := Φ(v(S)), ∅ ≠ S ⊆ [n].

Note that Φ(v)(∅) = 0 by the definition of the game. Also note that Φ only needs to be defined on the image of v, v(2^{N} \ {∅}) and that the range of Φ might only be the positive (nonnegative) numbers.

For α ∈ R, the game αv is defined by (αv)(S) := αv(S) (i.e., αv = Φ(v) where Φ(t) = αt).

We will say that v is a ratio scale game (interval scale game, ordinal scale game, positive (nonnegative) interval scale game, …) if v is a game whose game values represent data measured on a ratio scale (interval scale, ordinal scale, positive(nonnegative) interval scale, …).

Let P[v] be a statement about the game v where the game values represent data measured on some scale of measurement S. Let AT (S) denote the set of all admissible transformations of the scale of measurement S.

We say that P[v] is a meaningful statement about the game v if

∀Φ ∈ AT (S) : P[v] ⇔ P[Φ(v)].

If P[v] is not meaningful, we say that P[v] is meaningless. In other words, P[v] is a meaningless statement about the game v if

∃Φ ∈ AT (S) : P[v] ⇎ P[Φ(v)].

Remark 2 Let the game values of v represent data measured on a scale S and let Φ ∈ AT (S). Then P[v] is meaningful if and only if P[Φ(v)] is meaningful. This follows directly from the definition of meaningfulness.

Example 3 We say that a game v is superadditive if

∀S, T ⊆ [n], S ≠ ∅ ≠ T, S ∩ T = ∅ : v(S) + v(T) ≤ v(S ∪ T).  (1)

In some sense, superadditivity indicates that any group of players would be at least as well off (as a group) if they form one big coalition, than if they partition themselves in several coalitions. Most of the games, as mathematical models for practical problems, are superadditive. Some authors even require (1) to hold as a part of the definition of a game (for example, Roberts [7]).

If v is a ratio scale game, then the statement P[v]= “v is superadditive” is meaningful. Obviously,

v(S) + v(T) ≤ v(S ∪ T) ⇔ αv(S) + αv(T) ≤ αv(S ∪ T)

for any α > 0.

If v is an interval scale game then the statement P[v] is meaningless. For any pair of disjoint nonempty S, T ⊆ [n] and any Φ_{β}(t) = t + β (which is an admissible transformation with α = 1) we get

Φ_{β}(v)(S) + Φ_{β}(v)(T) ≤ Φ_{β}(v)(S ∪ T) ⇔ β ≤ v(S ∪ T) − v(S) − v(T)

Hence, if we choose β_{1} and β_{2} such that

β_{1} ≤ min{v(S ∪ T) − v(S) − v(T) : S, T ⊆ [n], S ≠ ∅ ≠ T, S ∩ T = ∅} < β_{2},

then the game Φ_{β_{1}}(v) is superadditive while the game Φ_{β_{2}}(v) is not. Hence, the conclusion that v is a superadditive game is meaningless since either P[v] ⇎ P[Φ_{β_{1}}(v)] or P[v] ⇎ P[Φ_{β_{2}}(v)].

3 Meaningful Solution Concepts: The Case of Ratio Scales

In this section we first introduce the solution concepts that will be considered and then analyze the meaningfulness of the statements about these solution concepts for ratio scale games.

The following notation will be handy: for any x ∈ R^{n} and S ⊆ N let

x(S) = ∑_{i∈S} x_{i}.

We define x(∅) := 0. In this notation, x = (x_{1}, …, x_{n}) is a solution if x(N) = v(N).

We will also use v_{max} and v_{min} to denote the maximum and minimum among all game values:

v_{max} := max_{S≠∅} v(S) and v_{min} := min_{S≠∅} v(S).

It is reasonable to assume that any solution x for the game v should guarantee that player i will get at least as much as v({i}). (Otherwise, this player would be better off if (s)he leaves the grand coalition). This principle is called individual rationality, i.e., x ∈ R^{n} satisfies individual rationality for the game v if x_{i} ≥ v({i}), for all i = 1, …, n. Solutions (i.e., Paretooptimal vectors) that are also individually rational (x_{i} ≥ v({i})) are called imputations. We will denote the set of all imputations of the game v by M, i.e.,

M = M(v) = {x ∈ R^{n} : x(N) = v(N), x_{i} ≥ v({i}), i = 1, …, n}

Consider two solutions x, y. We say that x dominates y (and write x ≻ y) if there exists a nonempty S such that

x_{i} > y_{i} for all i ∈ S and x(S) ≤ v(S)  (2)

Therefore, if x ≻ y then y is unlikely to be considered as a “fair” allocation of v(N) since players from S would be better off by forming their own coalition S and distributing v(S) according to x.

The core of the game v (introduced by Shapley [11] and independently by Gillies [2]) is the set

C = C(v) := {x : x(N) = v(N) and x(S) ≥ v(S), S ⊆ N}.

The core is the set of all possible solutions where no coalition has an incentive to secede from the grand coalition. Note that C = ∅ indicates that there is no solution such that everyone in the grand coalition is satisfied, i.e., for any solution x, there is a coalition S which is dissatisfied with x.

The first solution concept for n-person games was the concept of the stable set introduced by von Neumann and Morgenstern [15]. The set V ⊂ M is an externally stable set for game v if for every solution y ∉ V there exists x ∈ V such that x ≻ y. The set V is stable if it is a minimal externally stable set, i.e., if it is externally stable and no W ⊂ V is externally stable. Note that any stable set V partitions M in a natural way: M = V ∪ (M \ V) where M \ V is exactly the set of all vectors dominated by some element of V:

M \ V = {y ∈ M : ∃x ∈ V s.t. x ≻ y}.

Clearly, if there exists a stable set V, then C ⊆ V ⊂ M. In some sense, a stable set is a relaxation of the core since it just gives a set of distributions x that have a chance to be acceptable to all players in the sense that if y ∉ V then ∃x ∈ V such that x ≻ y.

In many cases it is important to have a single solution for the game. In this sense, the core and a stable set of the game might not be satisfactory solutions. In what follows we recall definitions of some widely used single point solution concepts.

For a solution x we define the excess of the coalition S with respect to x:

e^{v}(S, x) = e(S, x) := v(S) − x(S).

(Note that e(∅, x) = 0). e(S, x) is a measure of the dissatisfaction of coalition S with distribution x. The larger e(S, x) is, the more dissatisfied players from S are with distribution x (the more they can get by seceding). A “democratic” solution for a game would be to minimize the maximal dissatisfaction of any of the coalitions. This idea was introduced by Schmeidler [10] More precisely, for a given solution x, we consider a 2^{n}-dimensional vector e(x) where the coordinates of e(x) are the numbers e(S, x), S ⊆ N, arranged in nonincreasing order. The nucleolus of the game is a solution x such that e(x) is lexicographically smaller than e(y) for any other solution y. In other words, for i := min{j : e(x)_{j} ≠ e(y)_{j}} we have e(x)_{i} < e(y)_{i}. It is not so obvious that the nucleolus always exists and that it is unique [10](1994). The nucleolus minimizes maximal dissatisfaction and, in contrast to stable set and core, is not a set but a single distribution, and it always exists.

Maybe the most important solution concept for n-person games is the Shapley value (introduced by Shapley [11]). For every player i we define

s_{i} = s_{i}(v) := ∑_{S⊆N−\{i\}} \frac{|S|!(n − |S| − 1)!}{n!}[v(S ∪ \{i\}) − v(S)].  (3)

The vector s = s(v) := (s_{1}, …, s_{n}) is the Shapley value of the game v.

Shapley’s idea leads to the whole new class of value solutions for n-person games: Suppose that we are given constants c(S, i) for all i ∈ N and all S ⊆ N − {i}. Then we can define the c-value of the game v to be the vector c(v) = c = (c_{1}, …, c_{n}) where

c_{i}(v) = ∑_{S⊆N−{i}} c(S, i)[v(S ∪ {i}) − v(S)].  (4)

(For example, by taking C(S, i) = 1 for all i and all S, we obtain the Banzhaf value [1]) There is no reason to assume that the vector [c(v)](N) is a solution, i.e., that [c(v)](N) = v(N) (in fact, the Shapley value is the only c-value which is a solution for any game v [11]). However, multiplying c by v(N)/[c(v)](N) (provided [c(v)](N) ≠ 0), we obtain a solution. We call such solution the c-index. Any c-index is a measure of power of players in the game and gives consequent distribution of v(N) If, in addition, c(S, i) = c(S) (independent of i) we say that the c-value (and the c-index) is symmetric.

We will analyze the meaningfulness of the solution concepts introduced in this section. As already mentioned, the game values, v(S), may represent data measured on a certain scale of measurement. In such a case, it makes sense to investigate how much of the total value of the game one player should get compared to how much of that value another player should get, but it makes no sense to hope for a fixed solution x as the following Proposition shows:

Proposition 4 For any interval (ordinal) scale game v and any vector x, the statement P[v]=”x is a solution for v” is meaningless. Similarly, for any ratio scale game and any vector x such that v(N)x(N) > 0, P[v] is a meaningless statement.

Instead of solutions x (x(N) = v(N)), it is natural to consider normalized solutions y = (1/v(N))x (y is the normalization of x). Note that y also describes the allocation (prescribed by x) of the total value of the game, v(N), among the players. Also note that y(N) = 1 (provided that x(N) = v(N) ≠ 0), so determining whether y is a normalized solution does not depend on the scale of measurement of the game values.

The following notation will be handy: for a set D ⊆ R^{n} and λ ∈ R we define

αD := {αx : x ∈ D}.

If there exists α > 0 such that ∀x ∈ D, x(N) = α^{−1}, then ∀αx ∈ αD, (αx)(N) = 1, and we say that αD is the normalization of D. L The following theorem shows that there is a natural correspondence between solution concepts for the game v and αv.

Theorem 5 For any game v,

1. x ∈ C(v) if and only if αx ∈ C(αv). In other words, C(αv) = αC(v).

2. V is a stable set for v if and only if αV is a stable set for αv.

3. x is the nucleolus of v if and only if αx is the nucleolus of αv.

4. Let c(S, i), i = 1, …, n, and S ⊆ N − {i}, be given. Then x is the c-index of v if and only if αx is the c-index of αv

A direct consequence of this result is that, in the case of ratio scale games, it is meaningful to assert that a vector x is (in) the normalization of any of the solution concepts that we have introduced. In other words, the conclusions about the existence of the normalization of the core, a stable set, the nucleolus, or a c-index are meaningful for ratio scale games.

Corollary 6 Let D ⊆ {x ∈ R^{n} : x(N) = 1}. Suppose P[v] is the statement “D is the normalization of the core (a stable set, the nucleolus, the c-index) for game v.” Then P[v] is a meaningful statement for any ratio scale game v.

4 Meaningless Solution Concepts: The Case of Interval Scales

In this section we discuss the meaningfulness of the statement P[v] from Corollary 6 for interval scale games. The analysis in the case of ratio scale games was straightforward (and almost trivial). Unfortunately, things get much more complicated in the case of interval scale games. Furthermore, the results are negative: Example 1 (revisited): Let v : 2^{[2]} → R be a game whose game values are v({1}) = 2, v({2}) = 3, and v({1, 2}) = 6. Then the core of v is the set C(v) = {(x_{1}, x_{2}) : x_{1} ≥ 2, x_{2} ≥ 3, x_{1} + x_{2} = 6}, and the normalization of C(v) is the set D(v) = {(x_{1}, x_{2}) : x_{1} + x_{2} = 1, .˙3 ≤ x_{1} ≤ .5}.

If v is an interval scale game, then, for every Φ(t) = αt + β, α > 0, the game values of Φ(v) are an acceptable way of representing the game values of v. (In the situation presented in Example 1, α might be viewed as the exchange rate, and β might represent a government licence fee or a government premium, say in the form of a flat tax break.)

Consider the game Φ_{0}(v) where Φ_{0}(t) = t − 1. Then, [Φ_{0}(v)]({1}) = 1, [Φ_{0}(v)]({2}) = 2, and [Φ_{0}(v)]({1, 2}) = 5. Thus, C(Φ_{0}(v)) = {(x_{1}, x_{2}) : x_{1} ≥ 1, x_{2} ≥ 2, x_{1} + x_{2} = 5} and the normalization of C(Φ_{0}(v)) is the set D(Φ_{0}(v)) = {(x_{1}, x_{2}) : x_{1} + x_{2} = 1, .2 ≤ x_{1} ≤ .6}.

Note that D(v) ≠ D(Φ_{0}(v)). For example, (.3, .7) ∈ D(Φ_{0}(v))\D(v). (In fact, it is straightforward to show that D(v) ≠ D(Φ(v)) for any increasing affine transformation Φ ≠ id. Furthermore, D(Φ(v)) = ∅, for any Φ(t) = αt + β where β > α > 0.)

Hence, the statement P[v]=“x is in the normalization of C(v)” might be meaningless.

We first note that without loss of generality we may always assume that v(N) = 1.

Remark 7 Let v be an interval scale game (positive interval scale game, nonnegative interval scale game). Note that there exists an admissible transformation Φ such that Φ(v(N)) = 1 (take Φ(t) = \frac{1}{v(N)}t if v(N) > 0, and take Φ(t) = t + 1 − v(N) if v(N) ≤ 0). and let P[v] be some statement about games. v. By Remark 2, P[v] is a meaningful statement if and only if P[Φ(v)] is a meaningful statement. In other words, in analysis of meaningfulness of P[v], we may always assume that v(N) = 1.

It is rather surprising that, for any interval scale game v, and for any normalized solution x that allocates “positive” share of the total value of the game to every player (i.e., any x such that x_{1} > 0, x_{2} > 0, …, x_{n} > 0 or in short notation: x ≥ 0), not only that there is an acceptable way to measure game values so that x is not in the normalization of the core, but there is also another acceptable way to measure game values so that x is in the normalization of the core. In other words,

Theorem 8 For any interval scale game v and any x > 0 such that x(N) = 1, the statement P[v]= “x is in the normalization of C(v)” is meaningless.

This result has several important consequences:

Corollary 9 For any D ⊆ {x ∈ R^{n}: x(N)= 1} and any interval scale game v, the statement P[v]= “D is the normalization of the core (a stable set) of v” is meaningless.

Corollary 10 For any interval scale game v and any vector x > 0 such that x(N) = 1, the statement P[v]= “x is in the normalization of M(v)” is meaningless.

Corollary 11 Let x be a vector, let v be an interval scale game, and let P[v] be the statement “x is in the normalization of C(v)”. If P[v] is meaningful, then it is false.

Corollary 11 shows that, in the case of interval scale games, no normalized solution x (regardless whether x > 0 or not) can be in the normalization of C(Φ(v)) for every admissible transformation Φ. Hence, if only normalized solutions that are in the normalization of C(v) are considered “fair”, then no interval scale game has a “fair” normalized solution (i.e., such statement is either false or meaningless). However, there can be solutions for which it is meaningful to say that they are “unfair” (i.e., a normalized solution which is not in C(Φ(v)) for any choice of an admissible transformation Φ).

Example 12 As demonstrated by Corollary 11, the statement P[v]= “x is in the normalization of C(v)” is meaningful only if it is false.

For example, consider an interval scale two player game v, defined by v({1}) = 2, v({2}) = 0, and v({1, 2}) = 1. Then x = (1, 0) cannot be in the normalization of C(Φ(v)) for any Φ(t) = αt + β, α > 0. This is because ([Φ(v)]({1, 2}))x = (α + β, 0) and [Φ(v)]({1}) = 2α + β. Hence ([Φ(v)]({1, 2}))x_{1} = α + β < 2α + β = [Φ(v)]({1}). Hence, P[Φ(v)] is false for any choice of an admissible transformation Φ.

Corollary 11 holds even in a more restrictive case when we require that all game values are positive, i.e., in the case of positive interval scale games. (In fact, the same is true for non-negative interval scales also.)

Theorem 13 Let v be a positive interval scale game and let P[v] be the statement “x is in the normalization of C(v)”. If P[v] is meaningful then it is false.

Corollary 14 Let v be a positive interval scale game and let P[v] be the statement “x is in the normalization of some stable set of v”. If P[v] is meaningful then it is false.

Now we turn our attention to single point solution concepts. In what follows, we will show that statements similar to statements of Corollary 11, Theorem 13, and Corollary 14 hold for the single point solution concepts that were introduced in Section 3. More precisely, for almost every interval scale game v, the statement that x is the normalization of a single point solution of v is meaningful only if it is always false (i.e., false for every game Φ(v) where f(t) = αt + β, α > 0). However, we first present a class of interval scale games for which this statement is always true.

We say that the game v is symmetric if for any permutation π of [n], and any S ⊆ N, v(π(S)) = v(S). This is clearly equivalent to saying that for every S ⊆ N, v(S) = f(|S|) for some function f.

Proposition 15 Let v be a symmetric game. Then the normalization of the nucleolus and any symmetric c-value is x = \frac{1}{n}(1, 1, …, 1).

Corollary 16 If v is a symmetric interval scale game then the statement P[v]= “x is the normalization of the nucleolus (a symmetric c-value)” is meaningful.

For any interval scale game, the equidistribution of the total value of the game (i.e., a solution whose normalization is \frac{1}{n}(1, …, 1)) is the only solution that has a chance to be the normalization of the nucleolus for any choice of an acceptable way to measure game values. In order to prove this, we need the following Lemma.

Lemma 17 Let v be a game such that v(N) = 1. Suppose that there exists a y such that for arbitrary large β, y is the normalization of the nucleolus of the game Φ(v) where Φ(t) = t + β. Then

y = \frac{1}{n}(1, 1, …, 1).

Theorem 18 Let y ≠ \frac{1}{n}(1, 1, …, 1) be the normalization of the nucleolus of an (positive) interval scale game v Let P[v] be the statement “y is the normalization of the nucleolus”. If P[v] is meaningful then it is false.

Finally, we show that similar results hold for c-values. We first give an example: Example 1 (revisited again): Let v and Φ_{0}(v) be as before, that is, let v : 2^{[2]} → R be a game whose game values are v({1}) = 2, v({2}) = 3, and v({1, 2}) = 6, and let Φ_{0}(t) = t − 1 (i.e., [Φ_{0}(v)]({1}) = 1, [Φ_{0}(v)]({2}) = 2, and [Φ_{0}(v)]({1, 2}) = 5).

The Shapley value of v is s(v) = 6(\frac{5}{12}, \frac{7}{12}), and the Shapley value of Φ_{0}(v) is s(Φ_{0}(v)) = 5(\frac{2}{5}, \frac{3}{5}). Hence, \frac{s(v)}{v(N)} = (\frac{5}{12}, \frac{7}{12}) ≠ (\frac{2}{5}, \frac{3}{5}) = \frac{s(Φ_{0}(v))}{Φ_{0}(v)(N)}. Therefore, for the interval scale game v and any y, the statement P[v]= “\frac{1}{v(N)}s(v) = y” cannot be a meaningful true statement (because y ≠ (\frac{2}{5}, \frac{3}{5}) or y ≠ (\frac{5}{12}, \frac{7}{12}).

Theorem 19 Let y ≠ 0, and let c(v) ≠ 0 be the symmetric c-value of an (positive) interval scale game v Suppose that [c(v)](N) ≠ 0 and suppose that the statement P[v]= “\frac{1}{[c(v)](N)}c(v) = y” is true. Then P[v] is meaningful if and only if one of the following holds:

1. y is the normalization of (c(∅, 1), c(∅, 2), …, c(∅, n)). or

2. (c(∅, 1), c(∅, 2), …, c(∅, n)) = 0

For example, both the Shapley value and the Banzhaf value are symmetric c values with c(∅) = 1/n in the former and c(∅) = 1 in the latter case. Therefore, condition 2. of Theorem 19 is not satisfied and in these cases a true statement P[v] (from Theorem 19) is meaningful if and only if y = 0 or y = \frac{1}{n}(1, 1, …, 1).

5 An Impossibility Result: The Case of Ordinal Scales

It should be noted that all results from Section 4 extend to ordinal scale games. This is because every admissible transformation for interval scale games, Φ(t) = αt + β, α > 0, is also an admissible transformation for ordinal scale games (since Φ is increasing). Also, the proof of the only “positive” result, Corollary 16, only requires that Φ is injective (so, Corollary 16 holds for ordinal scale games also). In other words, replacing “interval scale” with “ordinal scale” throughout Section 4 yields results about meaningless statements about ordinal scale games.

In order to show that, essentially, there is no solution concept which would yield meaningful conclusions for every ordinal scale game, we need a slightly different point of view on ordinal (ratio, interval) scale games.

Let u, v be two ordinal scale n-person games. We say that u ∼ v if there exists an admissible transformation Φ (i.e., increasing function) such that u = Φ(v). Note that ∼ is an equivalence relation on the set of all n-person games. The number of different equivalence classes is the number of different ordinal scale games (in the sense that they do not present the same game whose game values are measured in different but acceptable ways). This can be generalized for ratio and interval scale games: if u, v are two ratio (interval) scale games, then we say that u ∼ v if there exists an admissible transformation Φ such that u = Φ(v). Relation ∼ is an equivalence relation and the number of different equivalence classes is the number of different ratio (interval) scale games. (In fact, any group G of real valued functions defines an equivalence relation ∼: u ∼ v ⇔ ∃f ∈ G:u = Φ(v)). Hence, ratio (interval, ordinal) scale games can be viewed as equivalence classes defined by the equivalence relation ∼ on the set of all n-person games (u ∼ v ⇔ u = Φ(v) for some admissible transformation Φ of game values of v).

Proposition 20 Let n > 1. There are

(r) uncountably many ratio scale n-person games.

(i) uncountably many interval scale n-person games.

(o) finitely many ordinal scale n-person games. More precisely, the number of ordinal scale n-person games is the number of preferential assignments of 2^{n} − 1 objects.

Remark 21 There are 13 ordinal scale two-player games, 47293 ordinal scale three-player games, 230283190977853 ordinal scale four-player games … (that is, the number of preferential assignments of 3, 7, 15,… objects). More about the number of preferential assignments can be found in [13].

Note that there is a natural 1-1 correspondence between n-person games and R^{2^{n}−1}: we just list all game values in the vector form

v = (v({1}), v({2}), v({1, 2}), v({3}), v({1, 3}), …, v({2, …, n}), v([n]))

In this notation, any singe point solution concept is just a function f : R^{2^{n}−1} → R^{n} such that [f(v)](N) = v(N). Similarly, a normalized solution concept is a function f : R^{2^{n}−1} → {x ∈ R^{n} : x(N) = 1}. The other solution concepts can also be viewed as functions. For example, the normalization of the core can be represented as a function f : R^{2^{n}−1} → {D ⊂ R^{n} : x ∈ D → x(N) = 1}. The truth value of any statement P[v] about the games can also be represented as a function f_{P[v]} : R^{2^{n}−1} → {True,False}. In this setup, P[v] is meaningful for a ratio (interval, ordinal) scale game v if and only if f_{P[v]} is a constant function on the v’s equivalence class (under ∼).

We will call a function f defined on the set of all n-person games, R^{2^{n}−1} non-degenerate if it attains infinitely many values, i.e., if the set f(R^{2^{n}−1}) is not finite. For example, (the normalization of) the core, a stable set, the nucleolus, the c-value, are all examples of non-degenerate functions. In the case of single point solution concepts (i.e., functions f : R^{2^{n}−1} → R^{n}) it is reasonable to expect that f is not a constant function and that f is continuous (small changes in game values result in small changes in the proposed solution for distribution of the total value of the game). Note that any such function is non-degenerate.

Unfortunately, there is no hope for a non-degenerate solution concept that would yield to meaningful conclusions in the case of ordinal scale games.

Theorem 22 Let f : R^{2^{n}−1} → T be a non-degenerate function defined on the set of all n-person games. Then there exists an ordinal scale game v such that, for any x ∈ T, the statement P[v] = “x = f(v)” is meaningful only if it is false.

A direct consequence of Theorem 22 is an impossibility result:

Corollary 23 There is no f : R^{2^{n}−1} → T such that both of the following hold:

(a) f is non-degenerate.

(b) For every ordinal scale game v, there exists x ∈ T such that the statement P[v] = “x = f(v)” is a meaningful true statement.

6 Concluding Remarks

In this paper we have considered the meaningfulness of various statements about the most common solution concepts for n-person games. We showed that these statements are meaningful in the case of ratio scale games (Section 3) but, except in some special cases, they are meaningless in the case of interval scale games (Section 4). In the case of ordinal scales, we have demonstrated that there is no hope that any “reasonable” solution concept would yield to meaningful true statements(Section 5).

From the point of view of measurement of game values, there is no reason to prefer any of the solution concepts to another. Our analysis can also be viewed as an attempt to compare the “robustness” of various solution concepts (in a sense of invariance under perturbations of data). We have analyzed robustness of several standard solution concepts under linear and affine scaling of game values (i.e., under admissible transformations for ratio and interval scales). However, more general approach (not necessarily along the lines of our presentation) is needed in order to understand how various solution concepts compare to each other and whether any of the solution concepts are more robust than others. A first step toward such analysis would be to define the concept of an “invariant transformation” for a solution concept (i.e., a transformation of game values which does not affect certain conclusions that might be drawn using a particular solution concept). Then, one would be able to compare different solution concepts by comparing corresponding sets of invariant transformations.

Although we have shown that, in the case of interval scale games (i.e., under affine scaling of game values), all solution concepts that were considered yield meaningless conclusions, c-values should be considered more robust than the other solution concepts. Namely, if we redefine a game to be any function v : 2^{N} → R (i.e., if v(∅) can also be any real number and be considered a game value), then all the results concerning the core, stable sets, and the nucleolus still hold (because ∅ didn’t play any role in the ratio scale considerations and it doesn’t change anything in the interval scale considerations of the core, a stable set, and the nucleolus). However, the statement P[v]= “x is the normalization of a symmetric c-value” would be meaningful for any interval scale game v and any c-value. This is obvious from (4) since αv(S) + β − (αv(T) + β) = α(v(S) − v(T)). In other words, normalized c-values are invariant under affine scaling of game values (provided that v(∅) is also considered a game value), while the normalizations of the core, stable sets, or nucleolus are not. Hence, in some sense, c-values (such as the Shapley value and the Banzhaf value) are more robust solution concepts.

Finally, the reader should note that the aim of this paper is not to present an exhaustive analysis of the meaningfulness of all solution concepts for cooperative n-person games (we have not considered several well-known concepts such as the kernel and the bargaining set, neither we have discussed solution concepts for non-cooperative games such as Nash equilibria). Our goal is to point out that information about scales of measurement of game values (as well as any other type of invariance) is important and should not be overlooked not only in sensitivity analysis of various solution concepts, but whenever cooperative n-person games are used as a mathematical model for a practical problem.

Appendix

Proof of Proposition 4. We need to find two admissible transformations, Φ_{1}, Φ_{2} such that P[Φ_{1}(v)] is true and P[Φ_{2}(v)] is false (i.e., [Φ_{1}(v)](N) = x(N) ≠ [Φ_{2}(v)](N)). For Φ_{1}, take Φ_{1}(t) = t−v(N)+x(N) (Φ_{1}(t) = \frac{x(N)}{v(N)}t in the case of ratio scale games). For Φ_{2}, take Φ_{2}(t) = t − v(N) + x(N) + 1 (Φ_{2}(t) = 2\frac{x(N)}{v(N)}t in the case of ratio scale games). Proof of Theorem 5. Straightforward from definitions of various solution concepts. First note that x is a solution for v if and only if αx is a solution for αv, α > 0. Also note that we only need to prove the sufficiency in each of the four statements. This is because, for any α > 0, the necessity direction is just the sufficiency direction for the game αv with α^{−1}.

1. (core) We just need to check that for every S:

x(S) ≥ v(S) ⇒ αx(S) ≥ (αv)(S).

This is obvious since (αv)(S) = αv(S) for every S.

2. (stable set) Let y ∉ αV be a solution for the game αv. Then, there exists x ∈ V and S ⊆ N such that x ≻ α^{−1}y (note that α^{−1}y is a solution for v). In other words,

x(S) ≤ v(S) and x_{i} > α^{−1}y_{i}, ∀i ∈ S.

Hence, it follows immediately that

αx(S) ≤ (αv)(S) and αx_{i} > y_{i}, ∀i ∈ S,

i.e., αx ≻ y in the game αv. Therefore, αV is a stable set for the game αv.

3. (nucleolus) First note that for any solution x for the game v and any

S ⊆ N,

αe^{v}(S, x) = α(v(S) − x(S)) = e^{αv}(S, αx).

Hence, for any solution y for the game αv, e^{αv}(αx) is lexicographically smaller than e^{αv}(y) if and only if e^{v}(x) is lexicographically smaller than e^{v}(α^{−1}y). Since x is the nucleolus of v, αx is the nucleolus of αv.

4. (c-index) Note that for any S ⊆ N − {i} (including S = ∅):

(αv)(S ∪ {i}) − (αv)(S) = α(v(S ∪ {i}) − v(S)).

Therefore, from (4) we get that c_{i}(αv) = αc_{i}(v). From here we get that x is the c-index for v (i.e., if and only if αx is the c-index for αv (i.e., x = \frac{c(αv)}{[c(αv)](N)}).

Proof of Corollary 6. Note that D might be a singleton or even the empty set. We need to show that P[v] ⇔ P[αv] for any α > 0. This is a direct consequence of Theorem 5.

Proof of Theorem 8. By Remark 7 we only need to show that for every game v such that v(N) = 1 and every x > 0 such that x(N) = 1, there exist β_{1} and β_{2} such that

(Φ_{1}(v))(N)x ∈ C(Φ_{1}(v)) and (Φ_{2}(v))(N)x ∉ C(Φ_{2}(v))

where Φ_{1}(t) := t + β_{1} and Φ_{2}(t) := t + β_{2} (both Φ_{1} and Φ_{2} are admissible transformations). Note that

(Φ_{i}(v))(N)x(S) ≥ (Φ_{i}(v))(S)  (5)

is equivalent to

(1 + β_{i})x(S) ≥ v(S) + β_{i},

and this is equivalent to

x(S) − v(S) ≥ β_{i}(1 − x(S))  (6)

Note that for any nonempty S ≠ N, (1 − x(S)) > 0 (because x > 0 and x(N) = 1). Therefore choosing β_{1} such that

β_{1} ≤ min_{S≠N,∅} \frac{x(S) − v(S)}{1 − x(S)}

implies (5) for any S ≠ N, ∅. Hence, (Φ_{1}(v))(N)x ∈ C(Φ_{1}(v)). On the other hand, choosing β_{2} such that

β_{2} > max_{S≠N,∅} \frac{x(S) − v(S)}{1 − x(S)}

implies (5) is violated not only for one but for any S ≠ N, ∅. Hence, (Φ_{2}(v))(N)x ∉ C(Φ_{2}(v)). Proof of Corollary 9. This follows directly from Theorem 8. Note that it is meaningless to conclude that x > 0, x(N) = 1, belongs to the normalization of the core. Moreover, by the proof of Theorem 8, any such x is in the core of Φ_{1}(v) and it is not in the core of Φ_{2}(v) for some admissible transformations Φ_{1} and Φ_{2}. If P[v] were a meaningful statement, then the statement “x ∈ D” would be meaningful for any such x.

The same result holds for stable sets since the core is contained in any stable set. Proof of Corollary 10. The proof is almost the same as the proof of Theorem 8. Again, by Remark 7 we may assume that v(N) = 1. We will consider admissible transformations Φ of the form Φ_{β}(t) = t + β. Then Φ(v)(N)x ∈ M(Φ(v)) if and only if

(1 + β)x_{i} ≥ v({i}) + β, i = 1, …, n

and this is equivalent to

x_{i} − v({i}) ≥ β(1 − x_{i}), i = 1, …, n  (7)

Since x > 0 and x(N) = 1, we have (1 − x_{i}) > 0, and (7) can be rewritten as

\frac{x_{i} − v_{i}}{1 − x_{i}} ≥ β, i = 1, …, n.

Hence, Φ(v)(N)x ∈ M(Φ(v)) if and only if

β ≤ min_{i} \frac{x_{i} − v_{i}}{1 − x_{i}}

Therefore, there exists a small enough β such that (7) is violated (i.e., (Φ_{β}(v))(N)x ∉ M(Φ_{β}(v))) and large enough β > 0 such that (7) holds (i.e., (Φ_{β}(v))(N)x ∈ M(Φ_{β}(v))). Hence, P[v] is a meaningless statement.

Proof of Corollary 11. This is similar to the proof of Theorem 8. We will show that if P[v] is true (that is, v(N)x ∈ C(v)), then P[v] is meaningless. The proof is similar to the proof Theorem 8. We may again assume that v(N) = 1 (Remark 7). Also note that x(N) = 1 since v(N)x ∈ C(v) (i.e., v(N)x must be a solution). We only need to find β_{2} from the proof of Theorem 8 (β_{1} := 0 works because v(N)x ∈ C(v) by assumption).

Let nonempty S ⊆ N be such that x(S) ≠ 1 (such S exists; for example, for at least one i: x_{i} ≠ 1). For that S, we can find β_{2} such that

x(S) − v(S) < β_{2}(1 − x(S)).  (8)

(Note that (8) is the negation of (6).) Obviously, (8) is equivalent to

(1 + β_{2})x(S) < v(S) + β_{2}

(which is the negation of (5)). Hence, for Φ_{2}(t) = t + β_{2} we have

(Φ_{2}(v)(N))x(S) = (1 + β_{2})x(S) < v(S) + β_{2} = Φ_{2}(v(S))

and we conclude that x is not in the normalization of C(Φ_{2}(v)). Therefore, P[v] is a meaningless statement since P[v] is true and P[Φ_{2}(v)] is false. Proof of Theorem 13. Suppose that P[v] is true. We will show that P[v] is meaningless. Let α = \frac{1}{v(N)} > 0 and let Φ_{α}(t) = αt. Note that Φ_{α} is an admissible transformation of game values of v. Let w = Φ_{α}(v). If P[w] is false, then P[v] is meaningless.

Hence, we may assume that P[w] is true (i.e., x ∈ C(w); note that the normalization of C(w) is C(w) itself since w(N) = 1). Therefore, we have x(N) = 1 (since x is a solution for w) and x_{i} ≥ w({i}) > 0 for every i ∈ [n] (this is because x ∈ M(w) and because w({i}) ≥ w_{min} = αv_{min} > 0). Pick any {i} ⊂ N. Note that 0 < x_{i} < 1 (because x(N) = 1 and because x_{i} > 0 for every i ∈ [n]). Let β > 0 be such that

x_{i} − w({i}) < β(1 − x_{i}).

Let Φ_{β}(t) = t + β. Now we have

(Φ_{β}(w)(N))x_{i} = (1 + β)x_{i} < w({i}) + β = (Φ_{β}(w))({i})

and we conclude that P[Φ_{β}(w)] is false (i.e., x is not in the normalization of C(Φ_{β}(w))).

Finally, note that Φ_{β}(w) = (Φ_{β} ∘ Φ_{α})(v) and Φ(t) := Φ_{β} ∘ Φ_{α}(t) = αt + β is an admissible transformation of game values of v since β > 0. Hence, since P[v] is true and P[Φ(w)] is false, P[v] is meaningless. Proof of Corollary 14. The proof is the same as the proof of Theorem 13. Suppose that v(N)x is in some stable set of v. Then v(N)x ∈ M(v). Note that in the proof of Theorem 13 we have actually shown that if v(N)x ∈ M(v), then (Φ(v)(N))x ∉ M(Φ(v)). Hence, x cannot be in the normalization of any stable set of Φ(v). Therefore, if P[v] is true, then P[Φ(v)] is false, i.e., P[v] is meaningless. Proof of Proposition 15. Let π be a permutation of [n] and let π(x) be a vector defined by π(x)_{i} := x_{π^{−1}(i)}, for all i ∈ [n]. Then, since v is symmetric, v(N)x is the nucleolus of v if and only if v(N)π(x) is. But the nucleolus is a single point, hence we must have x = π(x) for any π, i.e., x = \frac{1}{n}(1, 1, …, 1).

Note that for any symmetric c value

c_{i}(π(v)) = c_{π(v)}(v), i = 1, …, n.

(This follows directly from (4).) By symmetry, π(v) = v for any permutation π, so we get that v(N)x is the symmetric c-value if and only if v(N)π(x) is. Therefore, we again get x = π(x) for any π, i.e., x = \frac{1}{n}(1, 1, …, 1). Proof of Corollary 16. For any injective Φ, Φ(v) is symmetric because (Φ(v))(S) = Φ(f(|S|)). Therefore, by Proposition 15, \frac{1}{n}(1, 1, …, 1) is the normalization of the nucleolus and any symmetric c-value of Φ(v). Proof of Lemma 17. By hypothesis, for any M > 0 there exists β > M such that y is the normalization of the nucleolus of Φ(v). Then without loss of generality we may assume M > n(v_{max} − v_{min}) − 1). Therefore, for any β > M,

\frac{1}{n}(β + 1) > v_{max} − v_{min}

holds. Let x := \frac{1}{n}(1, 1, …, 1). Then x(S) = |S|/n for any S ⊆ N. Let S, T ⊆ N such that 0 < |S| < |T | < n. Then

(x(T) − x(S))(β + 1) = (\frac{|T | − |S|}{n})(β + 1)
≥ \frac{1}{n}(β + 1)
> v_{max} − v_{min}
≥ v(T) − v(S),

which is equivalent to

v(S) − (β + 1)x(S) > v(T) − (β + 1)x(T).

From here we conclude

(Φ(v))(S) − (Φ(v))(N)x(S) = β + v(S) − (1 + β)x(S)
> β + v(T) − (1 + β)x(T)
= (Φ(v))(T) − (Φ(v))(N)x(T).

Therefore, we get

max_{S≠∅,N} e^{Φ(v)}(S, Φ(v)x) = max_{i} e^{Φ(v)}({i}, Φ(v)x),

which shows that a nontrivial coalition with maximal dissatisfaction is a singleton. Let {i_{0}} be a coalition where such a maximum is attained.

Now suppose that y ≠ x and that (Φ(v)(N))y is the nucleolus of Φ(v). Then, from the the definition of the nucleolus (Φ(v)(N))y :

max_{S≠∅,N} e^{Φ(v)}(S, (Φ(v)(N))y) ≤ max_{S≠∅,N} e^{Φ(v)}(S, (Φ(v)(N))x)
= e^{Φ(v)}({i_{0}}, (Φ(v)(N))x)
= β + v(\{i_{0}\}) − (1 + β)\frac{1}{n}.  (9)

In particular for any singleton {i}, (9) implies

β + v(\{i\}) − (1 + β)y_{i} ≤ β + v(\{i_{0}\}) − (1 + β)\frac{1}{n},

which is equivalent to

v(\{i\}) − v(\{i_{0}\}) ≤ (1 + β)(y_{i} − \frac{1}{n}).  (10)

Since (10) must hold for arbitrary large β > 0, we conclude that y_{i} ≥ 1/n for all i = 1, …, n. This immediately implies y = x (since y(N) = 1), a contradiction. Proof of Theorem 18. Suppose that P[v] is true. We will show that P[v] is meaningless. As in the proof of Theorem 13, we consider the game w = αv where α = \frac{1}{v(N)} (note that Φ_{α}(t) = αt is an admissible transformation; also note that w(N) = 1). If P[w] is false, then P[v] is meaningless.

Hence, we may assume that P[w] is true, i.e., we may assume that y is the normalization of the nucleolus of w. Let Φ_{β}(t) = t + β. If P[Φ_{β}(w)] is true for arbitrary large β > 0, then y = \frac{1}{n}(1, 1, …, 1) by Lemma 17. This contradicts the hypothesis y ≠ \frac{1}{n}(1, 1, …, 1) and we conclude that P[Φ_{β}(w)] is false for some β. Note that, for any β > 0, Φ(t) := (Φ_{β} ∘ Φ_{α})(t) = αt + β is an admissible transformation of game values of v and Φ(v) = Φ_{β(w)}. Hence, P[v] is meaningless. Proof of Theorem 19. Let Φ(t) = αt + β, α > 0. For any S ≠ ∅ we have (Φ(v))(S) = αv(S) + β. Let w_{β} be a symmetric game defined by w_{β}(S) = β for all S ≠ ∅. Then

Φ(v) = αv + w_{β}

and we have

c(Φ(v)) = c(αv) + c(w_{β}).

(This follows directly from (4).) Note that c(w_{β}) = β(c(∅, 1), …, c(∅, n)). Also note that c(αv) = αc(v) (follows directly from (4)) Hence,

c(Φ(v)) = αc(v) + β(c(∅, 1), …, c(∅, n))  (11)

First suppose that P[v] is a true meaningful statement. Hence, for any α > 0 and any β ≥ 0 (since Φ(t) = αt + β is an admissible transformation for (positive) interval scales), we have that c(Φ(v)) is a scalar multiple of y. Since P[v] is true, y is a scalar multiple of c(v), so we conclude that c(Φ(v)) is a scalar multiple of c(v). From (11) we conclude that c(Φ(v)) is a scalar multiple of c(v) for any choice of α > 0, β ≥ 0 if and only if one of the following holds:

(a) (c(∅, 1), …, c(∅, n)) = 0.

(b) c(v) ≠ 0 is a scalar multiple of (c(∅, 1), …, c(∅, n)). In this case, the normalization of y is the normalization of (c(∅, 1), …, c(∅, n))

(Note that c(v) ≠ 0 by hypothesis.)

Conversely, suppose that either 1. or 2. hold. First suppose that 1. holds. Then there exists λ ∈ R, λ ≠ 0, such that c(v) = λ(c(∅, 1), …, c(∅, n)) (this is because P[v] is true). From (11) we conclude that, c(Φ(v)) = μ(c(∅, 1), …, c(∅, n)) where μ = αλ + β. Hence, \frac{1}{[c(Φ(v)](N)}c(Φ(v)) = y (because y is the unique scalar multiple of (c(∅, 1), …, c(∅, n)) such that y(N) = 1), i.e., P[Φ(v)] is true for any admissible transformation Φ. In other words, P[v] is meaningful.

Finally, suppose that 2. holds. Then, by (11), c(Φ(v)) = αc(v) and

([c(Φ(v))](N))y = α([c(v)](N))y = αc(v) = c(Φ(v)).

(Note that the second equality holds because P[v] is true.) Hence, P[v] is a meaningful true statement since P[Φ(v)] is true for any admissible transformation Φ. Proof of Proposition 20. We first show (i). We will show that there are uncountably many interval scale games v for which v({1}) = 0, v({2}) = 1 and v({1, 2}) ≠ 0, 1. Note that for two such games u ∼ v ⇔ u = v because the only Φ(t) = αt + β such that Φ(0) = 0 and Φ(1) = 1 is the identity, i.e., Φ(t) = t. Therefore, (i) holds since v({1, 2}) can be any real number different from zero and one.

Obviously, if there is no Φ_{α,β}(t) = αt + β such that u = Φ_{α,β}(v), then there is no Φ_{α}(t) = αt such that u = Φ_{α}(v). Hence, (i)⇒(r).

It remains to show (o). Let Φ_{v} be any increasing function such that Φ_{v}(v(S)) = k if and only if v(S) is the k-th smallest value among {v(S) : S ⊆ [n], S ≠ ∅}. Note that the game Φ_{v}(v) is integer valued and the set of all game values of Φ_{v}(v) is the set [k] = {1, …, k} where k is the cardinality (the number of different elements) of {v(S) : S ⊆ [n], S ≠ ∅}. (Φ_{v} gives a ranking to all game values of v: for all coalitions S with the smallest value, [Φ_{v}(v)](S) = 1, for all coalitions T with the second smallest value, [Φ_{v}(v)](T) = 2, …). Note that for an ordinal scale game v, v ∼ Φ_{v}(v), so u ∼ v ⇔ Φ_{u}(u) ∼ Φ_{v}(v). Also note that Φ_{u}(u) ∼ Φ_{v}(v) ⇔ Φ_{u}(u) = Φ_{v}(v). Hence, the number of ordinal scale games is equal to the number of different games w such that {v(S) : S ⊆ [n], S ≠ ∅} = {1, … k} for some positive integer k. Clearly such games are in one to one correspondence with preferential assignments of 2^{n} − 1 objects (nonempty subsets of N in our case). Proof of Theorem 22. Since there are finitely many ordinal scale games ((o) of Proposition 20) and the set f(R^{2^{n}−1}) is infinite (f is non-degenerate), there exists an ordinal scale game v and an admissible transformation Φ such that f(v) ≠ f(Φ(v)). Hence, for any x ∈ T either “x = f(v)” is false or “x = f(Φ(v))” is false and we conclude that P[v] =”x = f(v)” cannot be a meaningful true statement.

Acknowledgement

The author gratefully acknowledges the support of the National Science Foundation under grant number SES-9211492 to Rutgers University. He also thanks Dr. Fred S. Roberts for his helpful comments.

References

[1] J.F. Banzhaf. Weighted voting doesn’t work: A mathematical analysis. Rutgers Law Review, 13:317–343, 1965.

[2] D.B. Gillies. Some Theorems on N-Person Games. PhD thesis, Princeton University, 1953.

[3] D.H. Krantz, R.D. Luce, P. Suppes, and A. Tversky. Foundations of Measurement, Vol. I. Academic Press, NY, 1971.

[4] R.D. Luce, D.H. Krantz, P. Suppes, and A. Tversky. Foundations of Measurement, Vol. III. Academic Press, NY, 1990.

[5] L. Narens. Abstract Measurement Theory. MIT Press, Cambridge, MA, 1985.

[6] J. Pfanzagl. Theory of Measurement. Wiley, NY, 1968.

[7] F.S. Roberts. Discrete Mathematical Models, with Applications to Social, Biological, and Environmental Problems. Prentice-Hall, NJ, 1976.

[8] F.S. Roberts. Measurement Theory. Addison-Wesley, Reading, MA, 1979.

[9] F.S. Roberts. Limitations of conclusions using scales of measurement. In S.M. Pollock, M.H. Rothkopf, and A. Barnett, editors, Handbooks in OR & MS, volume 6, pages 621–671. North-Holland, NY, 1994.

[10] D. Schmeidler. The nucleolus of a characteristic function game. SIAM J. of Appl. Math., 17:1163–1170, 1969.

[11] L.S. Shapley. A value for n-person games. In H. Kuhn and A.W. Tucker, editors, Contributions to the Theory of Games, volume 2, pages 307–317. Princeton University Press, Princeton, NJ, 1953.

[12] M. Shubik. Game Theory in the Social Sciences. The MIT Press, Cambridge, MA, 1985.

[13] N.J.A. Sloane and S. Plouffe. The encyclopedia of integer sequences. Academic Press, San Diego, CA, 1995.

[14] P. Suppes, D.H. Krantz, R.D. Luce, and A. Tversky. Foundations of Measurement, Vol. II. Academic Press, NY, 1989.

[15] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ, 1944.

Recent Publications in the BRICS Report Series

RS-96-47 Aleksandar Peke� c. Meaningful and Meaningless Solutions for Cooperative N-person Games. December 1996. 28 pp.

RS-96-46 Alexander E. Andreev and Sergei Soloviev. A Decision Algorithm for Linear Isomorphism of Types with Complexity Cn(log^{2}(n)). November 1996. 16 pp.

RS-96-45 Ivan B. Damg� ard, Torben P. Pedersen, and Birgit P�tzmann. Statistical Secrecy and Multi-Bit Commitments. November 1996. 30 pp.

RS-96-44 Glynn Winskel. A Presheaf Semantics of Value-Passing Processes. November 1996. 23 pp. Extended and revised version of paper appearing in Montanari and Sassone, editors, Concurrency Theory: 7th International Conference, CONCUR ’96 Proceedings, LNCS 1119, 1996, pages 98�114.

RS-96-43 Anna Ing� olfsd� ottir. Weak Semantics Based on Lighted Button Pressing Experiments: An Alternative Characterization of the Readiness Semantics. November 1996. 36 pp. An extended abstract to appear in the proceedings of the 10th Annual International Conference of the European Association for Computer Science Logic, CSL ’96.

RS-96-42 Gerth St�lting Brodal and Sven Skyum. The Complexity of Computing the k-ary Composition of a Binary Associative Operator. November 1996. 15 pp.

RS-96-41 Stefan Dziembowski. The Fixpoint Bounded-Variable Queries are PSPACE-Complete. November 1996. 16 pp. Presented at the 10th Annual International Conference of the European Association for Computer Science Logic, CSL ’96.