Файл: В. А.МАТВЕЕВ.pdf

Пример15.2. Решитьграфическимметодомматричнуюигру с матрицей

2 4 11

A = .

7 4 2

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

Обозначим

f1 (α) = 7 −5α, f2 (α) = 4,

f3 (α) = 2 +9α.

Найдём

max (min(7 −5α, 4, 2 +9α )).

αi

Для нахождения максимина приведём геометрическую иллюстрацию на рис.15.2.

Вначале для каждого α [0,1] найдём

min(7 −5α, 4, 2 +9α ).

i

На рис. 15.2 такие минимумы для каждого α [0,1] образуют

ломаную – нижнюю огибающую АВСD. Затем на огибающей находим наибольшее значение, равное 4. Оно достигается в бесконечном множестве точек. Это все точки отрезка ВС. Они

расположены на участке графика функции f2=4, когда α [29 , 35].

130

Рис. 15.2.

ЛеваяграницаэтогомножестваестьточкаВ. Еёкоординатынаходятся изуравненияf2 = f3 или4 = 2+9 α. Праваясоответственноизуравнения

1= f2 или 7-5 α = 4.

Вситуации равновесия входят стратегии первого игрока x

=( α , 1- α ), α [2 9 , 35]. Для каждой такой стратегии

определяется соответствующая стратегия второго игрока. Например, для стратегии x =(2/9, 7/9) найдём минимаксную стратегию второго игрока. Его стратегию обозначим

y = (0, β, 1− β), 0 ≤ β ≤1. Первая компонента этого вектора y

равна 0, т.к. максиминная стратегия определяется вторым и третьим столбцом матрицы А (т.е. функциями f2 и f3). В этом случае в максиминной стратегии первая компонента равна 0. Для

нахождения β [0 1] в матрице А оставим только второй и третий

столбцы. Вычислим

131

Обозначим

min (max(11−7β, 2 + 2β)).

β i

Для нахождения минимакса приведём геометрическую иллюстрацию на рис.15.3.

y

E

F f2

f1

M

Рис. 15.3.

Вначале для каждого β [0,1] определим

max(11−7β, 2 + 2β).

i

На рис.15.3 такие минимумы для каждого β [0,1] образуют

ломаную – верхнюю огибающую EF. Затем, на огибающей, находим наименьшее значение, которое достигается в точке F.

Эта точка появляется при β = 1 и F(1,4). В смешанном расширении данной игры

132

min (max(11−7β, 2 + 2β)) = 4.

β i

Минимаксная стратегия второго игрока yB = (0, β,, 1- β) = (0, 1, 0).

В примере выполнены условия утверждения 4.2. для стратегий x = (2/9, 7/9) и y = (0, 1, 0). В самом деле, минимакс и максимин существуют и выполнено равенство

νB = νН = 4.

Значит цена игры ν * = 4 и седловая точка (x, y) = ((2/9, 7/9) (0, 1, 0)). Аналогичные рассуждения верны для любой другой стратегии x

=( α, 1- α), α [29 , 35].

Витоговой проверке покажем выполнение равенства

x * A( y*)T = v *. В данном примере получаем

Это верное равенство.

Ответ: X *×Y* = ((α,1 −α),(0,1,0)),α [29 , 35),ν* = 4.

Задачидлясамостоятельногорешения

Задача 15.1. Решить графическим методом матричную игру с матрицей выигрыша первого игрока

133

Задача1.2. Длябиматричнойигрынайтитезначенияпараметра p R, при которых биматричная игра имеет бесконечное множество равновесных решений. Указать эти решения

134

§16. Алгоритм Лемке -Хаусона

Нахождение равновесия по Нэшу в произвольной, даже конечной, игре вызывает определённые трудности. Случай матричной игры разработан наиболее полно. Такая игра сводится

кпаре двойственных задач линейного программирования. Для них существует отработанный численный метод: симплекс – метод. Другие способы решения матричной игры по отношению

кнему носят вспомогательный характер (§2, 4, 6). В данной работе задача линейного программирования и симплекс – метод применяется для решения матричной игры в §11.

Вболее общем случае биматричной игры ситуация равновесия по Нэшу вычисляется с использованием различных линейных методов, имеющих своей основой задачу линейного программирования. Исторически один из первых подходов разработан в начале 60-ых годов. Это известный алгоритм Лемке

– Хаусона нахождения решения в биматричной игре. В ситуации равновесия игры двух лиц смешанная стратегия одного игрока уравновешивает выигрыш другого игрока при использовании им чистых стратегий.

Пусть матрицы А, В имеют размеры m × n. Будем рассматривать невырожденные биматричные игры (А, В), где А, В - матрицы выигрышей первого и второго игроков. Биматричная игра (А, В), называется невырожденной, если для каждой исходной стратегии первого (второго) игрока число чистых стратегий, являющихся наилучшим ответом второго (первого) игрока, не превосходит числа стратегий из спектра исходной стратегии, первого (второго) игрока.

Рассмотрим применение алгоритма Лемке – Хаусона для нахождения равновесий в невырожденной биматричной игре

размера 2×3.

Пример 16.1. Решить биматричную игру, заданной матрицами выигрыша первого игрока и второго игрока, используя алгоритм Лемке - Хаусона

135