Дополнение. Выпуклые игры [c.264]
Множество всех выпуклых игр мы будем обозначать через [c.264]
Сначала мы построим достаточно простую теорию выпуклых игр на единичном квадрате, а затем рассмотрим некоторые вопросы, относящиеся к случаю более общих выпуклых игр. [c.118]
ВЫПУКЛЫЕ ИГРЫ НА ЕДИНИЧНОМ КВАДРАТЕ. ЧИСТЫЕ ОПТИМАЛЬНЫЕ СТРАТЕГИИ ИГРОКА 2 [c.121]
Как и во всякой непрерывной игре на единичном квадрате (см. последнее следствие в п. 11.4), в выпуклой игре игроки имеют смешанные оптимальные стратегии. В этом и в следующих параграфах будут описаны строение и способы нахождения оптимальных стратегий игроков в выпуклых играх на единичном квадрате. [c.121]
Согласно принципу двойственности для антагонистических игр (см. п. 5.4 гл. 1) выпуклым играм соответствуют вогнутые в смысле следующего определения. [c.121]
Далее нами будет строиться теория выпуклых игр. Очевидно, теория вогнутых игр будет двойственной к ней, и ее положения получаются естественным образом из соответствующих положений теории выпуклых игр. [c.121]
Теорема. В выпуклой игре на единичном квадрате игрок 2 имеет чистые оптимальные стратегии. Множество всех таких стратегий составляет сегмент. [c.121]
Следствие. Б выпуклой игре [c.122]
Следствие. Чистые оптимальные стратегии у игрока 2 в выпуклой игре суть решения уравнения [c.122]
ВЫПУКЛЫЕ ИГРЫ НА ЕДИНИЧНОМ КВАДРАТЕ. ОПТИМАЛЬНЫЕ СТРАТЕГИИ ИГРОКА 1 [c.123]
Лемма. Если у - оптимальная стратегия игрока 2 в выпуклой игре с функцией выигрыша Н, дифференцируемой по у, и у > 0, то существует такая существенная стратегия х игрока 1, что [c.123]
Теорема. Пусть Г - выпуклая игра с функцией выигрыша Н, дифференцируемой по у при любом х, у - чистая оптимальная стратегия игрока 2 в ней, avr -ее значение. Тогда [c.124]
СТРОГО ВЫПУКЛЫЕ ИГРЫ [c.125]
Теорема. В строго выпуклой игре Г игрок 2 имеет единственную оптимальную стратегию, которая является чистой. [c.125]
ОБЩАЯ СХЕМА РЕШЕНИЯ ВЫПУКЛЫХ ИГР НА ЕДИНИЧНОМ КВАДРАТЕ. ПРИМЕРЫ [c.125]
На основе сказанного в 13 и 14 решения выпуклых игр естественно находить по схеме, состоящей из следующих пунктов. [c.125]
Говоря даже чисто формально, в игре из предыдущего параграфа случай, когда я = 0 или Ъ = 1, рассматривать нельзя ввиду обращения в нуль знаменателей в дробях из (18.1) и (18.2). Однако, как мы сейчас увидим, отличие выпуклой игры на единичном квадрате с неограниченной функцией выигрыша от ранее рассмотренных выпуклых игр чисто формальным и остается, потому что стратегии игрока 2, на которых его потери становятся уже очень большими, оказываются доминируемыми и могут быть исключены из рассмотрения. [c.133]
Покажем, что анализ игр такого рода сводится к анализу уже рассмотренных выше выпуклых игр. [c.133]
Анализ таких игр во многом напоминает анализ выпуклых игр на единичном квадрате, проведенный в предшествующих параграфах. [c.136]
Теорема. В выпуклой игре Г = < х, у, Я) игрок 2 имеет чистую оптимальную стратегию. [c.136]
Доказательство. Так как рассматриваемая выпуклая игра компактна, согласно теореме п. 10.1 она имеет значение иг, а игроки 1 и 2 — оптимальные (вообще говоря, смешанные) стратегии X и Y. Тогда [c.136]
Следствие. В выпуклой игре Г из (22.1) имеет место равенство [c.136]
Для простоты дальнейших рассмотрений мы ограничимся случаем, когда оптимальная стратегия у игрока 2 в выпуклой игре Г является единственной. Это будет, например, в том случае, когда функция выигрыша Я строго выпукла (ср. 15). [c.137]
ВЫПУКЛЫЕ ИГРЫ С ВЕКТОРНЫМИ СТРАТЕГИЯМИ. ОПТИМАЛЬНЫЕ СТРАТЕГИИ ИГРОКА I [c.137]
Усложнение, которое наблюдается в описании и нахождении оптимальных стратегий игрока 1 при переходе от выпуклых игр на единичном квадрате к векторным выпуклым играм, выходит за пределы обычных усложнений, возникающих при переходе от оптимизационных задач одной переменной к оптимизационным задачам нескольких переменных не поддается распространению на векторный случай теорема п. 14.5. Ее роль будет играть следующее утверждение. [c.137]
Теорема. В выпуклой игре Г = < х, у, Н) <, где у G Rw, игрок 1 имеет оптимальную стратегию, являющуюся смесью не более чем п+ 1 [c.138]
Выпуклая игра Г является непрерывной, а потому (см. п. 11.2) вполне ограниченной. Следовательно, согласно теореме п. 8.1 она имеет значение vr, а при любом е > О игрок 1 имеет в ней е-оптимальную стратегию с конечным спектром. [c.138]
В выпуклой игре Г из (24.3) игрок 2 обладает чистой оптимальной стратегией , и мы имеем [c.141]
Кардинально выпуклая игра также имеет непустое с -ядро. [c.204]
Заметим, что выпуклая игра является супераддитивной, так [c.211]
Никаких общих методов для точного нахождения решений бесконечных антагонистических игр, и в том числе непрерывных игр на единичном квадрате, пока не найдено. Известны только отдельные индивидуальные приемы, годные лишь для тех или иных сравнительно узких классов игр. Один из таких классов составляют антагонистические игры с выпуклыми функциями выигрыша. Они представляют также известный при- > кладной интерес. Далее мы рассмотрим несколько примеров таких выпуклых игр. [c.117]
Доказательство. Рассмотрим выпуклую игру Г с функцией выиг- [c.121]
Пусть в выпуклой игре Г на единичном квадрате функции Я (х, ) y->R не обязательно непрерывны. Тогда, как это было установлено в п. 12.5, точками разрыва каждой из этих функций могут быть разве лишь точки 0 или 1 (в которых эти функции должны быть полунепрерывны сверху). [c.134]
Нашей ближайшей целью является распространение методики решения выпуклых игр на единичном квадрате на аналогичные игры, в которых множествами стратегий игроков являются подмножества конечномерных евклидовых пространств. В основе такого обобщения будет лежать тот факт, что можно говорить о выпуклых функциях нескольких переменных (или, что то же самое, - о выпуклых функциях от векторного переменного), причем как определение, так и основные свойства этих функций те же, что и для выпуклых функций одного переменного. [c.135]
Отмеченная в п. 8.3 принципиальная возможность сколь угодно точного решения вполне ограниченных игр, и в том числе — согласно п. 11.4 - непрерывных игр на единичном квадрате, распространению на игры на единичном квадрате с разрывными функциями выигрыша, вообще говоря, не поддается. В 20 нами были рассмотрены выпуклые игры с разрывными функциями выигрыша при конкретных значениях стратегий игрока 2. Модифицируя эти рассуждения, можно без труда показать, что игры на единичном квадрате, в которых функция выигрыша Н терпит разрывы лишь вдоль конечного числа отрезков вида х - onst или у - onst, являются вполне ограниченными, и их решение напоминает решение непрерывных игр. [c.145]
Заметим, что выпуклая игра является супераддитивной, так как и(0) = 0. [c.186]
Если игра v выпукла, то значение Шепли игры v лежат в с -ядре игры v (Shap-ley, 1971). Заметим, что в случае, например, супераддитивности игры v вектор Ф(и) может даже не принадлежать непустому с-ядру. Более подробно о выпуклых играх см. раздел 6.6. [c.191]