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




НазваниеХарактеристическая функция игры в нормальной форме
Дата публикации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Решение Построим сначала график функции при неотрицательных значениях...
Надеюсь, вы внимательно изучили пункт 23 и понимаете, чем отличается функция вида от функции. Теперь разберем еще пару примеров,...
Характеристическая функция игры в нормальной форме iconИгра «Экологический калейдоскоп»
Игра проводится в форме отдельных тематических конкурсов, Победитель определяется по сумме баллов, которые участники получают в ходе...
Характеристическая функция игры в нормальной форме iconКонспект учебного занятия в форме игры состязания по теме «Текстовый...
В данной методической разработке представлен конспект учебного занятия в форме игры – состязания по теме «Текстовый редактор и электронные...
Характеристическая функция игры в нормальной форме iconИгра «В царстве Берендея» Выполнено
Это методическая разработка экологического внеклассного мероприятия в форме командной игры. Продолжительность примерно 50 минут,...
Характеристическая функция игры в нормальной форме iconЦель игры: в яркой и увлекательной форме расширить и углубить знания,...
Цель игры: в яркой и увлекательной форме расширить и углубить знания, полученные учащимися на уроках по Электростатике и Электричеству....
Характеристическая функция игры в нормальной форме iconИсследование устойчивости нелинейных систем. Определение устойчивости,функции ляпунова
Общее определение понятия устойчивости любой динамической системы по Ляпунову выглядит следующим образом. Запишем уравнения динамики...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


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