ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2012, том 48, № 3, с. 113-120
МЕТОДЫ ОПТИМИЗАЦИИ
ОБ ОДНОМ КЛАССЕ АНТАГОНИСТИЧЕСКИХ ИГР
© 2012 г. Е.Г. Гольштейн
(Москва)
Выделен класс антагонистических игр, обладающих свойствами кососимметричной матричной игры. При определенных условиях бескоалиционная игра многих лиц оказывается эквивалентной игре из этого класса. Если игра многих лиц конечна, то функция выигрышей эквивалентной антагонистической игры билинейна и кососимметрична.
Ключевые слова: антагонистическая игра, кососимметричная матрица, бескоалиционная игра многих лиц.
1. Рассмотрим вещественную функцию Ф = Ф(м, v) двух векторных аргументов и, v, заданную на прямом произведении G х G, где G - выпуклый компакт некоторого евклидова пространства. Введем антагонистическую игру Г(Ф, G), в которой оба игрока имеют одинаковые множества стратегий G, а функцией выигрышей первого игрока является Ф(и, v).
Будем говорить, что функция Ф(и, v) удовлетворяет условию Qj, если Ф вогнута на G по и при любом фиксированном v ! G, выпукла на G по v при любом фиксированном u ! G, непрерывна на G х G и, кроме того,
Ф(и, и) = 0 6и ! G. (1)
Если Ф является билинейной функцией, определяемой квадратной матрицей A, а G = {и = (и1, ..., ип) $ 0:/" и,- = 1}, то игра Г(Ф, G) превращается в матричную игру в смешанных стратегиях, задаваемую матрицей A.
Легко доказать, что условие Q1 в данном случае эквивалентно требованию кососимметричности матрицы A. Таким образом, при соблюдении условия Q1 игра Г(Ф, G) является обобщением кососимметричной матричной игры. Как известно, матричная игра, определяемая кососиммет-ричной матрицей, обладает следующими свойствами: ее цена равна 0, а множества оптимальных стратегий обоих игроков одинаковы. Как будет установлено ниже, для любой антагонистической игры Г(Ф, G), в которой функция выигрышей удовлетворяет условию Q1, оба эти свойства сохраняются.
Что касается первого свойства (нулевая цена игры), то соответствующее обоснование очевидно. Действительно, в силу (1)
maxФ(и, v)>0 6v ! G,
и ! G
minФ(и, v)<0 6и ! G,
v ! G
откуда следует, что цена игры Г(Ф, G) равна нулю. Обоснование второго свойства потребует существенно больших усилий.
Обозначим U* и V* множества оптимальных стратегий первого и второго игроков игры Г(Ф, G).
Лемма 1. Если функция Ф удовлетворяет условию Q1, а множество G совпадает с отрезком [0, 1], то
U* = V*. (2)
Доказательство. Пусть v* - произвольный элемент множества V*. Учитывая, что цена игры Г(Ф, G) равна нулю, имеем
maxФ(u, ü*) = 0 = Ф(v*, v*). (3)
u ! [0,1]
Покажем, что
v* ! U*. (4)
Доказательство проведем методом "от противного". Если v* g U* то minvе [01] Ф(v*, v) < 0, т.е. найдется такая точка v ! [0,1], для которой
Ф(v*, v)<0. (5)
Выберем произвольную точку u* ! U*. Для определенности условимся считать u* < v* (другая возможность анализируется аналогично). Из того, что Ф(u*, v*) = 0, имеет место (3) и функция Ф вогнута по первому аргументу, вытекает
Ф(^ v*) = 0 6u ! [u*, v*]. (6)
Поскольку minve [01] Ф(u*, v) = 0, Ф(u*, v*) = Ф(u*, u*) = 0, а функция Ф выпукла по второму аргументу, имеет место
Ф(u , v) = 0 6v ! [u*, v*]. (7)
Таким образом, согласно (1), (6) и (7) функция Ф равна нулю на границе треугольника
А = {(u, v): u ! [u*, v*], v ! [u, v*]}. Отсюда с учетом вогнутости (выпуклости) Ф по u(v) получаем, что
Ф(^ v) = 0 6(u, v) ! А. (8)
Соотношение (8) с учетом выпуклости функции Ф по v приводит к равенству
min Ф(^ v) = 0, (9)
v ! [0,1]
которое имеет место для всех u ! [u*, v*). Из (9) и непрерывности функции Ф следует неравенство Ф(v*, v) > 0, которое входит в противоречие с (5). Следовательно, v* ! U*. Тем самым установлено включение V* С U*. Обоснование противоположного включения может быть проведено аналогично.
Теорема 1. Если функция Ф удовлетворяет условию Q1, а G - выпуклый компакт, то цена игры Г(Ф, G) равна нулю и имеет место соотношение (2).
Доказательство. То, что цена игры Г(Ф, G) равна нулю, доказано ранее. Убедимся в верности включения
V* С U*. (10)
Зафиксируем произвольную оптимальную стратегию v* второго игрока игры Г(Ф, G). В таком случае
maxФ(^ v*) = 0. (11)
u ! G
Если будет установлено, что
minФ(v*, v) = 0, (12)
v ! G
то тем самым будет доказана верность включения (10).
Зафиксируем произвольную точку v ! G. Убедимся в справедливости неравенства
Ф^*, v) > 0. (13)
Для этого введем антагонистическую игру Г1 = Г(Ф1, G1), где G1 = [0, 1], Ф1(а, ß) = Ф(av + (1- a) v*, ßv + (1- ß) v*). Согласно (11), точка ß = 0 является оптимальной стратегией второго игрока игры Г1. Поскольку функция Ф1 удовлетворяет условию Q1, согласно лемме 1 точка a = 0 - оптимальная стратегия первого игрока игры Г1. Это означает, что Ф1(0, ß) > 0
для всех 3 £ [0, 1], и в частности Ф1(0,1) = Ф(у*, V) > 0, т.е. для любого V ! О имеет место неравенство (13), а значит, и равенство (12).
Включение и* С V устанавливается при помощи аналогичных рассуждений.
2. Любая вещественная функция Ф, определенная на прямом произведении двух выпуклых компактов О, помимо антагонистической игры Г(Ф, О) порождает задачу Р(Ф, О) определения такой точки равновесия и* £ О, что
Ф(и*, и*) = тахФ(и, и ). (14)
и ! О
Если функция Ф удовлетворяет условию 01, то из (14) и теоремы 1 вытекает соотношение
и" = и *= V *, (15)
где и - множество решений (точек равновесия) задачи Р(Ф, О), а и* (V*) - множество оптимальных стратегий первого (второго) игрока игры Г(Ф, О) .
Ослабим условие за счет того, что вместо (1) будем предполагать вогнутость функции Ф(и, и) на О. Ослабленный вариант условия Q1 обозначим Q2. Положим
Ф = Ф(и, V) = Ф(и, V) - Ф^, V),(и, V) ! О х О.
Если функция Ф удовлетворяет условию^ Q2, то, очевидно, функция Ф удовлетворяет условию Q1. Заметим также, что, поскольку Ф - Ф зависит лишь от аргумента V, множества решений задач Р(Ф, О) и Р(Ф, О) совпадают. С учетом этих двух фактов и (15) из теоремы 1 вытекает следующее утверждение.
Теорема 2. Пусть функция Ф удовлетворяет условию Q2. В таком случае седловое множество антагонистической игры Г(Ф, О) имеет вид_ и* х и*, где и* - множество решений (точек равновесия) задачи Р(Ф, О), причем цена игры Г(Ф, О) равна нулю.
Значение теоремы 2 состоит в том, что в соответствии с ней численный анализ задачи Р(Ф, О) при Ф, удовлетворяющей условию Q2, может быть проведен при помощи методов отыскания седловых точек вогнуто-выпуклой функции, определенной на прямом произведении двух одинаковых выпуклых компактов. Как известно, среди таких методов имеются весьма эффективные. Доказательство теоремы 2 при дополнительном предположении о липшицевости функции Ф содержится в (Гольштейн, 2009).
Заметим, что вогнутая непрерывная и супердифференцируемая на выпуклом компакте функция не обязана быть липшицевой. Приведем подтверждающий пример.
Пусть
О = {(х, у):-1< у <-|х|3/2, |х|<1},
\х2/у, (х,у) ! О, (х,у) ! (0,0), /<Х У) = *
[0 (х, у) = (0,0).
Нетрудно проверить, что функция / вогнута и непрерывна на выпуклом компакте О. Кроме того, она дифференцируема во всех точках О, отличных от (0, 0), а в точке (0, 0) супердифференци-руема. Вместе с тем эта функция не является липшицевой в любой окрестности точки (0, 0).
Рассмотрим бескоалиционную игру Я с числом игроков к > 2, которая задается для каждого игрока множеством Х1 его стратегий (предполагается, что Х1 - непустой выпуклый компакт) и функцией выигрышей/, определенной на прямом произведении X = Х1 х...х Хкмножеств стратегий всех игроков, 1 < г < к. Обозначим Х*(Х* С X) множество точек Нэша игры Я.
Условимся говорить, что игра Я удовлетворяет условию 8, если функция / непрерывна, вогнута относительно х1 £ Хг , выпукла относительно
хг = (хъ ..., хг-ъ хг+ъ ..., хк) ! Х1 = Х1 х... х Хг-1 х Хг+1 х... хXk, 1 < г < k, а функция / = суммарных выигрышей всех игроков игры Я вогнута.
Игре Я сопоставим функцию ФЯ(и, V), и е С, V е С, используя соотношение
к
Фя(и, V) = //(V1,..., Vм, иь V1+1,..., Vк) - /(V1,..., Vк), (16)
г=1
где
/(V1,..., Vк) = /к=1 /(V1,..., Vк), С = X1 X... XХк, и = (и 1, ...ик) е С, V = (V1,..., Vк) е С. Из определения (14) задачи Р(Ф, С) и (16) функции ФЯ следует:
1) что множество решений и* задачи -Р(ФЯ, С) совпадает с множеством X точек Нэша игры Я;
2) функция ФЯ удовлетворяет условию 01, если игра Я удовлетворяет условию 8.
С учетом этого в качестве следствия теоремы 2 получаем следующий результат.
Теорема 3. Если бескоалиционная игра Я удовлетворяет условию Б, а функция ФЯ задается соотношением (16), то седловое множество антагонистической игры Г(ФЯ, С) имеет вид X х X*, где X - множество точек Нэша игры Я.
3. Рассмотрим частный случай бескоалиционной игры многих лиц, в которой каждый из игроков имеет конечное число стратегий. Такие игры называют конечными. Дальнейшие наши рассмотрения связаны с выделением подкласса конечных игр многих лиц, удовлетворяющих условию 8 и, следовательно, допускающих сведение к антагонистической игре с нулевой ценой.
Для описания конечных игр обычно используют таблицы, элементы которых нумеруются при помощи к индексов, где к > 2 - число игроков соответствующей игры. Условимся называть такие таблицы к-мерными. По аналогии с матрицами (двумерными таблицами) при записи к-мер-ной таблицы А будем пользоваться обозначением А = (а^...^)п1...пк, где яа - индекс с номером а, принимающий целые значения от 1 до па, 1 < а < к, а*1 ..*, - элемент таблицы А, определяемый к индексами 51, ..., як соответственно. Условимся при суммировании элементов таблицы А по р < к
индексам вместо обозначения /п'_1-./ р а51...ч использовать более экономное обозначение
Рассмотрим конечную игру с числом игроков к, в которой игрок г имеет пг стратегий, а его выигрыш задается к-мерной таблицей А1 = (а*'1)...*к)п1...пк, где а*'1)...*к - выигрыш игрока г, если игрок а выбирает стратегию *а, 1 < а < к. Если расширить множества стратегий игроков смешанными стратегиями, то приходим к конечной игре Я в смешанных стратегиях с к участниками, в которой
Xi = {Хг = (хгЪ ..., Х1щ): / хщ = 1, Х*. > ° 1< * < пг }, (17)
*г =1
/(Х) = / а?-...ЧХии ..., х^ 1< I < k, ...*к
гд
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.