Характеристическая функция игры в нормальной форме




НазваниеХарактеристическая функция игры в нормальной форме
Дата публикации15.03.2014
Размер82 Kb.
ТипДокументы
shkolnie.ru > Математика > Документы

Кооперативные игры

Введение


  • НМ – не теория игр.

  • Империализм – высшая стадия капитализма.

  • Незнайка на луне.

  • Скучная математика.

  • Дилемма заключенного.

  • Нэш – некооперативный.

  • Сложные стратегии переговоров.

  • Агрегирование.

  • Репка

  • Монополизация рынка: два варианта и сравнение

  • Джаз-оркестр.: v(SPD)=1000, v(SP)=800, v(DP)=300,v(DS)=500, v(P)=300, v(S)=200, v(D)=0. S – певец, P – пианист, D(drummer) – ударник.

Характеристическая функция игры в нормальной форме


Обозначим стандартный симплекс в n-мерном евклидовом пространстве.

Рассмотрим произвольную игру n-лиц в нормальной форме Г=<N,U1,…,Un,g1,…,gn>. Определим новую игру , положив , . Игру называют игрой с побочными платежами, соответствующей исходной игре Г.

Откат

Трансферабельная полезность.

Семейный спор

Челси.

- и -ядро в играх с побочными платежами

Определение. Характеристической функцией игры в нормальной форме Г=<N,U1,…,Un,g1,…,gn> называется функция, которая каждой коалиции KN ставит в соответствие число .

Здесь и далее считаем по определению, что .

Определение. Функция f, ставящая в соответствие каждому подмножеству Y множества X число f(Y) называется супераддитивной, если для любых непересекающихся множеств Y и Z из X выполняется неравенство ..

  • Супераддитивность

  • Двойной Клико

  • пнсн f(x0)-e0)+e пнсв

Теорема. Характеристическая функция любой игры в нормальной форме супераддитивна.

Доказательство. Нужно доказать, что для любых коалиций I и K выполняются неравенства. Для упрощения формул, будем считать, что I={1,…,i} и K={i+1,…,i+k} (остальные случаи получаются из данного перестановкой игроков). Обозначим L=N\I\K – множество игроков, не входящих ни в I ни в K.

Пусть – такая стратегия коалиции I, что



и – такая стратегия коалиции K, что

.

Тогда



и

.

Складывая эти неравенства, получим

.

Но сумма минимумов меньше минимума суммы, поэтому

,

и тем более

.

Лемма доказана.
^

Игра в форме характеристической функции


Определение. Игрой в форме характеристической функции называется пара <N,v>, где N={1,…,n} – конечное множество, называемое множеством игроков, а функция, определенная на семействе всех подмножеств множества N и удовлетворяющая следующим двум условиям:

  1. v()=0 (персональность);

  2. функция v супераддитивна.

  • Две конфетки (Роман).

  • Единица – вздор, единица – ноль (Маяковский)

  • Смешанные стратегии.
^

Теорема о реализуемости


Теорема. Для всякой игры в форме характеристической функции <N,v> найдется такая игра в нормальной форме Г=<N,U1,…,Un,g1,…,gn>, что функция v будет характеристической функцией игры Г.

Доказательство. Построим явно соответствующую игру Г. Положим Ui=2N для всех i. Выигрыш i-го игрока в заданной ситуации u определим следующим образом. Назовем коалицию K замкнутой, если uj=K для всех игроков jK. Если игрок i входит в некоторую замкнутую коалицию K, содержащую k игроков, то положим его выигрыш . Если же игрок i не входит ни в какую замкнутую коалицию, то по определению gi(u)=v(i).

Барышня.

Заметим, что по определению различные замкнутые коалиции не пересекаются, поэтому данное определение корректно.

Найдем характеристическую функцию построенной игры в нормальной форме. Фиксируем произвольную коалицию ^ K и обозначим число входящих в нее игроков буквой k.

Если все игроки из коалиции K выберут стратегии , то не зависимо от выбора стратегий остальных игроков каждый из них получит выигрыш и, следовательно

.

Значит,

.

Пусть теперь все игроки, не входящие в ^ K выбрали стратегию . Тогда коалиция K будет замкнутой. В ситуации могут образоваться еще какие-то замкнутые коалиции I1,…,Ip, содержащиеся в K, и игроки из множества не войдут ни в одну из замкнутых коалиций. Обозначим число игроков в коалиции Iq через mq. Тогда



(неравенство выполняется в силу супераддитивности функции v).

Тем более

.

А поскольку это неравенство выполняется для любой стратегии uK, получим

.

Окончательно имеем

,

что в силу произвольности коалиции K означает, что функция v является характеристической функцией игры Г.
^

Аффинная эквивалентность.


Определение. Игры <N,v> и <N,v> называются аффинно эквивалентными, если найдутся положительное число k и произвольные действительные числа ai такие, что для любой коалиции i выполняется равенство .

Удав.

^ Лемма. Отношение аффинной эквивалентности является отношением эквивалентности.

Определение. Игрок iN называется болваном в игре <N,v>, если для любой коалиции I, не содержащей игрока i выполняется равенство . Игроки, не являющиеся болванами, называются существенными.

Здесь и далее для сокращения формул мы пишем v(i) вместо v({i}).

Обрубок бревна – идол - карточный болван - болван.

Определение. Множество, содержащее всех существенных игроков и, может быть, каких-то болванов называется носителем игры <N,v>.

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

Лемма. Всякая несущественная игра эквивалентна игре <N,v>, в которой v(I)=0 для любой коалиции I.

Доказательство. В силу несущественности рассматриваемой игры для любой коалиции K выполняется равенство . Поэтому в определении аффинной эквивалентности достаточно взять k=1 и ai=–v(i).

Определение. Игра <N,v> называется 0-1-редуцированной, если для любого игрока i верно равенство v(i)=0 и v(N)=1.

Лемма. Всякая существенная игра аффинно эквивалентна некоторой 0-1-редуцированной игре.

Доказательство. Искомые числа k и a1,…,an должны удовлетворять системе уравнений

kv(i)+ai=0, i=1,…,n,

.

Суммируя первые n уравнений этой системы, получим . Подставляя это равенство в последнее уравнение системы, получим .

В силу существенности игры число , положительно, поэтому положительно и число . Теперь легко находим .

^ Лемма. Характеристическая функция 0-1-редуцированной игры неотрицательна.

Лемма. Если <N,v> – 0-1-редуцированная игра, и две коалиции I и K удовлетворяют условию IK, то v(I)v(K).

Доказательства двух последних лемм немедленно следуют из свойства супераддитивности.

Перечень всех игр двух лиц

Перечень всех игр трех лиц.

Все принципы оптимальности ниже – ковариантны.
^

Линейная структура.


Выпуклый конус.

0-1-редуцироаннные игры образуют выпуклое подмножество этого конуса.

Определение. Игра <N,v> называется простой, если множество значений функции v есть {0,1}.

Определение. Игра <N,vR> называется простейшей, если существует коалиция RN такая, что vR(I)=1 тогда и только тогда, когда RI.

Лемма. Множество характеристических функций образует линейное пространство, размерность которого не превосходит 2n–1.

^ Лемма. Множество простейших игр образует базис в пространстве всех игр форме характеристической функции.

Доказательство. С учетом предыдущей леммы достаточно доказать, что простейшие характеристические функции линейно независимы. Допустим, что



и докажем, что все коэффициенты R равны нулю. Доказательство будем вести индукцией по числу игроков в коалиции.

Покажем сначала, что N=0. Из предыдущего равенства следует, в частности, что

.

По определению простейшей функции для всех RN выполняется равенство vR(N)=0, а vN(N)=1. Откуда немедленно получаем N=0.

Пусть утверждение уде доказано для всех коалиций, содержащих более k игроков, и докажем его для произвольной коалиции K, содержащей ровно k игроков. В силу сделанного предположения выполняется равенство

.

По предположению индукции, для всех коалиций I, содержащих K, выполняется равенство I=0. А для всех коалиций I, не содержащих K, выполняется равенство vI(K)=0 (по определению простейшей функции). Следовательно, последнее равенство эквивалентно условию KvK(K)=0. С учетом равенства vK(K)=1, получаем требуемое.

Лемма доказана.

Обозначим #K число элементов множества K.

Лемма. Если , где vR­ – простейшие функции, то

.

Доказательство. Так как простейшие функции образуют базис, достаточно проверить равенство

.

Фиксируем произвольную коалицию ^ I и докажем, что

.

Число vR(I) отлично от нуля только для RI, а для таких R vR(I)=1. Поэтому данное равенство перепишется в виде

.

Поменяем порядок суммирования

.

Сгруппируем слагаемые, соответствующие коалициям содержащим одинаковое количество элементов



и вынесем множитель v(K) за скобку

.

Сумма , поскольку выбрать r-элементное множество, содержащее #K-элементное множество K и содержащееся в #I-элементном множестве I, это все равно, что из множества I\K, имеющего #I–#K элементов, выбрать недостающие
r–#K элементов.

Вычислим сумму . При K=I сумма содержит одно слагаемое, равное 1. В остальных случаях, воспользовавшись формулой бинома Ньютона, получим . Таким образом, в сумме



ненулевой коэффициент имеет только один член v(I), причем этот коэффициент равен 1. Необходимое равенство доказано.

Формула включений-исключений.

Пример.. Та же формула для игры трех лиц.

v(K)=v(1)v1(K)+v(2)v2(K)+v(3)v3(K)+(v(12)-v(1)–v(2))v12(K)+
+(v(13)-v(1)–v(3))v13(K)+(v(23)-v(2)–v(3))v23(K)+
(v(123)–v(12)–v(13)–v(23)+v(1)+v(2)+v(3))v123(K)

Примеры


  • Олигополия Курно

  • Производитель и посредники

  • Распределение затрат на объект (стр. 130).

  • Распределение затрат с независимым спросом (Стр. 134). Доходы 41, 24, 22, 12. Расходы: на одного 40, на двух 60, на трех 70, на четырех 80. Супераддитивность расходов. .

  • Экономика производства Кукурузы (стр. 178). Для супераддитивности достаточно неорицательности и неубываения функции f.

  • Взносы пользователей (стр. 159). Строительство взлетной полосы. .

  • Ценообразование в многопродуктовой монополии (стр. 143)

Задачи


  1. Установите взаимнооднозначное соответствие между множеством ситуаций равновесия по Нэшу в игре Г и множеством ситуаций равновесия по Нэшу в соответствующей ей игре с побочными платежами .

  2. Всегда ли множество выигрышей в игре с побочными платежами является выпуклым?

  3. Докажите, что игра <N,v> несущественна тогда и только тогда, когда .

Литература


  1. Фон Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.

  2. Воробьев Н.Н. Теория игр для экономистов–кибернетиков. М.: Наука, 1985.

  3. Кукушкин Н.С., Морозов В.В. Теория неантагонистических игр. М.: МГУ. 1984.

  4. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. М.: Высшая школа. 1998.

  5. Оуэн Г. Теория игр. М.: Мир. 1971.



115367.doc 14.03.14

Похожие:

Характеристическая функция игры в нормальной форме iconЛабораторная работа 11. Приведение формул логики предикатов к сколемовской...
Цель работы: Изучить приведение формул логики предикатов к сколемовской нормальной форме
Характеристическая функция игры в нормальной форме icon4. Какие вхождения переменных являются свободными, а какие связанными...
Привести к предваренной нормальной форме, считая, что а и в — безкванторные формулы
Характеристическая функция игры в нормальной форме iconИгра в нормальной форме Определение
Унтер-офицерша налгала вам, будто бы я ее высек; она врет, ей-Богу врет. Она сама себя высекла
Характеристическая функция игры в нормальной форме iconИгра в нормальной форме Определение
Унтер-офицерша налгала вам, будто бы я ее высек; она врет, ей-Богу врет. Она сама себя высекла
Характеристическая функция игры в нормальной форме iconПоддержкой заместителя директора по учебно-воспитательной работе...
«По страницам истории». Мы воспользовались идеями Совета студентов и поддержкой заместителя директора по учебно-воспитательной работе...
Характеристическая функция игры в нормальной форме iconРешение Построим сначала график функции при неотрицательных значениях...
Надеюсь, вы внимательно изучили пункт 23 и понимаете, чем отличается функция вида от функции. Теперь разберем еще пару примеров,...
Характеристическая функция игры в нормальной форме iconИгра «Экологический калейдоскоп»
Игра проводится в форме отдельных тематических конкурсов, Победитель определяется по сумме баллов, которые участники получают в ходе...
Характеристическая функция игры в нормальной форме iconКонспект учебного занятия в форме игры состязания по теме «Текстовый...
В данной методической разработке представлен конспект учебного занятия в форме игры – состязания по теме «Текстовый редактор и электронные...
Характеристическая функция игры в нормальной форме iconИгра «В царстве Берендея» Выполнено
Это методическая разработка экологического внеклассного мероприятия в форме командной игры. Продолжительность примерно 50 минут,...
Характеристическая функция игры в нормальной форме iconЦель игры: в яркой и увлекательной форме расширить и углубить знания,...
Цель игры: в яркой и увлекательной форме расширить и углубить знания, полученные учащимися на уроках по Электростатике и Электричеству....
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
shkolnie.ru
Главная страница