Теория игр. Оуэн (1971) (1186151), страница 7
Текст из файла (страница 7)
е. данную ситуацию. Поэтому для описания математического ожидания функции выигрыша при условии, что игрок 7 применяет стратегию еч е- =Хь можно употребить следующее обозначение: п(оь пт . о )=(п1(пь и )* "2(.. ) и (и! . о )) Исходя из этого, функцию я(пь ..., о,) на множестве всех возможных значений переменных оь ..., па можно выразить либо Ч Иными словами, определяется последовательность ребер н вершин от начальной познани до некоторой окончательной позинни, т. е. определяется партия и выигрыш в аей. — 77рим.
нерее. Гм д Онределемие иерее ЗО в форме соотношения, либо в виде и-мерной таблицы п-векторов. (В случае н = 2 эта запись сводится к матрице, элементами которой являются пары вещественных чисел.) Такая и-мерная таблица называется нормальной формой игры Г. 1.3.2. Пример. В игре в орлянку (см. пример 1.2.3) каждый игрок имеет две стратегии: «решетку» и «герб». Нормальной формой этой игры является матрица Р Г (здесь каждая строка представляет стратегию игрока 1, а каждый столбец — стратегию игрока П). 1.3.3. П р и мер. Рассмотрим следующую игру.
Случайно выбирается целое число г с возможными значениями 1, 2, 3, 4 (каждое имеет вероятность 1/4). Игрок 1, не зная результата этого хода, выбирает целое число х. Игрок 11, не зная ни результата случайного хода, ни выбора игрока 1, выбирает целое число у. Выигрыш определяется следующим образом: () у — г ! — ~ х — г 1, 1х — г 1 — 1у — г )), т. е. целью является выбор числа, по возможности близкого к г.
В этой игре каждый игрок имеет четыре стратегии: 1, 2, 3, 4, так как от других целых чисел мало проку, Если, например, игрок 1 выбирает 1, а игрок П выбирает 3, то выигрыш будет равен (2,— 2) с вероятностью 1/4, (0,0) с вероятностью 1/4 и ( — 2,2) с вероятностью !/2. Ожидаемый выигрыш тогда равен п(1,3) = ( — 1/2, 1/2). Подсчитывая все значения п(егп ае), мы получаем такую таблицу: 1 2 3 4 1.3.4. Определен и е.
Игра называется конечной, если ее дерево содержит только конечное число вершин. В этом смысле большинство салонных игр оказывается конеч- ным, Шахматы, например, являются конечной игрой в силу того А 4. Ситуации равиовесиз правила, что игра прекращается после некоторык последовательностей ходов. Следует отметить, что в конечной игре каждый игрок имеет лишь конечное число стратегий. 1.
4. СИТУАЦИИ РАВИОВЕСИЯ !.4.1. Определение. Пусть дана игра Г; говорят, что ситуация (т. е. и-набор стратегий) (ор а", ..., о'„) равновесна, или что она является ситуацией равновесия, если для любого 1= 1, ..., л и для любого о, ~ Х, имеет место неравенство п~(вр ° ° ° в~ р ор о~+р ° ° в„) ~ п~ (вр ° ° ° в„) Другими словами, ситуация равновесна, если ни один игрок не имеет никаких разумных оснований для изменения своей стратегии при условии, что все остальные 'игроки собираются придерживаться своих стратегий.
В этом случае, если каждый игрок знает, как будут играть остальные, он имеет основание придерживаться той стратегии, которая соответствует этой ситуации равновесия; тем самым игра становится весьма устойчивой. 1.4.2. Пример. Для игры в нормальной форме а, (2, 1) ~ (О, 0) а, (О, 0) ! (1, 2) как (аь (Зю), так и (аь рз) являются ситуациями равновесия. К сожалению, не каждая игра обладает ситуациями равновесия. Например, игра в орлянку (пример 1.3.2) такой ситуации не имеет.
Вообще, если игра не-имеет ситуаций равновесия, то обычно некоторые игроки пытаются отгадать стратегии остальных участников, сохраняя собственные стратегии в тайне. Это наводит на мысль (и это действительно верно), что в играх с полной информацией ситуации равновесия существуют. Чтобы доказать это утверждение, мы должны изучить вопрос о разложении игры. Будем говорить, что игра Г разложима в некоторой позиции Х, если не существует информационных множеств, которые содержали бы позиции из следующих двух множеств одновременно: а) Х и все следующие за ней позиции, б) остальные позиции деева игры. В этом случае мы можем выделить подигру Гх, сооящую из Хи всех следующих за ней позиций, и факторигру Г/Х, Гл.
1 Определенгге игры состоящую нз всех оставшихся позиций плюс Х, т. е. разложить игру Г. Для факторигры позиция Х будет окончательной; в качестве выигрыша здесь можно рассматривать Г», т. е. выигрышем в этой позиции является партия ') подигры Г». Далее, как мы видели, стратегия для игрока г' — это функция, область определения которой состоит из информационных множеств этого игрока. Если мы разложим игру в Х, то сможем также разложить стратегию о на две части: на о,, являющуюся ограничением о информационными множествами нз Г/Х, и на о г, являющуюся ограничением о информационными множествами йз Г».
Обратно, стратегия для Г/Х и стратегия для Г» могут быть объединены очевидным образом в стратегию для всей игры Г. а.4.3. Теорема. Пусть Г разложена в Х, Для о;а=Хт поставим в соответствие позиции Х (рассматриваемой как окончательная позиция для Г/Х) выигрыш ях(огггх, оа~г»,, о ~гх). В этом случае п(ог, ., о )=пггх(оггггх,, о, ~ггх). Доказательство этой теоремы несложно и может быть предоставлено читателю в качестве упражнения.
Коротко говоря, необходимо только проверить, что для каждого возможного исхода случайных ходов в конечном счете достигается одна и та же окончательная вершина как для исходной игры, так н для разложенной игры. На основании этого мы можем доказать следующее утверждение. а.4.4. Теорема. Пусть Г разложена в Х, и пусть огенХг таковы, что а) (оггг»,, ои~г ) есть ситуация равновесия для Г„ и б) (о,,г,, ..., о„~гг ) есть ситуация равновесия для Г/Х с выигрьгшем п(ог г гх,,„о„! г ), сопоставленным окончательной позиции Х. Тогда (ог, ..., ое) есть ситуация равновесия для Г.
Доказательство. Пусть огенХг. Так как (ога с, ..., о„~г») является ситуацией равновесия для Г», мы имеем пг(пг ниг», ° °, от~ г», ..., о„Ггх) ~ п,(пг ни г», ..., ои~гх). С другой стороны, в силу б) мы знаем, что если позиции Х приписан выигрыш и (ог ~ гх, °, ои ~ г»), то пг(ог!ггх, ..., ог~ггх.....
ое|ггх) ~ пг(выггх... о„! ггх). г) См. примечание на стр. 29 н последующее рассуждение.— Прим. нерее. Задачи зз Далее, выигрыш (в данной ситуации) есть взвешенное среднее выигрышей в некоторых из окончательных позиций дерева. Следовательно, если выигрыш игрока 1 в данной окончательной позиции (Х в нашем случае) уменьшается, то его ожидаемый выигрыш при любом выборе стратегий будет либо оставаться тем же, либо уменьшится. Поэтому, применяя теорему 1. 4.3, мы получаем неравенство Пг(ОЬ ..., и„..., Оя)~П!(ао ..., О„), так что (оь ..., о ) является ситуацией равновесия.
Теперь мы можем доказать следующий результат, 1.4.5. Теор е м а. Любая конечная игра и лиц с полной ингрормацией имеет ситуацию равновесия. До к а з а т е л ь с т в о. Определим длину игры как наибольшее возможное число ребер, которые можно пройти прежде, чем попасть в окончательную позицию, т. е. наибольшее возможное число ходов до конца игры. Очевидно, что конечная игра имеет конечную длину.
Доказательство проводится индукцией по длине игры. Если Г имеет длину О, теорема тривиальным образом справедлива. Если Г имеет длину 1, то не более чем один игрок имеет возможность сделать ход и он добивается равновесия, выбирая свою наилучшую альтернативу. Если игра Г имеет длину пг, то она разлагается (ввиду того, что информация полная) на несколько подигр длины, меньшей гп. По предположению индукции каждая из этих подигр имеет ситуацию равновесия; на основании теоремы 1.4.4 они образуют ситуацию равновесия для игры Г.
Заданы 1. Бесконечная игра, даже с полной информацией, не обязательно имеет ситуацию равновесия. а) Рассмотрим игру двух лнц, в которой игроки ходят поочередно и прн каждом ходе каждый игрок выбирает одну из двух цифр 0 и 1. Если при Ьм ходе выбирается цифра хь то каждой партии игры соответствует число х=~и', хг2 г 1 нз интервала [О, 1]. тогда игрок 1 выигрывает единицу у игрока П, если х ~а 8, и проигрывает единицу, если х~Я, где 5 — некоторое подмножество из [0,1]. б) Каждый игрок имеет ровно 2ю стратегий, которые можно обозначить, таким образом, соответственно через ор, тб для р < а, где а — наименьшее порядковое число, которому предшествует по крайней мере 2"' порядковых чисел, в) Пусть (о,т) означает партию (или число х), получающуюся, если игроки выберут стратегии о и т соответственно.
Для каждой стратегии и игрока 1 игрок П имеет 2"' стратегий т, которые дадут различные значения для (о,т). (Аналогично обстоит дело для каждой стратегии т игрока П.) 2 Зак. аю Гл. 1. Определение игры г) Можно построить (с использованием аксиомы выбора) такое множество 8, что для каждого ор существует тр с (ор, тр) ~5, а для каждого тт существует оч с (о, т ) гни. 0,0, (9,-6,01 Р и с, 1. ЗЛ. 2. Построить нормальную форму для игры с деревом, изображенным на рис. 1. 3.!. Игра начинается а позиции О (позиция случая); каждый из трех игроков имеет по одному информационному множеству с двумя познцнямя и с дву.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
