Записи с меткой «теория игр»

Пробки и теория игр

14.05.2012

В связи с успешным окончанием курса по теории игр хочу рассказать еще об одной простой модели, хорошо иллюстрирующей наш мир. В оригинале она называется «Tradegy of commons», что можно перевести как «Трагедия общин», хотя я бы перевел как «Трагедия (драма) общежития», ибо общинами сейчас уже почти не живут, а вот в общежитиях – запросто.

Итак, рассмотрим типичную ситуацию: две дороги сливаются в одну. Пропускная способность слияния падает по мере увеличения интенсивности вливающихся потоков машин. В предельном случае, когда машин очень много, все встают, образовывается мертвая пробка. Пусть из каждого рукава идет поток в q_i машин в час. Допустим также, что пропускная способность падает линейно и равна S = 300-\sum\limits_{i=1}^n q_i (конкретные значения констант сейчас не важны, важна сама идея). В нашем случае n=2. Тогда из каждого потока за час проедет q_iS = q_i(300-q_i-q_{-i}), где q_{-i} – другой поток. Каждый поток будет стараться максимизировать свое количество проехавших машин. Приравняем производную по q_i к нулю, чтобы найти максимум:

300-2q_i-q_{-i}=0

Отсюда

q_i=150-q_{-i}/2

Так как ситуация симметрична для обоих потоков, то каждый из них будет действовать одинаково, и в равновесии их интенсивности сравняются. Обозначим равновесную интенсивность через q_{eq}:

q_{eq}=150-q_{eq}/2

Откуда

q_{eq}=100

То есть в равновесии, к которому будут стремиться участники движения, из каждого потока будет въезжать по 100 машин в час. Посмотрим, сколько из них проедет слияние:

q_{eq}S = 100(300-100-100)=10000

Не нужно удивляться, что проедет больше чем въехало. Число 10000 означается лишь, что въехавшие 100 машин проедут слияние быстрее, чем за час, а конкретнее за 100/10000=1/100 часа. Теперь попробуем максимизировать не количество проехавших машин в каждом рукаве, а общее число машин, проехавших через слияние. Обозначим общий въезжающий поток через q_{total} = q_1+q_2, тогда число машин, проехавших через слияние будет

q_{total}S = q_{total}(300-q_{total})

Возьмем производную по q_{total} и приравняем к нулю для поиска максимума:

300-2q_{total} = 0

Отсюда q_{total}=150. Опять-таки в силу симметричности ситуации для все участников

q_{total} = q_1 + q_2 = 2q_{op}, где q_{op} – оптимальный поток из каждого рукава.

Значит, q_{op} = 150/2=75. Видим, что в этом случае интенсивность каждого потока меньше. Посмотрим, как изменилось количество проехавших через слияние машин для каждого потока:

q_{op}S=75(300-75-75)=11250

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

,

Революция и теория игр

20.04.2012

Я сейчас изучаю стэнфордский курс «Теория игр» и не перестаю удивляться, как достаточно простые модели хорошо описывают окружающую действительность. Возьмем относительно недавнее выступление Навального на митинге в Москве. Он сказал примерно следующее: «Мы можем занять Кремль уже сейчас, но не собираемся этого делать, так как мы мирный народ.» Что эта фраза значит в терминах теории игр?

Пусть у нас есть два игрока, условно, Навальный и Путин. У игрока Навальный есть две стратегии: штурм Кремля или ничего не делание. У Путина в ответ на действия Навального также есть две стратегии: подавление штурма или капитуляция. Если Навальный штурмует и Путин капитулирует, Навальный выигрывает, Путин проигрывает. Если Навальный штурмует, и Путин подавляет штурм, Навальный проигрывает. Но выигрывает ли в этом случае Путин? Тут нужно сделать одно допущение, чтобы наша моделька заработала. Допустим, при подавлении Путин проигрывает больше, чем при капитуляции: кровавая бойня, шок у западных партнеров, волнения в стране и так далее. Всего этого можно избежать, если в случае активных действий оппозиционеров попытаться договориться, «заболтать», как он умеет, и так далее.

Итак, мы только что описали нашу игру в нормальной форме. Запишем ее в виде таблицы.

             Путин
          Подавление Переговоры
Навальный
Штурм       -1, -2     1, -1
Нет          0,  0     0,  0

Игрок номер 1 – Навальный, номер 2 – Путин. В клетках таблицы указаны выигрыши игроков. И вот что получается. Состояние (Нет, Подавление) является устойчивым (равновесие Нэша), так как ни одному из игроков не выгодно из него выходить. Если Навальный пойдет на штурм (передвинется вверх по таблице), то его выигрыш изменится с 0 до -1, то есть уменьшится. Если Путин пойдет на переговоры (сместится вправо), то его выигрыш останется равным нулю, то есть он индифферентен в данном случае. Поэтому обоим игрокам выгодно находится именно в этой позиции, то есть играть с такими стратегиями. Именно поэтому Навальный не идет на штурм. Однако, конкретно в этой игре есть еще одно состояние равновесия! Посмотрим на клетку (Штурм, Переговоры). Навальному нет смысла ее покидить, так как его выигрыш уменьшится с 1 до 0. И Путину также не выгодно менять стратегию, иначе его выигрыш уменьшится с -1 до -2. То есть это еще одно равновесие, еще один вероятный сценарий развития событий. Проблема в том, что если ты уже находишься в равновесии (Нет, Подавление), то выйти из него крайне сложно, так как это ведет к уменьшению выигрыша.

А в следующий раз я расскажу вам про автомобильные пробки, не переключайтесь.

,