научная статья по теме О МОНОТОННОСТИ ОТОБРАЖЕНИЯ, СВЯЗАННОГО С БЕСКОАЛИЦИОННОЙ ИГРОЙ МНОГИХ ЛИЦ Математика

Текст научной статьи на тему «О МОНОТОННОСТИ ОТОБРАЖЕНИЯ, СВЯЗАННОГО С БЕСКОАЛИЦИОННОЙ ИГРОЙ МНОГИХ ЛИЦ»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2009, том 49, № 9, с. 1554-1564

УДК 519.626+519.83

О МОНОТОННОСТИ ОТОБРАЖЕНИЯ, СВЯЗАННОГО С БЕСКОАЛИЦИОННОЙ ИГРОЙ МНОГИХ ЛИЦ1

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

(117418Москва, Нахимовский пр-т, 47, ЦЭМИРАН) e-mail: golshtnv@cemi.rssi.ru Поступила в редакцию 26.12.2008 г.

С бескоалиционной игрой многих лиц может быть связано отображение, которое порождает вариационное неравенство. Задачи отыскания точек Нэша игры и решения этого неравенства эквивалентны. Численные методы решения вариационного неравенства существенно опираются на монотонность отображения, порождающего неравенство. Вместе с тем отображение, связанное с бескоалиционной игрой многих лиц, может и не быть монотонным. Установлены необходимые и достаточные условия, при соблюдении которых отображение, связанное с конечной бескоалиционной игрой трех и более лиц в смешанных стратегиях, обладает свойством монотонности. Библ. 3.

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

Пусть X — подмножество евклидова пространства Е, Т — точечно-множественное отображение, которое каждой точке х е Xставит в соответствие непустое подмножество Т(х) пространства Е. Вариационное неравенство, определяемое отображением Т, имеет вид

г е Т(х), < г, X - х) ^ 0 Ух' е X. (1)

Под решением вариационного неравенства (1) понимается такая точка х* е X, что при некотором ?* е Т(х*) неравенство <?*, х' — х*) > 0 справедливо для всех точек х' е X. Множество всех решений вариационного неравенства (1) обозначим через X*.

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

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

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

< г' - г", х' - х") > 0. (2)

Можно показать (см., например, [1]), что требование A гарантирует разрешимость вариационного неравенства, т.е. непустоту множества X*. Однако требование A не обеспечивает выпуклости X*. Если же помимо A выполняется и требование B, то множество решений X* вариационного неравенства (1) является непустым выпуклым компактом.

К вариационным неравенствам могут быть сведены многие классы задач оптимизации и равновесия: задачи выпуклой оптимизации, поиск точек Нэша бескоалиционных игр многих лиц, отыскание равновесного состояния в ряде экономических моделей (например, определение цен, обеспечивающих равновесие спроса и предложения).

В [2] описан достаточно эффективный численный метод решения вариационного неравенства (1) и показано, что если отображение Т, определяющее (1), удовлетворяет условиям A и B, то метод порождает последовательность, сходящуюся к множеству X* решений неравенства (1). В [1] приведено обобщение этого метода на случай, когда отображение Т задано неточно. Естественно, что в [1] также предполагается соблюдение допущений A, B.

1) Работа выполнена при финансовой поддержке РФФИ (код проекта 09-01-00156).

1554

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

Настоящая работа посвящена выявлению условий, гарантирующих монотонность вспомогательного отображения для выпуклой бескоалиционной игры трех и более лиц. Аналогичные вопросы применительно к выпуклым неантагонистическим играм двух лиц рассмотрены в [3].

Пусть X, — подмножество евклидова пространства Е,, 1 ^ I ^ к;/ — функция, определенная конечными вещественными значениями на множестве X, являющемся декартовым произведением множеств Х1, ..., Хк; Е — декартово произведение евклидовых пространств Е1, ..., Ек, к > 2. Введем бескоалиционную игру Г с числом игроков к, задаваемую для каждого игрока , множеством его стратегий X и функцией выигрыша/,, 1 ^ , ^ к. Условимся обозначать через X* множество точек

Нэша игры Г, т.е. таких точек х* = (х* , ..., х* ) е X, что

тах/1 (х*, ..х*_ 1, х;> х*+ ь ..х*) = /1(х*), 1 ^ / ^ к. (3)

Х1 е X

Будем говорить, что игра Г удовлетворяет требованиям А1, если X — непустой выпуклый компакт, функция/ ,, 1 ^ I ^ к, определена и непрерывна на множестве {х = (х1, ., хк): х5 е X, 1 ^ 5 ^ к,

х, е X} и вогнута по х I е X при любых фиксированных х8 е X, 1 ^ 5 ^ к, 5 Ф ,, где X — выпуклое открытое множество, содержащее X.

Игру, удовлетворяющую требованиям А1, условимся называть выпуклой. Свяжем с выпуклой игрой Г точечно-множественное отображение Тг множества X в подмножества евклидова пространства Е, содержащего X. Отображение Тг определяется соотношением

Тг(х) = {X = (1Ъ Хк): -Ц е дхДх), 1 ^ I ^ к}, х е X, (4)

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

Из определений точки Нэша (3) игры Г и решения вариационного неравенства (1) вытекает, что множество X* точек Нэша игры Г совпадает с множеством решений вариационного неравенства (1) при Т = Тг. Поэтому задача поиска точек Нэша выпуклой игры Г эквивалентна задаче решения вариационного неравенства (1) при Т = Тг. Если игра Г является выпуклой, то легко проверяется, что точечно-множественное отображение Тг удовлетворяет требованиям А.

Таким образом, возможность использования методов решения вариационных неравенств, описанных в [1], [2], для отыскания точек Нэша выпуклой игры Г зависит от монотонности отображения Тг.

Учитывая определения (4) отображения Тг, условие монотонности этого отображения можно представить в следующем виде.

В1. Для произвольных х' = (х1, ..., х'к), х" = (х" , ..., х"к ) е X, е дх ^ (х'), е дх,^ (х"), 1 ^ I ^ к, имеет место неравенство

к

£ < X' - X", х - х'') ^ 0. (5)

1= 1

Введем следующую систему требований к множеству Xи функциям/ ,, 1 ^ I ^ к, определяющим игру Г.

В2. Функция/ = Е к= 1/] является вогнутой и супердифференцируемой на выпуклом компакте X; функция/, вогнута и дифференцируема по х, на X, при произвольных фиксированных х, е X,, 1 ^

5 к, 5 Ф функция/ выпукла и субдифференцируема по совокупности переменных х5 е X,, 1 ^ 5 ^ к, 5 Ф ,, при любом фиксированном х, е X,, 1 ^ , ^ к.

Как показано в [1], условие B2 является достаточным для соблюдения требований B1, т.е. для монотонности отображения Тг.

Ослабим требования B2 к игре Г, предположив, что функции выигрышей игроков / и множества их стратегий XI удовлетворяют следующим условиям.

Bз. Функция/ = /1, + /2,, 1 ^ I ^ к, где функции/1, и множества XI подчиняются требованиям B2, функция/2, при произвольных фиксированных х,. е X,, 1 ^ 5 ^ к, 5 Ф ,, непрерывно дифференцируема на открытом множестве, содержащем X,, и постоянна на X,, 1 ^ , ^ к.

Покажем, что B3 также обеспечивает выполнение требований B1, т.е. гарантирует монотонность отображения Тг.

Пусть Ь, = 1тX, — линейная оболочка выпуклого компакта X,, О, — линейное подпространство евклидова пространства Е ,, порождающее Ь,. Согласно B3, при любых q е О, и х е Xимеет место равенство

</2х(х), д) = 0, 1 ^ г ^ к. (6)

Если х', х" — две произвольные точки множества X, то в силу (6) и того, что х' — х" е О,, имеем

/х(х-) -Л1х<(х"), х\ - х") = 0, 1 ^ г ^ к. (7)

Учитывая (7), а также свойства функций/1, и множеств X,, отмеченные в B3, получаем для любых х', х" е X

к к

X (х') -/х((х"Xх'- х") = X (х') -Ах,(х" X х'.- х',:) ^ 0,

г = 1 г = 1

что указывает на монотонность отображения Тг.

Таким образом, B3 является более сильным по сравнению с B2 достаточным условием монотонности отображения Тг.

Отметим еще одну связь между условиями B2 и B3. Пусть Г — игра, которая определяется функциями/ и множествами X, удовлетворяющими требованиям B3, а Г1 — игра, порождаемая функциями /1, и множествами X. Из определения точки Нэша бескоалиционной игры следует, что множества точек Нэша игр Г и Г1 совпадают. Поэтому если игра Г удовлетворяет условию B3, то при отыскании ее точки Нэша можно заменить Г игрой Г1, удовлетворяющей требованиям B2.

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

с номером а, принимающий целые значения от 1 до па, 1 ^ а к, а, ^ — элемент таблицы А, определяемый к индексами при значениях, соответственно, 51, ..., В дальнейшем нам придется суммировать элементы таблицы А по нескольким индексам. Условимся при р ^ к вместо обозна-

п1 п

чения Е, _ п ...Е, _ 1 а, . использовать более экономное обозначение Е, ,а, . , опуская макси-

_ п !р _ 1 • • • !к • • • !р • • • !к'

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

Рассмотрим конечную бескоалиционную игру с числом игроков к, в которой игрок I располагает п стратегиями, а его функция выигрыша задается при помощи к-мерной таблицы А =

= (а<([).., )п . п , где а<('1)

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

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