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

Рассмотрим платежную матрицу игры , раскрытую в, виде (рисунок). Здесь 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].

5.6.2. Сведение матричной игры к задаче линейного программирова­ния

При наличии неопределенности, причиной которой является присут­ствие нескольких принципов оптимальности , удобно воспользоваться двойственной задачей линейного программирования.

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

Итак, набору принципов , ,..., соответствует набор критериев оптимальности , ,…, .

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

Рассмотрим матрицу игры (2.2.1). Соотношениям отыскания нижней и верхней цены игры можно поставить в соответствие эквивалент­ные им задачи:

(19)

(20)

где (21)

есть математическое ожидание выигрыша первого игрока. Тогда для любой чистой стратегии У(j) игрока П.

можно записать

(22)

а для любой чистой стратегии Х(i) игрока Р

можно записать

(23)

Следовательно, задачи (2.6.7) — (2.6.11) допускают следующую за­пись в форме задач линейного программирования:

(24)

Нетрудно видеть, что задачи (5.21) и (5.20) взаимнодвойственные, а поэтому их оптимальные значения должны совпадать, т.е. , где V— цена игры (требуемое значение эффективно­сти).

Для задачи (2.6.12) положим:

и (25)

а для задачи (2.6.13) положим:

и (26)

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

минимизировать линейную функцию

(27)

при условиях

(28)

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

максимизировать линейную функцию

(29)

при условиях

(30)