Решение Предварительное обсуждение

Скачать 75.78 Kb.

Название	Решение Предварительное обсуждение
Дата публикации	03.07.2013
Размер	75.78 Kb.
Тип	Решение

09.10.07

Решение

Предварительное обсуждение

Сильно агрегированная модель
Смешанные стратегии
Трансферабельная полезность
Доминирование по фон Нейману и по Парето
Супераддитивность: связь с теорией меры (турпоход)
Пример: монополизация рынка.
Игра трех лиц с нулевой суммой
Гарантированный результат
Симметричное решение
Внутренняя и внешняя устойчивость

Определение

Определение. Решением игры <N,v> называется всякое множество дележей R, удовлетворяющее следующим двум условиям:

никакие два дележа из R не доминируют друг друга (внутренняя устойчивость);
для любого дележа x, не принадлежащего R, найдется дележ y, принадлежащий R и доминирующий x (внешняя устойчивость).

Выбор решения – установка в обществе, а выбор дележа в решении зависит от качеств личности.
Купцы – староверы.
Бардак времен перестройки – пока не выбрано решение.
Устойчивость всего решения а не отдельного дележа из него

Связь с многокритериальными задачами

Два определения максимума в обычной задаче оптимизации.
Ядро для бинарного отношения.
Максимальное множество элементов не доминирующих друг друга.
Минимальное множество элементов доминирующих всех остальных
Решение
Агрегирование отношений: объединение и пересечение.

Основные свойства

Теорема. Ядро содержится в любом решении.

Доказательство. Всякий дележ из C-ядра не доминируем никаким другим дележом, в частности, никаким дележом из решения. Значит, он принадлежит решению.

Теорема. Если в игре существует решение, состоящее из одного дележа, то игра не существенная.

Доказательство. Предположим противное. Тогда, не ограничивая общности, можно считать, что игра является 0-1-редуцированной.

Пусть дележ x принадлежит решению и его компонента xⁱ положительна. Рассмотрим дележ y, определенный условиями

Дележ x не может доминировать дележ y ни по какой коалиции, содержащей игрока ji, поскольку y^j>x^j. Но и по коалиции, состоящей из одного игрока i доминирование невозможно. Получено противоречие.

Пусть  – перестановка множества N={1,…,n}. Определим отображение

условием

.

Теорема. Пусть для некоторой перестановки  функция v удовлетворяет условию v((K))=v(K) для любой коалиции K. Тогда если R – решение игры <N,v>, то (R) – тоже ее решение.

Теорема. Всякое решение является замкнутым множеством.

В играх 3 и 4 лиц решения существуют
В игре 10 лиц решения может не быть (Lucas W.F., 1968).

Решение в игре трех лиц

Ex. Решения в играх трех лиц с постоянной суммой.

Дискриминирующие
Игра: олигархи – бюрократы – народ
Такой эффект не был заложен изначально
Пример: сильное решение (Льюс и Райфа стр. 277). Рассмотрим решение состоящее из дележей (x¹,x2,1/4). Ему принадлежит дележ (7/12,2/12,1/4).Его доминирует дележ (0,1/2,1/2) не из решения. Он в свою очередь доминируется дележом (2/12,7/12,1/4) из решения. При этом второй игрок в результате отклонения все-таки выигрывает.
симметричное

Ex. Решения в общих играх трех лиц.

Неформальное обсуждение

Воробьев.а) нет решение; б)Много решений; в)в одном решении много дележей; г)решение может быть несимметричным в симметричной игре.

Решение в простых играх

Рынок с одним товаром

Рассмотрим следующую модель рынка. Пусть множество игроков N разбито на два непустых подмножества: множество продавцов S и множество покупателей P, а функция v определяется условиями

.

Теорема. Рассмотрим систему функций f¹,…,fⁿ, определенных на отрезке [0,1] и удовлетворяющую следующим условиям

fⁱ(t)≥0 для всех t[0,1];
функция fⁱ не убывает, если iS;
функция fⁱ не возрастает, если iP;
для всех x[0,1] выполняются равенства и .
для любых t[0,1], iS и kP выполняется неравенство fⁱ(t)+ f^k(t)1.

Тогда множество R={( f¹(t),…,fⁿ(t)): t[0,1]} является решением рассматриваемой игры.

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

Лемма. Всякий вектор x из R является дележом.

Доказательство. Так как пересечение множеств S и P пусто, то для любого игрока i выполняется условие v(i)=0. А значит xⁱ=fⁱ(t)≥0=v(i) в силу условия 1.. Кроме того, в силу условия 4 выполняется равенство

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

Лемма. Все функции fⁱ являются непрерывными.

Доказательство. Рассмотрим случай iS (случай iP полностью аналогичен). Фиксируем произвольное  и положим

. Для любого t[0,1] и любого q, удовлетворяющего условиям tq<t+ имеем

(оба неравенства выполняются в силу неубывания функций f^j). Аналогично, для любого q, удовлетворяющего условиям t–<q<t имеем

.

Необходимый результат следует теперь из определения непрерывности по Коши.

Лемма. Для iS выполняются равенства fⁱ(0)=0, а для iP – равенства fⁱ(0)=1.

Доказательство. По условию 4 имеем

. А поскольку в силу условия 1 все слагаемые неотрицательны, каждое из них должно быть равно нулю. Первое равенство доказано. Второе доказывается аналогично.

Лемма. Множество R удовлетворяет условию внешней устойчивости.

Доказательство. Рассмотрим произвольный дележ x не принадлежащий R. Пусть t₀ – наибольшее из чисел t, для которых неравенства f^s(t)x^s выполняются для всех sS, а t₁ – наименьшее из чисел t, для которых неравенства f^p(t)x^p выполняются для всех pP.

Тогда

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

,

или, с учетом условия 4,

.

Отсюда (t₀–t₁)v(N)0 и t₀t₁ (v(N)>0, так как множества S и P не пусты).

Предположим, что t₀=t₁. Тогда неравенства fⁱ(t₀)xⁱ выполняются для всех iN, а поскольку (f¹(t₀),…,fⁿ(t₀)) и x – дележи, суммы компонент этих двух векторов равны. Значит fⁱ(t₀)=xⁱ для всех iN и значит x содержится в R, что противоречит его выбору. Значит, на самом деле t₀<t₁.

Выберем число t_*, удовлетворяющее условиям t₀<t_*<t₁. Тогда найдутся игроки sS и pP, для которых f^s(t_*)>x^s и f^p(t_*)>x^p. Но согласно условию 5 выполняется неравенство f^s(t_*)+f^p(t_*)1=v({s,p}), значит дележ (f¹(t_*),…,fⁿ(t_*)) доминирует дележ x по коалиции {s,p} . Лемма доказана.

Лемма. Множество R удовлетворяет условию внутренней устойчивости.

Доказательство. Пусть даны два дележа x=(f¹(t₁),…,fⁿ(t₁)) и y=(f¹(t₂),…,fⁿ(t₂)), принадлежащие множеству R. Не ограничивая общности, можем считать, что t₁<t₂. Тогда в силу свойства 2 выполняются неравенства f^s(t₁)f^s(t₂) для всех sS. Поэтому, если

, то дележ x не может доминировать дележ y по коалиции K. А если KP, то v(K)=0. Если бы дележ x доминировал дележ y по такой коалиции, то выполнялось бы неравенство

, а значит и равенства fⁱ(t₁)=0 для всех iK. Но тогда неравенство fⁱ(t₁)>fⁱ(t₂) не может выполняться ни для какого iK. Таким образом, x не может доминировать y и по такой коалиции.

Аналогично доказывается, что y не может доминировать x. Лемма, а вместе с ней и теорема доказаны.

Условия совпадения ядра и решения

Теорема. Пусть <N,v> – 0-1-редуцированная игра и для всякой коалиции K выполняется неравенство

. Тогда C-ядро этой игры не пусто и является ее решением.

Доказательство. Если C-ядро совпадает со множеством всех дележей, то доказывать нечего.

Пусть x – произвольный дележ, не принадлежащий C-ядру. Тогда множество коалиций I, для которых выполняются неравенства

не пусто. Выберем в этом множестве наименьшую по включению коалицию K. Тогда величина

строго положительна.

Определим новый дележ y условием:

Для iK имеем yⁱ≥xⁱ≥v(i). Для iK выполняется неравенство yⁱ≥0=v(i), так как рассматриваемая игра является 0-1-редуцированной. Кроме того,

Поэтому y действительно является дележом.

Далее

и yⁱ>xⁱ для всех iK, следовательно, y доминирует x по коалиции K.

Докажем, что y принадлежит C-ядру. Допустим противное. Пусть некий дележ z доминирует y по коалиции I.

Коалиция I не может содержаться в K, так как в силу выбора последней, тогда выполнялось бы неравенство

, что противоречит определению доминирования.

Если хоть один игрок j из коалиции I не содержится в K, то

.

В случае #I#K отсюда получаем

,

что опять противоречит определению доминирования. Значит, #I>#K.

Если I содержит K, то

и снова получается противоречие.

Если же I не содержит K, то #(I\K)≥#I-#K+1 и поэтому

и вновь получено противоречие.

Поскольку рассмотрены все возможности, сделанное предположение не верно и y на самом деле принадлежит C-ядру.

Итак, доказано что C-ядро не пусто. Более того, так как дележ x выбирался произвольно, то доказано, что всякий дележ, не принадлежащий C-ядру доминируется некоторым дележом из C-ядра. А это означает, что C-ядро является решением.

Задачи

Болван

Литература

Фон Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.
Воробьев Н.Н. Теория игр для экономистов–кибернетиков. М.: Наука, 1985.
Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. М.: Высшая школа. 1998.
Оуэн Г. Теория игр. М.: Мир. 1971.
Бондарева О.Н. Развитие теоретико-игровых методов оптимизации в кооперативных играх и их приложение к многокритериальным задачам // Современное состояние теории исследования операций. М,: Наука, 1979. С.150–172.
Воробьев Н.Н. Современное состояние теории игр // Успехи матем. Наук. Т. XXV. Вып 2(152). 1970. С. 81–140.

9707.doc 01.07.13

Добавить документ в свой блог или на сайт

Похожие:

	Применение ит органами, осуществляющими предварительное расследование преступлений Аипс в деятельности органов, осуществляющих предварительное расследование 8		Урок математики в 6 классе. Проценты. Решение задач Форма урока: решение проблемного вопроса «Жить или курить?» при помощи решения задач, урок беседа, обсуждение
	Методическая разработка урока математики в 6-м классе по теме «Проценты. Решение задач» Форма урока: решение проблемного вопроса «Жить или курить?» при помощи решения задач, урок-беседа, обсуждение		Методические рекомендации для слушателей по подготовке и защите рефератов... Настоящие рекомендации имеют цель оказать помощь курсантам 4-х курсов очной формы обучения факультета следователей по написанию рефератов...
	Закономерности процесса психического развития лиц с овз Обсуждение выявленных показателей образовательной среды и критериев оценки иот, обсуждение презентаций		Урок математики Форма урока: решение проблемного вопроса «Жить или курить?» при помощи решения задач, урок-беседа, обсуждение
	Программа по формированию навыков безопасного поведения на дорогах... Форма урока: решение проблемного вопроса «Жить или курить?» при помощи решения задач, урок-беседа, обсуждение		Решение линейных уравнений и неравенств, систем линейных уравнений с 2 и 3 переменными.(2ч) Обсуждение сборника аналитических (статистических) материалов по итогам участия выпускников области в егэ и в новой форме в 2008-2009...
	Решение организационных вопросов. Обсуждение предложений и вариантов... Общественно-значимые мероприятия, реализующие «Программу воспитания» на 2007-2012гг, подпрограммы«Наша малая Родина», «Здоровье»...		Оборудование для реализации технологии художественной обработки материалов Гостами, Интернет-ресурсами и т п.; элементы программированного обучения; обсуждение докладов и рефератов; составление рецензий;...
	Урок (русский язык, литература, история) «Человек и природа» (10 11 классы) Предварительное д/з: выучить стихотворения русских поэтов, подготовить презентации о природе		Курс 2 курс 17. 01 Мастер-класс И. Штейнберга Проектный семинар.... Проектный семинар. Обсуждение эмпирической части магистерского исследования. Выступают
	Янович Е. Ю. Участие гражданина в уголовном процессе ...		Программа по формированию навыков безопасного поведения на дорогах... Предварительное задание для учащихся. Класс делится на 3 группы, каждая группа получает задание
	Презентация «Решение задач с помощью кругов Эйлера». Презентация... Интегрированное занятие математического кружка (математика + информатика) в 5-м классе по теме "Решение задач с помощью кругов Эйлера....		Тема: Экономический рост Требования к студентам. Курс предназначен для студентов бакалавриата, специализирующихся по направлению «Логистика и управление цепями...

Школьные материалы