МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение
Костромской государственный университет имени Н.А. Некрасова
Скаржинская Е.М., Илюхина А.С., Метелькова К.С.
Теория игр для экономистов
Кострома
Скаржинская Е.М., Илюхина А.С., Метелькова К.С. Теория игр: конспект лекций с методическими указаниями: Учебное пособие. – Кострома. 2008. –90с.
Рецензенты:
Землякова И.В., доктор технических наук, профессор
Цуриков В.И., доктор экономических наук, профессор
Настоящее учебное пособие разработано доктором экономических наук, профессором Скаржинской Е.М. и сотрудниками кафедры «Математические методы в экономике». Пособие предназначено для аспирантов и студентов экономических специальностей.
Глава 1. Введение.
§1.1. Предмет теории игр 4
§1.2. Формальное описание игры. 10
§1.3. Классификация игр 11
Глава 2. Бескоалиционные игры
§2.1. Антагонистические игры
§2.1.1. Понятие антагонистической игры. Матричная игра 13
§2.1.2. Доминирование стратегий. Редукция игры. 14
Решение игры в доминирующих стратегиях
§2.1.3. Решение игры в чистых стратегиях 16
§2.1.4. Смешанное расширение игры 22
§2.1.5. Решение игры в смешанных стратегиях 28
§2.1.6. Игра против природы 31
§2.1.7. Критерии оптимальности решения в
условиях неопределённости 32
§2.1.8 Критерий Лапласа 33
§2.1.9. Критерий Вальда (максиминный критерий) 34
§2.1.10. Критерий Гурвица (критерий взвешенного
оптимизма /пессимизма) 35
§2.1.11. Критерий Сэвиджа (критерий наименьших
сожалений) 36
§2.1.12. Решение игры против природы в смешанных
стратегиях 37
§ 2.2 Неантагонистические игры
§2.2.1. Понятие неантагонистической игры 40
§2.2.2. Биматричные игры 42
§2.2.3. Равновесие Нэша 44
§2.2.4. Эффективность по Парето 48
§2.2.5. Повторяющиеся игры. Применение к микроэкономике 49
§2.2.6. Последовательные игры 54
Глава 3. Кооперативные решения
§3.1. Понятие коалиционной игры 62
§3.2. Определение решения игры 65
§3.3. Эффективность обмена. Ящик Эджворта 66
§3.4. Арбитражное решение 72
Практикум 79
Литература 93
Введение
§1.1. Предмет теории игр
Любой процесс в экономике происходит при активном взаимодействии людей, стремящихся реализовать собственные цели, имеющих собственные интересы, оценивающих результаты процесса с точки зрения своих интересов. Интересы участников экономического взаимодействия часто не совпадают. Результаты, которые выгодны одним участникам, могут быть не выгодны другим. Так, например, продавцы заинтересованы в увеличении выручки, а покупатели заинтересованы в понижении цены; наемные работники заинтересованы в повышении заработной платы, что снижает прибыль нанимателей. Перечисленные ситуации имеют общее свойство – наблюдается конфликт интересов участников, т.е. лиц, от которых зависит конечный результат экономического процесса.
Конфликт присутствует в принятии решений даже в том случае, когда решение принимает одно лицо. Например, человек собирается купить квартиру и руководствуется четырьмя критериями: квартира должна быть недорогой, удобно расположенной, иметь хорошее качество, быть удачно спланированной. При выборе из множества предлагаемых вариантов покупатель видит, что одни варианты лучше других по критерию цены, но уступают по критерию расположения, и т.д. В данном случае выбор варианта осложняется конфликтом целей , которые ставит покупатель при покупке жилья.
Принятие решений еще более усложняется, если результат, который получает некоторое лицо, зависит не только от принимаемого им решения, но и от решений, которые принимают другие лица. Например, цена товара на рынке, где предложение поступает от нескольких продавцов, зависит от того, какую рыночную стратегию (объем предложения и назначенная цена) выберет каждый продавец. Таким образом, каждый участник, выбирая те или иные действия (т.е. выбирая свою стратегию ), воздействует на конечный результат, т.е. на цену и объем реализации, и в конечном итоге на выручку всех продавцов.
Многообразие ситуаций принятия решений в экономике и в других сферах имеет три общие черты, которые можно сформулировать в виде трех принципов:
1. Конечный результат зависит от выбора решений несколькими лицами (которых мы будем называть участниками игры ). Этот принцип носит название «совместность действий» .
2. Принцип, согласно которому возникает конфликт между участниками какого-либо общего процесса из-за несовпадения их интересов, носит название «конфликт интересов» .
3. Участник экономического процесса стоит перед выбором решения, которое в наибольшей степени должно соответствовать его интересам Для выбора разумного (т.е. рационального) решения, участник должен осознавать, что другие участники имеют собственные интересы, а значит, будут выбирать решения, которые выгодны им. Принцип, согласно которому каждый участник конфликта принимает наиболее эффективные для достижения своих интересов решения, учитывая возиможные действия других участников, называется принципом рациональности .
Легко заметить, что эти три принципа характерны для любой конфликтной ситуации не только в экономике. Примерами конфликтов служат спортивные состязания, политическая борьба, карточные игры, трудовые отношения, рыночное ценообразование, конкуренция, цена акций и т.п. Все эти разнообразные конфликтные ситуации допускают общие формализованные описания и анализ с помощью математических методов. Формализованное описание конфликта (т.е. его математическая модель) называется игрой (The Game ). Теория игр является разделом математики, в котором изучаются математические модели конфликтов.
Конфликты и возможности математического анализа вариантов их разрешения, предсказания их исходов давно привлекают внимание математиков. Зарождение теории игр как математической дисциплины можно отнести к письму Б. Паскаля к П. Ферма от 29 июля 1654 года, которое принято считать началом математической теории вероятностей. В дальнейшем отдельные математические вопросы, которые можно отнести к теоретико-игровым, рассматривались многими учеными. Объектом изучения вначале были азартные и карточные игры. Вальдеграв нашел оптимальные смешанные стратегии в игре «проходящий туз» (1712 год), Д. Бернулли проанализировал «петербургскую игру» (1732 год), П. Лаплас рассмотрел принципы оптимальности (1814 год), Ж. Бертран представил теоретико-игровой подход к игре в баккара (1888 год), в 1911 году Э. Цермело описал теоретико-игровой подход к шахматной игре.
Систематическое изучение матричных игр началось с работы Э. Бореля (1921 г.), содержащей доказательство существования оптимальных смешанных стратегий для некоторых случаев игры..
В XX веке теория игр получила энергичное развитие, вызванное не только теоретическим интересом математиков, но и запросами прикладных задач экономики и техники. По сути, математическая теория игр была детально разработана американскими учеными Дж. Нейманом и О. Моргенштерном в известной работе «Теория игр и экономическое поведение» (1944 год) как средство математического подхода к явлениям конкурентной экономики.
Вторая половина XX века отмечена важнейшими результатами в теории игр и ее применением в самых разнообразных сферах, прежде всего в экономике, политике и военном деле. Понятие равновесия , имеющее центральное значение в теории игр, сформулировано выдающимся математиком и экономистом Дж. Нэшем, им же доказана теорема существования равновесия в бескоалиционной игре (теорема Нэша ). Дж. Нейман и О. Моргенштерн получили первое из решений для коалиционных игр, Н-М решение . Современная теория коалиционных игр, на основе которых моделируются политические и экономические процессы, сложилась благодаря работам Л.С. Шепли. Р. Аумана, А.И. Соболева. Общее определение игры и исчерпывающую классификацию игр впервые дал выдающийся российский математик Н.Н. Воробьев. Значительный вклад в развитие теории игр внесли российские Е.Б. Яновская, Ю.Б. Гермейер, Э. Вилкас, Г.Н. Дюбин и В.Г. Суздаль.
В ходе своего развития теория игр превратилась в общую математическую теорию конфликтов . В рамках теории игр поддаются математическому описанию военные и правовые конфликты, спортивные состязания, а также явления, связанные с биологической борьбой за существование. Теория игр позволяет формализовать некоторые важные аспекты принятия решений в технике, сельском хозяйстве, медицине и социологии. Проблемы управления, планирования и прогнозирования также часто решаются с помощью сценарного подхода, разрабатываемого с применением теории игр.
Как всякая математическая модель, игра создается с определенными целями, для того, чтобы ответить на определенные вопросы. Формулировка некоторых вопросов, на которые должен ответить анализ игры, очевидна – например, как должен действовать участник игры, стремящийся получить наибольший выигрыш? Или – как должен действовать игрок, стремящийся обезопасить себя от наибольших потерь? На языке теории игр вопросы подобного рода формулируются следующим образом. И чем (каким исходом) закончится игра, если все участники выберут свои оптимальные стратегии? Имеют ли игроки оптимальные стратегии? Существуют ли в данной игре исходы, которые выгодны всем игрокам? Будут ли все участники стремиться именно к этим исходам?
Заметим, что анализ игры способен дать ответы далеко не на все вопросы. Так, например, часто нет ответа на «детский» вопрос – чем закончится данная игра, или кто будет победителем? Дело в том, что, во-первых, исход игры может зависеть от случайных факторов, во-вторых, некоторые игры имеют несколько решений, в-третьих, реальные участники игры могут действовать не вполне рационально, т.е. не принимать оптимальные решения.
Лекция 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 В игре «коршун и голубь» есть три точки равновесия по Нэшу: «Дилемма заключенного» — одна из наиболее распространенных конфликтных ситуаций, рассматриваемая в теории игр. Классическая «дилемма заключенного» звучит следующим образом: двое подозреваемых, A и B, находятся в разных камерах. Следователь, навещая их поодиночке, предлагает сделку следующего содержания: если один из них будет свидетельствовать против другого, а второй будет молчать, то первый заключенный будет освобожден, а второго осудят на 10 лет. Если оба будут молчать, то отсидят по 6 месяцев. Если оба предадут друг друга, то каждый получит по 2 года. Каждый из заключенных должен принять решение: предать подельника или молчать, не зная о том, какое решение принял другой. Дилемма: какое решение примут заключенные? Платежная матрица игры: В данном случае, результат базируется на решении каждого из заключенных. Положение игроков осложняется тем, что они не знают о том, какое решение принял другой, и тем, что они не доверяют друг другу. Наилучшей стратегией игроков будет кооперация, при которой оба молчат, и получают максимальный выигрыш (меньший срок), каждое другое решение будет менее выигрышным. Проанализируем «дилемму заключенного», перейдя для наглядности к платежной матрице канонического вида: Согласно этой матрице, цена взаимного отказа от кооперации (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: Точки равновесия по Нэшу: (B,A), (A,B) и (C,C). Indeed, for cell (B,A), так как 40 — максимальное значение в первом столбце, 25 максимальное значение во втором ряду. Для ячейки (A,B) 25 — это максимальное значение во втором столбце, 40 — максимальное значение во втором ряду. То же самое и для ячейки (C,C). Рассмотрим пример игры в загрязнения (окружающей среды). Здесь объектом нашего внимания станет такой вид побочных эффектов производства, как загрязнение. Если бы фирмы никогда и никого не спрашивали о том, как им поступить, любая из них скорее предпочла бы создавать загрязнения, чем устанавливать дорогостоящие очистители. Если же какая-нибудь фирма решилась бы уменьшить вредные выбросы, то издержки, а, следовательно, и цены на ее продукцию, возросли бы, а спрос бы упал. Вполне возможно, эта фирма просто обанкротилась бы. Живущие в жестоком мире естественного отбора, фирмы скорее предпочтут оставаться в условиях равновесия по Нэшу (ячейка D), при котором не нужно расходовать средства на очистные сооружения и технологии. Ни одной фирме не удастся повысить прибыль, уменьшая загрязнение. Таблица — Платежная матрица игры в загрязнение окружающей среды. Вступив в экономическую игру, каждая неконтролируемая государством и максимизирующая прибыль сталелитейная фирма будет производить загрязнения воды и воздуха. Если какая-либо фирма попытается очищать свои выбросы, то тем самым она будет вынуждена повысить цены и потерпеть убытки. Некооперативное поведение установит равновесие по Нэшу в условиях высоких выбросов. Правительство может предпринять меры с тем, чтобы равновесие переместилось в ячейку А. В этом положении загрязнение будет незначительным, прибыли же останутся теми же. Игры загрязнения - один из случаев того, как механизм действия «невидимой руки» не срабатывает. Это ситуация, когда равновесие по Нэшу неэффективно. Иногда подобные неконтролируемые игры становятся угрожающими, и здесь может вмешаться правительство. Установив систему штрафов и квот на выбросы, правительство может побудить фирмы выбрать исход А, соответствующий низкому уровню загрязнения. Фирмы зарабатывают ровно столько же, сколько и прежде, при больших выбросах, мир же становится несколько чище. Рассмотрим пример решения матричной игры в чистых стратегиях, в условиях реальной экономики, в ситуации борьбы двух предприятий за рынок продукции региона. Два предприятия производят продукцию и поставляют ее на рынок региона. Они являются единственными поставщиками продукции в регион, поэтому полностью определяют рынок данной продукции в регионе. Каждое из предприятий имеет возможность производить продукцию с применением одной из трех различных технологий. В зависимости от экологичности технологического процесса и качества продукции, произведенной по каждой технологии, предприятия могут установить цену единицы продукции на уровне 10, 6 и 2 денежных единиц соответственно. При этом предприятия имеют различные затраты на производство единицы продукции. Таблица — Затраты на единицу продукции, произведенной на предприятиях региона (д.е.). В результате маркетингового исследования рынка продукции региона была определена функция спроса на продукцию: Y = 6 - 0.5⋅X, где Y — количество продукции, которое приобретет население региона (тыс. ед.), а X — средняя цена продукции предприятий, д.е. Данные о спросе на продукцию в зависимости от цен реализации приведены в таблице: Цена реализации 1 ед. продукции, д.е. Средняя цена реализации 1 ед. продукции, д.е. Спрос на продукцию, тыс. ед. Таблица — Спрос на продукцию в регионе, тыс. ед. Значения Долей продукции предприятия 1, приобретенной населением, зависят от соотношения цен на продукцию предприятия 1 и предприятия В результате маркетингового исследования эта зависимость установлена и значения вычислены: Таблица — Доля продукции предприятия 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 и предприятия Таблица — Платежная матрица в игре «Борьба двух предприятий». В данной матрице нет ни доминируемых, ни дублирующих стратегий. Это значит, что для обоих предприятий нет заведомо невыгодных технологий производства продукции. Определим минимальные элементы строк матрицы. Для предприятия 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, который наилучшим образом отражает мотивацию его поведения. В зависимости от условий внешней среды и степени информативности ЛПР производится следующая классификация задач принятия решений: Использование критерия ожидаемого значения обусловлено стремлением максимизировать ожидаемую прибыль (или минимизировать ожидаемые затраты). Использование ожидаемых величин предполагает возможность многократного решения одной и той же задачи, пока не будут получены достаточно точные расчетные формулы. Математически это выглядит так: пусть Х — случайная величина с математическим ожиданием 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 * →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 можно составить следующую таблицу Из таблицы видно, что профилактический ремонт необходимо делать в течение каждого интервала Т * =1. Критерий предельного уровня не дает оптимального решения, максимизирующего, например, прибыль или минимизирующего затраты. Скорее он соответствует определению приемлемого
способа действий. Пример 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) Любое из этих значений удовлетворяет условиям задачи. Будем предполагать, что лицу, принимающему решение не противостоит разумный
противник. Данные, необходимо для принятия решения в условии неопределенности, обычно задаются в форме матрицы, строки которой соответствуют возможным действиям, а столбцы — возможным состояниям системы. Пусть, например, из некоторого материала требуется изготовить изделие, долговечность которого при допустимых затратах невозможно определить. Нагрузки считаются известными. Требуется решить, какие размеры должно иметь изделие из данного материала. Варианты решения таковы: Е 1 — выбор размеров из соображений максимальной долговечности; Е m — выбор размеров из соображений минимальной долговечности; E i — промежуточные решения. Условия требующие рассмотрения таковы: F 1 — условия, обеспечивающие максимальной долговечность; F n — условия, обеспечивающие min долговечность; F i — промежуточные условия. Под результатом решения e ij = е(E i ; F j) здесь можно понимать оценку, соответствующую варианту E i и условиям F j и характеризующие прибыль, полезность или надежность. Обычно мы будем называть такой результат полезностью решения
. Тогда семейство (матрица) решений ||e ij || имеет вид: Чтобы прийти к однозначному и по возможности наивыгоднейшему варианту решению необходимо ввести оценочную (целевую) функцию. При этом матрица решений ||e ij || сводится к одному столбцу. Каждому варианту E i приписывается, т.о., некоторый результат e ir , характеризующий, в целом, все последствия этого решения. Такой результат мы будем в дальнейшем обозначать тем же символом e ir . Правило выбора решения в соответствии с минимаксным критерием (ММ-критерием) можно интерпретировать следующим образом: матрица решений дополняется еще одним столбцом из наименьших результатов e ir каждой строки. Необходимо выбрать те варианты в строках которых стоят наибольшее значение e ir этого столбца. Выбранные т.о. варианты полностью исключают риск. Это означает, что принимающий решение не может столкнуться с худшим результатом, чем тот, на который он ориентируется. Это свойство позволяет считать ММ-критерий одним из фундаментальных. Применение ММ-критерия бывает оправдано, если ситуация, в которой принимается решение следующая: Обозначим через q i — вероятность появления внешнего состояния F j . Соответствующее правило выбора можно интерпретировать следующим образом: матрица решений дополняется еще одним столбцом содержащим математическое ожидание значений каждой из строк. Выбираются те варианты, в строках которых стоит наибольшее значение e ir этого столбца. При этом предполагается, что ситуация, в которой принимается решение, характеризуется следующими обстоятельствами: При достаточно большом количестве реализаций среднее значение постепенно стабилизируется. Поэтому при полной (бесконечной) реализации какой-либо риск практически исключен. Т.о. критерий Байеса-Лапласа (B-L-критерий) более оптимистичен, чем минимаксный критерий, однако он предполагает большую информированность и достаточно длительную реализацию. 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 — полная проверка; Е 2 — минимальная проверка; Е 3 — отказ от проверки. ЭВМ может находиться в следующих состояниях: F 1 — вирус отсутствует; F 2 — вирус есть, но он не успел повредить информацию; F 3 — есть файлы, нуждающиеся в восстановлении. Результаты, включающие затраты на поиск вируса и его ликвидацию, а также затраты, связанные с восстановлением информации имеют вид: Согласно ММ-критерию следует проводить полную проверку. Критерий Байеса-Лапласа, в предположении, что все состояния машины равновероятны. Пример специально подобран так, что каждый критерий предлагает новое решение. Неопределенность состояния, в котором проверка застает ЭВМ, превращается в неясность, какому критерию следовать. Поскольку различные критерии связаны с различными условиями, в которых принимается решение, лучшее всего для сравнительной оценки рекомендации тех или иных критериев получить дополнительную информацию о самой ситуации. В частности, если принимаемое решение относится к сотням машин с одинаковыми параметрами, то рекомендуется применять критерий Байеса-Лапласа. Если же число машин не велико, лучше пользоваться критериями минимакса или Севиджа. Стараясь занять наиболее уравновешенную позицию, Гурвиц предположил оценочную функцию, которая находится где-то между точкой зрения крайнего оптимизма и крайнего пессимизма: 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. Критерий Гурвица применяется в случае, когда: Этот критерий опирается одновременно на ММ-критерий и критерий Баеса-Лапласа. С помощью параметра 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 субъективен т. к. Степень достоверности какой-либо функции распределения — дело темное. Для применения критерия Ходжа-Лемана желательно, чтобы ситуация в которой принимается решение, удовлетворяла свойствам: Этот критерий ориентирован на величину потерь, т.е. на отрицательные значения всех 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}, они становятся идентичными. Условия его применимости таковы: Если функция распределения известна не очень надежно, а числа реализации малы, то, следуя критерию Гермейера, получают, вообще говоря, неоправданно большой риск. Стремление получить критерии, которые бы лучше приспосабливались к имеющейся ситуации, чем все до сих пор рассмотренные, привело к построению так называемых составных критериев. В качестве примера рассмотрим критерий, полученный путем объединения критериев Байеса-Лапласа и минимакса (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 доп. Значение же из третьего столбца должно быть больше значения из второго столбца. Применение этого критерия обусловлено следующими признаками ситуации, в которой принимается решение: BL(MM)-критерий хорошо приспособлен для построения практических решений прежде всего в области техники и может считаться достаточно надежным. Однако заданные границы риска E доп и, соответственно, оценок риска E i не учитывает ни число применения решения, ни иную подобную информацию. Влияние субъективного фактора хотя и ослаблено, но не исключено полностью. max j (e ij)-max j (e i 0 j)≥E i существенно в тех случаях, когда решение реализуется только один или малое число раз. В этих условиях недостаточно ориентироваться на риск, связанный только с невыгодными внешними состояниями и средними значениями. Из-за этого, правда, можно понести некоторые потери в удачных внешних состояниях. При большом числе реализаций это условие перестает быть таким уж важным. Оно даже допускает разумные альтернативы. При этом не известно, однако, четких количественных указаний, в каких случаях это условие следовало бы опускать. max i (e ir):= max i (∏e ij) Правило выбора в этом случае формулируется так: Матрица решений ||e ij || дополняется новым столбцом, содержащим произведения всех результатов каждой строки. Выбираются те варианты, в строках которых находятся наибольшие значения этого столбца. Применение этого критерия обусловлено следующими обстоятельствами: Критерий произведений приспособлен в первую очередь для случаев, когда все e ij положительны. Если условие положительности нарушается, то следует выполнять некоторый сдвиг e ij +а с некоторой константой а>|min ij (e ij)|. Результат при этом будет, естественно зависеть от а. На практике чаще всего а:= |min ij (e ij)|+1. Если же никакая константа не может быть признана имеющей смысл, то критерий произведений не применим. Рассмотрим тот же пример, что и ранее (см. выше). Построение оптимального решения для матрицы решений о проверках по критерию Гурвица имеет вид (при С=0, в 10 3): В данном примере у решения имеется поворотная точка относительно весового множителя С: до С=0,57 в качестве оптимального выбирается Е 3 , а при больших значениях — Е 1 . Применение критерия Ходжа-Лемана (q=0,33, v=0, в 10 3): Критерий Ходжа-Лемана рекомендует вариант Е 1 (полная проверка) — так же как и ММ-критерий. Смена рекомендуемого варианта происходит только при v=0,94. Поэтому равномерное распределение состояний рассматриваемой машины должно распознаваться с очень высокой вероятностью, чтобы его можно было выбрать по большему математическому ожиданию. При этом число реализаций решения всегда остается произвольным. Критерий Гермейера при q j = 0.33 дает следующий результат (в 10 3): В качестве оптимального выбирается вариант Е 1 . Сравнение вариантов с помощью величинe e ir показывает, что способ действия критерия Гермейера является даже более гибким, чем у ММ-критерия. В таблице, приведенной ниже, решение выбирается в соответствии с BL(MM)-критерием при q 1 =q 2 =q 3 =1/2 (данные в 10 3). Вариант Е 3 (отказ от проверки) принимается этим критерием только тогда, когда риск приближается к E возм = 15⋅10 3 . В противном случае оптимальным оказывается Е 1 . Во многих технических и хозяйственных задачах допустимый риск бывает намного ниже, составляя обычно только незначительный процент от общих затрат. В подобных случаях бывает особенно ценно, если неточное значение распределения вероятностей сказывается не очень сильно. Если при этом оказывается невозможным установить допустимый риск E доп заранее, не зависимо от принимаемого решения, то помочь может вычисление ожидаемого риска E возм. Тогда становится возможным подумать, оправдан ли подобный риск. Такое исследование обычно дается легче. Результаты применения критерия произведения при а = 41⋅10 3 и а = 200⋅10 3 имеют вид: Условие e ij > 0 для данной матрицы не выполнимо. Поэтому к элементам матрицы добавляется (по внешнему произволу) сначала а = 41⋅10 3 , а затем а = 200⋅10 3 . Для а = 41⋅10 3 оптимальным оказывается вариант Е 1 , а для а = 200⋅10 3 — вариант Е 3 , так что зависимость оптимального варианта от а очевидна. Дадим формальное определение
игр, которые мы будем рассматривать. Кстати, шахматы или даже го не будут подпадать под это определение
. Что и логично: мы тут математикой занимаемся, а не эффективными алгоритмами; а с математической точки зрения (да и с точки зрения теории сложности алгоритмов, асимптотической по своей природе) шахматы или го совершенно неинтересны: на конечной доске с конечной продолжительностью партии и с полной информацией выигрышную (или беспроигрышную, если выигрышной нет) стратегию можно "легко" подсчитать простым перебором вариантов. Игры, которые будем рассматривать мы, тоже обычно подразумевают конечное (или в теории непрерывное, но в реальности все равно конечное, как множество возможных цен, которые игрок может объявить на аукционе) множество возможных стратегий. Но при этом информация
принципиально будет неполной; об этом и вся теория. В нашем понимании стратегической игры все игроки будут действовать одновременно, и выигрыш каждого будет зависеть от того, какие стратегии изберут все остальные. Определение 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.3
. Рассмотрим рынок некоего продукта, на котором находятся ровно две фирмы: 1. Бузуверова Н.В., Дьяченко М.Е. Отечественная история: вопросы и ответы. Учебное пособие. Магнитогорск: ГОУ ВПО «МГТУ», 2006. 2. Мунчаев Ш.М., Устинов В.М. История России. Учебник для вузов. М., 2005. 3. История России с древнейших времен до конца XX в.: Учебное пособие для студентов вузов. М., 2007. 4. _______________________________________________________________________ 5. _______________________________________________________________________ Уважаемые студенты.
Вам нужно прочитать лекции, разобраться в них и выполнить задания-примеры (стр. 17) в EXCEL. Это и будет Ваша контрольная работа. Результаты оформить как обычную контрольную с выводом рабочих листов на бумажный носитель (изменить размер и типы шрифта). Каждый будет защищать свою контрольную индивидуально. Можно сбросить программы с решением на флешку. ЛЕКЦИИ ПО ТЕОРИИ ИГР
Теория игр в контексте теории принятия решений Рассмотренные до сих пор задачи формулировались и решались, в основном, в предположении наличия полной информации. Их можно отнести к совокупности задач принятия решений в условиях определенности. В реальных экономических условиях, однако, часто приходится действовать при ограниченности, неточности исходной информации о самом объекте и внешней среде, в которой он функционирует. При принятии управленческих решений, влияющих на функционирование и развитие экономического объекта, необходимо учитывать важнейшую характеристику внешней среды – неопределенность. Под неопределенностью следует понимать отсутствие, неполноту, недостаточность информации об объекте, процессе, явлении или неуверенность в достоверности информации. В экономической сфере имеется множество источников возникновения неопределенности для систем самого различного уровня сложности и масштабов. Неопределенность обуславливает появление ситуаций, не имеющих однозначного исхода (решения). Среди тех из них, с которыми в процессе производства сталкиваются предприятия, особое место занимают ситуации риска. Ситуации риска сопутствуют три условия: · наличие неопределенности; · необходимость выбора альтернативы; · возможность оценить вероятность осуществления выбираемых альтернатив. Таким образом, ситуация риска характеризуется возможностью количественного и качественного определения степени вероятности того или иного варианта развития событий. Экономический риск предстает в виде совокупности вероятных экономических, политических, нравственных и других последствий (как благоприятных, так и неблагоприятных), которые могут наступить при реализации выбранных решений. Существуют различные виды неопределенности, в частности: · количественная, обусловленная значительным числом объектов или элементов в ситуации; · информационная, вызванная недостатком информации или ее неточностью по техническим, социальным и другим причинам; · стоимостная из-за слишком дорогой или недоступной платы за определенность; · профессиональная как следствие недостаточного профессионализма ЛПР (не учитывается, например, требуемое количество влияющих факторов); · ограничительная (вызванная ограничениями в ситуации принятия решений, например ограничения по времени и др.); · внешней среды, связанная с поведением среды или реакцией конкурента на процесс принятия решения. Природа риска в рыночной экономике обусловлена следующими факторами: · ограниченной сферой государственного регулирования хозяйственной деятельности; · усилением роли случайных факторов во взаимодействии предприятия с внешней средой; · частной (и ее видами) собственностью предпринимателя, ее владением, пользованием, распоряжением; · конкурентной борьбой товаропроизводителей и других хозяйствующих субъектов; · всеобъемлющим характером риска, распространяющимся на сферы общественной жизни, как производственную, так и непроизводственную. Он имеет место на этапах производства, продажи, закупки и др. Рыночные отношения порождают различные виды рисковых ситуаций, более того, в работе предприятий риск становится необходимым и обязательным компонентом. Для иллюстрации различия между ситуациями, когда приходится принимать решения в условиях риска или в условиях неопределенности, рассмотрим задачу оптимального выбора ассортимента выпускаемой продукции. В условиях риска доход от реализации единицы продукции не является фиксированной величиной. Это – случайная величина, точное численное значение которой неизвестно, но описывается с помощью известной функции распределения . В условиях неопределенности функция распределения неизвестна. Вообще говоря, неопределенность не означает полного отсутствия информации о задаче. Например, может принимать некоторое число определенных значений, но вероятности этих значений неизвестны. Таким образом, с точки зрения полноты исходных данных определенность и неопределенность представляют два крайних случая, а риск определяет промежуточную ситуацию. Уровень имеющейся информации о проблеме определяет, каким образом может быть формализована и решена задача принятия решения. При решении задач в условиях неопределенности внешней среды наиболее часто возникают две ситуации. При первой сама система препятствует принятию решений (задачи “природной неопределенности” – например, задача производства сельскохозяйственной продукции на некоторой территории, когда неизвестны погодные условия предстоящего сезона). В этой ситуации природа может рассматриваться как доброжелательный противник, в том смысле, что она не преследует целей, противоположных целям человека. Во второй ситуации возможно наличие конкуренции, когда два или более участника находятся в конфликте, и каждый стремится, как можно больше, выиграть у конкурента (конкурентов). В этом случае лицу, принимающему решения, противостоит мыслящий противник. Для ситуаций этого типа (называемых конфликтными) характерно, что эффективность решений, принимаемой каждой из сторон, существенно зависит от действий другой стороны. При этом ни одна из сторон не может полностью контролировать положение. Например, при определении объема выпуска продукции на одном предприятии нельзя не учитывать размеров выпуска аналогичной продукции на других предприятиях. В реальных условиях часто также возникают ситуации, в которых антагонизм отсутствует, но необходимо учитывать противоположные тенденции. Например, для нормального функционирования производства, с одной стороны, необходимо наличие запасов разнообразных ресурсов, но с другой, их хранение вызывает появление дополнительных расходов. Раздел математики, изучающий конфликтные ситуации на основе их математических моделей, называется теорией игр
. Можно также сказать, что теория игр - математическая теория конфликтных ситуаций, разрабатывающая рекомендации по наиболее рациональному образу действий каждого из участников в ходе конфликтной ситуации, т.е. таких действий, которые обеспечивали бы ему наилучший результат. Игровые схемы можно применять во многих экономических ситуациях. Выигрышем могут при этом выступать величина прибыли, себестоимость, эффективность использования дефицитных ресурсов, производственных фондов, и т.д. Существенным обстоятельством является то, что методы и рекомендации теории игр разработаны применительно к таким конфликтным ситуациям, которые обладают свойством многократной повторяемости. Если конфликтная ситуация реализуется однократно или ограниченное число раз, то рекомендации теории игр становятся малоэффективными. Анализ реальной конфликтной ситуации требует ее существенного (иногда радикального) упрощения – учета лишь наиболее существенных для конфликта факторов. В связи с этим, можно рассматривать игру как упрощенную математическую модель конфликтной ситуации, характеризующуюся наличием определенных правил. Эти правила устанавливают: · выбор образа действия игроков на каждом этапе игры; · информацию, которой обладает каждый игрок при осуществлении таких выборов; · плату для каждого игрока после завершения любого этапа игры. Стратегией игры называется совокупность правил, определяющих поведение игрока на протяжении всей игры. Стратегии каждого игрока определяют результаты или платежи в игре; при этом каждый игрок имеет некоторое множество (конечное или бесконечное) возможных стратегий. К числу определяющих характеристик игр можно отнести следующие: · имеется конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают; · сформулированы правила выбора допустимых стратегий, известные игрокам; · определен набор возможных конечных состояний игры (например, выигрыш, проигрыш, ничья); · всем участникам игры (игрокам) заранее известны платежи, соответствующие каждому возможному конечному состоянию. Конфликтные ситуации, встречающиеся в практике, порождают различные виды игр. Классификация игр возможна по разным признакам. А) По количеству игроков. В игре может принимать участие любое конечное число игроков. Если игроков всего двое, или игроки объединяются в две группы, преследующие противоположные цели, то имеет место парная игра. В зависимости от количества стратегий в игре они делятся на конечные и бесконечные. Б) В зависимости от взаимоотношений участников различают бескоалиционные (участники не имеют права заключать соглашения) и коалиционные игры (иногда используются синонимы – некооперативные и кооперативные игры соответственно). В) По характеру выигрышей игры делятся на игры с нулевой суммой и ненулевой суммой. В играх с нулевой суммой общий капитал игроков не меняется, а лишь перераспределяется в ходе игры, в связи с чем сумма выигрышей равна нулю (при этом проигрыш рассматривается как отрицательный выигрыш). В играх с ненулевой суммой сумма выигрышей отлична от нуля. Г) По виду функции выигрыша игры делятся на матричные, биматричные и др. В матричных играх (при двух участниках) выигрыши первого игрока задаются матрицей, в биматричных – выигрыши каждого игрока задаются своей матрицей. Д) По количеству ходов игры делятся на одноходовые (выигрыш распределяется после одного хода каждого игрока) и многоходовые (выигрыш распределяется после нескольких ходов). Стратегия игрока называется оптимальной, если она обеспечивает данному игроку при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш, независимо от поведения противника. В дальнейшем мы ограничимся рассмотрением парных матричных игр с нулевой суммой. Задание стратегий двух игроков в парной игре такого типа полностью определяет ее исход, т.е. выигрыш одного или проигрыш другого. Как уже отмечалось, результаты конечной парной игры с нулевой суммой можно задавать матрицей, строки и столбцы которой соответствуют различным стратегиям 1-го и 2-го игроков соответственно, а ее элементы - выигрышам одной стороны (равные проигрышам другой). Эта матрица называется платежной матрицей или матрицей игры. Возникшая в сороковых годах XX века математическая теория игр чаще всего применяется именно в экономике. Но как с помощью концепции игр смоделировать поведение людей в обществе? Зачем экономисты изучают, в какой угол чаще бьют пенальти футболисты, и как выиграть в «Камень, ножницы, бумагу» в своей лекции рассказал старший преподаватель кафедры микроэкономического анализа ВШЭ Данил Федоровых. Игра - это любая ситуация, в которой прибыль агента зависит не только от его собственных действий, но и от поведения остальных участников. Если вы раскладываете дома пасьянс, с точки зрения экономиста и теории игр, это не игра. Она подразумевает обязательное наличие столкновения интересов. В фильме «Игры разума» о Джоне Нэше, нобелевском лауреате по экономике, есть сцена с блондинкой в баре. В ней показана идея, за которую ученый и получил премию, - это идея равновесия по Нэшу, которое он сам называл управляющей динамикой. Стратегия - описание действий игрока во всех возможных ситуациях. Исход - комбинация выбранных стратегий. Итак, с точки зрения теории, игроками в этой ситуации являются только мужчины, то есть те, кто принимает решение. Их предпочтения просты: блондинка лучше брюнетки, а брюнетка лучше, чем ничего. Действовать можно двумя способами: пойти к блондинке или к «своей» брюнетке. Игра состоит из единственного хода, решения принимаются одновременно (то есть нельзя посмотреть, куда пошли остальные, и после походить самому). Если какая-то девушка отвергает мужчину, игра заканчивается: невозможно вернуться к ней или выбрать другую. Каков вероятный финал этой игровой ситуации? То есть какова ее устойчивая конфигурация, из которой все поймут, что сделали лучший выбор? Во-первых, как правильно замечает Нэш, если все пойдут к блондинке, ничем хорошим это не кончится. Поэтому дальше ученый предполагает, что всем нужно пойти к брюнеткам. Но тогда, если известно, что все пойдут к брюнеткам, ему следует идти к блондинке, ведь она лучше. В этом и заключается настоящее равновесие - исход, в котором один идет к блондинке, а остальные - к брюнеткам. Может показаться, что это несправедливо. Но в ситуации равновесия никто не может пожалеть о своем выборе: те, кто пойдут к брюнеткам, понимают, что от блондинки они все равно ничего б не получили. Таким образом, равновесие по Нэшу - это конфигурация, при которой никто по отдельности не хочет менять выбранную всеми стратегию. То есть, рефлексируя в конце игры, каждый участник понимает, что даже зная, как походят другие, он сделал бы то же самое. По-другому можно назвать это исходом, где каждый участник оптимальным образом отвечает на действия остальных. Рассмотрим другие игры на предмет равновесия. Например, в «Камне, ножницах, бумаге» нет равновесия по Нэшу: во всех ее вероятных исходах нет варианта, в котором оба участника были бы довольны своим выбором. Тем не менее, существует Чемпионат мира и World Rock Paper Scissors Society, собирающее игровую статистику. Очевидно, что вы можете повысить свои шансы на победу, если будете что-то знать об обычном поведении людей в этой игре. Чистая стратегия в игре - это такая стратегия, при которой человек всегда играет одинаково, выбирая одни и те же ходы.
По данным World RPS Society, камень является самым часто выбираемым ходом (37,8%). Бумагу ставят 32,6%, ножницы - 29,6%. Теперь вы знаете, что нужно выбирать бумагу. Однако, если вы играете с тем, кто тоже это знает, вам уже не надо выбирать бумагу, потому что от вас ожидается то же самое. Есть знаменитый случай: в 2005 году два аукционных дома Sotheby“s и Christie”s решали, кому достанется очень крупный лот - коллекция Пикассо и Ван Гога со стартовой ценой в 20 миллионов долларов. Собственник предложил им сыграть в «Камень, ножницы, бумагу», и представители домов отправили ему свои варианты по электронной почте. Sotheby“s, как они позже рассказали, особо не задумываясь, выбрали бумагу. Выиграл Christie”s. Принимая решение, они обратились к эксперту - 11-летней дочери одного из топ-менеджеров. Она сказала: «Камень кажется самым сильным, поэтому большинство людей его выбирают. Но если мы играем не с совсем глупым новичком, он камень не выбросит, будет ожидать, что это сделаем мы, и сам выбросит бумагу. Но мы будем думать на ход вперед, и выбросим ножницы». Таким образом, вы можете думать на ход вперед, но это не обязательно приведет вас к победе, ведь вы можете не знать о компетенции вашего соперника. Поэтому иногда вместо чистых стратегий правильнее выбирать смешанные, то есть принимать решения случайно. Так, в «Камне, ножницах, бумаге» равновесие, которое мы до этого не нашли, находится как раз в смешанных стратегиях: выбирать каждый из трех вариантов хода с вероятностью в одну третью. Если вы будете выбирать камень чаще, соперник скорректирует свой выбор. Зная это, вы скорректируете свой, и равновесия не выйдет. Но никто из вас не начнет менять поведение, если каждый просто будет выбирать камень, ножницы или бумагу с одинаковой вероятностью. Все потому что в смешанных стратегиях по предыдущим действиям невозможно предугадать ваш следующий ход. Более серьезных примеров смешанных стратегий очень много. Например, куда подавать в теннисе или бить/принимать пенальти в футболе. Если вы ничего не знаете о вашем сопернике или просто постоянно играете против разных, лучшей стратегией будет поступать более-менее случайно. Профессор Лондонской школы экономики Игнасио Паласиос-Уэрта в 2003 году опубликовал в American Economic Review работу, суть которой заключалась в поиске равновесия по Нэшу в смешанных стратегиях. Предметом исследования Паласиос-Уэрта выбрал футбол и в связи с этим просмотрел более 1400 ударов пенальти. Разумеется, в спорте все устроено хитрее, чем в «Камне, ножницах, бумаге»: там учитывается сильная нога спортсмена, попадания в разные углы при ударе со всей силы и тому подобное. Равновесие по Нэшу здесь заключается в расчете вариантов, то есть, к примеру, определении углов ворот, в которые надо бить, чтобы выиграть с большей вероятностью, зная свои слабые и сильные стороны. Статистика по каждому футболисту и найденное в ней равновесие в смешанных стратегиях, показало, что футболисты поступают примерно так, как предсказывают экономисты. Вряд ли стоит утверждать, что люди, которые бьют пенальти, читали учебники по теории игр и занимались довольно непростой математикой. Скорее всего, есть разные способы научиться оптимально себя вести: можно быть гениальным футболистом, и чувствовать, что делать, а можно - экономистом, и искать равновесие в смешанных стратегиях. В 2008 году профессор Игнасио Паласиос-Уэрта познакомился с Авраамом Грантом, тренером «Челси», который играл тогда в финале Лиги чемпионов в Москве. Ученый написал записку тренеру с рекомендациями по серии пенальти, которые касались поведения вратаря соперника - Эдвина ван дер Сара из «Манчестер Юнайтед». Например, по статистике, он почти всегда отбивал удары на среднем уровне и чаще бросался в естественную для пробивающего пенальти сторону. Как мы определили выше, правильнее все-таки рандомизировать свое поведение с учетом знаний о сопернике. Когда счет по пенальти был уже 6:5, Николя Анелька, нападающий «Челси», должен был забивать. Показывая перед ударом в правый угол, ван дер Сар будто спросил у Анелька, не собирается ли он бить туда. Суть в том, что все предыдущие удары «Челси» были нанесены именно в правый от пробивающего угол. Мы не знаем точно почему, может быть, из-за консультации экономиста бить в неестественную для них сторону, ведь по статистике к этому менее готов ван дер Сар. Большинство футболистов «Челси» были правшами: ударяя в неестественный для себя правый угол, все они, кроме Терри, забивали. Видимо, стратегия была в том, чтобы Анелька пробил туда же. Но ван дер Сар, похоже, это понял. Он поступил гениально: показал в левый угол дескать «туда собрался бить?», от чего Анелька, наверное, пришел в ужас, ведь его разгадали. В последний момент он принял решение действовать по-другому, ударил в естественную для себя сторону, что и было нужно ван дер Сару, который взял этот удар и обеспечил «Манчестеру» победу. Эта ситуация учит случайному выбору, ведь в ином случае ваше решение может быть просчитано, и вы проиграете. Наверное, самая известная игра, с которой начинаются университетские курсы о теории игр, - это «Дилемма заключенного». По легенде двух подозреваемых в серьезном преступлении поймали и заперли в разные камеры. Есть доказательство, что они хранили оружие, и это позволяет посадить их на какой-то небольшой срок. Однако доказательств, что они совершили это страшное преступление, нет. Каждому по отдельности следователь рассказывает об условиях игры. Если оба преступника сознаются, оба же сядут на три года. Если сознается один, а подельник будет молчать, сознавшийся выйдет сразу, а второго посадят на пять лет. Если, наоборот, первый не сознается, а второй его сдаст, первый сядет на пять лет, а второй выйдет сразу. Если же не сознается никто, оба сядут на год за хранение оружия. Равновесие по Нэшу здесь заключается в первой комбинации, когда оба подозреваемых не молчат и оба садятся на три года. Рассуждения каждого таковы: «если я буду говорить, я сяду на три года, если молчать - на пять лет. Если второй будет молчать, мне тоже лучше говорить: не сесть лучше, чем сесть на год». Это доминирующая стратегия: говорить выгодно, независимо от того, что делает другой. Однако в ней есть проблема - наличие варианта получше, ведь сесть на три года хуже, чем сесть на год (если рассматривать историю только с точки зрения участников и не учитывать вопросы морали). Но сесть на год невозможно, ведь, как мы поняли выше, молчать обоим преступникам невыгодно. Есть известная метафора про невидимую руку рынка, принадлежащая Адаму Смиту. Он говорил, что если мясник будет сам для себя стараться заработать деньги, от этого будет лучше всем: он сделает вкусное мясо, которое купит булочник на деньги от продажи булок, которые он, в свою очередь, тоже должен будет делать вкусными, чтобы они продавались. Но оказывается, эта невидимая рука не всегда работает, и таких ситуаций, когда каждый действует за себя, а всем плохо, очень много. Поэтому иногда экономисты и специалисты по теории игр думают не об оптимальном поведении каждого игрока, то есть не о равновесии по Нэшу, а об исходе, при котором будет лучше всему обществу (в «Дилемме» общество состоит из двух преступников). С этой точки зрения, исход эффективен, когда в нем нет улучшения по Парето, то есть невозможно сделать кому-то лучше, не сделав при этом хуже другим. Если люди просто меняются товарами и услугами, это Парето-улучшение: они делают это добровольно, и вряд ли кому-то от этого плохо. Но иногда, если просто дать людям взаимодействовать и даже не вмешиваться, то, к чему они придут, не будет оптимальным по Парето. Это и происходит в «Дилемме заключенного». В ней, если мы даем каждому действовать так, как им выгодно, оказывается, что всем от этого плохо. Всем было бы лучше, если бы каждый действовал не оптимально для себя, то есть молчал. «Дилемма заключенного» - это игрушечная стилизованная история. Вряд ли вы ожидаете оказаться в подобной ситуации, но похожие эффекты есть везде вокруг нас. Рассмотрим «Дилемму» с большим количеством игроков, ее иногда называют трагедией общины. Например, на дорогах - пробки, и я решаю, как ехать на работу: на машине или на автобусе. Это же делают остальные. Если я поеду на машине, и все решат сделать то же самое, будет пробка, но мы доедем с комфортом. Если я поеду на автобусе, пробка-то все равно будет, но ехать я буду некомфортно и не особо быстрее, поэтому такой исход еще хуже. Если же в среднем все ездят на автобусе, то я, сделав то же самое, довольно быстро доеду без пробки. Но если при таких условиях поехать на машине, я тоже доеду быстро, но еще и с комфортом. Итак, наличие пробки не зависит от моих действий. Равновесие по Нэшу здесь - в ситуации, когда все выбирают ехать на машине. Что бы не делали остальные, мне лучше выбрать машину, потому что будет там пробка или нет, неизвестно, но я в любом случае доеду с комфортом. Это доминирующая стратегия, поэтому в итоге все едут на машине, и мы имеем то, что имеем. Задача государства - сделать поездку на автобусе лучшим вариантом хотя бы для некоторых, поэтому появляются платные въезды в центр, парковки и так далее. Другая классическая история - рациональное незнание избирателя. Представьте, что вы не знаете исход выборов заранее. Вы можете изучить программу всех кандидатов, послушать дебаты и после проголосовать за самого лучшего. Вторая стратегия - прийти на участок и проголосовать как попало или за того, кого чаще показывали по телевизору. Какое поведение оптимально, если от моего голоса никогда не зависит, кто выиграет (а в 140-миллионной стране один голос никогда ничего не решит)? Конечно, я хочу, чтобы в стране был хороший президент, но я же знаю, что никто больше не будет изучать программы кандидатов внимательно. Поэтому не тратить на это время - доминирующая стратегия поведения. Когда вас призывают прийти на субботник, ни от кого в отдельности не будет зависеть, станет двор чистым или нет: если я выйду один, я не смогу убрать все, или, если выйдут все, то не выйду я, потому что все и без меня уберут. Другой пример - перевозка грузов в Китае, о котором я узнал в замечательной книге Стивена Ландсбурга «Экономист на диване». 100-150 лет назад в Китае был распространен способ перевозки грузов: все складывалось в большой кузов, который тащили семь человек. Заказчики платили, если груз доставлялся вовремя. Представьте, что вы - один из этих шести. Вы можете прилагать усилия, и тянуть изо всех сил, и если все будут так делать, груз доедет вовремя. Если кто-нибудь один так делать не будет, все тоже доедут вовремя. Каждый думает: «Если все остальные тянут как следует, зачем это делать мне, а если все остальные тянут не со всей силы, то я ничего не смогу изменить». В итоге, со временем доставки все было очень плохо, и сами грузчики нашли выход: они стали нанимать седьмого и платить ему деньги за то, чтобы он стегал лентяев плетью. Само наличие такого человека заставляло всех работать изо всех сил, потому что иначе все попадали в плохое равновесие, из которого никому в отдельности с выгодой не выйти. Такой же пример можно наблюдать в природе. Дерево, растущее в саду, отличается от того, что растет в лесу, своей кроной. В первом случае она окружает весь ствол, во втором - находится только вверху. В лесу это является равновесием по Нэшу. Если бы все деревья договорились и выросли одинаково, они бы поровну распределили количество фотонов, и всем было бы лучше. Но никому в отдельности так делать невыгодно. Поэтому каждое дерево хочет вырасти немного выше окружающих. Во многих ситуациях одному из участников игры может понадобиться инструмент, который убедит остальных, что тот не блефует. Он называется commitment device. Например, закон некоторых стран запрещает платить выкуп похитителям людей, чтобы снизить мотивацию преступников. Однако это законодательство часто не работает. Если вашего родственника захватили, и у вас есть возможность спасти его, обойдя закон, вы это сделаете. Представим ситуацию, что закон можно обойти, но родственники оказались бедными и выкуп им платить нечем. У преступника в этой ситуации два пути: отпустить или убить жертву. Убивать он не любит, но тюрьму он не любит больше. Отпущенный пострадавший, в свою очередь, может либо дать показания, чтобы похититель был наказан, либо молчать. Самый лучший исход для преступника: отпустить жертву, которая его не сдаст. Жертва же хочет быть отпущенной и дать показания. Равновесие здесь в том, что террорист не хочет быть пойманным, а значит, жертва погибает. Но это не равновесие по Парето, потому что существует вариант, при котором всем лучше - жертва на свободе хранит молчание. Но для этого надо сделать так, чтобы молчать ей было выгодно. Где-то я прочитал вариант, когда она может попросить террориста устроить эротическую фотосессию. Если преступника посадят, его подельники выложат фотографии в интернет. Теперь, если похититель останется на свободе - это плохо, но фотографии в открытом доступе - еще хуже, поэтому получается равновесие. Для жертвы это способ остаться в живых. Модель Бертрана
Раз уж мы говорим об экономике, рассмотрим экономический пример. В модели Бертрана два магазина продают один и тот же товар, покупая его у производителя по одной цене. Если цены в магазинах одинаковы, то примерно одинакова и их прибыль, ведь тогда покупатели выбирают магазин случайно. Единственное равновесие по Нэшу здесь - продавать товар по себестоимости. Но магазины хотят зарабатывать. Поэтому если один поставит цену 10 рублей, второй снизит ее на копейку, увеличив тем самым свою выручку вдвое, так как к нему уйдут все покупатели. Поэтому участникам рынка выгодно снижать цены, распределяя тем самым прибыль между собой. Разъезд на узкой дороге
Рассмотрим примеры выбора между двумя возможными равновесиями. Представьте, что Петя и Маша едут навстречу друг другу по узкой дороге. Дорога настолько узкая, что им обоим нужно съехать на обочину. Если они решат повернуть налево или направо от себя, они просто разъедутся. Если же один повернет направо, а другой налево от себя, или наоборот, случится авария. Как выбрать, куда съехать? Чтобы помогать искать равновесие в подобных играх, существуют, например, правила дорожного движения. В России каждому нужно повернуть направо. В забаве Chiken, когда два человека едут на большой скорости навстречу друг другу, тоже есть два равновесия. Если оба сворачивают на обочину, возникает ситуация, которая называется Chiken out, если оба не сворачивают, то погибают в страшной аварии. Если я знаю, что мой соперник едет прямо, мне выгодно съехать, чтобы выжить. Если я знаю, что мой соперник съедет, то мне выгодно ехать прямо, чтобы после получить 100 долларов. Сложно предсказать, что случится на самом деле, однако, у каждого из игроков есть свой метод выиграть. Представьте, что я закрепил руль так, что его нельзя повернуть, и показал это своему сопернику. Зная, что у меня нет выбора, соперник отскочит. QWERTY-эффект
Иногда бывает очень сложно перейти из одного равновесия в другое, даже если оно означает пользу для всех. Раскладка QWERTY была создана, чтобы замедлить скорость печати. Поскольку если бы все печатали слишком быстро, головки печатной машинки, которые бьют по бумаге, цеплялись бы друг за друга. Поэтому Кристофер Шоулз разместил часто стоящие рядом буквы на максимально далеком расстоянии. Если вы зайдете в настройки клавиатуры на своем компьютере, вы сможете выбрать там раскладку Dvorak и печатать гораздо быстрее, так как сейчас нет проблемы аналоговых печатных машин. Дворак рассчитывал, что мир перейдет на его клавиатуру, но мы по-прежнему живем с QWERTY. Конечно, если бы мы перешли на раскладку Дворака, будущее поколение было бы нам благодарно. Все мы приложили бы усилия и переучились, в результате вышло бы равновесие, в котором все печатают быстро. Сейчас мы тоже в равновесии - в плохом. Но никому не выгодно быть единственным, кто переучится, потому что за любым компьютером, кроме личного, работать будет неудобно.3. Дилемма заключенного
—
Кооперация
Отказ от кооперации
Кооперация
3, 3
0, 5
Отказ от кооперации
5, 0
1, 1
Равновесие по Нэшу.
A
B
C
A
0, 0
25, 40
5, 10
B
40, 25
0, 0
5, 15
C
10, 5
15, 5
10, 10
Фирма 1
Фирма 2
Низкий уровень загрязнения
Высокий уровень загрязнения
Низкий уровень загрязнения
А
100,100
В
-30,120
Высокий уровень загрязнения
С
120,-30
D
100,100
Пример решения матричной игры в чистых стратегиях
Задача.
Предприятие 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
Решение задачи
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. Критерий ожидаемого значения.
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
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
3. Критерий предельного уровня
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
Принятие решений в условиях неопределенности
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
Классические критерии принятия решений
1. Минимаксный критерий.
2. Критерий Байеса—Лапласа.
3. Критерий Сэвиджа.
4. Пример и выводы.
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. Критерий Гурвица.
2. Критерий Ходжа–Лемана.
3. Критерий Гермейера.
4. Объединенный критерий Байеса-Лапласа и минимакса.
5. Критерий произведений.
Пример.
||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
∑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
||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
||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
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
. Это далеко не всегда так, и в "Теоремы Эрроу и Гиббарда-Саттертуэйта" мы еще поговорим об интересных эффектах, возникающих, когда предпочтения так выразить нельзя. Но для базовой теории игр
придется это предположение все-таки сделать.
стоят исходы . В случае игры с двумя игроками эта конструкция превращается в самую обычную матрицу.
.
Рис.
1.1.
. Стратегия каждого из участников - количество продукта, которое он производит: 
.Джон Нэш и блондинка в баре
«Камень, ножницы, бумага»
Смешанные стратегии и спорт
«Дилемма заключенного»
Улучшение по Парето
Трагедия общины
Сommitment device
Другие примеры игр:
