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

Графикмногозначнойфункции α = α(β) изображённарисунке12.3.

Он соответствует ломаной EFBKL.

Определим наилучшую реакцию второго игрока на действие первого в соответствии с (12.3). Тогда последнее означает

β arg max β[0,1]{(xT B )1,(xT B )2} =arg max β[0,1]{6α−2,1−4α};

График многозначной функции β= β( α ) изображён на рисунке 12.3. Он соответствует ломаной ОАВСD.

Для аналитического нахождения равновесия рассмотрим систему двух уравнений

1,β[0, 38 ), α = [0,1],β = 38 ,

0,β( 3 ,1].

8

110

Решимсистемуграфически. Построимграфикифункцийводной системекоординат. Результатпостроенияпредставленнарисунке12.3.

Здесь функция наилучшей реакции первого игрока α = α(β) представлена ломаной EFBKL, а функция наилучшей реакции второго игрока β = β( α) представлена ломаной OABCD. Общие

точки двух графиков соответствуют равновесным ситуациям. Такая точка одна: C(3/10, 3/8). Она определяет равновесное решение(x*, y*) X×Y= [0, 1]2 × [0, 1] 2; где стратегии x* = (3/10, 7/10), y*= (3/8, 5/8). Вычислим выигрыши игроков в равновесной ситуации f(x*, y*) = (f1(x*, y*), f2(x*, y*)) и выигрыши

Ответ: x* = (3/10, 7/10), y*= (3/8, 5/8);f(x*, y*) = (0,5, -0,2).

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

Задача 12.1. Решить биматричную игру, заданную двумя матрицами выигрышей первого и второго игроков

Задача 12.2. Решить биматричную игру, заданную двумя матрицами выигрышей первого и второго игроков

111

Задача 12.3. Указать те значения параметра p R, что соответствующая биматричная игра имеет решение в чистых стратегиях. Указать это решение.

112

§13. Существование равновесия по Нэшу вбескоалиционнойигре

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

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

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

Рассматривается бескоалиционная игра (1.1), в которой представлено конечное число игроков N ={1,...,n}. Обсудим

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

113

Стратегии игроков будем отождествлять с точками евклидова векторного пространства, т.е xi Rmi , i N. Такой подход

соответствует смешанному расширению конечной бескоалиционной игры. В этом случае стратегии игрока представляются точкам фундаментального симплекса (5.1, 5.2) в конечномерном евклидовом пространстве. Будем рассматривать компактные множества

(Определение 7.2.) стратегий X i Rmi , i N.

Так в евклидовом пространстве R1 = R отрезок [a, b] является ограниченным и замкнутым множеством, значит, компактом; интервал (a, b) является ограниченным и не замкнутым множеством. В евклидовом пространстве R множество положительных действительных чисел является неограниченным и не замкнутым. Это множество обозначается (0, ∞ ). Отметим, что множества стратегий в игровых задачах из §1 – 4 являются конечными. В евклидовом пространстве конечное множество является компактным. Рассматривая смешанное расширение конечной игры. Множество смешанных стратегий игрока было определено, как m - 1 мерный симплекс в m – мерном евклидовом пространстве и определяется ортами (5.3). Это также компактное множество.

Множество стратегий X i Rmi в евклидовом пространстве является выпуклым, если x', x" X ,λ [0,1] выполнено

включение λ x'+λ x" X (Определение 7.3). Так отрезок [a, b], интервал (a, b), бесконечное множество (0, ∞ ) являются выпуклыми, а множество чистых стратегий в игровых задачах из

§1 - 4 нет.

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

114

Задача оптимизации (и игровая задача) в своей формализации кроме множества стратегий должна содержать ещё функцию цели. Это функция с областью определения в некотором евклидовом пространстве (или на его подмножестве) и значениями – действительными числами. Часто такая функция предполагается непрерывной. Функция цели

называется непрерывной в точке x0 Rm , если предел функции в

точке равен значению функции в этой точке. Функция в (13.1) является непрерывной на области определения, если она непрерывна в каждой точке области определения.

В терминах компактных множеств и непрерывных функций можно сформулировать “классическую” задачу математического программирования (задачу максимизации).

Задача (классическая задача математического программирования). Пусть задано компактное множество X в

евклидовом пространстве Rm и функция цели f : Rm → R

непрерывна. Найти точку x* X , что доставляет максимум этой

функции на X, т.е.такое x* X , что f (x*) ≥ f (x), x X .

Существование решения задачи математического программирования устанавливает вторая теорема Вейерштрасса (§8). В задаче (8.1) – (8.3) область допустимых значений является ограниченной, замкнутой и, значит, компактной. Функция цели в задаче является линейной и, значит, непрерывной. По второй теореме Вейерштрасса в такой задаче существует максимальное значение у функции цели. Учитывая линейные ограничения для области допустимых значений (8.1) можно показать, что она является многоугольником и максимум достигается в одной из его вершин.

Важное место в построении теории имеют функции со специальными свойствами. Функция f (x) из (13.1) называется вогнутой на области определения X Rm , если множество X выпукло и x', x" X , λ [0,1] выполнено неравенство

115