77403-1 (612449), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

(1) = (2) = (3) = (4) = 0

(1,2,3,4) = 1.

Исходя из свойства дополнительности, получаем

(1,2,3) = (1,2,3,4) (4) = 1 0 =1;

(1,2,4) = (1,2,3,4) (3) = 1 0 =1;

(1,3,4) = (1,2,3,4) (2) = 1 0 =1;

(2,3,4) = (1,2,3,4) (1) = 1 0 =1.

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

(1,2), (1,3), (1,4), (2,3), (2,4), (3,4).

Характеристическая функция на этих коалициях согласно свойству дополнительности удовлетворяет только следующим соотношениям :

(1,4) = 1 (2,3),

(1,3) = 1 (2,4),

(1,2) = 1 (3,4).

Так как значений неизвестных шесть, а соотношений только три, то значения из шести могут быть выбрана произвольно. Обозначим эти произвольные значения через x₁, x₂, x₃, т.е.

(1,4) = x₁ , (2,4) = x₂ , (3,4) = x₃ ,

Тогда

(2,3) = 1 x₁ , (1,3) = 1 x₂ , (1,2) = 1 x₃ .

Кроме того должно быть

0 x₁, x₂, x₃ 1 ,

так как значение характеристической функции на коалиции из двух игроков не может быть меньше, чем значение характеристической функции для одного из этих игроков (равное нулю для одного игрока), и не может быть больше, чем значение характеристической функции для коалиции из трёх игроков (равное 1 для трех игроков). Геометрически (x₁, x₂, x₃) можно изобразить как точку единичного куба, т.е. каждому классу стратегической эквивалентности игр четырёх игроков будет соответствовать точка единичного куба.

Итак, множество классов стратегической эквивалентности существенных игр четырёх игроков бесконечно и зависит от трёх произвольных параметров.

4. Игры, состоящие из более чем 4-х игроков, имеют большее разнообразие классов стратегической эквивалентности существенных игр.

Так, размерность множества классов игр n игроков равна , т.е. имеется произвольных параметров.

Рассмотрим теперь кооперативные игры без условия постоянства суммы.

1. Для игр 2-х игроков множество N={1,2}, условия редуцированности дают

() = (1) = (2) = (1,2) = 1.

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

2. Для игр 3-х игроков множество N={1,2,3}, условия редуцированности дают

() = (1) = (2) = (3) = 0; (1,2,3) = 1.

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

(1,2) = C₃, (1,3) = C₂, (2,3) = C₁,

но удовлетворяющие условию

0 C₁, C₂, C₃ 1.

Таким образом, классы стратегической эквивалентности общих кооперативных игр трёх игроков могут быть поставлены в соответствие точкам трёхмерного единичного куба подобно тому, как это получилось для игр 4-х игроков с нулевой суммой.

Для игр более 3-х игроков с ненулевой суммой рассмотрения аналогичны.

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

Определение. Пусть имеется два дележа x = (x₁, ..., x_n) и y = (y₁, ..., y_n) в кооперативной игре G = {N,}, и K N некоторая коалиция. Тогда делёж x доминирует y по коалиции K, если

1) (K) (свойство эффективности доминирующего платежа)

2) x_i > y_i для всех iK (свойство предпочтительности)

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

Условие предпочтительности отражает необходимость единодушия в предпочтении со стороны коалиции: если хотя бы одно из неравенств x_i > y_i будет нарушено, т.е. если хотя бы для одного из членов коалиции K выигрыш в условиях дележа y будет не меньшим, чем в условиях дележа x, то можно будет говорить о предпочтении дележа x дележу y не всей коалицией K, а только теми её членами, для которых соответствующее неравенство x_i > y_i соблюдается.

Соотношение доминирования x над y по коалиции K обозначается через

.

Определение. Делёж x доминирует y, если существует такая коалиция K, для которой делёж x доминирует y. Это доминирование обозначается так:

x > y.

Наличие доминирования x > y означает, что в множестве игроков N найдётся коалиция, для которой x предпочтительнее y. Отношение доминирования не обладает полностью свойствами рефлексивности, симметрии, транзитивности, возможна только частичная симметрия и транзитивность. Соотношение доминирования возможно не по всякой коалиции. Так, невозможно доминирование по коалиции, состоящей из одного игрока или из всех игроков.

Справедлива следующая теорема.

Теорема. Если и ¹ две стратегически эквивалентные характеристические функции, причём дележам x и y соответствуют дележи и , то из x > y следует > .

Очевидно, все явления, описываемые в терминах доминирования дележей, относятся к классам стратегической эквивалентности, поэтому достаточно изучать эти классы (а не сами игры) для существенных игр по их (0,1)-редуцированной форме, а для несущественных игр по нулевым играм.

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

Рассмотрим доминирование дележей в существенной игре на следующем примере.

Пример. Пусть имеется (0,1)-редуцированная форма существенной игры трёх игроков с постоянной суммой (равной 1). Поскольку доминирование невозможно ни по одной из одноэлементных коалиций 1,2,3, а также по коалиции, состоящей из всех трёх игроков, то доминирование возможно только по одной из двухэлементных коалиций {1,2}, {1,3}, {2,3}.

Для наглядности доминирования дележей введём понятие бароцентрических координат. Осями координат служат три оси x₁, x₂, x₃, составляющие между собой одинаковые углы 60^о, ось x₃ находится на расстоянии единицы от точки пересечения осей x₁ и x₂ (рис.1), координаты точки x = (x₁, x₂, x₃) соответственно расстояния от этой точки до осей x₁, x₂, x₃, взятые с такими знаками, как указано на рис.1. (Например, для точки x на рис.1. x₁ < 0, x₂ > 0, x₃ > 0).

В барицентрической системе координат всегда выполняется равенство

x₁ + x₂ + x₃ = 1.

В плоскости всегда имеется точка с координатами x₁, x₂, x₃, удовлетворяющими равенству (6). По этому бароцентрическая система координат автоматически удовлетворяет одному из условий, определяющих исход игры трёх игроков. С другой стороны, поскольку игра в (0, 1)-редуцированной форме, то точка x должна находиться в заштрихованном треугольнике (см. рис. 2). Дележи x₁, x₂, x₃ должны удовлетворять неравенствам

x₁ + x₂ (1, 2), x₁ + x₃ (1, 3), x₂ + x₃ (2, 3).

Очевидно, из условия дополнительности, что

x₁ + x₂ = 1 x₃ 1 = (1, 2), x₁ + x₃ 1, x₂ + x₃ 1.

Делёж x = (x₁, x₂, x₃) доминирует дележ y = (y₁, y₂, y₃)

по коалиции {1, 2}, если x₁ > y₁, x₂ > y₂;

по коалиции {1, 3}, если x₁ > y₁, x₃ > y₃;

по коалиции {2, 3}, если x₂ > y₂, x₃ > y₃,

т.е. если делёж y находится в одном из заштрихованных параллелограммов (за исключением трёх граничных прямых, проходящих через точку x) на рис. 3, то делёж x доминирует делёж y, а всякая точка находящаяся в не заштрихованных треугольниках, является предпочтительнее исхода x.

x₃ = 1 x₂ = 1

x = (x₁, x₂, x₃)

x₃ = 1 C₃

x₁ = 0

x₁ = 1 C₁ x₂ = 1 C₂

Рис.3 Рис. 4

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

Пример. Пусть имеется (0, 1)-редуцированная игра трёх игроков с ненулевой суммой.

Рассмотрим сначала условия доминирования дележа x = (x₁, x₂, x₃) над дележём y = (y₁, y₂, y₃) по коалиции {1, 2}. В этом случае имеем :

Поскольку может быть, что C₃ < 1 , то первое из условий (7) нельзя отбросить, как это делает- ся в играх с постоянной суммой. Это значит что, x должна быть не ниже прямой

x₁ + x₂ = C₃.

Или, учитывая (6), последнее уравнение принимает вид

x₃ = 1 + C₃ .

Таким образом, если делёж x таков, что

x₁ 1 C₁, x₂ 1 C₂, x₃ 1 C₃,

то имеется три параллелограмма, заштрихованных на рис. 4, находясь в которых, точки x доминируют y.

Если в (8) одно из неравенств, например, третье не имеет места, то есть только 2 парал- лелограмма, заштрихованных на рис. 5, находясь в некоторых точках x доминирует y.

x₁ = 1 C₁ x₂ = 1 C₂ x₂ = 1 C₂ x₁ = 1 C₁

x₃ = 1 C₃

x

Рис. 5 Рис. 6

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

Теорема. Для того чтобы делёж x принадлежал с-ядру кооперативной игры с характеристической функцией , необходимо и достаточно, чтобы для любой коалиции K выполнялось неравенство

Характеристики

Список файлов курсовой работы