«Теория игр Краткий конспект лекций Тема 1. Введение в теорию игр Теория игр как научная дисциплина изучает отношения между людьми, ...»

Теория игр

Краткий конспект лекций

Тема 1. Введение в теорию игр

Теория игр как научная дисциплина изучает отношения между людьми, которые

руководствуются несовпадающими (а иногда и противоположными) мотивами. Наряду с

традиционными играми, такими как покер, шахматы, футбол и многие другие, теория игр

изучает и такие серьезные отношения как рыночная конкуренция, гонка вооружений,

загрязнение окружающей среды. В теории игр все эти серьезные отношения называют

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

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

Неоклассическая экономическая теория обычно предполагает существование и функционирование «совершенного рынка». Каждый субъект принимает решения, основываясь на индикаторах состояния этого рынка.

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

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

Применительно к экономике, теория игр изучает функционирование экономических систем в условиях «несовершенного рынка». Игровые модели олигополий и аукционов являются примерами успешного применения игрового подхода в экономике. Решение проблемы ассимметричной информированности участников экономической системы - также важное достижение теории игр. Первое математически строгое определение игры было дано венгерским математиком Джоном фон Нейманом, которого по праву считают одним из величайших математиков 20-го века1. Удивительно, но в своей работе, опубликованной в далеком 1928 году2, он сформулировал игру n лиц с нулевой суммой точно также, как она формулируется сегодня.

В этой же работе Дж. фон Нейман доказал свою знаменитую теорему о существовании решения в смешанных стратегиях для матричных игр (n = 2). Пожалуй трудно вспомнить другой такой случай (в любой области знаний), когда новая теория была столь строго формализована с момента ее зарождения. Но все же принято считать, что теория игр как самостоятельный раздел экономической теории сформировалась после публикации в 1944 г. Дж. фон Нейманом в соавторстве с Оскаром Моргенштерном книги «Теория игр и экономическое поведение» . Сегодня игровые модели столь разнообразны, что вряд ли возможно дать простое формальное определение игры, которое бы включало все модели. Неформально, игра - это модель конфликтной ситуации, в которой 1) участвует n лиц (игроков), 2) заданы правила игры (способ принятия решений каждым из игроков), 3) определены правила осуществления платежей между игроками.

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

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

Тема 2. Стратегическое взаимодействие

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

Предположим, что два человека играют в простую игру. Игрок A пишет на листке бумаги одно из двух слов: "верх" или "низ". Одновременно игрок B пишет на листке бумаги "слева" или "справа". После того как они это сделают, листки бумаги передаются на рассмотрение, и каждый из них получает выигрыш, представленный в табл.27.1. Если A говорит "верх", а B говорит "слева", то мы смотрим в верхний левый угол матрицы. В этой матрице выигрыш A показан первой записью в клеточке, 1, а выигрыш B - второй,

2. Аналогично, если A говорит "низ", а B говорит "справа", то A получает выигрыш 1, а B - выигрыш 0.

У игрока A имеются две стратегии: он может выбрать "верх" и может выбрать "низ".

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

Каков будет исход игры такого рода? Игра, описанная в табл.27.1, имеет очень простое решение. С точки зрения игрока A, для него всегда лучше сказать "низ", так как его выигрыш при таком выборе (2 или 1) всегда больше, чем соответствующие записи в таблице в случае, если бы он сказал "верх" (1 или 0). Аналогично для B всегда лучше сказать "слева", поскольку 2 и 1 лучше, чем 1 и 0. Таким образом, следует ожидать, что стратегия равновесия для A будет заключаться в том, чтобы следовать стратегии "низ", а для B - стратегии "слева".

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

Каков бы ни был выбор игрока B, игрок A всегда получит больший выигрыш, если будет следовать стратегии "низ", поэтому ему имеет смысл выбирать стратегию "низ". И каков бы ни был выбор, сделанный игроком A, B получит больший выигрыш, если будет следовать стратегии "слева". Следовательно, эти варианты выбора доминируют над альтернативными, и перед нами - равновесие с доминирующими стратегиями.

Если в какой-то игре у каждого игрока имеется доминирующая стратегия, можно предсказать, что данная игра будет иметь равновесный исход. Ведь доминирующая стратегия есть стратегия, которая является наилучшей вне зависимости от того, что делает другой игрок. В данном примере следовало бы ожидать равновесного исхода, при котором A следует стратегии "низ", получая равновесный выигрыш 2, а B следует стратегии "слева", получая равновесный выигрыш 1.

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

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

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

Утверждалось, что реально существующие картели иногда пытаются использовать такую стратегию. Пример такого рода был недавно описан Робертом Портером в одной из статей. Объединенный Исполнительный Комитет был знаменитым картелем, устанавливавшим в конце 1800-х гг. цену грузовых железнодорожных перевозок в Соединенных Штатах. Образование этого картеля предшествовало введению в Соединенных Штатах антитрестовского законодательства, и в те времена он был совершенно законным.

Картель определял, какова могла быть рыночная доля каждой железной дороги в грузовых перевозках. Каждая фирма устанавливала свои тарифы индивидуально, а ОИК следил за тем, сколько груза отправляла каждая из фирм. Однако в течение 1881, 1884 и 1885 гг. было несколько случаев, когда, по мнению некоторых членов картеля, другие фирмы-члены, невзирая на соглашение, снижали тарифы с целью увеличения своей рыночной доли. В эти периоды часто имели место ценовые войны. Когда одна из фирм пыталась смошенничать, все остальные снижали цены, чтобы "наказать" отступника.

Такого рода стратегия "зуб за зуб" могла, очевидно, поддерживать картельное соглашение в течение какого-то времени.

ПРИМЕР: Стратегия "зуб за зуб" в ценообразовании авиакомпаний Стратегия "зуб за зуб" широко используется реально существующими олигополиями. Интересный пример данного рода дает ценообразование авиа-компаний.

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

Так, "Northwest" ввела льготные ночные тарифы на рейсы в города Западного побережья в попытках заполнить пустые места. "Continental Airlines" истолковала это как попытку увеличить долю рынка за ее счет и ответила снижением всех тарифов до Миннеаполиса до уровня ночных тарифов "Northwest". Однако сроки действия сниженных тарифов "Continental" истекали через день или два после их введения.

"Northwest" истолковала это как сигнал о том, что "Continental" не имеет серьезных намерений в отношении данного рынка и просто хочет, чтобы "Northwest" отменила свои льготы по ночным тарифам. Однако "Northwest" решила послать "Continental" собственное сообщение: она ввела набор дешевых тарифов на полеты на Западное побережье из Хьюстона - опорного пункта "Continental"! Тем самым, "Northwest" давала понять, что считает введенные ею льготы оправданными, ответ же "Continental" - неуместным.

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

Неписаные правила конкуренции на рынках авиаперевозок, где существует дуополия, состоят, похоже, в следующем: если другая фирма поддерживает высокий уровень цен, я тоже буду поддерживать высокий уровень цен; однако если другая фирма снизит цены, я, следуя стратегии "зуб за зуб", тоже отвечу снижением цен. Другими словами, обе фирмы "живут в соответствии с Золотым правилом": поступай с другими так же, как ты хотел бы, чтобы они поступали с тобой. Эта угроза возмездия способствует поддержанию всех цен на высоком уровне.

Тема 3. Игры в нормальной форме

Итак, игра в нормальной (или стратегической) форме - это тройка {I, S = Пi{Si}iI u = (u1,…,un)}, где I = {1,..., n} - множество игроков, Si - множество стратегий (ходов), доступных игроку i = 1,..., n, ui: S = ПiI Si R1 - функция выигрышей игрока i, ставящая в соответствие каждому набору стратегий s = (s1,..., sn), называемому также ситуацией, выигрыш этого игрока.

Стандартный пример здесь - дуополия по Бертрану и по Курно, когда стратегии - это цены или объемы выпуска, соответственно, а выигрыши - это прибыль (см. п. 1.8Важным предположением, которое играет ключевую роль в теории, состоит в предположении, что все игроки рациональны, в том смысле, что каждый игрок рассматривает имеющиеся в его распоряжении альтернативы, формирует представления относительно неизвестных параметров, имеет четко определенные предпочтения и выбирает свои действия в результате некоторого процесса оптимизации (максимизации своей целевой функции). Более того, не менее существенным является факт общеизвестности (общего знания) рациональности игроков, т. е. все игроки не только рациональны, но и знают, что другие игроки рациональны, что все игроки знают, что все игроки знают, что они рациональны и т. д. Формальное определение общеизвестности см.

Замечание 1.2.1. В последние годы появилось значительное число работ, посвященных исследованию моделей ограниченной рациональности. Основная мотивация этих работ - неудовлетворенность теорией, оперирующей с "совершенно рациональным человеком", поскольку мы является свидетелями весьма частого несоответствия реального поведения людей предположению "совершенной рациональности". Идея моделирования ограниченной рациональности восходит к работам Герберта Саймона (Simon (1955, 1956), см. также Simon (1972, 1976)). Обсуждение проблем, связанных с моделировнием ограниченной рациональности можно найти, например, в книге Rubinstein (1998).

Различные взгляды на проблемы моделирования рациональных и ограниченных рациональных игроков изложены в работах Binmore (1987, 1988), Auman (1996).

Обратимся к тому случаю, когда I = {1,2} и множества стратегий каждого из двух игроков - конечны. В этом случае игру можно "изобразить" с помощью матрицы (см.

рис.6), где М = Si - число возможных стратегий игрока 1, К =S2 -число возможных стратегии игрока 2, a mk u1 s1m, s 2k, bmk u 2 s1m, s2k, k = l,...,K, m = 1,...,M.

Эту же игру можно представить в виде двух матриц (поэтому такие игры называются часто биматричными), элементами которых являются элементы аmk и bmk, соответственно.

Для конечной антагонистической игры, т. е. игры двух лиц такой, что u1(s1, s2) = u2(s1, s2) для всех siSi, i = 1,2, справедливо равенство аmk = bmk, для всех m и k,

Рис. 6.

а поэтому такая игра может быть задана только одной матрицей (аmk) m=1,...,M, k=1,..., К и поэтому конечные антагонистические игры называются матричными (см. подробнее Дополнение (Раздел 1.13)).

Смешанная стратегия i - это вероятностное распределение на множестве чистых стратегий Si. (Мотивацию введения смешанных стратегий мы оставляем на будущее).

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

Будем обозначать пространство смешанных стратегий i-ого игрока через i, а i(s i) - вероятность того, что выбирается стратегия s;. Пространство наборов смешанных стратегии элементы которого мы будем обозначать через. Носитель смешанной стратегии i - это множество тех чистых стратегий, которым "приписана" положительная вероятность.

Определение 1.2.1. Если Si - конечное множество чистых стратегий игрока i, то смешанная стратегия i: Si ставит в соответствие каждой чистой стратегии siSi вероятность i(si) 0 того, что она будет играться, причем (Обратим внимание на то, что индекс i означает здесь, что речь идет о стратегии игрока i. Поэтому, если мы будем говорить о разных стратегиях игрока i, то мы будем обозначать их si, s"i, s"i,...).

Нетрудно заметить, что множество смешанных стратегий игрока i - это (ki 1)мерный симплекс, где ki - число чистых стратегий i-го игрока.

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

Важно отметить, что выигрыш i-ого игрока есть линейная функция от вероятностей i, а также является полиномом от профиля, а потому непрерывен. Наконец, чистые стратегии являются вырожденными смешанными стратегиями, приписывающими вероятность 1 данной чистой стратегии и вероятность 0 - остальным.

Определение 1.2.2. Смешанным расширением игры Г = {I, S, u} называется игра а, u(), где, определяется равенством (2.1).

Пример. Рассмотрим игру, изображенную на рис. 7.

L M R Рис. 7.

Пусть 1 = (1/3, 1/3, 1/3) (это означает, что смешанная стратегия игрока 1 приписывает ему играть стратегии u, m и d с вероятностями 1/3), 2 = (0, 1/2, 1/2) (эта смешанная стратегия игрока 2 предписывает играть стратегии М и P с равными вероятностями и не играть стратегию L вовсе). В данном случае мы получаем + 1/3(02 +1/2*8 + *3) + 1/3(0*3 + *9 +1/2*2) = 11/2,

–  –  –

Посмотрим внимательно на приведенную выше игру (рис.7). Независимо от того, как играет игрок 1, R дает игроку 2 строго больший выигрыш нежели М. В этом смысле стратегия М строго доминируема, поэтому ясно, что рациональный игрок 2 не должен играть М. Далее, если игрок 1 знает (т.к. он сам рационален и знает, что другой рационален...), что 2 не будет играть М, то для него и будет лучше, чем га или d. Наконец, если игрок 2 знает, что игрок 1 знает, что игрок 2 не будет играть М, то игрок 2 знает, что 1 будет играть и, а тогда 2 должен играть L. Этот процесс - последовательное удаление строго доминируемых стратегий (мы дадим позднее строгое определение и соответствующий экономический пример). Вопрос, естественно возникающий здесь: "А не зависит ли множество стратегий, выдерживающих такое исключение доминируемых стратегий, от порядка исключения?" К счастью, нет, и дело здесь в том, что если стратегия si строго хуже чем s" для всех стратегий оппонента из множества D, то она хуже чем s" и для любого подмножества множества D.

Посмотрим теперь на следующую игру (см. рис. 8) Рис. 8.

Здесь М не доминируется строго стратегией u, и М не доминируется строго стратегией D. Однако, если игрок 1 играет u с вероятностью 1/2 и D - с вероятностью 1/2, он обеспечивает себе выигрыш 1/2 независимо от того, как играет игрок 2.

Следовательно, чистая стратегия может строго доминироваться смешанной стратегией, даже если она не доминируется строго никакой чистой стратегией.

Введем следующие обозначения: пусть iI, тогда через s-i S-i будем обозначать набор стратегий игроков из I\{i}, (s"i, s-i) обозначает набор стратегий (s1, …, si-1, s"i, si+1, …, sn). Аналогично, для смешанных стратегий ("i, -i) - это (1, …, i-1, "i, i+1, …, n).

(Заметим, что в этих обозначениях s = (si, s-i)).

Определение 1.3.1 Чистая стратегия Si игрока i в игре Г строго доминируема (строго доминируется), если существует другая чистая стратегия s"i такая, что (3.1) для всех s-i S-i.

В этом случае говорят, что стратегия s"i доминирует стратегию si. Стратегия si. слабо доминируется, если существует такая s"i, что (3.1) выполняется как нестрогое неравенство, но хотя бы для одного набора s-i неравенство строгое.

Аналогично определение и для смешанных стратегий:

Определение 1.3.2. Смешанная стратегия i строго доминируется в игре; если существует другая стратегия "i такая, что для всех -i-i выполняется Стратегия i называется строго доминирующей стратегией для игрока i в игре, если она строго доминирует любую другую стратегию из i.

Заметим, что для того, чтобы проверить, что i строго доминируется стратегией "i, нам нужно посмотреть на "поведение" этих двух стратегий против чистых стратегий оппонентов игрока i.

Формально:

тогда и только тогда, когда Действительно: рассмотрим разность Тогда если (В), то (А), т.к. все 0. (В) следует из (А), т.к. s-i - вырожденный случай -i.

Задача. Докажите, что если чистая стратегия si является строго доминируемой, то таковой же является и любая стратегия, использующая si с положительной вероятностью.

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

Рис. 9.

Стратегия первого игрока (1/2, 1/2,0) дает ожидаемый выигрыш вне зависимости от того, что играет игрок 2, а следовательно, строго доминируется стратегией D.

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

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

Вернемся к игре, изображенной на рис. 7. Нетрудно убедиться в том, что здесь в результате последовательного удаления строго доминируемых стратегий остается пара стратегий (u, L). На первом шаге удаляется стратегия М (она доминируется стратегией R).

Затем удаляется стратегия m (доминируемая стратегией u).На третьем шаге удаляется стратегия d (доминируется стратегией u). Наконец, на последнем шаге удаляется R.

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

Рассмотрим, например, следующую игру (рис. 10).

Очевидно, что здесь стратегия L доминируется стратегией R, а потому ситуация (D,R) является хорошим кандидатом. Но... Проигрыш игрока 1 в ситуации (_D, L) слишком велик, поэтому вполне можно допустить, что игрок 1 может не рискнуть сыграть стратегию d (допуская, например, возможность случайной ошибки игрока 2).

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

Последовательное удаление слабо доминируемых стратегий Рассмотрим следующую известную игру "Море Бисмарка". Предыстория события такова: 1943г. Адмирал Imamura получил приказ доставить подкрепление по морю Бисмарка на Новую Гвинею. В свою очередь адмирал Кеnnеу должен был воспрепятствовать этому. Imamura должен был выбрать между Северным (более коротким) и Южным маршрутами, а Кеnnеу - решить куда посылать самолеты, чтобы разбомбить конвой. Причем в течение одного дня самолеты могут бомбить лишь на одном из двух направлений - либо на Северном, либо на Южном маршрутах (но не на двух).

Поэтому, если Кеnnеу посылает самолеты в сторону неправильного маршрута, то они могут вернуться, но число дней, когда возможна бомбежка, уменьшается. Описываемая ситуация моделируется следующей игрой. Считаем, что Северный маршрут займет 2 дня, а Южный - 3. (См. рис. 11).

Рис. 11.

Вообще говоря - это матричная игра, т. е. антагонистическая игра с конечным множеством стратегий у каждого игрока. Ни один игрок не имеет доминирующей стратегии. Но здесь можно говорить о слабом доминировании: для Imamur"ы стратегия Юг слабо доминируема, так как для любой стратегии Кеппеу проигрыш Imamur"ы (число дней, когда конвой будет подвергаться бомбордировкам) не меньше для Ю, чем для С, но для стратегии Кеnnеу Ю - проигрыш при С строго меньше, чем при Ю.

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

Представим себе, что Кеnnеу понимает это и считает, что Imamura выберет Север. В этой новой ситуации Кеnnеу имеет уже доминирующую стратегию - Север. Это и дает нам равновесие при последовательном удалении доминируемых стратегий. (В действительности, так и случилось: 2-5марта 1943 г. ВВС США и Австралии атаковали японский конвой, который шел по Северному пути и потопили все транспортные корабли и 4 эсминца: из 7000 чел. до Новой Гвинеи добрались 1000.) Процедура последовательного удаления слабо доминируемых стратегий аналогична удалению строго доминируемых стратегий. Однако здесь есть одно весьма значительное отличие. А именно, множество стратегий, которые выдерживают последовательное удаление слабо доминируемых стратегий (то есть остаются) может зависеть от порядка удаления стратегий.

Действительно, рассмотрим следующую игру (рис. 12).

–  –  –

Если вначале удаляется u (слабо доминируется М), а затем L (слабо доминируется R), то мы приходим к исходу (2,1) (второй игрок выбирает R). Если же вначале удаляется D (слабо доминируется М), а затем R (слабо доминируется L), то мы приходим к исходу (1,1).

Рассмотрим несколько примеров. Мы начнем со знаменитой Дилеммы Заключенного - в некотором смысле чрезвычайно простой игры, которая в разных формулировках встречается в большинстве учебников по теории игр, которая приводится едва ли не в самом начале каждого курса и которую многие сразу же вспоминают, когда слышат словосочетание "теория игр".

Дилемма Заключенного. Ставший почти хрестоматийным сюжет этой стилизованной истории таков. Двое подозреваемых в совершении тяжкого преступления арестованы и помещены в одиночные камеры, причем они не имеют возможности передавать друг другу какие-либо сообщения. Их допрашивают поодиночке. Если оба признаются в совершении преступления, то им грозит, с учетом их признания, тюремное заключение сроком по 6 лет каждому. Если оба будут молчать, то они будут наказаны за совершение какого-то незначительного преступления и получат в этом случае по 1 году тюремного заключения. Если же один из них сознается, а другой - нет, то первый, за содействие следствию, будет вовсе освобожден от наказания, тогда как второй будет приговорен к максимально возможному за данное преступление наказанию - 10-летнему тюремному заключению.

Описанная история может быть представлена следующей игрой (рис. 13).

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

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

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

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

"Дилемма заключенного - 2". Рассмотрим две страны добывающие нефть, которые мы назовем, скажем, А и В. Эти две страны могут кооперироваться, договариваясь об объемах ежедневной добычи нефти, ограничиваясь, к примеру, добычей 2 млн. баррелей нефти в день для каждой страны. С другой стороны, страны могут действовать некооперативно, добывая, скажем, по 4 млн. баррелей в день. Такая ситуация может быть представлена следующей игрой, в которой указаны прибыли стран, в зависимости от их объемов добычи нефти (рис. 14).

Рис. 14.

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

Легко видеть, что и здесь у каждого из игроков есть доминирующая стратегия - "не кооперироваться". В результате страны получают прибыль 32 и 24 (млн. долларов в день), что гораздо меньше, нежели в ситуации кооперативного поведения.

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

Можно ли достичь "кооперативного поведения" в дилемме заключенного? Как мы увидим в следующей главе - да.

Здесь мы ограничимся лишь еще одним примером на эту же тему.

"Дилемма заключенного - 3". Предположим, что есть 2 работника, которые могут "работать" (si = 1) и "увиливать" (si = 0) (si - уровень усилий, которые прикладывает работник i). Суммарный выпуск "команды" 4(s1+s2) делится поровну между работниками.

Каждый работник несет издержки равные 3, если работает, и равные 0, если увиливает.

Соответствующая матрица изображена на рис. 15.

"Работать" - строго доминируемая стратегия для каждого работника.

Аукцион второй цены. У продавца есть одна единица неделимого товара. Есть п потенциальных покупателей, которые оценивают товар, соответственно, в 0 v1 … vn и эти оценки являются "общеизвестными". Покупатели одновременно делают свои заявки (назначают цену) six x...x, а каждый игрок i принимает решение в зависимости от различных возможных реализаций его сигнала i.

Предположим, однако, что есть некий общий сигнал , который могут наблюдать все игроки. В этом случае появляются новые возможности. Так, к примеру, в упомянутой только что игре "Семейный спор" оба игрока могут, например, решить идти на футбол, если, скажем, 1/2, и идти на балет, если 1/2. Выбор стратегии каждым игроком остается случайным, тем не менее здесь мы имеем дело со вполне скоординированными действиями (Он и Она оказываются вместе), явно имеющими равновесный характер, причем если один игрок решает следовать этому правилу, то и для второго оптимально придерживаться этого же правила. Это дает нам пример коррелированного равновесия (совместного равновесия), введенного Р.Ауманом (Auman (1974)).

Формально такое равновесие - это специальный случай равновесия по БайесуНэшу, которое мы рассмотрим в главе 3.

Предложение 1.7.2 В смешанном расширении любой игры Г с конечными множествами стратегий S1,..., Sn существует равновесие по Нэшу в смешанных стратегиях.

Это предложение непосредственно следует из следующего более общего результата, так как в игре множества стратегий игроков - это симплексы в соответствующем пространстве RM.

Теорема 1.7.

1 Debreu (1952), Glicksberg (1952), Fan Ky (1952). Если для каждого i = 1,..., п (1) Si - непусто, выпукло и компактно (в некотором RM);

(2) ui(s1,..., sn) - непрерывна по (s;,..., sn) и квазивогнута по s;, то в игре Г = {I, {Si}, {ui}} существует равновесие по Нэшу в чистых стратегиях.

Напомним, что функция f: RK R называется квазивогнутой, если для любого а множество {х: f(x) а} - выпукло.

Доказательство этого предложения опирается на следующую лемму.

Лемма 1.7.

1 Если выполнены условия Теоремы 1.7.1, то отображение лучших ответов bi непусто, выпуклозначно (т. е. множества bi(s-i) - непусты и выпуклы) и полунепрерывно сверху.

Доказательство леммы 1.7.1. Во-первых заметим, что bi(s-i) - это множество тех стратегий i-го игрока, которые максимизируют ui(,s-i) на компакте Si. Его непустота следует из непрерывности Ui. Выпуклость множества bi(s-i) следует из квазивогнутости функции ui(-,s_;). Чтобы проверить полунепрерывность сверху, мы должны показать, что для любой последовательности: (sf,s^) - (s;,s_;), такой что sf G bi(s^i)\/k мы имеем Si G 6(s_;). Заметим, что VA; Ui(s^s^) Ui(s",s^) V s" G Si. В силу непрерывности u;(-), u4(s4,s_4) u4(s",s_4).

Доказательство Теоремы. Определим отображение b: S - S формулой 6(si,..., sn) = 6i(s_i) x 62(5-2) x x b(s_n) Ясно, что b() - многозначное отображение S = Si X X Sn в себя. По лемме b() непусто, выпукло-значно, полунепрерывно сверху. Следовательно, по Т. Какутани о неподвижной точке существует неподвижная точка, т. е. набор стратегий s G S: s G b(s).

Этот набор стратегий является равновесием по Нэшу, т.к. по построению Si G bi(s-i) V г = 1,..., п. Справедлива также следующая теорема.

Теорема 1.7.

2 (Glicksberg (1952)). Если в игре Г множества Si стратегий игроков являются непустыми компактными подмножествами метрического пространства, а функции выигрышей Ui непрерывны, то существует равновесие по Нэшу в смешанных стратегиях.

Таким образом, пространство стратегий Si = {А, В, С}. Альтернатива, получившая большинство, побеждает. Если ни одна из альтернатив не получает большинства, то выбирается альтернатива А.

Функции выигрышей таковы:

u1(А) = и2(В) = и3(с) = 2, u1(B) = и2(С) = и3(А) = 1, u1(С) = и2(А) = и3(В) = 0.

В этой игре три равновесных исхода (в чистых стратегиях): А, В и С. Теперь посмотрим на равновесия (их больше 3): если игроки 1 и 3 голосуют за А, то игрок 2 не изменит исход, как бы он ни голосовал, и игроку 3 безразлично, как он голосует. (А, А, А) и (А, В, А) -р.Н., но (А, А, В) -не р.Н., т.к. второму лучше голосовать за В.

Тема 6. Динамические игры с полной информацией

Определение. Графом называется пара (V,E), где V – конечное множество, а ES2(V) (здесь S2(V) обозначает множество неупорядоченных пар элементов множества V). Элементы множества V называют вершинами графа, а элементы множества E – его ребрами. Если v – вершина, а e – ребро, и ve, то говорят, что вершина v и ребро e инцидентны. Если v и w – вершины и {v,w}E, то говорят, что вершины v и w – смежные.

Матрицы смежности и инцидентности Определение. Упорядоченный набор (v1,v2,…,vn) вершин графа называется путем в графе, если вершины vi и vi+1 смежны для любого i=1,…,n–1. Говорят, что путь (v1,v2,…,vn) соединяет вершины v1 и vn. Число n–1 называют длиной пути.

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

Определение. Путь (v1,v2,…,vn) называется простым, если вершины v1,v2,…,vn попарно различны.

Определение. Путь (v1,v2,…,vn) называется циклом, если v1=vn.

Определение. Цикл (v1,v2,…,vn) называется простым, если вершины v1,v2,…,vn–1 попарно различны.

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

Лемма. Если в дереве заданы две вершины, то существует единственных простой путь соединяющий их.

Доказательство. Пусть v и w – две вершины дерева. Так как дерево – связный граф, существует соединяющий их путь. Пусть (v=v1,v2,…,vn=w) кратчайший из таких путей.

Тогда этот путь – простой. Действительно, если vi=vj для некоторого i и некоторого ji, то путь (v1,v2,…,vi,vj+1,vj+2,…,vn) по-прежнему соединяет v и w и имеет меньшую длину, что противоречит выбору исходного пути. Существование доказано.

Докажем единственность. Пусть существуют два различных простых пути (v=v1,v2,…,vn=w) и (v=w1,w2,…,wk=w). Так как они различны, найдется вершина wi, не принадлежащая пути (v=v1,v2,…,vn=w). Пусть j – наименьший номер, такой, что все вершины wj,wj+1,…,wi не принадлежат (v=v1,v2,…,vn=w), а l – наибольший номер, такой, что все вершины wi,wi+1,…,wl не принадлежат (v=v1,v2,…,vn=w). Тогда вершины wi–1 и wl+1 принадлежат пути (v=v1,v2,…,vn=w), то есть wj–1=vp и wl+1=vq для некоторых p и q. Если pq, то путь (vp,wj,…,wl,vq,vq–1,…,vp) будет простым циклом, а если pq, то простым циклом будет путь (vp,wj,…,wl,vq,vq+1,…,vp). В обоих случаях получается противоречие с определением дерева. Лемма доказана.

Определение. Семейство множеств V0,V1,…,Vn называется разбиением множества V, если множества V0,V1,…,Vn попарно не пересекаются, а их объединение равно V.

Определение. Пусть заданы два разбиения V0,V1,…,Vn и W0,W1,…,Wk множества V.

Говорят, что разбиение V0,V1,…,Vn является утончением разбиения W0,W1,…,Wk, если каждое из множеств V0,V1,…,Vn содержится ровно в одном из множеств W0,W1,…,Wk.

Определение. Пусть в дереве отмечена некоторая вершина o. Ребра, инцидентные вершине v и не принадлежащие простому пути, соединяющему v с o, называются альтернативами в вершине v. Все вершины дерева с отмеченной вершиной естественным образом разбиваются на классы в соответствии с количеством альтернатив в них. Это разбиение называется альтернативным. Вершины, в которых нет альтернатив, называются финальными.

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

Лемма. Любое дерево может быть вложено в плоскость.

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

Произвольным образом выберем вершину v0 дерева и отнесем ее классу V0. Для t отнесем к классу Vt те и только те вершины, которые находятся на расстоянии t. Все множество вершин разобьется на конечное число классов.

Введем на плоскости декартовы координаты и положим (v0)=(0,0).

Произвольным образом перенумеруем вершины v1,…,vl множества V1 и положим (vi)=(i,1).

Каждая вершина множества Vt+1 смежна ровно с одной вершиной множества Vt.

Считая, что вершины множества Vt уже перенумерованы, перенумеруем вершины множества Vt+1 так, чтобы выполнялось неравенство ij всякий раз, когда viVt+1, vjVt+1, {vi,vp}E, {vj,vq}E, vpVt, vqVt и pq. Положим (vj)=(j,t), если vjVt.

Построенное отображение удовлетворяет условиям леммы. Если viVt+1, vpVt, vjVr+1, vqVr и tr, то отрезки [(vi),(vp)] и [(vj),(vq)] не пересекаются, так как лежат по разные стороны от прямой y=r, а если t=r, то эти отрезки не пересекаются в силу выбора способа нумерации.

Игры в позиционной форме

Определение. Говорят, что задана игра n лиц в позиционной форме, если заданы:

a) Вложенное в плоскость дерево, называемое деревом игры, с отмеченной вершиной v0 и выделенным ребром, инцидентным этой вершине.

b) Разбиение множества вершин этого дерева на подмножества V0,V1,…,Vn. Это разбиение называется разбиением по игрокам. Элементы множества V0 называются позициями случая, а элементы множества Vi – личными позициями i-го игрока (i=1,…,n).

c) Разбиение множества вершин дерева игры, являющееся утончением, как альтернативного разбиения, так и разбиения по игрокам. Элементы этого разбиения называются информационными множествами.

d) Вероятностное распределение (p1(I),p2(I),…,pm(I)) на множестве {1,…m} для каждого информационного множества I, содержащегося в V0, в вершинах которого имеется m альтернатив.

e) Упорядоченный набор из n чисел, называющихся выигрышами игроков для каждой финальной вершины.

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

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

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

a) Если игра находится в позиции v, принадлежащей множеству V0, то находится реализация j случайной величины, заданной для информационного множества, содержащего вершину v. Находится j-я альтернатива в вершине v, считая против часовой стрелки от единственного ребра, инцидентного вершине v и не являющегося альтернативой (если вершина v – начальная, то отсчет начинается с отмеченного ребра). Далее берется вторая вершина w, инцидентная выбранной альтернативе, и считается, что игра перешла в позицию w.

b) Если игра находится в позиции v, принадлежащей Vi, то выбор альтернативы делает i-ый игрок. При этом он не знает, в какой именно позиции находится игра, но знает информационное множество, которому эта позиция принадлежит. Следовательно, он знает число альтернатив m в позиции v. Он выбирает натуральное число jm.

После этого находится j-я альтернатива в вершине v, считая против часовой стрелки от единственного ребра, инцидентного вершине v и не являющегося альтернативой (если вершина v – начальная, то отсчет начинается с отмеченного ребра). Далее берется вторая вершина w, инцидентная выбранной альтернативе, и считается, что игра перешла в позицию w.

За конечное число таких шагов игра попадет в одну из финальных вершин v, в которой заданы числа (h1(v),h2(v),…,hn(v)). Выигрыш игрока i составит hi(v).

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

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

Пусть iN и W={I1,I2,…,Ik} – семейство всех информационных множеств позиционной игры, содержащихся в множестве Vi. Будем считать, что Ui есть множество всех функций ui, отображающих W в и удовлетворяющих следующему условию: число i u (I) не превосходит количества альтернатив в любой вершине из множества I.

Стратегия ui задает вероятностное распределение (p1(v),p2(v),…,pm(v)) на множестве 1, если v I и u i (I) j, всех альтернатив в вершине v по следующему правилу: p j (v) В 0 в противном случае.

позициях случая также задается вероятностное распределение (p1(v),p2(v),…,pm(v)) на множестве альтернатив условием pj(v)=pj(I), если jI.

Для каждой финальной вершины w определен единственный путь (v0,v1,…,vk=w), соединяющий ее с начальной вершиной v0 и числа qt (t=0,…,k–1), равные pj(vt), где j номер k альтернативы {vt,vt+1} в вершине vt. Положим P (w) qt. Непосредственно проверяется, t 0 что величины P(w) задают вероятностное распределение на множестве финальных вершин. Таким образом, величины hi(w) можно считать случайными, причем распределения этих величин зависят от стратегий всех игроков. Обозначим gi(u1,u2,…,un) математическое ожидание величины hi при условии, что игроки выбрали стратегии u1,u2,…,un соответственно.

Определение. Построенная таким образом игра Г=N,U1,…,Un,g1,…,gn называется нормальной формой данной позиционной игры.

Пример: Фан-тан С помощью этой конструкции на класс позиционных игр переносятся понятия седловой точки, смешанной стратегии, равновесия по Нэшу и т. д.

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

Определение. Позиционная игра n лиц называется игрой с полной информацией, если все ее информационные множества содержат ровно по одному элементу.

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

Шахматы, шашки и нарды являются играми с полной информацией, а покер и преферанс – нет.

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

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

Лемма. В классе существует единственная игра с полной информацией. Она является квазиинформационным расширением любой игры класса.

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

Потеря структуры при переходе к нормальной форме Совершенное равновесие в динамических играх Теорема. Во всякой игре с полной информацией существует ситуация равновесия по Нэшу.

Доказательство. Для каждой вершины v дерева игры определим набор чисел (h (v),h2(v),…,hn(v)) и для каждой нефинальной личной позиции v i-го игрока определим

–  –  –

игры. Вновь индукцией «с конца» доказывается, что hi(vk)hi(vl). Из неравенств hi(vk)hi(v0) следует, что построенная ситуация u – ситуация равновесия. Теорема доказана.

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

Пусть v – произвольная вершина дерева игры и V(v) – это множество всех вершин w, для которых существует такой набор (v=v1,v2,…,vk=w), что для всех j=1,…,k–1 {vk,vk+1} есть альтернатива в вершине vk. Очевидно, V(v0)=V.

Дерево подыгры с вершиной v имеет множество вершин V(v). Его ребрами являются все ребра исходной игры, обе вершины которой принадлежат V(v). Разбиение по игрокам в подыгре есть V 0 V (v), V 1 V (v),..., V n V (v), а всякое информационное множество в подыгре имеет вид V (v) I, где I – некоторое информационное множество в исходной игре. Выигрыши игроков (h1(w),h2(w),…,hn(w)) в любой финальной вершине w подыгры и вероятности (p1(w),…,pm(w)) в любой позиции w случая в подыгре те же, что в исходной игре. Начальной позицией подыгры является вершина v, а отмеченным ребром – первая альтернатива в этой вершине, считая против часовой стрелки от ребра, не являющегося альтернативой.

Непосредственно проверяется, что так определенная подыгра сама является позиционной игрой n лиц.

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

Если ui – любая стратегия в исходной игре, то ограничение функции ui на множество V i V (v) будет стратегией того же игрока в подыгре.

Определение. Ситуация u в позиционной игре называется ситуацией совершенного равновесия, если для любой вершины v дерева игры ограничения стратегий ui образуют ситуацию равновесия по Нэшу в подыгре с начальной вершиной v.

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

Тема 7. Статические игры с неполной информацией

Рассмотрим дуополию Курно для рынка с обратной функцией спроса P(Q)=a-Q, где Q=q1+q2 – общий спрос на рынке. Обе фирмы имеют одинаковые функции затрат ci(qi)=cqi, но спрос является неопределенным: высоким (a=aH) с вероятностью или низким (a=aL) с вероятность 1-. Информация асимметрична: фирма 1 знает, какой спрос (высокий или низкий), а вторая фирма нет. Все описание ситуации общеизвестно. Обе фирмы выбирают размер выпуска одновременно. Каково множество стратегий для каждой фирмы? Предположите, что параметры aH, aL, и c таковы, что равновесные выпуски положительны. Найдите равновесие Байеса-Нэша в этой игре.

Рассмотрим дуополию Бертрана с асимметричной информацией и различающейся продукцией. Спрос на продукцию фирмы равен i qi(pi,pj)=a-pi-bipj. Затраты будем считать равными нулю для обеих фирм. Чувствительность спроса фирмы i к цене фирмы j может быть высокой или низкой. Точнее, для каждой фирмы величина bi может принимать значение bH с вероятностью и bL – с вероятностью 1-. Каждая фирма знает свою чувствительность, но не знает чувствительность конкурента. Это описание общеизвестно. Каковы множества действий, типов, ожиданий и функции полезности для данной игры? Каковы множества стратегий? При каких условиях в этой игре существует симметричное равновесие Байеса-Нэша в чистых стратегиях?

Найдите это равновесие.

Найдите все равновесия Байеса-Нэша в чистых стратегиях в следующей игре:

1. Природа с равной вероятностью выбирает Игру 1 или Игру 2, которые отличаются только выигрышами.

2. Игрок 1 узнает выбор Природы, а игрок 2 нет.

3. Игроки одновременно выбирают свои действия.

4. Выигрыши определяются следующими матрицами L R L R T 1,1 0,0 T 0,0 0,0 B 0,0 0,0 B 0,0 2,2 Игра 1 Игра 2 Вспомним, что следующая игра с угадыванием монеты (статическая игра с полной информацией) не имела равновесия Нэша в чистых стратегиях, но обладала единственным равновесием в смешанных стратегиях, в котором каждый игрок выбирал О c вероятностью:

Игрок 2 О Р Игрок 1 О 1,-1 -1,1 Р -1,1 1,-1 Постройте соответствующую игру с неполной информацией, в которой равновесие Байеса-Нэша в чистых стратегиях превращается в равновесие Нэша в смешанных стратегиях по мере того, как неполнота информации исчезает.

Рассмотрите аукцион с закрытыми ставками по первой цене, в котором оценки покупателей независимы и одинаково равномерно распределены на отрезке .

Покажите, что если число покупателей равно n, то заявки по цене (n-1)/n от индивидуальной оценки стоимости составляют равновесие Байеса-Нэша для этого аукциона.

Рассмотрите аукцион с закрытыми ставками по первой цене, в котором оценки покупателей независимы и одинаково распределены на отрезке с положительной функцией плотности f(vi). Найдите симметричное равновесие Байеса-Нэша для случая двух участников.

Рассмотрим другую интерпретацию двойного аукциона. Пусть имеется фирма и работник, причем фирма знает, какой у нее выигрыш m от деятельности работника на данной позиции, а рабочий знает свои альтернативные возможности v. Сделка означает, что работник принимается на работу, а цена сделки равна его зарплате w. Если сделка заключена, то фирма выигрывает m-w, а работник – w. Если нет сделки, то выигрыш фирмы равен нулю, а работника – v.

Предположим, что m и v распределены независимо и равномерно на отрезке .

Найдите линейное равновесие в этом двойном аукционе.

Рассмотрим две других торговых игры в качестве альтернативы двойного аукциона.

Игра 1. Перед тем, как стороны получают приватную информацию, они подписывают контракт о том, что фирма нанимает работника с зарплатой w, но любая из сторон имеет право выйти из трудового соглашения без каких-либо затрат.

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

Игра 2. Перед получением приватной информации оба игрока подписывают контракт:

будет ли работник нанят и если будет, то на какую зарплату, определяется в рамках следующей динамической игры. После получения приватной информации фирма выбирает уровень зарплаты w и предлагает ее работнику, который может согласиться или отказаться. Попробуйте проанализировать эту игру методом обратной индукции. Что будет делать работник при заданных v и w? Если фирма предвидит действия работника в ответ на ее предложение, то что она будет предлагать при заданном m.

Тема 8. Динамические игры с неполной информацией, элементы эволюционной теории игр Рассмотрим две приведенные таблицы, игровой смысл которых состоит в следующем.

У первого игрока (игрок 1) есть возможность выбрать либо стратегию (ход) u (первая строка), либо стратегию d (вторая строка). Второй игрок (игрок 2) может выбрать либо стратегию l (первый столбец), либо стратегию r (второй столбец). Они делают свои ходы одновременно и независимо. После этого они получают свои выигрыши, которые указаны в соответствующих клетках: если, например, игрок 1 выбрал u, а игрок 2 выбрал r, то в случае А оба они получат по 2 рубля (доллара, фунта,...), а в случае В - первый получит - 5, а второй - 4.

В случае А, по-видимому, совершенно очевидно, что "играть" надо левую нижнюю клетку (т.е. выбирать, соответственно, d и l), тогда как совершенно не понятно, что нужно играть во втором случае. И одна из возможностей состоит в разрешении предварительных переговоров. Но если бы понятие равновесия по Нэшу можно было оправдать, апеллируя только к предварительным переговорам, то значение этого понятия было бы достаточно низким, поскольку центральным становился бы вопрос о "силе договоренности". Однако "оправдание" равновесия по Нэшу исходит из ряда других соображений, на которых мы остановимся, в частности, в главе 1. Мы не будем пытаться приводить сложные модели, а лишь упомянем некоторые возможные приложения. Рассмотрим следующую игру Ситуации подобного рода достаточно часто возникают в экономических рассмотрениях. Представим себе, например, две фирмы, продающие один и тот же (точнее, однородный) продукт. Каждая из фирм может рекламировать свой товар, скажем предлагая его на распродаже, что может увеличить ее прибыль и уменьшить прибыль конкурента, при данном фиксированном способе действия конкурента. Если обе фирмы рекламируют, то чистая прибыль каждого из конкурентов может уменьшиться. (Пример такого рода ситуации дает конкуренция между Airbus и Boeing. Хотя реклама в этом случае не была существенным элементом, в то же время ценовые уступки играли важную роль). Второго рода пример - две страны, являющиеся торговыми партнерами. Каждая из стран может использовать различные виды протекционистских мер, что в ряде случаев может приводить к выгоде своей страны, при данных фиксированных действиях второй страны. Если обе страны занимаются протекционистской политикой, общее благосостояние стран может снижаться.

В этом примере (мы впоследствии будем неоднократно возвращаться к такого типа игре) равновесие по Нэшу определяется стратегией d первого игрока и r - второго игрока. Действительно, если первый игрок выбрал стратегию d, то второму игроку невыгодно отклоняться от стратегии r, так как он вместо 0 получит выигрыш - 1.

Аналогично, если второй игрок придерживается стратегии r, то первому невыгодно вместо d играть u, так как он также вместо 0 проиграет 1.

В тоже время "хорошая" ситуация (u, l), когда игрок 1 выбирает u, а второй - l, не является ситуацией равновесия по Нэшу, так как, например, игроку 1 выгодно (при условии, что второй играет l) отклониться от a и сыграть d, поскольку вместо 5 он выиграет 6.

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

Безусловно, следует специально подчеркнуть, что большая роль теории игр в экономике во многом объясняется тем, что теория игр дает язык для моделирования и технику анализа специфического динамического конкурентного взаимодействия. Скажем, в достаточно простом варианте это можно проиллюстрировать на следующем примере (см., Kreps (1990)). Представим себе монополиста (в классическом смысле), производящего некоторый товар для продажи. Для простоты будем считать, что спрос определяется кривой х = 13 р. Структура затрат монополиста также весьма проста: с(х) = 6.25 + х. Стандартная теория предсказывает, что монополист, максимизирующий прибыль, будет выпускать 6 единиц готовой продукции и получит прибыль 29.75 (при цене 7). В то же время, если в данной ситуации рассмотреть возможность входа новичка (с такими же характеристиками), то ответ будет уже совершенно другим: укоренившийся монополист, предвидящий возможность входа, будет производить 7 единиц готового продукта (при цене 6), теряя несколько в прибыли в данном периоде, но обеспечивая себе большую прибыль в длительном периоде, поскольку новичок, считающий, что укоренившаяся фирма будет продолжать выпускать тот же объем продукции, воздержится от входа, так как его вход принесет ему нулевую прибыль.

Разумеется, здесь возникает, например, такой вопрос. А почему собственно новичок должен верить в то, что монополист будет продолжать выпускать такой-то объем готовой продукции, если новичок все-таки "осмелится" войти в отрасль? Этот вопрос, безусловно, существенен для этой истории. Хотя простейшая модель не дает ответа на этот вопрос, тем не менее, более сложные модели входа со сложной динамикой, которые используют многошаговые игры, уже позволяют анализировать ситуации входа с различными гипотезами о поведении агентов. Скажем, если мы будем рассматривать двухпериодную модель, то уже появляется возможность рассматривать более сложное поведение.

Например, возможен вариант, когда монополист в первом периоде выбирает технологию.

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

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

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

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

Следующий классический пример, связанный с повторяющимся взаимодействием участников - неявный сговор в олигополии. Он базируется на так называемой Folk Theorem ("народной теореме", "фольклорной теореме" - см. гл.2), которая утверждает, что любые выигрыши двух фирм, которые дают каждой из фирм больше максиминного выигрыша и в сумме меньше, чем монопольная прибыль (за период) может поддерживаться в равновесии, если будущее ценится фирмами достаточно высоко. Как и во многих случаях, здесь возникает неприятный момент множественности равновесия, который, увы, оказывается весьма существенным и вынуждает пытаться вводить различные модификации равновесия по Нэшу.

Равновесия по Нэшу - это "согласованные" предсказания того, как игра будет разыгрываться, в том смысле, что если все игроки предсказывают, что возникнет определенное равновесие, то ни у одного из игроков не будет стимулов для отклонения.

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

4. В то самое время, когда теория бескоалиционных игр становится стандартным инструментом в экономике, она подвергается значительной критике со стороны как теоретиков так и экспериментаторов. Бескоалиционная теория игр, подобно неоклассической экономике, базируется на двух "героических" предположениях:

МАКСИМИЗАЦИИ (каждый экономический агент рационален и ясно представляет себе мир); и СОГЛАСОВАННОСТИ (представления агента, и, в частности, его ожидания относительно поведения остальных агентов правильны). Эти два предположения, по сути дела и оправдывают то, что общие образцы индивидуального оптимизирующего поведения формируют равновесие по Нэшу.

Основная проблема, с которой в настоящее время столкнулись теоретики - это проблема "неотразимого" обоснования этих двух предположений, ибо традиционные обоснования отнюдь не являются неотразимыми. В то же время без такого обоснования использование теории игр в приложениях становится проблематичным. Использование теории игр требует понимания того, когда эти предположения осмысленны, а в каких случаях - нет. Основной упрек, часто адресуемый экономической методологии, касается центральной роли гипотезы максимизации. Общий неформальный аргумент в пользу максимизации состоит в том, что любой не максимизирующий агент, и в частности, любая фирма, не максимизирующая прибыль, будет выдавлена рыночными силами. Это эволюционный аргумент, и как таковой, хорошо известен. Однако, работает ли такое оправдание? Является ли равновесие по Нэшу, или какое-либо связанное с ним понятие, хорошим предсказанием?

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

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

В настоящее время очень стремительно развивается эволюционная теория игр.

Большинство работ по эволюционной теории игр мотивированы двумя основными вопросами: 1. Действительно ли агенты играют равновесие по Нэшу? 2.Если агенты играют равновесие по Нэшу, то какое?

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

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

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

Эволюционная теория игр дает положительный ответ на первый вопрос: во многих постановках игроки действительно играют равновесие по Нэшу. Таким образом, это дает оправдание равновесного анализа тогда, когда осмысленны эволюционные аргументы.

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

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

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

Оправдание с помощью "фокальной точки" (Т. Шеллинг) можно формулировать примерно так: "если есть очевидный путь играть в игре (либо в силу специфики постановки, либо в силу специальной структуры), то игроки будут знать, что будут делать другие игроки".

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

АСПЕКТ Аннотация. Актуальность и цели. Предмет исследования – влияние интернет-коммуникаций на формирование интернет-зависимости. Вопросы психологической природы и...» "Кемеровский государственный университе...»

«РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ РЕГИСТРАТОР ДОМОВОЙ ТУ 4372001864198722009 на базе системы "Интеллект видео" Москва 2009 Регистратор домовой "Комплекс". Руководство пользователя. Оглавление РЕГИСТРАТОР ДОМОВОЙ 1. Общее описание 2. Меры безопасности 3. Установка 3.1 Мон...»

« Сохраните руководство для будущего использования. Благодарим Вас за выбор интеллектуальной MIDI-клавиатуры UF v2 Запишите всю важную информацию здесь Прик...»

«УДК 159.9:371.39:004 Казарова Диана Сергеевна Kazarova Diana Sеrgeevna кандидат психологических наук, доцент кафедры PhD in Psychology, Assistant Professor, гуманитарных и естественнонаучных дисциплин Humanities and Natural Sciences Department, Липецкого филиала Российской академии Lipetsk branc...» – С. 12-18. Научно доказан тот факт, что первые знания о законах и явлениях жизни человек получает из сказок, притч, легенд...» ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ (12) ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ПАТЕНТУ (21)(22) Заявка: 2010135778/13, 26.01.2009 (72) Автор(ы): ЛУКОМИТРОС Ди...»

1. Бузуверова Н.В., Дьяченко М.Е. Отечественная история: вопросы и ответы. Учебное пособие. Магнитогорск: ГОУ ВПО «МГТУ», 2006.

2. Мунчаев Ш.М., Устинов В.М. История России. Учебник для вузов. М., 2005.

3. История России с древнейших времен до конца XX в.: Учебное пособие для студентов вузов. М., 2007.

4. _______________________________________________________________________

5. _______________________________________________________________________

Уважаемые студенты.

Вам нужно прочитать лекции, разобраться в них и выполнить задания-примеры (стр. 17) в EXCEL. Это и будет Ваша контрольная работа. Результаты оформить как обычную контрольную с выводом рабочих листов на бумажный носитель (изменить размер и типы шрифта). Каждый будет защищать свою контрольную индивидуально. Можно сбросить программы с решением на флешку.

ЛЕКЦИИ ПО ТЕОРИИ ИГР

Теория игр в контексте теории принятия решений

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

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

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

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

Ситуации риска сопутствуют три условия:

· наличие неопределенности;

· необходимость выбора альтернативы;

· возможность оценить вероятность осуществления выбираемых альтернатив.

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

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

Существуют различные виды неопределенности, в частности:

· количественная, обусловленная значительным числом объектов или элементов в ситуации;

· информационная, вызванная недостатком информации или ее неточностью по техническим, социальным и другим причинам;

· стоимостная из-за слишком дорогой или недоступной платы за определенность;

· профессиональная как следствие недостаточного профессионализма ЛПР (не учитывается, например, требуемое количество влияющих факторов);

· ограничительная (вызванная ограничениями в ситуации принятия решений, например ограничения по времени и др.);

· внешней среды, связанная с поведением среды или реакцией конкурента на процесс принятия решения.

Природа риска в рыночной экономике обусловлена следующими факторами:

· ограниченной сферой государственного регулирования хозяйственной деятельности;

· усилением роли случайных факторов во взаимодействии предприятия с внешней средой;

· частной (и ее видами) собственностью предпринимателя, ее владением, пользованием, распоряжением;

· конкурентной борьбой товаропроизводителей и других хозяйствующих субъектов;

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

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

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

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

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

Уровень имеющейся информации о проблеме определяет, каким образом может быть формализована и решена задача принятия решения.

При решении задач в условиях неопределенности внешней среды наиболее часто возникают две ситуации. При первой сама система препятствует принятию решений (задачи “природной неопределенности” – например, задача производства сельскохозяйственной продукции на некоторой территории, когда неизвестны погодные условия предстоящего сезона). В этой ситуации природа может рассматриваться как доброжелательный противник, в том смысле, что она не преследует целей, противоположных целям человека.

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

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

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

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

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

· выбор образа действия игроков на каждом этапе игры;

· информацию, которой обладает каждый игрок при осуществлении таких выборов;

· плату для каждого игрока после завершения любого этапа игры.

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

К числу определяющих характеристик игр можно отнести следующие:

· имеется конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают;

· сформулированы правила выбора допустимых стратегий, известные игрокам;

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

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

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

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

Б) В зависимости от взаимоотношений участников различают бескоалиционные (участники не имеют права заключать соглашения) и коалиционные игры (иногда используются синонимы – некооперативные и кооперативные игры соответственно).

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

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

Д) По количеству ходов игры делятся на одноходовые (выигрыш распределяется после одного хода каждого игрока) и многоходовые (выигрыш распределяется после нескольких ходов).

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

В дальнейшем мы ограничимся рассмотрением парных матричных игр с нулевой суммой. Задание стратегий двух игроков в парной игре такого типа полностью определяет ее исход, т.е. выигрыш одного или проигрыш другого. Как уже отмечалось, результаты конечной парной игры с нулевой суммой можно задавать матрицей, строки и столбцы которой соответствуют различным стратегиям 1-го и 2-го игроков соответственно, а ее элементы - выигрышам одной стороны (равные проигрышам другой). Эта матрица называется платежной матрицей или матрицей игры.

теории игр , были сделаны биологами, рассматривавшими теорию естественного отбора и поведения животных; поведение было, разумеется, эгоистическим. Классический труд Рональда Фишера содержит многие методы теории игр , а уже после математического оформления этой теории эстафету принял Джон Майнард Смит . Математически же теорию игр оформил Джон фон Нейман: сначала в статьях 1920-х годов , а затем в книге с Оскаром Моргенштерном , с которой, наверное, и нужно вести историю теории игр как развитого математического аппарата. Учебники по теории игр мы здесь пересказывать не будем, цель этой книги совершенно другая; мы просто изложим вкратце некоторые вещи из теории игр , без которых нам совсем уж не обойтись. А если читатель заинтересуется теорией игр всерьез, рекомендуем ему учебники [ , , , , ].

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

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

Определение 1.1 .Стратегическая игра - это тройка

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

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

Есть и еще одно важное замечание: в течение этой лекции мы предполагаем, что у участников есть предпочтения по поводу исходов игры и эти предпочтения можно выразить при помощи функций . Это далеко не всегда так, и в "Теоремы Эрроу и Гиббарда-Саттертуэйта" мы еще поговорим об интересных эффектах, возникающих, когда предпочтения так выразить нельзя. Но для базовой теории игр придется это предположение все-таки сделать.

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

Пример 1.1 . Первый пример возьмем совсем уж из детства - рассмотрим классическую игру "камень-ножницы-бумага" 2Хотя насчет детства еще можно поспорить: в США вот недавно появилась аж целая ассоциация, посвященная игре в " Rock , Paper , Scissors " под логичным названием USARPS. Призы неплохие - можете попробовать свои силы на сайте http://www.usarps.com/ . . Камень побеждает ножницы, ножницы побеждают бумагу, бумага - камень. У игры получается вот какая матрица (где означает победу того игрока, чьи стратегии выписаны слева, а - победу игрока, стратегии которого стоят в первой строке):

Конец примера 1.1 .

Пример 1.2 . В качестве второго примера рассмотрим классическую игру полковника Блотто [ , ]. Полковник Блотто должен распределить свои силы ( солдат) между несколькими участками поля боя ( участков). Его противник должен сделать то же самое (количество его солдат может отличаться). Выигрывает тот, кто победит на большем количестве участков боя.

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

(3,0,0), (2,1,0), (2,0,1), (1,2,0), (1,1,1), (1,0,2), (0,3,0), (0,2,1), (0,1,2), (0,0,3).

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

Конец примера 1.2 .

Отметим, что в играх из примеров 1.1 и 1.2 прибыль одного участника строго равнялась убытку второго. Такие игры называются играми с нулевой суммой ; формально говоря, в таких играх для любого профиля действий участников верно, что .

В дальнейшем нас будут интересовать не только игры с конечными множествами стратегий, но и игры с непрерывными такими множествами. Возьмем классический пример - конкуренцию по Курно (Cournot competition) 3Этот пример действительно восходит к классику экономической теории Антуану Огюстену Курно .

Рис. 1.1.

Пример 1.3 . Рассмотрим рынок некоего продукта, на котором находятся ровно две фирмы: . Стратегия каждого из участников - количество продукта, которое он производит: .

→

Лекция 11: Теория игр и принятие решений

Предмет и задачи теории игр

Классическими задачами системного анализа являются игровые задачи принятия решений в условиях риска и неопределенности.

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

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

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

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

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

Ход — выбор одного из предусмотренных правилами игры действий и его осуществление. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор игроком одного из возможных вариантов действий и его осуществление. Случайным ходом называется выбор из ряда возможностей, осуществляемый не решением игрока, а каким-либомеханизмом случайного выбора (бросание монеты, выбор карты из перетасованной колоды и т. п.). Для каждого случайного хода правила игры определяют распределение вероятностей возможных исходов. Игра может состоять только их личных или только из случайных ходов, или из их комбинации. Следующим основным понятием теории игр является понятие стратегии. Стратегия — это априори принятая игроком система решений (вида «если — то»), которых он придерживается во время ведения игры, которая может быть представлена в виде алгоритма и выполняться автоматически.

Целью теории игр является выработка рекомендаций для разумного поведения игроков в конфликтной ситуации, т. е. определение «оптимальной стратегии» для каждого из них. Стратегия, оптимальная по одному показателю, необязательно будет оптимальной по другим. Сознавая эти ограничения и поэтому не придерживаясь слепо рекомендаций, полученных игровыми методами, можно все же разумно использовать математический аппарат теории игр для выработки, если не в точности оптимальной, то, во всяком случае «приемлемой» стратегии.

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

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

В зависимости от числа возможных стратегий игры делятся на «конечные » и «бесконечные ».

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

По характеру взаимодействия игры делятся на бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции; коалиционные (кооперативные) — могут вступать в коалиции.

В кооперативных играх коалиции заранее определены.

По характеру выигрышей игры делятся на: игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой.

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

Матричная игра — это конечная игра двух игроков с нулевой суммой, в которой задается выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец — номеру применяемой стратегии игрока на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

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

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

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

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

Запись матричной игры в виде платежной матрицы

Рассмотрим конечную игру, в которой первый игрок А имеет m стратегий, а второй игрок B-n стратегий. Такая игра называется игрой m×n. Обозначим стратегии A 1 , А 2 , ..., А m ; и В 1 , В 2 , ..., В n . Предположим, что каждая сторона выбрала определенную стратегию: A i или B j . Если игра состоит только из личных ходов, то выбор стратегий однозначно определяет исход игры — выигрыш одной из сторон a ij . Если игра содержит кроме личных случайные ходы, то выигрыш при паре стратегий A i и B является случайной величиной, зависящей от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша, которое также обозначается за a ij .

Предположим, что нам известны значения a ij при каждой паре стратегий. Эти значения можно записать в виде прямоугольной таблицы (матрицы), строки которой соответствуют стратегиям A i , а столбцы — стратегиям B j .

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

	B 1	B 2	...	B n
A 1	a 11	a 12	...	a 1n
A 2	a 21	a 22	...	a 2n
...	...	...	...	...
A m	a m1	a m2	...	a mn

Таблица — Общий вид платежной матрицы матричной игры

где A i — названия стратегий игрока 1, B j — названия стратегий игрока 2, a ij — значения выигрышей игрока 1 при выборе им i–й стратегии, а игроком 2 — j-й стратегии. Поскольку данная игра является игрой с нулевой суммой, значение выигрыша для игрока 2 является величиной, противоположенной по знаку значению выигрыша игрока 1.

Понятие о нижней и верхней цене игры. Решение игры в чистых стратегиях

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

V н = max i min j a ij

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

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

Величина выигрыша игрока 1 равна, по определению матричной игры, величине проигрыша игрока Поэтому для игрока 2 необходимо определить значение

V в = min j max i a ij

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

В случае, если значения V н и V в не совпадают, при сохранении правил игры (коэффициентов a ij) в длительной перспективе, выбор стратегий каждым из игроков оказывается неустойчивым. Устойчивость он приобретает лишь при равенстве V н = V в = V. В этом случае говорят, что игра имеет решение в чистых стратегиях , а стратегии, в которых достигается V — оптимальными чистыми стратегиями . Величина V называется чистой ценой игры .

Например, в матрице:

	B 1	B 2	B 3	B 4	Min j
A 1	17	16	15	14	14
A 2	11	18	12	13	11
A 3	18	11	13	12	11
Max i	18	18	15	14

Таблица — Платежная матрица, в которой существует решение в чистых стратегиях

существует решение в чистых стратегиях. При этом для игрока 1 оптимальной чистой стратегией будет стратегия A 1 , а для игрока 2 — стратегия B 4 .

В матрице решения в чистых стратегиях не существует, так как нижняя цена игры достигается в стратегии A 1 и ее значение равно 12, в то время как верхняя цена игры достигается в стратегии B 4 и ее значение равно 13.

	B 1	B 2	B 3	B 4	Min j
A 1	17	16	15	12	12
A 2	11	18	12	13	11
A 3	18	11	13	12	11
Max i	18	18	15	13

Таблица — Платежная матрица, в которой не существует решения в чистых стратегиях

Уменьшение порядка платежной матрицы

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

Стратегия K* называется доминируемой стратегией K**, если при любом варианте поведения противодействующего игрока выполняется соотношение

A k* < A k** ,

где A k* и A k** — значения выигрышей при выборе игроком, соответственно, стратегий K* и K**.

В случае, если выполняется соотношение

стратегия K* называется дублирующей по отношению к стратегии K**.

Например, в матрице с доминируемыми и дублирующими стратегиями стратегия A 1 является доминируемой по отношению к стратегии A 2 , стратегия B 6 является доминируемой по отношению к стратегиям B 3 , B 4 и B 5 , а стратегия B 5 является дублирующей по отношению к стратегии B 4 .

	B 1	B 2	B 3	B 4	B 5	B 6
A 1	1	2	3	4	4	7
A 2	7	6	5	4	4	8
A 3	1	8	2	3	3	6
A 4	8	1	3	2	2	5

Таблица — Платежная матрица с доминируемыми и дублирующими стратегиями

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

Множество недоминируемых стратегий, полученных после уменьшения размерности платежной матрицы, называется еще множеством Парето.

Примеры игр

1. Игра «Цыпленок»

Игра «Цыпленок» заключается в том, что игроки вступают во взаимодействие, которое ведет в нанесению серьезного вреда каждому из них, пока один из игроков не выйдет из игры. Пример использования этой игры — взаимодействие автотранспортный средств, например, ситуации, когда два автомобиля идут навстречу друг другу, и тот, который первым сворачивает в сторону, считается «слабаком» или «цыпленком». Смысл игры заключается в создании напряжения, которое бы привело к устранению игрока. Подобная ситуация часто встречается в среде подростков или агрессивно настроенных молодых людей, хотя иногда несет в себе меньший риск. Еще одно из применений этой игры — ситуация, в которой две политические партии вступают в контакт, при котором они не могут ничего выиграть, и только гордость заставляет их сохранять противостояние. Партии медлят с уступками до тех пор, пока не дойдут до финальной точки. Возникающее психологическое напряжение может привести одного из игроков к неправильной стратегии поведения: если никто из игроков не уступает, то столкновение и фатальная развязка неизбежны.

Платежная матрица игры выглядит следующей:

	Уступить	Не уступать
Уступить	0, 0	-1, +1
Не уступать	+1, -1	-100, -100

2. Игра «коршун и голубь»

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

Здесь V — цена соглашения, C — цена конфликта, причем V

В игре «коршун и голубь» есть три точки равновесия по Нэшу:

1. первый игрок выбирает «коршуна», а второй «голубя».
2. первый игрок выбирает «голубя», а второй «коршуна».
3. оба игрока выбирают смешанную стратегию, в которой «коршун» выбирается с вероятностью p, а «голубь» — с вероятностью 1-p.

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

«Дилемма заключенного» — одна из наиболее распространенных конфликтных ситуаций, рассматриваемая в теории игр.

Классическая «дилемма заключенного» звучит следующим образом: двое подозреваемых, A и B, находятся в разных камерах. Следователь, навещая их поодиночке, предлагает сделку следующего содержания: если один из них будет свидетельствовать против другого, а второй будет молчать, то первый заключенный будет освобожден, а второго осудят на 10 лет. Если оба будут молчать, то отсидят по 6 месяцев. Если оба предадут друг друга, то каждый получит по 2 года. Каждый из заключенных должен принять решение: предать подельника или молчать, не зная о том, какое решение принял другой. Дилемма: какое решение примут заключенные?

Платежная матрица игры:

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

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

Проанализируем «дилемму заключенного», перейдя для наглядности к платежной матрице канонического вида:

—	Кооперация	Отказ от кооперации
Кооперация	3, 3	0, 5
Отказ от кооперации	5, 0	1, 1

Согласно этой матрице, цена взаимного отказа от кооперации (S) составляет по 1 баллу для каждого из игроков, цена за кооперацию (R) — по 3 балла, а цена соблазна предать другого (T) составляет 5 баллов. Можем записать следующее неравенство: T > R > S. При повторении игры несколько раз, выбор кооперации превосходит соблазн предать и получить максимальный выигрыш: 2 R > T + S.

Равновесие по Нэшу.

Равновесие по Нэшу — это ситуация, когда ни у одного игрока нет стимулов изменять свою стратегию при данной стратегии другого игрока (другой фирмы), позволяющая игрокам достичь компромиссного решения.

Определение равновесия по Нэшу и его существование определяется следующим образом.

Пусть (S, f) — это игра, в которой S — множество стратегий, f — множество выигрышей. Когда каждый из игроков i ∈ {1, ..., n} выбирает стратегию x i &isin S, где x = (x 1 , ..., x n), тогда игрок i получает выигрыш f i (x). Выигрыш зависит от стратегии, выбранной всеми игроками. Стратегия x* ∈ S является равновесием по Нэшу, если никакое отклонение от нее каким-то одним игроком не приносит ему прибыль, то есть, для всех i выполняется следующее неравенство:

f i (x*) ≥ f i (x i , x* -i)

Например, игра «дилемма заключенного» имеет одно равновесие по Нэшу — ситуацию, когда оба заключенных предают друг друга.

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

Например, применим это правило для матрицы 3x3:

	A	B	C
A	0, 0	25, 40	5, 10
B	40, 25	0, 0	5, 15
C	10, 5	15, 5	10, 10

Точки равновесия по Нэшу: (B,A), (A,B) и (C,C). Indeed, for cell (B,A), так как 40 — максимальное значение в первом столбце, 25 максимальное значение во втором ряду. Для ячейки (A,B) 25 — это максимальное значение во втором столбце, 40 — максимальное значение во втором ряду. То же самое и для ячейки (C,C).

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

	Фирма 1
Фирма 2	Низкий уровень загрязнения	Высокий уровень загрязнения
Низкий уровень загрязнения	А 100,100	В -30,120
Высокий уровень загрязнения	С 120,-30	D 100,100

Таблица — Платежная матрица игры в загрязнение окружающей среды.

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

Игры загрязнения - один из случаев того, как механизм действия «невидимой руки» не срабатывает. Это ситуация, когда равновесие по Нэшу неэффективно. Иногда подобные неконтролируемые игры становятся угрожающими, и здесь может вмешаться правительство. Установив систему штрафов и квот на выбросы, правительство может побудить фирмы выбрать исход А, соответствующий низкому уровню загрязнения. Фирмы зарабатывают ровно столько же, сколько и прежде, при больших выбросах, мир же становится несколько чище.

Пример решения матричной игры в чистых стратегиях

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

Задача.

Два предприятия производят продукцию и поставляют ее на рынок региона. Они являются единственными поставщиками продукции в регион, поэтому полностью определяют рынок данной продукции в регионе.

Каждое из предприятий имеет возможность производить продукцию с применением одной из трех различных технологий. В зависимости от экологичности технологического процесса и качества продукции, произведенной по каждой технологии, предприятия могут установить цену единицы продукции на уровне 10, 6 и 2 денежных единиц соответственно. При этом предприятия имеют различные затраты на производство единицы продукции.

Таблица — Затраты на единицу продукции, произведенной на предприятиях региона (д.е.).

В результате маркетингового исследования рынка продукции региона была определена функция спроса на продукцию:

Y = 6 - 0.5⋅X,

где Y — количество продукции, которое приобретет население региона (тыс. ед.), а X — средняя цена продукции предприятий, д.е.

Данные о спросе на продукцию в зависимости от цен реализации приведены в таблице:

Цена реализации 1 ед. продукции, д.е.		Средняя цена реализации 1 ед. продукции, д.е.	Спрос на продукцию, тыс. ед.
Предприятие 1	Предприятие 2
10	10	10	1
10	6	8	2
10	2	6	3
6	10	8	2
6	6	6	3
6	2	4	4
2	10	6	3
2	6	4	4
2	2	2	5

Таблица — Спрос на продукцию в регионе, тыс. ед.

Значения Долей продукции предприятия 1, приобретенной населением, зависят от соотношения цен на продукцию предприятия 1 и предприятия В результате маркетингового исследования эта зависимость установлена и значения вычислены:

Таблица — Доля продукции предприятия 1, приобретаемой населением в зависимости от соотношения цен на продукцию

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

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

1. Существует ли в данной задаче ситуация равновесия при выборе технологий производства продукции обоими предприятиями?
2. Существуют ли технологии, которые предприятия заведомо не будут выбирать вследствие невыгодности?
3. Сколько продукции будет реализовано в ситуации равновесия? Какое предприятие окажется в выигрышном положении?

Решение задачи

1. Определим экономический смысл коэффициентов выигрышей в платежной матрице задачи. Каждое предприятие стремится к максимизации прибыли от производства продукции. Но кроме того, в данном случае предприятия ведут борьбу за рынок продукции в регионе. При этом выигрыш одного предприятия означает проигрыш другого. Такая задача может быть сведена к матричной игре с нулевой суммой. При этом коэффициентами выигрышей будут значения разницы прибыли предприятия 1 и предприятия 2 от производства продукции. В случае, если эта разница положительна, выигрывает предприятие 1, а в случае, если она отрицательна — предприятие 2.
2. Рассчитаем коэффициенты выигрышей платежной матрицы. Для этого необходимо определить значения прибыли предприятия 1 и предприятия 2 от производства продукции.

Прибыль предприятия в данной задаче зависит:

• от цены и себестоимости продукции;
• от количества продукции, приобретаемой населением региона;
• от доли продукции, приобретенной населением у предприятия.

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

D = p⋅(S⋅R1 - S⋅C1) - (1 - p)⋅(S⋅R2 - S⋅C2),

где D — значение разницы прибыли от производства продукции предприятия 1 и предприятия

p — доля продукции предприятия 1, приобретаемой населением региона;

S — количество продукции, приобретаемой населением региона;

R1 и R2 — цены реализации единицы продукции предприятиями 1 и

C1 и C2 — полная себестоимость единицы продукции, произведенной на предприятиях 1 и

Вычислим один из коэффициентов платежной матрицы.

Пусть, например, предприятие 1 принимает решение о производстве продукции в соответствии с технологией III, а предприятие 2 — в соответствии с технологией II. Тогда цена реализации единицы. продукции для предприятия 1 составит 2 д.е. при себестоимости единицы. продукции 1,5 д.е. Для предприятия 2 цена реализации единицы. продукции составит 6 д.е. при себестоимости 4 д.е..

Количество продукции, которое население региона приобретет при средней цене 4 д.е., равно 4 тыс. ед. (таблица 1). Доля продукции, которую население приобретет у предприятия 1, составит 0,85, а у предприятия 2 — 0,15 (табл. 1.3). Вычислим коэффициент платежной матрицы a 32 по формуле:

a 32 = 0,85⋅(4⋅2 - 4×1,5) - 0,15⋅(4⋅6 - 4⋅4) = 0,5 тыс. ед.

где i=3 — номер технологии первого предприятия, а j=2 — номер технологии второго предприятия.

Аналогично вычислим все коэффициенты платежной матрицы. В платежной матрице стратегии A 1 — A 3 – представляют собой решения о технологиях производства продукции предприятием 1, стратегии B 1 – B 3 — решения о технологиях производства продукции предприятием 2, коэффициенты выигрышей — разницу прибыли предприятия 1 и предприятия

	B 1	B 2	B 3	Min j
A 1	0,17	0,62	0,24	0,17
A 2	0,3	-1,5	-0,8	-1
A 3	0,9	0,5	0,4	0,4
Max i	3	0,62	0,4

Таблица — Платежная матрица в игре «Борьба двух предприятий».

В данной матрице нет ни доминируемых, ни дублирующих стратегий. Это значит, что для обоих предприятий нет заведомо невыгодных технологий производства продукции. Определим минимальные элементы строк матрицы. Для предприятия 1 каждый из этих элементов имеет значение минимально гарантированного выигрыша при выборе соответствующей стратегии. Минимальные элементы матрицы по строкам имеют значения: 0,17, -1,5, 0,4.

Определим максимальные элементы столбцов матрицы. Для предприятия 2 каждый из этих элементов также имеет значение минимально гарантированного выигрыша при выборе соответствующей стратегии. Максимальные элементы матрицы по столбцам имеют значения: 3, 0,62, 0,4.

Нижняя цена игры в матрице равна 0,4. Верхняя цена игры также равна 0,4. Таким образом, нижняя и верхняя цена игры в матрице совпадают. Это значит, что имеется технология производства продукции, которая является оптимальной для обоих предприятий в условиях данной задачи. Эта технология III, которая соответствует стратегиям A 3 предприятия 1 и B 3 предприятия Стратегии A 3 и B 3 — чистые оптимальные стратегии в данной задаче.

Значение разницы прибыли предприятия 1 и предприятия 2 при выборе чистой оптимальной стратегии положительно. Это означает, что предприятие 1 выиграет в данной игре. Выигрыш предприятия 1 составит 0,4 тыс. д.е. При этом на рынке будет реализовано 5 тыс. ед. продукции (реализация равна спросу на продукцию, таблица 1).. Оба предприятия установят цену за единицу продукции в 2 д.е. При этом для первого предприятия полная себестоимость единицы продукции составит 1,5 д.е., а для второго — 1 д.е. Предприятие 1 окажется в выигрыше лишь за счет высокой доли продукции, которую приобретет у него население.

Критерии принятия решения

ЛПР определяет наиболее выгодную стратегию в зависимости от целевой установки, которую он реализует в процессе решения задачи. Результат решения задачи ЛПР определяет по одному из критериев принятия решения . Для того, чтобы прийти к однозначному и по возможности наиболее выгодному варианту решению, необходимо ввести оценочную (целевую) функцию. При этом каждой стратегии ЛПР (A i) приписывается некоторый результат W i , характеризующий все последствия этого решения. Из массива результатов принятия решений ЛПР выбирает элемент W, который наилучшим образом отражает мотивацию его поведения.

В зависимости от условий внешней среды и степени информативности ЛПР производится следующая классификация задач принятия решений:

• в условиях риска;
• в условиях неопределенности;
• в условиях конфликта или противодействия (активного противника).

Принятие решений в условиях риска.

1. Критерий ожидаемого значения.

Использование критерия ожидаемого значения обусловлено стремлением максимизировать ожидаемую прибыль (или минимизировать ожидаемые затраты). Использование ожидаемых величин предполагает возможность многократного решения одной и той же задачи, пока не будут получены достаточно точные расчетные формулы. Математически это выглядит так: пусть Х — случайная величина с математическим ожиданием MX и дисперсией DX. Если x 1 , x 2 , ..., x n — значения случайной величины (с.в.) X, то среднее арифметическое их (выборочное среднее) значений x^=(x 1 +x 2 +...+x n)/n имеет дисперсию DX/n. Таким образом, когда n→∞ DX/n→∞ и X→MX.

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

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

Так как невозможно предсказать заранее, когда возникнет неисправность, необходимо найти вероятность того, что ПЭВМ выйдет из строя в период времени t. В этом и состоит элемент »риска».

Математически это выглядит так: ПЭВМ ремонтируется индивидуально, если она остановилась из-за поломки. Через T интервалов времени выполняется профилактический ремонт всех n ПЭВМ. Необходимо определить оптимальное значение m, при котором минимизируются общие затраты на ремонт неисправных ПЭВМ и проведение профилактического ремонта в расчете на один интервал времени.

Пусть р t — вероятность выхода из строя одной ПЭВМ в момент t, а n t — случайная величина, равная числу всех вышедших из строя ПЭВМ в тот же момент. Пусть далее С 1 – затраты на ремонт неисправной ПЭВМ и С 2 — затраты на профилактический ремонт одной машины.

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

ОЗ = (C 1 ∑M(n t)+C 1 n)/T,

где M(n t) — математическое ожидание числа вышедших из строя ПЭВМ в момент t. Так как n t имеет биномиальное распределение с параметрами (n, p t), то M(n t) = np t . Таким образом

ОЗ = n(C 1 ∑p t +C 2)/T.

Необходимые условия оптимальности T * имеют вид:

ОЗ (T * -1) ≥ ОЗ (T *),

ОЗ (T * +1) ≥ ОЗ (T *).

Следовательно, начиная с малого значения T, вычисляют ОЗ(

T), пока не будут удовлетворены необходимые условия оптимальности.

Пусть С 1 = 100; С 2 = 10; n = 50. Значенияp t имеют вид:

T	р t	∑р t	ОЗ(Т)
1	0.05	0	50(100⋅0+10)/1=500
2	0.07	0.05	375
3	0.10	0.12	366.7
4	0.13	02	400
5	0.18	0.35	450

T * →3, ОЗ(Т *)→366.7

Следовательно профилактический ремонт необходимо делать через T * =3 интервала времени.

Критерий «ожидаемое значение — дисперсия».

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

Если х — с. в. с дисперсией DX, то среднее арифметическое x^ имеет дисперсию DX/n, где n — число слагаемых в x^. Следовательно, если DX уменьшается, и вероятность того, что x^ близко к MX, увеличивается. Следовательно, целесообразно ввести критерий, в котором максимизация ожидаемого значения прибыли сочетается с минимизацией ее дисперсии.

Пример 2 . Применим критерий «ожидаемое значение — дисперсия» для примера 1. Для этого необходимо найти дисперсию затрат за один интервал времени, т.е. дисперсию

з Т =(C 1 ∑n t +C 2 n)/T

Т.к. n t , t = {1, T-1} — с.в., то з Т также с.в. С.в. n t имеет биномиальное распределение с M(n t) = np t и D(n t) = np t (1–p t). Следовательно,

D(з Т) = D((C 1 ∑n t +C 2 n)/T) = (C 1 /T) 2 D(∑n t) =

= (C 1 /T) 2 ∑Dn t = (C 1 /T) 2 ∑np t (1-p t) = (C 1 /T) 2 {∑p t - ∑p t 2 },

где С 2 n = const.

Из примера 1 следует, что

М(з Т) = М(з(Т)).

Следовательно искомым критерием будет минимум выражения

М(з(Т)) + к D(з Т).

Замечание . Константу «к» можно рассматривать как уровень не склонности к риску , т.к. «к» определяет «степень возможности» дисперсии Д(з Т) по отношению к математическому ожиданию. Например, если предприниматель, особенно остро реагирует на большие отрицательные отклонения прибыли вниз от М(з(Т)), то он может выбрать «к» много больше 1. Это придает больший вес дисперсии и приводит к решению, уменьшающему вероятность больших потерь прибыли.

При к=1 получаем задачу

M(з(T))+D(з(T)) = n { (C 1 /T+C 1 2 /T 2)∑p t - C 1 2 /T 2 ∑p t 2 + C 2 /T }

По данным из примера 1 можно составить следующую таблицу

T	p t	p t 2	∑p t	∑p t 2	М(з(Т))+D(з(Т))
1	0,05	0,0025	0	0	500.00
2	0,07	0,0049	0,05	0,0025	6312,50
3	0,10	0,0100	0,12	0,0074	6622,22
4	0,13	0,0169	0,2	0,0174	6731,25
5	0,18	0,0324	0,35	0,0343	6764,00

Из таблицы видно, что профилактический ремонт необходимо делать в течение каждого интервала Т * =1.

3. Критерий предельного уровня

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

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

Т.к. определить потери от дефицита очень трудно, ЛПР может установить необходимый уровень запасов таким образом, чтобы величина ожидаемого дефицита не превышала A 1 единиц, а величина ожидаемых излишков не превышала A 2 единиц. Иными словами, пусть I — искомый уровень запасов. Тогда

ожидаемый дефицит = ∫(x-I)f(x)dx ≤ A 1 ,

ожидаемые излишки = ∫(I-x)f(x)dx ≤ A 2 .

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

Пусть, например,

f(x) = 20/x 2 , 10≤x≤20,

f(x) = 0, x≤10 и x≥20.

∫(x-I)f(x)dx = ∫(x-I)(20/x 2)dx = 20(ln(20/I) + I/20 – 1)

∫(I-x)f(x)dx = ∫(I-x)(20/x 2)dx = 20(ln(10/I) + I/10 – 1)

Применение критерия предельного уровня приводит к неравенствам

ln(I) - I/20 ≥ ln(20) – A 1 /20 – 1 = 1,996 - A 1 /20

ln(I) - I/10 ≥ ln(10) – A 2 /20 – 1 = 1,302 - A 2 /20

Предельные значения A 1 и A 2 должны быть выбраны так, что бы оба неравенства выполнялись хотя бы для одного значения I.

Например, если A 1 = 2 и A 2 = 4, неравенства принимают вид

ln(I) - I/20 ≥ 1,896

ln(I) - I/10 ≥ 1,102

Значение I должно находиться между 10 и 20, т.к. именно в этих пределах изменяется спрос. Из таблицы видно, что оба условия выполняются для I, из интервала (13,17)

I	10	11	12	13	14	15	16	17	18	19	20
ln(I) - I/20	1,8	1,84	1,88	1,91	1,94	1,96	1,97	1,98	1,99	1,99	1,99
ln(I) - I/10	1,3	19	18	16	14	11	1,17	1,13	1,09	1,04	0,99

Любое из этих значений удовлетворяет условиям задачи.

Принятие решений в условиях неопределенности

Будем предполагать, что лицу, принимающему решение не противостоит разумный противник.

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

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

Варианты решения таковы:

Е 1 — выбор размеров из соображений максимальной долговечности;

Е m — выбор размеров из соображений минимальной долговечности;

E i — промежуточные решения.

Условия требующие рассмотрения таковы:

F 1 — условия, обеспечивающие максимальной долговечность;

F n — условия, обеспечивающие min долговечность;

F i — промежуточные условия.

Под результатом решения e ij = е(E i ; F j) здесь можно понимать оценку, соответствующую варианту E i и условиям F j и характеризующие прибыль, полезность или надежность. Обычно мы будем называть такой результат полезностью решения .

Тогда семейство (матрица) решений ||e ij || имеет вид:

	F 1	F 2	...	F n
E 1	e 11	e 12	...	e 1n
E 2	e 21	e 22	...	e 2n
...	...	...	...	...
E m	e m1	e m2	...	e mn

Чтобы прийти к однозначному и по возможности наивыгоднейшему варианту решению необходимо ввести оценочную (целевую) функцию. При этом матрица решений ||e ij || сводится к одному столбцу. Каждому варианту E i приписывается, т.о., некоторый результат e ir , характеризующий, в целом, все последствия этого решения. Такой результат мы будем в дальнейшем обозначать тем же символом e ir .

Классические критерии принятия решений

1. Минимаксный критерий.

Правило выбора решения в соответствии с минимаксным критерием (ММ-критерием) можно интерпретировать следующим образом:

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

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

Применение ММ-критерия бывает оправдано, если ситуация, в которой принимается решение следующая:

1. О возможности появления внешних состояний F j ничего не известно;
2. Приходится считаться с появлением различных внешних состояний F j ;
3. Решение реализуется только один раз;
4. Необходимо исключить какой бы то ни было риск.

2. Критерий Байеса—Лапласа.

Обозначим через q i — вероятность появления внешнего состояния F j .

Соответствующее правило выбора можно интерпретировать следующим образом:

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

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

1. Вероятности появления состояния F j известны и не зависят от времени.
2. Решение реализуется (теоретически) бесконечно много раз.
3. Для малого числа реализаций решения допускается некоторый риск.

При достаточно большом количестве реализаций среднее значение постепенно стабилизируется. Поэтому при полной (бесконечной) реализации какой-либо риск практически исключен.

Т.о. критерий Байеса-Лапласа (B-L-критерий) более оптимистичен, чем минимаксный критерий, однако он предполагает большую информированность и достаточно длительную реализацию.

3. Критерий Сэвиджа.

a ij:= max i (e ij) - e ij

e ir:= max i (a ij) = max j (max i (e ij) - e ij)

Величину a ij можно трактовать как максимальный дополнительный выигрыш, который достигается, если в состоянии F j вместо варианта E i выбирать другой, оптимальный для этого внешнего состояния вариант. Величину a ij можно интерпретировать и как потери (штрафы) возникающие в состоянии F j при замене оптимального для него варианта на вариант E i . В последнем случае e ir представляет собой максимально возможные (по всем внешним состояниям F j , j = {1,n}) потери в случае выбора варианта E i .

Соответствующее критерию Сэвиджа правило выбора теперь трактуется так:

1. Каждый элемент матрицы решений ||e ij || вычитается из наибольшего результата max(e ij) соответствующего столбца.
2. Разности a ij образуют матрицу остатков ||e ij ||. Эта матрица пополняется столбцом наибольших разностей e ir . Выбирают те варианты, в строках которых стоит наименьшее для этого столбца значение.

Требования, предъявляемые к ситуации, в которой принимается решение, совпадают с требованием к ММ-критерию.

4. Пример и выводы.

Из требований, предъявляемых к рассмотренным критериям становится ясно, что в следствии их жестких исходных позиций они применимы только для идеализированных практических решений. В случае, когда возможна слишком сильная идеализация, можно применять одновременно поочередно различные критерии. После этого среди нескольких вариантов ЛПР волевым методом выбирает окончательное решение. Такой подход позволяет, во-первых, лучше проникнуть во все внутренние связи проблемы принятия решений и, во-вторых, ослабляет влияние субъективного фактора.

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

Варианты решения таковы:

Е 1 — полная проверка;

Е 2 — минимальная проверка;

Е 3 — отказ от проверки.

ЭВМ может находиться в следующих состояниях:

F 1 — вирус отсутствует;

F 2 — вирус есть, но он не успел повредить информацию;

F 3 — есть файлы, нуждающиеся в восстановлении.

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

	F 1	F 2	F 3	ММ-критерий		критерий B-L
				e ir = min j (e ij)	max i (e ir)	e ir = ∑e ij	max i (e ir)
E 1	-20,0	-20	-25,0	-25,0	-25,0	-22,33
E 2	-14,0	-23,0	-31,0	-31,0		-22,67
E 3	0	-24.0	-40.0	-40.0		-21.33	-21.33

Согласно ММ-критерию следует проводить полную проверку. Критерий Байеса-Лапласа, в предположении, что все состояния машины равновероятны.

	F 1	F 2	F 3	Критерий Сэвиджа
				e ir = min j (a ij)	min j (e ir)
E 1	+20,0	0	0	+20,0
E 2	+14,0	+1,0	+6,0	+14,0	+14,0
E 3	0	+2,0	+15,0	+15,0

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

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

Производные критерии.

1. Критерий Гурвица.

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

max i (e ir) = { C⋅min j (e ij) + (1-C)⋅max j (e ij) },

где С — весовой множитель.

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

матрица решений ||e ij || дополняется столбцом, содержащим среднее взвешенное наименьшего и наибольшего результатов для каждой строки. Выбираются только те варианты, в строках которых стоят наибольшие элементыe e ir этого столбца.

При С=1 критерий Гурвица превращается в ММ-критерий. При С = 0 он превращается в критерий «азартного игрока»

max i (e ir) = max i (max j (e ij)),

т.е. мы становимся на точку зрения азартного игрока, делающего ставку на то, что «выпадет» наивыгоднейший случай.

В технических приложениях сложно выбрать весовой множитель С, т.к. трудно найти количественную характеристику для тех долей оптимизма и пессимизма, которые присутствуют при принятии решения. Поэтому чаще всего С:=1/2.

Критерий Гурвица применяется в случае, когда:

1. о вероятностях появления состояния F j ничего не известно;
2. с появлением состояния F j необходимо считаться;
3. реализуется только малое количество решений;
4. допускается некоторый риск.

2. Критерий Ходжа–Лемана.

Этот критерий опирается одновременно на ММ-критерий и критерий Баеса-Лапласа. С помощью параметра n выражается степень доверия к используемому распределений вероятностей. Если доверие велико, то доминирует критерий Баеса-Лапласа, в противном случае — ММ-критерий, т.е. мы ищем

max i (e ir) = max i {v⋅∑e ij ⋅q i + (1-v) min j (e ir)}, 0 ≤ n ≤ 1.

Правило выбора, соответствующее критерию Ходжа-Лемана формируется следующим образом:

матрица решений ||e ij || дополняется столбцом, составленным из средних взвешенных (с весом v≡const) математическое ожиданиями и наименьшего результата каждой строки (*). Отбираются те варианты решений в строках которого стоит набольшее значение этого столбца.

При v = 1 критерий Ходжа-Лемана переходит в критерий Байеса-Лапласа, а при v = 0 становится минимаксным.

Выбор v субъективен т. к. Степень достоверности какой-либо функции распределения — дело темное.

Для применения критерия Ходжа-Лемана желательно, чтобы ситуация в которой принимается решение, удовлетворяла свойствам:

1. вероятности появления состояния F j неизвестны, но некоторые предположения о распределении вероятностей возможны;
2. принятое решение теоретически допускает бесконечно много реализаций;
3. при малых числах реализации допускается некоторый риск.

3. Критерий Гермейера.

Этот критерий ориентирован на величину потерь, т.е. на отрицательные значения всех e ij . При этом

max i (e ir) = max i (min j (e ij)q j) .

Т.к. в хозяйственных задачах преимущественно имеют дело с ценами и затратами, условиеe e ij <0 обычно выполняется. В случае же, когда среди величин e ij встречаются и положительные значения, можно перейти к строго отрицательным значениям с помощью преобразования e ij -a при подходящем образом подобранном a>0. При этом оптимальный вариант решения зависит от а.

Правило выбора согласно критерию Гермейера формулируется следующим образом:

матрица решений ||e ij || дополняется еще одним столбцом содержащим в каждой строке наименьшее произведение имеющегося в ней результата на вероятность соответствующего состояния F j . Выбираются те варианты в строках которых находится наибольшее значениеe e ij этого столбца.

В каком-то смысле критерий Гермейера обобщает ММ-критерий: в случае равномерного распределения q j = 1/n, j={1,n}, они становятся идентичными.

Условия его применимости таковы:

1. с появлением тех или иных состояний, отдельно или в комплексе, необходимо считаться;
2. допускается некоторый риск;
3. решение может реализоваться один или несколько раз.

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

4. Объединенный критерий Байеса-Лапласа и минимакса.

Стремление получить критерии, которые бы лучше приспосабливались к имеющейся ситуации, чем все до сих пор рассмотренные, привело к построению так называемых составных критериев. В качестве примера рассмотрим критерий, полученный путем объединения критериев Байеса-Лапласа и минимакса (BL(MM)-критерий).

Правило выбора для этого критерия формулируется следующим образом:

матрица решений ||e ij || дополняется еще тремя столбцами. В первом из них записываются математические ожидания каждой из строк, во втором — разность между опорным значением

e i 0 j 0 = max i (max j (e ij))

и наименьшим значением

соответствующей строки. В третьем столбце помещаются разности между наибольшим значением

каждой строки и наибольшим значением max j (e i 0 j) той строки, в которой находится значение e i 0 j 0 . Выбираются те варианты, строки которых (при соблюдении приводимых ниже соотношений между элементами второго и третьего столбцов) дают наибольшее математическое ожидание. А именно, соответствующее значение

e i 0 j 0 - max j (e ij)

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

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

1. вероятности появления состояний F j неизвестны, однако имеется некоторая априорная информация в пользу какого-либо определенного распределения;
2. необходимо считаться с появлением различных состояний как по отдельности, так и в комплексе;
3. допускается ограниченный риск;
4. принятое решение реализуется один раз или многократно.

BL(MM)-критерий хорошо приспособлен для построения практических решений прежде всего в области техники и может считаться достаточно надежным. Однако заданные границы риска E доп и, соответственно, оценок риска E i не учитывает ни число применения решения, ни иную подобную информацию. Влияние субъективного фактора хотя и ослаблено, но не исключено полностью.

max j (e ij)-max j (e i 0 j)≥E i

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

5. Критерий произведений.

max i (e ir):= max i (∏e ij)

Правило выбора в этом случае формулируется так:

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

Применение этого критерия обусловлено следующими обстоятельствами:

1. вероятности появления состояния F j неизвестны;
2. с появлением каждого из состояний F j по отдельности необходимо считаться;
3. критерий применим и при малом числе реализаций решения;
4. некоторый риск допускается.

Критерий произведений приспособлен в первую очередь для случаев, когда все e ij положительны. Если условие положительности нарушается, то следует выполнять некоторый сдвиг e ij +а с некоторой константой а>|min ij (e ij)|. Результат при этом будет, естественно зависеть от а. На практике чаще всего

а:= |min ij (e ij)|+1.

Если же никакая константа не может быть признана имеющей смысл, то критерий произведений не применим.

Пример.

Рассмотрим тот же пример, что и ранее (см. выше).

Построение оптимального решения для матрицы решений о проверках по критерию Гурвица имеет вид (при С=0, в 10 3):

||e ij ||			С⋅min j (e ij)	(1-С)⋅max j (e ij)	e ir	max i (e ir)
-20,0	-22,0	-25,0	-12,5	-10.0	-22,5
-14,0	-23.0	-31.0	-15,5	-7.0	-22,5
0	-24.0	-40.0	-20.0	0	-20.0	-20.0

В данном примере у решения имеется поворотная точка относительно весового множителя С: до С=0,57 в качестве оптимального выбирается Е 3 , а при больших значениях — Е 1 .

Применение критерия Ходжа-Лемана (q=0,33, v=0, в 10 3):

∑e ij ⋅q j	min j (e ij)	v⋅∑e ij ⋅q j	(1-v)⋅∑e ij ⋅q j	e ir	max i (e ir)
-22,33	-25,0	-11,17	-12,5	-23,67	-23,67
-22,67	-31,0	-11,34	-15,5	-26,84
-21,33	-40,0	-10,67	-20,0	-30,76

Критерий Ходжа-Лемана рекомендует вариант Е 1 (полная проверка) — так же как и ММ-критерий. Смена рекомендуемого варианта происходит только при v=0,94. Поэтому равномерное распределение состояний рассматриваемой машины должно распознаваться с очень высокой вероятностью, чтобы его можно было выбрать по большему математическому ожиданию. При этом число реализаций решения всегда остается произвольным.

Критерий Гермейера при q j = 0.33 дает следующий результат (в 10 3):

||e ij ||			||e ij q j ||			e ir = min j (e ij q j)	max i (e ir)
-20,0	-22,0	-25,0	-6,67	-7,33	-8,33	-8,33	-8,33
-14,0	-23,0	-31,.0	-4,67	-7,67	-10,33	-10,33
0	-24,0	-40,0	0	-8,0	-13,33	-13,33

В качестве оптимального выбирается вариант Е 1 . Сравнение вариантов с помощью величинe e ir показывает, что способ действия критерия Гермейера является даже более гибким, чем у ММ-критерия.

В таблице, приведенной ниже, решение выбирается в соответствии с BL(MM)-критерием при q 1 =q 2 =q 3 =1/2 (данные в 10 3).

||e ij ||			∑e ij q j	e i 0 j 0 - min j (e ij)	max j (e ij)	max j (e ij) - max j (e i 0 j)
-20,0	-22,0	-25,0	-23,33	0	-20,0	0
-14,0	-23,0	-31,0	-22,67	+6,0	-14,0	+6,0
0	-24,0	-40,0	-21,33	+15,0	0	+20,0

Вариант Е 3 (отказ от проверки) принимается этим критерием только тогда, когда риск приближается к E возм = 15⋅10 3 . В противном случае оптимальным оказывается Е 1 . Во многих технических и хозяйственных задачах допустимый риск бывает намного ниже, составляя обычно только незначительный процент от общих затрат. В подобных случаях бывает особенно ценно, если неточное значение распределения вероятностей сказывается не очень сильно. Если при этом оказывается невозможным установить допустимый риск E доп заранее, не зависимо от принимаемого решения, то помочь может вычисление ожидаемого риска E возм. Тогда становится возможным подумать, оправдан ли подобный риск. Такое исследование обычно дается легче.

Результаты применения критерия произведения при а = 41⋅10 3 и а = 200⋅10 3 имеют вид:

a	||e ij + a||			e ir = ∏ j e ij	max i e ir
41	+21	+19	+16	6384	6384
	+27	+18	+10	4860
	+41	+17	+1	697
200	+180	+178	+175	5607
	+186	+177	+169	5563
	+200	+176	+160	5632	5632

Условие e ij > 0 для данной матрицы не выполнимо. Поэтому к элементам матрицы добавляется (по внешнему произволу) сначала а = 41⋅10 3 , а затем а = 200⋅10 3 .

Для а = 41⋅10 3 оптимальным оказывается вариант Е 1 , а для а = 200⋅10 3 — вариант Е 3 , так что зависимость оптимального варианта от а очевидна.