Цена анархии

Четвёртая комната состязаний, для одного. Соперника здесь нет, и ставить нечего. Каждую неделю, в воскресенье в 21:00 по Москве, на сети Талии появляются четыре новых потока пакетов. У вас пять распоряжений, чтобы задержка сети стала меньше. Броска нет: одни и те же распоряжения всегда дают один и тот же счёт.

Сеть

Линия задерживает пакет на постоянное время и ещё на сколько-то за каждый пакет на ней. Запись «13 + 40 на пакет» при десяти пакетах даст 413 мс каждому. Местные линии быстры, пока пусты, и быстро вязнут. Магистрали долгие и почти не вязнут. Если наземного пути нет, пакет уходит через спутник, а это 40 000 мс.

Каждый пакет идёт сам за себя, выбирает самый быстрый для себя путь и меняет его, пока есть смысл. Когда менять некому, наступает равновесие. Послушная сеть, где каждого пакета посылают куда надо, работала бы быстрее. Число, во сколько раз она быстрее худшего равновесия, и называют ценой анархии.

Распоряжения

На линию можно поставить тариф или отключить её. Тариф идёт ступенями: 150, 300, 600, 1 200, 2 400. Пакет прибавляет тариф к времени, когда выбирает путь, и часть пакетов уходит на другие линии. В счёт тариф не идёт, настоящей задержки он не добавляет. Отключённая линия не работает ни в мирный день, ни в день удара.

Нажмите на линию, и под картой появится пульт. То же можно сделать в таблице «Все линии словами». Страница считает сеть сразу и ничего при этом не записывает. Если карта на нажатия не отвечает, выберите распоряжения в таблице и нажмите «Посчитать».

Удар

Хакер видит вашу сеть и бьёт одну линию, ту, после падения которой задержка дня больше всего. Пакеты с упавшей линии ищут новый путь, за ними двигаются другие, и наступает новое равновесие. Крест на карте показывает, куда придётся удар. Столбики показывают, что будет от удара по каждой линии, и если нажать на столбик, карта покажет этот день. Столбик вниз значит, что удар помог бы, потому что такая линия мешает сети сама.

Счёт

Счёт — это задержка мирного дня плюс задержка дня худшего удара, всех пакетов вместе. Чем он меньше, тем лучше. Шкала показывает, сколько лишней задержки снято: ноль у сети как есть, сто процентов у границы. На картах недели граница посчитана для сети, где каждый пакет идёт туда, куда его пошлют, и в мирный день, и после удара. Толпу так не построить, и до ста процентов там вряд ли кто дойдёт. В учебных сетях сто процентов значит лучшее, что можно сделать. Меньше нуля тоже бывает, распоряжение способно навредить.

Таблица недели

Когда сеть готова, нажмите «Сдать сеть». Сдавать можно сколько угодно раз, в таблице стоит лучшая ваша сеть. При равенстве выше тот, кто сдал раньше. Пока неделя идёт, другие видят только ваш счёт. Когда она кончится, распоряжения откроются всем. Нажмите на имя, и сеть появится на карте. Поправить её и посчитать заново можно, сдать уже нельзя.

Дежурный стоит в таблице без номера. Он отдаёт распоряжения по одному, каждый раз беря то, что лучше всего прямо сейчас. Его счёт — первая отметка, до которой стоит дойти. Карт посчитано на 52 недели, дальше они идут сначала. Пока карта идёт снова, её прошлогодние распоряжения закрыты.

Администрация сети не сдаёт (принцип 10). Запрет состязаний на деньги («Постоянные рычаги») эту комнату не закрывает.

Учебные сети

Три малые сети показывают по одной мысли, и в таблицу они не идут. В сети «Два пути» надо подобрать тариф на загруженной дороге, в сети «Мост» найти линию, без которой всем быстрее, а в сети «Удар» понять, почему тариф бывает лучше отключения.

Как думать

Отключение редко лучшее, потому что линия пропадает и на день удара, когда она нужна. Самая загруженная линия не всегда лучшая цель, потому что пакеты уходят туда, где их никто не ждал. Учебник ставит на всякую линию плату, равную вреду пакета для других. У вас пять распоряжений, и на пяти линиях с наибольшим вредом такая плата иногда хуже, чем ничего. Настройка на один мирный день подставляет сеть под удар. Смотрите, как после каждого распоряжения меняются столбики: хакер меняет цель вслед за вами.

От авторов. Название взято из теории игр: так Христос Пападимитриу назвал отношение худшего равновесия к наилучшему порядку. Равновесие на дорогах описал Джон Вардроп (1952), налог на загруженную дорогу разобрал Артур Пигу (1920), новую дорогу, от которой всем хуже, — Дитрих Браесс (1968). Тим Рафгарден и Ева Тардош доказали, что при большом числе мелких участников и задержке из постоянного времени и равной прибавки за каждого цена анархии не больше 4/3 (2002). Наши пакеты неделимы, и эта граница здесь только ориентир. Подробнее об этих идеях — в собрании «Откуда это взято».

Смотрите ещё: Состязания, Многорукий бандит, Лимбо