Справочник от Автор24
Высшая математика

Конспект лекции
«Матричные игры 2×n»

Справочник / Лекторий Справочник / Лекционные и методические материалы по высшей математике / Матричные игры 2×n

Выбери формат для чтения

docx

Конспект лекции по дисциплине «Матричные игры 2×n», docx

Файл загружается

Файл загружается

Благодарим за ожидание, осталось немного.

Конспект лекции по дисциплине «Матричные игры 2×n». docx

txt

Конспект лекции по дисциплине «Матричные игры 2×n», текстовый формат

Матричные игры 2×n Рассмотрим многоразовую игру с матрицей выигрышей . В такой игре игрок A имеет две стратегии A1 и A2, а игрок B – n стратегий B1, B2,…, Bn. Пусть смешанные стратегии игроков A и B имеют вид . Предполагаем, что седловая точка в игре отсутствует. Имеем где . Для нахождения используем графический метод. Для этого в плоскости построим прямые : , . Здесь – независимая переменная, а – переменная, зависящая от . Далее построим ломаную , огибающую снизу все эти прямые для . Тогда ордината y верхней точки ломаной L даст значение , в которой и достигается . Это значение и будет ценой игры. В качестве примера рассмотрим случай . Построим три прямые: и их нижнюю огибающую (рис. 1). Из рисунка находим точку , которая и будет являться решением игры. Найдем теперь оптимальную стратегию игрока B. Для этого снова используем теорему об активных стратегиях. При нахождении оптимальной стратегии игрока B необходимо учитывать как расположение точки на плоскости, так и ее единственность (или неединственность). Рассмотрим возможные варианты. 1. Точка единственна. В этом случае точка максимума огибающей L является точкой пересечения двух прямых. Например, на рисунке 1 такими прямыми являются прямые и , которые соответствуют первому и второму столбцу матрицы выигрышей . По теореме об активных стратегиях активными будут только стратегии B1 и B2, а их вероятности войдут в уравнение для нахождения оптимальной смешанной стратегий игрока B. 2. Точка не является единственной, то есть нижняя огибающая L содержит целый горизонтальный участок, например, как на рис. 2. Тогда для игрока B оптимальной является стратегия соответствующая прямой , а для игрока A существует бесконечно много оптимальных смешанных стратегий, в которых вероятности находятся между значениями и (см. рис. 2). Доминирующие и доминируемые стратегии Иногда платежная матрица , , имеет такую структуру, что игра может быть упрощена отбрасыванием в этой матрице некоторых строк (столбцов). Рассмотрим матричную игру двух игроков A и B. Пусть игрок A имеет стратегии A1, A2,…, Am, а игрок у игрока B имеются стратегии B1, B2,…, Bn. Определение. Будем говорить, что стратегия Ai доминирует стратегию Ak (стратегия Ak доминируется стратегией Ai), если для элементов платёжной матрицы C выполняются неравенства то есть элементы k-й строки матрицы C не превосходят соответствующих элементов ее i-й строки и хотя бы для одного значения j неравенство является строгим. Будем говорить, что стратегия Bj доминирует стратегию Bl (стратегия Bl доминируется стратегией Bj), если то есть элементы j-го столбца матрицы C не превосходят соответствующих элементов ее l-го столбца и хотя бы для одного значения i неравенство является строгим. Справедливо следующее очевидное утверждение. Утверждение 1. Если платежная матрица C имеет доминируемые стратегии (строки или столбцы), то оптимальное решение такой игры совпадает с оптимальным решением игры с платежной матрицей C*, полученной из матрицы C отбрасыванием доминируемых строк (столбцов). Замечание. 1. При отбрасывании доминируемых строк (столбцов) размер матрицы C уменьшается. Этот процесс упрощения игры можно продолжать до тех пор, пока не останется доминируемых стратегий. 2. Если платежная матрица содержит несколько одинаковых строк (столбцов), то оставляют только одну из таких строк (столбцов), а остальные отбрасывают. Утверждение 2. Если элементы двух платежных матриц и , где , , связаны соотношениями где , γ – произвольное число, то оптимальные стратегии этих игр совпадают, а цены игр связаны равенством (1) Будем искать оптимальные смешанные стратегии и игроков A и B. Для решения используем графический метод. Построим прямые: и нижнюю огибающую (рис. 3). Из рис. 3 видно, что оптимальная точка – это точка пересечения прямых и , то есть она определяется из системы Решив систему, получим , , . Таким образом, оптимальная стратегия игрока A имеет вид . Теперь найдем цену игры D. Заметим, что элементы матриц C и D связаны соотношением: , , . Тогда по формуле (1) находим цену второй игры: Применение методов линейного программирования при решении матричных игр Рассмотрим игру двух лиц с платежной матрицей (матрицей выигрышей игрока A) , , . Не ограничивая общности, можем считать, что матрица C положительна. В противном случае к элементам матрицы C следует добавить одно и то же положительное число, применяя утверждение 2. Пусть смешанная стратегия игрока A имеет вид Тогда средний выигрыш игрока A при использовании игроком B чистой стратегии Bj составит . Обозначим через минимальный средний выигрыш игрока A при любой чистой стратегии игрока B, т. е . Тогда выполняются неравенства (2) Введем новые переменные и перепишем неравенства (2) в виде (3) Задача игрока A – максимизировать свой выигрыш, то есть . Введем в рассмотрение функцию , где . В силу (3) . Следовательно, функцию надо минимизировать. Таким образом, приходим к следующей задаче линейного программирования. Найти минимум функции (4) при следующих ограничениях (5) Рассмотрим теперь игру игрока B. Его смешанная стратегия обеспечит ему средний проигрыш, не больший чем , при любой чистой стратегии игрока A, то есть (6) Вводя новые переменные преобразуем систему (6) к виду (7) Рассмотрим функцию , где . В силу (7) . Так как для игрока B его проигрыш надо минимизировать, то функцию надо, напротив, максимизировать. Приходим к задаче линейного программирования: найти максимум функции (8) при следующих ограничениях (9) Из курса линейного программирования известно, что задачи (4)–(5) и (8)–(9) представляют собой пару двойственных задач и эти задачи имеют оптимальные решения и . Таким образом, приходим к следующему результату. Теорема 1. Решение матричной игры с положительной матрицей выигрышей , , , равносильно решению двойственных задач линейного программирования (4)–(5), (8) – (9). При этом цена игры удовлетворяет равенству а оптимальные вероятности и определяются формулами , . Алгоритм решения матричной игры с помощью решения двойственных задач линейного программирования следующий. 1. Ко всем элементам платежной матрицы C прибавим одно и то же положительное число γ так, чтобы все ее элементы стали положительными. 2. Составим пару двойственных задач линейного программирования (4)–(5) и (8)–(9) и найдем их решения , . В качестве контроля правильности решения задач можно использовать равенство 3. Построим оптимальные смешанные стратегии игроков: , , , . (10) 4. Вычислим цену игры: (11)

Рекомендованные лекции

Смотреть все
Высшая математика

Основные понятия теории игр

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

Автор лекции

Зиганшина Айгуль Раисовна

Авторы

Высшая математика

Элементы теории игр

Лекция №3: Элементы теории игр 1. Понятие об играх и стратегиях 2. Классификация игр 3. Запись матричной игры в виде платёжной матрицы 4. Понятие о ни...

Программирование

Элементы теории игр

Лекция №3: Элементы теории игр 1. Понятие об играх и стратегиях 2. Классификация игр 3. Запись матричной игры в виде платёжной матрицы 4. Понятие о ни...

Высшая математика

Введение в теорию игр.Матричные игры.Игры с природой

3 6.1.Введение в теорию игр 6.2. Матричные игры 6.3. Игры с природой Е.В. Яроцкая, к.э.н., доцент кафедры экономики ТПУ 4 Теория игр – это раздел мате...

Теория вероятностей

Решение матричных игр

Решение матричных игр Содержание лекции •Аналитическое решение матричных игр 2 × 2 в смешанных стратегиях •Графическое решение матричных игр 2 × 2 в с...

Высшая математика

Ситуация равновесия в матричных играх

Лекция 2 (ММвТУиИО) СИТУАЦИЯ РАВНОВЕСИЯ В МАТРИЧНЫХ ИГРАХ Рассмотрев на Лекции №1 некоторые принципы формализации конфликтных ситуаций с помощью модел...

Теория вероятностей

Детализация поведения игроков во времени — многошаговые игры

Лекция 8 Многошаговые игры В предыдущих лекциях мы рассматривали такие игры, динамика развития которых не оказывала влияния на поведение участников. П...

Высшая математика

Теория игр

Министерство образования и науки Российской Федерации Амурский государственный университет УДК 519.832 ББК 22.18 М17 Рекомендовано учебно-методическим...

Автор лекции

Н.Н. Максимова

Авторы

Высшая математика

Графический метод решения матричных игр (часть 1)

Лекция 3 (ММвТУиИО) ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ МАТРИЧНЫХ ИГР Рассмотрение методов поиска решения матричных игр начнем с игр, в которых число стратегий,...

Программирование

Теория принятия решений

Министерство образования и науки Российской Федерации Балтийский государственный технический университет «Военмех» Е.Е. ВОРОБЬЕВА, В.Ю. ЕМЕЛЬЯНОВ ТЕОР...

Автор лекции

Воробьева Е.Е., Емельянов В.Ю.

Авторы

Смотреть все