29-03-2011, 03:13 PM
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
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