27. Рассмотрим игру со стороны А. Он, выбирая свою стратегию Аi, понимает, что В ответит ему такой стратегией Вj, чтобы выигрыш А был минимальным. Поэтому, из всех наихудших вариантов (минимальных

27. Рассмотрим игру со стороны А. Он, выбирая свою стратегию Аi, понимает, что В ответит ему такой стратегией Вj, чтобы выигрыш А был минимальным. Поэтому, из всех наихудших вариантов (минимальных элементов каждой строки платежной матрицы), игроку А выгодно выбрать стратегию, соответствующую максимальному из этих элементов: Величина a называется нижней ценой игры или максимином. Это гарантированный выигрыш игрока А. С другой стороны, игрок В выбирая свою стратегию Вj понимает, что игрок А ответит такой стратегией Аi, чтобы его выигрыш был максимален. Поэтому из наилучших вариантов для А (максимальных элементов каждого столбца) игроку В рационально выбрать свою стратегию, соответствующую минимальному из этих чисел: . Величина β называется верхней ценой игры или минимаксом. Это максимальный проигрыш игрока В. Реальный результат решения конфликтной ситуации, называемый ценой игры n, заключен между верхней и нижней ценой:. В случае, если верхняя и нижняя цены совпадают, то игра имеет решение в чистых стратегиях, то есть можно точно определить стратегии, которые выгодны для обоих сторон. Если одна сторона отойдет от своей оптимальной стратегии, то ее выигрыш от этого только уменьшится. Пример: Дебитор А желает выбрать один из четырех условий займа: А1, А2, А3, А4. Кредитор может на любой вариант займа ответить вариантом предоставления кредита В1, В2, В3, В4, В5. Процентные ставки для дебитора при любом варианте кредитора представлены платежной матрицей:

В1 В2 В3 В4 В5

А1 6 1 8 7 4

А2 4 3 2 6 5

А3 3 7 6 9 8

А4 2 6 7 8 3

Находим минимальные элементы каждой строки платежной матрицы αI и из них находим максимальное значение. Из максимальных элементов каждого столбца βj выбираем минимальный.

В1 В2 В3 В4 В5 αi

А1 6 1 8 4 4 1

А2 9 6 7 5 8 5

А3 3 7 6 2 8 2

А4 2 6 7 3 3 2

βj 9 7 8 5 8

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

28. Пусть дана матрица игры:

C1 C2 C3 C4 Мin строк

К1 10 1 2 1 1

К2 6 8 5 6 5

К3 2 4 4 8 2

Мах

столбцов 10 8 5 8

Требуется найти нижнюю цену игры α, верхнюю цену игры β и минимаксные стратегии и проверить, являются ли они устойчивыми.

Решение. Из анализа дополнительных столбца и строки получаем: α = 5, β = 5. Максимин равен минимаксу! Случай особый. Что же из этого следует?

Возьмем пару минимаксных стратегий: К2 и С3. Если оба держатся этих стратегий, то выигрыш будет равен 5. Допустим, мы узнали о поведении противника. Но мы по-прежнему будем держаться стратегии К2, потому что любое отступление от нее нам невыгодно. Знаем мы или не знаем о поведении противника — все равно будем держаться стратегии К2! То же относится и к «синим» — им нет смысла менять свою стратегию С3.

В данном примере пара стратегий К2 и С3 устойчива, т. е. представляет собой положение равновесия и дает решение игры. В матрице имеется особый элемент 5; он является минимальным в своей строке и одновременно максимальным в своем столбце. Такой элемент называется седловой точкой. Если матрица имеет седловую точку (т. е. нижняя цена игры равна верхней), то игра имеет решение в чистых стратегиях: это — пара стратегий, пересекающихся в седловой точке. Сама же седловая точка дает цену игры — в нашем примере она равна 5.

Класс игр, имеющих седловую точку, имеет большое значение в теории игр. В частности, доказано, что если по правилам игры каждый из игроков знает результат всех предыдущих ходов, как своих, так и пр-ка (так называемая игра с полной информацией), то игра имеет седловую точку и, значит, имеет решение в чистых стратегиях. Пр-ми игр с полной информацией могут служить: шахматы, шашки, «крестики и нолики» и т. п. Приведем пример игры с полной информацией, решение которой легко найти. Два игрока — К и С — поочередно кладут одинаковые монеты на круглый стол. Положение каждой монеты выбирается произвольно, лишь бы она не перекрывалась другими. Выигрывает тот из игроков, который положит монету последним (когда места для других уже не остается). Сущ-т вполне опр-ленная стратегия, гарант-я выигрыш тому из игроков, который кладет монету первым (пусть это будет К). К должен положить первую монету в центр стола, а далее на каждый ход С отвечать в точности симметр. относительно центра стола ходом. Очевидно, такая игра имеет смысл только для тех, кто не знает решения. Заметим в заключение, что седловых точек в матрице может быть не одна, а несколько; тогда решений игры в чистых стратегиях существует столько, сколько имеется седловых точек. Каждое из них дает выигрыш, равный цене игры.

29. Рассмотрим случай, когда игра не имеет седловой точки, т.е. . Требуется найти оптимальные стратегии игроков и цену игры.

Т.к. в игре нет седловой точки, то обе стратегии игроков являются активными. В соответствии с теоремой об активных стратегиях, если 1 игрок будет применять свою оптимальную стратегию, то, независимо о действий второго игрока, его выигрыш будет цены игры . Пусть. Если 2-ой игрок применяет стратегию, то выигрыш первого игрока определяется из уравнения

Если 2 применяет, то выигрыш 1 Т.к. , то получим систему. Ее решение

Аналогично определяется оптимальная стратегия 2 игрока из системы уравнений

Суть решения: исключить дублирующие и заведомо невыгодные стратегии.

Общий метод:

Разделим обе части неравенств на положительную величину v и обозначим .

Тогда .

Получаем задачу линейного программирования.

30. Игры, повторяемые многократно. Смешанные стратегии. Если партнеры играют только один раз, то игрокам целесообразно придерживаться принципа минимакса, как в игре с седловой точкой, так и в игре без седловой точки.

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

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

Действительно, в игре без седловой точки элемент платежной матрицы , соответствующий минимаксной стратегии игрока A, не обязан быть минимальным в своей строке. Следовательно, игрок B, зная о том, что игрок A в следующей игре будет использовать минимаксную стратегию , может выбрать стратегию, отвечающую минимальному элементу строки . В результате выигрыш игрока A уменьшится от величины до величины . Аналогично может поступить и игрок A, неожиданно применив против игрока B стратегию, соответствующую максимальному элементу столбца .

Более того, доказано, что при многократно повторяемой игре без cедловой точки игроку A, для обеспечения среднего выигрыша, большего, чем , следует чередовать свои стратегии . Игроку B для улучшения результата также целесообразно чередовать свои стратегии .

По этой причине для многократно повторяемых игр без седловой точки вводится следующее определение.

В играх, которые повторяются многократно, каждая из стратегий называется чистой стратегией.

Стратегия игрока A, обозначаемая

=

и состоящая в том, чтобы применять чистые стратегии , чередуя их по случайному закону с частотами , называется смешанной стратегией. Частоты удовлетворяют соотношению

+ + + = 1.

Чистые и смешанные стратегии игрока B определяются аналогично.

Замечание. Каждая чистая стратегия является частным случаем смешанной стратегии, когда одна из стратегий применяется с частотой 1, а все остальные − с частотой 0.

Смешанные стратегии, избранные игроками, называются оптимальными, если одностороннее отклонение любым игроком от своей оптимальной стратегии может изменить средний выигрыш только в сторону, невыгодную для этого игрока.

Совокупность, состоящая из оптимальной стратегии одного игрока и оптимальной стратегии другого игрока, называется решением игры.

Средний выигрыш V при применении обоими игроками оптимальных стратегий называется ценой игры.

Стратегии, входящие с ненулевыми частотами в оптимальную стратегию игрока, называются полезными.

В 1928 году фон Нейманом была доказана основная теорема теории игр, утверждающая, что каждая игра имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий.

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

Следствие 1. Любая игра имеет цену.

Следствие 2. Цена игры удовлетворяет неравенству ≤ V≤ .

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

32. Графический метод решения игр 2 х n И m х 2. Рассмотрим игру, заданную платёжной матрицей.На плоскости хОy введём систему координат и на оси Ох отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (х, 1 - х). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1;0) – стратегия А2 и т.д.

В точках А1 и А2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии А1, а на втором – при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1 игрока 2 – 2, при стратегии В2 – 3, а при стратегии В3 – 11. Числам 2, 3, 11 на оси 0х соответствуют точки В1, В2 и В3.

Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки В¢1, В2¢, В3¢ на перпендикуляре, восстановленном в точке А2.Соединяя между собой точки В1 и В¢1, В2 и В¢2, В3 и В¢3 получим три прямые, расстояние до которых от оси 0х определяет средний выигрыш при любом сочетании соответствующих стратегий. Например, расстояние от любой точки отрезка В1В¢1 до оси 0х определяет средний выигрыш u1 при любом сочетании стратегий А1 А2 (с частотами х и 1–х) и стратегией В1 игрока 2. Это расстояние равно

2х1 + 6(1 - х2) = u1

(Вспомните планиметрию и рассмотрите трапецию А1 B1 B¢1 A2). Таким образом, ординаты точек, принадлежащих ломанной В1 M N В¢3 определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке N; следовательно этой точке соответствует оптимальная стратегия Х* = (х, 1-х), а её ордината равна цене игры u. Координаты точки N находим как точку пересечения прямых В2 B¢2 и В3 B¢3.

Соответствующие два уравнения имеют вид

Следовательно Х = (3/11;9/11), при цене игры u =(49/11). Таким образом мы можем найти оптимальную стратегию при помощи матрицы

Оптимальные стратегии для игрока 2 можно найти из системы

и, следовательно, Y = (0; 9/11;2/11). (Из рисунка видно, что стратегия B1 не войдёт в оптимальную стратегию.

31. Рассмотрим игру без седловой точки типа 2 x 2 с платежной матрицей

C = и найдем оптимальную стратегию =

игрока A. Согласно следствию 3 из основной теоремы теории игр эта стратегия обеспечивает игроку A выигрыш, равный цене игры V, даже если игрок B не выходит за пределы своих полезных стратегий. В данной игре обе чистые стратегии игрока B являются полезными, поскольку в противном случае игра имела бы решение в области чистых стратегий, т.е. была бы игрой с седловой точкой.

Отсюда вытекает, что неизвестные удовлетворяют следующей системе из трех линейных уравнений

решение которой имеет вид

Аналогичным образом можно найти оптимальную стратегию

игрока B. В этом случае неизвестные удовлетворяют системе уравнений

решение которой имеет вид

Применим теперь полученные формулы к карточной игре типа "веришь - не веришь". Имеются две карты: туз и двойка. Игрок А наугад берет одну из них. Если А взял туза, то он заявляет: "У меня туз" и требует у противника рубль. Если же А взял двойку, то он может либо сказать: "У меня туз" и потребовать рубль, либо признаться, что у него двойка и заплатить рубль. Игрок В, если ему предлагают рубль, берет его. Однако, если у него требуют рубль, то В может либо поверить, что у А туз, и заплатить рубль, либо не верить и потребовать проверки. Если в результате проверки окажется, что у А действительно туз, то В платит 2 рубля. Если же выяснится, что у А была двойка, то А платит 2 рубля.

Найти оптимальные стратегии для каждого из игроков.

Решение. У игрока A есть 2 стратегии: − обманывать, − не обманывать. У игрока В тоже есть 2 стратегии: − верить, −не верить. Это позволяет найти все элементы платежной матрицы игры, вычислив средний выигрыш для каждой комбинации стратегий.

1. Комбинация (А обманывает, В верит).

Если А берет туза (вероятностью этого 0,5), то он требует рубль. В верит ему и платит. Если А берет двойку (вероятность этого также 0,5), то он обманывает и тоже требует рубль. В верит ему и платит. Средний выигрыш А равен

2. Комбинация (А обманывает, В не верит).

Если А берет туза, то он требует рубль, а В не верит и после проверки платит 2 рубля. Если же А взял двойку, то он обманывает и тоже требует рубль. В не верит ему, и в результате А платит 2 рубля. Средний выигрыш А равен

3. Комбинация (А не обманывает, В верит).

Если А берет туза, то он требует рубль, В платит 1 рубль. Если А берет двойку, то он сообщает об этом и платит рубль. Средний выигрыш А равен

4. Комбинация (А не обманывает, В не верит).

Если А берет туза, то он требует рубль, В проверяет и платит 2 рубля. Если А берет двойку, то он сообщает об этом и платит рубль. Средний выигрыш А равен

Отсюда вытекает, что платежная матрица имеет вид

и можно найти нижнюю и верхнюю цены игры:

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

Следовательно, смешанная стратегия игрока A имеет вид

= Далее получаем =

Таким образом, оптимальным для А будет в одной трети случаев обманывать, а в двух третях случаев - не обманывать. Такая тактика обеспечит ему средний выигрыш, равный V = 1/3. Если бы А стал пользоваться своей максиминной стратегией, то его выигрыш был бы равен = 0. Для В оптимальная стратегия - это в одной трети случаев верить А и платить ему рубль, а в остальных случаях требовать проверки. В этой ситуации его средний проигрыш составит 1/3, тогда как при применении минимаксной стратегии он будет проигрывать в среднем = 0,5.

Значение V = 1/3 показывает, что рассмотренная игра выгодна для А и невыгодна для В, поскольку, пользуясь своей оптимальной стратегией, A всегда может обеспечить себе положительный средний выигрыш.

Дата добавления: 2015-08-27