GAME THEORY
WHAT IS GAME THEORY?
Game theory may be de ned as the study of mathematical models of interaction between rational,
intelligent decision maker, usually referred to as players or agents.
The interaction may involve con ict as well as cooperation.
Game theory provides general mathematical techniques for analyzing situations in which two or more
players make decisions that in uence one another’s welfare.
A game could be considered as a mathematical model of a situation where every player strives to
obtain her best possible outcome, knowing fully well that all other players are also striving to obtain
their respective best possible outcomes.
fi
fl
fl
SOME DEFINITIONS
Preferences - The preferences that a player has over outcomes can be formalized as a preference
relation over the set of outcomes S.
Utilities - The utility function or payoff function of a player is a real valued function defined on the
set of all outcomes or strategy profiles. The utility function of each player maps multi-dimensional
information (strategy profiles) into real numbers to capture preferences.
Rationality - An agent is said to be rational if the agent always makes decisions in pursuit of her
own objectives.
Intelligence - This notion means that each player in the game knows everything about the game
that a game theorist knows, and the player is competent enough to make any inferences about the
game that a game theorist can make.
Common Knowledge - A fact is common knowledge among the players if every player knows it,
every player knows that every player knows it, and so on. That is, every statement of the form
“every player knows that every player knows that ··· every player knows it” is true forever.
CLASSIFICATION
Non-cooperative Games and Cooperative Games
Static Games and Dynamic Games
Different Representational Forms
Extensive form
Strategic form
Games with Perfect Information and Games with Imperfect Information
Knowledge of the history of game
Complete Information and Incomplete Information Games
Some players know more information than others
STRATEGIC FORM GAME
Explanation
The strategies are also called actions or more specifically pure strategies.
The set S is the collection of all strategy profiles or strategy vectors of the players,
defined by the Cartesian product S1 × S2 × ··· × Sn.
Every profile of strategies corresponds to an outcome in the game.
STRATEGIC FORM GAME: STUDENT CO-ORDINATION GAME
Consider a student co-ordination game with the following payoffs. Obtain its strategic form representation.
TWO PERSON ZERO SUM GAME
Two player zero-sum games describe strictly competitive situations involving two players.
Matrix games are two player zero-sum games with finite strategy sets.
It was shown by von Neumann and Morgen- stern that linear programming can be used to solve these
games.
A critical point to note is that a player maximizing her payoff is equivalent to minimizing the payoff of the
other player.
For this reason, these games are also called strictly competitive games.
By convention, player 1 is called the row player and player 2 is called the column player.
DEFINITION – GAME THEORY TRIPLET
Suppose S1 = {s11,s12,...,s1m} and S2 = {s21,s22,...,s2n}
Assume that S1 = {1, 2, . . . , m} and S2 = {1,2,...,n}
Since the payoffs of one player are just the negative of the payoffs of the other player,
these games can be represented by a matrix A with m rows and n columns with aij =
u1(i,j) ∀i ∈ S1 and ∀j ∈ S2.
The number aij is the payoff to player 1 (row player) and −aij is the payoff to player 2
(column player) when player 1 chooses strategy i and player 2 chooses strategy j.
EXAMPLES
First note that maximizing the payoff of any player is the same as minimizing the payoff of the other player. When
the row player plays strategy i, the column player plays a strategy that will minimize the row player’s payoff
The above payoff is the minimum guaranteed payoff to the row player when she plays i. The row player will
therefore look for a pure strategy i that maximizes the above. That is, a strategy i such that
In other words, an optimal strategy for the row player is maxminimization.
Such a strategy of the row player is called the maxmin strategy or security strategy of the row player.
Similarly, when the column player plays pure strategy j, he assures himself of a payoff equal to
Thus, the maxmin value and minmax value play a natural role in describing the optimal strategies
of players in a matrix game.
SADDLE POINTS AND PURE STRATEGY NASH EQUILIBRIUM
SADDLE POINTS AND PURE STRATEGY NASH EQUILIBRIUM
SADDLE POINTS AND PURE STRATEGY NASH EQUILIBRIUM
SOME OBSERVATIONS ON SADDLE POINT
PURE STRATEGY NASH EQUILIBRIUM
PURE STRATEGY NASH EQUILIBRIUM
PURE STRATEGY
NASH EQUILIBRIUM
THEOREMS ON SADDLE POINT