Теория игр. Оуэн (1971) (1186151), страница 18
Текст из файла (страница 18)
Ввиду того что Ео является пределом подпоследовательности из Е„, мы имеем )' А (х, у) дРо (х) = 1пп ) А (х, у) дрн(х). о о Но последний предел не меньше о~ для каждого значения у. Таким образом, пппЕ(ро, у) ~ о~ (4.3.2) е и на Ро достигается требуемый максимум, Аналогично можно показать, что !п1знр можно заменить на пп'п шах. 1Ч.З.2.
Т е о р е м а. Если ядро А (х, у) непрерывно, то ое = оп. Д о к а з а т е л ь с т в о. Для любого целого числа п рассмотрим ((п+ 1) Х(и+ 1))-матрицу А„=(а"„), где а",. = А(1/и, //и), 1, /=О, ..., и. Игра с матрицей выигрыша А„имеет значение шн и оптимальные стратегии г„=(г,", ..., е„") и з„=(з", ..., зн) игроков 1 и 11 соответственно. Функция А(х,у) непрерывна. Так как квадрат компактен, то А равномерно непрерывна. Таким образом, для заданного а ) О можно найти такое б > О, что если 1/(х — х')'+ (у — у')' <б, 1А(х, у) — А(х', у') ~<е.
то Возьмем п столь большим, чтобы 1/п < б. Определим стратегию Ен(х) равенством [нх! Р„(х) = ~ г"„ (4.3.4) '(здесь (пх) обозначает целую часть числа пх). монотонны, точки их разрывов образуют счетное множество и по- этому для всех у 93 гу.8. Игры с непрерывным ядрам Для любого у положим 1 = [пу). Ясно, что и 17п) — ~~~~ пи г в ) в и так как !у — 1'/п~( б, ! А(х, у) — А(х, 17п) !(е, (4.3.5) имеем ! Е(Еп, у) — Е(Еп, 1!л) !(е. Следовательно, для любого у Е(Е„, у))в„— е и поэтому о~) в„— е. (4.3.6) Аналогично можно показать, что (4.3.7) оп(в„+е.
Из двух последних неравенств получаем о1) оп — 2е. Но из того, что ог-='оп и е произвольно, следует, что о~ = оп. (4.3.8) Из доказательства теоремы 117.3.2 следует, что, во-первых, о =!пп в„ (4.3.9) и н, во-вторых, что стратегии Еп аппроксимируют оптимальную стратегию сколь угодно точно.
В этом смысле матричные игры аппроксимируют непрерывную игру А(х, у). Если ядро очень гладкое, то может оказаться, что уже при очень небольшом и аппроксимация будет достаточно хорошей. С другой стороны, если ядро слишком нерегулярно, то для хорошей аппроксимации требуются большие значения и. Методы, в большинстве случаев используемые для решения матричных игр (метод фиктивного разыгрывания и симплекс-метод), не позволяют достаточно быстро решать игры размером, скажем, 100 Х 100. Таким образом, предпочтительнее было бы находить решения таких игр аналитически. К сожалению, общих методов для этого пока не существует.
Развитие таких методов — одна из насущных задач на сегодня. Было бы также желательно найти способ выяснения того, может ли оптимальная стратегия Е быть ступенчатой функцией, т, е. достаточно ли конечного числа чистых стратегий или же должны использоваться непрерывные функции распределения. Следующие параграфы показывают, каких успехов можно добиться в этих направлениях, Гл.
И. Бескокечныо игры ГЕ. 4. ВОГНУТО-ВЫПУКЛЫЕ ИГРЫ Д о к а з а т е л ь с т в о. Так как игра непрерывна, она имеет оптимальные стратегии. Пусть ими будут г и б для игроков 1 и П соответственно. Теперь положим хо= ~ хо(Е'(х), о 1 уо= ~ уо(В(у). о (4А.1) (4.4.2) Так как функция А вогнута по х, то для любой заданной у существует такое ос, что функция Во(х) = А(х, у) — ах достигает своего максимального значения (при фиксированной у) в точке х,. Мы имеем 1 Е(Р, у) = ~ (Во(х)+ах) ат" (х), о ! 1 Е (Р, у) = ) В „(х) 0Р (х) + а ) х дР (х). о о (4.4.3) Функция В„достигает максимума в хо, следовательно, первый интеграл в равенстве (4А.З) не превосходит Во(хо). Поэтому Е (Р, У) ~ Вд (хо) + ахо = А (хо У) (4,4.4) откуда следует, что хо не хуже Р против любой у, Аналогично можно показать, что уо не хуже б против любой х.
Таким образом, хо и уо — оптимальные чистые стратегии. В известном смысле доказательство теоремы 1Ч.4.2 излишне усложнено. Едва ли желательно, чтобы в ее доказательстве исполь- 1Ч.4.1. Определение. Говорят, что игра на квадрате вогнуто-вьтукла, если ее ядро А(х, у) вогнуто по х при каждом значении у и выпукло по у при каждом значении х.
По существу вогнуто-выпуклая игра должна иметь седлообразное ядро. Так как ядро седлообразно, следует ожидать, что игра будет иметь седловую точку в чистых стратегиях. То, что это действительно так, доказывается — при дополнительном предположении непрерывности — следующим образом. 1Ч.4.2. Теорема. Пусть вогнуто-выпуклая игра А(х,у) непрерывна.
Тогда она имеет оптимальные чистые стратегии, т"т', 4, Вогнуто-вылунлыг игры зовались смешанные стратегии, в то время как сама она касается лишь чистых стратегий. Поэтому мы дадим доказательство, в котором используются лишь чистые стратегии, при несколько более сильном предположении строгой вогнутости и строгой выпуклости. !Ч43. Вариант доказательства теоремы ГЪт42 (в предположении строгой вогнутости и выпуклости). Для любого значения х существует единственное значение у (ввнду строгой выпуклости), которое минимизирует А(х,у). Обозначим это значение у через ф(х). Таким образом, мы имеем А(х, ф(х)) = пипА(х, у).
(4.4.8) А(хл«, ф(х «)) < 4 (хл«> уа)1 а поэтому, переходя к пределу и используя непрерывность А, получаем А (хо у ) =.=' А (хо. Уо). Но уо — единственное значение у, которое минимизирует А(хо, у). Это противоречие показывает, что ф(х) должна быть непрерывной функцией. Аналогично мы можем определить функцию ф(у) как значение х, которое максимизнрует функцию А(х, у), т, е. А (ф (у), у) = шах А (х, у). л (4.4.6) Рассмотрим теперь композицию функций ф ° ф. Очевидно, что это непрерывное отображение отрезка (О, 1] в себя.
По теореме Брауэра о неподвижной точке должно существовать такое х, что х=ф ° ф(х). Если мы положим у = ф(х), то последнее будет означать, что х=ф(у), (4.4.7) у=ф(х). (4.4.8) Но это и значит, что х и у образуют седловую точку, т. е. яв- ляются оптимальными стратегиями. Предположим, что функция ф не непрерывна. Пусть, скажем, ф(х) разрывна в точке хо и ф(хо) = уо. Тогда существует такая последовательность чисел (хи хм...), что хо является пределом х„„а уо не является пределом ф(х„). В силу компактности существует такая подпоследовательность (х„«1 последовательности (хл), что ф(хл„)сходится к у', где у'Ф уо.
Далее, Гм !К Бесконечные игры И.4.4. П р и м е р. Рассмотрим игру с ядром А (х, д) = — 2х'+ у'+ Зху — х — 2у. А„= — 4х+ Зу — 1; полагая это выражение равным нулю, найдем Зу — 1 х=— 4 Это значение х максимизирует А. Однако оно не всегда лежит в единичном интервале, будучи отрицательным при у < 1/3.
В по- следнем случае мы получаем максимум, полагая х = О. Следова- тельно, (о, если у ( '/,, 1 (Зу — 1)/4, если у = '/,. (4.4.9) Аналогично находим Ае = 2у + Зх — 2, откуда следует, что (2 — Зх)/2, если х == '/„ О, если х = т/,. (4.4.10) Теперь легко найти оптимальные стратегии и значение игры: /и у= /п о= /и. 1Ч.5. ИГРЫ С ВЫБОРОМ МОМЕНТА ВРЕМЕНИ Выше мы упоминали, что непрерывные игры всегда имеют оптимальные стратегии, но общих аналитических методов их вычисления нет. С другой стороны, в то время как мы не можем быть уверены, что все игры с разрывными ядрами имеют оптимальные стратегии, в некоторых случаях именно разрывность позволяет нам находить оптимальные стратегии (если они существуют) аналитическими методами.
Здесь нас будет интересовать один тип игр на квадрате, называемых играли с выбором момента времени. Прототипом такой игры является игра, в которой каждый игрок может сделатьтолько одно действие в течение данного интервала времени. Порядок, в котором игроки действуют, чрезвычайно важен. Этот факт является причиной разрыва ядра вдоль диагонали х = у квадрата. Легко видеть, что А„, = — 4, А„„= 2, поэтому это игра действи- тельно вогнуто-выпуклая. Мы видим, что тУ.
5. Оерм с винером момента времена (4.5.2) (4.5.4) то Е(Е, уо)=о, (4.5.5) где о — значение игры. Теперь, если 0' положительна в точке уо, то она положительна и в некоторой окрестности уо. Поэтому для любого у, достаточно близкого к уо, мы будем иметь Е(у,у) о. Но это значит, что дЕ (Е, д)/ду = О. Уравнение (4.5.6) можно переписать в виде е (Е(у, у)-К(у, у)]Е'(у)= ~ Ко(х, у)Е'(х)с(х+ о ! + ~ Е„(х, у) Е' (х) Ых (4.5.6) (4.5,7) Рассмотрим игру с ядром А(х, у) вида К(х, у), если х<у, А(х, у)= !р(х), если х=у, (4.5.1) Е(х, у), если х)у, где функция К определена и непрерывна на множестве О~х~ : у Ы 1, функция Е определена и непрерывна на, множестве О==у~х~1, а функция !р непрерывна на (О, Ц. Нельзя быть уверенным, что оптимальные стратегии в этой игре существуют.
Тем не менее мы можем определить некоторые свойства оптималь- ных стратегий в предположении, что они существуют, Пусть Š— смешанная стратегия игрока 1. Для уен(0, Ц мы имеем Е(Е, у) = ~ К(х, у) с(Е(х)+ !р(у)(Г(у) — Е(у — 0)]+ о ! +1 Е(х, у)др(х). Если Š— непрерывная функция распределения, мы, разумеется, можем опустить среднее выражение и получим е ! Е(Г, у)= ~ К(х, у)с(Е(х)+ ) Е(х„д)!(Е(х).
(4.5.3) О у Предположим, что Е и ст — оптимальные стратегии игроков 1 и 11 и что обе они являются непрерывными функциями распреде- ления. Известно, что если Е и б оптимальны, а уо — точка, в ко- торой а'(уе) ~ О, Гл. гу, Бееконечнае игра Е(Р, у)=о для уен(с, с(), Е(Р, у) == о для всех у, Е(х, 6)=о для хы(а, Ь), Е(х, 6) ~ о для всех х, (Е(у, у) — К(у, уИР'(у)= е 1 = ) Ке(х, у)Р'(х)с(х+ ~ !.„(х, у)Р'(х)с(х для уев(с, с(), (45.12) о У (К(х, х) — Е(х, х)) б'(х) = л ! = ) Е„(х, у) 6'(у)Ну+ ) К„(х, у) б'(у)г!у для хан(а, Ь).
(4.5.13) (4.5.8) (4.5.9) (4.5.10) (4.5.1 1) Конечно, к этим шести соотношениям мы должны добавить ограничения О ~ а <Ь ~ 1, О ~ с <аг == 1; кроме того, Р и б должны быть стратегиями. Если вся система имеет решение, то это решение даст нам оптимальные стратегии, а также значение игры, Если решения нет, то мы заключим, что игра либо не имеет оптимальных стратегий, либо, если она их имеет, то они не такого типа, как предполагалось выше. Иногда ядро кососимметрично, т. е. (4.5.14) (4.5.15) Е(х, у) = — К (у, х), гр (х) = О. Если это так, то анализ, аналогичный проведенному в э П.б, показывает, что значение игры, если оно существует, должно равняться нулю, а оптимальные стратегии, если они существуют, должны быть одинаковы для обоих игроков.
Таким образом, мы будем иметь Р = б, а с, Ь = с! и о = О, и указанные выше соот- (интегральное уравнение относительно Р', которое иногда довольно легко решать). Предположим теперь, что нам дана игра с ядром вида (4.5.1). Мы не можем гарантировать существование оптимальных стратегий. Мы даже не знаем, будут ли они непрерывными, дискретными или частично непрерывными и частично дискретными распределениями. Однако довольно естественно считать, что оптимальные стратегии Р и б являются непрерывными распределениями, а их производные Р' и 6' положительны на интервалах (а, Ь) и (с, г!) соответственно и равны нулю вне этих интервалов, Теперь мы имеем несколько соотношений, связывающих функции Р, б и числа а, Ь, с, с(, о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
