Игра с седловой точкой

Предлагается к рассмотрению игра с платежной матрицей, заданной табл. 64.

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

Платежная матрица игры с седловой точкой

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

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

Чистые стратегии в играх с природой

Игра с природой с платежной матрицей, заданной матрицей (табл. 65), рассматривается ниже.

Таблица 65

Платежная матрица игры с природой (чистые стратегии)

Здесь Aj — ходы игрока А стратегии, Bj — состояния природы.

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

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

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

Стратегию предлагается считать доминирующей над стратегией А_к, если при любом состоянии среды выигрыш игрока А при выборе им стратегии Aj будет не меньше, чем при выборе стратегии А_к: > a_kj. Очевидно, что при любом состоянии среды стратегия A_t для игрока А лучше, чем А_к, поэтому вторую из них из рассмотрения можно исключить.

Еще одно напоминание: при рассмотрении задачи о выборе стратегии в предвыборной ситуации этот прием уже рассматривался. Стоит заметить, что в играх с природой можно по принципу доминирования исключать только стратегии игрока А. В данной задаче четвертая стратегия доминирует над пятой, а третья — над первой. Стало быть первая и пятая строки из платежной матрицы вычеркиваются (табл. 66).

Таблица 66

Преобразованная платежная матрица игры с природой (чистые стратегии)

Теперь все стратегии несравнимы между собой относительно доминирования. Чтобы сравнивать оставшиеся стратегии, нужны какие-то дополнительные соображения. До сих пор единственной рекомендацией для игрока А при выборе оптимального хода в антагонистических играх был принцип минимакса. Эта рекомендация основывалась на том, что его противник, игрок В, выбирает ход таким образом, чтобы минимизировать его выигрыш.

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

Эти рекомендации рассматриваются на конкретной ситуации.

Пример. Во время поездки в Китай туристка Зина рассказала соседке по гостинице Маше о том, что собирается купить на рынке несколько щенков-пекинесов — с тем, чтобы продать их в России. На родине каждого щенка можно продать по цене 3000 руб. В Китае они обойдутся гораздо дешевле: один щенок стоит 1000 руб., но если берешь больше, то за второго, третьего и т. д. платишь всего по 500 руб. Правда, больше трех щенков провозить через границу не разрешается.

Зина занимается продажей щенков регулярно. Она привозит щенков из Китая; затем она просто дает объявление в Интернете, и, как правило, за два-три дня щенков разбирают. Правда, сама она не работает, поэтому может ждать покупателей сколько угодно.

Зина предложила и Маше купить щенков на продажу. Маша сразу было отказалась: она работает и больше трех дней после поездки заботиться о щенках не может, а сами они настолько малы, что без ухода погибнут. Тогда Зина предложила Маше взять у нее телефон одного знакомого, к которому можно обратиться в случае, если щенков не купили. Непроданных щенков можно отдать этому человеку, приплатив за каждого по 500 руб. (таков его бизнес). Он, продав щенков, деньгами, конечно же, не поделится, но хотя бы душа будет спокойной: щенки не погибнут.

Чтобы ответить на вопрос, как поступить Маше, следует построить платежную матрицу игры. Решения: щенков не покупать; купить одного; купить двух; купить трех щенков (больше покупать нет смысла по условию), — обозначаются А_о, A_t, А₂ и А₃. Как В_о, В_х, В₂и В₃, соответственно, обозначаются следующие состояния природы: покупателей на щенков не найдется; найдется один покупатель; найдутся двое; найдутся трое или больше желающих (по условию, это один и тот же ход природы). Платежная матрица игры задается табл. 67.

Строка, соответствующая, например, ходу А₂, строится так. Маша покупает двух щенков за 1500 руб. Если никто их не покупает (В_о), то Маша относит их к знакомому Зины. При этом она теряет еще 1000 руб., и ее выигрыш в этом случае составляет —2500 руб. Если купят одного щенка (В^), то она получит за него 3000 руб., но за второго ей придется доплатить 500 руб.; ее выигрыш в этом случае

Платежная матрица задачи о покупке щенков

равняется 1000 руб. (—1,5 + 3 — 0,5 = 1). В том случае, если удастся продать обоих щенков (5₂), Маша получит за них 6000 руб., и с учетом их стоимости (1500 руб.) ее выигрыш составит 4500 руб. Если у кого-то появятся желающие купить еще щенков (2?₃), при ходе А₂ ситуация не изменится.

Остальные строки заполняются аналогичным образом. Все строки несравнимы между собой.

Теперь следует рассмотреть некоторые критерии, используемые в теории игр.

Критерий Лапласа основан на следующем соображении. Оценкой стратегии считается соответствующий ей средний выигрыш — математическое ожидание выигрыша. Для вычисления математического ожидания выигрыша при каждой стратегии игрока А желательно знать набор вероятностей возможных состояний природы. Если о состоянии природы ничего неизвестно, то все ее состояния считаются равновероятными.

Оптимальной является та стратегия, средний выигрыш которой максимален. Для конкретного примера вероятность состояний природы неизвестна, а значит, вероятность каждого состояния принимается - . Сред-4

ние выигрыши стратегий указаны в табл. 68. Оптимальным, по критерию Лапласа, является ход А₂.

Критерий Вальда основан на гипотезе крайней осторожности. Она формулируется так: при выборе стратегии рассчитывается на самый худший из возможных вариантов. Этот критерий рекомендует из всех возможных плохих вариантов выбирать наименее плохой (табл. 68). Выше этот принцип уже рассматривался; соответствующая ему стратегия называется максиминной. Для данного примера максиминной стратегией является А_о.

Таблица 68

Выбор оптимальной стратегии в задаче о покупке щенков

Критерий Сэвиджа основан на преобразовании платежной матрицы в матрицу рисков. Риском r_tj игрока А при использовании стратегии A_t называется разность между выигрышем, который он получил бы, если бы знал состояние и тем выигрышем, который получит, выбрав Д, не зная состояние природы. Это понятие можно пояснить на примере последней платежной матрицы.

Предполагается, что Маша выбрала стратегию А_} — купила одного щенка. Пусть природа находится в состоянии В-, (нашлись два покупателя). Если бы Маша заранее знала об этом, она купила бы двух щенков и получила «навар» в размере 4500 руб., а так ее выигрыш составил 2000 руб. Разница — 2500 руб. Вот эта неиспользованная возможность, о которой Маша, конечно, сожалеет, называется риском.

Строго говоря, риск в данной клетке — это разность между самым большим числом столбца и числом в данной клетке. Матрица рисков приведена в табл. 69.

Таблица 69

Матрица рисков в задаче о покупке щенков

Меньше всего максимальный риск при выборе хода Л₂. Он-то и считается оптимальным по критерию Сэвиджа.

На вопрос о том, как поступить Маше с покупкой щенков, однозначного ответа нет. По критерию Лапласа и Сэвиджа, следует купить двух щенков, а согласно критерию Вальда, их вообще покупать не следует.

Критерий Лапласа использован без знания о вероятностях состояния природы. В этом случае следует считать их равновероятными. Можно усложнить задачу, допустив, что Зина рассказала Маше подробнее о том, как быстро у нее расходятся щенки (по условию задачи, Машу интересует продажа щенков в течение первых трех дней). За последние 10 поездок Зине только один раз не удалось продать щенков за это время. Трижды у нее находился только один покупатель, четыре раза она продала за этот период двух щенков, и дважды ей удалось найти троих покупателей.

Теперь появились вероятности состояний природы, и можно уточнить оптимальный ход по критерию Лапласа (табл. 70). Средний выигрыш, или, что то же самое, математическое ожидание выигрыша для рассматриваемой задачи рассчитывается по формуле М(д) = Efl,/г; i,j = 0, 1, 2, 3.

Таблица 70

Критерий Лапласа в задаче о покупке щенков

Согласно уточненному критерию Лапласа, следует купить двух щенков.

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