Реферат: Теория игр

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

Е (А, х, y ) =Е (А, х, y ) = Е (А, х^о , у^о ).

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

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

Е (А, х, у^о )£ Е (А, х^о , у^о )£ Е (А, х^о , у )

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

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

Теорема (о минимаксе). Для матричной игры с любой матрицей А величины

Е (А, х, y ) и Е (А, х, y )

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

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

Обозначим через G (Х,Y,А ) игру двух лиц с нулевой суммой, в которой игрок 1 выбирает стратегию х Î Х , игрок 2 – y Î U, после чего игрок 1 получает выигрыш А = А (х, y ) за счёт игрока 2.

Определение . Стратегия х¹ игрока 1 доминирует (строго доминирует ) над стратегией х² , если

А (х¹ , y )³ А (х² , y )(А (х¹ , y ) > А (х² , y )), y Î U.

Стратегия y¹ игрока 2 доминирует (строго доминирует ) над стратегией y² , если

А (х, y¹ )£ А (х, y² )(А (х, y¹ ) < А (х, y² )), х Î Х.

При этом стратегии х² и y² называются доминируемыми (строго доминируемыми ) .

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

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

Свойство 2 . Ни одна строго доминируемая чистая стратегия игрока не содержится в спектре его оптимальной стратегии.

Игра G ¢ = (Х ¢,Y ¢,А ¢ ) называется подыгрой игры G (Х,Y,А ), если Х ¢ Ì Х, U ¢ Ì U, а матрица А¢ является подматрицей матрицы А . Матрица А ¢ при этом строится следующим образом. В матрице А остаются строки и столбцы, соответствующие стратегиям Х ¢ и U ¢ , а остальные “вычеркиваются”. Всё то что “останется” после этого в матрице А и будет матрицей А ¢.

Свойство 3 . Пусть G = (Х,Y,А ) – конечная антагонистическая игра, G ¢ = (Х \ х ¢,Y,А ) – подыгра игры G , а х ¢ – чистая стратегия игрока 1 в игре G , доминируемая некоторой стратегией , спектр которой не содержит х ¢. Тогда всякое решение (х^о , y^о , u ) игры G ¢ является решением игры G .

Свойство 4 . Пусть G = (Х,Y,А ) – конечная антагонистическая игра, G ¢ = (Х,Y \ y ¢,А ) – подыгра игры G , а y ¢ – чистая стратегия игрока 2 в игре G , доминируемая некоторой стратегией , спектр которой не содержит y ¢ .Тогда всякое решение игры G ¢ является решением G.

Свойство 5 . Если для чистой стратегии х ¢ игрока 1 выполнены условия свойства 3, а для чистой стратегии y ¢ игрока 2 выполнены условия свойства 4, то всякое решение игры G ¢ = (Х \ х ¢,Y \ y ¢,А ) является решением игры G = (Х,Y,А ).

Свойство 6 . Тройка (х^о , y^о , u ) является решением игры G = (Х,Y,А ) тогда и только тогда, когда (х^о , y^о , к u +а ) является решением игры G (Х,Y,кА+а ), где а – любое вещественное число, к > 0.

Свойство 7 . Для того, чтобы х^о = ( ) была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры u , необходимо и достаточно выполнение следующих неравенств

(j = )

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

(i = )

Из последнего свойства вытекает: чтобы установить, является ли предполагаемые (х, y ) и u решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (*) и (**). С другой стороны, найдя неотрицательные решения неравенств (*) и (**) совместно со следующими уравнениями