Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Решение матричной игры в смешанных стратегиях.




Читайте также:
  1. I. Решение телеграфных уравнений для линии без потерь
  2. II Решение телеграфных уравнений для линий с потерями.
  3. Аналитическое решение
  4. Билет 40. Линейные однородные уравнения в частных производных первого порядка. Связь решения с первым интегралом. Общее решение.
  5. В какие сроки решение КТС подлежит исполнению?
  6. Видео. Параметры видеофайлов - частота кадров, разрешение, цветовая модель и глубина цвета, соотношение сторон экрана. Потоки и их синхронизация. Компенсация движения.
  7. Влияние ионно-матричных эффектов на разрешение по глубине при измерении профилей концентрации
  8. Вопрос 1) Работа командира батареи (взвода) по подготовке и организации боевых действий. Решение командира батареи. Постановка задач подразделениям.
  9. Вопрос 36 : Методы поиска решения задач. Психологические барьеры , затрудняющие решение.
  10. Вопрос 56. Молодая семья как объект молодёжной политики. Решение жилищной проблемы молодых семей.

 

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

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

Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия X – это набор чисел X = (x1, ..., xm) удовлетворяющих соотношениям

xi  0 (i = 1,m), = 1.

Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y – это набор чисел

Y = (y1, ..., yn), yj  0, (j = 1,n), = 1.

Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии.

Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей

E (A, X, Y) = = X A YT

Функцию E (A, X, Y) называют также платежной функцией игры в смешанных стратегиях.

Например,

для матрицы в смешанных стратегиях

средний выигрыш равен

Первый игрок имеет целью за счёт изменения своих смешанных стратегий X максимально увеличить свой средний выигрыш Е (А, X, Y), а второй – за счёт своих смешанных стратегий стремится сделать Е (А, X, Y) минимальным, т.е. для решения игры необходимо найти такие X и Y, при которых достигается верхняя цена игры

Е (А, X, Y).

Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть

Е (А, X, Y).

Оптимальными смешанными стратегиями игроков 1 и 2 называются такие стратегии Xо, Yо соответственно, которые удовлетворяют равенству



Е (А, X, Y) = Е (А, X, Y) = Е (А, Xо, Yо).

Величина Е (А, Xо ,Yо) называется при этом ценой игры и обозначается через .

Имеется и другое определение оптимальных смешанных стратегий: Xо, Yо называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку:

Е (А, X, Yо)  Е (А, Xо, Yо)  Е (А, Xо, Y)

Оптимальные смешанные стратегии и цена игры называются оптимальнымрешением матричной игрыв смешанных стратегиях.

Основной теоремой матричных игр является

теорема Неймана( теорема о минимаксе ) :

для матричной игры с любой матрицей А величины

Е (А, X, Y) и Е (А, X, Y)

существуют и равны между собой: .

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

Имеют место следующие утверждения:

Утверждение 1.Тройка (Xо, Yо, ) является решением игры G = (Х,Y,А) тогда и только

тогда, когда (Xо, Yо, к +а) является решением игры G(Х,Y, кА+а), где а – любое вещественное число, к > 0.

Утверждение 2. Для того, чтобы Xо = ( ) была оптимальной смешанной

стратегией матричной игры с матрицей А и ценой игры , необходимо и достаточно выполнение следующих неравенств



(j =1,2…,n)

Аналогично для игрока 2 : чтобы Yо = ( , ..., , ..., ) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:

(i =1,2…m)

Из последнего свойства вытекает: чтобы установить, является ли предполагаемые (X, Y) и решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (2.1) и (2.2).

Найдя неотрицательные решения этих неравенств совместно со следующими уравнениями

,

получим оптимальное решение матричной игры.

Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (2.1) (2.2) и линейных уравнений (2.3). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например для матрицы 3 3 имеем систему из 6 неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства

= .

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


Дата добавления: 2015-07-26; просмотров: 13; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.029 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты