Game Theory - Lecture Notes.pdf - Teoria gier - Piffony

IE675 Game Theory

Lecture Note Set 1

Wayne F. Bialas 1

Friday, March 30, 2001

1 INTRODUCTION

1.1 What is game theory?

Game theory is the study of problems of conict and cooperation among independent

decision-makers.

Game theory deals with games of strategy rather than games of chance.

The ingredients of a game theory problem include

players (decision-makers)

choices (feasible actions)

payoffs (benets, prizes, or awards)

preferences to payoffs (objectives)

We need to know when one choice is better than another for a particular player.

1.2 Classication of game theory problems

Problems in game theory can be classied in a number of ways.

1.2.1 Static vs. dynamic games

In dynamic games, the order of decisions are important.

Question 1.1. Is it ever really possible to implement static decision-making in prac-

tice?

1 Department of Industrial Engineering, University at Buffalo, 342 Bell Hall, Box 602050, Buffalo,

NY 14260-2050 USA; E-mail: bialas@buffalo.edu; Web: http://www.acsu.buffalo.edu/˜bialas.

without written permission. This document produced March 30, 2001 at 2:31 pm.

1-1

1.2.2 Cooperative vs. non-cooperative

In a non-cooperative game, each player pursues his/her own interests. In a cooperative

games, players are allowed to form coalitions and combine their decision-making problems.

Non-cooperative Cooperative

Math programming Cooperative

Static Non-cooperative

Game

Game Theory

Theory

Cooperative

Dynamic Control Theory

Dynamic

Games

Note 1.1. This area of study is distinct from multi-criteria decision making.

Flow of information is an important element in game theory problems, but it is sometimes

explicitly missing.

noisy information

deception

1.2.3 Related areas

differential games

optimal control theory

mathematical economics

1.2.4 Application areas

corporate decision making

defense strategy

market modelling

public policy analysis

environmental systems

distributed computing

telecommunications networks

1-2

1.2.5 Theory vs. simulation

The mathematical theory of games provides the fundamental laws and problem structure.

Games can also be simulated to assess complex economic systems.

1.3 Solution concepts

The notion of a “solution” is more tenuous in game theory than in other elds.

Denition 1.1. A solution is a systematic description of the outcomes that may emerge

from the decision problem.

optimality (for whom??)

feasibility

equilibria

1.4 Games in extensive form

1.4.1 Example: Matching Pennies

Player 1: Choose H or T

Player 2: Choose H or T (not knowing Player 1’s choice)

If the coins are alike, Player 2 wins 1 cent from Player 1

If the coins are different, Player 1 wins 1 cent from Player 2

Written in extensive form, the game appears as follows

1-3

Information

Set

Player 1

Player 2

(-1,1)

(1,-1)

(-1,1)

In order to deal with the issue of Player 2’s knowledge about the game, we introduce the

concept of an information set . When the game’s progress reaches Player 2’s time to move,

Player 2 is supposed to know Player 1’s choice. The set of nodes, S 1 , is an information set

for Player 2.

A player only knows the possible options emanating from an information. A player does

not know which node within the information set is the actual node at which the progress of

play resides.

There are some obvious rules about information sets that we will formally describe later.

1-4

For example, the following cannot occur. . .

7KL FDQQR

KDSSHQ

Player 1

Player 2

Denition 1.2. A player is said to have perfect information if all of his/her information

sets are singletons.

JDP

ZLW

SHUIHF

LQIRUPDWLRQ

Player 1

Player 2

1-5

Game Theory - Lecture Notes.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: