Presented by:
SANDIP ROY

---

[attachment=11262]
What is a game?
- a competitive situation
o A game has the following:
1. Set of players D = {Pi | 1 <= i <= n}
2. Set of rules R
3. Set of strategies Si for each player Pi
4. Set of outcomes O
5. Pay off ui(o) for each player i and for each outcome o in O
What is game theory?
 Game Theory can be regarded as a multi – agent decision problem.
 Players have to make certain moves on which their payoff or rewards depends.
 Each player follows certain rules while making these moves.
 Each player is supposed to behave rationally.
 Each player tries to maximize his/her payoff irrespective to what other players are doing.
Classification of Game Theory
 Non co – operative game theory: The players work independently without assuming anything about what other players are doing.
 Co – Operative game theory: Players may co-operate with one another.
Coin Matching Game
1. Set of Players: The two players who are choosing either Head or Tail from the set of players i.e. P = {P1, P2}
2. Set of Rules: There are certain rules which each player has to follow while playing the game. Each player chooses either Head or Tail.
3. Set of strategies: S1 = {H, T} and S2 = {H, T} are the strategies of the two players.
o Set of Outcomes: {Loss, Win}
o S1 X S2 = { (H, H), (H, T), (T, H), (T, T)} is the strategy profile.
o Pay off: This is the amount of benefit a player derives if a particular outcome happens.
Here the payoff in coin matching game be,
u1(Win) = 100, u1(Loss) = 0.
u2(Win) = 100, u2(Loss) = 0.
Payoff matrix
o Player A has m strategies A1, A2, … , Am.
o Player B has n strategies B1, B2, … , Bn.
o assume that Player A is always gainer and Player B is always loser.
The Maximin - Minimax Principle
o Player A, minimum value in each row represents the least gain to him, row minima.
o Select the strategy the maximizes his minimum gains, called maximin principle.
o Player B, maximum value of each column represents the maximum loss to him, column maxima.
o Select the strategy the minimizes his maximum losses, called minimax principle.
Value of game
o If maximin value equals the minimax value, the game have a saddle point or equilibrium point.
o The amount of payoff at an equilibrium point is known as the value of game.
• Tic – Tac – Toe game
- there are two players x and o.
- Outcomes are O = { x wins, o wins, draw}
ux(x wins) = 1 ux(o wins) = -1 ux(draw) = 0
uo(x wins) = -1 uo(o wins) = 1 uo(draw) = 0
____________________________________________________
0 0 0
Chess game
- two players, one playing with white pieces and other playing with black pieces.
- three possible outcomes, O = { Black wins, White wins, Draw}.
Prisoner’s Dilemma game
 Two suspects arrested for a crime
 Prisoners decide whether to confess or not to confess
 If both confess, both sentenced to 5 years of jail
 If both do not confess, then both will be sentenced to 1 year of jail
 If one confesses and the other does not, then the confessor gets freed (0 year of jail) and the non-confessor sentenced to 10 years of jail
 What should each prisoner do?
Modern computer science and modern game theory originated in large measure at the same place and time.
Bidding up to 50
 Two-person game.
 Start with a number from 1-4.
 You can add 1-4 to your opponent’s number and bid that
 The first person to bid 50 (or more) wins.
 Example:
3, 5, 8, 12, 15, 19, 22, 25, 27, 30, 33, 34, 38, 40, 41, 43, 46, 50
 Game theory tells us that person 2 always has a winning strategy.
 Bid 5, 10, 15, …, 50
 Easy to train a computer to win.
Computer science applications
 Auction
 E-commerce
 Networking
 Artificial intelligence