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

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

Определение. Смешанной стратегией I-го игрока, имеющего K чистых стратегий (1, 2, ¼, K), называется полный набор вероятностей ( P1, P2, ¼, Pk) применения его чистых стратегий.

Следовательно, если у первого игрока имеется N чистых стратегий, то его смешанной стратегией X является набор чисел X = (X1, ¼, Xn), удовлетворяющих условиям:

, , . (3.9)

Для второго игрока, имеющего M чистых стратегий, его смешанной стратегией Y является набор чисел Y = (Y1, ¼, Ym), удовлетворяющих условиям

, , . (3.10)

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

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

Зная смешанные стратегии обоих игроков в матричной игре A, можно рассчитать средний выигрыш первого игрока в этой игре

. (3.11)

Поскольку средний выигрыш в матричной игре A есть функция двух смешанных стратегий, то первый игрок, изменяя свою смешанную стратегию X, будет стремиться довести средний выигрыш до верхней цены игры

, (3.12)

Где X и Y – соответственно множества возможных смешанных стратегий первого и второго игроков.

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

. (3.13)

По аналогии с матричными играми, имеющими седловые точки в чистых стратегиях, возникает вопрос о наличии подобных решений матричных игр с помощью смешанных стратегий. Ответ на этот вопрос дает основная теорема матричных игр, впервые доказанная Нейманом.

Теорема 3.2. Основная теорема матричных игр. Для матричной игры с любой конечной матрицей A нижняя и верхняя цены игры, соответственно a и b, существуют и равны между собой.

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

По аналогии с неравенствами (3.6) для оптимальных чистых стратегий для оптимальных смешанных стратегий , матричной игры A выполняются неравенства

, (3.14)

Где X и Y произвольные смешанные стратегии первого и второго игроков.

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

Теорема 3.3. Для того, чтобы смешанные стратегии и были оптимальными смешанными стратегиями соответственно первого и второго игроков в матричной игре A с ценой игры V, необходимо и достаточно выполнение следующих соотношений:

, ; (3.15)

; (3.16)

, ; (3.17)

. (3.18)

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

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

Неравенства (3.15) и (3.17) совместно с уравнениями (3.16) и (3.18) могут использоваться не только для проверки оптимальности смешанных стратегий обоих игроков, но и для определения оптимальных стратегий. Для этого необходимо только решить линейные неравенства (3.15) и (3.17) совместно с уравнениями (3.16) и (3.18).

Воспользуемся соотношениями (3.15) – (3.18) для аналитического определения решения матричной игры A порядка 2 ´ 2 для случая, когда она не имеет решений в чистых стратегиях. Для матричной игры порядка 2 ´ 2 неравенства (3.15) и (3.17) превращаются в равенства. Для доказательства этого утверждения воспользуемся следующей вспомогательной теоремой.

Теорема 3.4. Пусть задана матричная игра A с ценой игры V и оптимальными смешанными стратегиями соответственно первого и второго игроков , , тогда, если для некоторой стратегии I первого игрока будет выполняться неравенство

, (3.19)

То ;

Если для некоторой стратегии J второго игрока будет выполняться неравенство

, (3.20)

То .

Доказательство. Предположим, что для некоторой стратегии I первого игрока справедливо неравенство (3.19), однако , тогда левую и правую часть неравенства (3.19) можно умножить на

. (3.21)

Для оптимальной смешанной стратегии второго игрока по теореме 3.3. справедливы неравенства (3.17)

, . (3.22)

Из выражения (3.22) следуют следующие N неравенств

, .

Суммируя левые и правые части этих неравенств, получим

. (3.23)

Так как справедливо неравенство (3.21), то второе слагаемое в правой части неравенства (3.23) строго больше второго слагаемого в его левой части, поэтому имеем

Или

,

Что приводит к противоречию, следовательно, .

Аналогично доказывается и вторая часть теоремы.

Теперь докажем теорему о том, что для матричной игры порядка 2 ´ 2 соотношения (3.15) и (3.17) превращаются в равенства.

Теорема 3.5. Пусть задана матричная игра порядка 2 ´ 2 , не имеющая решения в чистых стратегиях, тогда для оптимальных смешанных стратегий и справедливы соотношения:

(3.24)

(3.25)

Доказательство. Согласно теореме (3.3) для оптимальных смешанных стратегий , матричной игры A должны выполняться соотношения (3.15) – (3.18):

(3.26)

(3.27)

Предположим, что оба неравенства из соотношений (3.26) будут строгими:

Тогда по вспомогательной теореме 3.4 должно выполняться условие , что противоречит равенству в соотношениях (3.27).

Аналогично доказывается, что не могут быть строгими оба неравенства их (3.27).

Теперь предположим, что только одно из неравенств (3.26) является строгим, например, первое. В этом случае по теореме 3.4 получим, что и, следовательно, . При данных компонентах смешанной стратегии из соотношений (3.27) получим

(3.28)

Поскольку доказано, что в соотношениях (3.26), (3.27) не может быть по два строгих неравенства, положим, что только одно из неравенств (3.28) является строгим. Однако по теореме 3.4 это приводит к тому, что одна из компонент смешанной стратегии равна нулю, а вторая, следовательно, равна единице. Учитывая, что и , получим, что матричная игра имеет решение в чистых стратегиях, а это противоречит условию теоремы. Таким образом, ни одно из неравенств (3.28) не может быть строгим, следовательно, . Подставим эти значения коэффициентов в первые два соотношения (3.26), учитывая, что в ходе доказательства было предположено, что первое из неравенств является строгим, а второе неравенство (3.26) превратилось в равенство:

(3.29)

Соотношения (3.29) имеют бесчисленное множество решений, что противоречит основной теореме матричных игр. Таким образом, предположение о том, что первое из неравенств (3.26) может быть строгим, не выполняется. Аналогично доказывается, что не может быть строгим и второе неравенство в соотношениях (3.26), а также, что не может быть строгим ни одно из неравенств соотношений (3.27).

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

(3.30)

(3.31)

. (3.32)

Пример 3.5. Рассмотрим решение игры из примера 3.1, матрица которой следующая:

.

Определим нижнюю и верхнюю чистые цены игры a и b:

;

.

Поскольку a ¹ b, то седловой точки в чистых стратегиях в этой игре нет. Поэтому воспользуемся выражениями (3.30) – (3.32):

.

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

Соотношения (3.15) – (3.18) позволили найти удобный способ решения матричных игр порядка 2 ´ 2. Однако их использование для определения решений матричных игр порядка 3 ´ 3 и больше много сложнее, поскольку приходится решать большое число систем, состоящих из строгих неравенств и уравнений, прежде чем удается найти решение матричной игры. Проиллюстрируем это следующим примером.

Пример 3.6. Определить решение матричной игры

.

Нетрудно проверить, что для этой матричной игры нижняя и верхняя чистые цены игры не совпадают:

;

.

Поэтому решение в чистых стратегиях отсутствует и его необходимо искать в смешанных стратегиях. Воспользовавшись выражениями (3.15) – (3.18) теоремы 3.3, получим следующую систему неравенств и уравнений:

(3.33)

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

То по теореме 3.4 получим и подсистема уравнений относительно компонент смешанной стратегии второго игрока примет вид:

Эта система уравнений является несовместной. Аналогичная ситуация возникает при замене любого одного нестрогого неравенства в системе (3.33) на строгое и превращении всех оставшихся неравенств в уравнения.

Затем необходимо из системы (3.33) получать системы, имеющие два строгих неравенства и шесть уравнений. Последовательный перебор таких систем приводит к соотношениям (3.34):

(3.34)

Так как и , то по теореме 3.4 имеем, что и . Подставив эти значения в систему (3.34) получим следующую систему уравнений:

Эта система уравнений распадается на две подсистемы, решая каждую из них, получим:

; ; ;

; ; .

Окончательно имеем:

; ; .

Из рассмотренного примера 3.6 видно, что метод решения матричных игр на основе соотношений (3.15) – (3.18) теоремы 3.3 даже для матриц небольшого размера требует значительных объемов вычислений. Поэтому для решения матричных игр необходимы более совершенные методы.

Нередко при определении решения матричной игры можно существенно уменьшить объем вычислений, если выявить превосходство одних стратегий над другими. Рассмотрим вначале две стратегии P и Q первого игрока.

Определение. Стратегия P первого игрока в матричной игре A доминирует или превосходит стратегию Q, если выполняются соотношения

, , (3.35)

Причем, хотя бы одно из неравенств (3.35) является строгим.

Аналогично определение доминирования одной стратегии над другой для второго игрока.

Определение. Стратегия K второго игрока в матричной игре A доминирует или превосходит стратегию J, если выполняются соотношения

, , (3.36)

Причем хотя бы одно из неравенств (3.36) является строгим.

Замечание. Изменение знака в неравенствах (3.36) по сравнению с неравенствами (3.35) связано с тем, что для первого игрока исходная матрица A является матрицей выигрышей, а для второго игрока – матрицей убытков.

Из соотношений (3.35) следует, что если стратегия P доминирует стратегию Q, то первому игроку не выгодно применять стратегию Q, т. е. доминируемая стратегия должна входить в оптимальную смешанную стратегию с нулевой вероятностью (). В связи с этим из исходной матрицы A можно вычеркнуть строку Q и получить матрицу с числом строк на единицу меньше. Если в матрице также имеются доминируемые стратегии первого игрока, то аналогичным образом можно уменьшить число строк и матрицы . Аналогичным образом за счет доминирования стратегий второго игрока можно уменьшить и число столбцов исходной матрицы.

Пример 3.7. Решить матричную игру со следующей матрицей

.

Проанализируем матрицу A. Вторая стратегия первого игрока доминирует его четвертую, поскольку по соотношениям (3.35) все четыре неравенства для стратегий 2 и 4 являются строгими: 7 > –9; 2 > 0; 6 > 3; –2 > –10. В связи с этим четвертая стратегия первого игрока должна входить в смешанную стратегию первого игрока с нулевой вероятностью. Поэтому ее можно удалить из матрицы A. В результате получим матрицу A1

.

Вторая стратегия второго игрока доминирует его третью стратегию, поскольку по соотношениям (3.36) все три неравенства для стратегий 2 и 3 являются строгими: –3 < 4; 2 < 6; – 4 < – 1. В связи с этим второму игроку нет смысла применять свою третью стратегию и она должна входить в смешанную стратегию с нулевой вероятностью, а размер матрицы A1 можно уменьшить, удалив третий столбец

.

Аналогично, учитывая, что вторая стратегия второго игрока доминирует его первую, из матрицы A2 можно получить матрицу A3

.

Из этой матричной игры нетрудно получить матричную игру порядка 2 ´ 2, поскольку первая стратегия первого игрока доминирует его третью стратегию

.

Полученную игру несложно решить с помощью соотношений (3.30) – (3.32).

< Предыдущая		Следующая >