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

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

ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2009, том 45, № 4, с. 97-104

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

ОБ ОДНОЙ ЗАДАЧЕ РАВНОВЕСИЯ, СВЯЗАННОЙ С БЕСКОАЛИЦИОННЫМИ ИГРАМИ*

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

(Москва)

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

1. Пусть E - евклидово пространство; G - непустой выпуклый компакт, содержащийся в E; Ф(м, w), u d G, w d G, - функция с вещественными значениями. Рассмотрим задачу Р(Ф, G) определения точки равновесия u* d G, такой, что

Ф(u*, u*) = maxФ(u, u*). (1)

u d G

В дальнейшем будем анализировать задачу Р(Ф, G) при различных допущениях относительно функции Ф. Наиболее слабыми из них являются следующие.

Условие R1. Функция Ф непрерывна на G # G и вогнута по u d G при любом фиксированном

w d G.

Если функция Ф удовлетворяет условию R1, то задача Р(Ф, G) разрешима, т.е. множество точек ее равновесия U * непусто. Это следует из теоремы Какутани о неподвижной точке. Вместе с тем соблюдение одного лишь условия R1 делает задачу Р(Ф, G) сопоставимой по сложности с задачей поиска неподвижной точки точечно-множественного отображения в условиях теоремы Какутани, решение которой весьма трудоемко. Ниже будет установлено, что задача Р(Ф, G) связана с некоторой антагонистической игрой и поэтому допускает достаточно эффективный численный метод решения, если функция удовлетворяет следующему условию.

Условие R2. Функция Ф - липшицева на G # G, вогнута по u d G при любом фиксированном w d G, выпукла по w d G при любом фиксированном u d G, и, кроме того, Ф(u, u), u d G, является вогнутой функцией.

Ниже будут указаны некоторые другие требования к функции Ф, при соблюдении которых задача Р(Ф, G) оказывается менее сложной, чем в общем случае.

2. Анализ задачи Р(Ф, G) при Ф, удовлетворяющей условию R2, основан на двух вспомогательных утверждениях.

Лемма 1. Если fx), x d G - вогнутая (выпуклая) функция, dfx) - супердифференциал (субдифференциал) f в точке x d G, то при любом x d G множество df(x) Ф 0 и содержит такие элементы l, что ||/|| < L, где L - постоянная в условии Липшица, которому удовлетворяет функция f.

Доказательство. Ограничимся случаем вогнутой функции f

1. Пусть int G Ф 0. Если x d int G, l d df(x), x(s) = x - sl, где s > 0 выбрано таким, чтобы x(s) d G, то f(x(s)) # f(x) + G l, x(s) - x H = f(x) - s || 1112, откуда, используя условие Липшица для функцииf, приходим к неравенству ||l|| < L. Итак, при x d intG норма каждого элемента супердифференциала dfx) не превышает L.

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

7

97

Рассмотрим произвольную граничную точку x компакта G. Выберем последовательность {xs} точек xs d int G, сходящуюся к x. Пусть ls d df(xs), || ls ||< L, s = 1, 2, ... Очевидно, что любая предельная точка l ограниченной последовательности {ls} содержится в dfx), причем ||l ||< L. Тем самым лемма доказана в случае int G Ф 0.

2. Предположим теперь, что int G = 0 и E - подпространство евклидова пространства E, некоторый сдвиг которого является линейной оболочкой G. Обозначим df (x) проекцию супердифференциала dfx) на E. Очевидно, что df (x) f df(x). Пусть ri G - относительная внутренность множества G. Рассуждения, аналогичные случаю int G ! 0, позволяют установить, что при x d ri G все элементы df (x) имеют норму, не превышающую L, а при x g ri G, x d G, df (x) содержит такие элементы l, что 11111 < L.

Лемма 2. Пусть Ф (u, w), (u, w) d G X G - такая липшицева функция с постоянной L, вогнутая по u при любом фиксированном w d G, выпуклая по w при любом фиксированном u d G, что

U(u, u) / 0, u d G. (2)

В таком случае при любом u d G

duф(u, u) = -dwф(u, u)! 0, (3)

где d^(u, w) - супердифференциал Ф по u в точке (u, w), а d^(u, w) - субдифференциал Ф по w в точке (u, w).

Доказательство. Для каждой точки u d G введем конус возможных направлений K(u) = {s d E: u + es d G3s >0}. Пусть u d G, l d duФ(u, u)(duФ(u, u) ! 0 в силу леммы 1), s d K(u). Для достаточно малых положительных e имеем

Ф(u + es, u)< Ф(u, u) + e (l, s >, (4)

U(u + es, u) > Ф(u + es, u + es) - e (l(e, s), s >,

где l(e, s) - некоторый элементдwФ(u + el, u + el), причем в силу леммы 1 можно считать, что

Ill(e, s)||<L.

Поскольку согласно (2) Ф(u, u) = Ф(u + es, u + es) = 0, то в силу (4) имеем

(l + l(e, s), s > >0, (5)

где l(e, s) d dwФ(u + es, u + es), || l(e, s) || < L.

Устремляя в (5) e > 0 к нулю, получаем при любых u d G, l d дмФ(u, u) и s d K(u)

(l +1(s), s > >0, (6)

где l(s) d dwФ(u, u), || l(s)||< L.

Из равномерной ограниченности векторов l(s) и замкнутости d„^(u, u) следует, что (6) имеет место для любых l d дмФ(u, u) и s d cl K(u) (cl K(u) - замыкание конуса K(u)). Итак, для произвольных l d дмФ(u, u) и s d cl K(u) справедливо неравенство

(l +1(s), s > >0, (7)

где l(s) - некоторый элемент множества d„^(u, u). Докажем, что из неравенства (7) вытекает включение

duФ(u, u) f -дwФ(u, u). (8)

Действительно, если (8) неверно, т.е. существует такой вектор l0 d дuФ(u, u), что l0 g -дwФ(u, u), то в силу выпуклости и замкнутости множества -d„^(u, u) существует вектор s0, удовлетворяющий требованиям

(l0, s0 ><0, (l, s0 >>0 6l d -дwФ(u, u). (9)

Проверим, что s0 d cl K(u). Если Г d -дwU(u, u), то очевидно, что l +1' d -дwU(u, u) при любом l d K*(u), где K*(u) = {l d E: (l, s ) >0 6 s d K(u)} - конус, сопряженный с K(u). Поэтому согласно правому неравенству (9) имеем

(l, s0 ) >0 6l d K*(u). (10)

Соотношения (10) означают, что s0 d (K*(u))* = K**(u). Но, как известно, K**(u) = clK(u). Следовательно,

s0 d cl K(u). (11)

Из (9) и (11) вытекает, что

(10 + l, s0 ) <0 6l d дwФ(u, u), s0 d clK(u). (12)

Но (12) входит в противоречие с (7). Следовательно, включение (8) верно. Если повторить рассуждения, использованные для доказательства (8), поменяв местами u и w, то получим противоположное включение: дwU(u, u) f дuU(u, u), которое совместно с (8) и эквивалентно (3).

Рассмотрим антагонистическую игру Г(Ф, G), в которой первый игрок выбирает стратегию u d G, второй игрок - стратегию w d G, а выигрыш первого игрока определяется функцией выигрышей Ф(^ w), u,w d G. Положим Ф1(u, w) = Ф(u, w) - Ф(w, w), u, w d G. Очевидно, что U1(u, u) = 0, u d G.

Теорема 1. Пусть функция Ф удовлетворяет требованиям R2. В таком случае седловое множество антагонистической игры Г(Ф, G) имеет вид U* х U*, где U* - множество решений (точек равновесия) задачи Р(Ф, G), а цена v* игры Г(Ф, G) равна нулю.

Доказательство. Пусть u* d U*. Тогда согласно (1) и определению функции Ф1 имеем

maxФ^, u*) = Ф1(и*, u*)=0. (13)

u d G

Следовательно, 0 d дuФ1(u*, u*). Тогда 0 d дwФ1(u*, u*) по лемме 2, откуда вытекает

minФ1(u*, w) = Ф1(u*, u*). (14)

w d G

Соотношения (13), (14) означают, что v* = 0, а (u*, u*) является седловой точкой функции Ф^, w), u d G, w d G.

Допустим теперь, что (u*, w*) - седловая точка функции Ф^, w), u d G, w d G. Поскольку Ф1(и*, w*) = v* = 0, Ф^*, w*) = 0, то

maxФ1(u, w*) = Ф1(и*, w*) = Ф^*, w*)

u d G

и согласно (1) точки u*, w* d U*. Таким образом, (u*, w*) d U* х U*.

3. Согласно теореме 1 задача Р(Ф, G) при Ф, удовлетворяющей требованиям R2, оказывается эквивалентной антагонистической игре с нулевой ценой игры и симметричным седловым множеством. Поэтому для численного решения задачи Р(Ф, G) можно воспользоваться достаточно эффективным методом отыскания седловых точек выпукло-вогнутых функций, содержащимся в (Гольштейн, Немировский, Нестеров, 1995).

Описание и анализ численного метода решения задачи Р(Ф, G) основан на соответствующих результатах работы (Гольштейн, Немировский, Нестеров, 1995) и отмеченной в теореме 1 специфике игры Г(Ф, G).

Метод решения задачи Р(Ф, G) является итерационным и зависит от параметра А, выбираемого из интервала (0, 1). Перед началом итерации q предполагается, что точки ui d G и векторы

Iг е диФ(и, иг), 1 < г < д, уже найдены. В качестве и1 может быть выбрана любая точка множества G. Введем задачу Лд с переменными и, х, имеющую вид:

х " тах, (I, и - и1) > х, 1 < г < д, и е G. (15)

Предположим, что выпуклый компакт G является многогранником. В этом случае Л - задача линейного программирования. Пусть Дд - максимальное значение переменной х задачи Л ; Ач -задача, двойственная Лд; пг - оптимальное значение переменной задачи Лд, отвечающей ограничению (I, и - иг ) > х задачи Лд, 1 < г < д. Из вида задачи Лд вытекает справедливость следующих двух соотношений:

q

max/n G h, u - u ) = A (16)

= 1

/ р,- =1, П,- >0, 1< i < q. (17)

i =1

Выберем произвольное s > 0. Итерация q начинается с решения двойственной пары задач линейного программирования Aq, Aq, в результате чего вычисляются Aq и р., 1 < i < q. Если Aq < s,

q

то в качестве приближенного решения задачи Р(Ф, G) принимается точка u*q = /pu,-, которая в

i=1

силу (17) содержится в G. В этом случае итерация q является последней. Если же Aq > s, то множество точек{и1, ... ,uq} пополняется новой точкой uq+1. Эта точка находится из решения задачи квадратичного программирования

||u - uq ||2 " min, и d Mq(AAq), (18)

где Mq(x) - многогранник, определяемый условиями задачи (15) при фиксированном значении x < Aq, а А е (0, 1) - параметр метода. Таким образом, точка uq+1 - проекция точки uq на многогранник Mq(AAq). На этом итерация q заканчивается.

Прежде чем приступить к обоснованию данного метода, уточним понятие приближенного решения задачи Р(Ф, G). Под s-решением задачи Р(Ф, G) при любом фиксированном s > 0 условимся понимать такую точку us е G, для которой верно неравенство

max Ф(и, ue)- Ф(ueue)< е. (19)

и d G

Из (1) и (19) следует, что е-решение задачи Р(Ф, G) при е = 0 совпадает с решением этой задачи. Обоснование метода основано на двух вспомогательных леммах. q

Лемма 3. Если функция Ф удовлетворяет условию R2, то точка «*q = /n,-«,- d G является Dq-р

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

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

Пoхожие научные работыпо теме «Экономика и экономические науки»