Adversaries Would Find Other Attack Methods, Game Theory Shows

[Faustine]

Interesting article, actually. 

I think game theory has the potential to be a powerful tool for any 
cypherpunk to have in his or her mental arsenal, (so to speak.) For those 
of you who haven't been introduced to game theory, how it works, and what 
it's used for, here's a modified excerpt from an essay outlining the 
basics...



Game theory can be described as the study of interactive decision making. 
Although game theory is relevant to parlor games such as poker or bridge, 
most research in game theory focuses on how groups of people interact. 
There are two main branches of game theory: cooperative and noncooperative 
game theory. Noncooperative game theory deals largely with how intelligent 
individuals interact with one another in an effort to achieve their own 
goals. 

Decision theory can be viewed as a theory of one person games, or a game of 
a single player against nature. The focus is on preferences and the 
formation of beliefs. The most widely used form of decision theory argues 
that preferences among risky alternatives can be described by the 
maximization the expected value of a numerical utility function, where 
utility may depend on a number of things, but in situations of interest to 
economists often depends on money income. Probability theory is heavily 
used in order to represent the uncertainty of outcomes, and Bayes Law is 
frequently used to model the way in which new information is used to revise 
beliefs. Decision theory is often used in the form of decision analysis, 
which shows how best to acquire information before making a decision. 

General equilibrium theory can be viewed as a specialized branch of game 
theory that deals with trade and production, and typically with a 
relatively large number of individual consumers and producers. It is widely 
used in the macroeconomic analysis of broad based economic policies such as 
monetary or tax policy, in finance to analyze stock markets, to study 
interest and exchange rates and other prices. In recent years, political 
economy has emerged as a combination of general equilibrium theory and game 
theory in which the private sector of the economy is modeled by general 
equilibrium theory, while voting behavior and the incentive of governments 
is analyzed using game theory. Issues studied include tax policy, trade 
policy, and the role of international trade agreements such as the European 
Union. 

Mechanism design theory differs from game theory in that game theory takes 
the rules of the game as given, while mechanism design theory asks about 
the consequences of different types of rules. Naturally this relies heavily 
on game theory. Questions addressed by mechanism design theory include the 
design of compensation and wage agreements that effectively spread risk 
while maintaining incentives, and the design of auctions to maximize 
revenue, or achieve other goals.

An Instructive Example

One way to describe a game is by listing the players (or individuals) 
participating in the game, and for each player, listing the alternative 
choices (called actions or strategies) available to that player. In the 
case of a two-player game, the actions of the first player form the rows, 
and the actions of the second player the columns, of a matrix. The entries 
in the matrix are two numbers representing the utility or payoff to the 
first and second player respectively. A very famous game is the Prisoner's 
Dilemma game. In this game the two players are partners in a crime who have 
been captured by the police. Each suspect is placed in a separate cell, and 
offered the opportunity to confess to the crime. The game can be 
represented by the following matrix of payoffs:

not confess confess 
not confess 5,5    0,10 
confess     10,0   1,1 

Note that higher numbers are better (more utility). If neither suspect 
confesses, they go free, and split the proceeds of their crime which we 
represent by 5 units of utility for each suspect. However, if one prisoner 
confesses and the other does not, the prisoner who confesses testifies 
against the other in exchange for going free and gets the entire 10 units 
of utility, while the prisoner who did not confess goes to prison and gets 
nothing. If both prisoners confess, then both are given a reduced term, but 
both are convicted, which we represent by giving each 1 unit of utility: 
better than having the other prisoner confess, but not so good as going 
free.

This game has fascinated game theorists for a variety of reasons. First, it 
is a simple representation of a variety of important situations. For 
example, instead of confess/not confess we could label the 
strategies "contribute to the common good" or "behave selfishly." This 
captures a variety of situations economists describe as public goods 
problems. An example is the construction of a bridge. It is best for 
everyone if the bridge is built, but best for each individual if someone 
else builds the bridge. This is sometimes refered to in economics as an 
externality. Similarly this game could describe the alternative of two 
firms competing in the same market, and instead of confess/not confess we 
could label the strategies "set a high price" and "set a low price." 
Naturally is is best for both firms if they both set high prices, but best 
for each individual firm to set a low price while the opposition sets a 
high price.

A second feature of this game, is that it is self-evident how an 
intelligent individual should behave. No matter what a suspect believes his 
partner is going to do, is is always best to confess. If the partner in the 
other cell is not confessing, it is possible to get 10 instead of 5. If the 
partner in the other cell is confessing, it is possible to get 1 instead of 
0. Yet the pursuit of individually sensible behavior results in each player 
getting only 1 unit of utility, much less than the 5 units each that they 
would get if neither confessed. This conflict between the pursuit of 
individual goals and the common good is at the heart of many game theoretic 
problems.

A third feature of this game is that it changes in a very significant way 
if the game is repeated, or if the players will interact with each other 
again in the future. Suppose for example that after this game is over, and 
the suspects either are freed or are released from jail they will commit 
another crime and the game will be played again. In this case in the first 
period the suspects may reason that they should not confess because if they 
do not their partner will not confess in the second game. Strictly 
speaking, this conclusion is not valid, since in the second game both 
suspects will confess no matter what happened in the first game. However, 
repetition opens up the possibility of being rewarded or punished in the 
future for current behavior, and game theorists have provided a number of 
theories to explain the obvious intuition that if the game is repeated 
often enough, the suspects ought to cooperate.



One of the most entertaining intro books is "The Compleat Strategist: Being 
a Primer on the Theory of Games of Strategy", (J.D. Williams, McGraw-Hill, 
New York 1966.) David Levine recommends "Thinking Strategically" by A. 
Dixit and B. Nalebuff (Norton, 1991) as good general reading. If you're 
interested in getting deeper into the subject you should try Game Theory 
with Economic Applications by H. Bierman and L. Fernandez (Addison-Wesley, 
1993). The next step up is the graduate level text Game Theory by D. 
Fudenberg and J. Tirole from MIT Press. There are also two other advanced 
textbooks worth taking a look at: "Fun and Games: A Text on Game Theory by 
K. Binmore" (D.C. Heath, 1992), a very focused and mathematical treatment...

---------------------
"Golden Age" History
---------------------

1944 

"Theory of Games and Economic Behavior" by John von Neumann and Oskar 
Morgenstern is published. As well as expounding two-person zero sum theory 
this book is the seminal work in areas of game theory such as the notion of 
a cooperative game, with transferable utility (TU), its coalitional form 
and its von Neumann-Morgenstern stable sets. It was also the account of 
axiomatic utility theory given here that led to its wide spread adoption 
within economics. 

1945 

Herbert Simon writes the first review of von Neumann-Morgenstern.

1946

The first entirely algebraic proof of the minimax theorem is due to L. H. 
Loomis's,On a Theorem of von Neumann, paper.

1950 

Contributions to the Theory of Games I, H. W. Kuhn and A. W. Tucker eds., 
published.

1950

In January 1950 Melvin Dresher and Merrill Flood carry out, at the Rand 
Corporation, the experiment which introduced the game now known as the 
Prisoner's Dilemma. The famous story associated with this game is due to A. 
W. Tucker, A Two-Person Dilemma, (memo, Stanford University). Howard Raiffa 
independently conducted, unpublished, experiments with the Prisoner's 
Dilemma.

1950-53

In four papers between 1950 and 1953 John Nash made seminal contributions 
to both non-cooperative game theory and to bargaining theory. In two 
papers, "Equilibrium Points in N- Person Games" (1950) and "Non-cooperative 
Games" (1951), Nash proved the existence of a strategic equilibrium for non-
cooperative games - the Nash equilibrium - and proposed the"Nash program", 
in which he suggested approaching the study of cooperative games via their 
reduction to non-cooperative form. In his two papers on bargaining theory, 
The Bargaining Problem (1950) and Two-Person Cooperative Games (1953), he 
founded axiomatic bargaining theory, proved the existence of the Nash 
bargaining solution and provided the first execution of the Nash program.

1951

George W. Brown described and discussed a simple iterative method for 
approximating solutions of discrete zero-sum games in his paper Iterative 
Solutions of Games by Fictitious Play.

1952 

The first textbook on game theory: John Charles C. McKinsey, "Introduction 
to the Theory of Games".

1952 

Merrill Flood's report, (Rand Corporation research memorandum, Some 
Experimental Games, RM-789, June), on the 1950 Dresher/Flood experiments 
appears.

1952

The Ford Foundation and the University of Michigan sponsor a seminar on 
the"Design of Experiments in Decision Processes" in Santa Monica.This was 
the first experimental economics/ experimental game theory conference.

1952-53 

The notion of the Core as a general solution concept was developed by L. S. 
Shapley (Rand Corporation research memorandum, Notes on the N-Person Game 
III: Some Variants of the von-Neumann-Morgenstern Definition of Solution, 
RM- 817, 1952) and D.B. Gillies (Some Theorems on N-Person Games, Ph.D. 
thesis, Department of Mathematics, Princeton University, 1953). The core is 
the set of allocations that cannot be improved upon by any coalition.

1953

Lloyd Shapley in his paper A" Value for N-Person Games" characterised, by a 
set of axioms, a solution concept that associates with each coalitional 
game,v, a unique out- come, v. This solution in now known as the Shapley 
Value.

1953

Lloyd Shapley's paper "Stochastic Games" showed that for the strictly 
competitive case, with future payoff discounted at a fixed rate, such games 
are determined and that they have optimal strategies that depend only on 
the game being played, not on the history or even on the date, i.e.: the 
strategies are stationary.

1953 

Extensive form games allow the modeller to specify the exact order in which 
players have to make their decisions and to formulate the assumptions about 
the information possessed by the players in all stages of the game. H. W. 
Kuhn's paper, "Extensive Games and the Problem of Information" includes the 
formulation of extensive form games which is currently used, and also some 
basic theorems pertaining to this class of games.

1953 

"Contributions to the Theory of Games II," H. W. Kuhn and A. W. Tucker 
eds., published.

1954

One of the earliest applications of game theory to political science is L. 
S. Shapley and M. Shubik with their paper "A Method for Evaluating the 
Distribution of Power in a Committee System." They use the Shapley value to 
determine the power of the members of the UN Security Council.

1954-55 

Differential Games were developed by Rufus Isaacs in the early 1950s. They 
grew out of the problem of forming and solving military pursuit games. The 
first publications in the area were Rand Corporation research memoranda, by 
Isaacs, RM-1391 (30 November 1954), RM-1399 (30 November 1954), RM-1411 (21 
December 1954) and RM-1486 (25 March 1955) all entitled, in part, 
Differential Games.

1955

One of the first applications of game theory to philosophy is R. B. 
Braithwaite's "Theory of Games as a Tool for the Moral Philosopher."

1957 

"Games and Decisions: Introduction and Critical Survey" by Robert Duncan 
Luce and Howard Raiffa published.

1957 

Contributions to the Theory of Games III, M. A.Dresher, A. W. Tucker and P. 
Wolfe eds., published.

1959 

The notion of a Strong Equilibrium was introduced by R. J. Aumann in the 
paper Acceptable Points in General Cooperative N-Person Games.

1959

The relationship between Edgeworth's idea of the contract curve and the 
core was pointed out by Martin Shubik in his paper Edgeworth Market Games. 
One limitation with this paper is that Shubik worked within the confines of 
TU games whereas Edgeworth's idea is more appropriately modelled as an NTU 
game.

1959 

Contributions to the Theory of Games IV, A. W.Tucker and R. D. Luce eds., 
published.

1959 

Publication of Martin Shubik's "Strategy and Market Structure: Competition, 
Oligopoly, and the Theory of Games". This was one of the first books to 
take an explicitly non-cooperative game theoretic approach to modelling 
oligopoly. It also contains an early statement of the Folk Theorem.

Late 50's 

Near the end of this decade came the first studies of repeated games. The 
main result to appear at this time was the Folk Theorem. This states that 
the equilibrium outcomes in an infinitely repeated game coincide with the 
feasible and strongly individually rational outcomes of the one-shot game 
on which it is based. Authorship of the theorem is obscure.