Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
М. Оркс 108ч Тукупова Л.А. ИЗО Зам УР 7 ч Рус.яз 7 ч+8ч Шагаев А.С. Соц.пед Шагаева А.Б. ЕГЭ В 11КЛ ОИВТ 8ч алгебра Мат-ка 108ч Шагаева Э.С. ВР 7 ч Ер...полностью>>
'Документ'
0 1950 1 4 4 - 8 19 Батлуков Матвей 003 г. Батайск 3 4 1 .5 11.0 1500 1 17 3 +14 1514 7 Никишин Захар 001 г. Миллерово 3 3,5 9.0 14.5 1500 1 9 3,5 +18...полностью>>
'Документ'
Принятие решений в экономике Тема ....полностью>>
'Документ'
Профориентационное мероприятие под девизом: «Правильный выбор профессии-моя будущая карьера» для учащихся МОУ «Лицей прикладных наук» Волжского района...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

ЭЛЕМЕНТЫ ТЕОРИИ ИГР

1. Матричные игры с нулевой суммой. Платежная матрица игры

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

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

  • Математическая модель конфликтной ситуации называется игрой, а математическая теория, помогающая принимать рациональные решения в конфликтной ситуации, - теорией игр.

  • Конфликтующие стороны называются игроками, а действия, которые могут выполнять игроки, - стратегиями.

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

  • Матричной игрой называется игра, осуществляемая по следующим правилам:

1. В игре участвуют два игрока;

2. Каждый из игроков обладает конечным набором стратегий;

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

4. И выигрыш, и проигрыш выражаются числами.

  • Матричная игра называется игрой с нулевой суммой, если в этой игре выигрыш одного игрока равняется проигрышу другого игрока.

Каждая матричная игра с нулевой суммой имеет платежную матрицу. Для того чтобы построить эту матрицу, обозначим одного из игроков символом А, а другого – символом В, и предположим, что А1, А2,…, Аm – стратегии, которые может применять игрок А, а В1, В2,…, Вn – стратегии, которые может применять игрок В.

  • Матричная игра, в которой у игрока А имеется m стратегий, а у игрока В – n стратегий, называется игрой типа .

Рассмотрим матрицу

,

у которой элементы равны выигрышам игрока А (и проигрышам игрока В) при применении игроками стратеги Ai и Bj соответственно.

  • Матрица С называется платежной матрицей игры.

Пример 1.1. Игра, называемая «Открывание пальцев», заключается в следующем. Два игрока одновременно из сжатого кулака правой руки открывают по несколько пальцев. Общее количество открытых пальцев является суммой выигрыша, причем, если общее количество открытых пальцев четно, то выигрывает первый игрок, если же общее количество пальцев нечетно, то выигрывает второй игрок.

Составить платежную матрицу игры.

Решение. Поскольку каждый из игроков может открыть 1, 2, 3, 4 или 5 пальцев, то у каждого из них имеется по 5 соответствующих стратегий: стратегии А1, А2, А3, А4, А5 у первого игрока, и В1, В2, В3, В4, В5 – у второго. Таким образом, рассматриваемая игра является матричной игрой типа , и можно составить таблицу выигрышей, в зависимости от стратегий, применяемых игроками (Таблица 2.1.1):

Таблица 1.1

Из таблицы 1.1 следует, что платежная матрица игры имеет вид

.

2. Нижняя и верхняя цена игры. Принцип минимакса

Рассмотрим матричную игру типа с платежной матрицей

.

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

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

  • Число

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

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

Проанализируем теперь платежную матрицу с точки зрения игрока В, заинтересованного в том, чтобы игрок А выиграл, как можно меньше.

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

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

  • Число

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

Таким образом, если игрок В применяет минимаксную стратегию, то игрок А не может выиграть больше, чем .

  • Принцип осторожности, заставляющий игроков придерживаться максиминной и минимаксной стратегий соответственно, называют «Принципом минимакса», а минимаксную стратегию называют общим термином «Минимаксные стратегии».

Пример 2.1. Найти нижнюю и верхнюю цены игры с платежной матрицей

.

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

.

Нижняя цена игры

.

Верхняя цена игры

.

3. Игры с деловой точкой

  • Игра называется игрой с деловой точкой, если ее нижняя верхняя цены совпадают, то есть выполняется равенство

.

  • Для игры с седловой точкой общее значение нижней и верхней цены игры

называется ценой игры.

Замечание 1. В Примере 2.1. нижняя и верхняя цены игры совпадают и равны 3, т.е. рассмотренная игра с седловой точкой.

Замечание 2. Максиминной стратегией в Примере 2.1. является стратегия А2, минимаксной стратегией является стратегия В3.

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

.

Следовательно, выполняется равенство

  • Элемент платежной матрицы называется седловой точкой.

Замечание 3. В Примере 2.1. седловой точкой является элемент с23 платежной матрицы. Этот элемент равен 3 и, конечно же, совпадает с ценой игры.

4. Игры без седловой точки

Рассмотрим следующий

Пример 4.1. Найти нижнюю и верхнюю цены игры с платежной матрицей

.

Решение. Действуя аналогично Примеру 2.1., получаем

Нижняя цена игры

.

Верхняя цена игры

.

Замечание 1. В Примере 4.1. нижняя цена игры отличается от верхней цены игры, следовательно, игра является игрой без седловой точки. Максиминной стратегией является стратегия А2. Минимаксной стратегией является стратегия В2.

Замечание 2. Для любой игры без седловой точки выполнено неравенство .

5. Игры, повторяемые многократно. Смешанные стратегии

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

3. Аналитический метод решения игры типа 2 х 2

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

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

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

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

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

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

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

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

Применим теперь полученные формулы к карточной игре типа «веришь – не веришь».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

Для В оптимальная стратегия – это в одной трети случаев верить А и платить ему рубль, а в остальных случаях требовать проверки. В этой ситуации его средний проигрыш составит 1/3, тогда как при применении минимаксной стратегии он будет проигрывать в среднем

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

7. Графический метод решения игр типа и

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

и проведем через точку (1;0) координатной плоскости Oxy прямую l, перпендикулярно оси абсцисс. После этого для каждой из стратегий Bi (i=1,2,…,n)проведем прямую

соединяющую точку на оси Oy с точкой на прямой l. Ось Oy отвечает за стратегию А1, а прямая l – за стратегию А2.



Если игрок А применяет смешанную стратегию

то его выигрыш в случае, если противник применяет чистую стратегию Вi, равен

и этому выигрышу соответствует М на прямой bi с абсциссой x=p2.

Ломанная b1MNb3, отмеченная на чертеже жирной линией, позволяет определить минимальный выигрыш игрока А при любом поведении игрока В. Точка N, в которой эта ломанная достигает максимума, определяет решение и цену игры. Ордината точки N равна цене игры V, а ее абсцисса p2 – частоте применения стратегии A1 в оптимальной смешанной стратегии игрока А.

Далее непосредственно по чертежу находим пару «полезных» стратегий игрока В, пересекающихся в точке N (если в точке N пересекается более двух стратегий, то выберем любые две из них). Пусть это будут стратегии Bi и Bj. Поскольку выигрыш игрока А, если он придерживается оптимальной стратегии, не зависит от того, в каких пропорциях игрок В применяет эти стратегии, то неизвестные p1, p2, V определяются из системы уравнений

Частоты q1, q2 в оптимальной стратегии

игрока В определяются из соотношения

Замечание. Иногда точка N не является пересечением двух стратегий, а попадает на одну из прямых х=0 или х=1. В этом случае решением игры будут соответствующие чистые стратегии.

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

Пример 7.1. Пусть игра задана матрицей

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

Решение.

Проведем прямые bi, и построим ломанную линию b1NMb3, соответствующую нижней границе выигрыша. Точка N, в которой эта ломанная достигает максимума, является пересечением прямых

и


Вычислив координаты точки N: х0=4/7, у0=27/7, получаем оптимальную стратегию игрока А


и цену V=27/7. Так как точка N является пересечением прямых b1 и b2, то полезными стратегиями игрока В будут стратегии B1 и B2. Найдем частоты их применения q1 и q2, зная, что выигрыш равен цене игры, если игрок В применяет оптимальную стратегию, а игрок А – любую из своих полезных стратегий, например стратегию A1:

=>

Ответ.

Пример 7.2. Пусть игра задана матрицей

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

Решение.

Воспользовавшись тем, что игрок В располагает двумя чистыми стратегиями, построим прямые аi, соответствующие выигрышам игрока А при чистых стратегиях Ai, и ломанную линию a1PNMa4, огибающую график сверху. Эта ломанная достигает минимума в точке N(x0,y0), которая является пересечением прямых

и

Следовательно, х0=0,6; V=7,2. и оптимальной стратегией игрока В является стратегия


Цена игры V=7,2. Полезными стратегиями игрока А являются стратегии А2 и А3. Найдем их частоты р2 и р3:

Ответ.

Задачи для самостоятельного решения

1. Дана задача принятия решения. В таблице – прибыль города при различных вариантах проведения праздника (тыс. руб.).

Погода

Праздник на открытом воздухе

Праздник в театре

Солнечно (60%)

1000

750

Дождь (40%)

200

500

Установить, где следует проводить праздник по критериям Лапласа, Вальда и математического ожидания? Каким будет α в критерии Гурвица, если предпочтение отдано театру?

Ответ: в театре, в театре, на открытом воздухе, .

2. Найти в антагонистической игре седловую точку, если она есть.

Ответ: седловой точки нет.

Ответ: (0,1).

3. Матрица А в матричной игре имеет вид

Установить, при каких х и у в матрице есть седловые точки.

Ответ: при х ≤ 6, у ≤ 6.

4. Матрица А в матричной игре имеет вид

Установить, при каких х в матрице есть седловые точки.

Ответ: при любых значениях х седловых точек нет.

5. Задача о зимней эксплуатации лесовозной дороги.

Предположим, что при заготовке леса зимой есть выбор – делать или не делать предварительную расчистку дороги. При этом известны предполагаемые высоты снежного покрова и матрица доходов при применении той или иной стратегии. Заготовитель – игрок 1, природа – игрок 2.

1 \ 2

20 мм

40 мм

60 мм

100 мм

Не делать

2

2

3

-1

Делать

4

3

2

6

Найти цену игры.

Ответ: v=2.5.

6. Найти с помощью графического метода, предварительно вычеркнув доминируемый столбец или строку, решение матричной игры с матрицей А=

Ответ:

7. Найти оптимальные стратегии игроков в игре с матрицей А=

Ответ:

8. Матрица А в биматричной игре имеет вид

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

Ответ: должно выполняться хотя бы одно из трех условий:

а) - максимум в первой строке; б) во второй строке есть элементы, не меньшие, чем ; в) в третьей строке есть элементы, не меньшие, чем .

9. Найти смешанные ситуации равновесия в игре с матрицами

А=, В=

Ответ:



Похожие документы:

  1. Бабочка-льдышка Ассоциации Вопросы на бумажках

    Документ
    ... не иссякнет фантазия на вопросы. Смысл игры заключается в том, что каждый игрок, отвечая на последний вопрос, не видит результатов ... из пруда; -Семь раз отмерь - один отрежь. Каждый игрок выбирает себе одно слово, и все произносят свои слова ...
  2. Тесты 7 матричные игры 8 Описание матричной игры 8 Принцип максимина в антагонистических играх. Седловая точка 9 тесты 11

    Тесты
    ... в свою пользу [1]. Еще одним недостатком теории игр является то, что каждому из игроков должны быть известны все возможные действия (стратегии) противника ...
  3. Н. Рубштейн Что нужно знать

    Документ
    ... улучшить свое движение, когда, попросту, «не получается». Дело в том, что у каждого из нас есть свой предел возможностей ... том, что их действия не приносят должного результата. Здесь есть только одна точная рекомендация – пересмотрите, что вы делаете ...
  4. Я выбрал свой путь

    Документ
    ... не стали бы делать лишних движений ни за одного из двух своих кандидатов. Тем более, что каждый из ... ними заключается в том, что безналичные средства никуда не могут деться. Они представляют только информацию, которая ...
  5. Макки Р. Ml5 История на миллион долларов: Мастер-класс для сценаристов, писателей и не только / Роберт Макки; Пер с англ

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

Другие похожие документы..