Ситуация равновесия. Седловая точка выигрыш-функции игрока А. Седловая точка матрицы выигрышей (платежной матрицы)

Ситуация (A_k, B_l) называется равновесной, если она удовлетворительна для каждого из игроков А и В то есть если выполняются неравенства и : (1) или равенства и : (2)

Таким образом, двойное нер-во (1) и двойное равенство (2) эквивалентны.

Выигрыш , соответствующий ситуации равновесия (A_k, B_l), называют седловой точкой матрицы игры. Таким образом, элемент , являющийся седловой точкой матрицы игры, является минимальным в своей i-й строке и максимальным в j-м столбце. Игра, матрица которой содержит хотя бы один такой элемент, называется игрой с седловой точкой.

Матрица игры может обладать несколькими седловыми точками или не обладать ими в целом.

Свойство равнозначности седловых точек матрицы игры

 

Седловые точки обладают важными свойствами. Одно из них – свойство равнозначности.

Теорема «свойство равнозначности седловых точек». Если и –седловые точки, то

Док-во: Т.к -седловая точка, то при имеем т.к. ,получим

Из неравенств выше, следует неравенство (1)

Применив аналогичные рассуждения сначала к седловой точке , а затем к седловой точке , получаем неравенство (2), неравенства (1) и (2) доказывают равенство

Свойство взаимозаменяемости седловых точек матрицы игры.

Теорема «св-во взаимозаменяемсотиседловых точек»

Если и , - седловые точки, то и и - также седловые точки

Док-во. т.к. и - седловые точки, то по теореме о равнозначности седловых точек справедливо равенство из которого получим

(1)

с другой стороны по опр. показателя эффективности и показ. неэфф-ти имеем (2):

Из равенства (1) и неравенства(2) следует,что

,

а это означает, что - седловая точка

Замечание. Теорема сформулирована для случая, когда взаимозаменяются вторые индексы седловых точек и , что приводит к седловым точкам .Если у седловых точек и взаимозаменить первые индексы,то это приведет к той же паре седловых точек

Если первые индексы седловых точек и равны: , то взаимозаменяемость вторых индексов не приводит к новым седловым точкам.То же относится к седловым точкам с равными вторыми индексами при взаимозаменяемости первых.

Стратегии, оптимальные во множестве чистых стратегий. Полное (общее) и частное решение игры в чистых стратегиях

 

Стратегии игроков A и B соответственно, создающие равновесную ситуацию или, другими словами, соответствующие седловой точке , называются оптимальными.

Если нижняя цена α = верхней цене β, то их общее значение γ=α=β называется ценой игры в чистых стратегиях. Совокупность множеств чистых оптимальных стратегий игрока A и B и цены игры γ называется полным решением игры в чистых стратегиях, а совокупность {A_k, B_l, γ} какой-нибудь пары чистых оптимальных стратегий и цена игры γ называется частным решением игры в чистых стратегиях. Цена игры в чистых стратегиях γ (если она существует) представляет собой значение выигрыша игрока А, кот. он не может увеличить, если игрок В придерживается своей оптимальной стратегии, и значение проигрыша игрока В, кот. последнее не может уменьшить при условии, что игрок А действует по своей оптимальной стратегии.

Критерий существования цены игры в чистых стратегиях

Теорема. Для того чтобы существовала цена игры в чистых стратегиях, т.е. для того чтобы нижняя цена игры равнялась верхней ценен игры , необходимо и достаточно существование у матрицы этой игры седловой точки.

Доказательство. Необходимость.

Пусть существует цена игры в чистых стратегиях, т.е. нижняя цена игры равняется верхней ценен игры (.

Пусть максиминная стратегия игрока А, а минимаксная стратегия игрока В. Тогда

Рассмотрим элемент стоящий на пересечении k-й строки и l-го столбца матрицы игры.

Из определений показателя эффективности стратегии A_k и показателя неэффективности стратегии В_l будем иметь:

откуда в силу получаем равенство

, которое обозначает, что элемент является седловой точкой.

Достаточность.

Пусть существует седловая точка . Тогда

Отсюда по определению нижней и верхней цен игры

т.е. . Но и потому , т.е. существует цена игры в чистых стратегиях.