КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Решение матричной игры в смешанных стратегиях.
Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивает исследование игры. Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Решение игры достигается путём применения чистых стратегий случайно, с определённой вероятностью.
Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий.
Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия X – это набор чисел X = (x1, ..., xm) удовлетворяющих соотношениям
xi 0 (i = 1,m), 
= 1.
Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y – это набор чисел
Y = (y1, ..., yn), yj 0, (j = 1,n), 
= 1.
Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии.
Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей
E (A, X, Y) = 
= X A YT
Функцию E (A, X, Y) называют также платежной функцией игры в смешанных стратегиях.
Например,
для матрицы 
в смешанных стратегиях 
средний выигрыш равен
Первый игрок имеет целью за счёт изменения своих смешанных стратегий X максимально увеличить свой средний выигрыш Е (А, X, Y), а второй – за счёт своих смешанных стратегий стремится сделать Е (А, X, Y) минимальным, т.е. для решения игры необходимо найти такие X и Y, при которых достигается верхняя цена игры
Е (А, X, Y).
Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть
Е (А, X, Y).
Оптимальными смешанными стратегиями игроков 1 и 2 называются такие стратегии Xо, Yо соответственно, которые удовлетворяют равенству
Е (А, X, Y) = 
Е (А, X, Y) = Е (А, Xо, Yо).
Величина Е (А, Xо ,Yо) называется при этом ценой игры и обозначается через .
Имеется и другое определение оптимальных смешанных стратегий: Xо, Yо называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:
Е (А, X, Yо) Е (А, Xо, Yо) Е (А, Xо, Y)
Оптимальные смешанные стратегии и цена игры называются оптимальнымрешением матричной игрыв смешанных стратегиях.
Основной теоремой матричных игр является
теорема Неймана( теорема о минимаксе ) :
для матричной игры с любой матрицей А величины
Е (А, X, Y) и 
Е (А, X, Y)
существуют и равны между собой: 
.
Другими словами, любая конечная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.
Имеют место следующие утверждения:
Утверждение 1.Тройка (Xо, Yо, ) является решением игры G = (Х,Y,А) тогда и только
тогда, когда (Xо, Yо, к +а) является решением игры G(Х,Y, кА+а), где а – любое вещественное число, к > 0.
Утверждение 2. Для того, чтобы Xо = ( 
) была оптимальной смешанной
стратегией матричной игры с матрицей А и ценой игры , необходимо и достаточно выполнение следующих неравенств
(j =1,2…,n) 
Аналогично для игрока 2 : чтобы Yо = ( 
, ..., 
, ..., 
) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:
(i =1,2…m) 
Из последнего свойства вытекает: чтобы установить, является ли предполагаемые (X, Y) и решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (2.1) и (2.2).
Найдя неотрицательные решения этих неравенств совместно со следующими уравнениями
, 
получим оптимальное решение матричной игры.
Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (2.1) (2.2) и линейных уравнений (2.3). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например для матрицы 3 
3 имеем систему из 6 неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства
= 
.
Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок 1 – чистую максиминная, а игрок 2 – чистую минимаксная). В противном случае хотя бы у одного игрока оптимальные стратегии будут смешанные.
Дата добавления: 2015-07-26; просмотров: 159; Мы поможем в написании вашей работы!; Нарушение авторских прав |