What is saddle point in a matrix?

Answer 1

Given a RxC Matrix, A, i.e. R rows and C columns we define a Saddle-Point as

Saddle_Pt (A(i,j))

≡ A(i,j) is the minimum of Row i and the maximum of Col j.

e.g.

1 2 3

4 5 6

7 8 9

-- 7 is Saddle_Pt.

at position (3,1)

There may be more than one Saddle-Pt,

In game theory, we look at the minimum value of all the rows which is this case is

(1,4, and 7,) We then take the max of those which is 7. This is the maxmin.

Then we look at the max of all the columns which are (7,8, and 9) and we take the min of those which is 7. So position (3,1) is the number 7 which would be the saddle point. The idea is if, the number in C means that person pays R that amount, then we want the be number in the matrix fro both R and C.

For example if R picks first and he pick row 1, then to minimize his payout, C picks 1. However, row three always has a better payout for R so he would never pick row 1 or 2. We can eliminate them from the matrix. We are left with

(7,8,9) But if you are C, want to pay the least and would always pick 7 if R picked that row. The point that is the greatest of the mimima and the least of the maxima is called a saddle point.

Sometimes there is no saddle point. We then pick the "best" policy and doing so involves some randomized strategies.

One more example is

2 -2 -3

1, 0, 2

-1 -1 3

In this example -2 means C pays -2 to R in other words R pays C 2 units.

The saddle point is 0 because it is the max(min of row) and it equals the

min ( max of columns)