Линейное программирование (стр. 4 из 8)

аij (i= )

т.е. определяется минимальный выигрыш для игрока 1 при условии, что он примет своюi-ю чистую стратегию, затем из этих минимальных выигрышей отыскивается такая стратегия i = iо, при которой этот минимальный выигрыш будет максимальным, т.е. находится

аij= = (1).

Определение. Число

, определённое по формуле (1) называетсянижней чистой ценойигрыи показывает, какой минимальный выигрыш может гарантировать себе игрок 1, применяя свои чистые стратегии при всевозможных действиях игрока 2.

Игрок 2 при оптимальном своём поведении должен стремится по возможности за счёт своих стратегий максимально уменьшить выигрыш игрока 1. Поэтому для игрока 2 отыскивается

аij , т.е. определяется max выигрыш игрока 1, при условии, что игрок 2 применит своюj-ю чистую стратегию,

затем игрок 2 отыскивает такую своюj = j1стратегию, при которой игрок 1 получит min выигрыш, т.е. находит

aij= = (2).

Определение.Число

, определяемое по формуле (2), называетсячистой верхней ценойигрыи показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1.

Другими словами, применяя свои чистые стратегии игрок 1 может обеспечить себе выигрыш не меньше

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

Определение.Если в игре с матрицей А

= , то говорят, что эта игра имеетседловуюточкув чистых стратегиях ичистую ценуигры

u =

= .

Седловая точка– это пара чистых стратегий (iо,jо) соответственно игроков 1 и 2, при которых достигается равенство

= . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:

гдеi, j– любые чистые стратегии соответственно игроков 1 и 2;(iо,jо)– стратегии, образующие седловую точку.

Таким образом, исходя из (3), седловой элемент

является минимальным в iо-й строке и максимальным в jо-м столбце в матрице А. Отыскание седловой точки матрицы А происходит следующим образом: в матрице А последовательно в каждойстрокенаходят минимальный элемент и проверяют, является ли этот элемент максимальным в своёмстолбце. Если да, то он и есть седловой элемент, а пара стратегий, ему соответствующая, образует седловую точку. Пара чистых стратегий(iо,jо)игроков 1 и 2, образующая седловую точку и седловой элемент , называется решением игры. При этом iоиjо называютсяоптимальными чистыми стратегиями соответственно игроков 1 и 2.

2.3 Решение матричных игр в смешанных стратегиях путём сведения к задаче линейного программирования

Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивается исследование игры. Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 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

Первый игрок имеет целью за счёт изменения своих смешанных стратегий х максимально увеличить свой средний выигрышЕ(А, х, y), а второй – за счёт своих смешанных стратегий стремится сделатьЕ(А, х, y) минимальным, т.е. для решения игры необходимо найти такие х и y, при которых достигается верхняя цена игры

Е(А, х, y).

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть

Е(А, х, y).

Подобно играм, имеющим седловые точки в чистых стратегиях, вводится следующее определение: оптимальными смешанными стратегиями игроков 1 и 2 называются такие наборыхо, уо соответственно, которые удовлетворяют равенству

Е(А, х, y) = Е(А, х, y) =Е(А, хо, уо).

ВеличинаЕ(А, хо ,уо) называется при этомценой игрыи обозначается через u.

Имеется и другое определение оптимальных смешанных стратегий: хо, уоназываются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:

Е(А, х, уо)<= Е(А, хо, уо)<= Е(А, хо, у)

Оптимальные смешанные стратегии и цена игры называютсярешением матричной игры.

Основная теорема матричных игр имеет вид :

Теорема(о минимаксе).Для матричной игры с любой матрицейАвеличины

Е(А, х, y) и Е(А, х, y) существуют и равны между собой.

Игра m × n в общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при больших m и n, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования.

Пусть игра m × n задана платежной матрицей p = (a_ij ), i = 1, 2, ..., m; j = 1, 2, ..., n. Игрок А обладает стратегиями A₁ , A₂ , ..., A_m , игрок В — стратегиями B₁ , B₂ , ..., B_m . Необходимо определить оптимальные стратегии S*_A = ( p*₁ , p*₂ , ..., p*_m ) и S*_B = ( q*₁ , q*₂ , ..., q*_n ), где p*_i, q*_j — вероятности применения соответствующих чистых стратегий A_i , B_j, p*₁ + p*₂ +...+ p*_m =1, q*₁ + q*₂ +...+ q*_n = 1.

Оптимальная стратегия S*_A удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока B. Без ограничения общности полагаем v > 0: этого можно добиться, сделав все элементы a_ij ≥ 0. Если игрок А применяет смешанную стратегию S*_A = ( p*₁ , p*₂ , ..., p*_m ) против любой чистой стратегии B_j игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша a_j = a_1j p₁ + a_2j p₂ +...+ a_{m j} p_m , о = 1, 2, ..., n (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий A₁ , A₂ , ..., A_m и результаты складываются).