Դիտել Բրաեսի պարադոքս էջի վիքիկոդը

{{ՎՏՔ}}
'''Բրաեսի պարադոքսն''' այն դիտարկումն է, որ ճանապարհային ցանցին մեկ կամ մի քանի ճանապարհ ավելացնելը կարող է դանդաղեցնել դրա միջով երթևեկող մեքենաների ընդհանուր հոսքը: Պարադոքսն առաջին անգամ ձևակերպվել է [[Արթուր Սեսիլ Պիգու|Արթուր Պիգուի]] կողմից 1920 թվականին<ref>{{Citation |last=Pigou |first=Arthur Cecil |title=Welfare and Economic Welfare |date=2017-10-24 |work=The Economics of Welfare |pages=3–22 |url=http://dx.doi.org/10.4324/9781351304368-1 |access-date=2023-03-24 |publisher=Routledge |doi=10.4324/9781351304368-1 |isbn=978-1-351-30436-8}}</ref>։ Ավելի ուշ այն անվանվել է գերմանացի մաթեմատիկոս Դիտրիխ Բրաեսի անունով, 1968 թվականին<ref>{{Cite journal |last=Braess |first=D. |date=December 1968 |title=Über ein Paradoxon aus der Verkehrsplanung |url=http://dx.doi.org/10.1007/bf01918335 |journal=Unternehmensforschung Operations Research - Recherche Opérationnelle |volume=12 |issue=1 |pages=258–268 |doi=10.1007/bf01918335 |issn=0340-9422 |s2cid=39202189}}</ref>։

Պարադոքսը զուգահեռներ ունի էլեկտրական ցանցերում և կենսաբանական համակարգերում: Առաջակվել է տեսություն, որ անսարք ցանցի բարելավումը կարող է իրականացվել՝ հեռացնելով դրա որոշ մասերը: Պարադոքսն օգտագործվել է երթևեկության հոսքի բարելավման օրինակները բացատրելու համար, երբ առկա հիմնական ճանապարհները փակ են եղել:

== Բացահայտում և սահմանում ==
[[Գերմանիա|Գերմանիայի]] Ռուր համալսարանի մաթեմատիկոս Դիտրիխ Բրաեսը, երթևեկության մոդելավորման վրա աշխատելիս նկատել է, որ ճանապարհային ցանցում հոսքը կարող է խոչընդոտվել նոր ճանապարհ ավելացնելով: Նրա գաղափարն այն էր, որ եթե յուրաքանչյուր վարորդ սեփական շահերից ելնելով որոշում է կայացնում, թե որ երթուղին է ամենաարագն իր համար, ապա նույն դյուրանցումը կարող է շատ հաճախ ընտրվել վարորդների կողմից: Ավելի ֆորմալ, Բրաեսի հայտնագործության հիմքում ընկած գաղափարն այն է, որ [[նաշ էքուիլիպըրեում|Նեշի հավասարակշռությունը]] նման համակարգերում պարտադիր չէ լինի օպտիմալ<ref name="ReferenceA">New Scientist, [https://www.newscientist.com/article/mg22129520-600-42nd-st-paradox-cull-the-best-to-make-things-better/ 42nd St Paradox: Cull the best to make things better], 16 January 2014 by Justin Mullins</ref>։

Պարադոքսը պնդում է հետևյալը.
<blockquote>«Դիցուք ճանապարհային ցանցի յուրաքանչյուր կետի համար տրված է դրանից դուրս եկող մեքենաների քանակը և նրանց ժամանման վայրը: Այս պայմաններում ցանկանում ենք գնահատել երթևեկության հոսքի բաշխումը: Մի փողոցի մյուսից նախընտրելի լինելը կախված է ոչ միայն ճանապարհի որակից, այլ նաև [[Վեկտորական դաշտի հոսք|հոսքի խտությունից]]: Եթե ամեն վարորդ գնա իրեն ամենանախընտրելի ճանապարհով, արդյունքում նրանց ընթացքի ժամանակները պարտադիր չէ լինեն մինիմալ։ Ավելին, օրինակով ցույց է տրվում, որ ճանապարհային ցանցի ընդլայնումը կարող է առաջացնել երթևեկության վերաբաշխում, ինչը կհանգեցնի վարորդների անհատական ընթացքի ժամանակի երկարելուն»։</blockquote>

[[Գրաֆներ|Ցանցին]] լրացուցիչ ուղիներ ավելացնելը, երբ շարժվող մեքենաները իրենք են ընտրում են իրենց երթուղին, որոշ դեպքերում կարող է բերել ընդհանուր արդյունավետության նվազեցման: Դա պայմանավորված է նրանով, որ նման համակարգի [[նաշ էքուիլիպըրեում|Նեշի հավասարակշռությունը]] պարտադիր չէ, որ օպտիմալը լինի: Ցանցի փոփոխությունը առաջացնում է խաղի նոր կառուցվածք, որը հանգեցնում է (բազմախաղացող) [[Բանտարկյալի դիլեմա|բանտարկյալի երկընտրանքի]] : Նեշի հավասարակշռության պայմաններում վարորդները չունեն իրենց երթուղիները փոխելու խթան: Քանի դեռ համակարգը չի գտնվում Նեշի հավասարակշռության մեջ, առանձին վարորդներ կարող են բարելավել իրենց ճամփորդության ժամանակները՝ փոխելով իրենց երթուղիները: Բրաեսի պարադոքսի դեպքում վարորդները կշարունակեն փոխել ճանապարհները, մինչև հասնեն Նեշի հավասարակշռությանը՝ չնայած ընդհանուր արդյունավետության նվազմանը:

== Պարադոքսի հնարավոր օրինակներ ==

=== Տարածվածություն ===
1983-ին Սթայնբերգը և Զանգվիլը տրամադրեցին անհրաժեշտ և բավարար պայմանները, որպեսզի ողջամիտ ենթադրությունների պարագայում տրանսպորտային ցանցում տեղի ունենա Բրաեսի պարադոքսը, երբ նոր երթուղի է ավելացվում: (Նկատի ունեցեք, որ դրանց արդյունքը վերաբերում է ''ցանկացած'' նոր երթուղու ավելացմանը, այլ ոչ միայն մեկ կապող ճանապարհի:) Որպես արդյունք նրանք ստացան, որ պատահական նոր երթուղի ավելացնելիս Բրաեսի պարադոքսի տեղի ունենալը նույնքան հավանական է, որքան չունենալը<ref>{{Cite journal |last=Steinberg |first=R. |last2=Zangwill |first2=W. I. |year=1983 |title=The Prevalence of Braess' Paradox |journal=Transportation Science |volume=17 |issue=3 |pages=301 |doi=10.1287/trsc.17.3.301}}</ref>։

=== Երթևեկություն ===
[[Պատկեր:Cheonggyecheon_stream_1.jpg|մինի| Երբ Սեուլում արագընթաց մայրուղին հանվեց, որպեսզի վերականգնվի գետը, երթևեկությունը տարածքում բարելավվեց։]]
Բրաեսի պարադոքսին նման պնդում է՝ ճանապարհային ցանցի կրճատումը կարող է հանգեցնել անհատական երթևեկության ժամանակի կրճատմանը<ref name="Razemon">{{in lang|fr}} Olivier Razemon, "Le paradoxde de l'« évaporation » du trafic automobile", ''[[Լը Մոնդ|Le Monde]]'', Thursday 25 August 2016, page 5. Published on-line as [https://www.lemonde.fr/blog/transports/2016/08/23/voitures-evaporees/ "Quand les voitures s’évaporent"] on 24 August 2016 and updated on 25 August 2016 (page visited on 3 August 2023).</ref>։

[[Հարավային Կորեա|Հարավային Կորեայի]] [[Սեուլ]] քաղաքում երթևեկությունն արագացել է, երբ Չեոնգյե արագընթաց մայրուղին հանվել է Չեոնգյեչեոնի վերականգնման ծրագրի շրջանակներում<ref>{{Cite book |last=Easley |first=D. |title=Networks |last2=Kleinberg |first2=J. |date=2008 |publisher=Cornell Store Press |page=71}}</ref>։ [[Գերմանիա|Գերմանական]] [[Շտուտգարտ|Շտուտգարտում]], 1969 թվականին ճանապարհային աշխատանքների մեջ ներդրումներ կատարելուց հետո, երթևեկության իրավիճակը չբարելավվեց, մինչև նորակառույց ճանապարհի մի հատվածը կրկին չփակվեց<ref name="Knödel1969">{{Cite book |last=Knödel |first=W. |url=https://books.google.com/books?id=bJ22pwAACAAJ |title=Graphentheoretische Methoden Und Ihre Anwendungen |date=31 January 1969 |publisher=[[Springer-Verlag]] |isbn=978-3-540-04668-4 |pages=57–59}}</ref>։ 1990 թվականին [[Երկրի օր|Երկրի օրվա]] կապակցությամբ [[Նյու Յորք|Նյու Յորքի]] [[Մանհեթեն|Մանհեթենի]] 42-րդ փողոցի ժամանակավոր փակումը  նվազեցրեց այդ տարածքում խցանումների քանակը<ref>{{Cite news |last=Kolata |first=Gina |author-link=Gina Kolata |date=1990-12-25 |title=What if They Closed 42d Street and Nobody Noticed? |url=https://www.nytimes.com/1990/12/25/health/what-if-they-closed-42d-street-and-nobody-noticed.html |access-date=2008-11-16 |work=New York Times}}</ref>։ 2008 թվականին Յունը, Գաստները և Ջոնգը ցույց տվեցին կոնկրետ երթուղիներ Բոստոնում, Նյու Յորքում և Լոնդոնում, որտեղ խցանումներ կարող էին լինել, և մատնանշեցին ճանապարհներ, որոնց փակելու դեպքում կանխատեսված ճանապարհորդության ժամանակը կնվազեր<ref name="YounGastner2008">{{Cite journal |last=Youn |first=Hyejin |last2=Gastner |first2=Michael |last3=Jeong |first3=Hawoong |year=2008 |title=Price of Anarchy in Transportation Networks: Efficiency and Optimality Control |journal=Physical Review Letters |volume=101 |issue=12 |pages=128701 |arxiv=0712.1598 |bibcode=2008PhRvL.101l8701Y |doi=10.1103/PhysRevLett.101.128701 |issn=0031-9007 |pmid=18851419 |s2cid=20779255}}</ref>։ 2009-ին Նյու Յորքը փորձարկեց փակել [[Բրոդվեյ (փողոց)|Բրոդվեյը]] [[Թայմս Սքվեր|Թայմս Սքվերում]] և Հերալդ Սքվերում, ինչը հանգեցրեց երթևեկության բարելավմանը և մշտական հետիոտնային հրապարակներին<ref>{{Cite episode |title=Braess' Paradox |url=http://www.uh.edu/engines/epi2814.htm |series=Engines of Our Ingenuity |last=Boyd |first=Andrew |number=2814}}</ref>։

2012-ին Պոլ Լեկրոտը, [[Իլ դը Ֆրանս (երկրամաս)|Իլ-դե-Ֆրանսի]] պլանավորման և զարգացման ինստիտուտից, գրել է՝ «Չնայած մտավախություններին, հիմնական ճանապարհների հեռացումը չի հանգեցնում երթևեկության պայմանների վատթարացմանը:»:  Նա նաև նշում է, որ մասնավոր տրանսպորտային միջոցներով որոշ ուղևորություններ (և հարակից տնտեսական գործունեություն) չեն տեղափոխվում հասարակական տրանսպորտ և պարզապես անհետանում են («գոլորշիանում»)<ref name="Razemon" />։

Նույն երևույթը նկատվել է նաև, երբ ճանապարհների փակվել են ոչ թե քաղաքային ծրագրի շրջանակներում, այլ վթարի հետևանքով։ 2012 թվականին [[Ռուան|Ռուենում]] կամուրջ է ավերվել հրդեհից։ Հաջորդ երկու տարիների ընթացքում ավելի շատ օգտագործվեցին այլ կամուրջներ, սակայն կամուրջներով անցնող մեքենաների ընդհանուր թիվը կրճատվեց։ 

=== Էլեկտրականություն ===
2012թ.-ին Մաքս Պլանկի դինամիկայի և ինքնակազմակերպման ինստիտուտի գիտնականները մոդելավորման միջոցով ցույց տվեցին երևույթի հավանականությունը էլեկտրահաղորդման ցանցերում, որտեղ էլեկտրաէներգիայի արտադրությունը ապակենտրոնացված է: <ref name="rdmag_mpi">{{Citation |last=Staff (Max Planck Institute) |title=Study: Solar and wind energy may stabilize the power grid |date=September 14, 2012 |work=[[R&D Magazine]] |url=https://www.rdworldonline.com/study-solar-and-wind-energy-may-stabilize-the-power-grid/ |access-date=September 14, 2012 |at=rdmag.com}}</ref>

2012 թվականին Institut Néel (CNRS, Ֆրանսիա), INP (Ֆրանսիա), IEMN (CNRS, France) և UCL (Բելգիա) հետազոտողների միջազգային թիմը ''Physical Review Letters''<ref name="PalaBaltazar2012">{{Cite journal |last=Pala |first=M. G. |last2=Baltazar |first2=S. |last3=Liu |first3=P. |last4=Sellier |first4=H. |last5=Hackens |first5=B. |last6=Martins |first6=F. |last7=Bayot |first7=V. |last8=Wallart |first8=X. |last9=Desplanque |first9=L. |last10=Huant |first10=S. |year=2012 |title=Transport Inefficiency in Branched-Out Mesoscopic Networks: An Analog of the Braess Paradox |journal=Physical Review Letters |volume=108 |issue=7 |pages=076802 |arxiv=1112.1170 |bibcode=2012PhRvL.108g6802P |doi=10.1103/PhysRevLett.108.076802 |issn=0031-9007 |pmid=22401236 |s2cid=23243934}}</ref> ամսագրում հրապարակեց մի գիտական աշխատանք, որը ցույց էր տալիս, որ Բրաեսի պարադոքսը կարող է առաջանալ մեզոսկոպիկ էլեկտրոնային համակարգերում։ Մասնավորապես, նրանք ցույց տվեցին, որ նանոսկոպիկ ցանցում էլեկտրոնների համար ուղի ավելացնելը պարադոքսալ կերպով նվազեցնում է դրա հաղորդունակությունը: Դա ցույց են տվել ինչպես սիմուլյացիաները, այնպես էլ ցածր ջերմաստիճանում արված փորձերը:

=== Զսպանակներ ===
[[Պատկեր:Braess-Paradoxon_der_Mechanik.svg|մինի| Աջ կողմում երկու զսպանակներ են՝ հաջորդաբար միացված կարճ պարանով։ Երբ B և C-ն միացնող կարճ պարանը հանվում է (ձախ), քաշը ավելի բարձր է կախվում:]]
Զսպանակներով և պարաններով մոդելը ցույց է տալիս, որ կախված կշիռը կարող է բարձրանալ, չնայած, որ կախովի համակարգում ձգված պարանը կտրված է։ Սա բխում է նույն մաթեմատիկական կառուցվածքից, ինչպիսին Բրաեսի սկզբնական պարադոքսն է<ref>{{Cite web |last=Mould |first=Steve |date=29 July 2021 |title=The Spring Paradox |url=https://www.youtube.com/watch?v=Cg73j3QYRJc |access-date=2 December 2022 |website=YouTube |language=en}}</ref>։

Կարճ պարանով միմյանց հաջորդաբար միացված երկու միանման զսպանակների ընդհանուր զսպանակային հաստատունը յուրաքանչյուր առանձին զսպանակի հաստատունի կեսին է հավասար, ինչը հանգեցնում է երկար ձգման, երբ կախված է որոշակի քաշ: Այսպես է մնում, երբ մենք երկու երկար պարան ենք ավելացնում, որպեսզի միացնենք վերին զսպանակի ստորին ծայրը կախված քաշին (ներքևի զսպանակի ստորին ծայրը), իսկ ստորին զսպանակի վերին ծայրը կախված կետին (վերին զսպանակի վերին ծայրը): Այնուամենայնիվ, երբ կարճ պարանը կտրվում է, երկար պարանները ձգվում են, և երկու զսպանակները դառնում են զուգահեռ (մեխանիկական իմաստով) միմյանց: Զսպանակի ընդհանուր հաստատունը երկու անգամ գերազանցում է յուրաքանչյուր առանձին զսպանակի հաստատունին, և երբ երկար պարանների երկարությունը շատ մեծ չէ, կախված քաշը իրականում ավելի բարձր կլինի՝ համեմատած կարճ պարանը կտրելուց առաջ:

Կախված կշռի բարձրանալը, կարճ պարանը կտրելուց հետո, կարող է հակաինտուիտիվ թվալ, բայց սա բխում է [[Հուկի օրենք|Հուկի օրենքից]] և զսպանակների հաջորդական և զուգահեռ աշխատանքի եղանակից:

=== Կենսաբանություն ===
Ադիլսոն Է. Մոթերը և նրա գործընկերները ցույց տվեցին, որ Բրաեսի պարադոքսը հաճախ կարելի է տեսնել կենսաբանական և էկոլոգիական համակարգերում<ref>{{Cite journal |last=Motter |first=Adilson E. |year=2010 |title=Improved network performance via antagonism: From synthetic rescues to multi-drug combinations |journal=BioEssays |volume=32 |issue=3 |pages=236–245 |arxiv=1003.3391 |doi=10.1002/bies.200900128 |pmc=2841822 |pmid=20127700}}</ref>:  Մոթերն առաջարկում է, որ խաթարված ցանցի մի մասը հեռացնելը կարող է փրկել այն: Վտանգված տեսակների սննդային ցանցերի ռեսուրսների կառավարման համար, որտեղ շատ տեսակների անհետացում կարող է լինել, դատապարտված տեսակների ընտրովի հեռացումը ցանցից սկզբունքորեն կարող է բերել դրական արդյունքի՝ կանխելով հետագա անհետացումները<ref>Sahasrabudhe S., Motter A. E., [http://www.nature.com/articles/ncomms1163 Rescuing ecosystems from extinction cascades through compensatory perturbations], Nature Communications 2, 170 (2011)</ref>: 

=== Թիմային սպորտի ռազմավարություն ===
Առաջարկվել է տեսություն, որ բասկետբոլում թիմը կարող է դիտվել որպես գնդակը զամբյուղին հասցնելու հնարավոր երթուղիների ցանց՝ յուրաքանչյուրը տարբեր արդյունավետությամբ, իսկ լավագույն խաղացողը կարող է նվազեցնել թիմի ընդհանուր արդյունավետությունը՝ ինչպես ճանապարհային դյուրանցում, որը չափից շատ է օգտագործվում՝ ավելացնելով ճանապարհային ցանցով երթևեկության ընդհանուր ժամանակը: Միավորներ հավաքելու առավելագույն արդյունավետության համար առաջարկվող լուծումն այն է, որ լավագույն խաղացողը նույնքան հարված կատարի, որքան իր թիմակիցները: Սակայն այս մոտեցումը չի հաստատվել վիճակագրական ապացույցներով, ինչպես նշված է սկզբնական գիտական աշխատանքում<ref>{{Cite journal |last=Skinner |first=Brian |last2=Gastner |first2=Michael T |last3=Jeong |first3=Hawoong |year=2009 |title=The price of anarchy in basketball |journal=Journal of Quantitative Analysis in Sports |volume=6 |issue=1 |arxiv=0908.1801 |bibcode=2009arXiv0908.1801S |citeseerx=10.1.1.215.1658 |doi=10.2202/1559-0410.1217 |s2cid=119275142}}</ref>: 

=== Բլոկչեյն ցանցեր ===
Բրաեսի պարադոքսը դիտվում է նաև բլոկչեյն վճարային ուղիների ցանցերում: <ref>{{Cite book |last=Kotzer |first=Arad |title=2023 IEEE International Conference on Blockchain and Cryptocurrency (ICBC) |last2=Rottenstreich |first2=Ori |year=2023 |isbn=979-8-3503-1019-1 |pages=1–9 |chapter=Braess Paradox in Layer-2 Blockchain Payment Networks |doi=10.1109/ICBC56567.2023.10174986 |chapter-url=https://ieeexplore.ieee.org/document/10174986}}</ref> Վճարային ուղիների ցանցերը լուծում են բլոկչեյն ցանցերի մասշտաբայնության խնդիրը՝ թույլ տալով բարձր դրույքաչափերով գործարքներ՝ առանց դրանք բլոկչեյնում գրանցելու: Նման ցանցում օգտատերերը կարող են ստեղծել ուղի՝ փակելով միջոցները ուղու յուրաքանչյուր կողմում: Գործարքները կատարվում են կա՛մ վճարողին և ստացողին ուղղակի կապող ուղու միջոցով, կա՛մ միջանկյալ օգտվողների հետ կապուղիների միջոցով, որոնք պահանջում են որոշակի վճար:

Թեև ինտուիտիվ կերպով, նոր ուղիների բացումը բերում է երթուղիների ավելի ճկուն ընտրության հնարավորության, նոր ուղի ավելացնելը կարող է ավելի բարձր վճարներ առաջացնել, և նմանապես՝ գոյություն ունեցող ուզիների փակումը կարող է նվազեցնել վճարները:

== Մաթեմատիկական մոտեցում ==

=== Օրինակ ===
[[Պատկեր:Braess_paradox_road_example.svg|աջից|500x500փքս]]
Դիտարկենք ճանապարհային ցանց, ինչպես ցույց է տրված պատկերում, որի վրա 4000 վարորդ ցանկանում է մեկնել սկզբնակետից վերջնակետ: Start–A ճանապարհի վրա  ճամփորդության ժամանակը րոպեներով հավասար է ճամփորդների քանակը (T) բաժանած 100-ի, իսկ Start–B-ում՝ հաստատուն 45 րոպե է (նմանապես նրանց դիմացի ճանապարհներին)։ Եթե կետագծերով ճանապարհը գոյություն չունենա (այսինքն երթևեկության ցանցն ընդհանուր առմամբ ունենա 4 ճանապարհ), ապա Start-A-End երթուղին անցնելու համար անհրաժեշտ ժամանակը <math>a</math> վարորդների դեպքում կլինի <math>\tfrac{a}{100} + 45</math> . Ժամանակը, որն անհրաժեշտ կլինի Start-B-End երթուղին վարելու համար <math>b</math> վարորդների դեպքում կլինի <math>\tfrac{b}{100} + 45</math> . Քանի որ ընդհանուր 4000 վարորդ կա, <math>a + b = 4000</math> պայմանից կարելի է ստանալ հետևություն, որ <math>a = b = 2000</math> երբ համակարգը գտնվում է հավասարակշռության մեջ։ Հետևաբար, յուրաքանչյուր երթուղի տևում է <math>\tfrac{2000}{100} + 45 = 65</math> րոպե. Եթե որևէ երթուղի ավելի քիչ ժամանակ պահանջեր, ապա Նեշի հավասարակշռություն տեղի չէր ունենա. ռացիոնալ վարորդը ավելի երկար երթուղուց կանցներ ավելի կարճ երթուղու:

Այժմ ենթադրենք, որ A–B կետագիծը ճանապարհ է, որով երթևեկելը չափազանց արագ է, մոտավորապես 0 րոպե: Ենթադրենք, որ ճանապարհը բաց է, և մի վարորդ փորձում է Start–A–B–End երթուղին: Ի զարմանս իրեն նա գտնում է, որ իր ժամանակը <math>\tfrac{2000}{100} + \tfrac{2001}{100} = 40.01</math> րոպե է դառնում, գրեթե 25 րոպե կարճ: Շուտով 4000 վարորդներից շատերը կփորձեն այս նոր երթուղին: Ժամանակը բարձրանում է 40.01-ից և շարունակում է բարձրանալ: Երբ նոր երթուղին փորձող վարորդների թիվը հասնում է 2500-ի, իսկ 1500-ը դեռ Start-B-End  ուղու վրա են, նրանց ժամանակը կկազմի <math>\tfrac{2500}{100} + \tfrac{4000}{100} = 65</math> րոպե, ինչը բարելավում չէ սկզբնական երթուղու համեմատ: Մինչդեռ այդ 1500 վարորդների երթևեկությունը դարձավ <math> 45 + \tfrac{4000}{100} = 85</math> րոպե, 20 րոպե ավելի երկար: Նրանք պարտավորված են այժմ նոր երթուղով գնալ՝ անցնելով A կետով, ուստի իրենց ժամանակը կդառնա <math>\tfrac{4000}{100} + \tfrac{4000}{100} = 80</math> րոպե։ Ոչ ոք որևէ դրդապատճառ չունի ճանապարհորդելու A-End կամ Start-B ուղիներով, քանի որ ցանկացած վարորդ այդ դեպքում կծախսի 85 րոպե: Այսպիսով, խաչմերուկի բացումը հանգեցնում է բոլորի կողմից դրա անշրջելի փոփոխությանը՝ յուրաքանչյուրի համար ճանապարհի տևողությունը սկզբնական 65-ի դարձնելով 80 րոպե: Եթե բոլոր վարորդները համաձայնվեն չօգտվել A-B ուղուց, կամ եթե այդ երթուղին փակվի, ապա յուրաքանչյուր վարորդ կշահի ճանապարհորդության ժամանակի 15 րոպեի կրճատում:

=== Հավասարակշռության առկայությունը ===
Հավասարակշռությունը միշտ գոյություն կունենա եթե կա ենթադրություն, որ բոլոր անձանց երթևեկության ժամանակը ուղու վրա հավասար է:

Դիցուկ <math>L_e(x)</math>-ը <math>e</math> ուղով ճանապարհորդող յուրաքանչյուր անձի ճամփորդության ժամանակի բանաձևն է, երբ այդ ուղով երթևեկում են <math>x</math> մարդիկ: Ենթադրենք, որ կա երթևեկության գրաֆ, որտեղ <math>x_e</math> մարդիկ քշում են <math>e</math> կողով։ Թող <math>e</math>-ի էներգիան՝ <math>E(e)</math>-ն լինի

: <math>\sum_{i=1}^{x_e} L_e(i) = L_e(1) + L_e(2) + \cdots + L_e(x_e)</math>

(Եթե <math>x_e = 0</math> թող <math>E(e) = 0</math>)։ Դիցուկ տրաֆիկի գրաֆի ընդհանուր էներգիան հավասար է նրա բոլոր կողերի էներգիաների գումարին:

Ընտրեք երթուղիներ, որոնք նվազագույնի են հասցնում ընդհանուր էներգիան: Նման ընտրություն պետք է գոյություն ունենա, քանի որ երթուղիների ընտրությունը վերջավոր է: Դա կլինի հավասարակշռության կետը:

Այժմ ենթադրենք հակառակը․ սա կնշանակի, որ կա առնվազն մեկ վարորդ, ով կարող է փոխել երթուղին և բարելավել իր ճամփորդության ժամանակը: Ենթադրենք սկզբնական երթուղին է <math>e_0, e_1, \ldots, e_n</math>, մինչդեռ նոր երթուղին է <math>e'_0, e'_1, \ldots, e'_m</math> ։ Թող <math>E</math>-ն լինի երթևեկության գրաֆի ընդհանուր էներգիան․ նկատենք, թե ինչ է տեղի ունենում երբ <math>e_0, e_1, ... e_n</math> երթուղին հանվում է։ Յուրաքանչյուր կողի էներգիան՝ <math>e_i</math>-ն կկրճատվի <math>L_{e_i}(x_{e_i})</math>-ով, և այսպիսով <math>E</math>-ն կկրճատվի <math display="inline">\sum_{i=0}^n L_{e_i}(x_{e_i})</math>-ով։ Սա պարզապես ճանապարհորդության ընդհանուր ժամանակն է, որն անհրաժեշտ է սկզբնական երթուղին անցնելու համար: Եթե նոր <math>e'_0, e'_1, \ldots, e'_m</math>երթուղին ավելացվի, ընդհանուր էներգիան կավելանա նոր երթուղին անցնելու համար անհրաժեշտ ընդհանուր ժամանակով: Քանի որ նոր երթուղին ավելի կարճ է, քան սկզբնական երթուղին, <math>E</math>-ն պետք է նվազի սկզբնականի համեմատ՝ հակասելով այն ենթադրությանը, որ երթուղիների սկզբնական խումբը նվազագույնի է հասցրել ընդհանուր էներգիան:

Հետևաբար, ընդհանուր էներգիան նվազագույնի հասցնելու երթուղիների ընտրությունը հավասարակշռության կետն է:

=== Հավասարակշռություն գտնելը ===
Վերոհիշյալ ապացույցը ցույց է տալիս մի ընթացակարգ, որը հայտնի է որպես [[Լավագույն արձագանք|լավագույն արձագանքի]] դինամիկա, որը գտնում է տրաֆիկի գծային գրաֆի հավասարակշռությունը և ավարտվում է վերջավոր քանակությամբ քայլերով: Ալգորիթմը կոչվում է «լավագույն արձագանք», քանի որ ալգորիթմի յուրաքանչյուր քայլում, եթե գրաֆը հավասարակշռության մեջ չէ, մի վարորդ տալիս է իր լավագույն արձագանքը՝ մյուս բոլոր վարորդների ռազմավարություններին։

Լավագույն արձագանքման դինամիկայի կոդ.
 Let ''P'' be some traffic pattern.
 '''while''' ''P'' is not at equilibrium:
     compute the potential energy ''e'' of ''P''
     '''for each''' driver ''d'' in ''P'':
         '''for each''' alternate path ''p'' available to ''d'':
             compute the potential energy ''n'' of the pattern when ''d'' takes path ''p''
             '''if''' ''n'' < ''e'':
                 modify ''P'' so that ''d'' takes path ''p''
 '''continue''' the topmost '''while'''
Յուրաքանչյուր քայլում, եթե որոշակի վարորդ կարող է կրճատել իր ժամանակը՝ անցնելով այլընտրանքային ճանապարհի («լավագույն արձագանքը»), ապա դա անելը խստորեն նվազեցնում է գրաֆի էներգիան: Եթե ոչ մի վարորդ չունի լավագույն արձագանք, ապա գրաֆը գտնվում է հավասարակշռության մեջ: Քանի որ գրաֆի էներգիան խստորեն նվազում է յուրաքանչյուր քայլի հետ, լավագույն արձագանքի դինամիկայի ալգորիթմը ի վերջո ավարտին կգա:

=== Որքա՞ն հեռու է օպտիմալից երթևեկությունը հավասարակշռության մեջ: ===
Եթե երթևեկության ժամանակի ֆունկցիաները գծային են, այսինքն <math>L_e(x) = a_e x + b_e</math> որոշ <math>a_e, b_e \geq 0</math>-ի համար, ապա վատագույն դեպքում՝ էներգիան նվազագույնի հասցնող հավասարակշռության մեջ երթևեկությունը երկու անգամ ավելի վատն է, քան սոցիալապես օպտիմալը: <ref name="EasleyKleinberg">
{{Cite web |last=Easley |first=David |last2=Kleinberg |first2=Jon |title=Networks, Crowds, and Markets: Reasoning about a Highly Connected World (8.3 Advanced Material: The Social Cost of Traffic at Equilibrium) |url=http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book.pdf |url-status=live |archive-url=https://web.archive.org/web/20150316015111/http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book.pdf |archive-date=2015-03-16 |access-date=2015-05-30 |website=Jon Kleinberg's Homepage |publisher=Jon Kleinberg}} – This is the preprint of {{ISBN|9780521195331}}</ref>

Ապացույց․ դիցուկ <math>Z</math>-ը երթևեկության որոշակի կոնֆիգուրացիա է՝ <math>E(Z)</math> էներգիայով և <math>T(Z)</math> ճանապարհորդության ընդհանուր ժամանակով։ Յուրաքանչյուր կողի համար էներգիան [[Թվաբանական պրոգրեսիա|թվաբանական պրոգրեսսիայի]] գումարն է, և օգտագործելով թվաբանական պրոգրեսսիայի գումարի բանաձևը, կարելի է ցույց տալ, որ <math>E(Z)\leq T(Z)\leq 2E(Z)</math> ։ Եթե <math>Z_o</math>-ն սոցիալապես օպտիմալ երթևեկության հոսքն է և <math>Z_e</math>-ն էներգիան նվազագույնի հասցնող երթևեկության հոսքն է, անհավասարությունը ցույց է տալիս, որ <math>T(Z_e) \leq 2E(Z_e) \leq 2E(Z_o) \leq 2T(Z_o)</math> ։

Այսպիսով, էներգիան նվազագույնի հասցնող հավասարակշռության  մեջ ընդհանուր ճանապարհորդության ժամանակը առավելագույնը երկու անգամ ավելի վատն է, քան օպտիմալ հոսքի ժամանակ:

=== Ցանցի տոպոլոգիայի ազդեցություն ===
Միլխտայքը<ref>{{Cite journal |last=Milchtaich |first=Igal |date=2006-11-01 |title=Network topology and the efficiency of equilibrium |url=https://www.sciencedirect.com/science/article/pii/S0899825605001284 |journal=Games and Economic Behavior |language=en |volume=57 |issue=2 |pages=321–346 |doi=10.1016/j.geb.2005.09.005 |issn=0899-8256 |hdl-access=free}}</ref> ապացուցել է, որ Բրաեսի պարադոքսը կարող է առաջանալ միայն այն դեպքում, եթե ցանցը շարքային զուգահեռ գրաֆ չէ:

== Ծանոթագրություններ ==
{{ծանցանկ}}
[[Կատեգորիա:1968 հայտնություններ]]
[[Կատեգորիա:Մաթեմատիկական պարադոքսներ]]