Эволюционная динамика для забавы
В прошлой передаче Латынина минут 15 посвятила пересказу "Эгоистичного гена" Докинза. Конечно, очень радостно, что журналисты интересуются такими темами, но аналогии с Израилем и Палестиной были весьма натянутыми. В свое время Докинз был вынужден сделать фильм, чтобы отбиться от притязаний и нападок разных правых и левых. Поскольку всплыла тема решил дописать пост, который наполовину был готово еще летом. Прямо ЭСС я не касаюсь, но в неявном виде он везде. :)
На досуге почитал книгу Мартина Новака "Evolutionary dynamics: Exploring the Equations of Life" - введение в популяционные уравнения и игры. Начиная с простых дифференциальных уравнений автор быстро переходит к повторяющейся дилемме заключенного. Много тем пересекается с "Эгоистичным геном" Докинза, в частности турниры Аксельрода, с которыми я немного поигрался.
Кратко напомню.
Дилемма заключенного
При встрече двух игроков каждый может выбрать кооперацию (Сooperate) или предательство (Defect). Возможны 4 исхода, где для игрока, выбравшего поступок из ряда таблицы, полученные очки выглядят следующим образом (противник делает поступок, указанный в столбце):CDC30D51.5
Если оба кооперируются, то получают по 3 очка. Если же кто-то предает кооперирующегося, то получает целых 5 очков, а его соперник 0. Диллемой она называется, поскольку рациональный шаг с точки зрения каждого игрока это предательство, независимо от того, что выберет противник. Однако про таком рациональном поведении проигрывают оба.
В повторяющейся дилемме заключенного при каждой встрече игроки делают M шагов (steps) и очки суммируются. Например
DDDDD = 5+4*1.5 = 11
CDDDD = 0+4*1.5 = 6
При 1 шаге обмануть всегда выгодно, что бы не выбрал противник. Однако в повторяющейся дилемме заключенного есть опасность скатится в пучину вражды и недоверия. Тогда каждый будет получать по 1.5 очка, а не 3 - в случае если бы соперники скооперировались.
В турнирах Аксельрода в популяции каждый игрок играл со всеми другими в повторяющуюся дилемму заключенного и при этом очки от всех игр суммировались. Если в популяции достаточно "добрых" стратегий, то "альтруисты" могут получить больше очков от кооперации друг с другом, чем "злые" стратегии от обмана слишком "добрых" стратегий.
Три простые стратегии это
Эволюционная (популяционная) динамика получается из турнира Аксельрода, если играть много раундов и в конце каждого раунда самого неудачного игрока заменять самым успешным. Если таких игроков несколько, то выбирать одного случайным образом. Вот что получается для популяции, где вначале по 50 игроков из каждой стратегии (делают по 10 шагов в каждой встрече):
В начале эгоисты получают больше всех очков, обманывая альтруистов. Однако, достаточно быстро альтруисты иссякают и "око за око", кооперируясь друг с другом, выбивают эгоистов.
Если начинать без эгоистов, то "око за око" неотличимо от альтруистов (они получают всегда одинаковой количество очков) и происходит просто дрейф (случайный игрок заменяется случайным)
Становится немного интересней, если ввести "мутации" - позволить игрокам случайным образом менять стратегию после каждого раунда. Например, каждый игрок с вероятностью 1% меняет стратегию на любую другую (втч и на свою) после каждого раунда - при общей популяции 150 в среднем 1.5 игрока за раунд (с 3 стратегиями в среднем 1 игрок за раунд действительно изменяет стратегию на другую):
После разгона эгоистов у альтруистов снова появляется шанс дрейфом вклиниться в популяцию "око за око". Учитывая, что "отбором" тоже меняется только один игрок, это очень большая вероятность для генетической мутации, но вполне подходящая для "культурной эволюции". :) Скорость "мутации" может играть большую роль. Например, в популяцию эгоистов не могут вклинится другие две стратегии при вероятности "мутации" 0.5%:
Однако при 1.5% "мутационный" дрейф сильнее отбора и популяция может набрать критическую массу "око за око", чтобы они вышибли из популяции эгоистов
В тех правилах, которые я выбрал есть пара нюансов. В отборе всегда выкидывается худшая стратегия, даже если она набрала только чуть меньше очков, чем вторая худшая. Поэтому у эгоистов нет шансов, пока в популяции не появляется критическая масса альтруистов, и в эти моменты происходят короткие вспышки роста эгоистов, а не плавное увеличение, как возможно при более "щадящих" правилах:
Более того, чтобы начать быстро расти, стратегия должна стать лучшей среди всех в популяции, а не только лучше какой-то другой. В последнем случае отбор "против стратегии" прекращается, но пока не станет лучшей она может расти только в результате "мутационного" дрейфа. Рассматривая дальнейшие примеры с большим количеством стратегий это надо иметь в виду.
TF2T: Око за 2 ока (подставь другую щёку)
Было замечено, что "Око за око" это одна из "добрых" стратегий: расположенная при первой встрече, быстро забывающая бывшие обиды (помнится только предыдущий шаг) и независтливая (не пытается обмануть и набрать больше очков, чем соперник)
Можно рассмотреть более "прощающую" стратегию: "око за 2 ока" (TF2T), которая в случае первого обмана "подставляет вторую щеку" и пытается еще раз сыграть мирно. Только при двух подряд обманах переходит на вражду, то есть по сути смотрит два последних шага. В обычной ситуации она ничем не лучше TFT, наоборот несколько хуже - позволяет эгоистам обмануть себя два раза вместо одного:
Однако все меняется, если в систему добавить возможность ошибки - недопонимания между игроками. В этом случае две TFT стратегии вступают на "путь кровной вражды" (допустим на 3 шаге происходит недопонимание):
CCCDCD...
CCDCDC...
Более того, кровная месть "око за око" может при второй ошибке скатиться к нескончаемой вражде. TF2T умеет избегать кровной вражды, "подставляя вторую щеку", надеясь, что это было просто недоразумение. В таком случае TF2T в отличие от TFT возвращаются к кооперации. Например, при вероятности недопонимания 10% и особенно при более длинной встрече (20 шагов) преимущество TF2T очевидно:
Можно начать с популяции, где есть только "око за око". Все равно в среде, где возможны недопонимания, "око за 2 ока" чувствует себя лучше и после нескольких этапов развития популяция приходит к логичному равновесию:
Последний тест еще раз показывает, что популяция может переживать этапы развития. Более добрые стратегии (TF2T) могут стать успешными, только когда прагматичные (TFT) проложили им дорогу, изведя в популяции эгоистов, которые выросли из-за короткого успеха альруистов.
WSLS: (Win - Stay, Loose - Shift)
"Выигрываешь - Продолжай, Проигрываешь - Исправь" (WSLS) очень интересная стратегия. Она старается не создавать конфликта, если его нет, использовать в свою выгоду дураков, и исправить конфликтную ситуацию, если такая возникла. Выбор действия WSLS в зависимости от предыдущего шага выглядят так (я-противник -> выбор):
и был расстроен, поскольку ничего она не сделала. Однако, просто удлинив встречу до 15 шагов, результат оказался в корне другим:
Это меня на время озадачило, особенно учитывая, что обе картинки в своем начале очень похожи, и у WSLS казалось нет особых преимуществ перед TFT и TF2T. Во-первых я заметил, что на 30 периоде в первом случае происходит небольшой спад WSLS, очевидно из-за уязвимости перед эгоистами, которых оказывается на ~10% больше в первом случае. Последнее же обусловлено длиной встречи: поскольку TFT чувствуют себя лучше, рост эгоистов прекращается чуть раньше. Во-вторых, я понял, что WSLS при ошибках лучше себя чувствует при встрече другого WSLS или TF2T, но хуже при встрече TFT. Получалось, что если есть критическая масса WSLS+TF2T, первые способны в итоге всех победить, или в обратном случае полностью проиграть. Конечное состояние системы определялось маленькими вариациями начального развития!
Последний факт напомнил мне еще одну тему из книги: стабильные и нестабильные равновесия. Мяч не вершине горки находится в равновесии, однако при маленьких флуктуациях скатится, при этом сложно сказать в какую сторону. Мяч, лежащий в яме, находится в стабильном равновесии. При решении дифференциальных уравнений в эволюционной динамике первым делом приходилось определять тип найденного в популяции равновесия.
На закуску приведу пару моделей с колебаниями в популяции (в отличие от предыдущего примера добавил возможность мутаций):
Только альтруисты всегда в проигрыше и способны лишь моментами недолго "пор(ае)звиться" когда эгоистов уже нет, а WSLS еще нет. На самом деле в книге есть еще стохастические модели, где решение принимается с определенной вероятностью. Это дает еще больше разнообразия в модели. Забавный результат в одной из них оставлял в популяции тех, кто прощал случайным образом с вероятностью 1/3. Кроме того могут существовать различные репутационные модели, где выбор поведения зависит не только от недавнего собственного опыта, но и от наблюдения за поведением в отношении других. Думаю в моделях с репутацией альтруисты будут себя чувствовать несколько лучше. :)
На досуге почитал книгу Мартина Новака "Evolutionary dynamics: Exploring the Equations of Life" - введение в популяционные уравнения и игры. Начиная с простых дифференциальных уравнений автор быстро переходит к повторяющейся дилемме заключенного. Много тем пересекается с "Эгоистичным геном" Докинза, в частности турниры Аксельрода, с которыми я немного поигрался.
Кратко напомню.
Дилемма заключенного
При встрече двух игроков каждый может выбрать кооперацию (Сooperate) или предательство (Defect). Возможны 4 исхода, где для игрока, выбравшего поступок из ряда таблицы, полученные очки выглядят следующим образом (противник делает поступок, указанный в столбце):CDC30D51.5
Если оба кооперируются, то получают по 3 очка. Если же кто-то предает кооперирующегося, то получает целых 5 очков, а его соперник 0. Диллемой она называется, поскольку рациональный шаг с точки зрения каждого игрока это предательство, независимо от того, что выберет противник. Однако про таком рациональном поведении проигрывают оба.
В повторяющейся дилемме заключенного при каждой встрече игроки делают M шагов (steps) и очки суммируются. Например
DDDDD = 5+4*1.5 = 11
CDDDD = 0+4*1.5 = 6
При 1 шаге обмануть всегда выгодно, что бы не выбрал противник. Однако в повторяющейся дилемме заключенного есть опасность скатится в пучину вражды и недоверия. Тогда каждый будет получать по 1.5 очка, а не 3 - в случае если бы соперники скооперировались.
В турнирах Аксельрода в популяции каждый игрок играл со всеми другими в повторяющуюся дилемму заключенного и при этом очки от всех игр суммировались. Если в популяции достаточно "добрых" стратегий, то "альтруисты" могут получить больше очков от кооперации друг с другом, чем "злые" стратегии от обмана слишком "добрых" стратегий.
Три простые стратегии это
- альтруисты (Altruist), которые всегда кооперируются,
- эгоисты (Defector), которые всегда обманывают,
- и "око за око" (TitForTat,TFT), которые начинают с кооперации и затем повторяют предыдущий шаг противника
Эволюционная (популяционная) динамика получается из турнира Аксельрода, если играть много раундов и в конце каждого раунда самого неудачного игрока заменять самым успешным. Если таких игроков несколько, то выбирать одного случайным образом. Вот что получается для популяции, где вначале по 50 игроков из каждой стратегии (делают по 10 шагов в каждой встрече):
В начале эгоисты получают больше всех очков, обманывая альтруистов. Однако, достаточно быстро альтруисты иссякают и "око за око", кооперируясь друг с другом, выбивают эгоистов.
Если начинать без эгоистов, то "око за око" неотличимо от альтруистов (они получают всегда одинаковой количество очков) и происходит просто дрейф (случайный игрок заменяется случайным)
Становится немного интересней, если ввести "мутации" - позволить игрокам случайным образом менять стратегию после каждого раунда. Например, каждый игрок с вероятностью 1% меняет стратегию на любую другую (втч и на свою) после каждого раунда - при общей популяции 150 в среднем 1.5 игрока за раунд (с 3 стратегиями в среднем 1 игрок за раунд действительно изменяет стратегию на другую):
После разгона эгоистов у альтруистов снова появляется шанс дрейфом вклиниться в популяцию "око за око". Учитывая, что "отбором" тоже меняется только один игрок, это очень большая вероятность для генетической мутации, но вполне подходящая для "культурной эволюции". :) Скорость "мутации" может играть большую роль. Например, в популяцию эгоистов не могут вклинится другие две стратегии при вероятности "мутации" 0.5%:
Однако при 1.5% "мутационный" дрейф сильнее отбора и популяция может набрать критическую массу "око за око", чтобы они вышибли из популяции эгоистов
В тех правилах, которые я выбрал есть пара нюансов. В отборе всегда выкидывается худшая стратегия, даже если она набрала только чуть меньше очков, чем вторая худшая. Поэтому у эгоистов нет шансов, пока в популяции не появляется критическая масса альтруистов, и в эти моменты происходят короткие вспышки роста эгоистов, а не плавное увеличение, как возможно при более "щадящих" правилах:
Более того, чтобы начать быстро расти, стратегия должна стать лучшей среди всех в популяции, а не только лучше какой-то другой. В последнем случае отбор "против стратегии" прекращается, но пока не станет лучшей она может расти только в результате "мутационного" дрейфа. Рассматривая дальнейшие примеры с большим количеством стратегий это надо иметь в виду.
TF2T: Око за 2 ока (подставь другую щёку)
Было замечено, что "Око за око" это одна из "добрых" стратегий: расположенная при первой встрече, быстро забывающая бывшие обиды (помнится только предыдущий шаг) и независтливая (не пытается обмануть и набрать больше очков, чем соперник)
Можно рассмотреть более "прощающую" стратегию: "око за 2 ока" (TF2T), которая в случае первого обмана "подставляет вторую щеку" и пытается еще раз сыграть мирно. Только при двух подряд обманах переходит на вражду, то есть по сути смотрит два последних шага. В обычной ситуации она ничем не лучше TFT, наоборот несколько хуже - позволяет эгоистам обмануть себя два раза вместо одного:
Однако все меняется, если в систему добавить возможность ошибки - недопонимания между игроками. В этом случае две TFT стратегии вступают на "путь кровной вражды" (допустим на 3 шаге происходит недопонимание):
CCCDCD...
CCDCDC...
Более того, кровная месть "око за око" может при второй ошибке скатиться к нескончаемой вражде. TF2T умеет избегать кровной вражды, "подставляя вторую щеку", надеясь, что это было просто недоразумение. В таком случае TF2T в отличие от TFT возвращаются к кооперации. Например, при вероятности недопонимания 10% и особенно при более длинной встрече (20 шагов) преимущество TF2T очевидно:
Можно начать с популяции, где есть только "око за око". Все равно в среде, где возможны недопонимания, "око за 2 ока" чувствует себя лучше и после нескольких этапов развития популяция приходит к логичному равновесию:
Последний тест еще раз показывает, что популяция может переживать этапы развития. Более добрые стратегии (TF2T) могут стать успешными, только когда прагматичные (TFT) проложили им дорогу, изведя в популяции эгоистов, которые выросли из-за короткого успеха альруистов.
WSLS: (Win - Stay, Loose - Shift)
"Выигрываешь - Продолжай, Проигрываешь - Исправь" (WSLS) очень интересная стратегия. Она старается не создавать конфликта, если его нет, использовать в свою выгоду дураков, и исправить конфликтную ситуацию, если такая возникла. Выбор действия WSLS в зависимости от предыдущего шага выглядят так (я-противник -> выбор):
- продолжай кооперацию C-C -> C
- не давай себя обманывать C-D -> D
- попробуй закончить вражду D-D -> C
- используй дураков D-C -> D
и был расстроен, поскольку ничего она не сделала. Однако, просто удлинив встречу до 15 шагов, результат оказался в корне другим:
Это меня на время озадачило, особенно учитывая, что обе картинки в своем начале очень похожи, и у WSLS казалось нет особых преимуществ перед TFT и TF2T. Во-первых я заметил, что на 30 периоде в первом случае происходит небольшой спад WSLS, очевидно из-за уязвимости перед эгоистами, которых оказывается на ~10% больше в первом случае. Последнее же обусловлено длиной встречи: поскольку TFT чувствуют себя лучше, рост эгоистов прекращается чуть раньше. Во-вторых, я понял, что WSLS при ошибках лучше себя чувствует при встрече другого WSLS или TF2T, но хуже при встрече TFT. Получалось, что если есть критическая масса WSLS+TF2T, первые способны в итоге всех победить, или в обратном случае полностью проиграть. Конечное состояние системы определялось маленькими вариациями начального развития!
Последний факт напомнил мне еще одну тему из книги: стабильные и нестабильные равновесия. Мяч не вершине горки находится в равновесии, однако при маленьких флуктуациях скатится, при этом сложно сказать в какую сторону. Мяч, лежащий в яме, находится в стабильном равновесии. При решении дифференциальных уравнений в эволюционной динамике первым делом приходилось определять тип найденного в популяции равновесия.
На закуску приведу пару моделей с колебаниями в популяции (в отличие от предыдущего примера добавил возможность мутаций):
Только альтруисты всегда в проигрыше и способны лишь моментами недолго "пор(ае)звиться" когда эгоистов уже нет, а WSLS еще нет. На самом деле в книге есть еще стохастические модели, где решение принимается с определенной вероятностью. Это дает еще больше разнообразия в модели. Забавный результат в одной из них оставлял в популяции тех, кто прощал случайным образом с вероятностью 1/3. Кроме того могут существовать различные репутационные модели, где выбор поведения зависит не только от недавнего собственного опыта, но и от наблюдения за поведением в отношении других. Думаю в моделях с репутацией альтруисты будут себя чувствовать несколько лучше. :)