Bugün öğrendim ki: Braess Paradoksu olarak bilinen, ek yolların trafiği azaltmak yerine daha fazla trafik yaratmasının mümkün olduğu
Yol Kapasitesini Artırmayla İlgili Paradoks
Braess paradoksu, bir yol ağına bir veya daha fazla yol eklemenin, genel trafik akışını yavaşlatabileceği gözlemidir. Paradoks ilk olarak 1920'de Arthur Pigou tarafından keşfedilmiş[1] ve daha sonra 1968'de Alman matematikçi Dietrich Braess'in adıyla anılmıştır[2].
Paradoksun elektrik şebekeleri ve biyolojik sistemlerde benzerlikleri olabilir. Teoride, arızalı bir ağın iyileştirilmesinin, belirli parçalarının çıkarılmasıyla gerçekleştirilebileceği öne sürülmüştür. Paradoks, mevcut ana yolların kapatılması durumunda trafik akışının iyileşmesini açıklamak için kullanılmıştır.
Keşif ve Tanım
[düzenle]
Almanya'daki Ruhr Üniversitesi'nde matematikçi olan Dietrich Braess, trafik modellemesi üzerinde çalışırken, bir yol ağına yeni bir yol eklenmesinin akışı engellediğini fark etti. Fikri, her sürücünün hangi güzergâhın en hızlı olduğuna dair en uygun öz çıkarlı kararı aldığında, sürücülerin mümkün olan en kısa seyahat sürelerine sahip olmaları için bir kısayolun çok sık seçilebileceğidir. Daha resmi olarak, Braess'in keşfinin ardındaki fikir, Nash dengesinin ağdaki genel en iyi akışa eşit olmayabileceğidir[3].
Paradoks şu şekilde ifade edilir:
Bir yol ağının her noktası için, oradan başlayan araç sayısı ve araçların hedefi verilsin. Bu koşullar altında, trafik akışının dağılımını tahmin etmek istenir. Bir sokağın diğerine tercih edilip edilmemesi yalnızca yolun kalitesine değil, aynı zamanda akışın yoğunluğuna da bağlıdır. Her sürücü kendileri için en uygun görünen yolu seçerse, ortaya çıkan çalışma süreleri minimum olmak zorunda değildir. Ayrıca, yol ağının genişletilmesinin, daha uzun bireysel çalışma sürelerine yol açan bir trafik yeniden dağılımına neden olabileceği bir örnekte gösterilmektedir.
Hareket eden varlıklar bencilce kendi güzergahlarını seçtiklerinde bir ağa ekstra kapasite eklemek, bazı durumlarda genel performansı azaltabilir. Bunun nedeni, böyle bir sistemin Nash dengesinin mutlaka optimal olmamasıdır. Ağ değişikliği, (çok oyunculu) mahkum ikilemine yol açan yeni bir oyun yapısı ortaya koyar. Bir Nash dengesinde, sürücülerin güzergahlarını değiştirmek için hiçbir teşvikleri yoktur. Sistem bir Nash dengesinde değilken, bireysel sürücüler aldıkları güzergahları değiştirerek kendi seyahat sürelerini iyileştirebilirler. Braess paradoksu durumunda, sürücüler genel performanstaki azalmaya rağmen Nash dengesine ulaşana kadar geçiş yapmaya devam edeceklerdir.
Gecikme fonksiyonları doğrusal ise, bir kenar eklemek, dengedeki toplam seyahat süresini 4/3'ten fazla bir faktörle asla kötüleştiremez[4].
Paradoksun Pratikte Olası Örnekleri
[düzenle]
Yaygınlık
[düzenle]
1983 yılında Steinberg ve Zangwill, makul[bağımsız kaynak gerekli] varsayımlar altında, yeni bir güzergah eklendiğinde genel bir ulaşım ağına Braess paradoksunun meydana gelmesi için gerekli ve yeterli koşulları sağlamıştır. (Sonucunun yalnızca tek bir bağlantı eklenmesi durumuna değil, herhangi bir yeni güzergâhın eklenmesine uygulandığını unutmayın.) Bir sonuç olarak, rastgele bir yeni güzergah eklendiğinde Braess paradoksunun meydana gelme olasılığının, meydana gelmeme olasılığıyla yaklaşık olarak aynı olduğunu elde ederler[5].
Trafik
[düzenle]
Ayrıca bakınız: Endüklenmiş talep
Braess paradoksunun, yol ağının azaltılması durumunda, bireysel yolculuk süresinde azalmaya neden olabilen bir karşılığı vardır[6].
Güney Kore'deki Seul'de, Cheonggyecheon restorasyon projesinin bir parçası olarak Cheonggye Otoyolu kaldırıldığında şehir etrafındaki trafik hızlanmıştır[7]. Almanya'daki Stuttgart'ta, 1969'da yol ağındaki yatırımlardan sonra, yeni inşa edilen bir yolun bir bölümü tekrar trafiğe kapatılana kadar trafik durumu düzelmemiştir[8]. 1990 yılında New York, Manhattan'daki 42. Cadde'nin Dünya Günü için geçici olarak kapatılması, bölgedeki tıkanıklığı azaltmıştır[9]. 2008 yılında Youn, Gastner ve Jeong, Boston, New York ve Londra'da gerçekten meydana gelebilecek belirli güzergahları göstermiş ve tahmini seyahat sürelerini azaltmak için kapatılabilecek yolları işaret etmiştir[10]. 2009 yılında New York, Times Meydanı ve Herald Meydanı'nda Broadway'in kapanmalarıyla deney yapmış ve bu da trafik akışının iyileşmesine ve kalıcı yaya alanlarına yol açmıştır[11].
2012 yılında, Île-de-France planlama ve geliştirme enstitüsünden Paul Lecroart, "Başlangıçtaki korkulara rağmen, ana yolların kaldırılması, başlangıçtaki ayarlamaların ötesinde trafik koşullarının bozulmasına neden olmaz. Trafik transferleri sınırlıdır ve beklentilerin altındadır" yazmıştır[6]. Ayrıca, bazı özel araç yolculuklarının (ve ilgili ekonomik faaliyetlerin) toplu taşımaya aktarılmadığını ve basitçe ortadan kaybolduğunu ("buharlaştığını") da belirtmektedir[6].
Aynı fenomen, yol kapatmanın bir kentsel projenin parçası olmaması, ancak bir kazanın sonucu olması durumunda da gözlemlenmiştir. 2012 yılında Rouen'de bir köprü yangında yıkılmıştır. Sonraki iki yıl boyunca diğer köprüler daha fazla kullanılmıştır, ancak köprülerden geçen toplam araç sayısı azalmıştır[6].
Elektrik
[düzenle]
2012 yılında, Max Planck Dinamik ve Öz-Organizasyon Enstitüsü'ndeki bilim insanları, hesaplama modellemesi yoluyla, enerji üretiminin merkezi olmayan olduğu güç iletim ağlarında olgunun meydana gelme potansiyelini göstermiştir[12].
2012 yılında, Institut Néel (CNRS, Fransa), INP (Fransa), IEMN (CNRS, Fransa) ve UCL (Belçika)'dan uluslararası bir araştırmacı ekibi, Physical Review Letters'da[13] Braess paradoksunun mezoskopik elektron sistemlerinde meydana gelebileceğini gösteren bir makale yayınlamıştır. Özellikle, nanoskopik bir ağdaki elektronlar için bir yol eklemenin paradoksal olarak iletkenliğini azalttığını göstermişlerdir. Bu, simülasyonlarla ve taramalı kapı mikroskobu kullanarak düşük sıcaklıkta yapılan deneylerle gösterilmiştir.
Yaylar
[düzenle]
Yaylar ve iplerle yapılan bir model, asılı bir ağırlığın, asılı sistemdeki gergin bir ipin kesilmesine rağmen yükseklikte yükselebileceğini ve orijinal Braess paradoksuyla aynı matematiksel yapıdan kaynaklandığını gösterebilir[14].
Kısa bir ip ile seri olarak birleştirilmiş iki özdeş yay için, toplam yay sabiti her bir ayrı yayın yarısıdır ve belirli bir ağırlık asıldığında uzun bir gerilme olur. Bu, üst yayın alt ucunu asılı ağırlığa (alt yayın alt ucu) ve alt yayın üst ucunu asılma noktasına (üst yayın üst ucu) bağlamak için gevşek iki daha uzun ip eklediğimizde de geçerlidir. Ancak, kısa ip kesildiğinde, daha uzun ipler gerilir ve iki yay birbirine (mekanik anlamda) paralel hale gelir. Toplam yay sabiti her bir ayrı yayın iki katıdır ve uzun iplerin uzunluğu çok uzun olmadığında, asılı ağırlık aslında kısa ip kesilmeden önceki durumuna göre daha yüksek olacaktır.
Asılı sistemde gergin bir ipin (kısa ip) kesilmesine rağmen asılı ağırlığın yükselmesi sezgiye aykırıdır, ancak Hooke yasasından ve yayların seri ve paralel olarak çalışma biçiminden kaynaklanır.
Biyoloji
[düzenle]
Adilson E. Motter ve işbirlikçileri, Braess paradoksu sonuçlarının biyolojik ve ekolojik sistemlerde sıklıkla meydana gelebileceğini göstermiştir[15]. Motter, bozulmuş bir ağın bir kısmının çıkarılmasının onu kurtarabileceğini öne sürüyor. Birçok türün ardışık olarak yok olmasının ardından birçok türün yok olmasının izleyebileceği nesli tükenmekte olan türlerin besin ağlarının kaynak yönetimi için, ağdan ölümcül bir türün seçici olarak çıkarılması, prensipte daha fazla yok oluş serisini önlemenin olumlu sonucunu getirebilir[16].
Takım Sporları Stratejisi
[düzenle]
Basketbolda, bir takımın, her yol için farklı bir verimlilikle ve aşırı kullanılan bir kısayolun bir yol ağındaki bir yolculuk için genel süreleri artırmasına benzer şekilde, sepet atmak için bir güzergâh olasılığı ağı olarak görülebileceği ve yıldız bir oyuncunun takımın genel verimliliğini azaltabileceği öne sürülmüştür. Skorlamada maksimum verimlilik için önerilen bir çözüm, yıldız bir oyuncunun takım arkadaşlarıyla yaklaşık aynı sayıda şut atmasıdır. Bununla birlikte, orijinal makalede belirtildiği gibi, bu yaklaşım güçlü istatistiksel kanıtlarla desteklenmemektedir[17].
Blok Zinciri Ağları
[düzenle]
Braess paradoksunun, 2. katman ağları olarak da bilinen blok zinciri ödeme kanalı ağlarında ortaya çıktığı gösterilmiştir[18]. Ödeme kanalı ağları, blok zincir ağlarının ölçeklenebilirlik sorununa bir çözüm uygular ve işlemleri blok zincirine kaydetmeden yüksek oranlarda gerçekleştirmeyi sağlar. Böyle bir ağda, kullanıcılar her kanalın her iki tarafında fonları kilitlemekle bir kanal kurabilirler. İşlemler ya doğrudan ödeme yapan ve ödeme alan kişiyi bağlayan bir kanal aracılığıyla ya da bazı ücretler isteyen ara kullanıcılarla kanallar yoluyla gerçekleştirilir.
Sezgisel olarak, yeni kanallar açmak daha yüksek yönlendirme esnekliği sağlarken, yeni bir kanal eklemek daha yüksek ücretlere, benzer şekilde mevcut kanalların kapatılması daha düşük ücretlere neden olabilir. Makale, paradoks için koşullar, paradoksu azaltma yöntemleri ve Bitcoin'in Lightning ağı üzerindeki paradoksun görünümünü ve etkilerini gösteren ampirik bir analiz içeren teorik bir analiz sunmaktadır.
Matematiksel Yaklaşım
[düzenle]
Örnek
[düzenle]
Yandaki diyagramda gösterilen bir yol ağını ele alalım; burada 4000 sürücü Başlangıç noktasından Bitiş noktasına gitmek istemektedir. Başlangıç-A yolu üzerindeki seyahat süresi dakikalar cinsinden, yolcuların (T) sayısının 100'e bölünmesidir ve Başlangıç-B üzerindeki seyahat süresi sabit 45 dakikadır (karşıdaki yollar için de aynısı geçerlidir). Kesikli yol yoksa (yani trafik ağı toplam 4 yoldan oluşuyorsa), a sürücüsüyle Başlangıç-A-Bitiş güzergahını kullanmanın süresi a/100 + 45 olur. b sürücüsüyle Başlangıç-B-Bitiş güzergahını kullanmanın süresi b/100 + 45 olur. 4000 sürücü olduğundan, a + b = 4000 gerçeği, sistem dengede olduğunda a = b = 2000 gerçeğini türetmek için kullanılabilir. Bu nedenle, her güzergâh 2000/100 + 45 = 65 dakika sürmektedir. Herhangi bir güzergâh daha az zaman alırsa, bu bir Nash dengesi olmaz: Mantıklı bir sürücü, daha uzun güzergâhtan daha kısa güzergâha geçer.
Şimdi, yaklaşık 0 dakika gibi son derece kısa bir seyahat süresine sahip kesikli A-B yolunun olduğunu varsayalım. Yolun açıldığını ve bir sürücünün Başlangıç-A-B-Bitiş yolunu denediğini varsayalım. Şaşkınlıkla, süresinin 2000/100 + 2001/100 = 40,01 dakika olduğunu, neredeyse 25 dakika tasarruf ettiğini görür. Yakında, 4000 sürücünün daha fazlası bu yeni güzergâhı denemektedir. Sürülen süre 40,01'den yükselir ve yükselmeye devam eder. Yeni güzergâhı deneyen sürücü sayısı 2500'e ulaştığında, 1500'ü hala Başlangıç-B-Bitiş güzergahındayken, süreleri 2500/100 + 4000/100 = 65 dakika olacak ve bu orijinal güzergâha göre bir iyileşme değildir. Bu arada, bu 1500 sürücü 45 + 4000/100 = 85 dakikaya yavaşlatılmıştır, bu da 20 dakikalık bir artıştır. A üzerinden yeni güzergâha geçmek zorundadırlar, bu nedenle şimdi 4000/100 + 4000/100 = 80 dakika sürmektedir. Kimsenin A-Bitiş veya Başlangıç-B'yi kullanmak için bir teşviki yoktur, çünkü bunları deneyen herhangi bir sürücü 85 dakika sürecektir. Bu nedenle, çapraz güzergâhın açılması, herkes tarafından ona geri dönüşü olmayan bir değişiklik tetikler ve herkese orijinal 65 yerine 80 dakika maliyeti çıkarır. Her sürücü A-B yolunu kullanmamayı kabul ederse veya bu güzergâh kapatılırsa, her sürücü 15 dakikalık bir seyahat süresi azalmasından faydalanacaktır.
Bir Dengenin Varlığı
[düzenle]
Her bir kişinin bir kenarda sürüşü için seyahat süresinin eşit olduğunu varsayarsak, bir denge her zaman var olacaktır.
Le(x), x kişi o kenarı kullandığında kenar e üzerinde seyahat eden her kişinin seyahat süresi formülü olsun. xe kişinin kenar e boyunca sürdüğü bir trafik grafiği olsun. e'nin enerjisi E(e),
∑i=1xe Le(i) = Le(1) + Le(2) + ⋯ + Le(xe)
(Eğer xe = 0 ise E(e) = 0 olsun). Trafik grafiğinin toplam enerjisi, grafikteki her kenarın enerjilerinin toplamı olsun.
Toplam enerjiyi en aza indiren bir güzergâh seçimi yapın. Böyle bir seçim, sonlu sayıda güzergâh seçeneği olduğu için var olmalıdır. Bu bir denge olacaktır.
Çelişki için varsayalım ki durum böyle değildir. O zaman, güzergâhı değiştirerek ve seyahat süresini iyileştirerek en az bir sürücü vardır. Orijinal güzergâhın e0, e1, …, en iken, yeni güzergâhın e'0, e'1, …, e'm olduğunu varsayalım. E, trafik grafiğinin toplam enerjisi olsun ve e0, e1, ..., en güzergâhının çıkarılması durumunda ne olduğunu düşünelim. Her kenar ei'nin enerjisi Lei(xei) kadar azalacak ve bu nedenle E, ∑i=0n Lei(xei) kadar azalacaktır. Bu, orijinal güzergâhı kullanmak için gereken toplam seyahat süresidir. Yeni güzergâh, e'0, e'1, …, e'm eklenirse, toplam enerji E, yeni güzergâhı kullanmak için gereken toplam seyahat süresi kadar artacaktır. Yeni güzergâh orijinal güzergâhtan daha kısa olduğundan, E orijinal yapılandırmaya göre azalmalıdır; bu da orijinal güzergâh kümesinin toplam enerjiyi en aza indirdiği varsayımına aykırıdır.
Bu nedenle, toplam enerjiyi en aza indiren güzergâh seçimi bir denge durumudur.
Bir Denge Bulma
[düzenle]
Yukarıdaki kanıt, doğrusal bir trafik grafiği için bir denge bulan ve sonlu sayıda adımda sonlanan en iyi yanıt dinamikleri olarak bilinen bir prosedürü özetlemektedir. Algoritma, "en iyi yanıt" olarak adlandırılır çünkü algoritmanın her adımında, grafik dengede değilse, bazı sürücülerin diğer tüm sürücülerin stratejilerine en iyi yanıtları vardır ve bu yanıta geçerler.
En İyi Yanıt Dinamikleri için Sahte Kod:
P bazı trafik kalıpları olsun. P dengede değilken: P'nin potansiyel enerjisi e'yi hesaplayın P'deki her sürücü d için: d için mevcut olan her alternatif yol p için: d yolu p aldığında kalıbın potansiyel enerjisi n'yi hesaplayın eğer n < e ise: d yolu p aldığında P'yi değiştirin en üstteki while'a devam edin
Her adımda, bazı belirli bir sürücü alternatif bir yol ("en iyi yanıt") alarak daha iyi bir performans sergileyebiliyorsa, bunu yapmak grafiğin enerjisini kesinlikle azaltır. Hiçbir sürücünün en iyi yanıtı yoksa, grafik dengededir. Grafiğin enerjisi her adımda kesinlikle azaldığından, en iyi yanıt dinamikleri algoritmasının sonunda durması gerekir.
Dengedeki Trafik Ne Kadar Optimolden Uzaktır?
[düzenle]
Seyahat süre fonksiyonları doğrusal ise, yani Le(x) = aex + be, bazı ae, be ≥ 0 için, o zaman en kötü durumda, enerjiyi en aza indiren dengedeki trafik sosyal olarak optimaldan iki kat daha kötüdür[19].
Kanıt: Z, ilişkili enerjisi E(Z) ve toplam seyahat süresi T(Z) olan bazı trafik yapılandırmaları olsun. Her kenar için enerji aritmetik bir dizinin toplamıdır ve aritmetik bir dizinin toplamı için formül kullanılarak E(Z) ≤ T(Z) ≤ 2E(Z) olduğu gösterilebilir. Zo sosyal olarak optimal trafik akışı ve Ze enerjiyi en aza indiren trafik akışı ise, eşitsizlik T(Ze) ≤ 2E(Ze) ≤ 2E(Zo) ≤ 2T(Zo) anlamına gelir.
Bu nedenle, enerjiyi en aza indiren denge için toplam seyahat süresi, optimal akış için olandan en fazla iki kat daha kötüdür.
Ağ Topolojisinin Etkisi
[düzenle]
Mlichtaich[20], Braess paradoksunun yalnızca ve ancak ağ seri-paralel bir grafik değilse meydana gelebileceğini kanıtlamıştır.
Ayrıca bakınız
[düzenle]
Downs-Thomson paradoksu – Yol ağındaki iyileştirmelerle ilgili trafik mühendisliğindeki paradoks
Jevons paradoksu – Verimlilik artan talebe yol açar
Marchetti sabiti – Ortalama yolculuk süresi
Lewis-Mogridge pozisyonu – Yol trafiği teorisi
Tıkanıklık oyunlarındaki anarşi fiyatı - tıkanıklığın dışsallıkları tarafından neden olunan verimlilik kaybının nicel bir analizi.
Referanslar
[düzenle]
Daha fazla okuma
[düzenle]
Braess, D. (1969). "Über ein Paradoxon aus der Verkehrsplanung" [Trafik Planlamasında Bir Paradoks Üzerine] (PDF). Unternehmensforschung (Almanca). 12: 258–268. (Nagurney & Wakolbinger tarafından çeviri)
Katharina Belaga-Werbitzky: „Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienern“ ISBN 3-89959-123-2
Braess 1968 makalesinin Almancadan İngilizceye çevirisi, Transportation Science dergisinde, cilt 39, 2005, ss. 446–450'de D. Braess, A. Nagurney ve T. Wakolbinger tarafından yazılan "Trafik Planlamasında Bir Paradoks Üzerine" makalesi olarak yer almaktadır. Daha fazla bilgi [Wayback Machine'de 27 Eylül 2011 tarihinde arşivlenmiş](https://web.archive.org/web/20110927114414/http://www.rpi.edu/~mitchj/braess.pdf)
Irvine, A. D. (1993). "Braess paradoksunun Newcomb problemini nasıl çözdüğü". Uluslararası Bilim Felsefesi Çalışmaları. 7 (2): 141–160. doi:10.1080/02698599308573460.
Steinberg, R.; Zangwill, W. I. (1983). "Braess Paradoksunun Yaygınlığı". Ulaşım Bilimi. 17 (3): 301. doi:10.1287/trsc.17.3.301.
Rapoport, A.; Kugler, T.; Dugar, S.; Gisches, E. J. (2009). "Tıkalı trafik ağlarındaki güzergâh seçimi: Braess Paradoksunun deneysel testleri" (PDF). Oyunlar ve Ekonomik Davranış. 65 (2): 538–571. doi:10.1016/j.geb.2008.02.007.
T. Roughgarden. "Anarşi Fiyatı." MIT Basım, Cambridge, MA, 2005.