Operations Research :- Unit IV Game Theory and Dynamic Programming

Unit IV Game Theory and Dynamic Programming

Syllabus:

Introduction, 2 person zero sum games, Maximi - Minimax principle, Principle of Dominance, Solution for mixed strategy problems, Graphical method for 2 x n and m x 2 games. Recursive nature of computations in Dynamic Programming, Forward and backward recursion, Dynamic Programming Applications – Knapsack, Equipment replacement, Investment models

4.1 Introduction

Game theory deals with decision situations in which two intelligent opponents with conflicting objectives are trying to outdo one another. Typical examples include launching advertising campaigns for competing products and planning strategies for warring armies.

In a game conflict, two opponents, known as players, will each have a (finite or infinite) number of alternatives or strategies. Associated with each pair of strategies is a payoff that one player receives from the other. Such games are known as two-person zero-sum games because a gain by one player signifies an equal loss to the other. It suffices, then, to summarize the game in terms of the payoff to one player. Designating the two players as A and B with m and n strategies, respectively, the game is usually represented by the payoff matrix to player A as

The representation indicates that if A uses strategy i and B uses strategy j, the payoff to

A is a_ij which means that the payoff to B is -a_ij

Real-life Application-Ordering Golfers on the Final Day of Ryder Cup Matches In the final day of a golf tournament, two teams compete for the championship. Each team captain must submit an ordered list of golfers (a slate) that automatically determines the matches. It is plausible to assume that if two competing players occupy the same order in their respective slates then there is 50-50 chance that either golfer will win the match. This probability will increase when a higher-order golfer is matched with a lower-order one. The goal is to develop an analytical procedure that will support or refute the idea of using slates. Case 12, Chapter 24 on the CD provides details on the study.

Game theory is a type of decision theory in which one’s choice of action is determined after taking into account all possible alternatives available to an opponent playing the same game,

rather than just by the possibilities of several outcomes. The game theory has only been capable of analysing very simple competitive situations. Thus, there has been a great gap

between what the theory can handle and most actual competitive situations in industry and elsewhere. So the primary contribution of game theory has been its concepts rather than

its formal application to solving real problems. Game is defined as an activity between two or more persons involving activities by each person according to a set of rule at the end of which each person receives some benefit or satisfaction or suffers loss (negative benefit). The set of rules defines the game. Going through the set of rules once by the participants defines a play.

Characteristics of Game Theory

There can be various types of games. They can be classified on the basis of the following characteristics.

i. Chance of strategy: If in a game, activities are determined by skill, it is said to be a game of strategy; if they are determined by chance, it is a game of chance. In general, a game may involve game of strategy as well as a game of chance. In this chapter, simplest models of games of strategy will be considered.

ii. Number of persons: A game is called an n-person game if the number of persons playing is 11.The person means an individual or a group aiming at a particular objective.

iii. Number of activities: These may be finite or infinite.

iv. Number of alternatives (choices) available to each person in a particular activity may also be finite or infinite. A finite game has a finite number of activities, each involving a finite number of alternatives, otherwise the game is said to be infinite.

v. Information to the players about the past activities of other players is completely available, partly available, or not available at all.

vi. Payoff: A quantitative measure of satisfaction a person gets at the end of each play is called a payoff. It is a real-valued function of variables in the game.

Let vi be the payoff to the player Pi, 1 < i < n, in an n person game. If ,  then the game is said to be a zero-sum game.

4.2 Two person zero sum games

A game with only two players (say, Player A and Player B) is called a ‘two person, zero-sum game’ if the losses of one player are equivalent to the gains of the other, so that the sum of

their net gain is zero.

Two-person, zero-sum games are also called rectangular games as these are usually represented by a payoff matrix in rectangular form.

Payoff Matrix: Suppose the player A has m activities and the player B has n activities. Then a payoff matrix can be formed by adopting the following rules:

1.     Row designations for each matrix are activities available to player A.

2.     Column designations for each matrix are activities available to player B.

3.     Cell entry ‘vij , is the payment to player A in A’s payoff matrix when A chooses the activity i and B chooses the activity.

4.     With a ‘zero-sum, two person game’, the cell entry in the player B’ s payoff matrix will be negative of the corresponding cell entry ‘Vi}, in the player A’s payoff matrix so that sum of payoff matrices for player A and player B is ultimately zero.

In order to make the above concepts a clear, consider the coin matching game involving two players only. Each player selects either a head H or a tail T. If the outcomes match (H, H or T, T), A wins Re 1from B, otherwise B wins Re 1from A. This game is a two-person zero-sum game. since the winning of one player is taken as losses for the other. Each has his choices between two pure strategies (H or T). This yields the following (2 x 2) payoff matrix to player A.

It will be shown later that the optimal solution to such games requires each player to play one pure strategy or a mixture of pure strategies.

Optimal Solution of Two-Person Zero-Sum Games

Because games are rooted in conflict of interest, the optimal solution selects one or more strategies for each player such that any change in the chosen strategies does not improve the payoff to either player. These solutions can be in the form of a single pure strategy or several strategies mixed according to specific probabilities. The following two examples demonstrate the two cases.

Example 13.4-2

Thus, in the coin-tossing example, the value of the game must lie between -$1 and +$1.

4.3 Maximi - Minimax principle

The maximum of the minimum gains is called the maximin value of the game and the corresponding strategy is called the maximin strategy. Similarly the minimum of the maximum losses is called the minimax value of the game and the corresponding strategy is called the minimax strategy. If both the values are equal, then that would guarantee the best of the worst results.

Minimax (Maximin) Criterion And Optimal Strategy

The ‘minimax criterion of optimality’ states that if a player lists the worst possible outcomes of all his potential strategies, he will choose that strategy to be most suitable for him which corresponds to the best of

these worst outcomes. Such a strategy is called an optimal strategy.

Example 1. Consider (two-person, zero-sum) game matrix, which represents payoff to the player A. Find, the optimal strategy, if any.(See Table)

4.4 Principle of Dominance

4.5 Solution for mixed strategy problems

4.6 Graphical method for 2 x n and m x 2 games

2x2 two person game and 2xn and mx2 games:

When the number of players in a game is two and each player has exactly two strategies, the

game is referred to as 2x2 two person game.

A game in which the first player has precisely two strategies and the second player has

three or more strategies is called an 2xn game.

A game in which the first player has three or more strategies and the second player has

exactly two strategies is called an mx2 game.

4.7 Recursive nature of computations in Dynamic Programming

The definition of the state leads to the following unifying framework for DP.

4.8 Forward and backward recursion

4.9 Dynamic Programming Applications – Knapsack, Equipment replacement, Investment models

4.9.1 Knapsack/Fly-Away/Cargo-Loading Model

The knapsack model classically deals with the situation in which a soldier (or a hiker) must decide on the most valuable items to carry in a backpack. The problem paraphrases

4.9.2   Equipment replacement

4.9.3 Investment model