Теория игр. Оуэн (1971) (1186151), страница 17
Текст из файла (страница 17)
(3.7.20) Можно показать, что задача (3.7.17) — (3.7.20) является двойственной для задачи (3.7.13) — (3.7.16). Поэтому если обе эти задачи допустимы, то выражения (3.7.1) и (3.7.6) будут равны и, таким образом, игра с ограничениями будет иметь решение в смешанных стратегиях. Задачи то ( с(х)1(х) дх ~ ~ Ь(у) у(у) Иу. 4, Пусть А — матричная игра, н пусть  — матрица тех же размеров, итон А. Обозначив через п(А) значение игры А, определим до (А) .
о (А+ пВ) — э (А) Вгп дВ а.»+о и Показать, что — - щах пйп хВу, до (А) г дВ х' эмт где Хо н у* — множества оптимальных стратегий соответственно агранов 1 и П для игры А. 5. Задача о потоке содержит систему узлов (вершин), пронумерованных числами О, 1, 2, ..., л+! н связанных ребрамн Аы (гча)).
Узлы, отмеченные 0 н л + 1, выделены; они называютси соответственно источником и стоком, Ребра неориентированные, следователю<о, Аы и Аы совпадают. Каждое ребро имеет пропускную способность Сы, и каждый узел также имеет пропускную способность Си. (Некоторые ребра А„могут отсутствовать; а этом случае Сы О,) Поток является вектором х (хы), в котором компонента х«представляет количество, «протекающее» от узла 1 к узлу 11 Поток должен, конечно, удовлетворять очевидным ограничениям 1,1-1, ..., л, <'=1, ..., л, х ~С х,. - ~я~~ х< ~х го«< !Ф< л+1 хо»= ~Х'„< хо! л "л+<,л+~-Х х<,л+<. г=о Значение потока есть число хао Показать, что х,„хо+<, о+ь Разрезом называется набор ребер н узлов, который пересекает любую цепь'.
из ребер и узлов, идущую от источника к стоку. Значение разреза равно сумме пропускных способностей ребер и узлов в соответствующем наборе. Доказать. теорему о максимальном потоке и минимальном разрезе: значение максималь- ного потока равно значению минимального разреза. 6. Максимизировать 2х, + 5хз при условиях хо +Зх, ~ 7, 2х<+ хз ~ 5, хьхз ~ О.
Зх< + бхз — хз х< + 4хз + 5хз ~ 7, Зхз+ хз ~ 5, Зх< — хз ~ 8, хь хз, хз~ О. Гл. П!. Линейное нрограммирование хз + 4хз — бхз Зхз+2хз — хз ~5, хз +4хз~у, -х,+4х,+ хзз 8. хь х„хз ~ О. х, +хе+хе+х, Зхз+2хз+хе+ хзм 1 хе+хе хз~6, «з +хз+2х, 8, хь хз, хз, хе~О.
8. Максимизировать при условиях 9. Минимизировать при условиях 2 5 б 3 10. 12. 5 8 3 1 6 4 2 б 3 5 2 4 6 4 1 ! 3 2 5 3 Найти пару оптимальных стратегий и значение для мых игр. Глава ГУ БЕСКОНЕЧНЫЕ ИГРЫ !У. и ИГРЫ СО СЧЕТНЫМИ МНОЖЕСТВАМИ СТРАТЕГИИ До сих пор мы имели дело главным образом с конечными играми, т. е.
с играми, в которых каждый игрок имеет конечное. число стратегий. Перейдем теперь к бесконечным играм. Рассмотрим прежде всего игры со счетным множеством чистых стратегий. Обычно этн стратегии будут нумероваться целыми по- ложительными числами. Как в конечных играх, пусть ап представ- ляет выигрыш, получаемый игроком 1 от игрока П при условии, что игрок 1 выбирает !-ю стратегию, а игрок П вЂ” свою 1-ю чистую стратегию. В этом случае смешанной стратегией игрока 1 будет последо- вательность (хь хм...), для которой ~ х,=1, ! ! х,:О.
(4.1.4) ОО С ~ х,ану! ! ! ! ! (4,!.5) существуют, но различны, Во-вторых„множества смешанных стратегий не компактны и, таким образом, максимумы и минимумы Смешанной стратегией игрока 11 будет последовательность ,(у„ум ...), определяемая аналогично. Функция выигрыша при смешанных стратегиях (х,у) определяется следующим образом: А (х, у) ~ х,а,!у! (4.1.3) !,! ! при условии, что этот ряд абсолютно сходится. Игры со счетным числом стратегий обладают рядом нежелательных свойств, которых нет у конечных игр. Здесь могут возникнуть следующие трудности: во-первых, ряд (4.1.3) не, обязательно сходится и может случиться, что суммы ~ ~~~~ х,ану! ! ! ! 1 Гл, !й. Бегееигчинг игры У-1 ;р~ х,)1 — е, :и, таким образом, ~ хг<е.
г у (4.1.6) Предположим, что если игрок 1 выбрал смешанную стратегию х, игрок П выберет свою М-ю чистую стратегию. Тогда, очевидно, ожидаемый выигрыш первого игрока равен ~~~~ аглхг< — 1+ 2е ,и поэтому 1п1 ~ агах,= — !. У ! .Но стратегия х произвольна; следовательно, знр!п1 ~ ад,х,= — 1. г Ф (4.1.7) Аналогично можно показать, что 1п1 епр ~ аз~у! = 1, у У ! (4.1.8) и 'мы видим, что теорема о минимаксе (даже обобщенная путем замены ппп и шах на !п1 и знр) не имеет места. Заметим также, что каждая строка и каждый столбец доминируются. 1'й.!.2. П ример. Рассмотрим игру с матрицей выигрышей ам =1 — 1. Как и в примере 1У.1.1, все дело здесь в выборе как можно большего числа. Однако это усложнено тем, что функция выигрыша не ограничена. не будут существовать. Для того чтобы продемонстрировать эти трудности, мы приведем два примера; следует заметить, что тот интерес, который представляют игры со счетным числом стратегий, практически исчерпывается этими примерами.
1'й.1.1. П р и м е р . Рассмотрим игру с функцией выигрыша ап = з)дп(! — 1), (В сущности эта игра приводит к следующему: каждый игрок выбирает натуральное число; выбравший меньшее число платит противнику единицу.) Такая игра представляется нелепой, но в действительности дело обстоит еще хуже, Действительно, предположим, что х — смешанная стратегия игрока 1. Известно, что для любого заданного е ) О можно найти такое М, что 1К 2. Игр!! на квадрате Рассмотрим теперь стратегию х, определяемую равенствами 11'(2!), если 1= 2", Й вЂ” целое, х,= 0 в противном случае. (4.!.9).
Легко проверить, что это действительно стратегия. Теперь для любого ! Ю О х,! х а! ! = ~х',! !х! — ~ /х! = ~~~ !х ! 1 ! ! ! ! ! Поэтому ~~р~ х;аы — — + со ! (4.1. ! 0) 1У. 2. ИГРЫ НА КВАДРАТЕ Важный класс бесконечных игр составляют игры, в которых каждый игрок имеет континуум чистых стратегий, обычно представляемых точками интервала [О, Ц. Тогда чистой стратегией каждого из игроков будет число из этого интервала, а функцией выигрыша — вещественнозначная функция А (х, у), определенная на единичном квадрате [О, Ц Х [О, Ц.
Как и прежде, смешанная стратегия представляет собой вероятностное распределение на множестве чистых стратегий. В нашем случае смешанная стратегия может быть представлена функцией распределения, т. е. функцией Р, определенной на [О, Ц и такой, что Р(0) =0; Р(Ц= 1; если х)х', то Р(х) ) Р(х'); если хФО, то Р (х) = Р (х+ 0). (4,2.!'р (4.2.2) (4.2.3) (4.2.4) Если игрок 1 использует чистую стратегию х, а игрок П вЂ” смешанную стратегию б, то ожидаемый выигрыш равен интегралу и, следовательно, математическое ожидание выигрыша игрока 1.
если он применяет смешанную стратегию х, а игрок П любую чистую стратегию, равно бесконечности. Иначе говоря, первый игрок может гарантировать себе бесконечное математическое ожидание выигрыша, как бы ни поступал игрок П. Но игра симметрична, и поэтому игрок П также может обеспечить себе бесконечное математическое ожидание выигрыша. Таким образом, мы имеем патологическую игру. Действительно, пример 1У. !.! противоречит только теореме о мннимаксе, последний же пример противоречит просто здравому смыслу. Га !"е'.
Беекооеооо!е ие!!о! -Стильтьеса Е (х, б) = ~ А (х, у) И О (у). о (4.2.5) Если же игрок П использует чистую стратегию у, а игрок 1— смешанную стратегию Р, го ожидаемый выигрыш равен Е(Р, у) = ) А(х, у) е(Р(х). о (4.2.6) Наконец, если игрок 1 использует Р, а игрок П использует б, то мы имеем Е(Р, О) = ~ ~ А(х, у) ИР(х) !(О(у), (4.2.7) о о считая в каждом случае, что интегралы существуют.
Разумеется, если они существуют, то Е(Р, О) = ~ Е (Р, у) с(б (у) = ~ Е (х, б) е1Р(х). (4.2,8) Оптимальные стратегии и значение игры. Как и в конечных играх, можно определить два числа о! — — зпр !п1 Е (Р, у) Р у (4.2.9) оп=!п1зцр Е(х, О). (4.2.10) Возникают два вопроса. !) Будет ли выполняться равенство о! = оп? 2) Можно ли зпр!п1 и !п1зпр заменить на шахппп н пинтах соответственно? Если ответ на оба эти вопроса положителен, то оптимальные смешанные стратегии существуют; если их можно найти, то игра определена столь же хорошо, как и конечные игры.
В таком случае, когда ответить утвердительно можно только на первый вопрос, игра имеет значение (общая величина о! и оп), но не имеет оптимальных стратегий. Тем не менее она будет иметь е-оптнмальные стратегии; иначе говоря, для любого е > 0 существуют такие смешанные стратегии Р и б игроков 1 и П соответственно, что Е(Р, у)) о — е (4.2.11) н Е(х, О)(о+в (4.2,12) !К 3.
Игры о непрерывным ядром 91 для любого х и у из [О, Ц. Таким образом, хотя игра определена не столь же хорошо, сколь конечные игры, она обладает известной устойчивостью. 1Ч. 3, ИГРЫ С НЕПРЕРЫВНЫМ ЯДРОМ Среди игр на квадрате самыми очевидными «кандидатами на проверку» являются игры, в которых функция выигрыша А(х,у) (обычно называемая ядром) непрерывна. Для таких игр оптимальные стратегии существуют, что мы сейчас и докажем. !Ч3.1. Т ео р ем а.
Если ядро А (х, у) — непрерывная функция, то зир !п1 и !п1 зир могут быть заменены на шах ппп и ш!п шах соответственно. Доказательство. Известно, что функция А(х,у) непрерывна. Поэтому для любой Р функция Е(Р, у)= ) А(х, у)др(х) о пип Е (Р„, у) ) о, — 1/л. Заметим теперь, что из любой последовательности функций распределения (Рь Рь...) на [О, Ц можно извлечь некоторую поточечио сходящуюся подпоследовательность. Пусть Ро — предел этой подпоследовательности. Ясно, что Ро удовлетворяет условиям (4.2.1), (4.2.2) и (4.2.3), так как им удовлетворяет каждая из функций Р„.
С другой стороны, Ро не обязательно удовлетворяет (4.2.4), потому что это свойство не сохраняется при предельном переходе, Тем не менее определим функцию Ро следующим образом: О, если х= 0, Ро(х)= Ро(х+0), если 0<х<1, 1, если х=1; (4.3.1) легко видеть, что Ро является стратегией.
Функции Ро и Ро отличаются только в точках разрывов; но так как эти функции непрерывна по у. Так как интервал [О, Ц компактен, Е(Р,у) в некоторой его точке будет достигать минимума. Таким образом, зпр!п1 можно заменить на знр ппп. По определению ог для любого а существует такое распределение Р„, что Гл. !У. Бееноненнь~е игры ) А(х, у)дго(х)= ) А(х, у)ЙРо(х). Функция А(х,у) непрерывна и, следовательно, равномерно непрерывна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
