Top

1994 | Book

Read chapter Read first chapter

Introduction to Game Theory

Author: Peter Morris

Publisher: Springer New York

Book Series : Universitext

Included in: Professional Book Archive

About this book

The mathematical theory of games has as its purpose the analysis of a wide range of competitive situations. These include most of the recreations which people usually call "games" such as chess, poker, bridge, backgam mon, baseball, and so forth, but also contests between companies, military forces, and nations. For the purposes of developing the theory, all these competitive situations are called games. The analysis of games has two goals. First, there is the descriptive goal of understanding why the parties ("players") in competitive situations behave as they do. The second is the more practical goal of being able to advise the players of the game as to the best way to play. The first goal is especially relevant when the game is on a large scale, has many players, and has complicated rules. The economy and international politics are good examples. In the ideal, the pursuit of the second goal would allow us to describe to each player a strategy which guarantees that he or she does as well as possible. As we shall see, this goal is too ambitious. In many games, the phrase "as well as possible" is hard to define. In other games, it can be defined and there is a clear-cut "solution" (that is, best way of playing).

Frontmatter

1. Games in Extensive Form

Abstract

All the games that we consider in this book have certain things in common. These are:

There is a finite set of players (who may be people, groups of people, or more abstract entities like computer programs or “nature” or “the house”).
Each player has complete knowledge of the rules of the game.
At different points in the game, each player has a range of choices or moves. This set of choices is finite.
The game ends after a finite number of moves.
After the game ends, each player receives a numerical payoff. This number may be negative, in which case it is interpreted as a loss of the absolute value of the number. For example, in a game like chess the payoff for winning might be +1, for losing −1, and for a draw 0.

Peter Morris

2. Two-Person Zero-Sum Games

Abstract

Let $ \vec \pi $ be a game in normal form with strategy sets X₁,...,X_N We say that this game is zero-sum if

$$ \sum\limits_{i = 1}^N {{\pi _i}\,({x_1},\,.\,.\,.\,,\,{x_N})\, = \,0,} $$

for every choice of x_i ∈ X_i, 1 ≤ i ≤ N. The corresponding definition for a game in extensive form states that the sum of the components of $ \vec p(v) $ is zero for each terminal vertex v. This condition is certainly true for ordinary recreational games. It says that one player cannot win an amount unless the other players jointly lose the same amount. Nonrecreational games, however, tend not to be zero-sum. Competitive situations in economics and international politics are often of the type where the players can jointly do better by playing appropriately, and jointly do worse by playing stupidly. The phrase “zero-sum game” has entered the language of politics and business.

Peter Morris

3. Linear Programming

Abstract

The subject of this chapter is the part of the field of linear programming which we will need later in the book. We will use it to solve matrix games. In addition, the theoretical aspects of linear programming developed here will, when applied to game theory, give us the minimax theorem and other theorems about matrix games.

Peter Morris

4. Solving Matrix Games

Abstract

In this chapter, we apply linear programming to matrix games. The first task is to set up the problem of computing optimal strategies for the row player and column player as a dual/primal pair of linear programming problems. The minimax theorem will then be proved. The rest of the chapter consists of examples.

Peter Morris

5. Non-Zero-Sum Games

Abstract

In studying games which are not zero-sum, the distinction between cooperative and noncooperative games is crucial. There are two types of cooperation among players. The first is the making of binding agreements before play starts about how they will play (that is, coordination of strategies); the second is the making of agreements about sharing payoffs (or about “side payments” from one player to another). The aim of the first type is to increase the payoffs to the cooperating players; the aim of the second is for one player (or group of players) to induce another player to coordinate strategies.

Peter Morris

6. N-Person Cooperative Games

Abstract

In the previous chapter, we studied cooperative games in which the players could coordinate their strategies but could not share payoffs. In the games considered in this chapter, the players are permitted to cooperate fully. Sets of players (called coalitions) cannot only make binding agreements about joint strategies, but can also agree to pool their individual payoffs and then redistribute the total in a specified way. In order for this latter kind of cooperation to be possible, we must assume that the payoffs are in some transferable quantity, such as money. The number of players is not explicitly restricted to be greater than two, but might as well be—the case of two players turns out either to be trivial or to have been covered in our earlier work.

Peter Morris

7. Game-Playing Programs

Abstract

Computer programs which are capable of playing chess and other games at a high level of skill have become familiar to most of us in recent years. In fact, there are chess-playing programs which can beat all but the best human players, and many experts think that the world champion will be a program within the next few years (see [Lev84]). Our aim in this chapter is to discuss the mathematical background involved in these programs.

Peter Morris

Backmatter

Title: Introduction to Game Theory
Author: Peter Morris
Publisher: Springer New York
Electronic ISBN: 978-1-4612-4316-8
Print ISBN: 978-0-387-94284-1
DOI: https://doi.org/10.1007/978-1-4612-4316-8

Springer Professional

Introduction to Game Theory

About this book

Table of Contents

Frontmatter

1. Games in Extensive Form

2. Two-Person Zero-Sum Games

3. Linear Programming

4. Solving Matrix Games

5. Non-Zero-Sum Games

6. N-Person Cooperative Games

7. Game-Playing Programs

Backmatter