Элементы теории игр - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Элементы теории игр. Доклад-сообщение содержит 49 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

Игра в смешанных стратегиях Если игроки играют со своими смешанными стратегиями 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*) – ценой игры

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

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

Слайд 20

Описание слайда:

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

Слайд 21

Описание слайда:

Решение в смешанных стратегиях для первого игрока Второй игрок так выбирает свои стратегии, чтобы обеспечить первому минимальный выигрыш: ν(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 руб. за одну партию.

Слайд 22

Описание слайда:

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

Слайд 23

Описание слайда:

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

Слайд 24

Описание слайда:

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

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

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

Слайд 33

Описание слайда:

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

Слайд 34

Описание слайда:

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

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

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

Слайд 37

Описание слайда:

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

Слайд 38

Описание слайда:

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

Слайд 39

Описание слайда:

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

Слайд 40

Описание слайда:

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

Слайд 41

Описание слайда:

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

Слайд 42

Описание слайда:

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

Слайд 43

Описание слайда:

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

Слайд 44

Описание слайда:

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

Слайд 45

Описание слайда:

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

Слайд 46

Описание слайда:

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

Слайд 47

Описание слайда:

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