Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Редуцированная форма кооперативной игры. Свойства характеристической функции, дележа кооперативной игры, представленной в такой форме.
Опред. Кооперат. игра с характеристической функцией u имеет (0,1)-редуцированную форму, если выполняются соотнош.: u(i) = 0 (i Î N), u(N) = 1. Теорема. Каждая существенная кооперат. игра стратег. эквивалентна одной и только одной игре в (0,1)-редуцированной форме. Сформулированная теорема показывает, что мы можем выбрать игру в (0,1)-редуцированной форме для представления любого класса эквивалентности игр. Удобство этого выбора состоит в том, что в такой форме значение u(K) непосредственно демонстрирует нам силу коалиции S (т.е. ту дополнительную прибыль, которую получают члены коалиции, образовав еѐ, а все дележи являются вероятностными векторами. В игре в (0,1)-редуцированной форме дележѐм является любой вектор x = (x1,..., xn), для которого xi ³ 0 (i Î N) xi iÎN å = 1. Свойства характеристической функции в 0,1-редуцированной коалиционной игре: 1. Всякая характеристическая функция является неотрицательной и неубывающей функцией. 2. Если K L, то v(K) + v(L/K) v(L) 3. Всякая характеристическая функция в игре из n игроков, I={1,2,…,n}, описывается 2n-1 числом параметров, а при приведении игры в 0,1-редуцированную форму накладывается n+1 дополнительных связей, и, следовательно, получается (2n - n - 2) свободных параметров. 16. Определение кооперативной игры (в форме характеристической функции). Основные свойства характеристической функции (супераддитивность, выпуклость). Игры существенные и несущественные. Игра называется кооперативной, если до начала игры игроки образуют коалиции и принимают взаимообязывающие соглашения о своих стратегиях. Предположим, что имеется множество игроков K – Некоторое подмножество , состоящее из игроков. - число возможных коалиций игроков, договаривающихся о совместных действиях. Определение 1. Функция V, ставящая в соответствии каждой коалиции K наибольший выигрыш, называется характеристической функцией игры. Определение 2. Характеристическая функция V(K) называется простой, если она принимает два значения: 0 и 1. Определение 3. Если характеристическая функция V простая, то коалиции K, для которых V(K) = 1 называются выигрывающими, а для которых V(K) = 0 – проигрывающими. Свойства характеристической функции. 1) персональность (коалиция, не содержащая ни одного игрока, ничего не выигрывает).
2) супераддитивность 3) дополнительность Обозначим через Xi выигрыш i-го игрока. И рассмотрим следующие два условия: индивидуальная рациональность коллективная рациональность Определение 4. Вектор выигрышей X = (X1, ¼, Xn), удовлетворяющий условиям 1 и 2, называется дележом в условиях характеристической функции V. Определение 5. Множество {N, V}, удовлетворяющее условиям 1 и 2, называется классической кооперативной игрой. Теорема 1. Для того чтобы X = (X1, ¼, Xn) был дележом в классической кооперативной игре, необходимо и достаточно, чтобы Определение 6. Кооперативные игры называются существенными, если для любых коалиций K и L выполняется неравенство: Если выполняется неравенство , то такая игра называется несущественной. Рассмотрим следующие свойства: для того, чтобы характеристическая функция V была аддитивной (кооперативная игра несущественной), необходимо и достаточно выполнения следующего равенства: в несущественной игре имеется только один дележ: в существенной игре более, чем одному игроку множество дележей бесконечно:
17. Определение и основные свойства дележа в кооперативной игре. Понятие доминирования дележей. Вектор называется дележом в игре <N,v>, если выполняются условия (коллективная рациональность); xi≥v(i) для всех iÎN (индивидуальная рациональность). В дальнейшем для краткости будем использовать следующее обозначение. Если x – дележ, а K – коалиция, то . В частности, x({i})=xi, x(N)=v(N). Лемма. Множество дележей не пусто. Доказательство. Определим вектор условиями x1=v(1),…,xn–1= v(n–1), . В силу свойства супераддитивности выполняется неравенство xn≥v(n), значит, этот вектор является дележом. Лемма. В несущественной игре дележ единственный. Доказательство. Если – дележ, то для всех iÎN выполняются неравенства xi≥v(i). Суммируя их, получим (последнее равенство выполняется в силу несущественности игры). Значит, на самом деле все сложенные неравенства на самом деле являются равенствами, то есть единственный дележ – вектор (v(1),…,v(n)). Дележ x доминирует дележ y по коалиции K, если выполняются условия
x(K)£v(K); xi>yi для всех iÎN. Если x доминирует дележ y по коалиции K, то будем писать .Лемма. Отношение доминирования по коалиции K обладает свойствами строгого порядкаДля любого дележа x не верно, что x y (антисимметричность); Для любых дележей x,y,z из условий x y и y z следует отношение x z (транзитивность). Доказательство. Лемма немедленно следует из того, что указанными свойствами обладает отношение «больше». Лемма. Отношение x y не выполняется ни для каких дележей x и y. Доказательство. Если x y, то xi>yi для любого iÎN. Суммируя эти равенства, получим (равенства выполняются в силу определения дележа). Получено противоречие. Лемма. Отношение x y не выполняется ни для какого игрока i и ни для каких дележей x и y. Доказательство. Если x y, то v(i)≥xi>yi≥v(i) (первые два неравенства выполняются в силу определения доминирования, а последнее – так как y – дележ). Получено противоречие. Лемма. Если x y, то x lx+(1–l)y для любого lÎ[0,1]. Дележ x доминирует дележ y, если найдется такая коалиция K, что x y. Если дележ x доминирует дележ y, то будем писать x y. Лемма. Если в некоторой игре найдутся дележи x и y такие, что x y и y x, то число игроков в этой игре не меньше пяти. Доказательство. Если и , то коалиции K и L не пересекаются, так как если , то xi>yi>xi, что не возможно. В силу доказанного выше, каждая из этих двух коалиций содержит не менее двух игроков. Не ограничивая общности, можно считать, что K={1,2}, L={3,4}. Так как , то x1+x2£v({1,2}). Так как , то x3+x4<y3+y4£v({3,4}). Отсюда x1+x2 x3+x4<v({1,2})+v({3,4})£v(N). Если игроков кроме 1,2,3 и 4 нет, это противоречит определению дележа.
|
||||||
Последнее изменение этой страницы: 2016-08-06; просмотров: 834; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.14.70.203 (0.007 с.) |