Теория игр. Оуэн (1971) (1186151), страница 21
Текст из файла (страница 21)
Значение игры равно нулю. г) Пусть Р(х) — любая оптимальная стратегия игрока 1. Функния Е(р,у)— аналитическая функция от у. Следовательно, либо оиа равна нулю иа всем интервале (0,1), либо имеет на нем лишь конечное число нулей. е) Если Е(Р, у) не обращается в нуль на всем интервале [О, 1), то С(р) не может быть оптимальной стратегией игрока П. ж) Тот факт, что Е(р,у) 0 на всем интервале (0,1) для любой оптимальной стратегии Р, позволяет нам вычислить ее моменты Ры( Следовательно, две любые оптимальные стратегии имеют одинаковые моменты.
(По известной теореме это означает, что любые две оптимальные стратегии идентичны.) Поэтому С вЂ” единственная оптимальная стратегия. Глава У МНОГОШАГОВЫЕ ИГРЫ У. $. СТРАТЕГИИ ПОВЕДЕНИЯ Рассмотрим многоходовую игру. Это может быть весьма простая игра, например «крестики и нолики», столь простая, что научиться играть в нее может даже ребенок. Предположим, однако, что мы хотим сосчитать число стратегий первого йгрока. Заметим (пренебрегая симметрией), что на первом коде он имеет девять альтернатив.
Далее для любого из восьми возможных ответов иа своем втором ходе у него будет семь альтернатив. Если мы рассмотрим только первые два хода первого игрока, то мы найдем, что у него 9 7' = 51883209 чистых стратегий. Естественно„ни о какой попытке перечислить их не может быть и речи. Даже если мы учтем симметрию, то увидим, что число чистых стратегий в этой игре астрономическое. А ведь эта игра чрезвычайно проста (в прак. тическом смысле слова в противоположность шахматам, которые тоже просты в теоретико-игровом смысле, но практически весьма сложны).
Таким образом, ясно, что чистые стратегии оставляют желать много лучшего. Вспомним определение чистой стратегии: это функция, определенная на совокупности информационных множеств одного игрока н приписывающая каждому информационному множеству число между 1 и й (где й — число альтернатив в данном информационном множестве). Таким образом, если у игрока М информационных множеств и в каждом из них й альтернатив, то общее число чистых стратегий равно Й", а это число может быть очень большим. Возвращаясь к примеру с «крестиками и ноликами», мы видим, что никто не играет в эту игру, фактически рассматривая все возможные чистые стратегии (т. е. все возможные последовательности ходов с первого до последнего), Скорее, в нее играют, рассматривая на каждом ходе все возможные альтернативы только для этого хода и выбирая из них наилучшую (исходя из собственного опыта или как-либо иначе), Итак, сущность упрощения состоит в том, чтобы рассматривать ходы по одному за раз.
Этот прием сводит один выбор из Й1йэ ... Й„возможных стратегий к й( выборам из й, возможных альтернатив в каждом информационном множестве. Это приводит к следующему определению. 112 Гл. 1г. Многошоговае игра Ч.1.1. Определение. Сграгегиеа поведения называется набор гЧ вероятностных распределений, каждое из которых задано на множестве возможных альтернатив в каждом информационном множестве.
Ч.1.2. Пример. Игроку сдается карта из колоды в 52 карты; посмотрев на свою карту, он может либо спасовать, либо поставить некоторую фиксированную величину. Общее число чистых стратегий равно 2"; следовательно, множество смешанных стратегий будет иметь размерность 2м — 1. С другой стороны, стратегия поведения приписывает каждой карте вероятность того, что игрок поставит (т.
е. число между О и 1). Таким образом, размерность множества стратегий поведения равна 52, Итак, множество стратегий поведения имеет, вообще говоря, гораздо меньшую размерность, чем множество смешанных страте- гий. С другой стороны, необхо- 2 3 4 1 1 5 6 О димо заметить что при некоторых условиях не все смешанные стратегии можно получить, используя стратегии, поведения, как показы- П вает следующий пример. ЧЛ.З. П р имер.
В игре, де- 1 рево которой изображено на Я г"г рис. Ч.!.1, мы можем обозначить чистые стратегии игрока П че- П рез ЛЛ, ЛП, ПЛ, ПП. Смешан- ная стратегия есть вектор (хь хь Рис. Ч.1.1, хг, хг), удовлетворяющий обыч- ным ограничениям; стратегия поведения есть пара чисел (уь уз), удовлетворяющая лишь условиям О ~ уг ~ 1. Стратегии поведения (уь !гг) соответствует смешанная стратегия (у~ум рг (1 — уг) (1 — у~) уз (1 — у~) (1 — Пг) ). (5.1.1) Далее, оптимальная стратегия игрока П есть вектор (О, г/и з)пО) (см. пример 11.5.9).
Ясно,что он не может быть представлен в виде (5.1.1). Следовательно, зта игра не имеет решения в стратегиях поведения. Трудность с примером Ч.1.3 в некотором смысле состоит в том, что игрок П на своем втором ходе не знает, что он делал на своем первом ходе. Говорят, что такая игра имеет неполную память. Эта трудность усложняет положение: нет уверенности, допускаются ли все смешанные стратегии. В бридже два партнера рассматриваются как один игрок, который «забывает» некоторые из своих предыдущих выборов, Так как секретные соглашения запрещены, партнер не может знать, было ли предложение, сделанное его партне- !13 Е 2.
Игры на разорение ром, честным или оно было рассчитано на психологический эффект, хотя он может знать вероятность такого «психологического» предложения. Мы не будем вдаваться здесь в эти трудности. Тип игр, которые мы собираемся изучать, весьма близок к играм с полной информацией: после заданного числа ходов оба игрока (одновременно) получают полную информацию (которая не забывается), так что в некотором смысле игру можно начинать снова из данной позиции. Общая схема игры будет такова: первым ходит игрок 1, затем игрок П (не зная предыдущего хода игрока 1); далее производится случайный ход, после чего оба игрока получают полную информацию. (Эта общая схема может меняться, но лишь незначительно.) Каждый из этих циклов будет называться шагозг игры. Ч,2.
ИГРЫ НА РАЗОРЕНИЕ Теперь мы будем рассматривать игры такого типа, в которых каждый игрок начинает игру, имея некоторые ограниченные ресурсы, На каждом шаге игры ресурсы одного из игроков уменьшаются на единицу. Выигравшим считается тот, кто истощит ресурсы своего противника (разорит его).
Возможно также, что на каждом шаге игрок может выиграть очко; тогда выигравшим будет тот, кто первым наберет фиксированное число очков. Ясно, что в первом случае общая величина ресурсов обоих игроков уменьшается на единицу; во втором случае общее число очков возрастает на единицу, Следовательно, эти игры всегда будут заканчиваться после некоторого фиксированного числа ходов. Целесообразно решать эти игры, двигаясь «от конца к началу».
Общая идея состоит в том, что каждый шаг можно рассматривать как отдельную игру. После того как стратегии для этого шага выбраны, выигрыш определяется либо как обычный выигрыш (если многошаговая игра закончена), либо как обязательство разыгрывать следующий шаг игры. Так как обычно мы имеем дело с математическими ожиданиями, мы можем заменить обязательство разыгрывать игру значением этой отдельной игры. У.2.1. Пример. Рассмотрим игру с матрицей (5.2.1) где элементы Г, и Гз представляют собой обязательство разыграть соответственно две другие игры с матрицами (5.2.2) Гл.
У. Многошаговые игра И4 Если значения игр Г~ и Гз равны соответственно о~ и оь то в смысле математических ожиданий перспектива играть вэти игры эквивалентна их значениям. Поэтому матрицу (5.2.1) мы можем заменить матрицей (5.2.3) Теперь можно решить игру с матрицей (5.2.3); решение даст нам оптимальные стратегии и значение игры (5.2.1). Таким образом, для игр на разорение мы начнем с нахождения решений во всех играх, в которых оба игрока начинают, имея лишь одну единицу ресурсов. Так как такая игра должна закончиться только за один шаг, ее можно решить непосредственно. Используя значение этой игры, мы можем затем решить все игры, в которых общая величина ресурсов обоих игроков составляет три единицы. Эти решения дадут нам возможность решить игры с величиной ресурсов в четыре единицы, затем в пять и т. д. Вообще говоря, для игр с небольшим количеством ресурсов (т.
е. для игр, которые должны закончиться после небольшого числа шагов) значение и оптимальные стратегии можно найти непосредственно. В играх с большим числом шагов для значения на каждом шаге можно вывести рекуррентное соотношение. Это рекуррентное соотношение обычно имеет вид разностного уравнения, которое может легко поддаваться решению, а может и не поддаваться ему. Если удастся решить это разностное уравнение, то значения игр для каждого шага можно использовать для нахождения оптимальных стратегий. Если разностные уравнения решить нельзя, то тем не менее может оказаться возможным получить разумные приближения к значениям игр и оптимальным стратегиям, У.2.2.
П р и м е р (игра инспектирования). Игрок 1 (нарушитель) хочет совершить некоторое запрещенное действие; имеется й! периодов времени, в которые это действие может быть осуществлено. Игрок П (инспектор), желающий предотвратить это действие, может провести только одну инспекцию в любой из этих периодов времени. Выигрыш равен 1, если запрещенное действие проводится и остается необнаруженным; он равен — 1, если нарушитель пойман (это будет в том случае, когда для совершения действия он выбирает тот же самый период времени, что и инспектор для проверки); выигрыш равен нулю, если нарушитель не действует вовсе.
В первом периоде (на первом шаге) игры каждый игрок имеет две альтернативы. Игрок 1 может предпринимать действие или, не предпринимать его; игрок 11 может инспектировать или не инспектировать. Если игрок 1 действует и игрок !! инспектирует, то игра заканчивается и выигрыш равен — 1. Если игрок 1 действует, а иг- К2. Игры но разорение рок П не инспектирует, то игра заканчивается и выигрыш равен 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
