Tímto článkem bych chtěl podat čtenářům špetku z teorie her aplikovanou
na dopravní systém. Auta se tady probírají docela často a podrobně, v tomto
článku chci ukázat, co dostaneme, když je hodně aut pohromadě.
Budu se
snažit použít co nejméně matematiky (přemíra matematických symbolů prý
to čtenáře odrazuje). Cílem není vyložit celou teorii najednou, spíš upozornit
na zajímavá fakta a pobídnout k dalšímu samostatnému bádání.
Nashova rovnováha
Začnu pojmem Nashova rovnováha. Je to pojem, na který v teorii
her narazíte téměř okamžitě. Podle názvu se čtenář dovtípí, že je pojmenován
po Johnu Nashovi. Definice Nashovy rovnováhy je vcelku prostá a intuitivní,
hodně neformální definice by byla asi tato:
Pokud žádný z hráčů nemůže zvýšit svůj zisk tím, že změní jednostranně
(tj. ostatní nezmění) svou strategii, je hra v Nashově rovnovážném bodě.
Přesnější (formálnější) definice najdete třeba na wikipedii (nebo v
pracích Johna Nashe).
Nashova hlavní zásluha je v tom, že dokázal, že pro každou hru s konečným
počtem hráčů a strategií existuje rovnovážný bod ve smíšených strategiích
(něco o smíšených strategiích si lehce najdete na internetu, tady s tím
nechci zdržovat, v tomto článku se bez nich obejdete). Stalo se tak v celkem
nenápadném článku, který vyšel v roce 1951 (a předtím ještě jeden v roce
1950).
Hra může mít i více rovnovážných bodů. V definici se nic neříká o výši
zisku pro jednotlivé hráče, zisk nemusí být pro všechny hráče stejný. Dokonce
ani není jasné, zdali se k této rovnováze hra dopracuje. Za určitých docela
přirozených podmínek (které je ale někdy v praxi obtížné splnit) se dá
dokázat, že iteračně se k nějaké rovnováze hráči dopracují.
Zatímco v teorii se o rovnovážném bodě pěkně mluví, v praxi je to poněkud
horší, protože život je složitější, než nějaká hra. Člověk většinou nemá
dost informací, nechová se úplně racionálně, případně jinak či špatně odhaduje
zisk své strategie (např. když obyvatel Brna volí v krajských volbách ČSSD
s vidinou "odpuštěných" poplatků v lékárně - v Brně není jediná krajská
lékárna). Ale jsou situace, kde se teorie her dá aplikovat docela dobře.
Prvním kouskem, který chci ukázat je Braessův paradox.
Braessův paradox
Prof. Dr. Dietrich Braess působí na "Fakultät für Mathematik Ruhr-Universität
Bochum" (tohle jsem se bál přeložit). V roce 1968 publikoval článek, kde
uvádí skutečný příklad, kdy po rozšíření dopravní sítě došlo proti očekáváním
ke zhoršení dopravní situace (prodloužení jízdní doby). Tento jev se dá
vysvětlit právě na základě Nashovy rovnováhy. Původní článek (v němčině)
i anglický překlad jsou k dispozici na univerzitních stránkách prof. Braesse.
Samozřejmě existuje i opačný jev, kdy se po odebrání spojnice jízdní doba
sníží (našel jsem jenom zmínku tohoto znění: „Earth Day 1990 - NYC closed
42nd street. Many were worried, actually improved.“, ale nikde jsem nenašel
mapku).
Demonstrace Braessova paradoxu
Pro jednoduchost předvedu zcela umělý příklad s nereálnými číselnými
hodnotami, aby paradox více vynikl (tento příklad se stejnými čísly najdete
u mnoha autorů, takže ani nevím, kdo s ním přišel první). V reálu nevychází
rozdíl tak divoce, ale je tam.
Představme si, že z místa A do místa B jede každé ráno 1000 aut. Mají
k dispozici 2 trasy, přes místa C a D. Jízdní doba na jednotlivých úsecích
může záviset na tom, kolik aut po trase jede (i tento předpoklad je v praxi
lehce nereálný, protože první auto projede bez zdržení, zdrží se až auta
za ním). Viz pokus o ASCII art.
_____ x/1000 _____
-------- | C | -------------------- | B |
/ ----- -----
1 / /
/ 1 /
/ /
_____ x/1000 _____ /
| A | ----------------------- | D | --------
----- -----
V úsecích AC a DB je jízdní doba 1 jednotka (třeba hodina) bez ohledu
na počet vozidel (představte si např. mnohaproudovou silnici). Naopak v
úsecích CB a AD je jízdní doba úměrná počtu vozidel označenému x (to by
byla nějaká úzká klikatá silnička).
Nedá moc práce zjistit, že Nashův rovnovážný bod je ve stavu, kdy půlka
aut (tj. 500) využije horní cestu ACB a druhá půlka spodní cestu. Tento
bod je zároveň "společenským optimem" v tom smyslu, že minimalizuje součet
jízdních dob všech aut, ale to sem až tak nepatří. Jízdní doba je v tomto
případě 1,5 jednotky.
Podívejme se na situaci, kdy nějaká hlava prosadí nápad, že přidá spojnici
CD s nulovou jízdní dobou (to je samozřejmě nereálné, ale pro jednoduchost
necháme nulu. Představte si třeba most přes řeku nebo tunel pod skalním
masívem, pár stovek metrů je mizivých ve srovnání např. s 50km). Nedá moc
práce zjistit, že původní rovnováha už není rovnováha, když řidič ze spodní
trasy ADB zvolí trasu ADCB, určitě si pomůže. Způsobí tak prodloužení jízdní
doby na horní cestě ACB, takže postižení řidiči začnou volit jinou strategii.
_____ x/1000 _____
-------- | C | ==================== | B |
/ ----- -----
1 / \\ /
/ \\ 0 1 /
/ \\ /
_____ x/1000 \\_____ /
| A | ======================= | D | ---------
----- -----
Nakonec se rovnováha posune do stavu, kdy všichni zvolí cestu ADCB
(na obrázku zdvojená). Jízdní doba tentokrát vyjde 2 jednotky, čili 4/3
původní doby (obzvláště to naštve řidiče, kteří projíždějí úsekem AD nebo
CB někam mimo obrázek a je jim docela volné, jak se dohodnou řidiči jedoucí
z A do B).
(Poznámka 1: číslo 4/3 nevyšlo náhodou. Pokud ve vzorci pro jízdní dobu
vystupuje x nanejvýš v první mocnině (tady to je x/1000), je to největší
možná hodnota. Pro vyšší mocniny x toto maximální číslo vyjde větší. Bližší
podrobnosti např. v doktorské práci Tima Roughgardena, viz odkazy).
Z tohoto příkladu je vidět, že Nashova rovnováha nemusí být optimální
(ale to byste se dočetli už v článku o Nashově rovnováze na wikipedii).
Zdánlivý paradox je v tom, že přidáním možnosti volby se situace zhorší.
Člověk by čekal, že když ke stávajícím možnostem dostane další volbu, může
si jenom polepšit.
Downs–Thomsonův paradox
(Též známý jako Pigou-Knight-Downs paradox)
Teď z jiného soudku. Z města A do města B dojíždí množství lidí do práce.
Dopravovat se můžou buďto vlakem nebo individuálně autem. Čistá jízdní
doba (ode dveří ke dveřím) je řekněme 40 minut vlakem a 30 minut autem.
Z nějakého důvodu se stane, že jízdní doba vlaku se zvýší (třeba nějaká
reorganizace, nové vedení apod.) na 50 minut. To povzbudí některé cestovatele
k přechodu od vlaku k autu. Následkem toho se ale zhorší dopravní zácpy
na silnici, takže jízdní doba autem se prodlouží na 40 minut. Ovšem vlakový
dopravce teď má prázdnější vlaky, takže se rozhodne prodloužit intervaly
mezi vlaky, takže jízdní doba vlakem se protáhne na 60 minut, což ovšem
povzbudí další cestovatele k přechodu na automobilovou dopravu. Silnice
je přeplněná a jízdní doba se zvýší na 50 minut. V tomto bodě zasáhnou
politici, kteří si libuji ve stříhání pásek a nechají stávající silnici
rozšířit (nebo postavit úplně novou). Jízdní doba se tak zkrátí na krásných
30 minut. Další část lidí z vlaku se přesune k automobilu, takže na silnici
je opět boží dopuštění a jízdní doba trvá 50 minut (za celou tu dobu se
cestovatelům změnila jízdní doba z původních 30/40 minut na 50/60 minut,
v tomto případě zcela záměrně vyšlo, že autem to nakonec trvá déle, než
předtím vlakem).
Shrnutí je v následující tabulce:
V obou případech je výsledek ten, že se utratila spousta peněz za rozšíření
silniční sítě, a situace se zhoršila.
Jak těmto paradoxům předcházet
Pokud si dobře pamatuji, tak jsem viděl nějaká kriteria na detekci Braessova
paradoxu v práci Tima Roughgardena (viz odkazy dole, mimochodem, měl to
moc pěkně zpracované), ale byla to spíš akademická diskuse. Když dáte v
Google hledat „detect braess paradox“, vypadne hromada článků. V jednodušších
případech by mělo být možné detekovat hrozbu Braessova paradoxu i bez velké
vědy. Stejně jako v jiných oblastech i tady platí, že by člověk měl jednat
s rozmyslem.
Pokud jde o Downs–Thomsonův paradox, tak nevím, žádné přesné kritérium
jsem nenašel. Vzhledem k množství vlivů to asi nebude jednoduché. Náprava
asi není tak jednoduchá, protože je těžší přesvědčit lidi, aby přesedlali
z auta na hromadnou dopravu. Navíc ne všichni se bez auta obejdou (představa
instalatéra, jak si vozí materiál vlakem je trošku mimo).
Mimo rámec článku je otázka, kolik investic do veřejné dopravy je ještě
efektivních a kdy už zvýšené náklady nepřinášejí užitek.
V obou ukázaných případech paradoxů je smůla, že větší množství lidí
se asi není schopno domluvit na společné strategii a pak ji dodržet (např.
nepoužívat spojnici CD). Pár takových experimentů jsme zažili a nedopadlo
to úplně dobře.
Braessův paradox může nastávat například i v počítačových sítích, ale
zatím se s ním daří bojovat, nejspíš i proto, že rychlost linek ještě stále
rychle roste (vysílání-nevysílání olympiády po internetu byl v podstatě
lokální problém).
Náměty na další čtení
V jednom článku se nedá popsat všechno, pro zvídavé uvádím pár námětů
na související témata. Kdybyste moc chtěli, možná bych napsal nějaký další
článek, ale už by to bylo trochu složitější čtení, objevily by se tam matematické
symboly.
Známé a zajímavé příklady Nashovy rovnováhy
· Vězňovo
dilema:
· Tragédie
obecní pastviny, to sice s dopravou nesouvisí vůbec, ale je to zajímavé,
v angličtině známá jako The
Tragedy of the Commons, prapůvodní článek
z roku 1968 anglicky:
Pareto dominance
V příkladu s Braessovým paradoxem jsme viděli, že v původním stavu je
jízdní doba každého cestovatele menší (tj. lepší), než v následném stavu
s přidanou spojnicí. O takovém (teď myslím to po přidání spojnice) řešení
se říká, že je Pareto-dominováno jiným řešením (anglicky Pareto-dominated,
Pareto není tajný kód, ale příjmení). Jak jsme viděli, toto lepší řešení
(bez spojnice CD) není rovnovážné a v praxi spadneme do jiného méně efektivního
řešení, které je stabilní.
Pár odkazů (většinou anglicky)
· Vilfredo Pareto
(česky)
· Vilfredo Pareto
· Pareto
dominance
· Pareto optimalita
· Pareto efektivita
(Pareto efficiency)
Dynamika dopravních zácp
Dynamiku dopravních zácp jsem záměrně pominul. Je to docela zajímavá,
ale velká oblast s přesahem do jiných odvětví mimo teorii her. Pokud vás
to zajímá, zkuste začít s časopisem Vesmír, kde je článek na toto téma.
Pokud chcete něco sami najít, tak dobrá klíčová slova jsou: (emergent)
traffic jam, (emergent) traffic congestion, Stop-and-Go Traffic, případně
můžete přidat slovo simulation apod.
Odkazy:
· Zákeřné dopravní zácpy, František Slanina, Vesmír 76, 545, 1997/10.
Na webu (pouze
pro předplatitele a hackery--správný identifikátor je 101)
· Dynamika lavín, Mária Markošová, Vesmír 76, 609, 1997/11. Lehce to
souvisí s předchozím článkem. Na webu
(opět jen pro předplatitele a hackery--id je 150)
Cena za chaos
Pokud vás zaujalo, že rovnovážný bod může znamenat značnou neefektivitu,
možná budete chtít najít víc článků na toto téma. Vhodná klíčová slova
jsou selfish routing, price of anarchy.
Odkazy
· Nashova
rovnováha (česky)
· Nashova rovnováha
(Nash equilibrium) (anglicky)
· Nashovy články:
o John F. Nash Jr., Equilibrium
Points in N-Person Games, PNAS 1950 36:48-49.
o John F. Nash Jr., Non-Cooperative
Games, The Annals of Mathematics 54(2):286-295. Článek je jenom pro
předplatitele JSTOR, ostatním se zobrazí jenom první strana. Dá se najít
i kompletní článek zálohovaný jinde, ale asi to není moc košer (doslova).
· Braessův
paradox (Braess paradox) (anglicky)
· Stránka
Dietricha Braesse (anglicky a německy). Na stránce je dostupná spousta
jeho prací.
· Downs–Thomson
paradox (anglicky)
· Stránka Tima Roughgardena.
Do práce Tima Roughgardena jsem se před několika lety začetl jenom náhodou
a jeho práce se mi hodně líbila. Na jeho stránkách je vystavených pár novějších
článků, původní doktorská práce je na této
adrese.
27.03.2010 TP