What is Game Theory?�

• It deals with Bargaining.

​

• The whole process can be expressed Mathematically

​

• Based on Behavior Theory, has a more casual approach towards study of Human Behavior.

​

• It also considers how people Interact in Groups.

​

Game Theory Definition�

Theory of rational behavior for interactive decision problems. In a game, several agents strive to maximize their (expected) utility index by choosing particular courses of action, and each agent's final utility payoffs depend on the profile of courses of action chosen by all agents. The interactive situation, specified by the set of participants, the possible courses of action of each agent, and the set of all possible utility payoffs, is called a game; the agents 'playing' a game are called the players.

​

Definitions�

Definition: Zero-Sum Game – A game in which the payoffs for the players always adds up to zero is called a zero-sum game.

​

Definition: Maximin strategy – If we determine the least possible payoff for each strategy, and choose the strategy for which this minimum payoff is largest, we have the maximin strategy.

​

A Further Definition�

Definition: Constant-sum and nonconstant-sum game – If the payoffs to all players add up to the same constant, regardless which strategies they choose, then we have a constant-sum game. The constant may be zero or any other number, so zero-sum games are a class of constant-sum games. If the payoff does not add up to a constant, but varies depending on which strategies are chosen, then we have a non-constant sum game.

​

Game theory: assumptions�

• (1) Each decision maker has available to him two or more well-specified choices or sequences of choices.

​

• (2) Every possible combination of plays available to the players leads to a well-defined end-state (win, loss, or draw) that terminates the game.

​

• (3) A specified payoff for each player is associated with each end-state.

​

Game theory: assumptions (Cont)�

(4) Each decision maker has perfect knowledge of the game and of his opposition.

​

(5) All decision makers are rational; that is, each player, given two alternatives, will select the one that yields him the greater payoff.

​

��Two-Person Zero-Sum and Constant-Sum Games �

• Two-person zero-sum and constant-sum games are played according to the following basic assumption:

​

• Each player chooses a strategy that enables him/her to do the best he/she can, given that his/her opponent knows the strategy he/she is following.

​

• A two-person zero-sum game has a saddle point if and only if
• Max (row minimum) = min (column maximum)
• all all
• rows columns

​

​

Cont..

• If a two-person zero-sum or constant-sum game has a saddle point, the row player should choose any strategy (row) attaining the maximum on the right side of (1). The column player should choose any strategy (column) attaining the minimum on the right side of (1).
• In general, we may use the following method to find the optimal strategies and value of two-person zero-sum or constant-sum game:
•  
• Step 1 Check for a saddle point. If the game has none, go on to step 2.
•  

​

Cont...

• Step 2 Eliminate any of the row player’s dominated strategies. Looking at the reduced matrix (dominated rows crossed out), eliminate any of the column player’s dominated strategies and then those of the row player. Continue until no more dominated strategies can be found. Then proceed to step 3.
•  
• Step 3 If the game matrix is now 2 x 2, solve the game graphically. Otherwise, solve by using a linear programming method.

​

Zero Sum Games�

• Game theory assumes that the decision maker and the opponent are rational, and that they subscribe to the maximin criterion as the decision rule for selecting their strategy
• This is often reasonable if when the other player is an opponent out to maximize his/her own gains, e.g. competitor for the same customers.

Consider:

Player 1 with three strategies S1, S2, and S3 and Player 2 with four strategies OP1, OP2, OP3, and OP4.

​

Zero Sum Games (Cont)�

Cont...

• Using the maximin criterion, player 1 records the row minima and selects the maximum of these (S2)
• Player 1’s gain is player 2’s loss. Player 2 records the column maxima and select the minimum of these (OP2).
• The value 4 achieved by both players is called the value of the game
• The intersection of S2 and OP2 is called a saddle point. A game with a saddle point is also called a game with an equilibrium solution.
• At the saddle point, neither player can improve their payoff by switching strategies

​

�Two-person zero-sum game with a saddle point�

Player #2

Player#1

​

​

Payoff Matrix

to Player#1

​

Row Domination:

(2)>(1) and (3)>(1), so eliminate Row (1).

Column Domination: (A)>(C) and (B)>(C) so eliminate column A and B.

Reduced Matrix

​

• The best strategy for player #1 is to choose 2.
• The best strategy for player #2 is to choose C.
• This results in a saddle/equilibrium point which gives us these simple strategies for each player

​

​

​

Saddle point

​

​

​

The value shown is the smallest in its row - to player #2’s advantage - and the largest in its column - to player #1’s advantage.

Two-Person Non constant-Sum Games�

• Most game-theoretic models of business situations are not constant-sum games, because it is unusual for business competitors to be in total conflict.

​

• As in two-person zero-sum game, a choice of strategy by each player is an equilibrium point if neither player can benefit from a unilateral change in strategy

​

The Prisoner’s Dilemma�

The prisoner’s dilemma is a universal concept. Theorists now realize that prisoner’s dilemmas occur in biology, psychology, sociology, economics, and law. The prisoner’s dilemma is apt to turn up anywhere a conflict of interests exists -- and the conflict need not be among sentient beings. Study of the prisoner’s dilemma has great power for explaining why animal and human societies are organized as they are. It is one of the great ideas of the twentieth century, simple enough for anyone to grasp and of fundamental importance (...). The prisoner’s dilemma has become one of the premier philosophical and scientific issues of our time. It is tied to our very survival (W. Poundstone,1992, p. 9).

​

Prisoner’s Dilemma�

• Two members of a criminal gang are arrested and imprisoned.
• They are placed under solitary confinement and have no chance of communicating with each other
• The district attorney would like to charge them with a recent major crime but has insufficient evidence
• He has sufficient evidence to convict each of them of a lesser charge
• If he obtains a confession from one or both the criminals, he can convict either or both on the major charge.

​

• �The district attorney offers each the chance to turn state’s evidence.�

• If only one prisoner turns state’s evidence and testifies against his partner he will go free while the other will receive a 3 year sentence.
• Each prisoner knows the other has the same offer
• The catch is that if both turn state’s evidence, they each receive a 2 year sentence
• If both refuse, each will be imprisoned for 1 year on the lesser charge

​

-What would you do if you were Prisoner A?�

In such games, one player’s gain is not equal to the other’s loss. Example: Prisoner’s dilemma�

e.g

​

• Prisoner A thinks: If the other prisoner refuses the deal then I am better off turning state’s evidence. If B turns state’s evidence, I am also better off turning state’s evidence.
• Prisoner B thinks similarly.
• Because there is no communication and no mutual trust, the rational prisoners obtain outcomes that are worst off than if they had cooperated.

​

�General questions in two-person games�

• Communication? We have assumed that there is no communication between the two prisoners. What would happen if they could communicate?

​

• Repetition? In the Prisoner’s Dilemma, the two prisoners interact only once. What would happen if the interaction were repeated?

​

• 2- vs. n-person Games? The Prisoner’s Dilemma is a two-person game, What would happen if there were many players?

​

• Dominance Reasoning? Compelling as the reasoning is that leads to the dominant strategy equilibrium may be, it is not the only way this problem might be reasoned out. Is it really the most “rational” answer after all?

​

Linear Programming and Zero-Sum Games

The value of the game and the optimal strategies for the row and column players reward matrix may be found by solving the row player’s LP and the column player’s LP, respectively.

​

​

�Linear Programming and Zero-Sum Games (Cont)�

The dual of the row (column) player’s LP is the column (row) player’s LP. The optimal objective function value for either the row or the column player’s LP is the value of the game to the row player. If the row player departs from her/his optimal strategy, she/he may receive an expected reward that is less than the value of the game. If the column player departs from her/his optimal strategy, she/he may incur an expected loss that exceeds the value of the game. Complementary slackness may be used to simultaneously solve the row and the column player’s LP’s.

​

Minimax Rule�

• Goal of game tree search: to determine one move for Max player that maximizes the guaranteed payoff for a given game tree for MAX
• Regardless of the moves the MIN will take
• The value of each node (Max and MIN) is determined by (back up from) the values of its children
• MAX plays the worst case scenario:
• Always assume MIN to take moves to maximize his pay-off (i.e., to minimize the pay-off of MAX)
• For a MAX node, the backed up value is the maximum of the values associated with its children
• For a MIN node, the backed up value is the minimum of the values associated with its children

​

Minimax procedure�

• Create start node as a MAX node with current board configuration
• Expand nodes down to some depth (i.e., ply) of lookahead in the game.
• Apply the evaluation function at each of the leaf nodes
• Obtain the “back up" values for each of the non-leaf nodes from its children by Minimax rule until a value is computed for the root node.
• Pick the operator associated with the child node whose backed up value determined the value at the root as the move for MAX

​