ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2013, том 49, № 4, с. 94-104
МАТЕМАТИЧЕСКИЙ АНАЛИЗ ЭКОНОМИЧЕСКИХ МОДЕЛЕЙ
ОБ ОДНОМ ЧИСЛЕННОМ МЕТОДЕ РЕШЕНИЯ БИМАТРИЧНЫХ ИГР
© 2013 г. Е.Г. Гольштейн, У.Х. Малков, Н.А. Соколов
(Москва)
Предложен метод решения биматричных игр, основанный на поиске глобального минимума функции Нэша. Осуществляя перебор начальных чистых стратегий, метод отыскивает точное решение игры, если выполнено условие дополнительности, либо приемлемое приближение к множеству точек Нэша. Проведено численное тестирование метода, выявившее его достоинства и недостатки.
Ключевые слова: выпуклая игра, функция Нэша, точка Нэша, биматричная игра, чистая стратегия, смешанная стратегия, дополнительность. Классификация JEL: С02, С72.
Пусть Х1 и Х2 - подмножества евклидовых пространств Е1 и Е2 соответственно;/1 и/2 - функции, определенные конечными значениями на множестве X=Х1 X Х2 С Е = Е1 X Е2. Рассмотрим бескоалиционную игру Г двух лиц, задаваемую множествами стратегий игроков Х1, Х2 и функциями их выигрышей /1, /2. Обозначим через Х* множество точек Нэша игры Г. Предполагая супердифференцируемость функций/ и/ по х1 ! Х1 и х2 ! Х2 соответственно, свяжем с игрой Г точечно-множественное отображение ТГ, определяемое соотношением
Тг(х) = Тг(х 1, х2) = (I = (?1, 12): ! дхДхъ х2), г = 1,2}, х = (х 1, Х2) !Х. (1)
Отображение ТГ порождает вариационное неравенство
t ! ТГ, (?, х' - х) >0 Ух' ! Х, (2)
множество решений которого совпадает с множеством Х* точек Нэша игры Г. Поэтому любой сходящийся численный метод решения вариационного неравенства (2) позволяет решить игру Г (найти с любой степенью точности одну из ее точек Нэша).
Игра называется выпуклой, если определяющие ее функции/1,/2 и множество Худовлетворяют следующим требованиям: Х - непустой выпуклый компакт; функция /1 определена на множестве Х1 X Х2, вогнута по х1 ! Х1 при любом фиксированном х2 ! Х2 и непрерывна на Х1 X Х2, а функция /2 - на множестве Х1 X Х2, вогнута по х2 ! Х2 при любом фиксированном х1 ! Х1 и
непрерывна на Х1 XХ2; Хг С Хг, Хг - открытое выпуклое множество, г = 1, 2.
Любая выпуклая игра имеет непустое множество Х* точек Нэша. Однако множество Х* не обязано быть выпуклым (например, оно может состоять из нескольких изолированных точек).
Условимся, что выпуклая игра Г имеет выпуклую структуру, если связанное с ней согласно (1) отображение Т Г является монотонным. У игры, имеющей выпуклую структуру, множество точек Нэша - непустой выпуклый компакт. В работе (Гольштейн, 2002) описан эффективный численный метод решения вариационных неравенств, порожденных монотонными отображениями. В частности, если игра Г имеет выпуклую структуру, этот метод, примененный к вариационному неравенству (2), порождает последовательность, сходящуюся к множеству точек Нэша игры Г.
Далее мы будем иметь дело с конечными бескоалиционными играми двух лиц, в которых каждый игрок имеет конечное множество стратегий.
Рассмотрим конечную игру Г, предполагая, что первый игрок располагает т стратегиями, а второй - п стратегиями. Пусть а- выигрыш игрока г, когда игрок 1 использует свою стратегию
i, а игрок 2 - стратегию j, r = 1, 2.. Таким образом, конечная игра Г задается двумя матрицами A1 и A2, имеющими m строк и n столбцов. Конечные игры двух игроков в смешанных стратегиях принято называть биматричными. Если Г - биматричная игра, определяемая матрицами A1 и A2, она характеризуется множествами стратегий
m
X1 = {x 1=(x Ш ..., xml):/xi1 = 1, xi1 > j<i < m},
i=1 (3)
n 4 7
X2={x2 = (x12^» ..., xn2):Sxj2=1, xj2>0, 1< j < n }
j =1
и функциями выигрышей игроков
f1(xЪ x2) = x 1A 1x2, f2(x 1, x2) = x 1A2x2 , (4)
где x обозначает операцию транспонирования.
Каждая биматричная игра является выпуклой игрой. Как установлено в (Гольштейн, 2008), биматричная игра, определяемая матрицами A1, A2, имеет выпуклую структуру в том и только в том случае, если
A = (aj) mn = A1+ A 2 = (a,- + bj) mn. (5)
Если биматричная игра Г, определяемая матрицами A1, A2, имеет выпуклую структуру, т.е. для матрицы A = A1 + A2 справедливо представление (5), множество точек Нэша игры Г совпадает с множеством седловых точек матричной игры Г' с матрицей A1 = (aj1)- bj)mn. Таким образом, класс биматричных игр с выпуклой структурой фактически совпадает с классом матричных игр. Поскольку решение матричной игры сводится к анализу пары взаимодвойственных задач линейного программирования, класс биматричных игр с выпуклой структурой обладает полиномиальной сложностью. Что касается всех биматричных игр, то этот класс задач имеет, по-видимому, сверхполиномиальную сложность. Во всяком случае, к настоящему моменту не существует численного алгоритма, который решает любую биматричную игру с наперед заданной точностью при числе операций, полиномиально зависящем от исходных данных игры.
Пусть Г - произвольная бескоалиционная игра двух лиц, задаваемая множествами X1 и X2 стратегий игроков и функциями f1 и f2 их выигрышей, f = f1 + f2- функция суммарных выигрышей обоих игроков. Введем функцию
N(x) = N(x 1, x2) = maxf^x 1, x2) + maxf2(x 1, x2) - f(x 1, x2), (6)
X1 ! X1 x2 ! X2
определенную на множестве X = X1 x X2.
Из (6) и определения точки Нэша игры Г следует, что, во-первых, N(x) > 0 для всех x ! X, а, во-вторых, N(x) = 0 в том и только в том случае, если x является точкой Нэша игры Г. Следовательно, множество точек минимума функции N(x) на X совпадает с множеством X* точек Нэша игры Г, причем значение минимума равно нулю. Таким образом, решение игры Г оказывается эквивалентным поиску точек глобального минимума функции N на множестве X, причем N(x) -это естественная мера отклонения точки x ! X от множества X*.
В случае биматричных игр вычисление функции N(x) в любой точке x ! X может быть упрощено. Действительно, если fr, Xr, r = 1, 2, определяются соотношениями (3), (4), то
nm
maxf1(x 1, x2) = max/ a(,r>xj2, maxf2(x 1, x2) = max/ a(,2)xi1.
x1 ! X1 1<i < mj=1 x2 ! X2 1<i <
Следовательно,
N(x) = max/аЦ xj2 +max/a(2) xi1 - x 1 Ax X, (7)
1<i<m . , 1< j<n . ,
j = 1 i = 1
где А = A1 + A2. Функция N(x) для биматричных игр была введена в работе (Mills, 1960).
Из представления (7) вытекает, что задача минимизации функции N(x) на X в случае бимат-ричных игр эквивалентна задаче минимизации функций Нэша
N(xj, X2, vь v2) = (v! - xj A2x2) + (v2 - xj Ajxl), (8)
N(xj, x2, vь v2) = max{vj - xjA2x2, v2 - xjAjx2}, (9)
где vj и v2 - скалярные переменные, связанные с векторными переменными xj ! X1 и x2 ! X2 условиями
n m
/ajxj2 < v2, J< i < m, /aj2)xn < v j, j< j < n.
j=J i=J
Как и функция N(x), функции Нэша и их различные нормированные варианты служат мерой близости точки x ! X к множеству X*.
При любом фиксированном x2 ! X2 введем задачу линейного программирования Pj(x2) относительно переменных x2, vj, определенную соотношениями
m
v j-xj Ax 2 " min, /aj2)x,j< v j, J< j < n, xj = (xn, ..., xmj) ! Xj. (10)
i = j
Аналогично, при любом xj ! Xj введем задачу линейного программирования P2(xj) относительно переменных x2, v2:
n
v 2- x j Ax 2 " min, /aj xfl< v 2,j< i < m, x 2 = (x j2, ..., xn2) ! X2. (jj)
j=j
Определим дополнительные переменные uj = (un,..., unj) задачи (j0) и u2 = (mJ2,..., um2) задачи (jj) при помощи формул
U jj и jj
(xj, v j) = vj- /ajxj, j< j < n,
«,'2 = ий(х2, У2) = V2 - /а(1)х,2, 1< г < т,
у = 1
в этих обозначениях функция Нэша (8) имеет вид
т п
Ы = /и,2 х'1+ /ип хп.
г=1 у=1
Все величины в этой формуле неотрицательные, поэтому, для того чтобы функция N обратилась в нуль, необходимо и достаточно, чтобы в каждой паре хотя бы один сомножитель был равен нулю, т.е. выполнялось условие дополнительности. Пусть 1{А} - индикатор события А, принимающий значение 1, если событие А истинно, и 0, если событие А ложно; функция
тп
А = А(х 1, х2, и1, и2) = //{х,1 > 0, иа > 0} + /1{ху2 > 0, ип > 0} (12)
г=1 у=1
есть число нарушенных в точке х ! Х условий дополнительности. Итак, х ! Х* тогда и только тогда, когда А(х1, х2, и1, и2) = 0.
Введем множества Х' точек х ! Х, являющихся точками локального минимума функции Щх) (см. (6)) на Х, и Х", состоящего из точек х = (х1, х2) ! Х таких, что х1 - решение задачи Р1(х2), а х2 - решение задачи Р2(х1). Очевидно, Х" 2 Х' 2 Х , где Х - введенное ранее множество точек Нэша игры Г, совпадающее с множеством точек глобального минимума функции Ы(х) на Х. Нетрудно проверить, что любая точка х = (х1, х2) ! Х" содержится в Х', если хотя бы одна из задач линейного программирования Р1(х2), Р2(х1) имеет единственное решение. Поэтому выход точки х ! Х" за пределы множества Х' скорее исключение, чем правило.
Отправляясь от произвольной точки x1 ! X1, определим последовательность точек x(k) = (x (к), x 2k)), руководствуясь правилом: x (11) = x 1, x 21) - решение задачи P2(x 1), x (k+1) - решение задачи P1(x2k)), x2+1) - решение задачи P2(xf+1)), k = 1, 2,... Поскольку N(x(k+1)) < N(x(k)), k >1, существует lim N(x(k)) = q 1(x 1).
k " 3 (k)
Очевидно, что любая предельная точка последовательности {x(k)} содержится в X", причем если x - предельная точка {x(k)}, то N(x) = q 1(x 1).
По аналогичным правилам можно определить последовательность {x(k)}, отправляясь от произвольной точки x2 ! X2, и ввести функцию q2(x2), x2 ! X2. В таком случае все предельные точки этой последовательности также содержатся в X" и значение функции N на каждой из них равно q2(x2).
Предложенный в данной работе приближенный метод решения биматричных игр основан на последовательном вычислении значений функций q1(x1) и q2(x2) при различных стратегиях x1 ! X1 и x2 ! X2.
Мы не будем останавливаться на существующих численных методах решения биматричных игр, а отошлем читателя к монографии (Стрекаловский, Орлов, 2007), в которой дан достаточно подробный анализ таких методов, а также детально описан и обоснован оригинальный метод авторов монографии.
Приведем блок-схему предлагаемого метода решения биматричной игры Г.
Шаг 0. Зададим константы: S - максимально разрешенное число выборов начальной стратегии; K - максимально разрешенное число решаемых пар задач линейного программирования
л
P1, P2
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.