научная статья по теме О МОДИФИКАЦИЯХ КОНЕЧНОЙ БЕСКОАЛИЦИОННОЙ ИГРЫ, ИМЕЮЩИХ ВЫПУКЛУЮ СТРУКТУРУ Экономика и экономические науки

Текст научной статьи на тему «О МОДИФИКАЦИЯХ КОНЕЧНОЙ БЕСКОАЛИЦИОННОЙ ИГРЫ, ИМЕЮЩИХ ВЫПУКЛУЮ СТРУКТУРУ»

ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2010, том 46, № 4, с. 101-107

= МЕТОДЫ ОПТИМИЗАЦИИ =

О МОДИФИКАЦИЯХ КОНЕЧНОЙ БЕСКОАЛИЦИОННОЙ ИГРЫ, ИМЕЮЩИХ ВЫПУКЛУЮ СТРУКТУРУ*

© 2010 г. Е.Г. Гольштейн

(Москва)

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

Ключевые слова: конечная бескоалиционная игра многих лиц, выпуклая структура игры, монотонное отображение.

1. Пусть Xг - непустое подмножество из евклидова пространства E¡• ; Л - функция, определенная конечными вещественными значениями на множестве X, являющемся декартовым произведением множеств Х1, ..., Хк, 1 < г < к; E - декартово произведение евклидовых пространств E1, ..., Ek, к > 2.

Введем бескоалиционную игру Г с числом игроков к, задаваемую для каждого игрока г множеством его стратегий Х1 и функцией выигрышей Л , 1 < г < к. Одна из основных задач анализа игры Г связана с отысканием так называемых точек Нэша этой игры, т.е. таких точек

х* = (х**, ..., х*) ! X, что

тахЛ(х*, ..., х*-1, Хг, х*+1, ..., х**) = Л(х*), 1< г < к.

хг е X

Условимся называть игру Г выпуклой, если функция Л, 1 < г < к, определена и непрерывна на множестве {х = (х1, ..., хк): х5 ! X, 1 < 5 < к, хг ! Xг} и вогнута по хг ! Хг при любых фиксированных х5 ! X, 1 < 5 < к, 5 ^ г, где Хг - выпуклое открытое множество, содержащее Хг. Пусть Х*(Г) - множество всех точек Нэша игры Г. Если Г - выпуклая игра, то множество ее точек Нэша Х*(Г) ^ 0. Однако из выпуклости игры Г не вытекает выпуклость Х*(Г). Например, множество Х*(Г) выпуклой игры Г может состоять из конечного числа точек.

Задача отыскания точек Нэша игры Г может быть сведена к задаче решения некоторого вариационного неравенства, связанного с Г. Пусть Т - точечно-множественное отображение, которое каждой точке х ! X ставит в соответствие подмножество Т(х) евклидова пространства E. Вариационное неравенство, определяемое отображением Т, имеет вид

t ! Т(х), х' - х) > 0 6 х' ! X. (1)

Под решением вариационного неравенства (1) понимается такая точка х* ! X, что при некотором { ! Т(х*) неравенство {{, х' - х*) > 0 справедливо для всех точек х' ! X. Множество всех

решений вариационного неравенства (1) обозначим X (Т).

* Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 09-01-

00156).

При анализе вариационного неравенства (1) обычно используются следующие два допущения относительно отображения Т.

Условие 1. Множества Xи Т(х) при любом х ! Xявляются выпуклыми компактами. Компакты Т(х), х ! X, равномерно ограничены, отображение Т(х) полунепрерывно сверху на X, т.е. если последовательности х1 ! X, t^ ! Т(х) сходятся соответственно к точкам х0 и то 10 ! Т(х0).

Условие 2. Отображение Т является монотонным, т.е. при любых х', х" ! X и t' ! Т(х'), I" ! Т(х") справедливо неравенство

(^ - Г, х' - х'') $ 0. (2)

Для сведения задачи поиска точки Нэша выпуклой игры Г к решению некоторого вариационного неравенства вида (1) свяжем с Г точечно-множественное отображение ТГ, определяемое соотношением

Тг(х)= ^ = ..., tk): -и ! дхДх), 1 < I < к}, х ! X, (3)

где дх /¡(х) - супердифференциал функции £ по х1 в точке х ! X.

Из определений точки Нэша игры Г и решения вариационного неравенства (1) вытекает, что

множество X,'(Г) точек Нэша игры Г совпадает с множеством X *(ТГ) решений вариационного неравенства (1) при Т = ТГ. Поэтому для поиска точек Нэша бескоалиционной игры Г можно использовать методы решения вариационного неравенства (1), определяемого отображением ТГ. В (Гольштейн, 2002, 2008а) описан достаточно эффективный численный метод решения вариационного неравенства (1), который в предположении, что отображение Т удовлетворяет условиям 1, 2, порождает последовательность, сходящуюся к множеству X (Т).

Что касается условия 1, то отображение ТГ удовлетворяет ему для любой выпуклой бескоалиционной игры Г. К сожалению, это не относится к условию 2. Для того чтобы оно соблюдалось, необходимо наложить на Г достаточно жесткие дополнительные требования.

Будем говорить, что бескоалиционная игра Г имеет выпуклую структуру, если отображение ТГ удовлетворяет условию 2, т.е. является монотонным.

Свяжем с выпуклой игрой Г ее модификацию Г(Я), определяемую функциями выигрышей игроков

£(х, Я) = Дх) - Я,.||х,.||2, х е X, 1 < I < к, (4)

где Я = (Я1, ..., Як) $ 0, Дх), х ! X, - функция выигрышей игрока I игры Г.

Представляет интерес вопрос о том, при каких значениях векторного параметра Я выпуклая игра Г(Я) имеет выпуклую структуру. Ответим на этот вопрос для случая конечных бескоалиционных игр Г, рассматриваемых в смешанных стратегиях.

2. Рассмотрим конечные бескоалиционные игры, в которых каждый игрок обладает конечным числом стратегий, т.е. каждое множество Xi состоит из конечного числа точек. Для описания таких игр удобно пользоваться таблицами, элементы которых нумеруются с помощью нескольких индексов (их число равно числу игроков к). Условимся называть такие таблицы к-мерными. Для записи к-мерной таблицы А обозначим А = (а. . )п п , где 5а - индекс с номером а, принимающий целые значения от 1 до па, 1 < а < к; а - элемент таблицы А, определенный к индексами при значениях 51, ..., .к , соответственно. В дальнейшем нам понадобятся суммы элементов таблицы А по нескольким индексам.

П1 пр

Условимся прир < к выражение / ... / а51...5к записывать как / а51...5к, опуская макси-

■4 = 1 Ир =1 .51,..., Ир

мальные значения индексов суммирования, величины которых будут ясны из контекста.

Рассмотрим конечную бескоалиционную игру с числом игроков к, в которой игрок I имеет п1 стратегий, а его функция выигрышей задается с помощью к-мерной таблицы А1 = (а 5'1)...5к) п1...пк, где а- выигрыши игрока ¡, если игрок а выбирает стратегию 5а, 1 < а < к. Если расши-

рить множества стратегии игроков с помощью введения смешанных стратегии, то приходим к выпуклой игре Г с к участниками, в котороИ:

=

"1

<Х! Ъ ... Хт): ^/Хгу ^ Хгу $ 0 у '

У" ' <5)

/г(х )= / а<$'1>...$кХ 1$1...Хк$к , 1 # г # k, Х = <Х 1, ..., Хк) ! Х = Х1 # ... #Хк .

$1 ...$к

В работах (Гольштейн, 20086, 2009) получены необходимые и достаточные условия, которые следует наложить на таблицы Аг, определяющие конечную игру Г, для того чтобы она имела выпуклую структуру. Как показывают результаты исследования, содержащиеся в (Гольштейн, 2008б, 2009), подкласс конечных игр, имеющих выпуклую структуру, чрезвычайно узок. Например, при к = 2 выпуклая структура будет только у таких конечных биматричных игр, в которых матрица А = А1 + А2 суммарных выигрышей игроков может быть представлена в виде

А (а$1 $2) "1 "2 (а$1 + а$2 ) "1 "2. (6)

Если биматричная игра Г, определяемая матрицами Аг = (а^$2) ^ П1, I = 1, 2, удовлетворяет требованию (6), то, как нетрудно проверить, ее множество точек Нэша совпадает с множеством седловых точек антагонистической игры Г двух лиц (матричной игры), задаваемой матрицей А1 = ($2) "1 "2 = (а$1$2 - а$'2 ) "1 "2. В связи с этим условимся в дальнейшем называть биматричную игру, удовлетворяющую (6), почти матричной.

Итак, класс биматричных игр с выпуклой структурой состоит из почти антагонистических игр и практически мало чем отличается от класса матричных игр. "

Пусть А = (агу)т" - произвольная матрица, состоящая из т строк и " столбцов, ы1 = /ау /",

т т " У =1

у У = '/ау/т, а = //агу/(т"). Введем обозначение

г=1 г = 1У=1

г ч 1/2

т"

г(А) = *//(агу - ^ - Уу + -)2 4 . (7)

Как показано в (Гольштейн, 2008б), неотрицательное число г(А) - значение наилучшего евкли-дового приближения матрицы А с помощью матриц вида (а'( + а У ) тп.

С каждой биматричной игрой Г = Г(А1, А2), определяемой матрицами выигрышей игроков А1, А2 и рассматриваемой в смешанных стратегиях, свяжем ее модификацию Г(Я) = Г(А 1, А2, Я), где Я - неотрицательный параметр. Игра Г(Я) задается функциями выигрышей игроков/г<х1, х2, Я) = = х1Агх2 - 0.5Я|| хг ||2, где хг ! Хг, I = 1, 2.

Как показано в (Гольштейн, 2008б), выпуклая игра Г(А1, А2, Я) имеет выпуклую структуру, если Я > 0.5г(А1 + А2). В п. 3 мы займемся распространением этого результата на игры Г, определяемые соотношениями (5), в которых число игроков к > 2.

3. Рассмотрим игру Г = Г(А1, ..., Ак), задаваемую согласно (5) набором таблиц А, 1 < г < к. Под модификацией игры Г будем понимать игру Г(Я) = Г(А1, ..., Ак, Я), в которой игрок г имеет функцию выигрышей

/г<Хъ ..^ Хъ Яг) = / а $г1)...$кХг$1... Хк$к-0.5Яг Ц Хг112, Хг = <Х!'1,..., Х1") ! хг, (8)

$1 ...$к

1 < г < к, где Я = (Я1, ..., Як) > 0 - векторный параметр модификации.

Для того чтобы сформулировать первую вспомогательную лемму, необходимую для анализа игры Г(Я), введем обозначения. Пусть (г, у) - пара различных целых чисел, расположенных на [1, к]; г - целое число из отрезка [1, к - 1]. Рассмотрим функции q<t), определенные на множестве целых чисел t отрезка [1, к - 1], за исключением t = г, и принимающие различные ^ q<t'r), t' ^ t") целые значения из отрезка [1, к], за исключением q(t) = г и q(t) = у. Множество таких функций q(t) обозначим Q<i, у, г).

Очевидно, что Q(i, ], г) состоит из (к - 2)! элементов. Для любых целых I ^у из отрезка [1, к], целого г из отрезка [1, к - 1] и функции q(t) ! Я(}, ], г) введем функцию {¡(х', х";], г, положив для произвольных х ' = (х 1, ..., хк), х " = (х/, ..., х'к) ! X::

{

i(x , x ; j, q) fi(x Ъ ■■■ xfc) / askx 1s 1---

xks.

(9)

где

x I, l = q(t), 1 < t < r -1, xl = [ x ", l = q(t), r + 1 < t < k -1, x i - x i , l = i, j■

Обозначим

{i(x ', x ''; j, r, q) + {j(x ', x ''; i, r, q) = {j

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком