7.6.3Решение игр 2х2, 2хп, тх2

Решением игры называется нахождение оптимальных стратегий игроков и цены игры. Покажем на примере, как решить игру 2х2.

матрица с седловой точкой а^ = 1:

Пример 5 Решить игру

2 -1

-I — левый верхний угол матрицы из

п 1 Сначала проверим, нет ли седловой точки; ведь если седловая точка есть, то решение игры ясно. Убеждаемся, что седловой точки нет. Обозначим искомую оптимальную стратегию Первого (х, 1-х) — это вектор-столбец, но для удобства записываем его в виде строки, искомую оптимальную стратегию Второго обозначим (у, 1 - у). Выигрыш Первого есть случайная величина с таким рядом распределения

2	-1	-4	7
^	х(1-у}	(1-^	(\-х)(1-у)

^щх' ^у\ \ху\х(1-у)\(1^х)у\(\-х)(1-у) •

Находим средний выигрыш за партию Первого — математическое ожидание случайной величины Щх,у).

М(х, у) = 2ху — х(1 -у)-4(1 -х)у+ 7(1 -х)(\ -у) = 2ху-х +ху-4у + 4ху+ + 7 - 7х -7} + 7ху = 13ху - 8л - \\у + 7 = \3х(у -8/13) - 110' -8/13) + 3/13 = =13(>'-8/13)(л-11/13)+3/13.

Докажем, что оптимальные стратегии игроков есть. Первого Р' = (11/13, 2/13), Второго — б» = (8/13, 5/13), цена игры v = 3/13 Для этого надо просто убедиться в выполнении необходимых требований, предъявляемых к оптимальным стратегиям, те в выполнении неравенств М(х, 8/13) ^ М(11/13, 8/13) ^ < М( 11/13, у) для любых вероятностей х и у. Но в этом нетрудно убедиться, анализируя формулу для среднего выигрыша Первого: М(х, у) = 13(у - 8/13)(л -- 11/13) + 3/13 Действительно, имеем 3/13 = М(х, 8/13) = М(11/13, 8/13) = 3/13 = =А/(11/13,у)=3/13

Формально условия оптимальности стратегий выполняются, значит, нужно признать стратегии Р' = (11/13, 2/13) и б» = (8/13, 5/13) оптимальными для игроков, а 3/13 нужно признать ценой игры v

Решение игр 2 х и покажем на примере.

Пример 6. Решить игру

(-47 4^{^} 182-2,

— две нижние строки матрицы

из п 1. Сначала проверим, нет ли седловой точки; ведь если седловая точка есть, то решение игры ясно Убеждаемся, что седловой точки нет Обозначим искомую оптимальную стратегию Первого (х, 1 - х) — это вектор-столбец, но для удобства записываем его в виде строки

Обозначим у,(л) — средний выигрыш Первого в расчете на партию, когда Первый использует стратегию (л, 1 - х), а Второй — у-ю чистую стратегию. Имеем у'|(л) = -4х + 8(1 - х), \'^(х) = 7х + 2(1 - х), у,(л) = Зл- -2(1 - л) Возьмем на плоскости систему координат (рис 1), по горизонтальной оси вправо отложим л, по вертикальной оси значения функций ^(л). Масштаб по осям сделаем разный, ведь графики нужны только над отрезком [О, 1]

Функции у,(л), I = 1, 2, 3 линейные, значит, их графики — прямые линии I, II, III соответственно Находим верхнюю огибающую семейства этих трех прямых над отрезком [О, 1] — это ломаная АВС. Находим самую низшую точку этой ломаной, это точка 5. Она и дает решение игры Координаты этой точ-

82

ки получаются решением уравнения у,(л) = у^(х), откуда л' = 6/17, v = у|(л') = =^(л')= 64/17.

Таким образом, оптимальная у стратегия Первого есть Р'= (6/17, 11/17), а цена игры v = 64/17.

Заметим теперь, что при этой стратегии Первого Второй игрок не выбирает свой 3-й столбец. Обозначим вероятность выбора Вторым 1 -го столбца через у, а 2-го столбца через (1 - у). Теперь

учтем, что, например, р] = х > О

и воспользуемся предложением 1 (см конец п. 3). Получаем М(\, у) =

-}/)=64/17, от-

Ри с 1

= v, т.е. -4у + 7(1 куда/= 5/17

Окончательный ответ, оптимальная стратегия Первого Р'

^6/ } /17 \ ;11/ ^ /\У

, опти

мальная стратегия Второго б' = (5/17, 12/17, 0), цена игры v = 64/17.

В начале п. 2 уже указывалось, что простота матричных игр кажущаяся. На примере только что решенной игры покажем, что игрокам нужно быть очень внимательными. Заметим сначала, что если Первый использует оптимальную стратегию, то он безусловно будет выигрывать 64/17 в среднем за партию. Представим, однако, что Первый почему-либо перестал придерживаться оптимальной стратегии и стал чаще выбирать 2-ю строку. Анализируя статистику ходов, Второй это уловил. Он немедленно начнет чаще выбирать 1-й столбец. Из рис. 1 видно, что выигрьил Первого уменьшится. Обнаружив это. Первый постарается вернуться к оптимальной стратегии. Примерно также Первый должен следить, придерживается ли Второй своей оптимальной стратегии. Аналогично решаются и анализируются игры т х 2. Отметим в заключение, что решение матричных игр с большим числом строк и столбцов находится методами линейного программирования.

Для сложных организационных систем получить критерий общей эффективности в виде скалярной функции не удается, и приходится иметь дело с векторным, многокомпонентным критерием, составляющие которого самостоятельные, независимые друг от друга критерии. Такие системы называются многокритериальными.

Достаточно эффективным способом, используемым в случаях векторного критерия, является выбор управляющих воздействий (решений) оптимальных по Парето. Множество оптимальных по Парето решений с векторным критерием составляют такие решения, ни одно из которых не доминируется (т.е. не улучшается в заданном смысле) никаким другим решением и этого множества. Это означает, что множество управляющих воздействий, оптимальных по Парето, включает в себя решения, фактически несравнимые по скалярному критерию, т.е. такие, о которых нельзя однозначно сказать, какое из них лучше. Это обусловлено тем, что нельзя сказать, какой из независимых критериев, являющихся компонентами векторного критерия, важнее с точки зрения обобщаемой оценки. Каждое из множества управляющих воздействий лучше любого другого по крайней мере по одному из независимых критериев, но в тоже время хуже него по другим. Ясно, что если множество по Парето содержит лишь одно решение, то оно является наилучшим по всем составляющим векторного критерия, т.е. по общей оценке.

Смысл оптимальности по Парето, таким образом, заключается в том, что выделяются только несколько решений, подлежащих дальнейшему рассмотрению, а все остальные исключаются.