Методические указания к выполнению задания

1. Основные понятия и определения. Предмет теории игр

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

Теория определения рационального решения участников конфликта - называется теорией игр.

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

Если в игре участвуют два игрока, то она называется парной (или двух игроков), и множественной (n игроков), если число игроков больше двух. Далее будем рассматривать только парные игры. В такой игре участвуют два игрока - A и B, интересы которых противоположны. Под игрой (процессом игры) будет понимать ряд действий со стороны A и B.

Количественная оценка результатов игры называется платежом.

Парная игра называется игрой с нулевой суммой, или антагонистической, если сумма платежей равна нулю, т.е выигрыш одного игрока равен проигрышу другого. В этом случае для полного задания игры достаточно указать одну из величин. Если, например, a – выигрыш одного из игроков, b - выигрыш другого, то для игры с нулевой суммой b = -a, поэтому достаточно рассматривать, например, a.

Будем рассматривать парные игры с нулевой суммой.

Выбор и осуществление одного из действий, предусмотренных правилами, называется ходом игрока.

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

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

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

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

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

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

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

2. Игры двух игроков с нулевой суммой. Решение в чистых стратегиях

Рассмотрим конечную игру с нулевой суммой.

Пусть игрок А располагает m личными стратегиями: A₁, A₂, …, A_m. Пусть у игрока B имеется n личных стратегий. Обозначим их B₁, B₂, …, B_n. В этом случае игра имеет размерность m×n. В результате выбора игроками любой пары стратегий (A_i, B_j), однозначно определяется исход игры, т.е. выигрыш a_ij игрока А (положительный или отрицательный) и проигрыш ( - a_ij) игрока В.

Предположим, что значения a_ij известны для любой пары стратегий (A_i,B_j).

Матрица А = (a_ij), , элементами которой являются выигрыши, соответствующие стратегиям A_i и B_j, называется платежной матрицей или матрицей игры.

Общий вид платежной матрицы приведен ниже:

Вj Аi	B1	B2	...	Bn
A1	a11	a12	...	а1n
A2	a21	a22	...	а2n
...	...	...	...	...
Am	am1	am2	...	аmn

Строки матрицы А соответствуют стратегиям первого игрока, а столбцы – стратегиям второго.

Эти стратегии называются чистыми.

Обозначим α_i - наименьший выигрыш игрока А при выборе им стратегии A_i для всех возможных стратегий игрока В (наименьшее число в i-ой строке платежной матрицы), т.е. .

Среди чисел α_i ( ) выберем наибольшее . Назовем α – нижней ценой игры или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В.

Итоговую формулу можно записать следующим образом:

.

Стратегия, соответствующая максимину, называется максиминной стратегией.

Аналогичные рассуждения могут быть выполнены и в отношении игрока B.

Игрок B заинтересован в том, чтобы уменьшить выигрыш игрока А.

Выбирая стратегию B_j, он учитывает, что игрок A будет стремиться к максимальному выигрышу.

Обозначим - наибольший проигрыш игрока B при выборе им стратегии B_j для всех возможных стратегий игрока A (наибольшее число в j-ой строке платежной матрицы).

Среди чисел ( ) выберем наименьшее и назовем β верхней ценой игры или минимаксом. Это минимальный гарантированный проигрыш игрока В.

Таким образом:

.

Стратегия, соответствующая минимаксу, называется минимаксной стратегией.

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

Игрок выбирает свои действия, предполагая, что противник будет действовать неблагоприятным образом, т.е. будет стараться "навредить".

Если же верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены v = = называется чистой ценой игры, или просто ценой игры. Максиминная и минимаксная стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность – оптимальным решением, или просто решением игры.

В этом случае игрок А получает максимальный гарантированный (не зависящий от поведения игрока В) выигрыш v, а игрок В добивается минимального гарантированного (не зависящего от поведения игрока А) проигрыша v. Говорят, что решение игры обладает устойчивостью, т.е., если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии.

Пара чистых стратегий A_i и B_j дает оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент a_ij является одновременно наибольшим в своем столбце и наименьшим в своей строке.

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

Пример. Определите нижнюю и верхнюю цену игры, которая задана следующей платежной матрицей:

А=

0,5 0,6 0,8 0,9 0,7 0,8 0,7 0,6 0,6

.

Решение.

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

Таблица - Платежная матрица примера с дополнительными строкой и столбцом

Вj Аi	B1	B2	B3
A1	0,5	0,6	0,8	0,5
A2	0,9	0,7	0,8	0,7
A3	0,7	0,6	0,6	0,6
	0,9	0,7	0,8	= 0,7 = 0,7

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

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

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

Смешанной стратегией игрока А называется применение чистых стратегий А₁, А₂, …, А_m c вероятностями u₁, u₂, …, u_m.

Обычно смешанную стратегию первого игрока обозначают как вектор: U = (u₁, u₂, …, u_m), а стратегию второго игрока как вектор: Z = (z₁, z₂, …, z_m).

Очевидно, что:

u_i ≥ 0, ,

z_j ≥ 0, ,

, .

Чистые стратегии можно считать частным случаем смешанных и задавать вектором, в котором единица соответствует чистой стратегии.

Оптимальное решение игры (или просто - решение игры) – это пара оптимальных стратегий U^*, Z^*, в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v. Цена игры удовлетворяет неравенству:

≤ v ≤ ,

Справедлива следующая основная теорема теории игр.

Теорема Неймана. Каждая конечная игра с нулевой суммой имеет решение в смешанных стратегиях.

Пусть U^* = ( , , ..., ) и Z^* = ( , , ..., ) - пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с вероятностью, отличной от нуля, то она называется активной.

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

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

Рассмотрим игру размера 2x2.

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

Для игры, в которой отсутствует седловая точка в соответствии с теоремой Неймана, оптимальное решение существует и определяется парой смешанных стратегий U^* = ( , ) и Z^* = ( , ).

Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А придерживается своей оптимальной стратегии U^*, то его средний выигрыш будет равен цене игры v, какой бы активной стратегией ни пользовался игрок В. Для игры 2x2 любая чистая стратегия противника является активной, если отсутствует седловая точка.

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

Пусть игра задача платежной матрицей:

A =

a11 a12 a21 a22

.

Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию U^* = ( , ), а игрок В – чистую стратегию B₁ (что соответствует первому столбцу платежной матрицы), равен цене игры v, т.е.:

a₁₁ + a₂₁ = v.

Тот же средний выигрыш получает игрок А, если противник применяет стратегию B₂, т.е. a₁₂ + a₂₂ = v. Учитывая, что + = 1, получим систему уравнений:

a11 + a21 = v, a12 + a22 = v, + = 1.

Решая систему, можно найти оптимальную стратегию U* и цену игры v.

Аналогичная система уравнений может быть получена для определения оптимальной стратегии игрока В:

a11 + a12 = v, a21 + a22 = v, + = 1.

Пример. Найдите решение игры, заданной платежной матрицей:

A =

2 5 6 4

.

Решение. Прежде всего, проверим наличие седловой точки. Для этого найдем минимальные элементы в каждой из строк (2 и 4) и максимальные в каждом из столбцов (6 и 5). Таким образом, нижняя цена игры = max (2, 4) = 4, верхняя цена игры = min (6, 5) = 5. Поскольку ≠ , решение игры следует искать в смешанных стратегиях, при этом цена игры находится в следующих пределах: 4 ≤ v ≤ 5.

Предположим, что для игрока А стратегия задается вектором U = (u₁, u₂). Тогда на основании теоремы об активных стратегиях можно записать систему уравнений:

2 + 6 = v, 5 + 4 = v, + = 1.

Решая систему из трех уравнений с тремя неизвестными, получим: = 2/5, = 3/5, v = 22/5.

Теперь найдем оптимальную стратегию игрока В. Пусть стратегия данного игрока задается вектором Z = (z₁, z₂). Тогда система уравнений, основанная на использовании теоремы об активных стратегиях, запишется следующим образом:

2 + 5 = 22/5, 6 + 4 = 22/5, + = 1.

Решая систему, состоящую из любых двух уравнений, взятых из последней системы, получим = 1/5, = 4/5.

Следовательно, решением игры примера 5.3 являются смешанные стратегии: U^* = (2/5, 3/5), Z^* = (1/5, 4/5), цена игры v = 22/5.

4. Решение игр 2×n и m×2.

Решение игр 2×n и m×2 в смешанных стратегияхсводится к решению игр 2×2 исключениемдоминируемых стратегий и выявлением активных стратегий игрока.

Стратегия игрока А i доминируема, если существует стратегия k,для которого а_ij<=а_kj, для всех . Другими словами, стратегия i первого игрока доминируема стратегией k, выигрыши игрока А будет выше при его стратегии k, независимо от того, какую стратегию выберет игрок В, .

Стратегия игрока B l доминируема, если существует стратегия m, для которого b_im<=b_il, для всех . Другими словами, стратегия l второго игрока доминируема стратегией k, если величина проигрыша игрока B будет ниже, чем при его стратегии m, независимо от того, какую стратегию выберет игрок A, .

На первом этапе решения игр 2×n и m×2 следует исключить из рассмотрения доминируемые стратегии игроков.

Далее определяется две активные стратегии игрока B (для игр 2×n) или игрока А (для игр m×2).

Рассмотрим игру размерности 2×n.

Пусть игра задана платежной матрицей

Вj Аi	B1	B2	...	Bn
A1	a11	a12	...	а1n
A2	a21	a22	...	а2n

Исключим из матрицы доминируемые стратегии игрока B. Пусть после исключения остается k стратегий, т.е. платежная матрица имеет вид:

Вj Аi	B1	B2	...	Bk
A1	a11	a12	...	а1k
A2	a21	a22	...	а2k

Пусть решение игры в чистых стратегиях не существует, т.е. цена игры удовлетворяет неравенству:

≤ v ≤ .

По теореме Неймана существует решение игры в смешанных стратегиях. Существует вектор Z = (z₁, z₂). Тогда из условия

а_1mz₁+ а_2mz₂£v, для всех .

z₁ + z₂=1,

z₁ ³0, z₂³0.

Изобразим графически на плоскости изменение цены игры в зависимости от одного из переменных, z₁ или z₂. Пусть эта переменная будет z₂. На рис 1, приводится область изменений z₂ и v.

Поскольку v – выигрыш первого игрока, игрок будет стремится увеличить свой гарантированный выигрыш за счет изменения z₂. Эта точка С₂ – точка пересечения прямых соответствующие стратегиям «2» и «3» (см. схематический пример). Именно, эти стратегии являются основными для нахождения смешанной стратегии игрока В. Далее для матрицы с двумя столбцами «2» и «3» находим смешанную стратегию, аналогично вышеприведенной схеме для игр 2´2. (см. вышеприведенный пример).

Рассмотрим игру размерности m×2, представленная платежной матрицей.

Вj Аi	B1	B2
A1	a11	a12
A2	a21	a22
...	...	...
Am	am1	am2

Исключим из матрицы доминируемые стратегии игрока А. Пусть после исключения остается k стратегий, т.е. платежная матрица имеет вид:

Вj Аi	B1	B2
A1	a11	a12
A2	a21	a22
...	...	...
Ak	ak1	ak2

Пусть решение игры в чистых стратегиях не существует, т.е. цена игры удовлетворяет неравенству:

≤ v ≤ .

По теореме Неймана существует решение игры в смешанных стратегиях. Существует вектор U = (u₁, u₂). Тогда из условия

а_m1u₁+ а_m2u₂³v, для всех .

u₁ + u₂=1,

u₁ ³0, u₂³0.

Изобразим графически на координатной плоскости изменение цены игры в зависимости одного из переменных, u₁ или u₂. Пусть эта переменная будет u₂. На рис 2, приводится область изменений u₂ и v.

Поскольку v – проигрыш второго игрока, он будет стремиться снизить свой проигрыш за счет изменения u₂, которая определяется верхней ломанной на графике. Эта точка О₃ – точка пересечения прямых соответствующие стратегиям «k» и «2» (см. схематический пример). Именно, эти стратегии являются основными для нахождения смешанной стратегии игрока В. Далее для матрицы с двумя строками «k» и «2» находим смешанную стратегию, аналогично вышеприведенной схеме для игр 2´2. (см. вышеприведенный пример).

4. Решение игр n × m.

В общем случае, игры n×m могут решаться методами линейного программирования.

Пусть игра задана платежной матрицей

Вj Аi	B1	B2	...	Bn
A1	a11	a12	...	а1n
A2	a21	a22	...	а2n
...	...	...	...	...
Am	am1	am2	...	аmn

По теореме Неймана решение игры в смешанных стратегиях всегда существует.

Пусть Z = (z₁, z₂, …, z_n) – стратегия второго игрока. Тогда целью игрока будет определение смешанной стратегии доставляющий минимум цены игры, т.е.

,

при ограничениях

а_k1z₁+ а_k2z₂+…+ а_knz_n£v, для всех .

z₁ + z₂+ … + z_n=1,

z₁ ³0, z₂³0, …, z_n³0.

Пусть U = (u₁, u₂, …, u_m) – стратегия второго игрока. Тогда целью игрока будет определение смешанной стратегии доставляющий минимум цены игры, т.е.

,

при ограничениях

а_1ku₁+ а_2ku₂+…+ а_mku_m≥v, для всех .

u₁ + u₂+ … + u_m=1,

u₁ ³0, u₂³0, …, u_m³0.

Решение игры n × m можно найти с использованием стандартных пакетов оптимизационных программ или «поиском решения» в MS-Excel.

Контрольные вопросы

1. Дайте определение игры, основных понятий, приведите примеры.

2. Когда игра 2-х игроков имеет решение в чистых стратегиях?

3. Поясните сущность седловой точки для игроков.

4. Как определяется решение игры в смешанных стратегиях?

5. В чем особенности решения игр 2×n и m×2?

6. Как определяется решение игры в смешанных стратегиях для игр n×m?