Занятие 1. Тема 1. Формальные модели рационального поведения и принципов оптимальности. Построение функции предпочтений и целевой функции.

Функции полезности.

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

(1) .

Значит, множество выбора агента зависит от его предпочтений f(×) и от того множества A, из которого он производит выбор.

Множество выбора зависит от двух составляющих: от функции и от допустимого множества. Предположение, что агент производит выбор из множества выбора (то есть, стремится максимизировать свою целевую функцию) называется гипотезой рационального поведения, которая заключается в том, что агент выбирает с учетом всей имеющейся у него информации наилучшую с его точки зрения допустимую альтернативу, т.е. одну из альтернатив y^*, на которых достигается максимум его целевой функции:

(2) y^* = arg f(y).

Пример. Рассмотрим экономического агента – производственное предприятие – принимающего решение об объеме выпускаемой продукции y. Технология производства такова, что может быть произведен любой объем продукции, не превышающий технологического ограничения y⁺ > 0, то есть множество допустимых действий агента A = [0; y⁺]. Предположим, что известна рыночная цена l > 0 на продукцию, производимую агентом, и известна функция затрат агента c(y) = y² / 2 r, где r > 0 – тип агента (параметр, отражающий эффективность его деятельности).

Если считать, что агент заинтересован в максимизации своей прибыли (разности между выручкой от продаж и затратами), то его функция полезности примет вид:

(3) f(y) = l y – y² / 2 r.

Максимум этой функции на положительной полуоси достигается при выборе действия y_max = l r. Значит решение задачи (2) имеет вид:

(4) y^* = min{l r, y⁺},

то есть агенту следует выбирать объем производства, максимизирующий его прибыль (если такой объем является технологически допустимым), либо максимально возможный (с точки зрения технологических ограничений) объем производства. ·

Помимо принципа (1) принятия решений, агент может использовать принципы ограниченной рациональности, то есть выбирать e-оптимальные действия:

(5) P_e(f(×) ,A) = {y Î A | f(y) ³ f(y^*) – e},

или действия, обеспечивающие ему заданный уровень полезности :

(6) P(f(×), A, } = {y Î A | f(y) ³ }.

Пример 2.2. Рассмотрим Пример 2.1, в котором агент готов выбирать e-оптимальные действия, то есть, действия, которые обеспечивают ему прибыль, отличающуюся от максимально возможной не более чем на e. Предполагая, что технологические ограничения отсутствуют (y⁺ = +¥), из (3) и (5) получим:

(7) P_e(f(×), A) = [l r – ; l r + ],

В свою очередь, из (3) и (6) получим:

(8) P(f(×), A, } = [l r – ; l r + ]

Отметим, что при e = 0 или = f(y^*), получаем, что (7) и (8) превращаются в соответствующее целевой функции (3) выражение (1). Последнее свойство называется принципом обобщения – при предельном переходе к случаю, который был обобщен, все результаты должны соответствовать обобщаемым результатам (отметим, что принцип обобщения справедлив в рамках одной научной парадигмы).

Занятие 2. Тема 1. Иллюстрация перехода от игры в развернутой форме к игре в нормальной форме на примерах игр.

Определение 1.

Игрой n лиц в нормальной форме называется совокупность

, (1)

Содержащая для каждого игрока :

– множество стратегий , элементы которого (возможные действия игрока ) обозначаются ;

– функцию выигрыша (функцию полезности, целевую функцию, критерий оптимальности) , являющуюся отображением из в . Элемент множества называется исходом (ситуацией) игры (1).

Пример. Рассмотрим следующую игру. Случайно выбирается некоторое число z из множества {1,2,3,4} . Каждое имеет вероятность 1/4 . Игрок А, не зная результата, выбирает целое число x , а игрок Б аналогично – число y. Выигрыш определяется следующим образом: |y-z|-|x-z|, (|x-z|-|y-z|) . Т.е. целью является выбор числа, наиболее близкого к z.

В этой игре каждый игрок реально имеет 4 стратегии {1,2,3,4}. (Остальные заведомо плохи.) Если, например, игрок А выбирает 1, а игрок Б выбирает 3, то выигрыш будет равен (2,-2) с вероятностью ¼, (0,0) с вероятностью ¼, (-2,2) с вероятностью ½. Ожидаемый выигрыш, таким образом, равен m(1,3)=(-1/2, 1/2). Подсчитывая все значения m(i,j)Б получим таблицу:

	1	2	3	4
1	(0,0)	(-1/2, 1/2)	(-1/2, 1/2)	(0,0)
2	(1/2, -1/2)	(0,0)	(0,0)	(1/2, -1/2)
3	(1/2, -1/2)	(0,0)	(0,0)	(1/2, -1/2)
4	(0,0)	(-1/2, 1/2)	(-1/2, 1/2)	(0,0)

Таким образом, мы получили игру в нормальной форме.

Занятие 3. Тема 2. Поиск и анализ игровых равновесий на примерах игр. Доминирующие, доминируемые, осторожные стратегии. Оптимальность по Парето.

Равновесие в доминирующих стратегиях постулируется рациональным некооперативным поведением изолированных игроков.

Пример: «дилемма заключенного».

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

Р1
А1
Р2	А2

Стратегиями первого игрока являются строки платежной матрицы: а стратегиями второго игрока – столбцы результаты игры приведены в матрице 2х2, причем «северо-западное» число обозначает выигрыш первого игрока, а «юго-восточное» - выигрыш второго игрока, например

Очевидно, для обоих игроков стратегия А доминирует стратегию Р. Таким образом, единственное равновесие в доминирующих стратегиях имеет вид , т.е. постулируется, что результатом некооперативного поведения является война. В то же время исход (мир) дает больший выигрыш сразу обоим игрокам.

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

Определение Исход в игре (1) доминирует по Парето исход , если

Исход х называется оптимальным по Парето, если он не доминирует по Парето.

Пример 2: «услуга за услугу».

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

благожелательность к игроку 2
неблагожелательность к игроку 2
	благожелательность к игроку 1	неблагожелательность к игроку 1

Любой исход является равновесием в доминирующих стратегиях (проверьте!), но только один из них (благожелательность к игроку 2, благожелательность к игроку 1) оптимален по Парето.

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

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

Определение. В игре (9.1) стратегия является осторожной стратегией -го игрока, если

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

Лемма 3. Пусть множества компактны, а функции непрерывны для всех . Тогда множество осторожных стратегий не пусто, компактно и пересекается с множеством недоминируемых стратегий:

Используя осторожную стратегию, игрок гарантирует себе выигрыш , который называется гарантированным выигрышем. Если набор гарантированных выигрышей оптимален по Парето, то осторожные стратегии также могут быть названы оптимальными.

Определение Игра в нормальной форме (1) несущественна, если нет исхода , для которого

В несущественной игре осторожные стратегии оптимальны в следующем смысле.

Теорема 1. Пусть игра несущественна, - осторожная стратегия игрока для всех . Тогда:

1. для всех и ;

2. – оптимальный по Парето исход;

3. для любого подмножества и любого набора стратегий одновременное выполнение следующих двух условий невозможно:

Доказательство. Поскольку - осторожная стратегия -го игрока, то

Поскольку игра несущественна, то для всех и утверждение 1 теоремы доказано.

Утверждение 2 следует из 3 при . Для доказательства утверждения 3 выберем и такие, что

(9.2)

Применяя утверждение 1 к , получаем

Объединяя обе системы неравенств для всех и учитывая несущественность игры, получаем . Следовательно, строгое неравенство в (9.2) невозможно.

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

Свойство 3 означает, что никакой отдельный игрок и никакая коалиция (подмножество) игроков не имеют причин для одностороннего отхода от оптимальных стратегий.

Заметим, что в игре, которая не является несущественной, никакой набор стратегий не может быть назван оптимальным. В самом деле, два требования оптимальности суть для всех и оптимальность исхода по Парето. По определению 8 эти условия вместе приводят к тому, что для некоторого

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

Оптимальность по Парето

«Равновесие» Парето можно назвать, наверное, самым общим принципом рациональности. Принцип В. Парето утверждает, что, если для ситуации x существует такая ситуация y, что выигрыш каждого из игроков при реализации ситуации у не меньше, чем при реализации ситуации x, и по крайней мере один игрок получает выигрыш, строго больший, то игроки предпочтут ситуацию y ситуации x. Формально определение выглядит следующим образом.

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

Этот принцип представляется в некотором смысле полярным, противоположным к равновесию в доминантных стратегиях. Если РДС представляет собой верх индивидуалистического поведения игроков, то равновесие Парето является критерием сотрудничества. Действительно, если есть ситуация, которая приносит всем игрокам не меньший доход, чем существующая, то почему им не реализовать более выигрышную для всех них ситуацию? Однако для этого необходимы объединенные усилия всех игроков, так как реализующаяся ситуация зависит от «правильного» выбора всех стратегий. Из принадлежности ситуации множеству недоминируемых по Парето ситуаций не следует, что такая ситуация выгодна для всех игроков. Как будет показано ниже при рассмотрении равновесия Нэша, отдельные игроки могут быть недовольны своим выигрышем в недоминируемой по Парето ситуации, так как, изменив в одиночку свою стратегию, они могут увеличить свой выигрыш. Ответные действия других игроков, ущемленных таким поведением, могут вывести ситуацию из множества Парето.

Как и удаление доминируемых стратегий, равновесие Парето обычно выделяет достаточно широкое множество ситуаций, в которых одновременно не может быть увеличен выигрыш всех игроков. Тем не менее, очевидная рациональность оптимальных по Парето исходов при водит к мысли, что хорошая теоретико – игровая концепция решения должна считать рациональными только оптимальные по Парето исходы.

Пример: «Сравнение оптимальности по Парето и РДС». Рассмотрим игру, в которой участвуют n>2 игроков со стратегиями Функции выигрыша игроков:

Так как целевые функции сепарабельны, доминантными стратегиями всех игроков являются стратегии Выигрыши игроков при этом будут равны

Равновесие в доминантных стратегиях не оптимально по Парето, поскольку при выборе, скажем, все игроки получают нулевой выигрыш вместо отрицательного выигрыша в РДС. •

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

Неустойчивость оптимальной по Парето ситуации поднимает вопрос о целесообразности расширения рассматриваемой модели игры. Можно, например, включить в модель возможность заключения игроками договора о выборе стратегий. Если этот договор будет предусматривать наказание за невыполнение соглашения, оптимальный по Парето исход в этой игре будет достижим. Такие игровые модели будут рассмотрены ниже. Аналогичные идеи используются для обеспечения устойчивости оптимальных по Парето исходов в повторяющихся играх.
Занятие 4. Тема 2. Удаление доминируемых стратегий.

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

Пример: выборы большинством голосов с решающим игроком.

Сообщество {1,2,3} должно выбрать одного из трех кандидатов {a,b,c}. Выбор осуществляется по большинству голосов, причем голос игрока 1 является решающим при равенстве голосов. Таким образом, множество стратегий суть Если игроки выдвинули кандидатуры {x₁,x₂,x₃},то выборы проходят по правилу

Предположим, что функция выигрыша игроков при избрании того или иного кандидата имеют следующую структуру:

Обозначим через композицию отображений и , т.е. . Тогда получаем игру трех лиц в нормальной форме .

Осторожное поведение в этой игре означает, что каждый игрок голосует за наиболее предпочтительного для себя кандидата. Очевидно, такое поведение приводит к избранию кандидата .

При условии полной информированности ситуация оказывается совершенно другой. Легко непосредственно проверить, что стратегия игрока 2 доминируется стратегией и что стратегии и не доминируемые, но и не эквивалентные:

Значит, ; аналогично, . С другой стороны, игрок 1 имеет доминирующую стратегию (упражнение 9.7). Таким образом, если считать, что игроки не будут использовать доминируемые стратегии, то множества стратегий сузятся до

, ,

При данном усечении множеств стратегий для игрока 2 стратегия теперь доминируется стратегией и поэтому может быть исключена:

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

Аналогично, стратегия игрока 3 теперь доминируется стратегий . Следовательно, после двух раундов исключения доминируемых стратегий у каждого игрока остается единственная стратегия:

, ,

Но это означает, что будет избран кандидат , хотя он является наихудшим для игрока 1! Получается, что право первого игрока разрешать спорные ситуации оказывается его слабым пунктом, потому что дает возможность сразу предвидеть его стратегический выбор.

Пример: выборы с правом вето.

Пусть сообщество выбирает одного кандидата из множества . Правило голосования такого: начиная с игрока 1, каждый игрок последовательно налагает вето на выбор кандидатуры одного из неотведённых кандидатов. Единственный оставшийся кандидат считается избранным.

Эту игру удобнее представлять не в нормальной, а в развёрнутой форме (рис.1).

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

Предположим теперь, что функции выигрыша удовлетворяют следующим условиям:

u₁(d) < u₁(c) < u₁(b) < u₁(a),

u₂(c) < u₂(d) < u₂(a) < u₂(b),

u₃(c) < u₃(a) < u₃(b) < u₃(d).

Заметим, что игрок 3 имеет доминирующую стратегию: при своём ходе он отводит менее предпочтительного для себя кандидата из двух ещё оставшихся в списке. Зная это и располагая данной информацией о функции выигрыша u₃ из (9.6), остальные игроки могут предвидеть поведение игрока 3, т. е. редуцировать игру на рис.1 к более простой игре в развёрнутой форме (рис. 2):

В свою очередь, для игры на рис. 2. игрок 1, зная предпочтения игрока 2 из (6), может получить ещё более простую игру с одним участником (рис. 3.).

Отсюда совершенно очевидно, как должен действовать игрок 1: отводя кандидата b, он обеспечивает избрание наиболее выгодного для себя кандидата a. Тем самым игрок 1 реализует стратегию, являющуюся компонентой сложного равновесия.

Заметим, что если игрок 1 применяет свою осторожную стратегию, отклоняя на первом шаге наименее выгодного для себя кандидата d, то в конечном итоге избранным оказывается менее выгодный (чем в сложном равновесии) для него кандидат b.

Описанная «попятная» процедура последовательной редукции дерева игры в развёрнутой форме на основе полной информации о функциях выигрыша всех игроков называется алгоритмом Куна.

Теорема Куна утверждает, что при достаточно слабом дополнительном предположении игра в развёрнутой форме (которую всегда можно представить как игру в нормальной форме) разрешима по доминированию, а выигрыши, соответствующие сложному равновесию, задаются алгоритмом Куна.

Пример: парадоксальный метод дележа.

Пираты делят добычу: 100 слитков золота. Процедура дележа устроена следующим образом. Сначала самый старший пират предлагает делёж по своему выбору. Если хотя бы половина пиратов согласна с этим дележом, то он считается принятым. В противном случае (т.е. если большинство пиратов отвергает предложенный делёж) второй по старшинству пират предлагает новый делёж добычи среди оставшихся (n-1) пиратов. Старший пират никакого участия в дальнейшём дележе не принимает. Если новый делёж отвергается большинством голосов, то предложивший его пират устраняется от дальнейшего участия в дележе, и процедура повторяется для (n-2) пиратов и т.д.

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

Если осталось только два пирата, то старший из них забирает всю добычу, поскольку младший пират не составляет большинства. Предположим, что осталось три пирата. Тогда старший из них предлагает делёж, дающий 99 слитков ему и 1 слиток младшему пирату. Младший пират вынужден согласиться с твоим предложением, поскольку он понимает, что, оставшись один на один со средним пиратом, он не получит ничего.

Если пиратов четверо (4, 3, 2, 1), то старший из них (4) будет рассуждать следующим образом: «Если моё предложение отвергнут, то три оставшихся игрока поделят добычу так: (99, 0, 1) (см. предыдущее рассуждение). Следовательно, я должен предложить такой делёж, который хотя бы одному из них был выгоднее этого, а мне давал наибольшую возможную долю». Единственным решением этой задачи является делёж (99, 0, 1, 0), в котором старший пират (4) жертвует всего лишь одним слитком золота в пользу пирата 2.

Равновесный делёж для произвольного количества пиратов теперь можно найти по индукции:

2p+2	2p+1	2p	…								Число пиратов
				…		…		…		…	…
			…	…		…		…		…	…
		100-p		…1							2p+1
	100-p			…0							2p+2

Итак, если или , то в дележе, соответствующем сложному равновесию, доля старшего пирата равна слитков. По одному слитку получают p пиратов, которые имеют номера той же точности, что и старший пират. Парадоксальность этой процедуры дележа состоит в том, что с виду она весьма «демократична», однако добыча делится отнюдь не поровну!

Причина этого парадокса в том, что при последовательном исключении доминируемых стратегий не остается никакой возможности для кооперации. Рассмотрим случай трёх игроков. Среднему пирату следовало бы поспешить предложить младшему некоторый договор (например, о дележе (50,50)), чтобы провалить предложение старшего пирата. Но откуда у младшего пирата возьмётся уверенность в том, что средний пират, став старшим, не отнимет у него всю добычу? Ведь именно такое поведение вытекает из стремления к максимизации выигрыша.

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