Теория игр

Размещено на http://www.allbest.ru/

ИНСТИТУТ МИРОВОЙ ЭКОНОМИКИ И ИНФОРМАТИЗАЦИИ

НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Контрольная работа

«Теория Игр»

Студентка

Шахлович Александра

Москва 2013



1. Игра в нормальной форме

Ответ: Пусть задана позиционная игра n лиц. Построим игру в нормальной форме Г следующим образом.

Множество игроков N в этой игре равно {1,2,…,,n}.

Пусть iN и } - семейство всех информационных множеств позиционной игры, содержащихся в множестве . Будем считать, что есть множество всех функций , отображающих W в ? и удовлетворяющих следующему условию: число не превосходит количества альтернатив в любой вершине из множества I.

Стратегия задает вероятностное распределение на множестве всех альтернатив в вершине v по следующему правилу:

В позициях случая также задается вероятностное распределение на множестве альтернатив условием

если jI.

Для каждой финальной вершины w определен единственный путь , соединяющий ее с начальной вершиной v₀ и числа q_t (t=0,…,k-1), равные p_j(vt), где j номер альтернативы {v_t,v_t+1} в вершине v_t.

Положим

.

Непосредственно проверяется, что величины P(w) задают вероятностное распределение на множестве финальных вершин. Таким образом, величины hⁱ(w) можно считать случайными, причем распределения этих величин зависят от стратегий всех игроков. Обозначим gⁱ(u¹,u²,…,uⁿ) математическое ожидание величины hⁱ при условии, что игроки выбрали стратегии u¹,u²,…,uⁿ соответственно.

Определение. Построенная таким образом игра называется нормальной формой данной позиционной игры.

2. Ситуации сильного равновесия

Ответ:

Пример. «Пиратские корабли»

Два корабля уходят в один и тот же день на остров сокровищ. Каждый из n пиратов должен принять решение, на каком корабле ему плыть: на корабле А или на корабле В. Если ( t-- число пиратов, решивших плыть на корабле А, то путешествие на корабле А затянется на a(t) дней, а путешествие на корабле В, на котором (n-t) пиратов, продлится b(n-t) дней. Каждый игрок стремится минимизировать длительность его собственного путешествия. Данная ситуация описывается следующей игрой:

означает, что игрок i плывет на корабле А.

Предположим, что функции а и b строго монотонно возрастают на {0, ..., n} и выполнены условия



.

Некооперативным равновесием (NE-исходом) в данной игре является любой исход х*, для которого число , удовлетворяет следующим условиям:

нет желания переключаться со стратегии 1 на стратегию О и

)

нет желания переключаться со стратегии 0 на стратегию 1.

Предполагая для простоты, что

для всех t, получаем, что существует единственное целое число t*, удовлетворяющее двум приведенным выше неравенствам, а именно

Следовательно, исход х* есть равновесие по Нэшу тогда и только тогда, когда

.

Если игроки не могут обмениваться информацией перед выбором стратегии (они должны забронировать место на одном из двух кораблей заранее), то они не смогут координировать свои выборы так, чтобы достигнуть равновесия по Нэшу в чистых стратегиях. По-видимому, они будут использовать симметричное вполне смешанное равновесие, которое в действительности доминируемо по Парето любым NE-исходом в чистых стратегиях.

Любое соглашение, основанное на использовании конкретного NE-исхода, является устойчивым также по отношению к отклонениям коалицией, т. е. любой NE-исход является в данном случае сильным равновесием (см. определение ниже). Если a(t*) и b(n--t*) достаточно близки, то все игроки в соответствии с соглашением получают приблизительно равные выигрыши, т. е. выбор конкретного NE-исхода не является конфликтной ситуацией. Для реализации одного из этих исходов пираты должны последовательно и открыто выбирать корабль по следующему алгоритму:

Определение . Для данной игры в нормальной форме скажем, что х*--исход сильного равновесия, если не существует коалиции игроков, для которых было бы выгодно отклониться от данного исхода в случае, если дополнительная коалиция не реагирует на отклонение: не выполнено

игра шепли нэш равновесие

Обозначим SE (G) множество сильных равновесий в игре G. Оно может быть пустым.

Ответ:

Определение 1. Пусть -- игра в нормальной форме, в которой -- конечные множества при всех

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

Смешанным расширением игры G называется игра в нормальной форме , где для всех

В смешанном расширении G_m игры G стратегия игрока i есть вероятностное распределение . Под этим подразумевается, что игрок i конструирует собственную лотерею, в которой стратегия выпадает в соответствии с . To, что лотерея его собственная, означает, что только игрок i знает стратегию, которая действительно выпала в лотерее (даже если остальные игроки, возможно, знают вероятностное распределение ). Более того, лотерея i-го игрока cтохастически не зависит от лотереи j-го игрока при всех j, (таким образом, игрок j не может получить никакой информации о лотерее i-ro игрока на основе наблюдения своей собственной лотереи).

Поскольку случайные переменные независимы в совокупности, то есть ожидаемый выигрыш игрока i. Принимая за функцию выигрыша игрока i в игре G_m, мы тем самым

считаем, что игрок i сравнивает различные лотереи на , попросту сопоставляя связанные с ними математические ожидания выигрыша и . Другими словами, и есть функция полезности по фон Нейману--Моргенштерну, которая распространяет предпочтения игрока i на все возможные лотереи на X_N. Теперь существенно, что функция u_i (х) принимает действительные значения, индуцированные функциями u_i на Х_N .

Чистая стратегия игрока i в исходной игре будет отождествляться со смешанной стратегией выбирающей x_i с вероятностью 1:

В самом деле, из формулы (1) сразу следует, что

для всех

Поэтому будем рассматривать Х_i как подмножество M_i а -- как расширение u_i с Х_N на М_N.

Лемма . Гарантированный выигрыш игрока i в исходной игре не больше его гарантированного выигрыша в смешанном расширении игры:

для всех

.

3. Дуэли с одним выстрелом

Ответ:

Пример «шумная дуэль»: Каждый из двух игроков может произвести один выстрел. Игроки сходятся с постоянной скоростью. В момент t = 0 игроки достаточно далеко друг от друга, а в момент t=1 сходятся вплотную. Задана действительная функция а, на отрезке [0, 1], измеряющая меткость игрока i, i=1, 2. Значение а_i(t) есть вероятность того, что игрок i поразит игрока j, если будет стрелять в момент t. Предположим, что а_i не убывает, непрерывна и удовлетворяет краевым условиям .

Выигрыш (игрока 1) равен +1, если первый игрок поражает второго до того, как сам будет поражен; --1 в симметричном случае и 0, если ни один не поражен, либо оба поражены одновременно.

Множества стратегий суть X₁ = X₂ = [0, 1]. Стратегия x_i игрока i означает:

«Я буду стрелять в момент t = x_i если противник не выстрелит раньше. Если же он выстрелит, но промахнется, то я для надежности буду стрелять в момент t= 1». Следовательно, нормальная форма игры имеет вид (X₁, X₂, u₁), где

Вычислим осторожные стратегии игрока 1. Для любого

Пусть l есть отрезок, принадлежащий [0, 1] (возможно, и точка), определяемый из условия

Функция возрастает до l, постоянна на l и убывает после l. Поэтому ) является множеством осторожных стратегий игрока 1. Гарантированный выигрыш игрока 1 есть общее значение функций на l. Аналогично можно показать, что и гарантированный проигрыш второго игрока равен . Следовательно, есть цена игры, а -- множество оптимальных стратегий для обоих игроков. Каждый стреляет оптимально, когда

4. Вектор Шепли произвольных игр

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

1. для любого носителя K (аксиома эффективности);

2. для любого автоморфизма игры (аксиома симметрии);

3. для любых двух игр <N,v> и <N,v> (аксиома агрегации).

Лемма. Вместо аксиомы эффективности можно использовать следующее свойство

4. для любого болвана i (аксиома болвана).

Доказательство. Пусть выполнены аксиомы 1,2,3. Рассмотрим произвольного болвана i. Множество N\{i} является носителем, поэтому

.

Так как игрок i является болваном



v(N\{i})+v(i)=v(N).

А так как вектор (v) является дележом в игре <N,v> выполняется условие

.

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

Обратно, пусть выполняются аксиомы 2, 3 и 4. Рассмотрим произвольный носитель K. Так как все игроки, не входящие в K являются болванами, выполняется условие

.

По аксиоме болвана v(j)=^j(j) для jN\K. А так как вектор (v) является дележом в игре <N,v> выполняется условие

.

Из этих трех условий получаем равенство

,

означающее, что выполнено утверждение аксиомы 1.



Лемма. Возможно задание вектора Шепли двумя свойствами:

1) для любой перестановки множества N (аксиома анонимности);

2) если для всех коалиций K не содержащих игрока i, то _i(v)= _i(w) (аксиома маргинальности).

5. Арбитражная схема Нэша

Ответ:

Арбитражные решения для случая двух игроков впервые определил Джон Нэш в 1950 г. Положения (принципы), принимаемые как исходные, называются аксиомами. Нэш предложил для обоснования арбитражного решения следующие аксиомы.

А1. Аксиома допустимости. Арбитражное решение должно содержаться в множестве , т.е. .

А2. Аксиома индивидуальной рациональности. Арбитражное решение должно давать каждому игроку выигрыш не меньший, чем его выигрыш в точке разлада (status quo), т.е.

, .

А3. Аксиома оптимальности по Парето. Арбитражное решение должно быть оптимальным по Парето, т.е. в не должно существовать такого , , которое не хуже для обоих игроков, чем арбитражное решение .

А4. Аксиома независимости от линейного преобразования. Этот принцип содержательно означает, что арбитражное решение не должно зависеть от выбора единицы измерения полезности и точки начала отсчета.

Определим этот принцип формально. Пусть множество получается из с помощью линейного преобразования, т.е.

,

где , , , - произвольные числа.

Тогда, если арбитражное решение для арбитражной задачи , то для арбитражной задачи , где

, ,

арбитражным решением должно быть

, .

А5. Аксиома симметрии. Если множество допустимых результатов симметрично, т.е. из того, что следует , то при в арбитражном решении арбитражной задачи должно выполняться . Другими словами, если множество симметрично и , то и в арбитражном решении должно быть .

А6. Аксиома независимости от посторонних альтернатив. Если арбитражное решение задачи и , где , то должно быть арбитражным решением задачи . Т.е. отбрасывание любых альтернативных исходов, если они не являются решением, не должно изменять арбитражного решения.

Справедливо следующее утверждение.

Теорема Нэша. Если множества выпуклы, замкнуты, ограничены и имеют внутренние точки, то существует единственное арбитражное отображение , удовлетворяющее аксиомам А1 - А6. При этом арбитражное решение определяется условием

.

Будем называть арбитражное решение, определяемое таким образом, арбитражным решением Нэша. Таким образом, задача отыскания арбитражного решения Нэша состоит в максимизации функции на множестве .

Итак, если принципы А1 - А6 принимаются как справедливые, то и арбитражное решение Нэша должно восприниматься как справедливое.

6. Существование ситуации равновесия в конечной позиционной игре с полной информацией

Ответ:

Теорема. В любой многошаговой (позиционной) игре с полной информацией на конечном древовидном графе существует ситуация абсолютного равновесия по Нэшу (NE)..

Доказательство. Докажем по индукции по длине игры l. Пусть l ??1 (рис. 1). Предположим - множеству очередностей i-го игрока. Игрок i выбирает альтернативу из условия максимизации своего выигрыша .

Игроки получают , соответственно. Если i -й игрок отклонится, он получит меньше, следовательно, он будет действовать согласно стратегии, образующей абсолютное NE.

Предположим теперь, что теорема справедлива для всех игр, таких что длина каждой из них не превосходит l?1.

Докажем, что ситуация равновесия существует для игры G длины l.

Так как подыгры (см. рис. 2), имеют длину не более l ?1, то по индукционному предположению теорема справедлива, следовательно, существует ситуация абсолютного NE

Пусть

.

И пусть в точке z* ходит игрок i : . Тогда игра G переходит в подыгру . Но в подыгре каждый i-ый игрок получает выигрыш , соответствующий ситуации NE . Поскольку - сужение стратегии на множество , то выигрыш i-го игрока в ситуации u* игры G равен выигрышу в ситуации

(1)

Аналогично доказывается, если . Пусть произвольная стратегия игрока в игре G. Обозначим .

Тогда

Утверждение теоремы следует теперь из (1), (2).

7. Теоремы о существовании ситуаций равновесия для непрерывных антагонистических игр

Ответ:

Существуют несколько теорем, которые обозначают необходимые условия существования равновесий в непрерывных играх. Определим такое свойство функций:

Определение: Пусть X - подмножество конечномерного Евклидова пространства.

Функция u: X > R является квазивогнутой если для всех , множество является выпуклым.

Легко показать, что каждая вогнутая функция является квазивогнутой, но не наоборот.

Также верно то, что каждая монотонная функция одной переменной является квазивогнутой.

Примеры квазивогнутой и не квазивогнутой функций приведены на рисунке.

На рисунке (a) функция удовлетворяет условиям: для данного (как и для любого другого) множество (показанное на рисунке) является выпуклым. На рисунке (b) условия квазивогнутости нарушаются: для данного множество является объединением двух отрезков - то есть не выпуклым.

На свойство квазивогнутости опирается следующая теорема, доказанная Гликсбергом (1952):

Теорема 1. Рассмотрим непрерывную игру G, в которой множества стратегий Si являются компактными. Предположим, что для каждого игрока i функция полезности является квази-вогнутой по s_i для всех s_?i ? S_?i. Тогда в игре существует равновесие Нэша в чистых стратегиях.

Доказательство этой теоремы похоже на доказательство теоремы Нэша: мы показываем, что точечно-множественное отображение, построенное из функций реакции игроков, удовлетворяет условиям теоремы Какутани и имеет непрерывную точку. Более того, теорема о существовании смешанного равновесия в конечных играх является частным случаем этой теоремы. Действительно, смешанное расширение любой конечной игры является непрерывной игрой, удовлетворяющей условиям Теоремы 1.

Теорема 2. Рассмотрим игру, в которой множества стратегий Si являются выпуклыми и компактными подмножествами конечномерных Евклидовых пространств . Предположим, что для каждого игрока i функция полезности является непрерывной по . Тогда в игре существует равновесие Нэша в смешанных стратегиях.

Доказательство этой теоремы технически более сложно, чем доказательства предыдущей теоремы, ибо множество смешанных стратегий в непрерывной игре является бесконечномерным. Здесь необходим более сильный результат, чем теорема Какутани; доказательство (или даже формулировка) которого выходят за рамки этой книги. Однако можно рассуждать (весьма приблизительно), что нарушение непрерывности функций полезности по чистым стратегиям ведет к нарушению непрерывности по смешанным стратегиям.

8. Вектор Шепли для игр власти

Ответ: Предположим, что некоторая интегрированная система, состоящая из n подразделений, совместно выполнила некоторый объем работ. Этот же объем могли бы выполнить либо одно «главное» (особенное) и любое (одно или несколько) из остальных подразделений, либо все остальные вместе без «главного». Требуется определить «справедливую» долю каждого из подразделений.

Построим формальную модель. Присвоим каждому подразделению интегрированной системы порядковый номер, обозначив «главное» номером «1». Если обозначить S - коалиция (группа) подразделений, а I - множество различных коалиций, то характеристическая функция данной игры примет следующий вид (1 - работа выполнена, 0 - нет):

Поскольку С-ядро рассмотренной выше игры является пустым множеством, поэтому представляют интерес другие принципы оптимальности.

Поскольку априори все «неглавные» участники равноправны, можно ожидать равенства их выигрышей для любого принципа оптимальности, что подтверждается полученными результатами. Выигрыш «главного» игрока всегда больше выигрыша других игроков (n > 3), но его относительная величина увеличивается с ростом количества участников. Например, вектор Шепли оценивает «монополию» «главного» игрока по «закону»

Вместе с тем качественное свойство, определяющее «главного» игрока, нуждается в уточнении. Если это свойство, например, отражает более высокую производительность, то согласно вектору Шеплиn«главный» игрок эквивалентен сразу трем игрокам. Его выигрыш должен составлять ровно половину от всего дохода, хотя остальные подразделения (без «главного») так же могли бы справиться с данной работой и получить больший выигрыш (каждому по 1/3 вместо 1/6). Поэтому дележ согласно N-ядру представляется более «справедливым», чем по вектору Шепли.

9. Связь вектора Шепли с С-ядром

Ответ:

Лемма. В 0-1-редуцированной игре трех лиц вектор Шепли принадлежит ядру тогда и только тогда, когда выполняются неравенства

4v({1,2})+ v({1,3}+ v({2,3})) 4, 4v({1,3})+ v({1,2}+ v({2,3})) 4,

4v({2,3})+ v({1,2}+ v({1,3})) 4.

Доказательство. Согласно полученной формуле в данном случае вектор Шепли имеет компоненты

Согласно теореме о характеризации ядра, этот вектор принадлежит C-ядру, тогда и только тогда, когда выполняются неравенства

Откуда и следует утверждение леммы.

Пример. Затраты на создание системы водоснабжения в трех районах описываются характеристической функцией

v({1})=-120,

v({2})=-140,

v({3})=-120,

v({1,2})=-170,

v({1,3})=-160,

v({2,3})=-190,

v({1,2,3})=-255.

Вектор Шепли в этой игре не принадлежит C-ядру, так как, например, . Однако C-ядро в этой игре не пусто. Ему принадлежит, например, точка .

Размещено на Allbest.ru

...