Теория игр - это не только об изучении стратегий в играх, таких как шахматы, го или других. Применять теорию игр уже сегодня пытаются в различных областях: в политике, в спорте, в кибернетике, в психологии и многих других местах. Данная наука выполняет математический анализ ситуаций (в которых сталкиваются интересы нескольких сторон, преследующих различные цели), пытаясь формализовать и описать данные ситуации в виде математической модели, определяющей некоторую игру.
Возникает логичный вопрос: а можно ли с помощью концепций теории игр смоделировать поведение индивидов в обществе?
Недавно я наткнулся на лекцию в интернете, где была поставлена интересная задача, и мне захотелось смоделировать подобную ситуацию (ссылка на видео).
P.S. В данной статье не хотелось бы зацикливаться на программировании, статья направлена на то, чтобы показать, как случайные (и не очень) ошибки могут повлиять на жизнь небольшого выдуманного поселения.
Постановка задачи
Пусть имеется некоторое поселение людей, которое живет вокруг болота. Всего в этом поселение есть 2 типа жителей, которые увлекаются разными хобби (будем раскрашивать таких жителей в разные цвета).
Каждый житель имеет свой уровень счастья, счастье жителя зависит от его соседей. Если сосед жителя увлекается другим хобби, то житель не получается счастья, а за каждого соседа с таким же хобби житель получает +1 очко счастья.
Задача состоит в следующем: как достичь максимального уровня счастья в поселении?
Максимальное счастье поселения может быть рассчитано по формуле: (n-4)*2 + 4. Для поселения из 16 человек: (16-4)*2 + 4 = 28, для 32: (32-4)*2 + 4 = 60. То есть нужно добиться такого состояния поселения, чтобы все жители с одним хобби жили в линию (тогда уровень счастья каждого жителя будет максимальным, как следствие и счастье всей колонии станет максимально возможным)
Каждый день 2 случайных жителя встречаются и обмениваются информацией о своем уровне жизни. А также они решают, стоит ли им поменяться местами. Они могут поменяться местами только в том случае, если уровень счастья хотя бы одного из жителей вырастет, а уровень счастья другого жителя не станет ниже после переезда.
Очевидное решение
Для реализации логики сначала напишем алгоритм, который берет 2 случайные клетки в поселении и сравнивает их на возможность переезда. Для этого сначала рассчитывается счастье одного поселенца в его текущем месте, затем счастье этого жителя в потенциально новом месте. Если его счастье изменилось в лучшую сторону, а счастье второго жителя при переезде не ухудшится, то эти два жителя меняются местами.
Для тестирования рассмотрим наихудший вариант при котором все жители чередуются, в таком случае их уровень счастья изначально равен 0. Проведем тестирование и посмотрим, что произойдет спустя 15 итерацией.
Уже после первых 15 итераций счастье в колонии значительно увеличилось. Посмотрим, чего можно добиться за большее число итераций.
Как видим, образовались группы поселенцев по интересам, и эти жители более ни с кем не хотят меняться, так как ни одному из них не выгодно менять своё местоположение. Спустя время получается, что максимальное счастье в популяции составило 52, а необходимо достичь 60. Что делать в таком случае?
Добавляем случайность
Можно попробовать научить жителей ошибаться. Другими словами, при встрече можно заставить первого жителя говорить неправду о своих соседях второму жителю. Тогда второй житель будет неправильно оценивать обстановку, как следствие будет появляться вероятность того, что жители начнутся меняться даже если счастье населения будет оставаться таким же или даже станет меньше.
Назовем вероятность того, что житель говорит неправду о своих соседях “ложью”. Значение лжи будет задаваться параметром от 0 до 1 (где 0 - вариант из решения выше, все жители говорят только правду, 1 - каждый раз врут). Пусть в первый раз все жители лгут с вероятностью 10% (0.1). Посмотрим, чего смогут добиться жители.
Как видно на gif выше, получилось добиться того, что все жители пришли к максимальному счастью. Это очень удивительно, как случайные отклонения могут помочь достичь нужного результата в задачах, где есть взаимодействия в группе.
Немного тестов
Тут мне стало интересно, а что будет, если вероятность лжи в группе будет меняться, при каком проценте получится максимально быстро достичь нужного уровня счастья. Было решено провести тестирование для 0.001, 0.0015, 0.005, 0.01, 0.015, 0.02, 0.05, 0.075, 0.1, 0.125, 0.175, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4, 0.45, 0.5 вероятностей лжи. Для каждой вероятности будет браться среднее значение из 100 испытаний. Важным условием будет следующее: если после 100000 итераций не было достигнуто максимального уровня счастья, то цикл завершался и переходил к следующему тесту (так как в некоторых случаях приходилось ждать по 1-2 млн итераций). Вот результаты:
Вывод
Даже несмотря на то, что случайные отклонения приводили в некоторых моментах к понижению счастья в поселении, но в конечном итоге умеренные отклонения от нормы приводили к стабилизации ситуации и достижению нужной цели. Это наводит на мысль о том, что ошибаясь в реальной жизни, мы не всегда получаем только негативные последствия, а иногда наши ошибки могут приводить к чему-то новому, к более значимому результату.
