Позиционные игры

Содержание

 

 

Введение

В какой-либо конфликтной ситуации решение принимается не одним индивидуумом, а несколькими участниками, и функция выигрыша каждого индивидуума зависит не только от его стратегии, но также и от решений других участников. Математическая модель такого рода называется игрой, а участники конфликта игроками.

Если игроков двое, а интересы их противоположны, то игра называется антагонистической.

На практике участники конфликтов часто совершают свой выбор не один раз и на всегда, а последовательно во времени, в зависимости от развития конфликта. Одним из классов игр, которые описывают конфликты, динамика которых влияет на поведение участников, являются позиционные игры.

 

§1. Необходимые сведения о матричных и антагонистических играх

1. Понятия антагонистической и матричной игр

Пусть функция определена на декартовом произведении , где — множества произвольной природы.

Определение 1. Пара называется седловой точкой функции на , если

 

или, эквивалентно,

 

Опишем антагонистическую игру. В ней принимают участие два игрока – 1 и 2. Игрок 1 выбирает стратегию из множества стратегий , игрок 2 выбирает стратегию из множества стратегий . Задана функция выигрыша первого игрока , определенная на . Выигрыш первого игрока является проигрышем для второго. Целью первого игрока является увеличение , а целью второго – уменьшение . Таким образом, антагонистическая игра задается набором .

Определение 2. Говорят, что антагонистическая игра имеет решение, если функция имеет на седловую точку. Пусть — седловая точка функции . Тогда тройка называется решением игры, — оптимальными стратегиями игроков, — значением (ценой) игры.

Так же называют ситуацией равновесия (равновесием по Нэшу) в игре Г.

Лемма 1. Если , — две седловые точки функции на , то , т.е. цена игры не зависит от выбора седловой точки.

Определение 3. Антагонистическая игра Г называется матричной, если множества стратегий игроков конечны: . При этом принято обозначать стратегию первого игрока через , стратегию второго через , а выигрыш первого через . Матрица называется матрицей игры. Первый игрок выбирает в ней номер строки , а второй — номер столбца .

В обозначениях матричной игры — седловая точка матрицы A, если

 

2. Принципы оптимальности в матричных играх

Определение 4. Стратегия первого игрока называется максиминной, если . При этом величина называется нижней ценой игры.

Определение 5. Стратегия второго игрока называется минимаксной, если . При этом величина называется верхней ценой игры.

Далее будем полагать, что множества конечны.

Обозначим , где – количество строк матрицы А игры Г, а – количество столбцов.

В обозначениях матричной игры и учитывая, что и , т.к. на функция достигает своего наименьшего и наибольшего значения, то определения 4 и 5 можно записать в следующем виде.

Определение 4. Стратегия первого игрока называется максиминной, если . При этом величина называется нижней ценой игры.

Определение 5. Стратегия второго игрока называется минимаксной, если . При этом величина называется верхней ценой игры.

Лемма 2. В любой антагонистической игре Г справедливо неравенство

 

Теорема 1.

1) Для того, чтобы имела седловую точку на , необходимо и достаточно, чтобы было выполнено равенство

 

2) Пусть выполнено  предыдущее равенство. Пара  является седловой точкой тогда и только тогда, когда – максиминная, а – минимаксная стратегии игроков.

Теорема .

1) Если – максиминная стратегия первого игрока, – минимаксная стратегия второго игрока игра Г имеет решение, – цена игры, – ситуация равновесия.

2) Если Г  имеет решение  – максиминная стратегия первого игрока, – минимаксная стратегия второго игрока.

3. Смешанное расширение игры

Так же теория игр предлагает использовать игрокам смешанные стратегии. Рассмотрим, как они определяются.

Определение 6. Смешанной стратегией первого игрока в игре Г называется вероятностное распределение на множестве стратегий .

Для первого игрока применить смешанную стратегию — это выбрать стратегию как реализацию случайной величины, имеющей закон распределения .

Рассмотрим вид смешанной стратегии, характерный для матричной игры.

Пусть . Тогда вместо для обозначения смешанной стратегии будем использовать “вероятностный” вектор удовлетворяющий ограничениям Если применяется , то стратегия выбирается с вероятностью .

Множество будем называть множеством чистых стратегий.

Обозначим множества “вероятностных” векторов для первого и второго игроков соответственно. Тогда функция выигрыша - , а соответствующая антагонистическая игра .

Определение 7. Антагонистическая игра называется смешанным расширением игры Г. – множества стратегий.

Для игры можно также ввести понятия максиминной и минимаксной стратегий, седловой точки функции , решения игры. С точностью до обозначений они будут аналогичны соответствующим понятиям для игры Г. Все свойства игры Г справедливы и для игры

Теорема 2. (основная теорема теории матричных игр).

Всякая игра имеет решение.

Последнее утверждение эквивалентно тому, что любая матричная игра Г имеет решение в смешанных стратегиях.

Теорема 3.

1) – решение

 

2) – ситуация равновесия в , при чем выполняются неравенства (1) – решение .

 

§2. Позиционные игры

1. Понятия позиционной игры, дерева игры и информационного множества

Определение 1. Позиционной игрой называется бескоалиционная игра, моделирующая процессы последовательного принятия решений игроками в условиях меняющейся во времени информации.

Простейшие примеры позиционных игр: шахматы, шашки, крестики-нолики, домино и др.

Определение 2. Состояния игры называют позициями, а возможные выборы в каждой позиции – альтернативами.

Определение 3. Древовидное упорядоченное множество, с помощью которого можно представить графически множество позиций в такой игре, называется деревом игры.

Для определенности будем рассматривать в этом параграфе, §3 и §4 позиционные игры, в каждой позиции которых ровно две альтернативы – 1 и 2.

Определение 4. Цепь, связывающая начальную вершину с окончательной называется партией.

Число различных партий равно числу окончательных вершин (позиций).

Различают позиционные игры с полной информацией и позиционные игры с неполной информацией.

В позиционных играх с полной информацией каждый игрок, делая свой ход, знает, в какой позиции дерева игры он находится в данный момент.

В позиционных играх с неполной информацией игрок, делающий ход, не знает точно в какой именно позиции дерева игры он фактически находится.

Определение 5. Информационным множеством называется некоторое множество позиций, известное игроку и включающее в себя его фактическую позицию.

Таким образом, в игре с неполной информацией игрок при своем ходе знает, в каком информационном множестве он находится, а в какой конкретно позиции этого множества – ему неизвестно.

2. Примеры

Пример 1. Дерево позиционной игры (жирным выделена одна из партий).

                                   Рис. 1.

 

§3. Позиционные антагонистические игры с полной информацией

1. Понятие позиционной игры с полной информацией

Определение 1. Позиционная игра называется игрой с полной информацией, если в каждой позиции любой ее партии игрок, делающий ход, знает, какие альтернативы были выбраны на предыдущих ходах.

Рассмотрим другое представление позиционной игры с полной информацией. Определим её следующим образом. Игра происходит в течение шагов с номерами На каждом шаге игроки по очереди выбирают альтернативы – значения переменных .

Шаг 1. Первый игрок выбирает альтернативу , затем второй игрок, зная выбор первого, выбирает альтернативу .

Пусть игроки в течение шагов выбирали альтернативы соответственно. Обозначим

Шаг t. Первый игрок, зная предыдущие значения , выбирает альтернативу . Далее второй игрок выбирает альтернативу , зная .

После последнего шага возникает пара – партия игры. Для любой партии задается выигрыш первого игрока.

2. Нормализация позиционной игры с полной информацией

Далее определим игру в нормальной форме. На шаге первый игрок может выбрать альтернативу как значение функции , которая должна быть определена при всевозможных значениях аргументов . Обозначим множество всех таких функций через . Заметим, что , так как на первом шаге первый игрок никакой информацией не располагает.

Стратегия первого игрока представляет собой набор функций

 

Аналогично, на шаге второй игрок может выбирать альтернативу как значение функции , которая должна быть определена при всевозможных значениях аргументов . Обозначим множество всех таких функций через . Стратегия второго игрока представляет собой набор функций

 

Любой паре стратегий однозначно соответствует партия игры: и т.д.

Далее , где — партия, соответствующая стратегиям . Многошаговая игра с полной информацией определена в нормальной форме .

Другими словами, нормализация – процесс сведения позиционной игры к матричной.

3. Теорема Цермело

Пусть - игра, в которой множества конечны.

Определим величину

 

Теорема 1 (Цермело).

Всякая многошаговая антагонистическая игра с полной информацией имеет решение в чистых стратегиях.

Доказательство.

Покажем, что функция имеет седловую точку на . Для того достаточно доказать, что

1. ;
2. .

Докажем неравенство 1). Имеем

 

Неравенство 2) доказывается аналогично.

4. Примеры

Пример 2. Рассмотрим игру с полной информацией. Начинает игрок А. Он выбирает одну из двух возможных альтернатив – число , равное либо 1, либо 2 (первая и вторая альтернатива соответственно). На ход игрока А игрок В отвечает своим ходом, также выбирая одну из двух альтернатив – число , равное либо 1, либо 2. В результате игрок А или выигрывает, или проигрывает.

1-й ход. Игрок А выбирает

2-й ход. Игрок В выбирает , зная выбор числа игроком А.

Функция выигрыша для игрока А задается следующим образом

 

На рисунке 2 показаны дерево игры и информационные множества.

                        Рис. 2                                                             Рис. 3

Пример 2 (продолжение). Нормализация игры.

В обозначениях, приведенных выше, , , , , , , .

Опишем стратегии игроков.

У игрока A две чистых стратеги, т.е. .У игрока В четыре чистых стратегии:

 

 

 

 

Покажем, как задается выигрыш игрока А.

Если, например, игрок А выбрал стратегию , а игрок B - -стратегию . Тогда . Остальные выигрыши рассчитываются аналогично. Запишем их в виде матрицы игры:

 

где строки соответствуют стратегиям игрока A, а столбцы – стратегиям игрока В.

Полученная матрица имеет седловую точку. Оптимальная стратегия первого игрока – выбрать , второго игрока - . Цена игры .

Пример 4. «Переговоры».

В переговорах участвуют две стороны A и B. Сначала сторона A высказывает одно из нескольких предложений, способных заинтересовать другую сторону. Затем сторона В, ознакомившись с предложением стороны А, высказывает одно из нескольких встречных предложений, способных, по ее мнению, заинтересовать сторону А. В свою очередь, сторона А, ознакомившись с реакцией стороны В на сделанные предложения, высказывает ей новое предложение, внеся одну из нескольких возможных корректировок в свое первоначальное предложение с учетом мнения стороны В и т. д.

Смоделируем короткий переговорный процесс трехходовой позиционной игрой с полной информацией.

Предположим, что переговоры заканчиваются через три хода, на каждом из которых соответствующая сторона имеет возможность выбора из двух альтернатив, и опишем соответствующую позиционную игру.

1-й ход делает сторона А. Она выбирает одно из двух возможных предложений – число .

2-й ход делает сторона B. Она выбирает число , зная число .

3-й ход делает сторона А. Она выбирает число зная .

После этого сторона А либо получает вознаграждение, либо выплачивает штраф стороне В.

Все эти возможности описываются функцией выигрышей , которая задана следующим образом

 

 

 

На рисунке 4 изображено дерево данной игры.

Опишем стратегии игроков.

Т.к. игроку В известен выбор игрока А на 1-м ходе, то у игрока В те же четыре стратегии, что и в предыдущем примере:

 

где означает, что если на первом ходе игрок А выбрал , то игрок В на своем ходе должен выбрать число , а если игрок А на первом ходе выбрал , то игрок В должен выбрать , т.е. при любом выборе и т. д.

У игрока А восемь возможных стратегий. Его чистая стратегия в данной игре описывается тройкой

 

Здесь – альтернатива, которую игрок А выбирает на 1-м ходе, – альтернатива, которую игрок А выбирает на 3-м ходе, если на втором ходе игрок В выбрал и – альтернатива, которую игрок А выбирает на 3-м ходе, если на втором ходе игрок В выбрал .

Опишем стратегии игрока А:

 

Далее покажем, как в зависимости от применяемых стратегий определяются элементы матрицы игры.

Пусть, например, игрок А выбрал стратегию , а игрок В – стратегию . Это означает, что на первом ходе игрок А выбрал , следовательно, игрок В на 2-м ходе выбрал а на 3-м ходе игрок А выбрал . Итак, . Тогда . Остальные выигрыши рассчитываются аналогично.

Теперь можем составить матрицу игры:

 

Вследствие того, что рассматриваемая позиционная игра является игрой с полной информацией, полученная матрица имеет седловую точку при любой функции выигрышей. 
§4. Позиционные антагонистические игры с неполной информацией