5.6.1. Верхняя и нижняя цена игры

Рассмотрим платежную матрицу игры, раскрытую в, виде (рисунок). Здесьi-я строка соответствует,-й стратегии игрокаA; j-й стол­бец соответствует -й стратегии игрока В.

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

α= α_ij (14)

Величина а называется нижней ценой игры (а — это гарантирован­ный выигрыш игрока А). Очевидно а находится в одной из строк мат­рицы Е, пусть в, тогда стратегия А называется максиминной.

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

С другой стороны, противник — игрок В, заинтересован в том, чтобы обратить выигрыш игрока А в минимум, поэтому он должен пе­ресмотреть каждую свою стратегию с точки зрения максимального вы­игрыша игроком А при этой стратегии. Другими словами, при выборе некоторой стратегии он должен исходить из максимального проиг­рыша в этой стратегии, равногонайти такую стратегию, при кото­рой этот проигрыш будет наименьшим, то есть не более, чем

β=α_ij (15)

Величина называется верхней ценой игры, а соответствующая ему стратегия— минимаксной.

Принцип осторожности, диктующий игрокам выбор стратегий максиминной ими минимаксной соответственно, в теории игр именуют принципом «минимакса», а сами стратегии максиминные и минимакс­ные — общим термином «минимаксные стратегии».

Вполне определенной игрой или игрой с седловой точкой называется игра, у которой совпадают нижняя и верхняя цены игры, то есть вы­полняется равенство:

α= α_ij = = α_ij = β (16)

При этом V = а = называется ценой игры, а элементсоответст­вующий равенству, называется седловой точкой.

Простота решения игры с седловой точкой заключается в том, что оптимальные стратегии обоих игроков находятся сразу. Для игрока А это стратегия, для игрока В —. Причем, такое решение обладает свойством устойчивости в том смысле, что, если один из игроков при­меняет свою оптимальную стратегию, то любое отклонение другого игрока от оптимальной стратегии может оказаться не выгодным для него.

Действительно, пусть игрок А выбрал оптимальную стратегию со­ответствующуюα= α_ij =α_iojo , то есть игрок А обеспечивает себе выигрыш, равный одному из элементов строки, причем, эле­мент встолбце наименьший среди них. И если игрок В выберетj-ю стратегию отличную от , то он проиграет сумму, равную (), а игрок А соответственно выиграет ее. Аналогичные рассу­ждения показывают невыгодность стратегии, отличной от опти­мальной, для игрока А, когда В придерживается своей оптимальной стратегии.

Среди конечных игр, имеющих практическое значение, сравни­тельно редко встречаются игры с седловой точкой. Более типичным является случай, когда нижняя и верхняя цены игры не совпадают (), причем, нетрудно показать, что тогда.Действительно, пусть

α= α_ij =α_KS, это означает, что в k-ой строке элемент ,наименьший, то есть при нахождениив их число попадут значения не меньшие, так как даже в этой строке элементы в дру­гих столбцах больше или равны.Значит и

Откуда следует; что, но мы рассматриваем случай, зна­чит. Итак, в играх не имеющих седловой точки, нижняя цена игрывсегда меньше верхней.

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

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

Таким образом, мы пришли к выводу, что при неоднократном повто­рении игры обоим игрокам следует менять свои стратегии. Тогда воз­никает вопрос: а каким образом их менять, чтобы в среднем выигрыш одного и проигрыш другого был аналогично одноходовой игре, огра­ничиваясь снизу и сверху соответственно?

Для ответа на этот вопрос введем вероятность (относительную час­тоту), применения игроком Аi-и стратегии, и — вероятность при­мененияj-й стратегии игроком В. Совокупности этих вероятностей определяют векторы, где

и , где

Эти векторы или наборы вероятностей выбора чистых стратегий на­зываются смешанными стратегиями игроков.

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

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

(17)

Если второй игрок В выбрал некоторую смешанную стратегию У, то первому игроку, естественно, считать лучшей ту смешанную стратегию X, при которой достигается

Аналогично, при выборе первым игроком некоторой стратегии X второму игроку следует выбирать стратегию такую, что

Ясно, что зависит отY и зависит отX. Перед каждым игроком, таким образом, возникает задача выбора оптимальной стратегии, под которой для игрока А понимается смешанная стратегия , которая максимизирует математическое ожидание его выигрыша, для игрока В — стратегия, минимизирующая мате­матическое ожидание его проиг­рыша.

Основная теорема теории игр (доказана фон Нейманом в 1928 году) утверждает:

каждая матричная игра с нулевой суммой имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий, то есть су­ществуют стратегии и, оптимальные для обоих игроков, причем

Число называют ценой игры.

Примечание. Нулевая сумма означает, что выигрыш одного игрока равен проигрышу другого.

Из основной теоремы следует, что каждая конечная игра имеет цену и она лежит между нижней и верхней ценами игры

И если одни из игроков придерживается своей оптимальной страте­гии, то выигрыш (проигрыш) его остается неизменным независимо от тактики другого игрока, если, конечно последний не выходит за пре­делы своих «полезных» стратегий, иначе выигрыш (проигрыш) возрас­тает.

Это означает выполнение неравенств

, (18)

Примечание. Эти неравенства будут необходимы при сведении мат­ричной игры к задаче линейного программирования [13].