Вплоне определенные игры (игры с седловой точкой)

Наиболее простым случаем в теории игр является случай, полученный в примере 1, когда нижняя цена игры совпадает с верхней ценой игры. Говорят, что в этом случае игра называется игрой с седловой точкой. А значение альфа=бетта называют ценой игры.

Элемент аij, находящийся на пересечении строки соответствующей альфа и столбца соответствующего бетта называют седловой точкой. Значение элемента аi называют ценой игры. Простота решения таких игр обусловлена тем, что оптимальные стратегии для игрока А и игрока В находятся на одном шаге. Оптимальная стратегия игрока А – стратегия соответствующая альфа. А стратегия В стратегия соответствующая бетта.

Говорят, что такое решение обладает устойчивостью. Если игрок А примет свою оптимальную стратегию, то любое отклонение игрока В от его оптимальной стратегии всегда приведет к лучшему или большему выигрышу игрока А и большему проигрышу игрока В. (пример1)

Игры не содержащие седловой точки. Смешанные стратегии

На практике игры в чистых стратегиях (игры с седловой точкой) встречаются редко, чаще всего решаюся игры, у которых нижняя цена игры альфа неравна верхней цене игры бетта, причем в большинстве случаев альфа<бетта.

В таком случае говорят, что игра не имеет седловой точки и не имеет решения в чистых стратегиях и необходимо искать решение игры в смешанных стратегиях.

Практика показывает, что если игра одноходовая, т.е. партнеры играют всего 1 раз выбирая по одной чистой стратегии, то в расчете на разумно играющего противника они должны придерживаться принципа minmax это гарантирует игроку А выигрыш V(цена игры)>=альфа, а игроку В проигрыш V<=бетта. При получении решения в смешанных стратегиях цена игры альфа<=V<=бетта.

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

Возникает вопрос каким образом менять стратегии игрокам А и В с тем, чтобы обеспечить цену игры V, находящуюся в пределах альфа и бетта.

Для решения игр в смешанных стратегия вводят обозначение P(xi) – вероятность выбора игроком А стратегий ai. И вероятность P(yj) – вероятность выбора игроком В стратегий bj.

Тогда в целом P(x)=<P(x1),P(x2),…,P(xn)>

P(y)=<P(y1),P(y2),…,P(yn)>

Где в сумме вероятности события каждого вектора должны быть равны 1.

Такие векторы или наборы вероятностей в теории игр называются смешанными стратегиями игроков, а каждый отдельный элемент вектора P(xi) или P(yj) называются чистыми стратегиями игрока.

Для получения ограничений на средний выигрыш или средний проигрыш рассчитывают математическое ожидание выигрыша первого игрока.

Рис1

Если игрок В выбрал некоторую стратегию, то А лучше считать ту смешанную стратегию, при котором достигается максимум этого мат.ожидания.

Аналогично при выборе игроком А некоторой смешанной стратегии, игроку В следует выбирать ту стратегию, которая обеспечила бы минимум этого мат. Ожидания.Таким образом мат.ожидание игрока А зависит и от выбранной смешанной стратегии игрока В и зависит от мат.ожидания для игрока В, тогда игрок А должен выбирать такую оптимальную стратегию Х*, которое максимизирует его мат.ожидание, а игрок В должен выбирать такую оптимальную стратегию У*, которая минимизирует его мат.ожидание.

Для решения игр в смешанных стратегиях существует и доказана фон Нейманом основная теорема теории игр. Эта теорема гласит, что каждая матричная игра с нулевой суммой имете покрайней мере одно решение. Возможно в области смешанных стратегий. То есть существуют такие типы смешанных решений, который оптимальны для обоих игроков, причем maxmin мат ожидания одного игрока равен мат ожидания другого игрока и такое ожидание называет ценой игры без седловой точки. При этом под нулевой суммой понимают ситуацию, когда выигрыш одного игрока равен проигрышу другого игрока. Из этой основной теоремы следует вывод, что любая конечная, матричная игра имеет решение возможно не в чистых, а в смешанных стратегиях и цена этой игры В лежит между нижней и верхней ценой игры, таким образом если один из игроков придерживается своей оптимальной стратегии, то выигрыш и соответственно проигрыш остается неизменным независимо от тактики другого игрока, если второй игрок не выходит за рамки своей «полезной стратегии» в результате такого выхода за рамки выигрыш или проигрыш будет увеличиваться, это означает выполнение неравенств рис2

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