ДНЕВНИК СТУДЕНТКИ: Равновесие Нэша и визуальная репрезентация игр

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

Отцы Теории Игр Джон фон Нейман и Оскар Моргенштерн долгое время находились в процессе поиска главной теории, которую можно применить для решения всех социальных проблем.

Сегодня ни для кого не секрет, что знаменитый гениальный американский математик Джон Нэш решил эту проблему и стал лауреатом Нобелевской премии по экономике. Всем, кто еще не смотрел потрясающий фильм Игры Разума (Beautiful Mind) c Расселом Кроу в роли Джона Нэша, советую его посмотреть, не пожалеете.

Удивительно, что Нэш нашел ответ в чашке кофе.

Равновесие Нэша (Nash Equilibrium)

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

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

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

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

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

У нас есть 3 маршрута из города А в город Б. По этому маршруту ездят 150 машин.

Число в скобках = длина пути.
Время в пути = (длина пути) + (количество машин на маршруте)
Выигрыш = -(время в пути)

Свойство равновесия Нэша говорит нам, что

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

Для данной ситуации Равновесием Нэша будет распределение машин по трем маршрутам первый 0 машин, второй 50 машин и третий 100 машин (красным цветом на схеме).
Посчитайте сами. Попробуйте переместить машину на другой маршрут - ага, как ни крути, а дольше ехать :) Правда интересно?

Удивительно, но это правило применимо ко всем социальным проблемам.
Условно принято записывать этот закон так:

Визуальная репрезентация игр

Существует 2 формы записи игр во время анализа: Игры в нормальной форме и Игры в развернутой форме.

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

Определяем множество игроков
Определяем множество стратегий
Определяем выигрыши

Рассмотрим классический пример из Теории Игр "Битва полов"

Муж и жена решают, как провести вечер.

жена хочет пойти на балет
муж хочет пойти на футбол

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

А можно записать все проще, в виде матрицы

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

отношения - это повторяющая игра и можно договориться на 2 раунда вперед - сначала на футбол, а в следующий вечер - на балет :)

Развернутая форма (дерево) - включает в себя тайминг по которому совершаются действия

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

Давайте рассмотрим классический пример из Теории Игр "Экзамен"

На экзамене студент не может решить задачу.

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

Платежи игроков

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

Запись в развернутой форме будет выглядеть так

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

Из этой схемы становится очевидно, что лучше не списывать :)

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

Напомню, что информацию для этого материала я получила в процессе изучения Теории Игр в следующих онлайн-курсах:

Game Theory, Stanford University, The University of British Columbia Matthew O. Jackson, Professor, Economics; Kevin Leyton-Brown, Professor, Computer Science; Yoav Shoham, Professor, Computer Science
Теория игр (Game Theory), Высшая школа экономики Dmitry Dagaev, Associate Professor, Deputy Vice Rector, Department of Higher Mathematics
Теория игр, Московский физико-технический институт Савватеев Алексей Владимирович, Доктор физико-математических наук, Профессор кафедры дискретной математики МФТИ
Welcome to Game Theory, The University of Tokyo Michihiro Kandori, Professor, Faculty of Economics

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

Надеюсь вам было интересно это читать и вы подпишитесь на мой дневник!

@studentka