ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2014, том 50, № 1, с. 110-116
= методы оптимизации
приближенный метод решения конечной игры
трех лиц
© 2014 г. Е.Г. Гольштейн
(Москва)
Описан численный алгоритм решения конечной бескоалиционной игры трех лиц в смешанных стратегиях. Алгоритм основан на минимизации некоторой функции, которая имеет большое число локальных минимумов, и опирается на линейное программирование.
Ключевые слова: бескоалиционная игра, точка Нэша, конечная игра, чистая стратегия, смешанная стратегия, игра с выпуклой структурой, вариационное неравенство.
Классификация JEL: С02, С72.
Рассмотрим бескоалиционную игру Г трех лиц, которая определяется множествами Х1, Х2, Х3 стратегий игроков и функциями/х,/2, /3 их выигрышей. Предполагается, что - подмножество евклидова пространства Ег, функция / определена вещественными значениями на множестве
X = X X х2 X Х3, г = 1, 2, 3, Е = Ех X Е2 X Е3.
Пусть X* С X - множество точек Нэша игры Г. В предположении супердифференцируемости функции/ по хг е Xi, г = 1, 2, 3, с игрой Г можно связать точечно-множественнное отображение ТГ: X" Е, определяемое соотношением
ТГ(х) = {X = (¿1, ¿2, Гз): - и е д/(х), г = 1, 2, 3 }, х е X, (1)
где дх/(х) - супердифференциал / по хг в точке х. Отображение ТГ порождает вариационное неравенство
X е ТГ(х), х е X, (х, х' - х) >0 Ух' е X. (2)
Под решением вариационного неравенства (2) понимается такая точка х* е X, что для некоторого X* е ТГ(х* X) и любых точек х' е X имеет место неравенство (X*, х' - х* ) >0. Из определения точки Нэша вытекает, что множество решений вариационного неравенства (2) совпадает с множествомX* точек Нэша игры Г.
Игра Г трех лиц называется выпуклой, если функции/1, /2, /3 и множество X удовлетворяют следующим требованиям: функция / определена и непрерывна на множестве X! X X2 X Xз, вогнута по х1 е X1 при любых х2 е X2, х3 е Xз, функция/ определена и непрерывна на множестве X} X ^^ X Xз, вогнута по х2 е при любых хг е X1, х3 е X3, функция / определена и непрерывна на множестве X1 X X2 X X3, вогнута по х3 е X3 при любых х! е X1, х2 е X2, X- выпуклый компакт, Лг - выпуклое открытое множество, содержащее X, г = 1, 2, 3. Любая выпуклая игра Г имеет непустое множество Х* точек Нэша и, кроме того, отображение ТГ, задаваемое соотношением (1), полунепрерывно сверху на X, причем и х е XTг( х) - ограниченное множество. Однако множество X * точек Нэша выпуклой игры может быть и невыпуклым.
Дальнейшее сужение класса бескоалиционных игр связано с понятием "выпуклая структура игры". Будем говорить, что выпуклая игра Г трех лиц имеет выпуклую структуру, если связанное с ней согласно (1) отображение ТГ обладает свойством монотонности, т.е. для любых х', х" е X, X' е Тг(х'), X" е Тг(х") справедливо неравенство (X' - X", х' - х" ) > 0. У игры с выпуклой структурой множество точек Нэша представляет непустой выпуклый компакт.
Рассмотрим вариационное неравенство
t ! T(u), u ! G, G t, u' - u H > 0 6u' ! G, (3)
которое порождается точечно-множественным отображением Т точек множества G в подмножества некоторого евклидова пространства, содержащего G.
При анализе вариационного неравенства (3) используются следующие допущения относительно отображения T.
1. Множества G, T(u) 6u ! G - выпуклые компакты; отображение T полунепрерывно сверху на G, т.е. если u0 = limi^3ui, ui ! G, t0 = limi^3 ti, ti ! T(ui), то t0 = T(u0); множества T(u), u ! G, равномерно ограниченны.
2. Отображение T является монотонным.
В (Гольштейн, 2002) описан численный метод решения вариационного неравенства (3) и показано, что при соблюдении двух допущений, приведенных выше, метод порождает последовательность, сходящуюся к множеству решений вариационного неравенства (3), причем скорость сходимости допускает теоретическую оценку, указывающую на достаточную эффективность метода. Игра Г трех лиц, имеющая выпуклую структуру, удовлетворяет условиям 1 и 2, поэтому для ее решения может быть использован отмеченный выше численный метод.
Отметим установленное в (Гольштейн, 2009а) условие, при соблюдении которого выпуклая игра имеет выпуклую структуру: функция f1(x1, x2, x3) выпукла относительно (x2, x3) ! X2 X X3 при любом фиксированном x1 ! Xb функция f2(x1, x2, x3) выпукла относительно (xj, x3) ! Xj X X3 при любом фиксированном x2 ! X2, функцияf3(x1, x2, x3) выпукла относительно (x1, x2) ! X1 X X2 при любом фиксированном x3 ! X3, функция суммарного выигрыша всех игроков f(x) = f1(x) +f2(x) +f3(x) вогнута относительно x ! X = X1 X X2 X X3.
Сформулированное условие является лишь достаточным, для того чтобы выпуклая игра Г имела выпуклую структуру, но, как будет следовать из дальнейшего, заведомо не необходимым.
Введем функцию
3
N(x) = N(xj, x2, x3) = /maxf (xj, x2, x3) - f(x), (4)
г = 1" ! x
3
определенную на множестве X = Х1 X Х2 X Х3, где /(х) = //(х). Очевидно, что при любом х ! X имеет место неравенство 1 = 1
maxf(xj, x2, x3)- f(x1, x2, x3)> 0, i = 1, 2, 3. (5)
Xi! Xi
Из определения точки Нэша игры Г вытекает, что x* ! X* в том и только в том случае, если все три неравенства (5) обращаются в равенства при x = (x 1, x2, x3) = x*. Следовательно, множество X* точек Нэша игры Г совпадает с множеством точек минимума функции N(x) наX. Таким образом, решение игры Г оказывается эквивалентным поиску точек глобального минимума функции N(x) на множестве X, причем значение глобального минимума N на X равно нулю. Заметим, что значение функции N(x) при любом x ! X является естественной мерой отклонения набора стратегий x от множества X *. Функция N(x) была введена в работе (Mills, 1960) для случая, когда Г - биматричная игра.
Далее мы сосредоточим свое внимание на конечных бескоалиционных играх трех лиц, в которых каждый игрок имеет конечное число стратегий. Для описания таких игр удобно пользоваться таблицами, элементы которых нумеруются при помощи индексов sl, s2, s3, принимающих значения от единицы до nb n2, n3 соответственно, где ni - число стратегий игрока i, i = 1, 2, 3.
Рассмотрим конечную игру трех лиц, в которой функция выигрышей игрока i задается таблицей Ai = a a S;)s2 s3), где a S^ s3 - выигрыш игрока i в предположении, что игрок a выбирает страте-
гию ;a, а = 1, 2, 3. Если расширить множества стратегий игроков за счет смешанных стратегий, то приходим к выпуклой игре Г с тремя участниками, в которой
X =
пг
хг (хг1, •••, х1п1 : ^ ' х1я1 1, хгХ1 > 0, 1, •••, Пг
«г = 1
щ П2 П3
/(х) = а« ^«3х 1^1 х2«2х3«3, г = 1 2, 3; (6)
«1 = 1 52 = 1 53 = 1
х = (х 1, х2, х3) е X = X^í X X2 X Xз.
Заметим, что в случае конечной игры Г в смешанных стратегиях, определяемой соотношениями (6), отображение ТГ является точечно-точечным, поскольку / линейно зависит от хг. В интересующем нас случае конечной игры Г трех игроков в смешанных стратегиях вычисление функции Щ(х) в любой точке х еX может быть упрощено. Действительно, если/, X;, г = 1, 2, 3, определяются соотношениями (6), то
п2 п3
х\е Xl 1 < < п1
тах/1(х 1, X2, х3 ) = тах / / а5152«3 х2«2 х3«3 ,
«2 = 1 «3 = 1 п1 п3
(2)
х3
тах/2(хЪ X2, х3 ) тах ^^ ^^ а«1^2«3 х1« 1 х3«3 , х2 еX2 1 < «2 < П2
«1 = 1 «3 - 1 п1 п2
тах/3(хl, х2, х3 )- тах // аS3S2«3 х 1«1 х2«2 .
х3е Xз 1 < «3 < п3^г1 ^
Отсюда и из (4) с учетом (6) получаем
п2 п3
1 «2 «3 х 1«1 х 3«3 +
N(х) = тах // а ^ «3 х^ х^ + тах // а ^
1 < < П1«2= 1 «3 - 1 1 < «2 < % - 1 «3 -1
п1 п2 п1 п2 п3
+ тах ^^ ^^ а^ «3 х 1«2 х2«2 - ^^ ^^ ^^ а«1 «2 «3 х 1« 1 х2«2 х3«3, (7)
1 < «3 < П3 л,,
«1 - 1 «2 - 1 «1 - 1 «2 = 1 «3 = 1
3
где а.ц «2«3 - /а;гl);2«3 для всех ;l, ;2, ^
-1
Для класса игр, множества стратегий и функции выигрышей которого задаются соотношениями (6), в работе (Гольштейн, 2009а) установлены необходимые и достаточные условия, для того чтобы соответствующая игра Г имела выпуклую структуру: конечная бескоалиционная игра Г трех лиц в смешанных стратегиях, задаваемая соотношениями (6), имеет выпуклую структуру в
том и только в том случае, если таблицы Аг - ^а;г1);2^ могут быть представлены в виде
Аг - А ц + А г2 + А,3, г- 1, 2, 3, (8)
где элементы а;г1);2«3 таблицы Ау зависят лишь от индексов ;i и у если г Ф у, и не зависят от индекса ; , если г - у, причем
А 12 +А 21 - А 13 +А 31 - А 23 +А 32 - ° (9)
где О - таблица, все п1п2п3 элементов которой равны нулю.
Сравним необходимые и достаточные условия наличия выпуклой структуры у конечных игр в смешанных стратегиях с приведенными выше достаточными условиями. В работе (Гольштейн,
0П1 A 12 A 13
A = - Ax л 12 Оп2 A 23
- Ax Л 13 - Ax 23 On3°
2012) установлено, что эти достаточные условия применительно к классу игр, определяемых соотношениями (6), помимо необходимых и достаточных условий включают следующее ограничение: каждая из таблиц А11, А22, А33, элементы которых зависят от двух индексов, допускает представление в виде суммы двух таблиц с элементами, зависящими лишь от одного индекса.
Элементы таблиц А^ из соотношения (9) зависят только от двух индексов. Поэтому эти таблицы определяются соответствующими матрицами, которые мы обозначим А у. Соотношения (9) в терминах этих матриц имеют вид
А 21 =- А А 31 =- А ^ А 32 = - А 23,
где х обозначает операцию транспонирования.
Введем кососимметричную матрицу А порядка п1 + п2 + п3 вида
(10)
где по диагонали стоят нулевые квадратные матрицы Опсоответствующих порядков.
Рассмотрим антагонистическую игру Я, в которой множества стратегий обоих игроков одинаковы и совпадают с множеством X = Х1 X Х2 X Х3 из (6), а функция выигрышей первого игрока представляет билинейную функцию ХА(х")х, х', х" ! X, где А - кососимметричная матрица (10).
Как установлено в (Гольштейн, 2012), седловое множество антагонистической игры Я совпадает с X* X X*, где X * - множество точек Нэша игры Г, которая определяется соотношениями (6), причем таблицы А1, А2, А3, в этих соотношениях удовлетворяют требованиям (8), (9), гарантирующим наличие выпуклой структуры у игры Г. Таким образом, решение конечных игр, имеющих выпуклую структуру, сводится к анализу простейших антагонистических игр. Заметим, что анализ антагонистической игры Я легко сводится к линейному програ
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.