<<
>>

14.8. РЕШЕНИЯ КОНКРЕТНЫХ ИГР

Когда хотя бы один из участников игры имеет только две стратегии,, то есть когда игра имеет платежную матрицу 2 X п или т X 2, игра всегда может быть решена при помощи приемов, описанных в разделах 14.5 и 14.6.
Как это следует из минимаксной теоремы, игра т X п всегда имеет решение, либо единственное, либо (в худшем случае) бесконечное множество. Следовательно, объект поиска существует, и проблема состоит в том, как его найти.

Введение понятия математического ожидания Z?(x, у) при практическом решении этой задачи, вероятно, не принесет пользы, так как с функцией двух векторов х и у, имеющей вид двойной суммы, вообще нелегко обращаться. Практическая методика нахождения решения должна быть создана на иных путях и разбита на две стадии. Рассмотрим платежную матрицу А = = [яГ8] размерности т X п. На первой стадии матрица уменьшается за счет удаления излишних строк и столбцов (соответствующих стратегиям, никогда не применяемым). Полученную матрицу можем далее, опираясь на свойство 1 из раздела 14.7, привести к более удобному виду (напримерг избавиться от отрицательных и дробных чисел) и, наконец, проверить матрицу на седловую точку, предполагая, что игроки применяют в устойчивом исходе только чистые стратегии. Если существует такая седловая точка, та решение найдено, и ничего больше не надо делать. В противном и более общем случае, необходимо переходить ко второй стадии нахождения решения. Идея здесь состоит в том, чтобы перебрать теми или иными средствами всевозможные мыслимые случаи оптимальных стратегий для каждого игрока и проверить их, опираясь на цену игры. Вот теперь на сцену появляются свойства II, III и IV раздела 14.7. Не следует отказываться ни от одной возможности найти решение, даже непосредственная догадка хороша. Ибо очень простым способом, при помощи свойства И(б), можно проверить, является ли какая-либо пара предлагаемых стратегий оптимальными стратегиями, и таким образом принять ее или отбросить.

Первая стадия нахождения решения нуждается в детальной разра- <ботке. Должны быть даны определения излишних строк и столбцов в матрице А и способ их выявления. Рассмотрим строки матрицы А. Строка может быть исключена как ненужная, если над ней доминирует другая строка в том смысле, что каждый элемент доминирующей строки больше или равен соответствующему элементу исключаемой строки. У игрока А никогда не будет основания для того, чтобы применять стратегию, соответствующую избыточной строке, как в чистом виде, так и в комбинации с другими стратегиями. Пользуясь другой стратегией, то есть доминирующей строкой, игрок А всегда может добиться лучшего или такого же результата. Например, если А = ^ J , то первая строка может быть исключена, и игроку А должно ограничиться рассмотрением только второй, или доминирующей, стратегии. Очевидным обобщением является случай, когда одна строка может быть исключена, если над ней доминирует некоторая выпуклая линейная комбинация других строк. Эта комбинация получается умножением соответствующих строк на положительные дроби, дающие в сумме единицу.

Например, если дана матрица:

"0-1 1" А =

1 1 0

1 -2 2 то комбинация (сумма) половины второй и половины третьей строки дает смешанную стратегию, для которой, при различных чистых стратегиях игрока Б, получения А будут соответственно равны 1, —1/2 и 1.

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

, Г 32-461

L —2 5 -1 2 J '

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

частоты для второй и четвертой стратегии игрока В. Как в примере (г) и на рис. 47 раздела 14.6, оптимальные стратегии игроков будут

•KM)- -

и

•а цена игры v= —— .

о

Пример (б)

Hi-?!]-

Вычеркнуть первый столбец, так как над ним доминируют два других: 1>±(2) + |(0) и 2>1(-1)+J-(3)

Решение получается из ? і 3 J * Оптимальные стратегии суть: а цена игры у = 1, как и в примере (в) раздела 14,6.

Пример (в)

[О 2-1 31 23 1 2. 3 4 О —4 J

Можно вычеркнуть первые два столбца, над которыми доминирует третий, и третыа строку для оставшейся матрицы, над которой доминирует вторая. Наконец, в матрице

С 12] вт0Р°й столбец и первая строка также исключаются, и остается единственный элемент 1. Цена игры есть 1, существует седловая точка и применяются только чистые стратегии из исходной матрицы А: вторая для игрока А и третья для игрока В-

Пример (г)

Г Г

3 3 3 2_ _J_ 3 3

_ JL 1 - з з

Исключить вторую строку, над которой доминирует комбинация (с равными частотами) третьей и четвертой строки. Решение следует находить по оставшейся квадратной матрице 3x3.

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

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

2 0 0"! 0 3 0, 0 0 4J

и для игры с такой матрицей легко найти решение. Исходная игра имеет те* же оптимальные стратегии, что и игра с полученной платежной матрицей. Кроме этого, если цена исходной игры равна v, то новая цена может быть найдена на основании того факта, что цена упрощенной игры равна (Зі; + 1).

На заключительном этапе первой стадии матрицу игры можно проверить на седловую точку, то есть определить, имеет ли игра решение в области чистых стратегий. Целесообразно это сделать до каких-либо преобразований матрицы А; или же можно попытаться найти такое решение для частично или полностью упрощенной (в смысле лишних строк и столбцов, дробных и отрицательных элементов) матрицы. Рассмотрим с этой точки зрения пример (в) настоящего раздела. Минимальные элементы в строках А равны соответственно —1, 1, —4, а максимальные элементы в столбцах будут 3, 4, 1, 3. Следовательно, в соответствии с методом, изложенным в конце разде- ла 14.4, цена игры и равна 1, игрок А применяет только свою вторую, а игрок В — только свою третью чистую стратегию. Этот же результат мы получили раньше путем исключения из матрицы А излишних строк и столбцов.

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

Это иллюстрируется следующим примером.

Пример («д).

Рассмотрим проблему закупки угля, сформулированную в примере (15) из книга Вильямса [11]. Вы имеете следующие данные о количестве и ценах угля, необходимого зимой для отопления вашего дома: Зима Количество угля, m Средняя цена, ф. ст. за 1 m Мягкая 4 7,0 Обычная .... 5 7,5 Холодная .... 6 8,0 Зима мягкая обычная холодная Г-24 -4 -40 ' -30 -30 -38 L-36 -36 -36*. Эти цены относятся к текущим покупкам угля в течение зимы. Летом, однако, уголь может быть куплен по цене 6 фунтов за тонну, и у вас есть место для хранения запаса до 6 тонн. Вы обдумываете три стратегии, выбирая меясду тремя вариантами запасов в 4, 5 или 6 тонн, заготовляемых летом. При этом вы предполагаете докупить недостающее количество (если потребуется) по зимним ценам. Весь уголь, который сохранится до конца зимы, вами в расчет не принимается, так как вы предполагаете оставить ваш дом и не сможете поэтому распоряжаться оставшимся углем. Платежная матрица (в фунтах) тогда, будет иметь вид:

Летний запас (в т) 4 5

6

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

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

Платежная матрица игры З X 3 — это матрица А= [ars] (г = 1, 2, 3; 5 = 1, 2, 3). Пусть цена игры будет v, и пусть (х1У х2, х3) и (у1$ z/2, у3) будут оптимальные стратегии для двух игроков. Тогда, согласно свойству II (б) раздела 14.7, семь неизвестных (иксы, игреки и и) подчинены восьми соотношениям:

х± + х2 + х3=1 Уі + У2 + Уз= 1 а11хх + «21^2 + Ч\хъ > V аг1ух + а12у2 + а13у3 < v а12х± + а22хг + а32х3 > v а21уг + а22у2 + а23у3 < v

+ «23^2 + aS3X3 > V . а>ЗіУі + «32^2 + ЧъУъ < v Кроме того, еще имеются ограничения, требующие неотрицательности всех хТ и ys. Смысл соотношений ясен. Выражение {а11х1 + а21х2 + а31х3) является математическим ожиданием выигрыша игрока А, когда он при- меняет свою оптимальную стратегию (хг, х2, х3), а игрок В — свою первую чистую стратегию. Следовательно, поскольку А придерживается своей оптимальной стратегии, вне зависимости от того, какую чистую стратегию выбирает В, выигрыш для А должен быть не менее v. Это остается справедливым, как бы игрок В не смешивал свои стратегии. Точно таким же образом, если В применяет свою оптимальную стратегию, то несущественно, какую -стратегию выбирает А в том смысле, что В никогда не проигрывает больше, чем и. В этом состоят ограничения при любых мыслимых оптимальных стратегиях и любой мыслимой цене игры. Эти условия должны автоматически выполняться.

Положение таково, что имеется больше соотношений, чем переменных, и среди соотношений есть неравенства. Но проблема состоит не в том, чтобы перечислить уравнения и затем решить их. Напротив, это не является нашей ближайшей целью; не все соотношения являются уравнениями, но если бы это было так, их подсчет показал бы, что уравнений «слишком много».

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

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

Имея это в виду, можно с новых позиций посмотреть на решение (оптимальную стратегию для игрока А) в случае игры с матрицей 2 X п, который проиллюстрирован, например, на рис. 48. Если оптимальной стратегией для А является (#!, х2), тогда имеется одно уравнение (хг + х2 = 1) и п неравенств относительно Хх и х2. Положим хг = X И х2 = 1 — X) в результате получим П неравенств относительно одного переменного Х и цены игры V. Любые два из них, записанные в виде уравнений, служат для определения величины х и и, но они могут противоречить другим из п соотношений или х может оказаться отрицательным. Графический метод, использованный на рис. 48, состоит в том, что все соотношения записывают как уравнения, затем изображают их в виде прямых линий, показывающих изменение и в зависимости от х, лежащего между 0 и 1, выбирают наименьшее v для каждого х и, наконец, определяют х для наибольшего из этих минимизированных v. Если игра имеет единственное решение, х находится решением двух уравнений и чертеж показывает, какими именно.

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

метода для случая 3x3 дано в [И, стр. 91 —98]. Примененный здесь метод является прямым подходом к решению вопроса, какие соотношения записываются в виде уравнений, и он выявляет важность свойства III, описанного в разделе 14.7. Метод можно объяснить на примере восьмиксоотношений между семью переменными, полученными для игры с платежной й матрицей 3x3.

Сначала запишем все восемь соотношений в виде уравнений, решим любые семь из них относительно входящих в них переменных, проверим неотрицательность переменных хт и ys и посмотрим, удовлетворяется ли также восьмое уравнение. Если это так, то решение получено. Если не так, то переходим к следующему приему. Выберем какое-либо соотношение и запишем его как строгое неравенство, а другие семь как уравнения. Если одно из соотношений между я'ами выполняется как строгое неравенство, то соответствующий ys равен нулю, что следует из свойства III раздела 14.7, Теперь мы имеем семь уравнений относительно шести переменных (нулевой ys будет исключен), и процесс повторяется. В конце концов, рассматривая некоторую совокупность уравнений, найдем решение относительно тех переменных, которые не должны быть равны нулю по свойству III. Изложенный метод иллюстрируется далее на реальном примере в разделе 14.9.

Мы можем пока продолжить дальнейшее изложение практических методов поиска решения, основанных на неравенствах свойства II (б) и условиях свойства III. Если соотношение между переменными х имеет место в форме

і т

«больше V» > тогда соответствующий у$ равен нулю, то есть,

г= 1

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

п

ys в форме «меньше и» (%arsys < v) справедливо аналогичное утвержде-

s=l

ниє. Если эти случаи исключены, то остается множество соотношений между я'ами и между г/'ами, в которых левые части равны v. Это относится к оптимальным хг и г/8, которые не равны нулю, то есть к стратегиям, которые применяются в устойчивом исходе. Таким образом, если А применяет свою оптимальную смешанную стратегию, тогда любая чистая стратегия, проводимая В, дает платеж игроку Л, равный точно v, при условии, что эта чистая стратегия является одной из стратегий, включаемых В в его оптимальную смесь. В этом смысле, пока А играет как следует, безразлично, как играет В. Аналогично, когда В придерживается своей оптимальной стратегии, безразлично, как играет А, выбирая чистые стратегии для своего оптимального смешивания. Это приводит к простейшему способу контроля оптимальности любых предлагаемых стратегий для того и другого игрока. Если взять оптимальную смесь стратегий для игрока А и оценить ее для каждой из чистых стратегий, применяемых В в своей оптимальной смеси, то в каждом случае в результате получим одинаковый платеж игроку А. Аналогично этот же платеж (v) мы найдем, оценивая оптимальную смесь для В для каждой из чистых стратегий, применяемых игроком А.

Задачи и упражнения

Г 121 1.

Если А= —1 0 , показать, что вторая строка' излишня. Затем решить

L і з]

игру и^сравнить с упражнением 4 (к 14.4) и упражнением 5 (к 14.6). 2.

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

ГО 3 —31 А=I3 9 —6

2

433

28 Р. Аллен

имеет цену ! а оптимальные стратегии И), — , для А и (о, A f -|ЛДЛЯВ.

3. Упростите матрицу предыдущего упражнения, исключив отрицательные" элементы. Решите преобразованную игру, а затем по цене последней найдите цену исход — 1 1 11 ;-И-

ной игры =

исключая сначала положительные эле

4. Решите игру с А= I менты. Это наводит на мысль, что является ценой игры.

5. Взять А в той же форме, как в предыдущем упражнении, но порядка п.

/1 1 1 \

Пользуясь свойством II (б), из 14.7, покажите, что стратегия ( — , )

является оптимальной для каждого игрока, т. е. все численности равны. Почему вы могли ожидать этого? Выведите, что цена игры равна . "3 О

-4

6. Игра имеет матрицу А =

. Упростите А, избавившись от отрица 4-'. Ґ 3 2 \

( 0, , -g- ) . Какова оптимальная стратегия для игрока А? 7. Показать, что игра с А=|

тельных и дробных элементов и исключив лишний столбец. Решить графически полученную игру с матрицей. (3x2) и показать, что оптимальная стратегия дляJB будет

имеет седловую точку.

-3 3 —1 01 12 0 1 _ 3-2-4 -l]

8. Показать на примере платежной матрицы А =

Вывести, что при устойчивом исходе игроки выбирают чистые стратегии и что» игра справедлива. 1 1

2 1 1"

2 —2 0 1

2 — 2 2 1

2 1 1

2 1

о — 1 1 — 1 , что воз

можны'многочисленные седловые точки. Каково решение игры, и как оно может быть истолковано? Какой компенсирующий платеж должен игрок А делать игроку В в каждой партии?

<< | >>
Источник: Р. Аллен. МАТЕМАТИЧЕСКАЯ ЭКОНОМИЯ. 1963

Еще по теме 14.8. РЕШЕНИЯ КОНКРЕТНЫХ ИГР:

  1. Решения с помощью теории игр
  2. 14.4. МИНИМАКС, СЕДЛОЭЫЕ ТОЧКИ И РЕШЕНИЯ ИГР
  3. 14.6. ГРАФИЧЕСКОЕ РЕШЕНИЕ ДЛЯ ИГР С ПЛАТЕЖНОЙ МАТРИЦЕЙ 2 х п
  4. Конкретный характер мышления. Переход от конкретного к обобщенному. Непоследовательность мышления. Некритичность суждений.
  5. ГЛАВА 14 ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ИГР
  6. Занятие 13.5 ПРОЕКТИРОВАНИЕ ДЕЛОВЫХ ИГР
  7. 14.1. ЭКОНОМИЧЕСКИЕ ПРИМЕНЕНИЯ ТЕОРИИ ИГР
  8. ПРАВИЛА РУССКИХ БИЛЬЯРДНЫХ ИГР
  9. 1. ПСИХОЛОГИЯ ОПАСНЫХ ИГР И ЛОВУШЕК.
  10. Место Олимпийских игр в жизни греков
  11. Абстрактное и конкретное.