рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Матричные игры с нулевой суммой

Матричные игры с нулевой суммой - Контрольная Работа, раздел Образование, ЛЕКЦИИ ПО ТЕОРИИ ИГР   Рассмотрим Парную Игру С Нулевой Суммой. Пусть Игрок I Имеет ...

 

Рассмотрим парную игру с нулевой суммой. Пусть игрок I имеет стратегий (1, 2,…,m), а игрок II - стратегий 1, 2,…, n). Такая игра называется матричной игрой размерности .

Предположим, игрок I выбрал одну из своих возможных стратегий (), а игрок II, не зная результата выбора игрока I, - стратегию ( ). Выигрыши игрока I и игрока II в результате выбора стратегий удовлетворяют соотношению ; таким образом, если ввести обозначение , то .

Элементы для каждой пары стратегий считаются известными и записываются в платежную матрицу (табл. 4.1), строки которой соответствуют стратегиям игрока I, а столбцы - стратегиям игрока II. Каждый положительный элемент матрицы определяет величину выигрыша игрока I и, соответственно, проигрыша игрока II при применении ими соответствующих стратегий. Естественно, целью игрока I является максимизация своего выигрыша, тогда как игрока II - минимизация своего проигрыша.

 

Таблица 4.1Платежная матрица парной игры с нулевой суммой

II I n
m

Решение парных матричных игр с нулевой суммой. Принцип минимакса

Используя платежную матрицу парной игры с нулевой суммой (табл. 4.1), определим наилучшую стратегию игрока I среди стратегий i ( i = ) и наилучшую стратегию игрока II среди стратегий j (j=).

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

Проанализируем стратегии игрока I. Игрок I, выбирая стратегию , должен рассчитывать, что игрок II ответит на нее той из своих стратегий , для которой выигрыш игрока I будет минимальным. Найдем минимальное число в каждой строке матрицы и, обозначив его , запишем в добавочный столбец платежной матрицы (см. табл. 4.2):

 

. (4.1)

 

Зная числа (свои выигрыши при применении i-х стратегий и разумном ответе игрока II), игрок I должен выбрать такую стратегию, для которой максимально. Обозначив это максимальное значение как

 

(т.е. и используя (4.1), получим

 

(4.2)

 


Таблица 4.2

II I . . . n
. . .
. . .
. . . . . . . . . . . . . . . . . .
m . . .
. . .  

 

Величина представляет собой гарантированный выигрыш, который может обеспечить себе игрок I; она называется нижней ценой игры (максимином). Стратегия, обеспечивающая получение нижней цены игры , называется максиминной стратегией. Если игрок I будет придерживаться своей максиминной (перестраховочной) стратегии, то ему гарантирован выигрыш, не меньший при любом поведении игрока II.

В свою очередь, второй игрок стремится уменьшить свой проигрыш или, что то же самое, выигрыш игрока I обратить в минимум. В связи с этим, для выбора своей наилучшей стратегии он должен найти максимальное значение выигрыша игрока I в каждом из столбцов и среди этих значений выбрать наименьшее. Обозначим через максимальный элемент в каждом столбце и запишем эти элементы в дополнительной строке табл. 4.2. Наименьшее значение среди обозначим через ; эта величина представляет собой верхнюю цену игры (минимакс), которая определяется по формуле

 

. (4.3)

 

Стратегия игрока II, обеспечивающая «выигрыш» , является его минимаксной стратегией. Выбор минимаксной стратегии игроком II гарантирует ему проигрыш не больше .

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

 

 

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

Общее значение нижней и верхней цены игры в играх с седловой точкой называется чистой ценой игры , а стратегии , позволяющие достичь этого значения, - оптимальными чистыми стратегиями; элемент = является одновременно минимальным в i-й строке и максимальным в j-м столбце. Оптимальные стратегии определяют в игре положение равновесия, поскольку каждому из игроков невыгодно отходить от своей оптимальной стратегии. Чистую цену игры в игре с седловой точкой игрок I не может увеличить, а игрок II ‑ уменьшить. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

Игры без седловых точек

 

Итак, если матрица игры содержит седловую точку, то ее решение находится по принципу минимакса. Рассмотрим методику решения игры, в платежной матрице которой отсутствует седловая точка. Применение минимаксных стратегий каждым из игроков обеспечивает первому выигрыш не меньше , а второму проигрыш не больше. Учитывая, что <, естественно для игрока I желание увеличить выигрыш, а для игрока II - уменьшить проигрыш. Поиск такого решения приводит к применению сложной стратегии, состоящей в случайном применении двух и более чистых стратегий с определенными вероятностями. Такая сложная стратегия в теории игр называется смешанной. Смешанные стратегии игроков I и II будем обозначать, соответственно,

 

и

 

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

 

 

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

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

– Конец работы –

Эта тема принадлежит разделу:

ЛЕКЦИИ ПО ТЕОРИИ ИГР

Вам нужно прочитать лекции разобраться в них и выполнить задания примеры стр в EXCEL Это и будет Ваша контрольная работа Результаты.. ЛЕКЦИИ ПО ТЕОРИИ ИГР..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Матричные игры с нулевой суммой

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

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

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

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги