УДК 677
Двухуровневая игра
с веерной иерархией на нижнем уровне
Л. В. Смирнова
Рассматривается двухуровневая иерархическая игра с бескоалиционным вариантом на нижнем уровне иерархии при использовании аналога решения по Штакельбергу и концепции равновесия по Бержу-Вайсману.
Ключевые слова: управляемые системы, двухуровневая система, условие равновесности по Бержу-Вайсману, теория иерархических игр, бескоалиционный вариант.
введение
Иерархические игры моделируют конфликтно управляемые системы с иерархической структурой. Такая структура определяется последовательностью уровней управления, следующих друг за другом в порядке определенного приоритета. В математической постановке иерархические игры классифицируются по числу уровней. Простейшей из них является двухуровневая система, состоящая их одного элемента верхнего уровня – центра и элементов нижнего уровня – игроков. Управляющий центр имеет право первого хода и может ограничивать возможности игроков нижнего уровня. Иными словами, иерархические игры - это класс игр, характеризующихся прежде всего неравноправным положением её участников. Особенность игры состоит в наличии на нижнем уровне иерархии не менее двух игроков. В связи с этим возникает вопрос о выборе игроками нижнего уровня правил рационального поведения. Предположим, что среди игроков нижнего уровня образование коалиций либо невозможно, либо запрещено правилами ведения игры, то есть игроки действуют изолированно.
Таким образом, в статье рассматривается иерархическая система с бескоалиционным вариантом на нижнем уровне. В этом случае будем считать, что выбор стратегий игроков нижнего уровня продиктован стремлением к достижению одной из равновесных ситуаций. В данной работе ограничимся концепцией равновесия по Бержу-Вайсману.
постановка задачи
Двухуровневая игра с одним игроком верхнего уровня иерархии и бескоалиционной игрой N лиц на нижнем уровне задается упорядоченной четверкой
Здесь множество порядковых номеров игроков (подсистем) нижнего уровня иерархии ; 0 – порядковый номер игрока верхнего уровня (центра), который распоряжается выбором своей стратегии . Стратегию –го игрока нижнего уровня иерархии будем отождествлять с вектор-функцией , предполагая при этом измеримость по Борелю компонент (этот факт обозначаем ).
Порядок ходов в игре следующий. Первый ход делает центр (игрок верхнего уровня иерархии), сообщая всем игрокам нижнего уровня свою стратегию . Затем (второй ход) игроки нижнего уровня выбирают свои стратегии , , которые совместно с образуют ситуацию игры . На множестве таких ситуаций , где , определена функция выигрыша каждого -го игрока , значение которой в конкретной ситуации называют выигрышем игрока . Окончательный (третий ход) делает центр, формируя свою стратегию , исходя из значения функционала . Будем считать, что при формировании своих стратегий (с учетом порядка ходов) все игроки стремятся к увеличению своих выигрышей. При этом в первую очередь, возникает вопрос о формализации «подходящего» решения игры .
Поясним подход, используемый далее в определении решения игры для случая, когда на нижнем уровне иерархии функционирует лишь один игрок (то есть и поэтому ), пусть также . При этом используем возможный аналог максимакса для однокритериальной задачи
.
Аналог максимакса для формализуем в два этапа.
I этап: для каждого строим множество
,
то есть множество состоит из точек , в которых реализуется максимум функции при заданном ; эту операцию естественно назвать построением внутреннего максимума.
II этап: предполагая существование измеримого по Борелю селектора многозначного отображения , построим суперпозицию и для заданного числа найдем стратегию такую, что
.
Пару (ситуацию) естественно назвать - максимаксимальным решением задачи (аналог решения двухуровневой игры по Штакельбергу и аналог внешнего максимума в максиминной задаче).
Следуя изложенному подходу, решение игры также будем определять в два этапа.
1 этап: для бескоалиционной игры лиц , которую получаем из , фиксируя , именно,
, (1)
в качестве аналога внутреннего максимума (этап I) используем концепцию равновесности по Бержу-Вайсману: ситуацию назовем удовлетворяющей условию равновесности по Бержу-Вайсману в игре , если
, (2)
здесь ; операция (2) «порождает» многозначное отображение
, (3)
причем ; пусть - измеримый по Борелю селектор отображения ; здесь и далее означает множество всех подмножеств компакта .
2 этап (аналог внешнего максимума из этапа II): для заданной постоянной найдем стратегию центра , при которой
.
С учетом упомянутого выше порядка ходов для игры ситуацию естественно называть -максимальным решением игры .
Цель предлагаемой статьи состоит в том, чтобы установить существование указанного -максимального решения при обычных для математической теории игр ограничениях на элементы игры .
свойства равновесия по Бержу-Вайсману
В этом разделе будем рассматривать бескоалиционную игру лиц для каждой стратегии центра . Напомним, что ситуация игры удовлетворяет условию равновесности по Бержу-Вайсману, если
, (4)
здесь , тогда равенства (4) можно представить в эквивалентном виде
. (5)
Далее будет установлен ряд свойств ситуаций, удовлетворяющих условию равновесности по Бержу-Вайсману, которые затем используются в разделе 3 при доказательстве существования -максимального решения игры .
Утверждение 1. Если при каждом в игре (1) множества суть компакты, а функции непрерывны на , то множество ситуаций из (3), удовлетворяющих условию равновесности по Бержу-Вайсману есть компакт (может быть и пустой).
Доказательство. В игре фиксируем какую-либо (произвольную) стратегию центра и тогда из (при фиксированном ) получаем бескоалиционную игру лиц . Множество ситуаций , удовлетворяющих условию равновесности по Бержу-Вайсману определено в (3). Заметим, что множество ограничено, так как является подмножеством компакта .
Покажем, что замкнуто. Для этого рассмотрим произвольную бесконечную последовательность точек из . Так как , а есть компакт, то существует подпоследовательность и ситуация такие, что (покомпонентно)
. (6)
Множество замкнуто, если . Установим этот факт от противного, предположим, что . Тогда найдутся (см. (4) и (5)) номер и набор стратегий игроков такие, что
(7)
Из (7), а также из непрерывности на , и, следовательно, непрерывности на получаем существование настолько малого числа такого, что для всех ситуаций игры , при которых евклидова норма (и, следовательно ), будет
(8)
Выберем теперь такой «достаточно большой» номер , чтобы
при всех (что возможно вследствие (6)). Тогда для этих из (8) следует
.
Данное неравенство противоречит тому факту, что и, поэтому является ситуацией игры (1), удовлетворяющей условию равновесности по Бержу-Вайсману, то есть
Из ограниченности и замкнутости множества следует его компактность.
Следствие 1. При выполнении требований утверждения 1 множество
является компактом (может и пустым) при каждом .
Здесь - множество ситуаций игры , удовлетворяющих условию равновесности по Бержу-Вайсману.
Справедливость следствия 1 сразу получаем из утверждения 1 и непрерывности вектор-функции по для каждого (при непрерывном отображении компакт переходит в компакт).
Для игры введем функцию
(9)
где ситуации , а стратегия центра фиксирована. Будем считать, что пара является седловой точкой , если при всех и справедлива цепочка неравенств
. (10)
Утверждение 2. Если функция из (9) имеет седловую точку , определенную в (10), то ситуация удовлетворяет условию равновесности по Бержу-Вайсману, то есть для выполняется система неравенств (5).
Доказательство. С учетом (9) неравенства (10) примут вид
(11)
Неравенства (11) выполнены и для . Отсюда, учитывая равенство
,
получим
Значит для всех и
Тогда, согласно приведенному выше определению, ситуация удовлетворяет условию (5) равновесности по Бержу-Вайсману.
Замечание 1. Утверждение 2 сводит задачу построения ситуации, удовлетворяющей условию равновесности по Бержу-Вайсману к нахождению седловой точки функции (9). Вопросам численного нахождения экстремумов для функций вида (9) посвящено значительное число публикаций (см. например, [1], [2]).
Перейдем к свойству многозначного отображения из (3), связанному с полунепрерывностью сверху. Итак, пусть выполнены требования утверждений 1 и 2, то есть имеют место
Условие 1. Множества суть компакты и функции выигрыша непрерывны на (где ).
Условие 2. Скалярная функция из (9) при каждом имеет седловую точку (определенную в (10)).
Построим многозначное отображение (3):
По утверждению 2 множество при каждом , а по утверждению 1 для всех множество есть компактное подмножество компакта . Таким образом, каждой стратегии центра поставлен в соответствие непустой компакт , точки которого в игре удовлетворяют условию равновесности по Бержу-Вайсману.
Отображение называется полунепрерывным сверху по включению при изменении , если справедливо следующее заключение:
пусть есть некоторая последовательность, имеющая предел (покомпонентный)
, , (12)
и пусть
- (13)
соответствующая ей последовательность ситуаций игр , также имеющая предел
. (14)
Тогда отображение полунепрерывно сверху по включению при изменении , если
(15)
Утверждение 3. При выполнении условий 1 и 2 многозначное отображение , где
полунепрерывно сверху по включению при изменении .
Доказательство. Используем определение (12)–(15). Пусть - некоторая последовательность стратегий центра, сходящаяся к , то есть имеет место (12). По построим соответствующую последовательность ситуаций, удовлетворяющих условию равновесности по Бержу-Вайсману
и имеющую предел
.
Заметим, что множество есть компакт (как декартово произведение компактов ), поэтому из последовательности всегда можно выделить подпоследовательность, сходящуюся к точке из .
Наконец, докажем, что справедливо включение
.
Предположим противное: пусть ситуация , то есть не удовлетворяет условию (4) равновесности по Бержу-Вайсману в игре . Тогда найдутся, по крайней мере, одна ситуация и номер такие, что
. (16)
Вследствие непрерывности на , существования пределов (12) и (14), а также выполнения неравенства (16) найдется достаточно большое целое число , что при будет
.
Эти неравенства противоречат условию равновесности по Бержу-Вайсману ситуаций в играх . Итак, установлено, что при выполнении условий 1 и 2 определенное в (3) многозначное отображение полунепрерывно сверху по включению при изменении .
равновесное решение иерархической двухуровневой игры
С учетом указанного в разделе 1 порядка ходов и применения на нижнем уровне иерархии концепции равновесности по Бержу-Вайсману, приведем формальное определение -равновесного решения иерархической двухуровневой игры .
Пусть априори задано (или выбрано) число ; далее BVS - первые английские буквы фамилий Бержа, Вайсмана и Штакельберга соответственно.
Определение. Ситуацию назовем -равновесным по BVS решением игры , если при каждой стратегии центра
а) справедливы равенства
, (17)
б) имеет место неравенство
. (18)
Замечание 2. Требование (17) означает, что при каждом ситуация удовлетворяет условию равновесности по Бержу-Вайсману (отсюда взятые первые две буквы BV в определении -равновесного по BVS решения). Ограничение (18) совместно с (17) означает, что в игре используется известная в теории иерархических игр концепция оптимальности по Штакельбергу [3] (поэтому использована последняя буква S в определении BVS решения).
Замечание 3. Случаю, когда на нижнем уровне иерархии используется (в играх ) концепция равновесности по Нэшу [4] посвящена работа [5].
Существование введенного выше -равновесного по BVS решения (при любых ) устанавливается в следующем утверждении.
Теорема. Предположим, что в игре
10) множества суть непустые компакты, а функции выигрыша непрерывны на ;
20) скалярная функция
при каждом имеет седловую точку , именно,
.
Тогда при любом в игре существует -равновесное по BVS решение.
Доказательство разобьем на два этапа. На этапе I докажем существование ситуации , , удовлетворяющей условию равновесности по Бержу-Вайсману в игре (то есть равенствам (17)) при каждой стратеги центра . На этапе II покажем, что для любого постоянного числа существует своя стратегия центра , при которой имеет место неравенство (18). Тогда, согласно приведенному выше определению, пара и будет -равновесным по BVS решением игры .
Этап I. Рассмотрим многозначное отображение , определяемое множеством ситуаций бескоалиционной игры
,
при каждом удовлетворяющих условию равновесности по Бержу-Вайсману:
Множество ,
во-первых, не пусто при каждом (согласно утверждению 2 и требованию (20) теоремы),
во-вторых, при каждом является компактным подмножеством множества ситуаций (согласно утверждению 1 и требованию (10) теоремы),
в-третьих, многозначное отображение полунепрерывно сверху по включению при изменении (согласно утверждению 3).
Учитывая, кроме этих трех фактов, компактность и непрерывность , по теореме об измеримом выборе [6, с. 26] получаем, что существует измеримый по Борелю селектор (измеримая по Борелю вектор-функция ), который при каждой стратегии центра и каждом , реализует равенство (17) и поэтому удовлетворяет требованию (а) приведенного выше определения.
Этап II. Функция выигрыша центра ограничена сверху, как непрерывная функция, определенная на компакте . С помощью найденной на этапе I измеримой по Борелю вектор-функции построим суперпозицию . Скалярная функция ,
во-первых, ограничена сверху, то есть найдется число такое, что при всех ,
во-вторых, функция измерима по Борелю (как суперпозиция непрерывной и измеримой функции).
Пусть теперь - произвольное положительное число. Тогда для каждого можно указать такую «свою» стратегию центра , что для всех имеет место неравенство
,
то есть выполнено неравенство (18) из определения -равновесной по BVS ситуации (в игре ). Следовательно, в результате этапов I и II показано, что в игре существует пара , удовлетворяющая требованиям (а) и (б) приведенного определения равновесной по BVS ситуации. Теорема доказана.
заключение
Для двухуровневой иерархической игры с бескоалиционным вариантом на нижнем уровне формализовано понятие -равновесного по BVS решения и установлены достаточные условия существования указанного решения.
библиографический список
-
Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.
-
Федоров В.В. Численные методы максимина. М.: Наука, 1979.
-
Von Stackelberg H. Marktform and Gleichgewicht. Vienna: Springer, 1934 (Англ. перев.: The theory of the market economy. Oxford: Oxford University Press, 1952).
-
Nash J.F. Non-cooperative games // Ann. Math.. 1951, № 54.
-
Жуковский В.И., Смирнова Л.В. Двухуровневая игра с бескоалиционным вариантом на нижнем уровне иерархии // Spectral and Evolution Problems, Ukraine, 2008, Vol. 18.
сведения об авторах
Российский заочный институт текстильной и легкой промышленности.
Россия, Москва
Достарыңызбен бөлісу: |