CS905N Lect 1 notes
Game Theory
Game Theory can be regarded as a multi-agent decision problem. Which means there are many people contending for limited rewards/payoffs. They have to make certain moves on which their payoff depends.
These people have to follow certain rules while making these moves. Each player is suposed to behave rationally. Rationality: In the language of Game Theory rationality implies that each player tries to maximize his/her payoff irrespective to what other players are doing.
In essence each player has to decide a set of moves which are in accordance with the rules of the game and which maximize his/her rewards.
Game Theory can be classified in two branches
1. Non co-operative game theory : In this case the players work independently without assuming anything about what other players are doing.
2. Co-operative game theory: Here players may co-operate with one another.
Game Theory has found applications in Economic, Evolutionary Biology, Sociology, Political Science etc, now Its finding applcations in Computer Science.
What is a game?
A game has the following
1.
2.
3.
4.
5.

Set of players
Set of rules
Set of Strategies
Set of Outcomes.
Pay off

D = { Pi | 1 <= i <= n}
R
Si for each player Pi
O
ui (o) for each player i and for each outcome o e O

Example 1{Coin Matching Game}
Coin Matching Game : Two players choose independently either Head or Tail and report it to a central authority. If both choose the same side of the coin , player 1 wins, otherwise 2 wins.
A game has the following :1. Set of Players.
The two players who are choosing either Head or Tail in the Coin Matching Game form the set of players
i.e. P={P1,P2}
2. Set of Rules.
R
There are ceratin rules which each player has to follow while playing the game. Each player can safely assume that others are following these rules. In coin matching game each player can choose either Head or