Стаття Браеса
Дітріх Браес надрукував статтю «Über ein Paradoxon aus der Verkehrsplanung» («Про парадокс транспортного планування») у німецькому журналі «Unternehmensforschung». Англійський переклад вийшов лише 2005 року в «Transportation Science».
Щоранку 4000 водіїв їдуть зі Старту на Фініш двома маршрутами. На кожному є вузька вулиця, де що більше машин, то повільніше, і широке шосе, де завжди 45 хвилин. Водії розподілилися порівну, і дорога займає 65 хвилин. Тепер місто будує миттєву перемичку між двома маршрутами. Кожен водій і далі обирає найшвидший шлях для себе. Скільки триватиме поїздка?
Здається, що нова дорога не може зашкодити: не подобається, то не їдь. Але перемичка вигідна кожному водієві окремо, хоч що роблять інші. Тож нею їдуть усі, обидві вузькі вулиці забиваються, і поїздка займає 80 хвилин замість 65. Якщо перемичку закрити, всі виграють по 15 хвилин.
1968 року німецький математик Дітріх Браес описав мережу доріг, у якій нова дорога сповільнює всіх. Ось найвідоміша версія його прикладу з конкретними числами.
Щоранку 4000 водіїв їдуть зі Старту на Фініш. Кожен хоче доїхати якнайшвидше і знає, скільки триває кожна дорога, наприклад з навігатора.
Вулиці Старт → A і B → Фініш вузькі: якщо нею їде T машин, проїзд займає T/100 хвилин. 1000 машин означає 10 хвилин, 4000 машин означає 40.
Шосе A → Фініш і Старт → B широкі, але довгі: 45 хвилин, хоч скільки на них машин.
Є два маршрути: через A і через B. Водії розподілилися порівну, по 2000, і кожен їде 2000/100 + 45 = 65 хвилин. Перейти на інший маршрут нікому не вигідно.
Місто будує перемичку A → B, яку проїжджають миттєво, за 0 хвилин. Водії знову обирають кожен найшвидший маршрут для себе, доки ніхто вже не захоче нічого змінювати. Скільки тоді займе поїздка?
«Нова дорога може лише допомогти. Гірше не буде: хто не хоче, той нею не їде»
Насправді перемичкою поїдуть усі 4000 водіїв, і кожен витрачатиме 80 хвилин. Ніхто з них не помиляється: для кожного окремо перемичка справді найшвидша. Програють вони разом.
Без перемички дорога займає 65 хвилин. Перемичку відкрили, водії звикли до неї, і ніхто вже не хоче міняти маршрут. Скільки тепер їде кожен?
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Подивіться очима одного водія одразу після відкриття: поки всі їдуть по-старому, маршрут перемичкою займає 20 + 0 + 20 = 40 хвилин. Хто від такого відмовиться?
Порівняйте шосе на 45 хвилин з вузькою вулицею. Навіть якщо вулицею їдуть усі 4000 машин, вона займає 40 хвилин. Чи буває так, що шосе вигідніше?
Якщо перемичка найкраща для кожного водія, хоч що роблять інші, нею поїдуть усі. Скільки машин тоді на кожній вузькій вулиці і скільки хвилин займає вся поїздка?
Повзунками розподіліть водіїв між маршрутами, а перемикачем відкрийте чи закрийте перемичку. Товщина дороги показує, скільки нею їде машин. Справа видно час кожного маршруту і чи хоче хтось перейти на швидший. Спробуйте знайти розподіл, за якого з відкритою перемичкою ніхто не хоче міняти маршрут.
Кожен із 4000 водіїв щоранку з певною ймовірністю передумує: дивиться у навігатор, скільки вчора тривав кожен маршрут, і обирає найшвидший. Навігатор трохи помиляється. Перемичку відкривають на 11-й день і закривають на 61-й. Графік показує, скільки в середньому їде водій.
Кожен водій моделюється окремо. Похибка навігатора означає, що до вчорашнього часу кожного маршруту додається випадкова помилка з таким стандартним відхиленням у хвилинах. Коли перемичку закривають, ті, хто нею їздив, наступного ранку обирають один із двох старих маршрутів.
Ніхто з водіїв не помиляється. Проблема в тому, що, обираючи дорогу, водій рахує лише свій час, а не час, який він забирає в інших.
Вулиця B → Фініш навіть ущент забита займає 4000/100 = 40 хвилин, а шосе завжди 45. Тому водієві, який доїхав до A, вигідніше перемичкою на B, хоч що роблять інші. Так само тому, хто стоїть на Старті, вигідніше вузька вулиця до A (≤ 40 хв), ніж шосе до B (45 хв). Обидва вибори разом дають маршрут перемичкою.
Новий водій на вузькій вулиці додає по 1/100 хвилини кожному, хто вже нею їде. Сам він цього не помічає, а разом це хвилини, а згодом і десятки хвилин. Поки перемичкою їде менше 500 водіїв, перехід вигідний усім разом. Далі кожен новий водій виграє собі менше, ніж забирає в інших.
| Мережа | Кожен сам | Диспетчер |
|---|---|---|
| Без перемички | 65 хв | 65 хв |
| З перемичкою | 80 хв | 64,69 хв |
1950 року Джон Неш назвав рівновагою такий стан гри, у якому жоден гравець не виграє, змінивши свій вибір сам. У нашій мережі з перемичкою рівновага одна: всі 4000 їдуть перемичкою. Звідти на маршрут через A чи через B переходити безглуздо: 85 хвилин замість 80.
Диспетчер, який розподіляє машини сам, пустив би перемичкою лише 500 водіїв, а решту порівну на маршрути через A і через B. Тоді в середньому 64,69 хвилини, на 19 секунд краще, ніж без перемички. Але цей розподіл нестійкий: ті, хто на шосе, одразу захочуть на перемичку.
Британський транспортний інженер Джон Вордроп 1952 року розділив дві мети. Перша описує, як водії розподіляються самі: усі маршрути, якими хтось їздить, займають однаковий час, і він не більший за час будь-якого іншого маршруту. Друга описує, як розподілив би їх планувальник: щоб сумарний час був найменшим. Без перемички обидва принципи дають одне й те саме, 2000 на 2000. Перемичка їх розводить.
Нехай a водіїв їдуть через A, b через B, z перемичкою, разом a + b + z = 4000. Вулицею Старт → A їдуть a + z машин, вулицею B → Фініш b + z.
Без перемички z = 0, а рівновага вимагає tA = tB, тобто a = b = 2000.
З перемичкою маршрут Z завжди швидший, бо b + z ≤ 4000 < 4500. Тому в рівновазі z = 4000.
Сумарний час для симетричного розподілу a = b = (4000 − z)/2 і його мінімум, який шукав би диспетчер.
Ціна анархії, тобто у скільки разів рівновага гірша за оптимум, у цій мережі:
Межа 4/3 не випадкова: 2002 року Тім Рафгарден і Єва Тардош довели, що коли час кожної дороги лінійно залежить від кількості машин, егоїстичні водії в будь-якій мережі витрачають щонайбільше на третину більше часу, ніж за найкращого розподілу.
Парадокс Браеса веде у три світи. У математиці він стає теорією ціни анархії: наскільки погано можуть розподілитися егоїстичні учасники. У логіці це та сама пастка, що й дилема в'язня. А на практиці міста закривають дороги, і рух від цього не гіршає.
Математика
Парадокс залежить від трафіку. Коли машин мало, до 3000, перемичка справді допомагає: вузькі вулиці майже порожні, і маршрут через неї найшвидший для всіх. Від 3000 до 9000 перемичка шкодить. Коли машин понад 9000, вузькі вулиці так забиті, що перемичкою вже ніхто не їде, і вона нічого не змінює.
Найбільша шкода при 4500 водіях: з перемичкою 90 хвилин, без неї 67,5. Відношення дорівнює рівно 4/3. Це не збіг: Рафгарден довів, що в мережі з лінійними дорогами нова дорога не може погіршити рівновагу більш ніж у 4/3 раза, і приклад Браеса досягає цієї межі.
1920 року економіст Артур Пігу розглянув дві дороги між тими самими містами. Перша завжди займає годину. Друга займає xd години, де x означає частку водіїв на ній. Друга ніколи не гірша за першу, тож егоїстичні водії їдуть нею всі і витрачають годину. Диспетчер пустив би частину водіїв першою дорогою, щоб друга була вільнішою.
За d = 1 ціна анархії дорівнює 4/3, як у Браеса. Рафгарден 2003 року показав, що для доріг із многочленним часом найгірший випадок у будь-якій мережі дає саме така пара доріг. Транспортні інженери часто описують затор формулою Бюро доріг США 1964 року, де час росте як четвертий степінь завантаження. Для d = 4 ціна анархії вже близько 2,15.
Логіка
Ви один із 4000 водіїв, а решта 3999 розподілилися якось. Повзунок задає, скільки з них їде перемичкою, інші порівну на два старі маршрути. Хоч куди ви його посунете, перемичка для вас швидша на 5–25 хвилин. Логіки тут дві: «що б не робили інші, мені краще так» і «якщо так зроблять усі, всім буде гірше». Обидві правильні.
Це будова дилеми в'язня, яку 1950 року придумали Мерріл Флад і Мелвін Дрешер у корпорації RAND, а назву й історію про в'язнів додав Альберт Такер. Двоє підозрюваних мовчать або зраджують, і зрада вигідна кожному, хоч що робить інший. Але якщо зрадять обидва, обом гірше, ніж якби обидва мовчали. Браес показав ту саму пастку для тисяч учасників, де кожен «зраджує», просто обираючи швидшу дорогу.
Практика
Ціну зручно міряти в хвилинах: скільки хвилин водієві не шкода, щоб не платити. Коли плата досягає 22,5 хвилини, перемичкою їдуть рівно 500 водіїв, як радив диспетчер, і середній час падає до 64,69. Плата не змушує нікого, вона лише додає до рішення водія той час, який він забирає в інших. Так працюють платні в'їзди до центру Лондона і Стокгольма.
Простіше перемичку закрити. 1969 року в Штутгарті рух покращився лише тоді, коли нову ділянку дороги знову закрили. 1990 року на День Землі в Нью-Йорку перекрили завжди забиту 42-гу вулицю, і обіцяного колапсу не сталося. 2003 року Сеул почав зносити естакаду Чхонгечхон, якою щодня їздило близько 170 тисяч машин, і на її місці 2005 року відкрили річку з парком. Місто розпланувало об'їзди й водночас реформувало автобуси, тож це не чистий експеримент, але затори не зросли.
2008 року фізики Хеджін Юн, Майкл Гастнер і Хавунг Чжон змоделювали вулиці Бостона, Нью-Йорка й Лондона і знайшли вулиці, закриття яких мало б скоротити час у дорозі.
Дітріх Браес надрукував статтю «Über ein Paradoxon aus der Verkehrsplanung» («Про парадокс транспортного планування») у німецькому журналі «Unternehmensforschung». Англійський переклад вийшов лише 2005 року в «Transportation Science».
За рік після статті Браеса Штутгарт уклав гроші в дорожню мережу, але рух не покращився, доки ділянку нової дороги знову не закрили. Цей випадок описав Вальтер Кнедель у книжці 1969 року про методи теорії графів.
На День Землі транспортний комісар Нью-Йорка Луціус Річчо закрив 42-гу вулицю на Мангеттені. Багато хто чекав «судного дня» на дорогах, але затору не сталося. 25 грудня «The New York Times» розповіла про це у статті Джини Колати з парадоксом Браеса.
Джоел Коен і Пол Горовіц описали в «Nature» конструкцію з пружин і мотузок, на якій висить вантаж. Якщо перерізати одну натягнуту мотузку, вантаж піднімається. Той самий ефект вони показали в електричному колі з резисторами й діодами.
Естакада Чхонгечхон завдовжки 5,6 км стояла над річкою, закутою в бетон. 2003 року мер Лі Мьон Бак почав її знесення, а 2005 року на її місці відкрили відновлену річку з парком. Машин, що в'їжджають у центр, стало на 2,3% менше.
Статтю Рафгардена й Тардош «How Bad Is Selfish Routing?» з межею 4/3 відзначили премією Геделя, однією з головних нагород теоретичної інформатики. Її розділили з двома іншими роботами з алгоритмічної теорії ігор, зокрема зі статтею, де Куцупіас і Пападімітріу ввели поняття ціни анархії.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Без формул» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.