<<
>>

14.7. ОБЩИЙ СЛУЧАЙ ИГРЫ ДВУХ^УЧАСТНИКОВ НУЛЕВОЙ СУММОЙ

ч

Теперь мы рассмотрим общий случай игры с платежной матрицей тхп. Гибкое применение матричных и векторных обозначений (см. главы Ни 12) облегчит наше изложение.

Пусть платежная матрица будет А= [ars] (г = 1,2,..., т; s = 1, 2..., п).

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

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

Заданная смешанная стратегия для игрока А тогда представлена вектором

(r= 1, 2, .. т) и 2 ХТ = 1-

г= і

подчиненным существенным ограничениям:

(І)

хг>0

Это включает и специальный случай чистой стратегии:

ХТ= 1 и хг> = 0 (г' = 1, 2, ..т\ г' фг).

В соответствии с выбором г существуют m чистых стратегий. В матричных обозначениях вектор х может быть изображен как вектор-столбец или как вектор-строка:

хг х = К} =

х — [#г] — \х1у Х2, ..., Штрих в обозначении х' показывает, как обычно, транспозицию строк и столбцов.

Таким же образом В выбирает между п стратегиями в соответствии

с вектором (у1% i/2,..., уп), координаты которого подчинены условиям, аналогичным (1). Этот вектор может быть обозначен в форме вектора-столбца У = ІУй} или в форме вектора-строки У'= Ш (« = 1. 2,..., и).

Если А применяет смешанную стратегию х = {хт} и В — смешанную стратегию у = {у3}, то математическое ожидание игры для А будет:

m п

У)=2 2 (2)

г=і S=1

(3)

Символ Е (х, у) теперь показываетг что величина Е является функцией двух векторов х и у, причем 3ta функция выражается через двойную сумму (2), включающую элементы х и у.

В матричном обозначении равенство (2) может быть записано (см. раздел 13.5) как билинейная форма:

Е{х, у) = х'Ау,

Размерности этих трех перемножаемых матриц равны соответственно (1 х m), (т X п) и (п X 1), и их произведение дает скаляр Е (см. 12.6).

Важно рассмотреть множество всех векторов х ={хг}, удовлетворяющих условиям (1). Обозначим это множество через X, тогда «х из X» обозначает один допустимый вектор х из полного множества X. Таким же образом множество всех векторов {ys}, удовлетворяющих условиям, подобным условиям (1), обозначается через У. Когда т=3, вектора х = {хг} (г = 1, 2, 3) могут быть показаны точками {хг,х2, х3) в пространстве трех измерений. Множество X тогда заключает в себе все точки, для которых хг>0„ ж2>0, ?3>0 и хх + х2 + х3 = 1. Это суть точки, которые лежат на части плоскости хх + х2 + х3 = 1, отсекаемой координатными плоскостями. На рис. 49 это показано частью плоскости, АХА<^3, где ОАх = ОА2= ОА3 = 1. Любая точка треугольника представляет собой систему стратегий игрока А; точки Ах, А2 или А3 представляют чистые стратегии; все другие точки представляют смешанные стратегии. Для т > 3 множества X векторов х может мыслиться как множество точек, лежащих на сегменте гиперплоскости в пространстве т измерений.

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

Определение: Если векторы х* и у* могут быть найдены так, что для каждого х из X и у из У

Е(ху у*)< Е (х*, у*)<Я(х*, у),

то есть

х'Ау*< (х*)' Ау*< (х*)' Ау,

то тогда (х*, у*) является седловой точкой для Е, игра имеет устойчивый исход или решение (х*, у*), и и = Е(х*, у*) есть цена игры для игрока А.

Когда х* принимается в качестве оптимальной стратегии для А, то это подразумевает, что оптимальный способ игры для А состоит в том, чтобы придерживаться своих т стратегий с частотами хх*, я2*,..., Хш, где х* есть вектор (хх*, Хт)- Определение показывает, что А выбирает х* пото

му, что в этом случае он может получить по меньшей мере 2?(х*, у*), чтобы ни делал его противник, в то время как всякий другой выбор х делает возможным для его противника удержать выигрыш А на уровне ниже Z?(x*, у*).

Отсюда следует (это было доказано в разделе 14.5): Е(х, у) имеет седло- вую точку (х*, у*) тогда и только тогда, когда

maxmini?(x, у) = min max Е (х, у) = Е(х,* у*).

х у ух

Основные положения теории завершаются затем минимаксной теоремойг

Билинейная форма Е(х, у) = х'Ау такова, что

max min Е (х, у) и min max Е (х, у)

X у ух

существуют и равны.

Специальный случай этой теоремы доказан в разделе 14.5, но общее доказательство здесь не приводится.

Доказательства, данные фон Нейманом и Моргенштерном [8],Вальдом [10, стр. 52—54], сложны. Существуют различные более простые доказательства. Одно из них опирается на применение теоремы Броуера о неподвижной точке преобразования в топологии; это доказательство найдено было Нэшем и приведено в прилож. 2 к [4]. Упрощенное алгебраическое доказательство дано Лумисом в [3]. Минимаксная теорема является частью общематематического фундамента теории игр| и минимаксных теорий решений, имеющих разнообразные применения. Ее значение для теории игр определяется следующим предложением:

Игра двух лиц с нулевой суммой с ожиданием Е(х, у) всегда имеет решение х*, у* — седловую точку для Е{х, у). Игрок А имеет не менее одной оптимальной стратегии (х* из X) и игрок В также имеет не менее одной оптимальной стратегии (у* из У). Цена игры есть v, равное Е(х*, у*), то есть общему значению для max min Е(х, у)

х у

и min max Е(х, у).

у X

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

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

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

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

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

Свойство I.

Если х* и у* являются оптимальными стратегиями для игроков в игре тхп с платежной матрицей А, то они также оптимальны для игры с платежной матрицей (сА + В), где с —положительный скаляр и В—матрица размерности тхп, имеет все элементы, равные скаляру Ъ. Если v есть цена исходной игры, то цена второй игры равна (cv-\-b).

Свойство II. Если игра имеет цену У, ТО х* и у* являются ^оптимальными стратегиями для игроков тогда и только тогда, когда:

а) Z?(x*, у)>?> для каждого у из У, Е (ху*)<у для каждого х из х,

и, следовательно, тогда и только тогда, когда

п т

б) 2 arsytS— І R= 1

для всех r = 1,2, ..., m и s = 1, 2, ..., /г.

Свойство III. Если игра имеет цену v и оптимальные стратегии х* и у*, то для любого г и s (г = 1, 2, ..., т\ s = 1, 2, ..., п):

п

неравенство 2 arSy* < v предполагает х* =. О и

S= 1 га

неравенство 2 arsx* > v предполагает yf = 0. r= і

Условия свойств II и III могут быть выражены в матричном обозначении:

11(a) (х*)'Ау>>и для каждого у из У,

(х)'Ау*<у для каждого х из X, Щб) Ау*< у {1}< А'х*,

где {1} есть вектор-столбец, состоящий из т или п элементов, каждый из которых равен единице.

III. В неравенстве Ау*<а{1} предполагается, что ели для одного какого-либо элемента левая часть строго меньше правой, то соответствующая координата вектора х* равна нулю, аналогично и для неравенства А'х* {1}.

Доказательства этих свойств основываются на определении решения игры и для иллюстрации мы приведем здесь доказательство свойства II (а).

Во-первых, пусть даны оптимальные стратегии х* и у*. По определению:

Е(х, у*)<а = #(х*, у*)<Я(х*, у)

для каждого х из X и у из У, что и требовалось доказать.

Во-вторых, пусть дано Е (х, у*)< ?"(х*, у) для каждого х из X и у из Г. Положим х = х* и у = у*: 2?(х*, у*)< Е (х*, у*), то есть v = E(x*, у*). Тогда 2?(х, у*)<2?(х*, у*)<і?(х*, у) для каждого х из X и у из У, то есть (х*, у*) является по определению седловой точкой функции а х* и у* — оптимальные стратегии.

Что и требовалось доказать.

Один частный случай является достаточно важным, чтобы привести его наряду с более общими свойствами:

Свойство {IV). Если платежная матрица игры квадратная и кососим- метрическая, тогда стратегия, являющаяся оптимальной для одного игрока, будет оптимальной и для другого, и цена игры равна нулю.

Кососимметричность платежной матрицы А показывает, что в игре имеет место симметрия между двумя игроками. Если переменить роли игроков и рассмотреть матрицу платежей, получаемых игроком В, то новая платежная матрица будет равна (—А'), Эта матрица, по определению косо- симметрической матрицы, равна исходной матрице А. Платежные матрицы игроков совпадают, и естественно ожидать, что совпадут и их оптимальные стратегии. Совершенно независимо от этого, игра может быть названа справедливой, если ее цена равна нулю: когда игроки выбирают оптимальные стратегии, то в результате ни один игрок не выигрывает у другого. В этом смысле почти все виды игр, в обычном значении этого слова, включая большинство салонных, являются справедливыми. В частности, для игр, симметричных по отношению к участникам, следует ожидать, что они также будут справедливыми. Например, для описанной в 14.2, пример (е), игры «двух- пальцевая Морра» платежная матрица является кососимметрической: 0 -3 2 0 3 0 0 -4 2 0 0 3 0 4 -3 0 Игра симметрична для игроков; естественно предположить, что она справедлива. Именно это и утверждает свойство IV.

На основании свойства II (б) можно доказать, что каждый игрок имеет в этом случае одну и ту же оптимальную стратегию z*, и цена игры равна О84.

Можно также привести некоторые соображения для игр, не являющихся справедливыми (v Ф 0). Пусть v > 0, так что в результате игрок В при устойчивом исходе проигрывает игроку А некоторую сумму. Почему вообще В будет играть? Действительно, если он знает решение игры, то не видно основания, по которому он должен был бы играть. Но здесь возможно существование компенсирующего соглашения, возможен обратный- платеж от игрока А игроку В в каждой партии рассматриваемой игры.

Встает вопрос: какой платеж делает игру справедливой? Исчерпывающий ответ дается свойством (1). Если А в каждой партии платит сумму, равную v, игроку В, тогда платежная матрица в действительности равна (А — В)г где все элементы матрицы В равны v. Цена игры в этом случае будет (v — v) = = 0. Обратный или компенсирующий платеж v от игрока А игроку^ В делает игру справедливой; В, если он искусен, может играть совершенна спокойно и без убытка для себя.

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

Вектор х принадлежит к множеству X, определенному условиями (I) настоящего раздела. Когда его размерность равна 2, показать, что х является точкой на плоскости Оххх2 и что X включает все точки, лежащие на отрезке прямой линии,* соединяющем лежащие на координатных осях точки Аг и А2, для которых ОЛ1 = 0Л2 = = 1, то есть х есть вектор (х, 1—х) при 0<><;1. 2.

Если вектор х имеет размерность 3, показать, что множество X включает все точки треугольника АгА2Аг, изображенного на рис. 49. Рассмотреть и истолковать случай, когда точки лежат на сторонах треугольника. Показать, что в общем случае х является вектором х2, 1—хг—х2), определяемым двумя такими переменными хъ x2f что точка (#!, х2) принадлежит треугольнику ОАгА2.

I 3.

Пусть х(1) и х(2) —два вектора из Х\ показать, что вектор х = (х(1)+х(2)>

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

4. Игра имеет платежную матрицу 2 х га. Показать, что если (#(1>, 1—#(1)) и (xi2)r 1— я(2)) — пара оптимальных стратегий для игрока А, то стратегия (х, 1-х) также является оптимальной стратегией, если х лежит между ха) и #<2). Вывести, что если существуют две различные оптимальные стратегии, то тогда существует и бесконечное множество оптимальных стратегий. Обобщить вывод для матриц га X га, пользуясь линейной выпуклой комбинацией. 5.

Доказать свойство I. 6.

Вывести свойство II (б) из свойства II (а) и затем доказать свойство III. 7.

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

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

Еще по теме 14.7. ОБЩИЙ СЛУЧАЙ ИГРЫ ДВУХ^УЧАСТНИКОВ НУЛЕВОЙ СУММОЙ:

  1. 14.2. ИГРА ДВУХ УЧАСТНИКОВ С НУЛЕВОЙ СУММОЙ И ЕЕ ПЛАТЕЖНАЯ МАТРИЦА
  2. 14.3. МАТЕМАТИЧЕСКОЕ ОЖИДАНИЕ ИГРЫ; ЧИСТЫЕ И СМЕШАННЫЕ СТРАТЕГИИ
  3. 14.4. МИНИМАКС, СЕДЛОЭЫЕ ТОЧКИ И РЕШЕНИЯ ИГР
  4. 14.7. ОБЩИЙ СЛУЧАЙ ИГРЫ ДВУХ^УЧАСТНИКОВ НУЛЕВОЙ СУММОЙ
  5. 14.8. РЕШЕНИЯ КОНКРЕТНЫХ ИГР
  6. 15.3. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К РЕШЕНИЮ ИГРЫ
  7. 15.5. ЭКВИВАЛЕНТНОСТЬ ОБЩИХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИГРЫ С ДВУМЯ УЧАСТНИКАМИ И НУЛЕВОЙ СУММОЙ
  8. 19.7. ОБЩИЙ СЛУЧАЙ: ОДНО МАКРОСООТНОШЕНИЕ
  9. Когда игра становится грубой
  10. Политика как игра
  11. Лекция 8 Основные положения вещного права и общего учения об обязательствах
  12. Теория ошибок и ошибки теории А.Т.Фоменко
  13. Решения с помощью теории игр
  14. Идеология в глобализирующемся мире
  15. Принцип игры с нулевой суммой
  16. ДВАДЦАТЬ ЛЕТ СПУСТЯ
  17. Верования, обряды, игрьь танцы, устное народное творчество
  18. «Пивная игра»г или Как среда влияет на поведение