Теория игр. Оуэн (1971) (1186151), страница 19
Текст из файла (страница 19)
Вот они: т'!г.б, Игры е выоором момента времени 99 Эта система вместе с обычными ограничениями даст нам решение игры, если такое решение существует. 11!5.1. П р и м е р. Рассмотрим следующую дуэль. Два дуэлянта («игрока») в момент Г = 0 начинают идти навстречу друг другу. Они встретятся (если ничто не помешает) в момент Г = 1. Каждый имеет пистолет только с одной пулей и может выстрелить в любой момент, когда пожелает. Если ему удалось поразить противника, а сам он невредим, то дуэль немедленно прекращается, и тот, кто выстрелил успешно, является победителем. Если оба дуэлянта промахнулись, то дуэль оканчивается вничью. Если оба стреляли одновременно и каждый поразил противника, то дуэль также считается окончившейся вничью.
Сделаем два предположения. Первое — меткость выстрела при сближении игроков возрастает таким образом, что если какой-либо игрок выстрелил в момент 1, то вероятность поражения противника равна б Второе — дуэль является бесшумной, т. е. игрок не знает, что его противник выстрелил (если, конечно, тот промахнулся). Найдем ядро этой игры. Если игрок 1 выбирает момент х, а игрок П вЂ” момент д > х, то игрок 1 с вероятностью х попадает в противника (в этом случае его выигрыш равен +1). Если он промахнулся (с вероятностью 1 — х), то он будет поражен с вероятностью д (получит выигрыш — 1). Таким образом, мы имеем К(х, д) х — д+хд. (4.5.19) Очевидно, эта игра симметрична, поэтому С(х, д)=х — д — хд (4.5.20) ~в (х) = О.
Мы имеем также (4.5.21) (4.5.22) Кр(х, д)- — 1+х, г,е(х, д) — 1 — х 1 (д, д) — К(д, д) = — 2д'. (4.5.23) ношения примут вид Е(Е, д)=0 для дев(а, Ь), Е(Е', д) ~ О для всех д, (Е(д, д)-К(д д))Е'(д)= У в = ~ К„(х, д)Р'(х)г(х+) Лв(х, д)Е'(х)дх для д~(а, Ь). (4.5.18) Гл. !К Бееконенные игры 100 Предположим теперь, что оптимальная стратегия является непрерывной функцией распределения Е с положительной производной в интервале (а, Ь). Тогда у ь — 2у'Е' (у) = ) ( — 1+ х) Е' (х) г!х+ ) ( — 1 — х) Е'(х) г!х. (4.5.24) Это интегральное уравнение может быть преобразовано в дифференциальное дифференцированием обеих частей, что даст — 4уЕ' — 2узЕа = (д — 1) Е'+ (у+ 1) Е', или после упрощений урн = -5Е', (4.5.25) Решение последнего уравнения таково: ре (р) ьу-з (4.5.26) Теперь нужно найти а, Ь и Ь.
Предположим, что Ь < 1. Мы знаем, что для всех у ен(а, Ь) Е(Е, д) =О. Но функция Е(Ргу) непрерывна по у, откуда следует, что Е(Е, Ь) О. Следовательно, ) (х- Ь + Ьх) г!г (х) = О. а Но если Ь < 1, то ~ (х — ! + х) ИЕ (х) < О, а и поэтому Е(Е, 1) < О, что противоречит условию (4.5.17). Таким образом, Ь = 1. (4.5,27) Так как Ь = 1, то Е(Г, 1) = О. Ввиду этого ь 1 2"-,1,!х = О, а откуда следует Заз — 4а + 1 = О.
!У. 6. Боксе вессокие размерности 1О! 1 1 /тх 3=1, ь и поэтому (4.5.29) Это дает нам оптимальную стратегию каждого нз двух игроков. Она является непрерывной функцией распределения, определенной следующим образом: ~ О, если х<'/тн г'(х) = 1 1/(4х'), если х > '/в. (4.5.30) Можно непосредственно проверить, что это — решение. 1У.5.2. Пример.
Рассмотрим снова дуэль, описанную в предыдущем примере, за одним исключением — дуэль теперь будет шумной, т. е. игрок знает, что его противник выстрелил и промахнулся. В таком случае он, естественно, не стреляет до момента 1 = 1, когда он попадает наверняка. Поэтому, если игрок 1 выбрал х, а игрок П выбрал у > х, то игрок 1 с вероятностью х побеждает и с вероятностью 1 — х проигрывает. Следовательно, К(х, у)=2х — 1, (4.5.31) с.(х, у) = 1 — 2у, (4.5.32) ср(х) = О. (4.5.33) Мы могли бы пытаться применить к этому примеру рассуждения того же типа, что и к предыдущему.
Однако легко видеть, что игра имеет седловую точку в чистых стратегиях. В самом деле, мы имеем А(с/е, У)=/.(х, У)=1 — 2У>0, если У<'/ю А(с/е, у) ср(т/е) = О, если у = '/е, А(т/е, у)=К(т/„у)=0, если у > '/е, и поэтому '/т — оптимальная чистая стратегия. 1Ъ".6. КОЛЕЕ ВЫСОКИЕ РАЗМЕРНОСТИ В последних четырех параграфах рассматривались игры на квадрате, т. е. игры, в которых чистые стратегии каждого игрока образовывали одномерный континуум. Разумеется, любое множе- Зто уравнение имеет два решения: а = 1 и а = '/з. Ясно, что значение а = 1 невозможно, следовательно, о = '/в.
(4.5.28) Так как г — стратегия, то 102 Гл. г"г'. Бесконечные игры ство, равномощное континууму, можно взаимно однозначно отобразить на единичный интервал. Таким образом, любая игра, в которой каждый игрок имеет равномощное континууму множество чистых стратегий, может быть представлена как игра на единичном квадрате. Однако трудность состоит в том, что при этом многие свойства функции выигрыша могут быть потеряны. Мы предпочитаем поэтому сохранить самую естественную структуру множеств стратегий. Как и прежде, мы будем иметь функцию А(х, у) — ядро игры, которое определено на прямом произведении Х Х У двух множеств чистых стратегий. Смешанной стратегией игрока 1 будет такая мера р, заданная на Х, что р(х)=1, (4.6.1) и аналогично смешанной стратегией игрока 11 будет такая мера т„ что т(У) =1. (4.6.2) Ожидаемый выигрыш определится следующим образом: Е(р, у) = ) А(х, у)др(х), (4.6.3) х Е(х, т) = ) А(х, у) с(т(у), т Е (р, т) = ~ А (х, у)с((р Х т), (4.6.6) ххт если эти интегралы существуют.
Следует заметить, что если интеграл (4.6.6) существует, то он может быть заменен на любой иэ соответствующих повторных интегралов. Значение игры и оптимальные стратегии для этих игр определяются точно так же, как и для игр на квадрате. Мы приведем следующие теоремы — непосредственные обобщения соответствующих теорем для игр на единичном квадрате.
1Ч.6.1. Теорем а. Если множества Х и У компактны, а ядро А(х,у) непрерывно, то ог= оп и, кроме того, существуют оптимальные стратегии. !Ч.6.2. Теорем а. Если множества Х и У вЂ” выпуклые компактные надпространства некоторых линейных пространств, ядро А(х, у) непрерывно, а также вогнуто по х (для каждого у) и выпукло по у (для каждого х), то игра имеет решение в чистых стратегиях. Доказательства теорем 1Ч.6.1 и 1Ч.6.2 являются легкими обобщениями доказательств теорем 1Ч.3.1, 1Ч.3.2 и 1Ч.4.2.
(Заметим, 1У. б. Более высокое раэмеркоеги $03 что эти доказательства не использовали конкретных особенностей структуры множеств чистых стратегий, а только их компактность н выпуклость.) Здесь мы не будем нх приводить. Как и прежде, необходимо указать, что общих методов решения непрерывных игр пока не создано, но разрывность очень часто будет давать нам возможность решать такие игры аналитически. !Ч.6.3. Пример. Два генерала, командующие одинаковыми армиями, должны бороться за захват трех стратегических пунктов. При этом боевые условия таковы, что та сторона, которая располагает у данного пункта ббльшим числом солдат, захватывает его. Считается, что обе армии бесконечно делимы, а выигрыш равен просто числу захваченных пунктов. Множество Х будет таким множеством всех упорядоченных троек х = (хь хэ, хэ), что х|+ хе+ хе = 1, х, 2:..
О, 1 = 1, 2„ 3. (4.6.6) (4.6.7) Множество У определяется аналогично. Функция выигрыша есть А(х, у)=з!пп(х,— у)+з1дп(х — у)+з!ап(х — у,). (4.6.8) (0,1, 0) Это эквивалентно тому, что каждый из игроков выбирает три неотрицательных числа, сумма которых равна 1. Игрок побеждает, если два из его чисел больше, чем соответствующие два числа, (, 1) выбранные его противником. Если какие-либо два соответствующих числа равны, то это приводит к ничьей.
Мы можем представить мно- ',Ф:: ° жество Х равносторонним треугольником (рис. 1Ч. 6.1). Можно заметить, что если игРок выбирает некоторую точку Р (как показано на рисунке), то он победит, если его противник выберет любую точку, содержа- ( 0 щуюся в областях О, Е и Р, и проиграет, если его противник выбе- Р и о. 1Ч. 6.!. рет любую точку, содержащуюся и областях А, В и С.
(При выборе противником точек на отрезках, разделяющих эти области, игра заканчивается вничью.) Предположим, что оптимальные стратегии существуют и что они являются непрерывными распределениями, которые могут быть представлены интегралом Лебега от некоторой функции 1, положи- Ге, 17. Бесконечные игра тельной внутри некоторого связного множества М и равной нулю вне его.
Предположим, далее, что 1 положительна в окрестности точки Р. Если Р' = Р+ ЬР— любая другая точка из этой окрестности, то мы знаем (ввиду симметрии игры), что В(р, Р) =ВЬч Р) =О. Тот факт, что Е(1г, Р) = О, означает !' г(О = ~/е лпвпс (где и†мера Лебега). Аналогично ИО= Ь, ЖПВ ОС (4.6.9) (4,6.10) (4.6.13) ы /.з ы Таким образом, мы можем утверждать, что интеграл от функции 1 имеет одно и то же значение вдоль всех отрезков, параллельных сторонам нашего треугольника и пересекающих множество М, где А', В', С' — множества точек, которые «выигрывают» у Р'. Из рис.
1Ч.6.2 легко усмотреть, что два множества А () В ()С и А'()В'()С' отличаются просто на три полоски, лежащие между прямыми Еь ~.ь Т.г, проходящими через точку Р параллельно сторонам треугольника (сплошные линии), и соответствующими пунктирными прямыми, проходящими через точку Р'. Если Р = (хь хь х,), а ггР— (Ахи егхе сгхг) го можно за метить, что для малых ЬР разность между левыми частями равенств (4.6.9) и (4.6.10) приближенно можно выразить как Лх, ~ ) (з+ Лх, ~ ~ с!з+ Ьхг ~ ~ Ь Р и с.
!ч1. 6.2. ы Ь» гн (4.6.1 !! (где з — линейная мера Лебега). Выражение (4.6.11) должно обращаться в нуль при всех значениях Ьхь Лхгн гххм удовлетворяющих условию счх, + счхе + счхг = О. (4.6.!2) Это значит, что ту. б. Более высокие розмериости 105 Теперь мы должны определить множество М. Предположим прежде всего, что замыкание множества М не касается прямой хз О, и найдем точку Р этого замыкания с минимальным значением хь Поскольку эта точка принадлежит замыканию множества М, в ней должно выполняться равенство (4.6.9).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
