【免费】TheLifeandWorkofJohnForbesNashJr资源-CSDN文库

Life

Work

需积分: 0 102 浏览量 2009-12-20 17:50:10 上传评论收藏 167KB PDF 举报

资源详情

资源评论

资源推荐

The Life and Work of John Forbes Nash Jr.

WINNER OF THE BANK OF SWEDEN PRIZE IN ECONOMIC SCIENCES

IN MEMORY OF ALFRED NOBEL, 1994

CS 294-6: Reading the Classics

Prof. Christos H. Papadimitriou

Fall 2004, U C Berkeley

Ben Blum, Arindam Chakrabarti, and Kamalika Chaudhuri

Graduate Students

Department of Electrical Engineering and Computer Sciences

University of California at Berkeley

bblum,arindam,kamalika

@CS.Berkeley.EDU

October 12, 2004

1 Introduction to game theory

The theory of games is the branch of mathematics used to model and analyse the interaction be-

tween rational agents in the real world. Game theory ﬁnds application in economics to model the

interaction between various agents, in political science to analyse decision making, and even in bi-

ology to analyze evolutionary dynamics. Traditionally game theory has been studied by economists

and mathematicians. Recently there has been a surge in interest in game theory in the computer

science community. From a theoretical computer science perspective, the ﬁeld of game theory is

an untapped source of interesting unsolved computational problems. For example, until recent re-

search, nothing had been known about the computability of Nash equilibria, a concept that has been

used by game theoreticians for the last ﬁve decades, and till now, the problem remains open even

for two-player games. Systems researchers on the other hand, have been looking at game theory

to model and draw conclusions about the behaviour of individual machines in large scale networks

such as the internet.

In game theory, the interaction between agents is modeled in the form of a strategic game. A strate-

gic game has two components: a set

players, and a set

of strategies for each player. When

all players choose a strategy from their available set, they each get a payoff which depends on the

strategies of all the players.

1 INTRODUCTION TO GAME THEORY

Rock Paper Scissors

Rock 0, 0 -1, 1 1, -1

Paper 1,-1 0,0 -1, 1

Scissors -1,1 0,0 1, -1

Figure 1: Table showing the payoffs for Rock-Paper-Scissors

1.1 Example

Consider the following simple two player game known popularly as Rock-paper-scissors. As the

rules of the game go, each player pick either of three objects - rock, paper and scissors. Scissors

cut paper, rock blunts scissors and paper covers rock. When one player plays scissors and the other

paper, the scissors player wins and so on. When both play the same strategy, there is a draw.

In game theory, we represent this game by the bimatrix shown in Table 1.1. The strategies of player

A occur along the rows, and the strategies of player B along the columns of this table. When the row

player plays strategy

and the column player plays strategy

, the payoffs they obtain occur in cell

(

i; j

)

. Note that this is a compact representation of the rules of the game. A player wins the game if

he obtains a payoff of 1, and loses the game if his payoff is -1. In general, the payoff is in some sense

a measure of the beneﬁt or utility the player obtains from the outcome that results from the choices

of all the players. The basic assumption underlying game theory is that all players are rational - that

is, they always aim to maximize their own payoffs from the game. Whether this assumption is rea-

sonable has been a subject of much debate. We defer a brief discussion to the end of the next section.

Given a set

of strategies available to player

, a mixed strategy is a sequence of

non-negative

numbers which add up to one, and which have a one-to-one correspondence with

. One can think

of a mixed strategy as a probability distribution over the set of strategies; the number corresponding

to a particular strategy

represents the probability with which

is picked. For example, in

Rock-paper-scissors,

;

can denote a mixed strategy of the row player. The row player

would execute this mixed strategy if at any given execution of the game, she picks each of the strate-

gies rock, paper and scissors at random with probability

To distinguish from mixed strategies, we call the strategies in the original set

pure strategies for

the rest of the section.

Deﬁnition 1 (Nash Equilibrium) A Nash equilibrium is deﬁned as a set of (possibly mixed)

strategies chosen by all the players, such that no player wants to change his strategy provided the

other players follow their current strategies. More formally, if

(

; : : : ; t

)

is the payoff

received by player

when players

; : : : ; n

play strategies

; : : : ; t

respectively, then the strategies

(

; : : : ; t

)

form a Nash equilibrium if:

(

; : : : ; t

)



(

; : : : ; s

; : : : ; t

)

(1)

holds for all players

2 A BRIEF HISTORY OF GAME THEORY

For example in Rock-paper-scissors, it is easy to verify that the mixed strategies

;

form a Nash equilibrium. Again, the usefulness of such equilibrium points as a

measure of behaviour has been a subject of much debate. We defer a discussion to a later section.

Note that a game can have no Nash equilibria in which the strategies adopted by all the players are

pure strategies. One can easily verify that the example Rock-paper-scissors presented above is such

a game. Nash’s major contribution to game theory was to show that every game has a mixed strategy

Nash equilibrium. His seminal paper

[

]

opened the doors for a long line of research on various

forms of equilibria and their properties.

2 A brief history of game theory

The theory of games, in the form we know it today, began with Von Neumann in 1928

[

]

. This is

not to say that games had received no previous attention in the literature. In 1921, Emile Borel, a

French mathematician, ﬁrst considered games of strategy in the abstract, and suggested that mixed

strategies—randomization over actions—might be necessary in optimal play

[

]

. However, his

deﬁnitions were limited to symmetric, two-player games, and he failed to fully characterize opti-

mal strategies. Much earlier, in 1838, a French philosopher named Antoine Cournot solved a few

isolated problems in economic theory using methods that anticipated the later discoveries of Nash

himself (see his famous duopoly model, for example)

[

]

. But it was Von Neumann who ﬁrst deﬁned

games in their full generality, who popularized them and foresaw their wide applicability to eco-

nomics and political science, and who made the ﬁrst signiﬁcant advances toward their solution. In

his 1928 paper, titled “A Theory of Parlor Games”, he provided the ﬁrst deﬁnition of extensive-form

games, still the most fundamental deﬁnition in game theory, and argued that all extensive-form

games could be reduced to a simpliﬁed “normal form” in which players move once, without any

information about their opponents’ moves. He then fully characterized optimal play in zero-sum

two-player games (games of a strictly competitive nature, in which one player wins exactly the

amount lost by the other) using his famous minimax theorem.

It was this latter result that truly inaugurated the study of games and strategies. It demonstrated

that game theory was a useful formalism, capable of positive statements about rational behavior.

Von Neumann himself, responding to claims by Maurice Frechet that Borel was the true founder of

Game Theory, wrote in a notice to the journal Econometrica:

“I am somewhat surprised that Professor Frechet views the mere desire to mathematize

strategic concepts and the straight formal deﬁnition of a pure strategy as the main

agenda of an “initiator” in this ﬁeld. Throughout the period in question I felt that

there was nothing worth publishing until the minimax theorem was proved.”

[

]

Perhaps because of the strength of the minimax solution, Von Neumann based his entire theory upon

zero-sum games. In his seminal 1944 book with Morgenstern, A Theory of Games and Economic

Behavior

[

]

he began with a thorough explication of the theory of two-player zero-sum games,

and proceeded to discuss, separately, three-person, four-person, and n-person zero-sum games—in

each case by reduction (through the formation of coalitions) to the zero-sum two-player case. His

“solutions” for these cases were not complete; he gave few guidelines for how coalitions might

2 A BRIEF HISTORY OF GAME THEORY

be formed. Furthermore, these solutions rested upon numerous assumptions: that players would

form coalitions at the onset of the game; that these coalitions would not change over the course of

the game; and that each coalition would act as a single player, with perfect agreement among its

constituents. Most prominently, they relied on the zero-sum assumption, which excluded nearly all

economic scenarios of interest—when any sort of good is produced, the total value of a game is

likely to be non-zero.

It is understandable that Von Neumann, whose word at the time was deﬁnitive, restricted his at-

tention to tractable games (and we use “tractable” here in the loose sense, since a full 110 pages

were devoted to three- and four-player zero-sum games). But it left the general applicability of the

theory of games open to serious doubts. When John Nash came to game theory in 1949, the set of

games for which anything at all could be said about optimal play was a tiny and largely insigniﬁcant

subclass. It would have been impossible to attempt coalitional analysis of games with more than a

few players; even in small games, the analysis was complicated and not entirely conclusive. After

Nash’s ﬁrst paper, a one-page notice in the Proceedings of the National Academy of Sciences

[

]

game theory could assure that rational behavior existed in any game, of any size. It was a tremen-

dous breakthrough.

However, it was not immediately accepted as such. In 1953, three full years after the publication of

Nash’s result, Von Neumann and Morgenstern published the third edition of the “Theory of Games

and Economic Behavior”, the deﬁnitive text on game theory at the time. The opportunity was cer-

tainly available to them to write an extra chapter or appendix on Nash’s results. Instead, all Nash

received was the following brief mention in the preface: “In the theory of n-person games, there

have been some further developments in the direction of ’non-cooperative’ games. In this respect,

particularly the work of J.F. Nash must be mentioned.”

[

]

It seems likely that Von Neumann re-

garded “non-cooperative” games as a specialized subclass of at most passing interest. In fact, when

Nash ﬁrst discussed his existence theorem with him, Von Neumann told him that it was merely a

nice ﬁxed-point result

[

]

2.1 Why did von Neumann miss it ?

It is interesting to note that Von Neumann was no stranger to ﬁxed-point results. In 1937 he was the

ﬁrst to employ what would later be called the Kakutani ﬁxed point theorem, in his classic paper on

the existence of a certain kind of general economic equilibrium

[

]

. This is precisely the ﬁxed-point

theorem that Nash used to prove the existence of equilibria in non-cooperative games. Furthermore,

the notion of equilibria in general as economic solutions was very familiar to the Vienna Collo-

quium, the center of game theory-inﬂuenced economics in the 1940s, of which Von Neumann was

a key member. Why, then, did Von Neumann, arguably the leading mathematician of his day, fail

to obtain Nash’s “nice ﬁxed-point result” himself? The answer seems clear: he never found the

solution because he never correctly formulated the question. It probably never occurred to him to

make the assumption that players would not cooperate. If it did, perhaps he considered it even more

restrictive than the zero-sum assumption. Since it took him at least three years to appreciate the

importance of Nash’s work, it is unlikely that he was open enough to the idea to have developed

it himself (although, of course, competitive attachment to his own theory must also be taken into

3 BIRTH OF A STAR

account). If we’d like to indulge in psychological speculation (although such speculation is always

suspect), we might guess that Von Neumann, the outgoing socialite, was more inclined to consider

cooperation, whereas Nash, the isolated eccentric, may have unconsciously attached a hidden social

cost to the formation of alliances. This is sort of a goofy way of looking at it. More seriously, the

formation of coalitions was the clearest way that games of more than two players might be reduced

to the two-player zero-sum games whose solution Von Neumann was so pleased with. In effect, Von

Neumann spent his efforts constructing methods by which this solution might be applied to larger

games, rather than seeking a generalization of the minimax solution which he did not believe to

exist.

Despite Von Neumann’s dismissive attitude toward the Nash equilibrium, it truly is a natural gen-

eralization of the minimax solution. Von Neumann himself gives a characterization of the minimax

solution in section 17.9.1, comment 17:D of

[

]

that is precisely the deﬁnition of a Nash equi-

librium. He apparently didn’t observe that this deﬁnition is realizable even when the game is not

zero-sum. In the case of rock-paper-scissors, our intuition tells us that if the payoffs are perturbed

slightly, the game doesn’t change that much—if either player chooses one action deterministically,

they can be soundly beaten by the other. The only reasonable way to play is, as before, to choose ac-

tions nearly uniformly at random. In other words, the minimax solution should perturb only slightly

when the payoffs are perturbed. But, in fact, the perturbation of payoffs, even by an inﬁnitesimal

amount, renders the minimax solution entirely inapplicable because the game is no longer zero-

sum. Suddenly Von Neumann’s methods say nothing at all about the solution to the game. But the

minimax solution of rock-paper-scissors is also the game’s unique Nash equilibrium, and unlike the

minimax solution, this Nash equilibrium perturbs exactly as we expect it too. It is a bit surprising

that Von Neumann didn’t examine his solution from this perspective.

3 Birth of a star

John Forbes Nash Jr. was born to John Forbes Nash Sr., and Margaret Virginia (Martin) Nash in

Blueﬁeld, West Virginia, on June 13, 1928. As a child he was extremely intelligent and had a great

thirst for knowledge. By the age of twelve he had turned his room into a laboratory and spent a

great deal of time doing experiments involving mainly high school physics and chemistry, though

quite a few were rather non-standard; for example, he reportedly found a way to modify the tele-

phone circuitry so that it would not ring when somebody called. Subsequently however, when he

was ﬁfteen, Nash engaged in bomb-making with two other friends, one of whom was killed in an

accidental explosion

[

]

From an early age, John Nash’s parents were worried about John’s lack of interest in friends and

childish pursuits. However, it was also clear to them that he was different from other children his

age; he was far more intelligent. Whether his lack of interest in socializing merely a by-product of

his genius, or a sign of a deeper problem: an inability to connect to people, was not clear to them.

They tried to involve him in social activities like Boy Scout camp, Sunday Bible classes, etc. His

sister Martha (two and half years younger) was asked, (much to her chagrin; she thought him to be

somewhat odd), to include him in her social circle.

剩余24页未读，继续阅读

评论收藏

内容反馈

jubincn

粉丝: 459
资源: 41

The Life and Work of John Forbes Nash Jr

评论0

最新资源

The Life and Work of John Forbes Nash Jr

评论0

John F.Nash Jr.访谈录.pdf

Game Theory and Nash Equilibrium

A Descriptive Analysis of the Forbes Richest Athletes Dataset R语

java开发笔试题面试题-books2explore:探索的书籍/探索的书籍

Forbes - 06.2021.pdf

Java: High-Performance Apps with Java 9

ssecmmv3final

SIMD Compression and the Intersection of Sorted Integers (simdcompressionarxiv)-计算机科学

6 - Real World Examples.zip_FTF_ball bearing_bearing_bpfo_lienzo

Culture Map

Forbes Personalized News-crx插件

ForBES：通用高效的MATLAB解算器，用于解决非平滑优化问题

德国现代光学设计讲义

Forbes Highest Paid Athletes 1990-2020-数据集

Forbes400:福布斯400富豪榜的JSON Api

forbes

Python_Project_FII:Forbes顶级存储库（B复杂度）-Python Project，FII

danforbesdev:技术爱好者Dan Forbes的个人博客

forbes-cyber-scraper

How to Shape Light with Spatial Light Modulators

python大作业 含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar

仿真电路以及操作方法

【纯干货啊】华为IPD流程管理(完整版).pptx

可编程语言标准IEC61131-3中文版.pdf

OFDM完整仿真过程与教程.zip

信号与系统——保研复习资料.pdf

Landsat_WRS2.zip

最全的Visio形状/图形库

AxureRP9项目原型50套、案例20个、元件库1套.zip

最新资源

python大作业含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar