Теория игр: Текст лекций. Саакян Г.Р. - 22 стр.

                                                                                          21

       Если в матрице A одна из строк ( j -я) доминирует другую строку ( i -ю), то число
строк в матрице A можно уменьшить путем отбрасывания доминируемой строки ( i -й).
       Далее, будем говорить, что k -й столбец матрицы A
                                            a1k
                                            a2 k
                                             M
                                            amk
не меньше l -го столбца этой матрицы
                                            a1l
                                            a2 l
                                             M
                                              aml
если одновременно выполнены следующие m неравенств:
                            a1k ≥ a1l , a2 k ≥ a2l , ..., amk ≥ aml .
       При этом говорят также, что l -й столбец доминирует k -й столбец или что стратегия
Bl игрока B доминирует стратегию Bk .
       Замечание. Игрок B поступит разумно, если будет избегать стратегий, которым в
матрице игры отвечают доминируемые столбцы.
       Если в матрице A один из столбцов ( l -й) доминирует другой столбец ( k -й), то число
столбцов в матрице A можно уменьшить путем отбрасывания доминируемого столбца ( k -
го).
       Важное замечание. Оптимальные смешанные стратегии в игре с матрицей, получен-
ной усечением исходной за счет доминируемых строк и столбцов, дадут оптимальное реше-
ние в исходной игре: доминируемые чистые стратегии игроков в смешении не участвуют –
соответствующие им вероятности следует взять равными нулю.
       Пример 6. Рассмотрим игру с матрицей
                                   ⎛ −1    0 2   1 ⎞
                                   ⎜                ⎟
                                   ⎜− 2    0 1   0 ⎟
                                   ⎜ 2                .
                                           1 −1 − 2⎟
                                   ⎜⎜               ⎟
                                    ⎝ −1   0 2   1 ⎟⎠
       Сравнивая строки матрицы, видим, что 1-я строка совпадает с 4-й строкой, или, что то
же, стратегия A4 дублирует стратегию A1 . Тем самым, одну из этих строк можно вычерк-
нуть, не нанося ущерба решению:
                                   ⎛ −1 0 2  1 ⎞
                                   ⎜           ⎟
                                   ⎜ − 2 0 1 0 ⎟.
                                   ⎜ 2 1 −1 − 2⎟
                                   ⎝           ⎠
       Сравнивая поэлементно 1-ю и 2-ю строки, замечаем, что 1-я строка доминирует 2-ю
строку, или, что то же, стратегия A1 доминирует стратегию A2 . Это вновь позволяет умень-
шить число строк матрицы:
                                   ⎛ −1 0 2   1 ⎞
                                   ⎜⎜           ⎟⎟ .
                                    ⎝ 2 1 −1 − 2⎠