![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Решение матричной игры в смешанных стратегиях.
Исследование в матричных играх начинается с нахождения её седловой точки в чистых стратегиях. Если матричная игра имеет седловую точку в чистых стратегиях, то нахождением этой седловой точки заканчивает исследование игры. Если же в игре нет седловой точки в чистых стратегиях, то можно найти нижнюю и верхнюю чистые цены этой игры, которые указывают, что игрок 1 не должен надеяться на выигрыш больший, чем верхняя цена игры, и может быть уверен в получении выигрыша не меньше нижней цены игры. Решение игры достигается путём применения чистых стратегий случайно, с определённой вероятностью. Смешанной стратегией игрока называется полный набор вероятностей применения его чистых стратегий. Таким образом, если игрок 1 имеет m чистых стратегий 1,2,...,m, то его смешанная стратегия X – это набор чисел X = (x1, ..., xm) удовлетворяющих соотношениям xi 0 (i = 1,m), Аналогично для игрока 2, который имеет n чистых стратегий, смешанная стратегия y – это набор чисел Y = (y1, ..., yn), yj 0, (j = 1,n), Чистая стратегия есть частный случай смешанной стратегии. Действительно, если в смешанной стратегии какая-либо i-я чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта i-я чистая стратегия является частным случаем смешанной стратегии. Средний выигрыш игрока 1 в матричной игре с матрицей А выражается в виде математического ожидания его выигрышей E (A, X, Y) = Функцию E (A, X, Y) называют также платежной функцией игры в смешанных стратегиях. Например, для матрицы
Первый игрок имеет целью за счёт изменения своих смешанных стратегий X максимально увеличить свой средний выигрыш Е (А, X, Y), а второй – за счёт своих смешанных стратегий стремится сделать Е (А, X, Y) минимальным, т.е. для решения игры необходимо найти такие X и Y, при которых достигается верхняя цена игры
Аналогичной должна быть ситуация и для игрока 2, т.е. нижняя цена игры должна быть
Оптимальными смешанными стратегиями игроков 1 и 2 называются такие стратегии Xо, Yо соответственно, которые удовлетворяют равенству
Величина Е (А, Xо ,Yо) называется при этом ценой игры и обозначается через . Имеется и другое определение оптимальных смешанных стратегий: Xо, Yо называются оптимальными смешанными стратегиями соответственно игроков 1 и 2, если они образуют седловую точку: Е (А, X, Yо) Е (А, Xо, Yо) Е (А, Xо, Y) Оптимальные смешанные стратегии и цена игры называются оптимальнымрешением матричной игрыв смешанных стратегиях. Основной теоремой матричных игр является теорема Неймана( теорема о минимаксе ) : для матричной игры с любой матрицей А величины
существуют и равны между собой: Другими словами, любая конечная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий. Имеют место следующие утверждения: Утверждение 1.Тройка (Xо, Yо, ) является решением игры G = (Х,Y,А) тогда и только тогда, когда (Xо, Yо, к +а) является решением игры G(Х,Y, кА+а), где а – любое вещественное число, к > 0. Утверждение 2. Для того, чтобы Xо = ( стратегией матричной игры с матрицей А и ценой игры , необходимо и достаточно выполнение следующих неравенств
Аналогично для игрока 2 : чтобы Yо = (
Из последнего свойства вытекает: чтобы установить, является ли предполагаемые (X, Y) и решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (2.1) и (2.2). Найдя неотрицательные решения этих неравенств совместно со следующими уравнениями
получим оптимальное решение матричной игры. Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (2.1) (2.2) и линейных уравнений (2.3). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например для матрицы 3
Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок 1 – чистую максиминная, а игрок 2 – чистую минимаксная). В противном случае хотя бы у одного игрока оптимальные стратегии будут смешанные.
|