- •Основные понятия теории игр
- •Классификация игр
- •Описание игры в развернутой форме
- •Бескоалиционные игры
- •Приемлемые ситуации и ситуации равновесия в игре
- •Стратегическая эквивалентность игр
- •Антагонистические игры. Общие сведения
- •Чистые и смешанные стратегии
- •Верхняя и нижняя цены игры при использовании смешанных стратегий
- •Основная теорема антагонистических игр.
- •Верхние и нижние цены в s-игре
- •Разделительная и опорная гиперплоскость двух выпуклых множеств
- •Теорема о минимаксе
- •Геометрическая интерпретация минимакса
- •Решение антагонистических игр. Доминирующие и полезные стратегии
- •Игры с частными случаями платежных матриц
- •Решение матричных игр
- •Линейное программирование для решения матричных игр
- •Графическое решение игр 2*n и m*2
- •Бесконечные антагонистические игры
- •Строго выпуклые игры на единичном квадрате
- •Неантагонистические игры
- •Бескоалиционные игры
- •Охрана воздушного бассейна от загрязнений атмосферы
- •Принципы оптимальности в бескоалиционных играх
- •Принцип оптимальности по Парето
- •Смешанное расширение бескоалиционной игры
- •Коалиционные и кооперативные игры
- •Характеристическая функция коалиционной игры
- •Свойства характеристической функции
- •Дележи в кооперативной игре
- •Стратегическая эквивалентность кооперативных игр
- •Общие сведения об играх с природой или теория статистических решений.
- •Пространство стратегий природы
- •Пространство стратегий статистика и функция выигрыша
- •Критерии выбора решений при неопределённости
- •Статистические игры без эксперимента. Представление игры с природой в виде s-игры
- •Допустимые стратегии в статистических играх
- •Геометрическая интерпретация выбора байесовской стратегии
- •Статистические игры с проведением единичного эксперимента Общие сведения
- •Пространство выборок
- •Функции риска
- •Принцип выбора стратегий в играх с единичным экспериментом.
- •Байесовский принцип.
- •Число чистых стратегий статистика в игре с единичным экспериментом.
- •Апостериорные распределения вероятности.
- •Определение байесовских решений с использованием апостериорных вероятностей
- •Двуальтернативная задача
- •Анализ целесообразности проведения экспериментов
- •Использование апостериорной вероятности для определения последовательных байесовских правил
- •Правило последовательных выборок
- •Функция риска при оптимальном последовательном правиле
Стратегическая эквивалентность кооперативных игр
Игра I, V стратегически эквивалентна игре I, V’ , (V~V’), если k>0, c , i I: V’(K) = kV(K) + , k I.
Стратегическая эквивалентность обладает следующими свойствами:
Рефлексивность (V~V);
Симметрия (V~V’ V’~V);
Транзитивность (V~V’, V’~V’’ V~V’’).
Т. о. стратегическая эквивалентность является отношением, которое разбивает множество кооперативных игр на непересекающиеся классы, т. к. если V~V’, то дележу x = (x , x ,…,x ) соответствует делёж x’ = (x’ , x’ ,…,x’ ), где x’ = kx + c , i = .
Если V(K) = 0, k I, то игра I, V называется нулевой. Любая несущественная коалиционная игра эквивалентна нулевой игре.
В 0,1-редуцированной форме дележом может быть любой вектор x = (x , x ,…,x ), компоненты которого удовлетворяют условиям: а) x 0;
б) = 1.
Каждой характеристической функции V(k) можно сопоставить множество дележей, удовлетворяющих условиям:
x V(i);
x(I) = V(I);
x 0, = 1.
При решении корпоративной игры необходимо найти единственно справедливый делёж. Для решения используется несколько предположений:
Введём отношение предпочтения дележей x >x (при коалиции k)
x x , i I x (I) = V(I)
Если для коалиции, то x (k) V(k), k I. Это условие практической реализуемости дележа.
Отношение дележей возможно не по всем коалициям.
k = 1 — коалиция из одного игрока
x y , x V(i) — это условие противоречит условию индивидуальной рациональности.
k = I — коалиция из всех игроков
x(I) > y(I) = V(I)
Таким образом, отношение доминирования можно изучать для классов стратегической эквивалентности. Причём, в качестве таких классов можно рассматривать либо несущественные игры, либо игры в 0,1-редуцированной форме. Отношение предпочтения и другие свойства позволяют определить некоторое множество дележей. Теория кооперативных игр занимается изучением множества дележей, удовлетворяющим рассмотренным свойствам.
Доминирование дележей невозможно по следующим коалициям:
из одного игрока, т. к. если y < x V(i), противоречит условию индивидуальной рациональности.
из всех игроков, т. к. > = V(I) противоречит условию коллективной рациональности.
Пусть есть две стратегически эквивалентных игры V~V’ и некоторые два дележа и , которые будут доминировать, соответственно, дележам: > , >
Можно показать, что если выполняется первое неравенство, то будет выполняться и второе по этой коалиции отношения доминирования могут исследоваться на примере наиболее простых игр каждого класса.
Для несущественных игр отношение доминирования можно рассматривать на примере нулевой игры, а для существенных на примере 0,1-редуцированной игры.
Рассмотрим доминирование дележей существенной игры трёх лиц:
x = (x , x , x ) – вектор дележей, x V(i), x + x + x = 1
Этот барицентрический треугольник называется двумерным симплексом.
Например, в симплексе зафиксировано x = x (прямая, параллельная АВ, будет иметь положение в зависимости от V ).
Подмножество С множества допустимых значений, где выполняются условия:
нет доминируемых дележей по любой коалиции из I;
для любой коалиции k I выполняются условие x(k) V(k), k I, называют С-ядром кооперативной игры с характеристической функцией V(k).
Компоненты С-ядра должны удовлетворять некоторой конечной системе линейных неравенств.
Рассмотрим методику составления неравенств на примере игры трёх лиц.
Эти неравенства: V(1,2) x +x
V(1,3) x +x
V(2,3) x +x
К этим неравенствам добавляются ещё два неравенства индивидуальной групповой рациональности x V(1), x V(2), x V(3), x + x + x = 1
При приведении этой игры к 0,1-редуцированной форме, получаем:
V(1) = V(2) = V(3) = 0
x 0, I = 1,2,3
x + x c
x + x c
x + x c , c 0
Условие нахождения С-ядра рассмотрим на следующем примере:
Пусть есть три предприятия П , П , П .
П – Д , Д по 900 шт.
П – Д , Д по 700 шт.
П – М , М по 1000 шт.
Поступил заказ поставить комплект товаров (Д , М ) по 1000 шт. Каким образом скомплектовать этот заказ?
Другими словами, как распределить величину Д относительно П и П ?
Данный конфликт можно моделировать кооперативной игрой трёх лиц, где участники могут заключать между собой соглашения и компенсировать друг другу их значимость.
Будем считать характеристическую функцию в единицах товаров.
V(П ) = V(П ) = V(П ) = V(П , П )
V(П , П ) = 1800
V(П , П ) = 1400
V(П , П , П ) = 2000
Перейдём к 0,1-редуцированной форме, тогда V(П ) = V(П ) = V(П )=0 V(П , П ) = 0
V(П , П ) = 0,9
V(П , П ) = 0,7
V(П , П , П ) = 1
Для дележей получим следующие неравенства:
. Это условие определяет С-ядро этой игры.
П оследнее неравенство определяет двумерный симплекс. Рассмотрим прямую x + x = 0,9. Это эквивалентно множеству точек, когда x = 0,1; x + x = 0,7; x = 0,3
— множество дележей, образует С-ядро этой игры. Любой делёж из этого ядра является наилучшим.
Например, x = 600 ед.
x = 200 ед.
x = 1200 ед.
Превышение x над x и x за счёт монополии; П и П придется доплачивать П , т. к. они не могут самостоятельно выполнить заказ.
Д = ,
М = 1000 ед.
П доплатит 150 ед., а П – 50 ед.
Более общим подходом к решению кооперативных игр является решение по Нейману-Моргенштерну. Н-М решения, как и с-ядро, определяют множество эквивалентных между собой решений.
Кроме С-ядра и Н-М решения для определения предпочтительного дележа используют вектор Шепли.