Двухуровневая игра с веерной иерархией на нижнем уровне

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Двухуровневая игра с веерной иерархией на нижнем уровне

Л.В. Смирнова

Аннотация

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

Ключевые слова: управляемые системы, двухуровневая система, условие равновесности по Бержу-Вайсману, теория иерархических игр, бескоалиционный вариант.

Введение

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

Таким образом, в статье рассматривается иерархическая система с бескоалиционным вариантом на нижнем уровне. В этом случае будем считать, что выбор стратегий игроков нижнего уровня продиктован стремлением к достижению одной из равновесных ситуаций. В данной работе ограничимся концепцией равновесия по Бержу-Вайсману.

Постановка задачи

Двухуровневая игра с одним игроком верхнего уровня иерархии и бескоалиционной игрой 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 решения (при любых ) устанавливается в следующем утверждении.

Теорема. Предположим, что в игре

1⁰) множества суть непустые компакты, а функции выигрыша непрерывны на ;

2⁰) скалярная функция

при каждом имеет седловую точку , именно,

.

Тогда при любом в игре существует -равновесное по BVS решение.

Доказательство разобьем на два этапа. На этапе I докажем существование ситуации , , удовлетворяющей условию равновесности по Бержу-Вайсману в игре (то есть равенствам (17)) при каждой стратеги центра . На этапе II покажем, что для любого постоянного числа существует своя стратегия центра , при которой имеет место неравенство (18). Тогда, согласно приведенному выше определению, пара и будет -равновесным по BVS решением игры .

Этап I. Рассмотрим многозначное отображение , определяемое множеством ситуаций бескоалиционной игры

,

при каждом удовлетворяющих условию равновесности по Бержу-Вайсману:

Множество ,

во-первых, не пусто при каждом (согласно утверждению 2 и требованию (2⁰) теоремы),

во-вторых, при каждом является компактным подмножеством множества ситуаций (согласно утверждению 1 и требованию (1⁰) теоремы),

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

Учитывая, кроме этих трех фактов, компактность и непрерывность , по теореме об измеримом выборе [6, с. 26] получаем, что существует измеримый по Борелю селектор (измеримая по Борелю вектор-функция ), который при каждой стратегии центра и каждом , реализует равенство (17) и поэтому удовлетворяет требованию (а) приведенного выше определения.

Этап II. Функция выигрыша центра ограничена сверху, как непрерывная функция, определенная на компакте . С помощью найденной на этапе I измеримой по Борелю вектор-функции построим суперпозицию . Скалярная функция ,

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

во-вторых, функция измерима по Борелю (как суперпозиция непрерывной и измеримой функции).

Пусть теперь - произвольное положительное число. Тогда для каждого можно указать такую «свою» стратегию центра , что для всех имеет место неравенство

,

игра неравенство бескоалиционный штакельберг

то есть выполнено неравенство (18) из определения -равновесной по BVS ситуации (в игре ). Следовательно, в результате этапов I и II показано, что в игре существует пара , удовлетворяющая требованиям (а) и (б) приведенного определения равновесной по BVS ситуации. Теорема доказана.

Заключение

Для двухуровневой иерархической игры с бескоалиционным вариантом на нижнем уровне формализовано понятие -равновесного по BVS решения и установлены достаточные условия существования указанного решения.

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

1. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.

2. Федоров В.В. Численные методы максимина. М.: Наука, 1979.

3. Von Stackelberg H. Marktform and Gleichgewicht. Vienna: Springer, 1934 (Англ. перев.: The theory of the market economy. Oxford: Oxford University Press, 1952).

4. Nash J.F. Non-cooperative games // Ann. Math. 1951, №54.

5. Жуковский В.И., Смирнова Л.В. Двухуровневая игра с бескоалиционным вариантом на нижнем уровне иерархии // Spectral and Evolution Problems, Ukraine, 2008, Vol. 18.

Размещено на Allbest.ru

...