9.2. Диагональные игры. 9.3. Симметричные игры.
9. 2. Диагональные игры Диагональной называется игра, в которой матрица имеет вид Где Диагональная игра может рассматриваться как следующая игра поиска. Имеется n коробок. Игрок 2 выбирает одну из коробок и прячет в ней некоторый предмет стоимостью а. Номер выбранной коробки есть номер стратегии 2-го игрока. Этот номер, разумеется, 1-му игроку не сообщается. Затем 1-й игрок выбирает одну из этих n коробок и проверяет, есть ли там предмет. Номер выбранной ячейки есть номер стратегии 1-го игрока. Если в коробке нет предмета, то выигрыш первого игрока равен нулю. Если в коробке есть предмет, то 1-й игрок получает часть стоимости предмета Покажем, что значение диагональной игры положительно. Возьмем стратегию первого игрока Тогда для всех По лемме 2 (третье замечание к лемме), для любого Но поскольку
Теперь покажем, что все стратегии 1-го игрока – активные, т. е., если 9. 3. Симметричные игры. Напомним, что квадратная матрица А называется кососимметрической, если
Матричная игра с кососимметрической матрицей выигрыша называется симметричной. Теорема 12. В симметричной игре 10. Итеративный метод решения матричных игр. В этом параграфе описан весьма наглядный и простой метод приближённого решения матричных игр, известный как метод Брауна-Робинсона или метод фиктивного разыгрывания. Подчеркнём, что в действительности игра не проводится и с помощью фиктивного (мысленного) разыгрывания игроки пытаются найти её решение.
И так, пусть разыгрывается игра Пусть в первых k фиктивных партиях 1-й игрок свою i-ю чистую стратегию Кроме того, обозначим Очевидно, что для всех i = 1, 2, …, m; j = 1, 2, …, n и любого k = 1, 2, ….
Формулы (99) показывают, что векторы В (k + 1)-й партии 1-й игрок выбирает чистую стратегию
или в развёрнутом виде Второй игрок в (k + 1)-й партии выбирает чистую стратегию
Таким образом, получаем некий итерационный процесс, в котором для каждого
Покажем, что для любого k:
Где v – значение игры Действительно, пусть Левая часть неравенства (103) доказана. Правая часть доказывается аналогично. Поскольку (103) верно для любого k, то после разыгрывания N партий можем написать:
Иначе говоря, после N партий может быть найдено приближенное значение игры, лежащее в промежутке:
Доказывается, (см. [21], с. 110), что
Таким образом, указанным способом значение игры может быть найдено с любой степенью точности. Если 1-й игрок имеет единственную оптимальную стратегию, то эта последовательность может не иметь предела. Однако любая ее сходящаяся последовательность сходится к одной из оптимальных стратегий 1-го игрока. То же верно для последовательности стратегий Достоинством метода является простота его реализации. К недостаткам метода относится его медленная и, главное, немонотонная сходимость. Длина промежутка (105) убывает со скоростью, пропорциональной
Для симметричных игр оценка скорости сходимости может быть улучшена (см. [21], с. 118) до 11. Матричные игры и линейное программирование. Решение матричной игры может быть сведено к задаче линейного программирования. Сначала будем считать, что все элементы матрицы игры
И двойную задачу
Из теоремы двойственности следует, что обе задачи (106), (107) имеют оптимальное решение
такое, что
Покажем, что векторы
Являются оптимальными стратегиями игроков, а Так как все координаты векторов А также
Таким образом, Далее имеем
С другой стороны, из (106), (107) следует, что Таким образом,
и из (108) получаем, что
Пусть
Следовательно, Если не все элементы матрицы А положительны, то можно ко всем ее элементам добавить достаточно большое число b так, чтобы
то Сведение решения матричной игры в задаче линейного программирования позволяет использовать любой метод решения задач линейного программирования для решения матричных игр, например, симплекс-метод. КООПЕРАТИВНЫЕ ИГРЫ 1. Смешанное расширение бескоалиционной игры Замена в бесконечной игре Обозначим через Лемма 1. Определение 1. Ситуация
Теорема 1. Ситуация Теорема 2 (теорема Ноша). В каждой бескоалиционной игре Г существует ситуация равновесия в смешанных стратегиях. 2. Биматричные игры
Решение 2× 2 биматричной игры. Пусть каждый из игроков располагает двумя стратегиями (m=n=2). Следовательно
Получаем выражения:
Ситуация (x, y) Является приемлемой для игрока 1, если
Одновременная реализация этих двух условий приводит к системе Где
Потребовав, чтобы ситуация (x; y) была приемлемой и для игрока 2, получим
Решение системы изображено на рис. 2, а, б; Примеры 1 «Дилемма бандита». [15] (Сравнение с примером 6 введения. ) В предварительном заключении находятся два преступника (игрок 1 и 2), подозреваемые в совершении тяжкого преступления. Каждый из них имеет две стратегии: 1 – сознаться, 2 – не сознаваться. Если оба сознаются, то будут осуждены на длительный срок (например, 8 лет). Если оба не сознаются, то обвинение в тяжком преступлении будет снято, но каждого из них смогут осудить на незначительный срок (например, 1 год). В случае же, кода сознается лишь один, о будет освобождён, а его упорствующий партнёр будет осуждён, например, на 10 лет. Матрицы выигрышей в рассматриваемой игре равны:
2. «Семейный спор» (пример 5 введения). Два партнера договариваются о совместно проводимых ими действиях 1 или 2. В случае совместного проведения действия 1 (выбор стратегии 1) первый игрок получает выигрыш 1, второй – 2. В случае совместного осуществления действия 2 первый игрок получает выигрыш 2, а второй – 1. При выполнении различных действий выигрыш каждого равен 0. Таким образом, матрицы выигрышей равны:
Кривые приемлемых ситуаций (1) и (2) представлены на рис. 4, из рассмотрения которого следует, что игра имеет три ситуации равновесия: В третьей ситуации, как легко убедиться, 3. Характеристическая функция кооперативной игры Любое подмножество множества игроков Примеры. 1. Игра с главным игроком. В игре участвуют n игроков из которых один (например, игрок a ) – главный. Коалиция K выигрывает 1, если она содержит главного игрока и еще хотя-бы одного из всех n-1 остальных («неглавных»): 2. «Помещик и батраки». В игре участвуют игроки 1; 2; …; n-1 – батраки и игрок n – помещик. Помещик, наняв k бараков, может получить доход f(k), а батраки в любом случае сами по себе (без помещика) дохода получить не могут. 3. В игре участвуют три игрока: 1, 2, 3, располагающие каждый тремя стратегиями соответственно:
Возможны коалиции: Подробно рассмотрим коалиции, объединяющие двух игроков. Каждая такая коалиция обладает
Так как каждая из этих трех таблиц описывает матричную игру, то легко найти её решение (см. §3 раздела «Матричные игры»), которое выделено в каждой из таблиц штриховкой. Таким образом, Система
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|