Теория игр. Оуэн (1971) (Теория игр. Оуэн (1971).djvu), страница 6

В конце игры игроки обычно получают какой-либо выигрыш (он может быть в форме денег, престижа или иного удовлетворения), который зависит от протекания игры. Его можно представить себе как функцию, которая каждой «окончательной позиции» игры ставит в соответствие определенный выигрыш. Е2.

ПОЗИЦИОННЫЕ ИГРЫ' В наше общее представление об игре входят, таким образом, три элемента: 1) чередование ходов, которые могут быть как личными, так и случайными, 2) возможная недостаточность информации и 3) функция выигрыша. ') В оригинале Кагпеа !п ех!епа!уе !опп, т. е. «игры а развернутой форне»,— .Прим. нерее. Гл. й Определение кери Определим прежде всего топологическое дерево, или дерево игры, как конечную совокупность узлов, называемых вершинами, соединенных линиями, называемыми ребрами, и притом так, что иолучается связная фигура, не содержащая простых замкнутых кривых. Отсюда следует, что для любых двух данных вершин А и В существует единственная последовательность ребер и вершин, соединяющая А с В.

Итак, мы получаем следующее определение. !.2А. Определение. Пусть à — топологическое дерево с выделенной вершиной А. Будем говорить, что вершина С следует за вершиной В, если последовательность ребер, соединяющая А. с С, проходит через В. Будем говорить, что С следует за В непосредственно, если С следует за В и, кроме того, существует ребро, соединяющее В с С. Вершина Х называется окончательной, если за Х не следует нн одной вершины. Б2.2. Определение. Под позиционной игрой и лиц пони.мается следующее: (а) топологическое дерево Г с выделенной вершиной А, называемой начальной позицией игры; ((») функция, называемая функцией выигрыша, которая ставит в соответствие каждой окончательной позиции (т.

е. окончательной вершине) дерева Г некоторый и-вектор; (у) разбиение множества всех неокончательных позиций (т. е. неокончательных вершин) дерева Г на и+ 1 множеств 5о, 5ь ... ..., 5„, называемых множествами очередности; (б) вероятностное' распределение для каждой позиции из 5а на множестве непосредственно следующих за ней позиций; (е) подразбиение множества 5; для каждого г = 1, ..., и на подмножества 5), называемые информационными множествами; при этом позиции из одного и того же информационного множества имеют одинаковое число непосредственно следующих за ними позиций, т. е.

альтернатив, и никакая позиция не может следовать за другой позицией из того же самого информационного множества; (~) для каждого информационного множества 5гг множество индексов т') вместе с взаимно однозначными отображениями множества т,' на множества альтернатив каждой позиции из 5гг Мы будем обозначать игру также через Г. Здесь перечислены все элементы игры: условие (и) устанавливает, что имеется начальная позиция; (В) задает функцию выигрыша; (у) разделяет множество неокончательных позиций на позиции с ходом случая (5з» и личные позиции, соответствующие каждому из п игроков: (5ь ..., 5 ) '); (Ь) задает схему раидоми- ') В позиции из З~ очередь хода прииадаежит игроку С вЂ” Прим.

иерее. й 2, Позиционные игры зации в каждой позиции случая; (и) разбивает позиции каждогсь игрока на «информационные множества»: игрок знает лишм в каком информационном множестве он находится, но ие знает, в какой именно позиции этого множества '). 1.2.3. Пример. В игре в орлянку ('рис. 1.2.1) игрок 1 выбирает «решетку» (Р) или «герб» (Г). Игрок П, не зная выбора игрока 1, также выбирает «решетку» или «герб». Если оба (-(,у) противника совершают одинаковый выбор, то игрок П выигрывает единицу у игрока 1; Р Г р и противном случае игрок 1 выигрывает единицу у игрока П.

На дереве игры (рис. 1.2.1) векторы при окончатель- Г Р ных позициях представляют функцию выигрыша; число при каждой из остальных позиций д1 означает игрока, которому Рис. ййдь принадлежит очередь хода в этой позиции. Затененная область охватывает позиции из одного ннформационного множества. 1.2.4.

Пример. Каждому из двух игроков сдается полная масть карт (трннадцать карт). Третья масть тасуется, и затем карты этой третьей масти открываются одна за другой. Каждык раз, когда карта открыта, оба игрока по своему желанию открывают одновременно какую-то одну из своих карт; тот, кто открыл старшую карту, «выигрывает» третью. (Если оба игрока открыли карты одинакового достоинства, никто не выигрывает.) Так продолжается до тех пор, пока все три масти не будут исчерпаны После этого каждый игрок подсчитывает количество очков на каргах, которые он «выиграл»; «счет» ведется по разности выигрышей игроков. В случае тринадцати карт каждой масти дерево такой игры слишком велико для того, чтобы его можно было привести здесь Мы изобразили лишь часть дерева для аналогичной игры с мастями из трех карт (рис. 1.

2.2). В этой игре есть один случайный ход, тасование, упорядочиваю1цее карты одним из шести возможных способов, каждый из коуорых имеет вероятность '/з. После этого ходы соответствуют двум ') (С) вводит одинаковые индексы на множествах альтернатив всех позиций Мз одного информационного множества; тем самым каждый индекс определяет 1 о одной альтернативе в каждой позиции данного информационного множества. од переводит игру нз некоторой позиции в какую.то ее альтернативу. †Пр. Верее. Гл, г Определение игра игрокам 1 и П, пока игра не кончится.

Мы изобразили часть дерева игры, содержащую начальную позицию, несколько ветвей и четыре окончательные позиции. Остальные ветви подобны изображенным. 5!2 Я(0) Р и с. б 2.2. По поводу информации сформулируем следующее определение. !.2.5. Определение. Говорят, что игрок ! имеет полную информацию в игре Г или что Г есть игра с полной информацией для игрока г, если каждое его информационное множество 'Зг со- 1 стоит из одного злемента. Говорят, что Г есть игра с полной информацией, если в Г каждый игрок имеет полную информацию.

Например, шахматы и шашки — это игры с полной информацией, а бридж и покер — нет. 7,8. Стратегии. Нормальная форма игры Ь З„СТРАТЕГИИ. НОРМАЛЬНАЯ ФОРМА ИГРЫ В интуитивном понимании стратегия есть некоторый план разыгрывания игры. Можно считать, что игрок говорит себе:«Если случится то-то и то-то, то я буду действовать так-то и так-то», Приведем точное определение.

!.3.1. Определение. Стратегия игрока 1 есть некоторая функция, которая ставит в соответствие каждому информационному множеству 5г этого игрока некоторый индекс из )р Множество всех стратегий игрока ( мы будем обозначать через Хь Вообще говоря, мы привыкли к тому, что игрок принимает решение о своем ходе в игре только на несколько ходов вперед, а обычно — даже только в тот момент, когда он должен сделать данный ход. На практике это так и должно быть ввиду того, что в таких играх, как шахматы или покер, число возможных ходов настолько велико, что нельзя заранее запланировать свои действия, учитывая все возможные обстоятельства.

Однако с чисто теоретической точки зрения можно абстрагироваться от такого практического ограничения и предполагать, что уже до начала игры каждый игрок решил, что он будет делать в каждом случае. Таким образом, фактически мы предполагаем, что каждый игрок выбирает некоторую стратегию еще до начала игры. Поскольку это так, остается лишь произвести случайные ходы. Более того, все случайные ходы можно объединить в один ход, результат которого вместе с выбранными стратегиями определяет исход игры'). В действительности нас, так же как и участников игры, интересует, какие из стратегий являются наилучшими с точки зрения максимизации доли каждого игрока в выигрыше (а именно, игрок 7 стремится максимизировать 1-ю компоненту функции выигрыша), Так как, однако, результаты случайных ходов известны только в вероятностном смысле, естественно рассматривать математическое ожидание функции выигрыша, определенное в случае, когда игроки используют данный и-набор стратегий, т.