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

Содержание

игра матричный позиционный равновесие

Введение

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

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

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

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

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

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

.2 Примеры

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

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

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

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

3.4 Примеры

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

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

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

4.3 Примеры

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

.1 Понятие биматричной игры

.2 Принцип максимина и принцип равновесия. Оптимальность по Парето

. Позиционная неантагонистическая игра. Ее свойства

Заключение

Список литературы

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 1.

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

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

Теорема .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 3.

)  - решение

)  - ситуация равновесия в , при чем выполняются неравенства (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. В результате игрок А или выигрывает, или проигрывает.

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

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

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

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

Рис. 2, 3

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

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

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

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

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

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

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

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

Пример 4. "Переговоры".

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

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

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

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

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

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

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

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

Рис. 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть дана игра .

Пусть  - множество всех отрезков партий вида  (вида ). Предположим, что множество  разбито на непересекающиеся подмножества . Перед выбором  первому игроку известно, что . Аналогично, пусть множество  разбито на непересекающиеся подмножества . Перед выбором  второму игроку известно, что . Если, в частности, , , а множества  и  содержат по одному элементу  и  соответственно, то получим игру с полной информацией.

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

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

4.3 Примеры

Пример 5. Рассмотрим позиционную игру с неполной информацией.

-й ход делает игрок А: он выбирает число .

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

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

Функция выигрыша игрока А :

Графическое представление этой игры показано на рисунке 5.

Рис. 5

Нормализуем эту игру.

Стратегии игрока А:

У игрока В всего две стратегии:

В этом случае матрица игры будет иметь вид:

Оптимальные смешанные стратегии игроков и цена игры соответственно равны

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

.1 Понятие биматричной игры

Введем понятие биматричной игры.

Пусть - множество стратегий первого и второго игроков соответственно. При выборе первым игроком стратегии , а вторым , возникает ситуация . Выигрыш первого игрока в этой ситуации - , второго - .

Данную игру можно полностью описать, если задать две матрицы:

Определение 1. Биматричной игрой называется совокупность , где , .

.2 Принцип максимина и принцип равновесия. Оптимальность по Парето

Обозначим

Определение 2. Числа  называются максиминными ценами первого и второго игроков;  - максиминные стратегии первого и второго игроков,  - максиминннная цена игры.

Определение 4. Ситуация  называется ситуацией равновесия (равновесием по Нэшу) в биматричной игре, если

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

Определение 6. Стратегия , входящая в какую либо ситуацию равновесия, называется равновесной стратегией первого игрока.

Определение 7. Стратегия , входящая в какую либо ситуацию равновесия, называется равновесной стратегией второго игрока.

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

Теорема 1.

1)     - максиминная цена биматричной игры.

2)     - равновесная цена биматричной игры, соответствующая ситуации равновесия .

.

Из определения 4 следует, что для нахождения ситуации равновесия и равновесной цены игры можно применить следующий способ:

)        В каждом столбце матрицы  выделить наибольший элемент.

)        В каждой строке матрицы  выделить наибольший элемент.

)        Общие выделенные элементы будут образовывать ситуации равновесия.

Определение 9. Пара стратегий  и соответствующий исход игры являются оптимальными по Парето, если не существует другого исхода (пары стратегий) игры, который увеличил бы выигрыш одного из игроков, при этом не уменьшив выигрыш другого.

6. Позиционная неантагонистическая игра. Ее свойства

Рассмотрим другой метод для решения позиционных игр. Он основан на понятии совершенства по подиграм.

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

Определение 2. Равновесие по Нэшу в позиционной игре называется совершенным по подиграм, если оно остается равновесием по Нэшу при его ограничении на каждую подигру.

Пример 6. "Семейный спор".

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

Стратегии мужа:

Стратегии жены аналогичны.

Заданы матрицы выигрышей мужа и жены соответственно:

Рассмотрим динамический вариант этой игры.

Предположим, что игроки не делают ходов одновременно, но муж делает первый выбор, а жена принимает решение, зная выбор мужа. Дерево такой игры имеет вид:

Рис. 6

Логика обратной индукции ведет к следующему решению. Муж может сообразить, что если он выберет футбол, то его жена тоже выберет футбол (т.к. такой выбор обеспечит ей наилучшую выплату 2), что окончательно приведет их к платежам . С другой стороны, если муж выберет балет, то его жена также выберет балет, что приведет к платежам . С точки зрения мужа,  лучше, чем , и, следовательно, на своем первом ходе ему разумно выбрать футбол.

Представим эту игру в нормальной форме.

Стратегии мужа:

Стратегии жены:

Первая буква в стратегиях жены означает реакцию на выбор мужем ф (футбол), а вторая означает реакцию на выбор мужем б (балет).

Получаем матрицы выигрышей мужа и жены:

В данной игре три равновесия по Нэшу:

Соответствующие равновесные цены:

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

Пример 7. "Мудрость царя Соломона".

Всем известна библейская история про то, как Соломон восстановил справедливость: установил, чей на самом деле ребенок.

Глазер и Ма предложили эффективный способ поиска истины в данной ситуации. Чтобы он сработал, нужна лишь грубая численная прикидка значений  полезности для женщин получить своего или чужого ребенка соответственно (индексы  происходят от английских слов true и false). Естественно, . Тогда женщинам следует предложить сыграть при свидетелях в следующую игру.

Шаг 1. Первую женщину спрашивают: "Это твой ребенок?" Если ее ответ "нет", ребенка отдают второй женщине, и игра завершается.

Шаг 2. Если же последует ответ "да", то затем тот же вопрос задают второй женщине: "Это твой ребенок?" Если ее ответ "нет", ребенка отдают первой женщине, и игра заканчивается. Если же следует ответ "да", то ребенка отдают второй женщине, но они обе получают наказание. Размер наказания для второй женщины составляет величину , а для первой женщины - величину , причем  выбираются так, чтобы выполнялось неравенство .

Если первая женщина на самом деле мать, ход игры можно описать графически следующим деревом игры:

Рис. 7

Здесь первое число в скобках означает выплату первой женщине, а второе - второй. Если же вторая женщина - настоящая мать, течение игры может быть описано графически с помощью такого дерева игры:

Рис. 8

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

Стратегии первой женщины:

Стратегии второй женщины аналогичны.

Составим матрицы  выигрышей двух женщин соответственно, .

В данной игре две ситуации равновесия:  Отметим, что эти ситуации равновесия являются также оптимальными по Парето.

Рассмотрим другой способ. Опишем логику обратной индукции. Начиная с последнего шага, когда вторая женщина принимает решение, видно, что для нее сказать "да" (т.е. солгать) означает отрицательный платеж , который хуже, чем сказать "нет" и не получить ничего. Таким образом, логичным ответом второй женщины будет "нет" (т.е. правда), что приводит к передаче ребенка первой женщине (его настоящей матери). Рассмотрим теперь первый шаг, на котором первая женщина делает свой выбор. Подчиняясь здравому смыслу, она может решить, что если она скажет "да", то ее соперница ответит "нет" и, следовательно, она получит , что лучше, чем не получить ничего, сказав "нет". Следовательно, ответы (да, нет) являются решением этой игры в данной ситуации, выплата составит , и настоящая мать получит своего ребенка.

Аналогичными рассуждениями можно показать, что и во втором случае ребенок попадет к настоящей матери.

Пример 8. Игра "Ультиматум".

Руслану и Светлане предложили сыграть в следующую игру. Аукционер дает три доллара Руслану, а он должен разделить эту сумму со Светланой по своему усмотрению, предложив ей любое целое число долларов (то есть 1, 2, 3). Если Светлана согласится принять его предложение, то остаток остается у Руслана. Если Светлана откажется от его предложения, то все 3 доллара возвращаются к аукционеру.

Опишем стратегии Руслана (Р) и Светланы (С).

У Руслана в этой игре три стратегии:

Дерево игры будет иметь вид:

Рис. 9

В скобках первое число - выигрыш Руслана, второе - Светланы.

Составим матрицы выигрышей Руслана и Светланы:

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

Отметим, что только одно равновесие в данной игре совершенно по подиграм, а именно .

Заключение

В данной работе был рассмотрен широкий класс игр - позиционные игры.

Первый параграф включает в себя основные понятия и теоремы о матричных и антагонистических играх.

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

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

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

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

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

Список литературы

1.      Васин А.А., Морозов В.В. "Введение в теорию игр с приложениями в экономике" (учебное пособие). - М.: МГУ им. М.В. Ломоносова, 2003.

.        Краснов М.Л., Киселев А.И., Макаренко Г.И., Шикин Е.В., Заляпин В.И., Соболев С.К. Вся высшая математика: Учебник. Т. 5. - М.: Эдиториал УРСС, 2001.

.        В. Н. Колокольцов, О. А. Малафеев. Математическое моделирование многоагентных систем конкуренции и кооперации (Теория игр для всех): Учебное пособие. - СПб.: "Лань", 2012.