Главная
страница 1
скачать файл
УДК 519.6

ПОСТРОЕНИЕ РАВНОВЕСНЫХ НАБОРОВ СТРАТЕГИЙ В ИГРАХ «В ПЕРЕМЕЩЕНИЯХ»

Лутманов Сергей Викторович

ПГУ, кафедра ПУиИБ, Генкеля, 7, mpu@psu.ru



Чернышев Кирилл Андреевич

ГК ИВС, Тимирязева 24а, ka.chernyshev@yandex.ru


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



1. Введение.
Рассмотрим некий класс игр, назовем его играми «в перемещениях», который является переходным от игр в нормальной форме к дифференциальным играм. Указанный класс игр имеет простой геометрический смысл.
1. Постановка игры «в перемещениях».
Рассмотрим некий класс игр, назовем его играми «в перемещениях», который является переходным от игр в нормальной форме к дифференциальным играм. Указанный класс игр имеет простой геометрический смысл.

В тоже время ряд результатов, полученных для игр «в перемещениях», в дальнейшем используется в линейных дифференциальных играх.



Игра 1. В игре участвуют игроков. Каждый игрок независимо от других назначает точке, расположенной в начале координат пространства , перемещение , стесненное геометрическим ограничением , . Множества , являются выпуклыми и компактными. Результирующее перемещение управляемой точки представляет собой геометрическую сумму выбранных игроками перемещений. В пространстве заданы выпуклых компактных множеств , называемых целевыми множествами соответствующих игроков. Платой – го игрока, , служит расстояние от финального положения управляемой точки до целевого множества этого игрока. Цель каждого из игроков состоит в минимизации своей платы.

На рис.1 приводится геометрическая интерпретация данной игры при .

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

Игру 1 будем называть игрой лиц «в перемещениях».

Заметим, что в силу теоремы Вейерштрасса минимумы и максимумы функций плат игроков в играх «в перемещениях» гарантированно существуют.

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

.

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

В принятых предположениях область достижимости игрока представляет собой выпуклое и компактное множество в пространстве .

Величина

(1)

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



2. Основные теоремы, обосновывающие реализацию принципа оптимальности в играх «в перемещениях».
Приведем ряд лемм и теорем необходимые при дальнейших исследованиях.

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



Лемма 1. Справедливо равенство

. (2)

Лемма 2 выражает наименьшее расстояние от управляемой точки до целевого множества, реализованное i-м игроком, при условии, что остальные игроки выбрали стратегии .



Лемма 2. Справедливо равенство

. (3)

Следующая лемма дает условие, при котором максимум правой части уравнения (3) достигается на единственном векторе.



Лемма 3. Пусть . Тогда максимум в правой части равенства (3) достигается на единственном векторе .

Сформулированная ниже теорема выражает необходимые условия оптимальности перемещения .



Теорема 1. Пусть . Для того, чтобы перемещение удовлетворяло равенству



необходимо, чтобы оно удовлетворяло условию

. (4)

Факт оптимальности перемещения можно также установить, вычислив величину по формуле (3). Если выполняется равенство



, ,

то перемещение является минимизирующим.

Теорема 2 дает ответ на вопрос определения искомого равновесного набора перемещений.

Теорема 2. Пусть для равновесной ситуации при всех выполнено неравенство

.

Тогда для всех множество состоит ровно из одного элемента , а перемещение необходимо удовлетворяет условию

.

Один из самых распространенных подходов к формированию принципа оптимальности в играх нескольких лиц связан с обобщением понятия приемлемой и равновесной ситуаций.



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

. (5)

Ситуация называется равновесной по Нэшу, если она приемлема для каждого игрока, т.е., если неравенство (5) выполняется для всех .

3. Алгоритм нахождения равновесной ситуации по Нэшу
Далее на примере игры 1 приведем алгоритм нахождения оптимального решения по Нэшу.

Функции платы в игре 1 определяются формулами



Приведем один способ построения равновесной по Нэшу ситуации. Для всех определим функцию из условия



.

Для функции



,

определенной формулой





,

строим набор векторов , удовлетворяющий условию



.(6)

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



(7)

Начальная ситуация выбирается произвольно. Далее полагаем









где


(8)

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



Теорема 3. Пусть последовательность (7) сходится и ситуация - её предел. Тогда для всех и справедливо неравенство

.

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

В силу теоремы 2 искомый равновесный набор перемещений необходимо вычисляется по формуле

.

Этот набор будет действительно равновесным по Нэшу, если при всех выполняется условие



. (9)

Доказательства теорем и лемм, приведенных в пунктах 2 и 3, находятся в публикации [1].


4. Модельный пример.
Рассмотрим следующую задачу

Теперь для этого примера найдем равновесную по Нэшу ситуацию. Из условия



находим функции . Далее строим функции





,

и набор векторов , удовлетворяющий условию (6).



,.

При этом







.

Тогда набор перемещений игроков, удовлетворяющий необходимым условиям оптимальности по Нэшу, имеет вид



,.

В случае, когда все игроки придерживаются этого набора стратегий, управляемая точка переместится в положение



.

Непосредственно проверяется, что расстояния от точки до целевых множеств игроков соответственно равны.



.

Таким образом, условия (9) выполнены, и набор перемещений образует равновесную ситуацию.

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

.

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

Аналогично проверим для остальных игроков:

, ,

, .

Получили следующее



,

,

.

Библиографический список


  1. Лутманов С. В. Сравнительный анализ принципов равновесия и компромисса в играх нескольких лиц «в перемещениях» // Вестник Пермского университета, Математика, Механика, Информатика, Вып.2. (2), Пермь, 2010, С.46-54.

CONSTRUCTION OF EQUILIBRIUM SETS OF STRATEGIES IN GAMES «IN TRANSITIONS»

Lutmanov Sergey Victorovich

PSU, MP and IS department, Genkelya, 7, mpu@psu.ru



Chernyshev Kirill Andreevich

GC ICS, Timiryazeva 24a, ka.chernyshev@yandex.ru



In this article for the game of several persons «in transitions» the unique algorithm of construction Nash equilibrium of a set of strategy is developed. The algorithm is realized in the form of the operating program. On a concrete example of game of three persons its efficiency is shown. In particular, it is shown that individual evasion of the player from the strategy ordered to it by an equilibrium set, leads to deterioration of a prize of this player.
скачать файл



Смотрите также:
В статье разработан оригинальный алгоритм построения равновесного по Нэшу набора стратегий в игре нескольких лиц «в перемещения». Алгоритм реализован в виде действующей программы
74.89kb.
А. В. Батов1, В. Ю. Королев
30.64kb.
Лабораторная работа №3 на тему «Хэш функции: алгоритм n-хэш»
66.65kb.
А. Н. Красненко
47.61kb.
Рассмотрена задача оценивания параметров регрессионных моделей. Для ее решения предлагается новый алгоритм, основанный на совместном использовании метода максимального правдоподобия и техники построения кривых Пирсона
19.5kb.
Определение астрономических координат автоматизированным зенитным телескопом
130.75kb.
Алгоритм методической работы по приведению программ спортивной подготовки к требованиям федеральных стандартов спортивной подготовки по видам спорта
162.55kb.
1. Інтерпретація формул логіки висловлювань. Інтерпретація формул логіки першого ступеня. Алгоритм Девіса-Патнема. Алгоритм Куайна
106.42kb.
Быстрое преобразование Фурье (бпф) это алгоритм вычисления преобразования Фурье для дискретного случая
428.62kb.
Решение колебательной задачи в естественных координатах с применением методов ab intio и теории функционала плотности (dft-методов)
60.21kb.
Новый алгоритм петрохимических пересчетов на основе cipw нормы
67.77kb.
Информация Пенсионного фонда России от 5 апреля 2012 г. "Об увеличении стоимости набора социальных услуг"
15.42kb.