Файл: В. А.МАТВЕЕВ.pdf

Если в (13.2) λ (0,1) выполнено строгое неравенство <, то

функция f (x) называется строго вогнутой на множестве X. Эта функция называется выпуклой (строго выпуклой), если в (13.2) использовать неравенство ≥ (>). Функция f (x) из (13.1) называется квазивогнутой на области определения X Rm , еслиβ R выпуклы множества уровня {z X | f (z) ≥ β}. Если в

множестве уровня использовать неравенство ≤ , то соответствующая функция называется квазивыпуклой на X.

Математическое программирование изучает теорию и методы решения задач о нахождении экстремумов (максимумов и минимумов) функций на множествах евклидова пространства. В частности здесь разрабатываются численные методы нахождения экстремумов. Один из них есть симплекс – метод из §10.

Бескоалиционная игровая задача в определённом смысле является обобщением задачи математического программирования. Если в задаче математического программирования наилучшее (оптимальное) в том или ином смысле решение принимает одно лицо, то в игровой задаче несколько лиц, n - игроков осуществляют выбор. В бескоалиционной задаче каждый игрок делает выбор так, чтобы доставить наиболее возможное значение “своей” функции цели. Бескоалиционность игры проявляется в том, что в ней предварительные переговоры и обязывающие соглашения между игроками до принятия решения запрещены. Такого рода действия, связанные с предварительными договорённостями, являются содержанием другой, кооперативной теории игр.

Здесь следует отметить, что бескоалиционная игра (как и кооперативная игра) является математической моделью, которая изучается математическими методами. Прообразами такой теории является реальное взаимодействие отдельных лиц, организаций, фирм, стран и т.д. Это процессы кооперации и конфликта. Такая математическая теория поставляет модели для

116

экономики, социологии, психологии, политологии и многих других гуманитарныхдисциплин. Нореальноевзаимодействиев теорияигр неизучается. Здесьисследуютсятолькомодели. Такнараннихэтапах развития в теории игр была популярна модель карточной игры – покера. Но никогда в этой науке не стояла задача создания теории салонных(карточных) игр. Изсказанногоследуетважныйвывод. Так как в теории игр рассматриваются модели, то предполагаются, что в них участвуют идеальные игроки. Они не делают ошибки, не допускают неточности и всегда выбирают наилучшие решения в рамках своей информированности. Говорят, что в моделях представлены рациональные игроки.

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

Такая теорема появилась в середине XX века. Это знаменитая теорема американского математика Джона Нэша. Предложенное им доказательство, а также вся идеология теории игр, быстро получила признание, особенно в прикладных областях, ввязанных с изучением общества. Теория игр поставила большое число моделей, раскрывающих логическую сущность взаимодействия людей. Эта теория изучает рациональное поведение людей, интересы у которых не тождественно совпадают. Большое значение этой теории было подтверждено Нобелевским комитетом, 1994 году присудившим Нобелевскую премию по экономике Джону Нэшу совместно с американцем Джоном Харшаньи и немцем Эрхардом Селтеном за новаторскую разработку концепции равновесия в теории бескоалиционной игры.

Считается, что теория игр как научная математическая дисциплина появилась в 1944 году. Датой её рождения считается публикация книги Неймана Д., Моргенштерна О. Теория игр и экономическогоповедения. Русскийперевод[12] появилсяв1970 году.

117

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

Теорема (Нэш, [15, с.205 -221]). Пусть в бескоалиционной игре Г из (1.1) конечное число игроков n. Для каждого игрока

вогнута на пространстве стратегий X i . Тогда в бескоалиционной

игре существует ситуация равновесия по Нэшу. Доказательство основано на применении теоремы о

неподвижной точке. Существует несколько таких теорем. Для некоторых из них формулировки, доказательства, обсуждения можно найти в [13, 14]. Из них монографию [14] отличает высокий математический уровень, она написана для математически подготовленного читателя. Монография [13] посвящена экономическим приложениям. Приведём схему доказательства, основанную на теореме Какутани [13, c.154; 14, c.336].

Теорема (Какутани). Пусть X – непустое, компактное, выпуклое подмножество евклидового пространства R m .

Многозначное отображение φ : X → X имеет значениями

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

точку, т.е. x* X , что φ(x*) = x *.

Рассмотрим бескоалиционную игру (1.1) и ситуацию

118

x = (x1 ,..., xn ) = f (x−i , xi ) X . Длякаждого i N обозначим

∏ψix (xi ) =ψ(x)

i N

будет замкнутым и выпуклым в пространстве всех ситуаций X. Рассмотрим многозначное отображение x →ψ(x). Оно

является полунепрерывным сверху по включению ввиду того, что в неравенствах из (13.3) стоят непрерывные функции от ситуации x, а при переходе к пределу неравенство сохраняется. Тогда выполнены все условия теоремы Какутани и, значит, существует

неподвижная точка x* X , что φ(x*) = x *. Для этой ситуации перепишем неравенство из (13.3).Получаем

fi (x*) = fi (x−*i , xi* ) ≥ fi (x−*i , xi ), xi X i .

Выполнено условие (3.1) определения и, значит, ситуация x* X является равновесием по Нэшу в бескоалиционной игре (1.1). Теорема доказана.

Часто в теореме Нэша условие вогнутости функции выигрыша игрока i N на множестве его стратегий заменяется условием квазивогнутости.

Если рассматривать игровую задачу примера 12.2 в чистых стратегиях, то для неё не выполнены условия теоремы Нэша. Действительно, множество стратегий первого (второго) игрока представляется двумя изолированными точками в евклидовом

пространстве X = Y ={(1,0);(0,1)} R2 . Это множество не являетсявыпуклым, соответствующаяфункциявыигрышей(заданная

119

матрицейА) неявляетсявогнутой. Проверкачетырёхситуацийвигре по определению 3.1, показывает, что в игре нет равновесия по Нэшу.

Но в смешанном расширении всё меняется. Множество стратегий игрока представляется одномерным симплексом, т.е. компактом. Функция выигрышей является полилинейной, т.е. является линейной по стратегиям отдельного игрока. Такая функция будет вогнутой (и выпуклой) на множестве стратегий. Для смешанного расширения игры примера 12.2 условия теоремы Нэша выполнены. В этом случае равновесие существует. В самом деле, равновесие было найдено с помощью неподвижной точки соответствующего многозначного отображения.

Рассуждения для игры из примера 12.2 в случае отсутствия равновесия в чистых стратегиях дословно переносятся на любую конечную бескоалиционную игру. Итак, из теоремы Нэша получаем Следствие. В конечной бескоалиционной игре Г из (1.1) существует равновесие по Нэшу, возможно в смешанных

стратегиях.

Задачидлясамостоятельногорешения

Задача 13.1. Решить задачу математического программирования f (x, y) = x2 + xy − 2 → extr;

4x2 −4 ≤ y ≤ 0.

Задача 13.2. Решить задачу математического программирования f (x, y) = x2 + y 2 −9xy + 27 → extr;

0 ≤ x ≤ 3,

0 ≤ y ≤ 3, x, y ≥ 0.

Задача 13.3. Найти локальные максимумы функции

120

121