Главная > Математика > Введение в теорию игр
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

ГЛАВА VII. ИГРЫ С БЕСКОНЕЧНЫМ ЧИСЛОМ СТРАТЕГИЙ

До сих пор мы ограничивались рассмотрением конечных игр. Однако в некоторых практически важных ситуациях, которые удобно изучать с точки зрения теории игр, участники производят выборы из бесконечных множеств. Так, предположим, например, что предприниматель сталкивается с вопросом, какой величины делать кусок мыла, который он намеревается продать за десять центов. Ему хотелось бы сделать его достаточно большим, чтобы быть в состоянии успешно соревноваться с другими предпринимателями и, таким образом, продать много кусков, но, конечно, он не хочет делать его столь большим, чтобы терпеть убыток на каждом проданном куске. Поскольку он должен стремиться как-то угадывать действия других предпринимателей, интересы которых противоположны его интересам, получается нечто подобное игре. А поскольку кусок мыла может иметь бесконечное число весов (или такое большое конечное число, что его удобно рассматривать как бесконечное), мы сталкиваемся с игроподобной ситуацией, в которой игроки производят выборы из бесконечных множеств. Поэтому представляется полезным расширить наше понятие игры так, чтобы включить также бесконечные игры, то есть игры, в которых некоторые из выборов игроки совершают из бесконечных множеств. Однако мы их будем разбирать далеко не в такой общей форме, в какой мы рассматривали конечные игры. Во-первых, мы будем рассматривать лишь игры с одним ходом для каждого игрока и такие, что ни один из игроков не получает информации о выборе другого. Таким образом, мы будем иметь дело лишь с играми, в которых; как в прямоугольных играх, определенных в главе I, игрок выбирает элемент х из множества А, а игрок выбирает элемент у из множества В.

Кроме того, как и для прямоугольных игр, мы предположим, что имеется действительная функция М двух переменных, такая, что если игрок выбирает а игрок выбирает , то игрок платит игроку сумму . Итак, мы обобщаем понятие прямоугольных игр только в том отношении, что допускаем бесконечные множества А и В.

Наше внимание будет почти исключительно ограничено случаем, когда оба множества А и В суть замкнутые интервалы [0, 1]; мы будем называть такие игры непрерывными. Это название происходит оттого, что замкнутый интервал (точек или действительных чисел) иногда называют континуумом, а не оттого, что на функцию М налагаются какие-либо свойства непрерывности. Следует заметить, что это ограничение для множеств не так существенно, как может показаться с первого взгляда: если А и В — любые замкнутые интервалы, то простым переименованием элементов множеств А и В мы получим игру, в которой выборы совершаются из замкнутого интервала [0, 1]. Итак, непрерывной игрой (или игрой, которая может быть приведена к непрерывной игре) называется игра, подобная прямоугольной, но в которой игроки делают выборы из конечных замкнутых интервалов.

Пример 7.1. Рассмотрим, напрймер, игру, в которой выбирает число из интервала [0, 1], а игрок независимо от него выбирает число у из того же интервала и в которой платеж игроку равен

Эта игра по существу так проста, что мы можем сразу узнать оптимальные стратегии игроков: , желая обеспечить максимум функции , выберет чтобы обеспечить минимум функции , также выберет тогда платеж будет равен 1.

Пример 7.2. В качестве примера немного более сложной непрерывной игры рассмотрим следующую ситуацию: некий полковник, назовем его Блотто, хочет атаковать две равноценные позиции А и В, послав часть своего полка к А, а остальную часть — к В.

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

где определяется так:

Возвращаясь к исследованию задачи в общем виде, мы рассмотрим теперь игру, имеющую платежную функцию М. Пусть существуют

и

Тогда, рассуждая, как в главе I, мы видим, что может сделать выбор, который обеспечит ему получение по меньшей мере может позаботиться о том, чтобы получил не больше Если то на основании теоремы 1.5 мы видим, что М имеет седловую точку и,

В этом случае естественно назвать оптимальными способами игры для (и, следовательно, ) ценой игры. Так, в примере 7.1 мы имели:

Эта функция имеет седловую точку ; отсюда

Напротив, в примере 7.2, как можно показать, седловой точки нет.

Нам остались два более трудных случая: 1) случай, когда не существуют, и 2) случай, когда обе эти величины существуют, но не одинаковы. Второй случай будет рассмотрен в главе X после того, как в главах VIII и IX мы введем некоторые необходимые чисто математические понятия. Что касается первого случая, то мы ограничимся тем, что покажем возможность такой ситуации.

Часто, когда не существуют, мы знаем, как определить цену игры или оптимальные стратегии для обоих игроков.

Пример 7.3. Платежная функция непрерывной игры определена следующим образом:

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

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

Однако не следует думать, что такая ситуация имеет место во всех случаях, когда не существуют. Напротив, может даже оказаться, что игра имеет седловую точку, хотя не существуют. Рассмотрим, например, непрерывную игру, у которой платежная функция М определена следующим образом:

Легко убедиться, что для не существует. Поэтому не существует, и также не существует. С другой стороны, функция имеет седловую точку . Итак, имеется способ игры (а именно, взять который гарантирует ему, что он получит по меньшей мере есть способ игры (а именно, взять который гарантирует ему, что получит самое большее Поэтому мы можем вполне обоснованно назвать 0 ценой этой игры и сказать, что оптимальный способ игры для — взять , а оптимальный способ игры для — взять .

Замечание 7.4. Легко найти функцию М двух переменных такую, что

и

не существуют, а величины

и

обе существуют и равны. Если у непрерывной игры имеется подобная платежная функция, то, хотя игра и не имеет седловой точки, общее значение величин (3) и (4) иногда называют ценой игры v. В таком случае вообще не может выбрать стратегию , которая гарантировала бы ему, что для любой стратегии , выбранной игроком ,

но он может, тем не менее, для любого выбрать стратегию , такую, что для любого у, выбранного игроком ,

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

Пример 7.5. Платежная функция М непрерывной игры определена следующими условиями:

В этом случае мы легко убеждаемся, что величины (1) и (2) не существуют. С другой стороны, мы имеем:

Поэтому мы называем 1 ценой этой игры. Выбрав , игрок может быть уверен в том, что для любого выбранного игроком ,

Аналогично, выбрав игрок может быть уверен, что для любого выбранного игроком

Библиографические замечания

Первый общий обзор бесконечных игр можно найти в работе Вили [109].

<< Предыдущий параграф Следующий параграф >>
Оглавление