Автор работы: Пользователь скрыл имя, 15 Октября 2014 в 21:54, курсовая работа
В какой-либо конфликтной ситуации решение принимается не одним индивидуумом, а несколькими участниками, и функция выигрыша каждого индивидуума зависит не только от его стратегии, но также и от решений других участников. Математическая модель такого рода называется игрой, а участники конфликта игроками.
Если игроков двое, а интересы их противоположны, то игра называется антагонистической.
Введение 3
§1. Необходимые сведения о матричных и антагонистических играх 4
1. Понятия антагонистической и матричной игр 4
2. Принципы оптимальности в матричных играх 5
3. Смешанное расширение игры 6
§2. Позиционные игры 9
1. Понятия позиционной игры, дерева игры и информационного множества 9
2. Примеры 10
§3. Позиционные антагонистические игры с полной информацией 11
1. Понятие позиционной игры с полной информацией 11
2. Нормализация позиционной игры с полной информацией 11
3. Теорема Цермело 12
4. Примеры 13
§4. Позиционные антагонистические игры с неполнойинформацией 19
1. Понятие позиционной игры с неполной информацией 19
2. Нормализация позиционной игры с неполной информацией 19
3. Примеры 19
§5. Необходимые сведения о биматричных играх 22
1. Понятие биматричной игры 22
2. Принцип максимина и принцип равновесия. Оптимальность по Парето 22
§6. Позиционная не антагонистическая игра. Ее свойства 25
Заключение 33
Список литературы 34
Определим модель многошаговой игры, в процессе которой игроки могут не иметь полной информации о сделанных выборах.
Пусть дана игра .
Пусть — множество всех отрезков партий вида (вида ). Предположим, что множество разбито на непересекающиеся подмножества . Перед выбором первому игроку известно, что . Аналогично, пусть множество разбито на непересекающиеся подмножества . Перед выбором второму игроку известно, что . Если, в частности, , , а множества и содержат по одному элементу и соответственно, то получим игру с полной информацией.
Стратегия первого игрока задается набором функций от , принимающих значения . Стратегия второго игрока задается набором функций от , принимающих значения . По определению , где партия игры однозначно задается стратегиями игроков и . Итак, определена игра в нормальной форме.
Пример 5. Рассмотрим позиционную игру с неполной информацией.
1-й ход делает игрок А: он выбирает число .
2-й ход делает игрок B: он выбирает число ,не зная о выборе игрока А на первом ходе.
3-й ход делает игрок А: он выбирает число не зная ни значения .
Функция выигрыша игрока А :
Графическое представление этой игры показано на рисунке 5.
Рис. 5
Нормализуем эту игру.
Стратегии игрока А:
У игрока В всего две стратегии:
В этом случае матрица игры будет иметь вид:
Оптимальные смешанные стратегии игроков и цена игры соответственно равны
Введем понятие биматричной игры.
Пусть - множество стратегий первого и второго игроков соответственно. При выборе первым игроком стратегии , а вторым , возникает ситуация . Выигрыш первого игрока в этой ситуации - , второго - .
Данную игру можно полностью описать, если задать две матрицы:
Определение 1. Биматричной игрой называется совокупность , где , .
Обозначим
Определение 2. Числа называются максиминными ценами первого и второго игроков; – максиминные стратегии первого и второго игроков, – максиминннная цена игры.
Определение 3. Выбор игроками стратегий называется принципом максимина.
Определение 4. Ситуация называется ситуацией равновесия (равновесием по Нэшу) в биматричной игре, если
Определение 5. Вектор , где называется равновесной ценой биматричной игры, соответствующей ситуации .
Определение 6. Стратегия , входящая в какую либо ситуацию равновесия, называется равновесной стратегией первого игрока.
Определение 7. Стратегия , входящая в какую либо ситуацию равновесия, называется равновесной стратегией второго игрока.
Определение 8. Способ выбора игроками в качестве своих стратегий , образующих ситуацию равновесия, называется принципом равновесия.
Теорема 1.
.
Из определения 4 следует, что для нахождения ситуации равновесия и равновесной цены игры можно применить следующий способ:
Определение 9. Пара стратегий и соответствующий исход игры являются оптимальными по Парето, если не существует другого исхода (пары стратегий) игры, который увеличил бы выигрыш одного из игроков, при этом не уменьшив выигрыш другого.
Рассмотрим другой метод для решения позиционных игр. Он основан на понятии совершенства по подиграм.
Определение 1. Подигрой какой-нибудь позиционной игры (с фиксированной начальной позицией) называется всякая игра, ведущаяся по тем же правилам, что и первоначальная, но начинающаяся не обязательно из начальной, но из любой промежуточной позиции первоначальной игры, которая может быть достигнута из заданной начальной позиции.
Определение 2. Равновесие по Нэшу в позиционной игре называется совершенным по подиграм, если оно остается равновесием по Нэшу при его ограничении на каждую подигру.
Пример 6. «Семейный спор».
В статическом варианте игры «семейный спор» муж и жена решали, как провести свободный вечер. Они хотели бы провести его вместе, но муж хотел бы пойти на футбол, а жена – в театр на балет.
Стратегии мужа:
Стратегии жены аналогичны.
Заданы матрицы выигрышей мужа и жены соответственно:
Рассмотрим динамический вариант этой игры. Предположим, что игроки не делают ходов одновременно, но муж делает первый выбор, а жена принимает решение, зная выбор мужа. Дерево такой игры имеет вид:
Логика обратной индукции ведет к следующему решению. Муж может сообразить, что если он выберет футбол, то его жена тоже выберет футбол (т.к. такой выбор обеспечит ей наилучшую выплату 2), что окончательно приведет их к платежам . С другой стороны, если муж выберет балет, то его жена также выберет балет, что приведет к платежам . С точки зрения мужа, лучше, чем , и, следовательно, на своем первом ходе ему разумно выбрать футбол.
Представим эту игру в нормальной форме.
Стратегии мужа:
Стратегии жены:
Первая буква в стратегиях жены означает реакцию на выбор мужем ф (футбол), а вторая означает реакцию на выбор мужем б (балет).
Получаем матрицы выигрышей мужа и жены:
В данной игре три равновесия по Нэшу:
Соответствующие равновесные цены:
Отметим, что только одно равновесие является совершенным по подиграм, а именно , что и получилось из обратной индукции.
Пример 7. «Мудрость царя Соломона».
Всем известна библейская история про то, как Соломон восстановил справедливость: установил, чей на самом деле ребенок.
Глазер и Ма предложили эффективный способ поиска истины в данной ситуации. Чтобы он сработал, нужна лишь грубая численная прикидка значений полезности для женщин получить своего или чужого ребенка соответственно (индексы происходят от английских слов true и false). Естественно, . Тогда женщинам следует предложить сыграть при свидетелях в следующую игру.
Шаг 1. Первую женщину спрашивают: «Это твой ребенок?» Если ее ответ «нет», ребенка отдают второй женщине, и игра завершается.
Шаг 2. Если же последует ответ «да», то затем тот же вопрос задают второй женщине: «Это твой ребенок?» Если ее ответ «нет», ребенка отдают первой женщине, и игра заканчивается. Если же следует ответ «да», то ребенка отдают второй женщине, но они обе получают наказание. Размер наказания для второй женщины составляет величину , а для первой женщины – величину , причем выбираются так, чтобы выполнялось неравенство .
Если первая женщина на самом деле мать, ход игры можно описать графически следующим деревом игры:
Рис. 7
Здесь первое число в скобках означает выплату первой женщине, а второе – второй. Если же вторая женщина – настоящая мать, течение игры может быть описано графически с помощью такого дерева игры:
Рис. 8
Рассмотрим первый случай, когда первая женщина на самом деле мать.
Стратегии первой женщины:
Стратегии второй женщины аналогичны.
Составим матрицы выигрышей двух женщин соответственно, .
В данной игре две ситуации равновесия: Отметим, что эти ситуации равновесия являются также оптимальными по Парето.
Рассмотрим другой способ. Опишем логику обратной индукции. Начиная с последнего шага, когда вторая женщина принимает решение, видно, что для нее сказать «да» (т.е. солгать) означает отрицательный платеж , который хуже, чем сказать «нет» и не получить ничего. Таким образом, логичным ответом второй женщины будет «нет» (т.е. правда), что приводит к передаче ребенка первой женщине (его настоящей матери). Рассмотрим теперь первый шаг, на котором первая женщина делает свой выбор. Подчиняясь здравому смыслу, она может решить, что если она скажет «да», то ее соперница ответит «нет» и, следовательно, она получит , что лучше, чем не получить ничего, сказав «нет». Следовательно, ответы (да, нет) являются решением этой игры в данной ситуации, выплата составит , и настоящая мать получит своего ребенка.
Аналогичными рассуждениями можно показать, что и во втором случае ребенок попадет к настоящей матери.
Пример 8. Игра «Ультиматум».
Руслану и Светлане предложили сыграть в следующую игру. Аукционер дает три доллара Руслану, а он должен разделить эту сумму со Светланой по своему усмотрению, предложив ей любое целое число долларов (то есть 1, 2, 3). Если Светлана согласится принять его предложение, то остаток остается у Руслана. Если Светлана откажется от его предложения, то все 3 доллара возвращаются к аукционеру.
Опишем стратегии Руслана (Р) и Светланы (С).
У Руслана в этой игре три стратегии:
У Светланы же стратегий:
Дерево игры будет иметь вид:
Рис. 9
В скобках первое число – выигрыш Руслана, второе – Светланы.
Составим матрицы выигрышей Руслана и Светланы:
Применив к данной игре способ нахождения ситуации равновесия, изложенный в предыдущем параграфе, получим следующие ситуации равновесия и равновесные цены:
Отметим, что только одно равновесие в данной игре совершенно по подиграм, а именно .
В данной работе был рассмотрен широкий класс игр – позиционные игры. Первый параграф включает в себя основные понятия и теоремы о матричных и антагонистических играх. Во втором параграфе вводится понятие позиционной игры, подробно описывается ее структура, рассматривается возможность графического представления, приводятся соответствующие примеры. Третий параграф посвящен виду позиционных игр – позиционным играм с полной информацией. В нем рассматривается процесс нормализации, приводятся примеры. В четвертом параграфе описывается процесс нормализации позиционной игры с неполной информацией, приводится пример. Пятый параграф включает в себя рассмотрение основных понятий, теорем, касающихся биматричных игр. В последнем параграфе приведены примеры таких позиционных игр, рассмотрены их свойства.