Академия. Теория игр. Неделя 7.
После долгого-долгого перерыва с радостью и некоторым опасением продолжаю изучение курса "Теории игр" проекта Академия от @ontofractal. С радостью от того, что соскучился по всем этим замысловатым стратегиям и равновесиям, с опасением - потому что вдруг всё успел позабыть. Но поскольку не попробуешь - не узнаешь, остаётся только одно - идти вперёд!
ИГРЫ С НЕСОВЕРШЕННОЙ ИНФОРМАЦИЕЙ: ТЕОРИЯ
До этого момента мне приходилось рассматривать решение игр, в которых все игроки чудесным образом в любой момент времени знали стратегии своих противников. Но на самом деле в реальной жизни такое случается крайне редко, обычно в качестве примеров к курсу "Теории игр" ))) Сегодня мне предстоит разобраться с ситуациями, когда один из игроков не знает, в какой вершине дерева игры он оказался.
Для этого мне надо вернуться к "Битве полов":
Пусть муж делает свой выбор немного раньше, чем его жена. А она не знает результата его выбора. То есть жена не представляет в какой же вершине дерева игры она сейчас оказалась - В или С?
Чтобы идти далее мне понадобится следующее определение:
Если все информационные множества игроков состоят из одной единственной вершины, то такая игра называется игрой с совершенной информацией. И если хотя бы у одного игрока есть хотя бы одно информационное множество с более, чем одной вершиной, то это уже будет игра с несовершенной информацией.
У жены одно информационное множество, состоящее из двух вершин - В и С. У мужа информационное множество тоже в единственном числе, но, в отличии от множества жены, оно состоит из одной вершины - А. Теперь жене предстоит сделать выбор в целом информационном множестве, а не в конкретной вершине (что свойственно для игр с совершенной информацией), поскольку она не знает, что выбрал муж.
Исходя из вышеизложенного можно сдать новое определение термину "стратегия": это набор действий игрока во всех информационных множествах, в которых ему принадлежит ход. Множество стратегий мужа, как и множество стратегий жены, включает два действия: пойти на футбол или пойти на балет.
Теперь необходимо уточнить значение термина "подыгра". В играх с совершенной информацией это была часть дерева игры, начинающаяся в нетерминальных вершинах. В нашем случае возможны такие ситуации, при которых информационное множество одного из игроков частично находится в этой части дерева, а частично в него не входит. То есть назвать этот фрагмент подыгрой уже нельзя, так как игрок не может быть уверенным в том, что находится в этой подыгре. Поэтому подыгрой теперь будет называться такое поддерево, для которого любое информационное множество, пересекающееся с ним, полностью лежит в нём. В рассматриваемой "Битве полов" такой единственной подыгрой будет сама игра.
В итоге у меня появилась возможность представлять в развёрнутой форме более широкий класс игр и, в частности, игры в нормальной форме.
ИГРЫ С НЕСОВЕРШЕННОЙ ИНФОРМАЦИЕЙ: ПРИМЕРЫ
В чём фишка игр с несовершенной информацией? Они помогают моделировать реальные жизненные ситуации, делая их нагляднее, а, значит, и понятнее.
Исторический сюжет: Часть армии Наполеона преследует отступающую прусскую армия, которая стремится соединиться с британскими войсками. Наполеон отправляет маршалу Груши, командующему преследователями, записку с приказом отступать для соединение с основными силами французов.
Построю игровую модель ситуации. Наполеон решает: отправлять записку (З) или не отправлять (Н). Если записка не отправлена, то он просто отступает (О), в противном случае опять принимает решение: ждать Груши (Ж) или отступать (О). Груши, пока до него не добралась записка Наполеона, делает свой выбор: вступать в бой с прусской армией (Б) или вернуться к Наполеону (В).
Возможные платежи Наполеона:
1) наибольший - записка отправлена, Груши вернулся, армия объединилась,
2) меньше - отступить (или не посылать записку), при условии, что Груши дал бой прусской армии,
3) ещё меньше - отступить (или не посылать записку), при условии, что Груши возвращается,
4) наименьший - ждать Груши, а тот не возвращается.
Возможные платежи Груши:
1) наибольший - записка отправлена, получена, Груши возвращается, Наполеон его ждёт,
2) меньше - дать бой, при условии, что Наполеон отступил (или при условии, что записка не отправлена),
3) ещё меньше - вернуться, при условии, что Наполеон отступил (или при условии, что записка не отправлена),
4) наименьший - дать бой, при условии, что Наполеон его ждёт.
У Наполеона два информационных множества: первое состоит из одной вершины, второе - из двух. Его возможные стратегии: ЗЖ, ЗО, НЖ, НО. У Груши - одно информационное множество и всего две возможные стратегии: В, Б.
Рассмотрю матрицу игры и найду все равновесия Нэша:
Видно, что их целых четыре! Но в реальности французы разыграли иную стратегию: Наполеон отправил записку, но Груши уже вступил в бой, а Наполеон остался его ждать. То есть они получили наименьшие из возможных платежей.
Другая ситуация. В некотором царстве-государстве царь решает: собирать ему с подданных высокие налоги (В) или низкие (Н). Местный губернатор при этом стоит перед выбором: добавить к царским налогам ещё и свои (С) или не добавлять (Н). В результате этой экономической политики перед народом встаёт выбор: устроить бунт (Б) или нет (Н). Это игра с совершенной информацией.
Платежи участников этой игры устроены следующим образом:
У царя всего две стратегии: В, Н. У губернатора - четыре: СС, СН, НС, НН. Столько же стратегий и у крестьян: ББ, БН, НБ, НН. Проанализирую игру с конца и найду все оптимальные стратегии игроков:
Видно, что умный царь примет решение назначить высокие налоги, умный губернатор - не вводить дополнительных поборов, а умные крестьяне - не бунтовать.
Теперь я изменю условия таким образом, чтобы получилась игра с несовершенной информацией. Пусть крестьяне не знают, кто и в какой пропорции участвует в введении налогов. До них доходит только требуемая сумма. У крестьян возникает одно информационное множество и количество стратегий на нём уменьшается до двух: Б, Н.
Рассмотрю матрицы игры для ситуации, когда царь решает установить высокие налоги и для ситуации, когда налоги - низкие. Найду все равновесия Нэша.
Видно, что всего их пять, и они не всем игрокам приносят оптимальные платежи. Причём, в случае с низкими налогами царя они неизбежно заканчиваются бунтом.
Рассмотрю ещё один вариант этой игры: перед губернатором стоит выбор не по поводу ввода дополнительных налогов (он их не вводит), а по поводу воровства некоторой части из уже собранных (забирать (З) или не забирать (Н)). В этой ситуации крестьяне не знают - честный у них губернатор или обычный.
Найду оптимальные стратегии игроков.
Видно, что царю выгоднее всего установить высокие налоги, губернатору - воровать, а крестьянам - устроить бунт. Почти как у нас (за исключением ситуации с крестьянами).
РОЛЬ ИНФОРМАЦИОННЫХ ПРЕДПОСЫЛОК
Из рассмотренных примеров становится понятна роль информационных предпосылок. Несовершенство информации приводит к тому, что в рассматриваемой игре или возникает много равновесий Нэша с совершенно различными результатами (второй случай) или игроки выбирают не самый благоприятный профиль стратегий (третья ситуация). И только в том случае, когда информация совершенна - и казна полна, и губернатор - вынужден быть приличным человек, и крестьяне мирно пашут землю.
ЧТО ДЛЯ МЕНЯ БЫЛО НАИБОЛЕЕ ИНТЕРЕСНЫМ ИЗ ЭТОЙ НЕДЕЛИ КУРСА
Если в предыдущих занятиях мне приходилось рассматривать стерильные ситуации, когда всё понятно и однозначно, то теперь я подобрался к более сложным задачам, когда не все игроки обладают полной информацией о стратегиях своих противников. Это приблизило теорию игр к реальной жизни, хотя и сделало её восприятие мною несколько сложнее. Но я считаю, что это вполне логично, ведь самые трудные задачи ставит перед нами именно обычная повседневность.