Gregersen E. (editor) The Britannica Guide to Statistics and Probability
Подождите немного. Документ загружается.
7 The Britannica Guide to Statistics and Probability 7
190
imputation within the solution. The imputations within
the solution are viable because they are not dominated by
any other imputations in the solution.
In any given cooperative game there are generally
many—sometimes infinitely many—solutions. A simple
three-person game that illustrates this fact is one in which
any two players, as well as all three players, receive one
unit, which they can divide between or among themselves
in any way that they wish. Individual players receive noth-
ing. In such a case the value of each two-person coalition,
and the three-person coalition as well, is 1.
One solution to this game consists of three imputa-
tions, in each of which one player receives 0 and the other
two players receive 1/2 each. There is no self-domination
within the solution, because if one imputation is substi-
tuted for another, one player gets more, one gets less, and
one gets the same (for domination, each of the players
forming a coalition must gain). In addition, any imputa-
tion outside the solution is dominated by one in the
solution, because the two players with the lowest payoffs
must each get less than 1/2. Clearly, this imputation is
dominated by an imputation in the solution in which these
two players each get 1/2. According to this solution, at any
given time one of its three imputations will occur, but von
Neumann and Morgenstern do not predict which one.
A second solution to this game consists of all the impu-
tations in which player A receives 1/4 and players B and
C share the remaining 3/4. Although this solution gives a
different set of outcomes from the first solution, it, too,
satisfies von Neumann and Morgenstern’s two conditions.
For any imputation within the solution, player A always
gets 1/4 and therefore cannot gain. In addition, because
players B and C share a fixed sum, if one of them gains
in a proposed imputation, the other must lose. Thus, no
191
7
Game Theory 7
imputation in the solution dominates another imputation
in the solution.
For any imputation not in the solution, player A must
get either more or less than 1/4. When A gets more than
1/4, players B and C share less than 3/4 and, therefore, can
do better with an imputation within the solution. When
player A gets less than 1/4, say 1/8, he always does better
with an imputation in the solution. Players B and C now
have more to share, but no matter how they split the new
total of 7/8, there is an imputation in the solution that one
of them will prefer. When they share equally, each gets
7/16, but player B, for example, can get more in the impu-
tation (1/4, 1/2, 1/4), which is in the solution. When players
B and C do not divide the 7/8 equally, the player who gets
the smaller amount can always do better with an imputa-
tion in the solution. Thus, any imputation outside the
solution is dominated by one inside the solution. Similarly,
it can be shown that all of the imputations in which player
B gets 1/4 and players A and C share 3/4, as well as the set
of all imputations in which player C gets 1/4 and players A
and B share 3/4, also constitute a solution to the game.
Although there may be many solutions to a game (each
representing a different “standard of behaviour”), it was
not apparent at first that there would always be at least
one in every cooperative game. Von Neumann and
Morgenstern found no game without a solution, and they
deemed it important that no such game exists. However,
in 1967 a fairly complicated 10-person game was discov-
ered by the American mathematician William F. Lucas
that did not have a solution. This and later counterexam-
ples indicated that the von Neumann–Morgenstern
solution is not universally applicable, but it remains com-
pelling, especially because no definitive theory of n-person
cooperative games exists.
7 The Britannica Guide to Statistics and Probability 7
192
The Banzhaf Value in Voting Games
It was shown that power defined as control over outcomes
is not synonymous with control over resources, such as a
chair’s tie-breaking vote. The strategic situation facing
voters intervenes and may cause them to reassess their
strategies in light of the additional resources that the chair
possesses. In doing so, they may be led to “gang up” against
the chair. (Note that Y and Z do this without any explicit
communication or binding agreement. The coalition they
form against the chair X is an implicit one and the game,
therefore, remains noncooperative.) In effect, the chair’s
resources become a burden to bear, not power to relish.
When players’ preferences are unknown beforehand,
though, it is useful to define power in terms of their abil-
ity to alter the outcome by changing their votes, as
governed by a constitution, bylaws, or other rules of the
game. Various measures of voting power have been pro-
posed for simple games, in which every coalition has a
value of 1 (if it has enough votes to win) or 0 (if it does
not). The sum of the powers of all the players is 1. When
a player has 0 power, his vote has no influence on the out-
come. When a player has a power of 1, the outcome
depends only on his vote. The key to calculating voting
power is determining the frequency with which a player
casts a critical vote.
American attorney John F. Banzhaf III proposed that
all combinations in which any player is the critical voter—
that is, in which a measure passes only with this voter’s
support—be considered equally likely. The Banzhaf value
for each player is then the number of combinations in
which this voter is critical divided by the total number of
combinations in which each voter (including this one)
is critical.
193
7
Game Theory 7
This view is incompatible with defining the voting
power of a player to be proportional to the number of
votes he casts, because votes per se may have little or no
bearing on the choice of outcomes. For example, in a
three-member voting body in which A has 4 votes, B 2
votes, and C 1 vote, members B and C will be powerless if a
simple majority wins. The fact that members B and C
together control 3/7 of the votes is irrelevant in the selec-
tion of outcomes, so these members are called dummies.
Member A, by contrast, is a dictator by virtue of having
enough votes alone to determine the outcome. A voting
body can have only one dictator, whose existence renders
all other members dummies, but there may be dummies
and no dictator (an example is given in the following text).
A minimal winning coalition (MWC) is one in which
the subtraction of at least one of its members renders it
losing. To illustrate the calculation of Banzhaf values, con-
sider a voting body with two 2-vote members (distinguished
as 2a and 2b) and one 3-vote member, in which a simple
majority wins. There are three distinct MWCs—(3, 2a),
(3, 2b), and (2a, 2b)—or combinations in which some voter
is critical. The grand coalition, comprising all three mem-
bers, (3, 2a, 2b), is not an MWC because no single member’s
defection would cause it to lose.
Because each member’s defection is critical in two
MWCs, each member’s proportion of voting power is
two-sixths, or one-third. Thus, the Banzhaf index, which
gives the Banzhaf values for each member in vector form,
is (1/3, 1/3, 1/3). Clearly, the voting power of the 3-vote
member is the same as that of each of the two 2-vote mem-
bers, although the 3-vote member has 50 percent greater
weight (more votes) than each of the 2-vote members.
The discrepancy between voting weight and voting
power is more dramatic in the voting body (50, 49, 1)
7 The Britannica Guide to Statistics and Probability 7
194
where, again, a simple majority wins. The 50-vote member
is critical in all three MWCs—(50, 1), (50, 49), and
(50, 49, 1), giving him a veto because his presence is neces-
sary for a coalition to be winning—whereas the 49-vote
member is critical in only (50, 49) and the 1-vote member
in only (50, 1). Thus, the Banzhaf index for (50, 49, 1) is
(3/5, 1/5, 1/5), making the 49-vote member indistinguish-
able from the 1-vote member. The 50-vote member, with
just one more vote than the 49-vote member, has three
times as much voting power.
In 1958 six West European countries formed the
European Economic Community (EEC). The three large
countries (West Germany, France, and Italy) each had 4
votes on its Council of Ministers, the two medium-size
countries (Belgium and The Netherlands) 2 votes each,
and the one small country (Luxembourg) 1 vote. The deci-
sion rule of the Council was a qualified majority of 12 out
of 17 votes, giving the large countries Banzhaf values of
5/21 each, the medium-size countries 1/7 each, and—
amazingly—Luxembourg no voting power at all. From
1958 to 1973—when the EEC admitted three additional
members—Luxembourg was a dummy. Luxembourg
might as well not have gone to Council meetings except to
participate in the debate, because its one vote could never
change the outcome. To see this without calculating the
Banzhaf values of all the members, note that the votes of
the five other countries are all even numbers. Therefore,
an MWC with exactly 12 votes could never include
Luxembourg’s (odd) 1 vote. Although a 13-vote MWC that
included Luxembourg could form, Luxembourg’s defec-
tion would never render such an MWC losing. It is worth
noting that as the Council kept expanding with the addi-
tion of new countries and the formation of the European
Union, Luxembourg never reverted to being a dummy,
195
7
Game Theory 7
even though its votes became an ever smaller proportion
of the total.
The Banzhaf and other power indices, rooted in coop-
erative game theory, have been applied to many voting
bodies, not necessarily weighted, sometimes with surpris-
ing results. For example, the Banzhaf index has been used
to calculate the power of the 5 permanent and 10 nonper-
manent members of the United Nations Security Council.
(The permanent members, all with a veto, have 83 percent
of the power.) It has also been used to compare the power
of representatives, senators, and the president in the U.S.
federal system.
Banzhaf himself successfully challenged the constitu-
tionality of the weighted-voting system used in Nassau
county, New York, showing that three of the County
Board’s six members were dummies. Likewise, the for-
mer Board of Estimate of New York City, in which three
citywide officials (mayor, chair of the city council, and
comptroller) had two votes each and the five borough
presidents had one vote each, was declared uncon-
stitutional by the U.S. Supreme Court. Brooklyn had
approximately six times the population of Staten Island
but the same one vote on the Board, in violation of the
equal-protection clause of the 14th Amendment of the
U.S. Constitution that requires “one person, one vote.”
Finally, it has been argued that the U.S. Electoral College,
which is effectively a weighted voting body because
almost all states cast their electoral votes as blocs, vio-
lates one person, one vote in presidential elections,
because voters from large states have approximately
three times as much voting power, on a per-capita basis,
as voters from small states.
Game theory is now well established and widely used
in a variety of disciplines. The foundations of economics,
7 The Britannica Guide to Statistics and Probability 7
196
for example, are increasingly grounded in game theory.
Among game theory’s many applications in economics is
the design of Federal Communications Commission auc-
tions of airwaves, which have netted the U.S. government
billions of dollars. Game theory is increasingly used in
political science to study strategy in areas as diverse as
campaigns and elections, defense policy, and international
relations. In biology, business, management science, com-
puter science, and law, game theory has been used to model
a variety of strategic situations. Game theory has even
penetrated areas of philosophy (e.g., to study the equilib-
rium properties of ethical rules), religion (e.g., to interpret
Bible stories), and pure mathematics (e.g., to analyze how
to divide a cake fairly among n people). All in all, game
theory holds out great promise not only for advancing the
understanding of strategic interaction in very different
settings but also for offering prescriptions for the design
of better auction, bargaining, voting, and information sys-
tems that involve strategic choice.
197
CHAPTER 5
CoMBInAtoRICs
C
ombinatorics is the fi eld of mathematics concerned
with problems of selection, arrangement, and opera-
tion within a fi nite or discrete system. This section also
includes the closely related area of combinatorial geometry.
One of the basic problems of combinatorics is to
determine the number of possible confi gurations (e.g.,
graphs, designs, arrays) of a given type. Even when the
rules specifying the confi guration are relatively simple,
enumeration may sometimes present formidable diffi cul-
ties. The mathematician may have to be content with
fi nding an approximate answer or at least a good lower and
upper bound.
In mathematics, generally, an entity is said to “exist” if
a mathematical example satisfi es the abstract properties
that defi ne the entity. In this sense it may not be apparent
that even a single confi guration with certain specifi ed
properties exists. This situation gives rise to problems of
existence and construction. There is again an important
class of theorems that guarantee the existence of certain
choices under appropriate hypotheses. Besides their
intrinsic interest, these theorems may be used as existence
theorems in various combinatorial problems.
Finally, there are problems of optimization. As an
example, a function f , the economic function, assigns the
numerical value f ( x ) to any confi guration x with certain
specifi ed properties. In this case the problem is to choose
a confi guration x
0
that minimizes f ( x ) or makes it ε = mini-
mal—that is, for any number ε > 0, f ( x
0
) f ( x ) + ε, for all
confi gurations x , with the specifi ed properties.
7 The Britannica Guide to Statistics and Probability 7
198
hisToRy
Since ancient times in cultures ranging from China
to Persia, combinatorial problems have inspired and
puzzled mathematicians. Even in our own day, the fiend-
ish game of Sudoku has inspired millions to dabble in
combinatorics.
Early Developments
Certain types of combinatorial problems have attracted
the attention of mathematicians since early times. Magic
squares, for example, which are square arrays of numbers
with the property that the rows, columns, and diagonals
add up to the same number, occur in the I Ching, a Chinese
book dating back to the 12th century BCE. The binomial
Millions of unwitting Sudoku addicts play at combinatorics every day.
Shutterstock.com
199
7
Combinatorics 7
coefficients, or integer coefficients in the expansion of
(a + b)
n
, were known to the 12th-century Indian mathe-
matician Bhāskara, who in his Līlāvatī (“The Graceful”),
dedicated to a beautiful woman, gave the rules for calcu-
lating them together with illustrative examples. “Pascal’s
triangle,” a triangular array of binomial coefficients, had
been taught by the 13th-century Persian philosopher Nas
·
īr
ad-Dīn al
·
-T
·
ūsī.
In the West, combinatorics may be considered to
begin in the 17th century with Blaise Pascal and Pierre
de Fermat, both of France, who discovered many clas-
sical combinatorial results in connection with the
development of the theory of probability. The term combi-
natorial was first used in the modern mathematical sense
by the German philosopher and mathematician Gottfried
Wilhelm Leibniz in his Dissertatio de Arte Combinatoria
(“Dissertation Concerning the Combinational Arts”).
He foresaw the applications of this new discipline to the
whole range of the sciences. The Swiss mathematician
Leonhard Euler was finally responsible for the develop-
ment of a school of authentic combinatorial mathematics
beginning in the 18th century. He became the father of
graph theory when he settled the Königsberg bridge
problem, and his famous conjecture on Latin squares was
not resolved until 1959.
In England, Arthur Cayley, near the end of the 19th
century, made important contributions to enumerative
graph theory, and James Joseph Sylvester discovered
many combinatorial results. At about the same time,
the British mathematician George Boole used combina-
torial methods in connection with the development of
symbolic logic, and the combinatorial ideas and meth-
ods of Henri Poincaré, which developed in the early part
of the 20th century in connection with the problem of