Решение матричных игр сведением к линейной задаче оптимизации

↑

⇐ ПредыдущаяСтр 12 из 28Следующая ⇒

Рассмотрим конечную игру двух лиц с нулевой суммой. Пусть игрок 1 имеет т ходов — ,а игрок 2 (противник) -— п ходов . Если игрок 1 выбрал ход , игрок 2 выбрал , то они получают выигрыш, соответственно:  причем  Из элементов можно составить матрицу

которая называется платежной- Тогда ходу  игрока 1 будет соответствовать выбор им  строки матрицы А, а ходу  для игрока 2—   столбца. Цель игрока 1 максимизировать  игрока 2 — максимизировать  ( или минимизировать ). Игроки выбирают свои ходы не зная какие ходы выберет противник. Считая противника разумным, игроки могут придерживаться осторожных (перестраховочных) стратегий. Игрок 1 в каждой строке находит минимальный элемент , а затем находит свой гарантированный выигрыш . Выбор соответствующий строки (строк) будет его макси-минной стратегией (при любом поведении игрока 2 он получит не менее ). Аналогично игрок 2 находит  и . Его минимаксной стратегией будет выбор соответствующего столбца (при любом поведении игрока а он обеспечит себе проигрыш не более ).

Если , то это значит, что существует элемент  который будет минимальным в строке  и максимальным в столбце . Тогда стратегии  и  будут оптимальными для игроков 1 и 2. Величина  называется ценой игры, а пара ходов ( ) — седловой точкой игры.

Если седловой точки у игры нет и розыгрыши совершаются неоднократно, то естественно для игрока 1 попытаться увеличить а, а для игрока 2 — уменьшить .

Смешанными стратегиями игроков 1 и 2 будем называть соответ­ственно  и , где — вероятности (частоты) применения чистых стратегий  и  при этом .Величина — средний выигрыш (математическое ожидание игрока 1).

Основная теорема. Любая матричная игра имеет пару оптимальных смешанных стратегий , обладающую свойством:

и цену игры . (То есть если игрок 1 не придерживается р*, а игрок 2 придерживается q^* тогда он может получить меньше . Соответственно для игрока 2.)

Будем считать .что все элементы платежной матрицы неотрицатель­ны (если это не так, то можно ко всем ее элементам прибавить некоторое положительное число L, переводящее платежи в область неотрицатель­ных значений; при этом решение игры р* и q* не изменится, цена игры лишь увеличится на L. Тогда

Введем обозначения:

Известно, что задача нахождения р* и q* сводится к паре взаимодвойственных задач:

                             (1)

                            (2)

Предположим, что мы нашли их решения (оно всегда существует)

Тогда:

Замечание. Задачу (2) удобно решать, применяя симплекс-метод, а задачу (1) — двойственный симплекс-метод. Однако на практике достаточно решить лишь одну из них, например задачу (2). Решение двойственной ей задачи (1) легко получить из последней симплекс-таблицы

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии