4.3. Применение матриц в теории игр

Теория игр – это недавно возникшая область математики, изучающая задачи о выработке оптимальной стратегии в той или иной конфликтной ситуации. Ситуация считается конфликтной, если в ней участвуют противоборствующие стороны, например, следователь и преступник, обвинитель и обвиняемый, группа захвата и задерживаемый. «Враждующие стороны» преследуют противоположные цели, и результат каждого мероприятия одной из сторон зависит от того, какие действия выберет «противник». Рассматриваемые в этой теории схемы охватывают как собственно игры, так и различные ситуации, возникающие из многих практических вопросов: рациональные производственные и экономические решения, вопросы военной тактики, вопросы выбора системы экспериментов.

Первые работы по теории игр были сделаны в 1909 году немецким математиком Э. Цермело (1871–1953). Большой вклад в становление этой теории внес Джон фон Нейман в1928 году: он сформулировал основные идеи и результаты и доказал основную теорему теории игр .значительное внимание задачам теории игр было уделено в годы второй мировой войны и непосредственно после нее.

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

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

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

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

Величина (1)

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

(2)

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

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

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

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

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

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

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

	2	–3	4	–5	–5
	–3	4	–5	6	–5
	4	–5	6	–7	–7
	4	4	6	6	4 –5

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

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

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

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

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

(3)

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

,

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

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

(4)

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

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

. (5)

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

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

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