Таблица 4. Решение задачи
Решение.
Решение задачи приведено в таблице 4
Ai Вj | стратегии игрока В | αi | нижняя цена игры, α | |||
В1 | В2 | В3 | ||||
стратегии игрока А | A1 | 0,5 | 0,6 | 0,8 | 0,5 | α=0,7 |
A2 | 0,9 | 0,7 | 0,8 | 0,7 | ||
A3 | 0,7 | 0,6 | 0,6 | 0,6 | ||
βj | 0,9 | 0,7 | 0,8 | чистая цена игры ν=α=β=0,7 | ||
верхняя цена игры, β | β=0,7 |
Анализируя строки матрицы (стратегии игрока А), заполняем столбец α i: α 1 =0,5, α 2 =0,7, α 3 =0,6 - минимальные числа в строках i= 1, 2, 3. Заполняем строку βj – максимальные числа в столбцах j=1.2,3 соответственно: β 1 =0,9, β 2 =0,7, β 3 =0,8.
Значения нижней цены игры α - наибольшее число в столбцеαi, и верхней цены игры β - наименьшее число в строке β j равны: α=β=0,7. Равные значения α и β достигаются на одной и той же паре стратегий (A 2, B 2).
Следовательно, игра имеет седловую точку (A 2 , B 2) и цена игры ν =0,7.
Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. Так, в примере1 α=-1 ≠ β=1, седловая точка отсутствует. В этом случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.
|
|
Смешанной стратегией SA игрока А называется применение чистых стратегий A1,A2,...,Am с вероятностями p1,p2,...,pi,...,pm. Причем сумма вероятностей равна 1:
Смешанные стратегии игрока А записываются в виде матрицы:
Аналогично смешанные стратегии игрока В обозначаются:
где сумма вероятностей появления стратегий также равна 1:
Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии.
Оптимальное решение (или решение) игры (на основании принципа минимакса) - это пара оптимальных стратегий S*A, S*B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей.
Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству: α ≤ v ≤ β, где α и β — нижняя и верхняя цены игры.
Справедлива следующая основная теорема теории игр - теорема Неймана:
каждая конечная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.
Пусть S*A = (p*1,p*2,...,p*i,...,p*m) и S*B = (q*1,q*2,...,q*j,...,q*n) - пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.
Справедлива теорема об активных стратегиях:
если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.
|
|
Эта теорема имеет большое практическое значение, так как она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки.
Рассмотрим игру размера 2×2, которая является простейшим случаем конечной игры.
Если такая игра имеет седловую точку, то оптимальное решение - это пара чистых стратегий, соответствующих этой точке.
Для игры, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий S*A = (p*1, p*2) и S*B = (q*1, q*2).
Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии S*A, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В.
Для игры 2×2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А (проигрыш игрока В) - случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А (оптимальная стратегия) будет равен v и для 1-й – B1, и для 2-й - B2 стратегии противника.
Пусть игра задана платежной матрицей /
Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию , а игрок В - чистую стратегию B1 (это соответствует 1-му столбцу платежной матрицы H), равен цене игры v:
h11 p*1+ h21 p*2= v.
Тот же средний выигрыш получает игрок А, если игрок B применяет стратегию B2, т.е.
h12 p*1+ h22 p*2= v.
Учитывая, что p*1+p*2=1, получаем систему уравнений для определения оптимальной стратегии S'A и цены игры v:
Решая эту систему, получим оптимальную стратегию игрока А:
и цену игры: .
Применяя теорему об активных стратегиях при отыскании S*В- оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А1 или А2) средний проигрыш игрока В равен цене игры v, т.е.
Тогда оптимальная стратегия игрока В определяется формулами: