Explain minimax principle with its use

Posted By on October 27, 2014


Download PDF
Branch and Bound Technique
What are NP, P, NP-complete and NP-Hard problems?

Minimax for One-Person Games

The Minimax Regret Principle is based on the Minimax Theorem advanced by John von Neumann, but is geared only towards one-person games. It relies on the concept of regret matrices. To demonstrate, consider an example of a company trying to decide whether or not it should support a research project. Let’s assume that the research project costs c units. If it succeeds, it will bring in a return of r units. If it fails, it will obviously not bring in anything.

The payoff matrix for the company looks like this:

Research
Succeeds Fails
Company Supports research

r – c

-c

Neglect research

0

0

By the maximax principle, a company should always support research if the expected return on it is greater than its cost. By maximin, the company should never support research, since it is risking the cost of the research. Minimax is slightly more complicated.

We need to come up with a matrix that shows the “opportunity cost,” or regret, of the player, depending on each possible decision. For example, if the company supports the research and it fails, the company’s regret will be c, the price of research. If the company supports the research and it succeeds, the company will have no regrets. If the company neglects research and it would have succeeded, its regret value is r-c, the return on the research. So, the minimax regret matrix will look like this:

Research
Succeeds Fails
Company Supports research

0

c

Neglect research

r-c

0

The object is to minimize the maximum possible regret. It is not obvious from the above matrix what the maximum value is. That is, is c greater than r-c? If (r-c) > c, the company should support research. If (r-c) < c, the company should not. In other words, the company should support research if c < r/2, or, if the expected return on research is more than twice its cost.

Minimax for Two-Person Games

In a two-person, zero-sum game, a person can win only if the other player loses. No cooperation is possible. Andrew Colman’s Game Theory and Experimental Games shows the following historical example:

In 1943, the Allied forces received reports that a Japanese convoy would be heading by sea to reinforce their troops. The convoy could take on of two routes — the Northern or the Southern route. The Allies had to decide where to disperse their reconnaissance aircraft — in the north or the south — in order to spot the convoy as early as possible. The following payoff matrix shows the possible decisions made by the Japanese and the Allies, with the outcomes expressed in the number of days of bombing the Allies could achieve with each possibility:

Japanese Route
North South
Allies Reconnaissance North

2

2

South

1

3

By this matrix, if the Japanese chose to take the southern route while the Allies decided to focus their recon planes in the north, the convoy would be bombed for 2 days. The best outcome for the Allies would be if they placed their airplanes in the south and the Japanese took the southern route. The best outcome for the Japanese would be to take the northern route, provided the Allies were looking for them in the south.

To minimize the worst possible outcome, the Allies would have to choose the north as the focus of their reconnaisance efforts. This ensures them 2 days of bombing, whereas they risk only 1 day of bombing if they focus on the south. Therefore, by minimax, the best strategy for them would be to focus on the north.

The Japanese can use the same strategy. The worst possible outcome for them is the 3 days of bombing which might occur if they took the southern route. Therefore, the Japanese would take the northern route.

It is, in fact, what had occurred: both the Allies and the Japanese chose the north, and the Japanese convoy was bombed for 2 days.

The previous matrix had a saddle point, meaning that both the Japanese and the Allies settled on the (North, North) square as the best outcome for both of them. Neither could do any better if the opponent was rational. In this case, the maximin and the minimax strategies produce the same result. Notice that if the Allies were following maximax, they would choose the South, and surely forfeit one day of bombing.

 

Branch and Bound Technique
What are NP, P, NP-complete and NP-Hard problems?

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com