Дидактические цели
Планировщик распределяет поток машин так, чтобы все доехали как можно быстрее; водители, каждый сам за себя, приходят к другому распределению, и худшему. Насколько худшему? Этот лаб для старшей школы сравнивает оптимум планировщика с равновесием водителей и измеряет разницу с помощью цены анархии — отношения среднего времени в равновесии к среднему времени в оптимуме. Он начинается с сети Пигу, переходит к «парадоксу Браеса» — новой дороге, из-за которой всем ехать дольше, — и заканчивается играми по раундам, в одиночку или всем классом: бар «Эль Фароль», общее пастбище, эффект кобры и час пик.
Чему учимся
Главная идея: когда каждый выбирает лучшее для себя, общий результат может оказаться хуже, чем при согласованном распределении, и это «хуже» можно измерить.
- Пигу: планировщик и водители (залы 1-4). Ученик распределяет 100 машин между автомагистралью в 60 мин и дорогой, которая забивается (60 по автомагистрали и 40 по дороге: в среднем 48 мин), и видит, что минимум — вершина параболы. Без планировщика каждый водитель переходит, пока это выгодно, и поток приходит к равновесию, в котором дорога не экономит никому ни минуты (в среднем 60 мин). Отношение двух средних — это цена анархии (60/48 = 1,25 при 0,75 мин на машину), а для линейных времён она никогда не превышает 4/3; при более резких зависимостях (функция BPR с показателем 4) эта оценка уже не работает.
- Браес (залы 5-11). При 4000 машин и двух одинаковых маршрутах равновесие — 2000 и 2000, 65 мин. Когда открывается короткая дорога в 2 мин, ею пользуются все, и все тратят 82 мин, больше, чем раньше, а выйти из неё никому не выгодно. Изучается, как равновесие зависит от времени короткой дороги, цена анархии при ней (82 / 64,89 ≈ 1,264), плата за проезд в 21,5 мин, которая приводит водителей к распределению планировщика, и почему закрытие дороги иногда улучшает движение. Тот же парадокс встречается в системе пружин и верёвок (перережем верёвку — груз поднимается) и в индуцированном спросе: расширение дороги лишь меняет, сколько людей ею пользуется.
- Игры по раундам и кобра (залы 12-15). Четыре ситуации, где разумное для каждого оборачивается плохим для всех. «Эль Фароль» (8 раундов): в баре приятно, если пришло не больше 60 % группы, и никто не может хорошо предсказать, если все пользуются одним и тем же предсказанием. Общее пастбище (20 дней): 5 овец выигрывают за 3 дня, но пастбище выдерживает только 2 на пастуха, и за 20 дней это проигрыш. Эффект кобры: при награде за каждую кобру их выгодно разводить (при 400 кобрах в начале — начиная с 8 €), а когда награду отменяют, кобр выпускают. Час пик в классе: сеть Браеса, сыгранная по раундам, с короткой дорогой, которая открывается в середине партии и поднимает среднее по группе примерно с 65 до 80 мин.
Залы 12, 13 и 15 играют в одиночку против ботов или всем классом. В классе раунды закрывает учитель на своей панели (а в часе пик ещё и открывает короткую дорогу); боты дополняют состав группы.
Ключевые математические идеи
- Равновесие и оптимум: распределение — равновесие, если никому не выгодно менять его в одиночку, и все используемые маршруты занимают одинаковое время; оптимум минимизирует среднее время. В общем случае они не совпадают.
- Цена анархии: среднее время в равновесии, делённое на оптимальное среднее время. Это отношение времён, без единиц измерения, и оно никогда не меньше 1.
- Оценка 4/3 (Рафгарден и Тардош, 2002): если время на каждом участке имеет вид a + bx, цена анархии в любой сети не больше 4/3, а сеть Пигу при d = 1 её достигает. Для других функций, например BPR, такой гарантии нет.
- «Парадокс Браеса»: добавленная дорога может ухудшить время для всех в равновесии, потому что каждый, кто ею пользуется, экономит время, но задерживает тех, кто делит с ним нагруженные участки.
- Плата за проезд по Пигу: если брать с каждого водителя плату за задержку, которую он создаёт другим, равновесие совпадёт с распределением планировщика; деньги собираются, а не теряются как время.
- Трагедия общин: лишняя овца приносит всю шерсть владельцу, а ущерб делится на всех; каждому выгодно её добавить, даже если пастбище истощится. Элинор Остром изучала общины, которые этого избегают, договариваясь о правилах.
- «Эль Фароль» (Брайан Артур, 1994): предсказание, в которое верят все, перестаёт сбываться, поэтому общего предсказателя, который всегда прав, быть не может; посещаемость колеблется около 60 %.
Содержание по залам
Зал 1 · Вы — планировщик
Сто машин едут из S в T по автомагистрали с постоянным временем 60 мин или по дороге, которая занимает 0,75 мин на каждую машину на ней. Ученик распределяет машины так, чтобы СРЕДНЕЕ время было как можно меньше (60 по автомагистрали и 40 по дороге: 48 мин, на 12 меньше, чем если все едут по автомагистрали). Затем дорога становится однополосной (1,5 мин на машину), и распределение нужно найти, не видя среднего. В теории объясняется, что минимум — это вершина параболы.
Задания для ученика
- Распределить 100 машин так, чтобы среднее время было минимальным.
- Повторить это для однополосной дороги, не видя среднего.
Зал 2 · Каждый водитель сам за себя
Планировщика нет: каждый водитель выбирает самый выгодный для себя маршрут. Ученик предсказывает, куда пойдёт поток, а анимация показывает, как водители переходят один за другим (от 60/40 к 20/80). Вводится понятие равновесия (никому не выгодно менять маршрут в одиночку), и его ищут для однополосной дороги: при целых машинах есть два соседних распределения — 39 или 40 по дороге. Вывод: в равновесии дорога не экономит ни минуты никому.
Задания для ученика
- Предсказать и посмотреть, куда движется поток, когда каждый заботится только о себе.
- Найти равновесие для однополосной дороги.
Зал 3 · Цена анархии
Определение: среднее в равновесии, делённое на оптимальное среднее; переключатель «Планировщик / Водители» анимирует смену распределения. При дороге 0,75 мин на машину средние равны 48 и 60 мин (отношение 1,25); при 1,2 мин на машину — 52,5 и 60 (8/7). Пока ученик считает, отношение скрыто. Зал заканчивается вопросом: может ли оно быть меньше 1?
Задания для ученика
- Найти цену анархии при k = 0,75 и при k = 1,2.
- Объяснить, что значит 1,25 и почему оно не бывает меньше 1.
Зал 4 · Сколько это может стоить?
Сеть Пигу с дорогой, время которой равно T·(x/100)^d. С помощью ползунка T и выбора d ученик видит, как строится график цены по тому, что он исследует. При d = 1 максимум равен 4/3 при T = 60. В теории сформулирована теорема Рафгардена и Тардоша (линейные времена: не больше 4/3) и функция BPR с показателем 4. Ученики спорят, превысит ли 4/3 случай d = 4, и считают вручную случай d = 3, T = 60 (≈ 1,90).
Задания для ученика
- Найти T, при котором цена наибольшая при d = 1.
- Сделать ставку и проверить, что происходит при d = 4; вручную посчитать d = 3.
Зал 5 · Два маршрута из A в B
Сеть Браеса без короткой дороги: 4000 машин, два одинаковых маршрута (A-Y-B и A-X-B), жёлтые участки по x/100 мин и красные автомагистрали по 45 мин. Ученик находит равновесие (2000 и 2000, 65 мин), проверяет, что планировщик не может его улучшить (они совпадают), и считает время маршрута при другом распределении.
Задания для ученика
- Найти равновесие сети без короткой дороги.
- Посчитать время маршрута при другом распределении.
Зал 6 · Строим короткую дорогу
Открывается дорога с односторонним движением из Y в X, длиной 2 мин. Сначала ученик делает ставку; затем анимация переводит машины на короткую дорогу по 100, пока все 4000 не едут по A-Y-X-B и каждый не тратит 82 мин против прежних 65. Это парадокс Браеса. Задания: время A-X-B для водителя, который бы вернулся (85 мин), почему никто не возвращается и что будет, если закрыть короткую дорогу (65).
Задания для ученика
- Сделать ставку и посмотреть, что будет, когда короткая дорога откроется.
- Объяснить, почему никто не уходит с короткой дороги, хотя все едут дольше.
Зал 7 · Сколько занимает короткая дорога?
Ползунок меняет время c короткой дороги (от 0 до 40 мин), а сеть показывает равновесие. При c = 10 по короткой дороге едут не все: три маршрута выравниваются при распределении 500 / 3000 / 500, и каждый занимает 80 мин. График строится по точкам, которые исследует ученик.
Задания для ученика
- Пройти ползунком по c и отметить, когда равновесие ухудшается.
- Найти равновесное распределение для заданного c.
Зал 8 · Короткая дорога в руках планировщика
При трёх маршрутах и группах по 50 машин ученик ищет распределение с наименьшим средним временем: при короткой дороге в 0 мин это 1750 / 500 / 1750 (64,69 мин), а при c = 5 планировщик уже не пользуется короткой дорогой. Затем считается цена анархии при c = 2 (82 / 64,89 ≈ 1,264). Последнее задание — плата за проезд по Пигу на короткой дороге. Ползунком ученик ищет плату в 21,5 мин, при которой водители, учитывающие только своё время плюс плату, приходят к распределению планировщика. В теории приведены примеры городских платежей за проезд (Сингапур, Лондон, Стокгольм).
Задания для ученика
- Найти распределение с наименьшим средним при короткой дороге и увидеть, когда ею перестают пользоваться.
- Посчитать цену анархии при c = 2.
- Найти плату за проезд, при которой равновесие совпадает с распределением планировщика.
Зал 9 · Закрыть дорогу
Если добавленная дорога может ухудшить движение, то закрытая может его улучшить. Ученик нажимает на участки двух сетей по 600 машин, чтобы закрыть или открыть их, и машины перераспределяются до нового равновесия. В первой сети (ромб Браеса в другом обличье) время снижает только закрытие A→B — с 46 до 39 мин; во второй — только B→C, с 90 до 80.
Задания для ученика
- В каждой сети найти единственный участок, закрытие которого улучшает равновесие.
- Проверить, что закрытие других участков оставляет время прежним или ухудшает его.
Зал 10 · Пружины и верёвки
Парадокс Браеса в механике (Коэн и Горовиц, 1991): две пружины последовательно, одна короткая верёвка и две слабо натянутые страховочные верёвки. Если перерезать среднюю верёвку, груз ПОДНИМАЕТСЯ. В теории напоминается закон Гука и почему два параллельных пути несут по половине нагрузки.
Задания для ученика
- Предсказать, что будет с грузом, если перерезать среднюю верёвку.
- Объяснить результат с помощью последовательного и параллельного соединения пружин.
Зал 11 · Больше полос — та же пробка
Каждый выбирает между машиной и поездом. Поезд идёт постоянное время; дорога — время, которое растёт с числом машин и убывает с числом полос. В равновесии, пока кто-то едет на поезде, дорога занимает столько же, сколько поезд: расширение дороги лишь меняет, сколько людей ею пользуется.
Задания для ученика
- Расширить дорогу и посмотреть, как система приходит в новое равновесие.
- Объяснить, почему равновесное время не уменьшается.
Зал 12 · Бар «Эль Фароль»
Игра из 8 раундов (Брайан Артур, 1994). В каждом раунде — идти в бар или остаться дома: если идёт не больше 60 % группы, пошедшие получают +1; если больше — теряют 1; тот, кто остался, получает 0. Боты используют простые предсказатели, и число посетителей колеблется около 60 %. Играют в одиночку против ботов или всем классом; в классе раунды закрывает учитель на своей панели. Задания: сколько человек ещё помещалось в одном из ваших раундов, что будет, если все используют один и тот же предсказатель, сколько очков больше набрала бы группа и почему посещаемость оказывается около 60 %.
Задания для ученика
- Сыграть 8 раундов, каждый раз решая, идти или остаться.
- Объяснить, почему предсказание, в которое верят все, перестаёт сбываться.
Зал 13 · Общее пастбище
Трагедия общин за 20 дней. Каждый пастух выбирает, сколько овец (от 0 до 5) вывести в дни 1, 2 и 3, а четвёртое, постоянное решение действует с 4-го по 20-й день. Каждая овца на пастуха в среднем съедает 5 % пастбища, а остаток отрастает на 0,4·r·(1−r). Каждый день анимируется (овцы пасутся, появляется шерсть, трава отрастает). В начале выгоднее всего выводить 5 (за 3 дня — 15 шерсти против 6), но пастбище выдерживает не больше 2 овец на пастуха: за 20 дней планировщик выигрывает 40 против 27,7. Играют в одиночку против ботов или всем классом, раунды закрывает учитель.
Задания для ученика
- Решить, сколько овец выводить, и посмотреть, как меняется пастбище.
- Посчитать, сколько овец выдерживает пастбище в день при пастухах вашей партии.
- Объяснить, почему эгоизм выигрывает за 3 дня и проигрывает за 20.
Зал 14 · Эффект кобры
Администрация платит за каждую сданную кобру, и разводить кобр оказывается выгодно. Ползунок меняет цену за голову, а два графика показывают год (дикие кобры, выведенные и всего) и попытки ученика. Начинают с 400 кобр: наименьшая целая цена, при которой через год кобр больше 400, — 8 €. Затем награду отменяют, и заводчики выпускают кобр. Зал заканчивается примером «Hoy no circula» (Мехико, 1989) и замечанием, что у истории про Дели нет надёжного источника.
Задания для ученика
- Найти наименьшую целую цену, при которой кобр становится больше, чем в начале.
- Объяснить, что происходит, когда награду отменяют.
Зал 15 · Час пик в классе
Сеть Браеса из залов 5-8, нормированная, на 7 раундов. У каждого игрока по 5 машин, и в каждом раунде он распределяет, сколько поедет по A-Y-B, A-X-B и, когда короткая дорога открыта, по A-Y-X-B. Жёлтые участки: 40 · (машины на участке / все машины) мин; красные — 45 мин; короткая дорога — 2 мин. Результат — среднее время ваших 5 машин. Первые 3 раунда проходят без короткой дороги; с 4-го она открывается (в одиночной игре — сама; в классе её открывает учитель на своей панели, где он также закрывает раунды). Среднее по группе с открытием короткой дороги растёт примерно с 65 до 80 мин. Задания опираются на данные вашей партии.
Задания для ученика
- Сыграть раунды без короткой дороги и с ней и сравнить среднее.
- Посчитать, насколько дольше ехала бы одна из ваших машин, если бы сменила маршрут.
- Объяснить, почему среднее ухудшается, когда открывается короткая дорога (на 17 мин больше на машину в равновесии: 82 против 65).
Залы для показа
Самые наглядные для показа и обсуждения в классе.