Теория игр. Оуэн (1971) (1186151), страница 22
Текст из файла (страница 22)
Если игрок 1 не действует, а игрок П инспектирует, то игрок 1 может предпринять действие в следующий период времени (в предположении, что )у) 1) и выигрыш также равен 1. Если игрок 1 не действует и игрок И не инспектирует, то мы переходим к следующему шагу игры, который отличается от предыдущего только тем, что до конца игры остается меньшее число периодов времени. Следовательно, матрица для первого шага игры выглядит следующим образом: р (5.2.4) Это дает нам следующее рекурсивное определение ') о„= ча! Далее ясно, что ок ~ < 1; следовательно, матрица (5.2.5) не имеет седловой точки. Поэтому мы можем применить формулу (2.5.24) и получить разностное уравнение оэ — о +3! (5.2.6) У-1 (5.2.5) которое вместе с начальным условием о,=О приводящей к новому разностному уравнению !я = гм, — !/2, !! = — 1.
(5.2.9) (5.2.10) Это уравнение имеет очевидное решение ! и = — (Лг + 1)/2, откуда оэ = (й! — 1)/(Лг + 1). (5.2.1 1) Таким образом, (5.2.11) дает нам значение игры на каждом шаге. После этого мы можем вычислить оптимальные стратегии каждого игрока на каждом шаге. Действительно, матрица игры (5.2.3) теперь принимает вид — 1 1 1 (й/ — 2)/)т' (5.2.12) '! Через ча1А обозначается значение нгрм с иатрнией А.
— Прим. нерва. (5.2.7) определяет ои Мы можем решить это уравнение подстановкой !и 1/(ои 1) (5.2.8) Гл. У. Многошаговеге иг12ее 116 и уравнения (2.5.22) и (2.5.23) дают нам оптимальные стратегии хп = (1/(/У+1), Ч/(/У+1)), (5.2.13) для У~2 уп =(1/(Ф+ 1), Ф/(Л(+1)). (5.2.14) Ч.2.3. Пример (женщины и кошки против мышей и мужчин). В этой фантастической игре группа 1 состоит из т, женщин и тг кошек; группа П состоит из п~ мышей и Л2 мужчин. На каждом шаге каждая группа выбирает представителя. Один из двух выбранных представителей устраняется, согласно следующим правилам: женщина устраняет мужчину; мужчина устраняет кошку; кошка устраняет мышь; мышь устраняет женщину.
Игра продолжается до тех пор, пока в одной из групп не останутся игроки только одного типа. Когда группа не имеет больше выбора, другая группа, очевидно, выигрывает. Матрица игры, вообще говоря, будет иметь следующий вид: с Г(т~ — 1, lП21 По П2) Г(то т2', П1, П2 — 1) (5.2.15) Г(т„т,; и, — 1, и,) Г(т„т,— 1; ио л,)/' и рассуждения, аналогичные рассуждениям примера Ч.2.2, при- водят к рекуррентному соотношению о т, т21 п, П2)- о (сл2 — 1) о (о22 — 1) — о (и, — 1) о (и, — 1) о (ое, — 1) + о (оге — 1) — о (и, — !) — о (л, — 1) (о.2.16 (здесь приняты следующие сокращенные записи: о (т, — 1) = о (т, — 1; т,; и„а,), о (т2 !) = — о (то т2 — 1; Ло П2), о (л2 1) — = о (то т2', л~ — 1, Л2), о (Л2 — 1) — = и (т1, т2'„ль пг — 1) ), которое вместе с граничными условиями о (т„т;1 п„О) = о (то т21 О, П2) = + 1, если т1, тг>О; (5.2.17) о(ть 0' ло Л2) = о (О, тг' П~ Л2) = 1 если п„пг>0, (5.2.18) индуктивно определяет значение игры.
К сожалению, это нелинейное уравнение в частных разностях решить нелегко. Однако иеко- У,З. Стокастические игры торые результаты мы получить можем; например, если тз = и, лз 1, то мы имеем и в силу симметрии (5.2.20) п (1, 1; 1, 1) = О. Но эти уравнения в точности совпадают с уравнениями примера 'у.2.2, .приведенными выше. Следовательно, п(т, 1; 1, 1) = (вг — 1)/(лт+ 1) (5.2.21) и оптимальные стратегии в этом случае также в точности совпа- дают с приведенными в примере Ч.2.2. У. 3.
СТОХАСТИЧЕСКИЕ ИГРЫ Эти игры аналогичны играм, рассмотренным в $ 7.2, но отличаются от них в некоторых важных отношениях. Здесь имеется. только конечное число различных позиций, но игра может возвращаться в предшествующую позицию, так что теоретически эти игры могут продолжаться бесконечно.
Кроме того, на каждом шаге игры обычно определен выигрыш, так что бесконечный выигрыш снова теоретически возможен. Однако правила игры включают рандомизацию, которая гарантирует, что для всех выборов стратегий вероятность бесконечной партии равна нулю и математическое ожидание выигрыша конечно. Точнее, стохастическая игра есть набор р «игровьи элементов», или позиций Гд. Каждый игровой элемент представляется (тд Х ли)-матрицей, элементы которой имеют вид а," = пег + Х ц~п Г=1 (5.3.!) где выпаО, а ~ дм<1.
(5.3.2)- (5.3.3) (5.3.4Р Элемент ае, определенный в (5.3.1); означает, что если в й-м игровом элементе игрок 1 выбирает свою 1-ю чистую стратегию„ а игрок 11 выбирает свою )чю чистую стратегию, то выигрыш равен а", и, кроме того, с вероятностью г)м для 1= 1, ..., р разыгрйвается 1-й игровой элемент, а с вероятностью Гл. !г. Гг!иогоигаговые игры з!в партия заканчивается. Условие (5.3.3) утверждает, что на каждом шаге вероятность того, что партия закончится, положительна.
Таким образом, вероятность того, что партия окажется бесконечной, равна нулю и математическое ожидание выигрыша конечно. Ч.З.!. Определение. Стратегия игрока 1 представляет собой для Ь =1, ..., р и всех положительных целых ! набор пги-векторов хи', удовлетворяющих условиям ыг ~хм 1 с-~ хг' ~ О. Стратегия будет называться сгрционарноя, если для всех й векторы хм не зависят от !. Аналогично стратегия игрока П есть набор пв-векторов ди'. Короче говоря, число хг' есть вероятность выбора игроком 1 на 1-м шаге игры в игровом элементе Гд своей (-й чистой стратегии. Так как элемент Гд может играться несколько раз, игрок 1 необязательно должен использовать одни и те же вероятности всякий раз, когда этот элемент разыгрывается.
Если же, однако, он действительно использует одну и ту же рандомизационную схему всякий раз, когда разыгрывается этот игровой элемент, то говорят, что стратегия стационарна. Естественно, что с точки зрения простоты стационарная стратегия предпочтительнее. Если дана пара стратегий, то математическое ожидание выигрыша можно вычислить для любого й = 1, ..., р в предположении, что первым шагом игры будет игровой элемент Гм Таким образом, математическое ожидание выигрыша для пары стратегий можно рассматривать как р-вектор. Как и в обычных матричных играх, это приводит к определению оптимальных стратегий и значения игры, причем значение игры есть р-вектор о =(о„оь ..., ор).
Ясно, что если вектор значений существует, то можно заменить игровой элемент Ги компонентой пи значения, Отсюда следует, что мы должны иметь (5.3.7) ог = ча! Вы где Вд есть (ти Х ли)-матРица (Ьгп), опРеделеннаЯ фоРмУлой Ф г чг гг Ьп = аг!+ ~г Ьпвь г 1 (5.3.8) Это, конечно, лишь неявное определение; мы должны показать, что существует в точности один вектор (оь ..., ор), удовлетворяющий уравнениям (5.3.7) и (5.3.8). ! !9' К д Стогагтичегкие игры Ч.3.2.
Лемма. Пусть А =(ац) и В =(Ьц) суть (т Х и)-матрицы, удовлетворяющие условию ац<Ьц+Ь, 1=1, ..., т; 1=1...., и, (5.3.9) для некоторого Ь. Тогда ча! А < ча! В + Ь. Дока з а те лье тв о. Пусть о = ча! В, а у — оптимальная стратегия игрока П в игре В. Тогда для всех ! Х а гу! < Х Ьцу, + lг Х у, -ь о+ lг, так что у дает верхнюю границу проигрыша в игре А, которая меньше о + й.
Ч.З.З. Т е о р е м а. Существует в точности один вектор о = (оь ..., оя), удовлетворяющий соотношениям (5.3,7) и (5.3.8). Д о к а з а т е л ь с т в о. Докажем сначала единственность. Предположим, что существуют два таких вектора, о и тв. Пусть. Ь вЂ” номер компоненты, для которого величина ~ог — твь! наибольшая, и предположим для определенности, что оь — твг = с) О. Определим две матрицы В„и Вг соотношениями г г ~т и -г г чт и Ьц =ац+ ~а дцоь Ьц=ац+ ~ дцшь Ясно, что и из леммы Ч.3.2 следует, что ча! Вг <ча! Вг+ с. Но так как, по предположению, о и тв оба удовлетворяют (5.3.7) и (5.3.8), то ог < твг+ с.
Однако мы предположим, что од — ш„= с. Это противоречие доказывает единственность. Докажем теперь существование. Мы построим последовательность векторов, которая будет сходиться к требуемому вектору значений. Определим индуктивно ос = (О, О ..., О), (5.3.10) Ьц = агц + ~ у~цот, г = 1, 2, ..., (5.3.! !) от+ =ча!Вг=ча! (Ь!т!). (5.3.12г Нам нужно доказать, что, во-первых, последовательность векторов о' (отц ..., о') сходится и, во-вторых, предел обладает Гл. !!. Многашагоеые игры требуемыми свойствами (5.3.7) и (5.3.8).
Положим з = !пах ~ дь!!! (5.3.13) В силу (5.3.3) и конечности множеств индексов й, !, ! имеем з < 1. Если мы положим !,= шах ~~ о',+' — о',~), то легко показать (по лемме !/. 3.2), что /, ~ з!, ! н, следовательно, /„( з'!ь. Отсюда следует, что последовательность векторов о' есть последовательность Коши и поэтому должна сходиться к пределу; обозначим этот предел через о. Положим теперь шь =ма! В, = ча!(Ьь!), тде .Мы увидим, что шь = оь для всех й.
Действительно, для любого е) О мы можем выбрать г столь большим, чтобы для всех Ф выполнялись неравенства ~ о' — о,) <е/2, ~ о'+' — о„) <е/2. (5.3.14) (5.3.15) Легко показать, что из (5.3.14) и леммы Ч.3.2 следует, что для всех й будет !оь+! — шь) <е/2; это вместе с (53.15) означает, что для всех /! ! и!ь — оь !<е. Но так как е произвольно, од = шь. Вторая часть доказательства теоремы !/. З.З конструктивна; она дает нам возможность аппроксимировать значения игровых элементов Гь достаточно эффективным способом. Если мы предположим, что игра будет продолжаться как стохастическая, пока мы не сыграем г раз, а затем необходимо заканчивается (если она уже не закончилась), то мы получим игру на разорение (усеченную игру), а не стохастическую игру.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
