DF4 - Dominated strategies

DF4 - Dominated strategies

Some choices can be replaced by another choice that is at least as good against every possible response. You will identify dominated rows and columns, reduce a game carefully, and explain why the reduction preserves its optimal value. Equality cases matter: a removable strategy need not be worse at every outcome.

Comparing rows and columns

Can removing choices leave the best guaranteed pay-off unchanged? Consider two rows giving (4,2,5)(4,2,5) and (1,2,3)(1,2,3). The first row gives the row player at least as much for every column: 4≥14\geq1, 2=22=2, 5≥35\geq3. The smaller row offers no advantage against any response.

Throughout, entries are the row player's gains. The row player wants larger values and the column player wants smaller values.

Dominated pure strategy

A row is dominated by another row when every entry of the other row is at least as large, with at least one strict inequality. A column is dominated by another column when every entry of the other column is at most as large, with at least one strict inequality. If every comparison is strict, the domination is strict; otherwise it is weak. Identical rows or columns are equivalent choices, and one copy may be kept.

Give the component-by-component comparisons, including any equalities, so the reason for a deletion is clear. Equivalent strategies give the same pay-off against every response; either representative can be kept.

Worked example 1: the row player prefers larger entries

Question. In (425123204)\begin{pmatrix}4&2&5\\1&2&3\\2&0&4\end{pmatrix}, with rows A, B, C, show that B can be removed by row domination.

Plan. Compare B with one alternative against each column separately.

4≥1,2≥2,5≥3.4\geq1,\qquad2\geq2,\qquad5\geq3.

Row A never pays less than B, and pays more in columns 1 and 3.

Answer. A dominates B, so we may remove B when seeking an optimal strategy and value. The equality in column 2 does not prevent this reduction.

Check. If the opponent chooses column 2, replacing B by A leaves the pay-off at 2. In either other column it raises the pay-off. There is no column in which this replacement harms the row player.

Keep the matrix unchanged and compare columns instead. Only the player's objective changes: a smaller recorded gain is now preferable.

Worked example 2: the column player prefers smaller entries

Question. In the same matrix, with columns X, Y, Z, show that Z can be removed by column domination.

Plan. Compare X and Z down all three rows.

(412)≤(534)entry by entry.\begin{pmatrix}4\\1\\2\end{pmatrix} \leq \begin{pmatrix}5\\3\\4\end{pmatrix} \quad\text{entry by entry}.

Answer. X dominates Z for the column player. Remove Z, the column with larger pay-offs to the row player.

Check. If the row player chooses B, column X makes their gain 1 rather than 3. The column player's gain improves from −3-3 to −1-1. The other two rows confirm the same direction of improvement.

You need all comparisons, not just a favourable total or average. Rows (5,0)(5,0) and (2,2)(2,2) cross in their preferences; neither dominates the other, even though their sums differ.

Watch out

Rows: keep the larger entries. Columns: keep the smaller entries. A single reversed comparison defeats the proposed domination; comparing row sums or column sums does not establish it.

Identify one safe deletion of each kind.

Reducing a game in stages

A deletion changes which responses remain. A strategy that was not dominated before can become dominated afterwards. Keep the original strategy labels on the surviving rows and columns so that a final answer still describes the original game.

Search for a valid comparison, remove only the strategy it justifies, and inspect the reduced matrix again. Do not delete every row that fails to be best in some column: a row can be useful without having the largest entry anywhere.

Worked example 3: remove a row, then a column

Question. Reduce (415203142)\begin{pmatrix}4&1&5\\2&0&3\\1&4&2\end{pmatrix}, with rows A, B, C and columns X, Y, Z, using dominated pure strategies.

Plan. Delete the dominated row first, then compare the remaining columns.

A dominates B since 4>24>2, 1>01>0, 5>35>3. Removing B leaves

XYZA415C142.\begin{array}{c|rrr} &X&Y&Z\\\hline A&4&1&5\\ C&1&4&2 \end{array}.

Now X dominates Z since 4<54<5, 1<21<2. Therefore

XYA41C14\begin{array}{c|rr} &X&Y\\\hline A&4&1\\ C&1&4 \end{array}

is the reduced game.

Answer. Keep rows A, C and columns X, Y. No further pure domination is possible: each pair crosses in its comparisons.

Check. Both deletions have a direct replacement that never worsens the relevant player's pay-off. The remaining row minima are both 1 and column maxima both 4, so the reduction has not manufactured a saddle point.

Change only the entry at (B, Z) from 3 to 6. B can no longer be removed first using A, because 5<65<6. A different order still works.

Worked example 4: the order of discovery changes

Question. Reduce (415206142)\begin{pmatrix}4&1&5\\2&0&6\\1&4&2\end{pmatrix}, with the same labels.

Plan. Look for a column deletion before retrying the rows.

X dominates Z because 4<54<5, 2<62<6, 1<21<2. After deleting Z,

XYA41B20C14.\begin{array}{c|rr} &X&Y\\\hline A&4&1\\ B&2&0\\ C&1&4 \end{array}.

A now dominates B because 4>24>2, 1>01>0.

Answer. The same reduced game (4114)\begin{pmatrix}4&1\\1&4\end{pmatrix} remains, with original rows A, C and columns X, Y.

Check. Before deletion, B's only advantage over A was in column Z. The column player can replace Z by the smaller column X against every row, so that advantage cannot force a better outcome against optimal opposition. The surviving two-by-two comparisons still cross.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account