5 SKFM9S83

Наконец, последнее утверждение теоремы вытекает из уже доказанных ут-

верждений. Действительно, в предположении существования решения задач

(5,16), (5.17) построена оптимальная стратегия с последней компонентой, от-

личной от нуля. Поэтому, если нет оптимальных стратегий в игре с матрицей D,

последняя компонента которых отлична от нуля, то задачи (5.16), (5.17) не могут иметь решения. С другой стороны, если существует оптимальная стратегия с от-

личной от нуля последней компонентой, то существование решения задач (5.16), (5.17) уже доказано конструктивно.

Полученные результаты позволяют свести решение игр к решению задач линейного программирования и применить к ним, например, симплекс-метод.

Сведением задач линейного программирования к играм пользуются реже.

Мы познакомились с несколькими основными методами решения мат-

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

Сноу можно рекомендовать для решения игр небольшой размерности. Наиболее простым в вычислительном плане является метод Брауна, но его сходимость дос-

таточно быстро ухудшается с ростом размерности, поэтому этот метод можно ре-

комендовать для решения игр средней размерности (порядка нескольких десят-

ков). Для решения игр большой размерности (порядка нескольких сотен или ты-

сяч) предпочтительнее метод сведения их к задачам линейного программирова-

ния.

§ 5.2. Нахождение седловых точек и точек равновесия

Седловые точки функции g(u1 , u2 ) на U1 × U 2 можно находить как решения максиминной и минимаксной задач (см. теорему 2.1)

ется седловой, а их несовпадение позволит сделать вывод о том, что седловых то-

чек нет (как и в случае, когда задачи (5.21), (5.22) не имеют решения). Однако решение максиминной и минимаксной задач весьма сложно, проще находить сед-

которые ничем не отличаются от условий максимума или минимума по всем пе-

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

мума находятся среди стационарных точек, удовлетворяющих условиям (5.23).

Для выделения седловых точек требуется дополнительная проверка убывания

нечно, аналитическое решение системы уравнений (5.23) и последующая провер-

ка возможны лишь в простейших случаях.

Численные методы нахождения седлойых точек также аналогичны методам поиска экстремума. Среди них наиболее распространенными являются гра-

диентные методы, представляющие собой итеративные процедуры решения сис-

темы уравнений (5.23). Для случая отсутствия ограничений (когда множест-

Общая задача поиска условного экстремума (задача математического про-

граммирования) формулируется следующим образом: найти верхнюю грань функции f (x) на множестве X

где

где

Таким образом, величину ν 1 можно интерпретировать как нижнюю цену ан-

тагонистической игры, в которой первый игрок выбирает х R, второй игрок вы-

бирает вектор множителей Лагранжа у ≥ 0, а платежной функцией является функция Лагранжа.

Двойственной к задаче (5.25), (5.26) называется задача поиска нижней грани функции ϕ ( y)

x R

Значит, экстремальное значение двойственной задачи равно верхней цене той же самой игры. Соотношением двойственности называется равенство

ν 1 = ν 2 ,что означает существование цены игры с платежной функцией L(x,y) в

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

цены игры с функцией Лагранжа или, что то же самое, существованию сед-

ловой точки (x0 , y 0 ) функции L(x,y) на R × { y ≥ 0} .

Следовательно, решение двойственных задач математического програм-

мирования сводится к решению антагонистической игры (ранее аналогичная связь была установлена для линейного программирования и матричных игр).

Сложнее найти седловые точки и цену антагонистической игры в сме-

шанных стратегиях. Для этой бесконечномерной задачи в настоящее время не существует общих методов решения. При большой размерности переменных u1 и u2 возможен подход, основанный на аппроксимации. Заменяя непрерывную анта-

гонистическую игру матричной и решая последнюю с помощью одного из мето-

дов, рассмотренных в §5.1, можно получить приближенное решение непрерывной игры в виде распределений вероятностей, сосредоточенных в конечном числе то-

чек. Однако с ростом размерности u1 и u2 размерность соответствующей мат-

ричной игры растет очень быстро, что приводит к практической неразрешимости последней.

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

шанные стратегии в явном виде или показать, что они сосредоточены в конечном числе точек. Наиболее полно эти вопросы изложены в монографии [7].

Способ нахождения точек равновесия в бескоалиционной игре п лиц анало-

гичен способу определения седловых точек. Если функции выигрыша игроков gi

являются непрерывно дифференцируемыми и точка равновесия ( u10 ,..., un0 )

является внутренней для произведения множеств U1 × ...× U n , то необ-

ходимо выполнение условий

∂g(u 0 ,..., u 0 )

1 n = 0, i = 1, n, (5.29)

∂u i

где ∂gi — вектор частных производных по векторной переменной иi.

∂ui

Равенства (5.29) вытекают из обычных условий экстремума, так как в точке равновесия каждая функция gi достигает максимума по "своей" переменной при ui фиксированных остальных переменных. В общем случае надо учитывать воз-

можную принадлежность равновесных стратегий ui0 границам множеств U i (для всех индексов i или для их части), поэтому либо отдельно проверяют граничные точки (если множества Ui имеют простой вид), либо вместо (5.29) используют условия экстремума с ограничениями (например, неположительность производ-

ных по всем допустимым направлениям). Рассмотрим процесс нахождения рав-

новесных ситуаций на следующем примере.

Пример 5.1 (модель рынка). Имеется п участников, которые могут произ-

водить некоторый однородный товар и продавать его на рынке. По-

тенциальные покупатели данного товара обладают все вместе суммой денег,

равной а. Если i-й участник производит и выставляет на рынке количество

цена, что весь предлагаемый товар покупается. Это значит, что цена равна c = au − 1.

На производство не накладывается никаких условий, кроме естественного условия неотрицательности, т.е. ui ≥ 0, i = 1, n , но оно связано с затратами.

Возьмем простейший случай, когда затраты линейны, т.е. равны

bi ui , i = 1, n (у каждого участника, вообще говоря, свой коэффициент про-

порциональности bi). В таких условиях прибыль i-го участника равна

( ) au − 1u − b u , u > 0;

gi u1 ,..., un = = i i i

0, u 0

Примем ее в качестве функции выигрыша данного участника.

Для определения ситуаций равновесия, лежащих внутри прямого про-

изведения пространств стратегий участников (в данном случае неотрица-

тельного ортанта n-мерного пространства), имеем систему уравнений

(при и > 0)

∂gi (u1 ,..., un ) = au − 1 − aui u − 2 − bi = 0, i = 1, n,

∂ui

откуда

Просуммировав n уравнений (5.30), имеем с учетом равенства ∑n ui = u

i= 1

одно уравнение для определения u:

i= 1

( ui0 ,..., un0 ) действительно будет равновесной. Это условие означает близость про-

изводственных затрат всех участников. Если же данное условие не выполняется,

то некоторые участники могут “выбыть из игры” (для них ui0 = 0 ). Следует отме-

тить, что точка равновесия, определяемая (5.33), не является паретовской. Участ-

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

практически не произведя затрат (в пределе нуль). Эту сумму можно распреде-

лить так, что все участники получат большую прибыль, чем в точке равновесия.

Однако такая ситуация уже не будет равновесной, т.е. каждому участнику

вотдельности выгодно ее нарушить. Чтобы подобные ситуации могли выступать

вкачестве решений, необходимо выйти за рамки бескоалиционных игр.

В общем случае для нахождения точек равновесия, как и седловых точек,

используются численные процедуры итерационного типа. Среди них распро-

странены градиентные методы, связанные с решением системы уравнений (5.29).

Некоторые из этих методов изложены в работе [1].

Опишем одну процедуру нахождения равновесия, которую можно интер-

претировать как динамический процесс принятия индивидуально выгодных не-

дальновидных решений, весьма напоминающий процесс обучения в методе Брау-

называемый процедурой нащупывания (одновременного) по Курно. Процедуру

(5.34) можно понимать так, что каждый игрок в ситуации uk максимизирует свой выигрыш, считая, что стратегии остальных игроков не меняются (для этого ему надо знать только свою функцию выигрыша и множество стратегий). В результа-

те происходит переход из ситуации uk в ситуацию uk + 1 и т.д.

Определение 5.2. Ситуация равновесия u, в игре Г называется устойчивой,

если процесс (5.34) сходится к ней при любой начальной позиции (ситуации) u1 .

Если ситуация равновесия устойчива, то ее можно гарантировано найти с помощью итерационного процесса (5.34), но, конечно, такая сходимость имеет место не всегда (очевидно, необходима единственность равновесия). Общих ус-

ловий устойчивости не существует. При надлежащем выборе начальной ситуации и ограничении множества наилучших откликов окрестностью равновесия можно находить локально устойчивые равновесия. Условия локальной ус-

тойчевости формулируются в терминах вторых производных функций выиг-

рыша достаточно просто (см. [10]).

Упражнения и задачи

5.1.Используя геометрический метод, найдите решение игр с матрицами:

−1 − 1

5.2.Преобразуя матрицу выигрышей и используя геометрический метод,

5.3.Найдите решение матричной игры методом Шепли – Сноу.

5.4.Решите методом Брауна матричную игру

−1 3 − 3

5.5.Решите симплекс-методом игру с матрицей: