Матричные игры двух игроков.

Date: 2015-10-07; view: 728.

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

Пусть игрок А располагает чистыми стратегиями , а игрок В – соответственно, чистыми стратегиями . Первый игрок может выбрать любую стратегию , в ответ на которую второй игрок может выбрать любую свою стратегию . Сочетание этих стратегий приводит к некоторому числовому результату («платежу»), который обозначим и будем называть «выигрышем» игрока А. Игра с «нулевой суммой» означает, что при этом «выигрыш» игрока В составит . Матрица порядка называется платежной матрицей или матрицей игры.

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

Величина (1)

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

(2)

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

Принцип, согласно которому игроки выбирают эти стратегии, называется принципом максимина (для игрока А) или минимакса (для игрока В).

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

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

В этом случае оптимальным решением игры для обоих игроков является выбор максиминной (для А) и минимаксной (для В) стратегий.

Задача 27.Игра заключается в том, что игрок А записывает числа 1 (стратегия ), или 2 (стратегия ), или 3 (стратегия ). Игрок В, в свою очередь, может записать числа 1 (стратегия ), 2 (стратегия ), 3 (стратегия ), или 4 (стратегия ). Если оба числа окажутся одинаковой четности, то А выигрывает сумму этих чисел, если – разной четности, то В выигрывает сумму этих чисел. Составьте платежную матрицу, определите верхнюю и нижнюю цену игры и минимаксные стратегии.

Решение. Согласно условию, игрок А выигрывает сумму записанных чисел, если записанные числа будут одной четности. Заметим, что сумма чисел, записываемых игроками, соответствует сумме индексов стратегий. Поэтому игрок А выигрывает, когда сумма индексов стратегий четна (на пересечении стратегий в матрице игры записывается положительное четное число). Выигрыш второго игрока равен нечетной сумме индексов стратегий. Этот выигрыш записывается в матрицу со знаком “–“. Таким образом, матрица игры имеет следующий вид:

		–3		–5	–5
	–3		–5		–5
		–5		–7	–7
					4 –5

Найдем минимально гарантированные выигрыши игрока А при каждой его стратегии: , , . Нижняя цена игры: . Теперь найдем минимально гарантированные проигрыши игрока В при каждой его стратегии: , , , . Верхняя цена игры: . Отсюда следует, что для игрока А максиминными стратегиями являются или . При этих стратегиях ему обеспечен «выигрыш» не менее –5 (то есть проигрыш не более 5). Для игрока В минимаксными стратегиями являются или ; они обеспечивают ему проигрыш не более 4.

Игра седловой точки не имеет.

Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. В этом случае применяют смешанные стратегии.

Смешанной стратегией игрока А называется применение им своих чистых стратегий с определенными частотами (вероятностями): (причем ). Такую стратегию записывают в виде вектора . Вектором ( ) определяется смешанная стратегия игрока В. Здесь есть частота использования игроком В стратегии . Чистые стратегии являются частным случаем смешанной стратегии, задаваемой единичным вектором.

Функцией выигрыша, или платежной функцией игры с матрицей при применении игроком А смешанной стратегии , а игроком В – смешанной стратегии , называется средняя величина выигрыша игрока А (проигрыша игрока В), подсчитываемая по формуле

(3)

Формулу (3) можно записать в матричном виде:

,

где и матрицы-строки координат векторов и .

Стратегии и называются оптимальными, если выполняются неравенства

(4)

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

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

. (5)

В теории игр важную роль играют следующие две теоремы.

Теорема 1(Неймана). Всякая конечная матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

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