🗊Презентация Элементы теории игр

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

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

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

Классификация игровых задач

Игра с нулевой суммой конфликт двух участников с противоположными интересами, выигрыш одной стороны конфликта в точности совпадает с проигрышем другой стороны Участники игры — лица, принимающие решения, — называются игроками. Целевые функции называются платежными функциями, и считается, что они показывают выигрыш игрока. Стратегия игрока — это осознанный выбор одного из множества возможных вариантов его действий

Платежная матрица Стратегии первого игрока пронумеруем числами от 1 до m, а стратегии второго игрока — числами от 1 до n. Конечная игра с нулевой суммой однозначно определяется платежной матрицей (матрицей выигрышей) aij – платеж второго игрока первому

Правила игры Игра происходит партиями. Партия игры состоит в том, что игроки одновременно называют свой выбор: первый игрок называет некоторый номер строки матрицы П (по своему выбору или случайно), а второй — некоторый номер столбца этой матрицы (также по своему выбору или случайно). После этого происходит «расплата». Цель каждого игрока — выиграть как можно бóльшую сумму в результате большого числа партий.

Решение игры Решением игры можно назвать любое описание того, каким образом должны вести себя игроки в той или иной игровой ситуации. Стратегия называется чистой, если выбор игрока неизменен от партии к партии. У первого игрока, очевидно, есть m чистых стратегий, а у второго - n. Решением может быть набор исходов игры. Решением игры может быть и набор смешанных стратегий, если одних только чистых стратегий недостаточно.

Игра в чистых стратегиях При анализе игр противник считается сильным, т.е. разумным. Нижняя цена игры представляет собой максимальный гарантированный выигрыш первого игрока. Стратегия 1-го игрока – максиминная. Верхняя цена игры представляет собой величину, противоположную минимальному гарантированному проигрышу второго игрока (второй игрок гарантирует, что он не проиграет больше чем β). Стратегия 2-го игрока – минимаксная.

Цена игры Если α=β, то говорят, что игра имеет седловую точку в чистых стратегиях. Общее значение α и β называется при этом ценой игры и обозначается ν=α=β. Стратегии игроков, соответствующие седловой точке, называются оптимальными чистыми стратегиями. Теорема. В любой матричной игре нижняя цена не превосходит верхней: α≤β.

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

Решение Нижняя цена игры соответствует второй стратегии первого игрока. Верхняя цена игры соответствует второй стратегии второго игрока. Если первый игрок будет действовать со второй стратегией, а второй игрок — со второй стратегией, то игроки могут гарантировать себе: первый — выигрыш не менее ν=α=β=0,3=30% рынка, а второй — что первый выиграет не более ν=30% рынка

Игра в смешанных стратегиях pi – вероятность, с которой первый игрок выбирает свою i-ю стратегию qi – вероятность, с которой второй игрок выбирает свою i-ю стратегию Смешанной стратегией первого игрока называется вектор где все pi ≥ 0 (i = 1, 2, …, m), а Σ pi = 1, т.е. распределение вероятностей на множестве его чистых стратегий Смешанной стратегией второго игрока называется вектор где все qi ≥ 0 (i = 1, 2, …, n), а Σ qi = 1,

Игра в смешанных стратегиях Если игроки играют со своими смешанными стратегиями p=(p1, p2, …,pm) и q = (q1, q2, …, qn) соответственно, то математическое ожидание выигрыша первого игрока равно математическому ожиданию проигрыша второго игрока Стратегии p*=(p*1, p*2, …,p*m) и q* = (q*1, q*2, …, q*n) называются оптимальными смешанными стратегиями соответственно первого и второго игрока, если Если у обоих игроков есть оптимальные смешанные стратегии, то пара (p*, q*) называется решением игры (или седловой точкой в смешанных стратегиях), а число ν = M(p*, q*) – ценой игры

Решение игры 2×2 в смешанных стратегиях Пусть - матрица игры Пусть (p1, p2) – оптимальная стратегия игрока 1; (q1, q2) – оптимальная стратегия игрока 2 Тогда, исключая тривиальный случай (наличие чистой оптимальной стратегии хотя бы у одного из игроков), имеем: p1 + p2 = 1, p1>0, p2>0; q1 + q2 = 1, q1>0, q2>0;

Решение игры 2×2 в смешанных стратегиях Цена игры игрока 1 равна: Подставляя , находим Аналогично для второго игрока находим

Пример. Игра «Угадывание монеты» Правила игры таковы. Первый игрок прячет в кулаке одну из двух монет: 1 руб. или 5 руб. по своему выбору и незаметно от второго игрока, а второй игрок пытается угадать, какая монета спрятана, и если угадывает, то получает эту монету, в противном случае платит первому игроку 3 руб. Требуется доказать, что данная игра не имеет седловой точки в чистых стратегиях и найти решение игры в смешанных стратегиях.

Решение Платежная матрица имеет вид Проверим, есть ли в игре седловая точка в чистых стратегиях. Нижняя цена игры Верхняя цена игры α≠β, и седловой точки (в чистых стратегиях) в игре нет

Решение в смешанных стратегиях для первого игрока Пусть первый игрок выбирает свою первую стратегию с вероятностью p[0,1], а вторую стратегию — соответственно с вероятностью (1 – p), т. е. первый игрок играет со смешанной стратегией p* = (p, 1-p). Обозначим νj(p) ожидаемый выигрыш (т. е. математическое ожидание выигрыша) первого игрока, если второй игрок при этом выберет свою j-ю стратегию.

Гарантированный выигрыш первого игрока

Решение в смешанных стратегиях для первого игрока Второй игрок так выбирает свои стратегии, чтобы обеспечить первому минимальный выигрыш: ν(p) = min { ν1(p), ν2(p)}. Наилучший для первого игрока выбор соответствует Из условия ν1(p) = ν2(p) или - p + 3(1- p) = 3 p - 5(1- p) находим p= p* = 2/3. Оптимальной смешанной стратегией первого игрока является стратегия p* = (2/3, 1/3). Цена игры равна ν* = ν1(2/3) = ν2(2/3) = 1/3. Вне зависимости от того, какую стратегию выберет второй игрок, первый игрок будет выигрывать в среднем за большое число партий по 1/3 руб. за одну партию.

Решение в смешанных стратегиях для второго игрока Пусть второй игрок выбирает первую стратегию с вероятностью q[0,1], а вторую — с вероятностью (1–q), т.е. вектор смешанной стратегии второго игрока имеет вид q = (q, 1- q). Проигрыш второго игрока равен , если первый игрок выбирает свою первую стратегию , если первый игрок выбирает свою вторую стратегию

Верхняя граница проигрыша второго игрока

Решение в смешанных стратегиях для второго игрока Наилучшее с точки зрения второго игрока значение q определяется из условия Из условия µ1(q) = µ2(q) находим q* = 2/3. Поэтому оптимальная смешанная стратегия второго игрока равна q* = (2/3, 1/3).

Основная теорема теории матричных игр В любой матричной игре у игроков есть оптимальные смешанные стратегии.

Решение игры 2×n Матрица игры Смешанные стратегии игрока 1 – вектор Ожидаемый выигрыш 1-го игрока при применении игроком 2 своей j-ой стратегии:

Гарантированный выигрыш игрока 1 Строим графики ожидаемых выигрышей и по графику устанавливаем точку М* - верхнюю точку нижней огибающей данного семейства прямых, которая соответствует оптимальной стратегии первого игрока

Пример Решить игру с платежной матрицей

Решение в чистых стратегиях Нижняя цена игры Верхняя цена игры α ≠β, значит, седловой точки (в чистых стратегиях) в игре нет

Решение в смешанных стратегиях для первого игрока Пусть первый игрок играет со смешанной стратегией Обозначим νj(p) ожидаемый выигрыш первого игрока, если второй игрок при этом выберет свою j-ю стратегию:

Гарантированный выигрыш первого игрока

Оптимальная стратегия первого игрока Из условия ν1(p) = ν2(p) находим p=6/11, т.е. оптимальная стратегия первого игрока равна Цена игры равна ν∗ = ν1(6/11) = ν2(6/11)= −2/11.

Решение в смешанных стратегиях для первого игрока Второй игрок, действуя разумно, никогда не будет выбирать третью и четвертую стратегии, поэтому вектор оптимальной смешанной стратегии второго игрока имеет вид Проигрыш второго игрока равен µ1(q) = − 2q + 3(1- q), если первый игрок выбирает свою первую стратегию, µ2(q) = 2q − 4(1-q), если первый игрок выбирает свою вторую стратегию.

Оптимальная стратегия второго игрока Из условия µ1(q) = µ2(q) находим q=7/11. Оптимальная смешанная стратегия второго игрока равна

Игра m ×n При решении матричной игры размерностью n × m могут быть применены два приема: сведение задачи к задаче m × 2 или 2×n; сведение задачи к задаче линейного программирования.

Доминирующие стратегии Говорят, что стратегия А1 первого игрока доминирует стратегию А2, если для всех j = 1, 2, …, n имеет место a1j ≥ a2j. В этом случае стратегия A2 заведомо хуже стратегии A1. Стратегия A2 называется доминируемой и может быть исключена из рассмотрения. Говорят, что стратегия B1 доминирует стратегию B2 второго игрока, если для любого i справедливо ai1 ≤ ai2. Здесь стратегия B2 заведомо хуже стратегии B1, она называется доминируемой и может быть удалена из рассмотрения.

Основные теоремы теории игр Ни одна из строго доминирующих чистых стратегий не содержится в спектре оптимальных решений. Если некоторая чистая стратегия A, доминируется смешанной стратегией B, в спектре которой нет A, то удаление A приводит к тождественной игре. Решения игр будут тождественными, если каждый элемент платежной матрицы преобразуется следующим образом пij = kaij + b, где k>0, b>0 – любые числа. Без изменения оптимального решения каждый элемент платежной матрицы можно умножить на любое положительное число и сложить с любым положительным числом. При этом новая цена игры ν будет связана с реальной ценой соотношением νij = kν*ij + b

Пример Решить игру, заданную платежной матрицей

Решение Стратегия А5 дублирует стратегию А2, поэтому любую из них можно отбросить. Отбросим А5. Заметим, что в строке А1 все выигрыши больше (или равны) выигрышам строки А4. Стратегия А1 доминирует над стратегией А4. Отбрасываем строку А4. Получим игру 3×5.

Решение Стратегия В3 доминирует над В4 и над В5, а В1 – над В2. Отбрасываем столбцы В2, В4, В5. Получим игру 3×2. Стратегия А3 дублирует стратегию А1, поэтому любую из них можно отбросить. Отбросим А3. Получим игру 2×2.

Решение матричной игры сведением к задаче линейного программирования Пусть рассматривается игра с платежной матрицей, все элементы которой строго положительны Смешанные стратегии первого и второго игрока Если стратегия p является оптимальной, то средний выигрыш первого игрока независимо от того, какую стратегию выберет второй игрок, будет не меньше цены игры ν∗:

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

Постановка двойственных задач линейного программирования для первого и второго игроков

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

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

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

Решение с помощью сведения задачи к паре взаимно двойственных задач линейного программирования От платежной матрицы путем добавления положительного числа b = 5 перейдем к матрице

Пара двойственных задач линейного программирования

Оптимальные решения Оптимальные решения задач ЛП Оптимальные смешанные стратегии игроков Цена игры