Bölüm 8: Ağ Tasarımı ve Yönlendirme

8.1Ağlar ve yönlendirme

Bu bölümün bütün kavramları tek bir gerilimin etrafında döner: bir ağın kullanıcıları kendi yolculuklarını kısaltmak ister, ama her kullanıcının seçimi ötekilerin yolculuğunu da uzatır. Önce küçük bir oyunla bu gerilimi somutlaştırıyoruz. Ardından ağ, bağlantı, kapasite ve gecikme gibi temel kavramları tanımlıyoruz. Bu kavramlar, sonraki kesimlerdeki bütün hesapların dilidir.

8.1.1Bir oyunla başlangıç: Braess paradoksu

N sürücü, S noktasından T noktasına gitmek ister. İki rota vardır: S→A→T (üst yol) ve S→B→T (alt yol). Her rotada bir dar yol ve bir geniş yol bulunur. Dar yolların süresi o yolu kullanan sürücü sayısıyla artar: dar yolda x sürücü varsa yolculuk 40 · x / N dakika sürer. Bütün sürücüler aynı dar yola girerse süre 40 dakikaya çıkar; hiç kimse yoksa yol boştur. Geniş yolların süresi ise trafikten bağımsızdır, her zaman 45 dakikadır.

Oyunun kuralı basittir: her sürücü kendi en hızlı yolunu seçer. Kimse ötekilerin süresini önemsemez; herkes yalnız kendi yolculuğuna bakar. Bu, “bencil” bir davranıştır ama kötü niyetli değildir. Sabah işe giden bir sürücü de navigasyon uygulamasının önerdiği en hızlı rotayı seçer; başkalarının yolculuğunu düşünmesi beklenmez.

Şekil 8.1 oyunun ağını gösterir. Kestirme yokken iki rota birbirinin aynası gibidir. Sürücüler iki rotaya eşit bölünürse her dar yolda N/2 sürücü olur ve dar yol 40 · (N/2)/N = 20 dakika sürer. Her rota böylece 20 + 45 = 65 dakikadır. Oyun iki merak sorusuyla başlar:

• A'dan B'ye süresi 0 olan bir kestirme açılırsa yolculuklar kısalır mı?
• Herkes kendi en hızlı yolunu seçince ortalama süre en küçük olur mu?

Sağduyu iki soruya da “evet” der. Yeni bir yol kapasiteyi artırır; daha çok kapasite daha az tıkanıklık demek gibi görünür. Herkesin en hızlı yolu seçmesi de “en hızlı” sonucu vermelidir. Bu bölümün en şaşırtıcı sonucu, iki cevabın da “hayır” olabileceğidir. Kestirme açıldığında her sürücü zikzak rotaya (S→A→B→T) geçer ve herkesin süresi 65 dakikadan 80 dakikaya çıkar. Hesabın bütün adımları 8.3.1'de verilir; şimdilik bu sonucu açıklamak için gereken kavramlar kurulur.

8.1.2Ağ tasarımı ve yönlendirme

Bir ağla ilgili kararlar iki düzeyde verilir. Birinci düzey ağın kendisini kurmaktır: hangi noktalar birbirine bağlanacak, her bağlantı ne kadar trafik taşıyabilecek, kurulum ne kadara mal olacak? İkinci düzey kurulmuş ağı kullanmaktır: bir noktadan ötekine giden trafik hangi yollardan akacak?

Şekil 8.2'de beş düğümlü küçük bir ağ görülür. Tasarımcı “a ile b arasında bir bağlantı olsun mu, olacaksa ne kadar geniş olsun?” diye sorar. Yönlendirme ise ağ kurulduktan sonra “s'den t'ye giden bir paket ya da araç hangi kenarlardan geçsin?” sorusudur. İki problem birbirine bağlıdır: iyi bir tasarım, kullanıcıların o ağda nasıl yol seçeceğini hesaba katmalıdır. Braess paradoksu tam olarak bu bağın ihmal edilmesinin bedelidir.

Algoritmik oyun kuramı bu problemlere yeni bir bakış ekler. Klasik ağ mühendisliğinde trafik “yönlendirilen” bir şeydir: bir merkez, paketlerin ya da araçların hangi yoldan gideceğine karar verir. Oysa gerçek ağların çoğunda kararları kullanıcıların kendisi verir. Şehirde her sürücü kendi rotasını seçer; internette her ağ işletmecisi kendi çıkarına göre trafik yönlendirir. Algoritmik oyun kuramı, kullanıcıların kendi maliyetlerini azaltmaya çalıştığı bu trafik ve iletişim ağlarını inceler. Temel uygulama alanları şehir trafiği, internet omurgaları ve enerji şebekeleridir.

8.1.3Temel kavramlar: düğüm, bağlantı, kapasite, maliyet

Matematikte bir ağ, çizge (graph) ile modellenir. Çizge, noktalardan ve bu noktaları birleştiren çizgilerden oluşur. Bu bölümde dört temel kavram sürekli kullanılır.

• Düğüm (node): ağdaki bir nokta. Şehir trafiğinde bir kavşak, internette bir yönlendirici (router), elektrik şebekesinde bir trafo merkezidir.
• Bağlantı (link) ya da kenar (edge): iki düğümü birleştiren hat. Bir yol, bir fiber optik hat ya da bir iletim hattıdır. Yönlü bir kenar (s→a) yalnız bir yönde kullanılabilir; tek yönlü bir cadde gibi.
• Kapasite (capacity) ve bant genişliği (bandwidth): bir bağlantının birim zamanda taşıyabildiği akış. Bir yolun saatte geçirebildiği araç sayısı ya da bir hattın saniyede taşıyabildiği bit sayısıdır. Kapasite aşılınca gecikme hızla artar.
• Maliyet: iki türlüdür. Kurulum maliyeti ağı kurarken ödenir ve tasarım kararlarını etkiler. Kullanım maliyeti ise ağı kullanırken ödenir: gecikme, harcanan enerji ya da ücret. Kullanım maliyeti yönlendirme kararlarını etkiler.

Düğümlerin birbirine nasıl bağlandığına ağın topolojisi denir. Şekil 8.3 dört temel topolojiyi gösterir.

Her topolojinin artısı ve eksisi vardır. Yıldız az bağlantı ister (n düğüm için n − 1 bağlantı) ve her düğüm merkeze bir adım uzaklıktadır; ama merkez çökerse bütün ağ çöker. Halka da az bağlantı ister (n bağlantı) ve tek bir kopukluğa dayanır, ama uzak düğümler arasında çok adım vardır. Tam örgü (mesh) her çift arasında doğrudan bağlantı kurar; uzaklıklar en kısadır ama bağlantı sayısı n(n − 1)/2'dir ve hızla büyür. Ağaç, katmanlı bir düzen kurar ve döngü içermez. Veri merkezlerinde ağaç ya da katmanlı topolojiler yaygındır; şehir trafiğinde ise yol ağı örgüye yakındır, çünkü iki nokta arasında çoğu zaman birden çok seçenek vardır.

Bu topolojiler 8.5'te yeniden karşımıza çıkar. Orada sorulan soru, bağlantıları kendileri satın alan oyuncuların sonunda hangi topolojide karar kılacağıdır. Bağlantı ucuzsa tam örgüye, pahalıysa yıldıza yakın ağlar ortaya çıkar.

8.1.4Klasik yönlendirme algoritmaları

Kenarların her birine bir sayı (ağırlık) atanmış bir ağda en kısa yolu bulmak, bilgisayar mühendisliğinin temel problemlerinden biridir. Ağırlık bir uzaklık, bir süre ya da bir maliyet olabilir. Tablo 8.1 yönlendirmede kullanılan dört klasik yöntemi özetler.

Tablodaki V düğüm sayısını, E kenar sayısını gösterir. Dijkstra algoritması kaynaktan başlar ve her adımda “kesin uzaklığı henüz belirlenmemiş düğümler içinde en yakın olanı” kesinleştirir. Bunun doğru çalışması için ağırlıkların negatif olmaması gerekir: bir kez kesinleşmiş bir uzaklık, sonradan negatif bir kenar yüzünden kısalamaz. İnternetteki OSPF (Open Shortest Path First) protokolünde her yönlendirici ağın tamamının haritasını tutar ve bu haritada Dijkstra çalıştırır.

Bellman–Ford algoritması farklı çalışır: her düğüm, komşularının bildirdiği uzaklıklara bakarak kendi tahminini günceller ve bu işlem tahminler değişmeyene kadar sürer. En çok V − 1 tur yeter ve her tur bütün kenarları dolaşır; süre bu yüzden O(V · E)'dir. Dijkstra'dan yavaştır ama negatif ağırlıkları kabul eder. Asıl önemli özelliği dağıtık çalışabilmesidir: hiçbir düğümün ağın tamamını bilmesi gerekmez, herkes yalnız komşusundan öğrenir. İnternetteki RIP protokolü bu “komşudan öğrenme” fikrine dayanan bir uzaklık vektörü protokolüdür.

Dinamik yönlendirme, bir bağlantı koptuğunda ya da maliyeti değiştiğinde yolları yeniden hesaplar. Yük dengeleme ise trafiği tek bir yola yığmak yerine birden çok yola ya da sunucuya dağıtır. ECMP (equal-cost multi-path, eşit maliyetli çok yol) bunun basit bir biçimidir: uzunluğu eşit olan birden çok en kısa yol varsa trafik bunlar arasında bölünür.

Bu algoritmaların hepsi ortak bir varsayım yapar: kenar ağırlıkları sabittir. Dijkstra, a→c kenarının 3 dakika sürdüğünü kabul eder ve bu sayıyı kimin o kenarı kullandığından bağımsız sayar. Gerçekte ise gecikme, o yolu kaç kişinin seçtiğine bağlıdır. Yukarıdaki örnekte bütün sürücülere s→a→c→t önerilirse a→c kenarı tıkanır ve artık 3 dakika sürmez. Stratejik kullanıcılar önerilen rotadan sapabildiğinde ağın dengesi ile toplam gecikmeyi en küçük yapan dağılım birbirinden ayrılır. Yönlendirmeyi bir oyuna dönüştüren de budur: her kullanıcının “en kısa yol”u, ötekilerin seçimine bağlıdır.

8.1.5Gecikme yüke bağlıdır

Yüke bağlı gecikmeyi modellemek için her kenara bir sayı yerine bir fonksiyon atanır.

“Azalmayan” koşulu sağduyuya dayanır: bir yola daha çok araç girdikçe yol daha hızlı olmaz. Bu bölümde dört tür gecikme fonksiyonu kullanılır.

• Sabit: ℓ(x) = b. Trafikten etkilenmeyen geniş bir otoyol. Braess örneğindeki 45 dakikalık geniş yollar böyledir.
• Doğrusal: ℓ(x) = a · x + b. b boş yoldaki süredir, a ise her ek aracın süreyi ne kadar uzattığıdır. İki yollu ağ ve Braess örnekleri bu türü kullanır; örneğin ℓ(x) = 5 + x/100 boş yolda 5 dakika sürer ve her 100 araç süreyi bir dakika uzatır.
• BPR (ABD Karayolları Bürosu, Bureau of Public Roads): ℓ(x) = t₀ (1 + 0,15 (x/c)⁴). Burada t₀ boş yoldaki süre, c yolun kapasitesidir. Trafik planlamasında standart olarak kullanılır.
• Kuyruk gecikmesi: ℓ(x) = 1/(c − x), yalnızca 0 ≤ x < c için. Bu, tek sunuculu bir kuyruğun (M/M/1 kuyruğu) ortalama gecikmesidir. c saniyede işlenebilen, x saniyede gelen paket sayısıdır.

Şekil 8.4 fonksiyonların biçimini karşılaştırır. BPR eğrisinin davranışı günlük deneyime uyar: yol kapasitesinin yarısıyla doluyken trafik neredeyse akıcıdır, kapasiteye yaklaşınca yavaşlama belirginleşir, kapasite aşılınca yolculuk süresi hızla uzar. Dördüncü kuvvet ((x/c)⁴) bu “önce yavaş, sonra hızlı” artışı üretir.

Kuyruk gecikmesinin bir özelliği ayrıca vurgulanmalıdır: x, c'ye yaklaştıkça 1/(c − x) sınırsız büyür. x ≥ c olduğunda ise formül anlamını yitirir; saniyede işlenebilenden çok paket geldiği için kuyruk durmadan uzar ve kararlı bir ortalama gecikme yoktur. Bu yüzden formül yalnız x < c için geçerlidir.

8.2Bencil yönlendirme

Bu kesimde yüke bağlı gecikmeleri olan bir ağda kullanıcıların nasıl yol seçtiği incelenir. İki soru sorulur: kullanıcılar kendi başlarına seçim yapınca trafik nasıl dağılır, ve bu dağılım toplam gecikme açısından ne kadar iyidir? İlk sorunun cevabı Wardrop dengesi, ikincisinin ölçütü sistem optimumudur.

8.2.1Model: akış, yol gecikmesi, toplam gecikme

Bölünebilir akış varsayımı bir yaklaşımdır. Şehirde binlerce sürücü vardır ve tek bir sürücünün bir yola girmesi o yolun süresini fark edilmeyecek kadar az değiştirir. Bu yüzden trafiği tek tek araçlar yerine akan bir sıvı gibi düşünmek hesapları kolaylaştırır. Sürücü sayısı az ve her birinin etkisi belirginse (örneğin dört sürücü) model atomik olur; bu durum 8.4'te ele alınır.

Modelin bileşenleri şunlardır:

• r birim trafik, kaynak s'den hedef t'ye gider. Örneğin r = 3.000 araç.
• f_P: P yolundaki akış, yani o yolu seçen trafik miktarı. Bütün yollardaki akışların toplamı r'dir.
• f_e: e kenarındaki toplam akış. Bir kenar birden çok yolun parçası olabilir; o kenarı içeren bütün yolların akışları toplanır: f_e = Σ_{P ∋ e} f_P.

Bu bileşenlerle iki ölçü tanımlanır. Bir yolun gecikmesi, üzerindeki kenarların gecikmelerinin toplamıdır:

ℓ_P(f) = Σ_{e ∈ P} ℓ_e(f_e)

Ağın toplam gecikmesi ise her kenarda akış ile gecikmenin çarpımının toplamıdır:

C(f) = Σ_e f_e · ℓ_e(f_e)

Toplam gecikmenin neden böyle yazıldığı bir örnekle görülür. Bir kenarda 2.000 araç varsa ve her biri o kenarda 25 dakika geçiriyorsa, o kenarda harcanan toplam zaman 2.000 × 25 = 50.000 araç·dakikadır. “Araç·dakika” birimi, her aracın harcadığı dakikaların toplamını ifade eder. Bütün kenarlar için bu çarpımlar toplanınca ağda harcanan toplam zaman bulunur.

Aynı toplam yollar üzerinden de hesaplanabilir: her yolun akışı o yolun gecikmesiyle çarpılıp toplanır, C(f) = Σ_P f_P · ℓ_P(f). İki yazım aynı sonucu verir. Bunun nedeni şudur: f_P · ℓ_P çarpımında ℓ_P kenar gecikmelerinin toplamı olduğundan, her kenarın gecikmesi o kenardan geçen bütün yolların akışlarıyla çarpılmış olur; bu akışların toplamı da f_e'dir. Toplam gecikmeyi r'ye bölmek ortalama yolculuk süresini verir.

Bireysel rota seçimleri, toplam gecikmeyi en aza indiren dağılımdan uzaklaşabilir. Braess paradoksu bunun en uç biçimidir: yeni bir bağlantı eklemek denge gecikmesini artırabilir. Önce bu uzaklaşmanın nasıl ölçüleceği tanımlanmalıdır.

8.2.2Wardrop ilkeleri

İngiliz ulaştırma mühendisi John Glen Wardrop, 1952'de trafik akışının iki farklı biçimde dağılabileceğini ileri sürdü (Wardrop, 1952). Bu iki ilke bugün de trafik planlamasının temelidir.

Birinci ilke üç eşdeğer biçimde okunabilir:

• Kullanılan bütün yolların gecikmesi eşittir ve en düşüktür.
• Kullanılmayan bir yol daha yavaştır (ya da kullanılanlarla eşit hızdadır).
• Tek bir kullanıcı yol değiştirerek yolculuk süresini azaltamaz.

Neden kullanılan yolların gecikmeleri eşit olmalıdır? Diyelim ki iki yol da kullanılıyor ama Yol 1 daha hızlı. O zaman Yol 2'deki bir sürücü Yol 1'e geçerek kazanır. Bu bir dengeyle bağdaşmaz; denge, kimsenin tek başına sapmak istemediği durumdur. Üçüncü okuma, Wardrop dengesinin aslında Nash dengesi fikrinin bölünebilir trafiğe uyarlanmış hâli olduğunu gösterir: her kullanıcı ötekilerin seçimine karşı en iyi tepkiyi vermektedir.

İkinci ilke ise bir planlayıcının bakış açısıdır. Bütün trafiği tek elden yönetebilen bir merkez, ortalama (toplam) gecikmeyi en küçük yapan dağılımı seçer. Bu dağılımda bazı kullanıcılar daha yavaş bir yola “feda edilebilir”: toplam açısından onların daha yavaş yolda olması, ötekilerin hızlanmasıyla telafi edilir. Sistem optimumunu uygulamak bu yüzden zordur; feda edilen kullanıcıların uymaya istekli olması gerekir.

Kısaca denge, kullanıcıların bireysel tercihlerini açıklar; ama sistem optimumuyla aynı olmak zorunda değildir. Doğrusal gecikmelerde (daha genel olarak sürekli ve azalmayan gecikmelerde) bir Wardrop dengesi her zaman vardır. Üstelik denge birden çok olsa bile her kenarın denge gecikmesi aynıdır; hangi denge bulunursa bulunsun kullanıcıların yaşadığı süreler değişmez. Bu sonuç 8.2.5'te Beckmann potansiyeliyle açıklanır.

8.2.3İki yollu ağda Wardrop dengesi

Tanımı somutlaştırmak için bütün bölüm boyunca kullanılacak iki yollu ağ kurulur. 3.000 araç A'dan B'ye gidiyor. Yol 1 kısa ama dardır: boşken 5 dakika sürer, ama her 100 araç süreyi bir dakika uzatır. Yol 2 uzun ama geniştir: boşken 20 dakika sürer, her 200 araç süreyi bir dakika uzatır.

ℓ₁(x₁) = 5 + x₁/100, ℓ₂(x₂) = 20 + x₂/200, x₁ + x₂ = 3.000

Her yol tek bir kenardan oluştuğu için burada yol gecikmesi ile kenar gecikmesi aynıdır. Dengeyi bulmak için önce iki “deneme” yapılır; bu denemeler dengenin neden belirli bir noktada olması gerektiğini gösterir.

Şekil 8.5'teki grafik her denemeyi tek bakışta değerlendirmeyi sağlar. Yatay eksende Yol 1'deki araç sayısı x₁ vardır; Yol 2'deki araç sayısı 3.000 − x₁'dir. Mavi doğru x₁ arttıkça yükselir (Yol 1 kalabalıklaşır), kırmızı doğru x₁ arttıkça alçalır (Yol 2 boşalır). İki doğrunun kesiştiği nokta, iki yolun eşit sürdüğü noktadır.

Şekil 8.6 dengeyi gösterir. Denge noktasının solunda mavi doğru kırmızının altındadır: Yol 1 daha hızlıdır ve araçlar Yol 1'e kayar, yani nokta sağa gider. Sağında mavi doğru üstte kalır: Yol 1 daha yavaştır ve araçlar Yol 2'ye kayar, nokta sola gider. Her iki yönden gelen bu “itiş”, akışı kesişme noktasına taşır. Denge bu yüzden kararlıdır.

Eşitleme yöntemi yalnız iki yol da kullanılıyorsa geçerlidir. Bir yol hiç kullanılmadığında bile daha hızlı olabilir mi? Örneğin Yol 1 öyle geniş olsaydı ki 3.000 araçla bile Yol 2'nin boş hâlinden hızlı kalsaydı (ℓ₁(3.000) ≤ ℓ₂(0)), denge herkesin Yol 1'de olduğu durum olurdu. O zaman kullanılan tek yol Yol 1'dir ve kullanılmayan Yol 2 daha yavaştır; tanımın ikinci okuması tam bu durumu kapsar. Bu yüzden eşitleme denkleminin çözümü 0 ile r arasında çıkmazsa denge bir uçtadır.

8.2.4Denge ile sistem optimumu aynı değil

Dengede herkes 25 dakika yolculuk eder ve toplam 75.000 araç·dakikadır. Bu, toplam gecikmenin olabilecek en küçük değeri midir? Bunu anlamak için toplam gecikme x₁'in bir fonksiyonu olarak yazılır:

C(x₁) = x₁ · ℓ₁(x₁) + x₂ · ℓ₂(x₂), x₂ = 3.000 − x₁

Bu fonksiyonun birkaç değeri Tablo 8.3'te verilmiştir. Tablo, eğrinin en alt noktasının dengede (2.000) değil, 1.500'de olduğunu gösterir.

Optimumu tablo taramadan, kesin olarak bulmak için marjinal maliyet (marginal cost) kavramı kullanılır. Bir yolun marjinal maliyeti, o yola bir araç daha eklemenin toplam gecikmeye kattığı miktardır.

Bu miktarın neden yolun kendi gecikmesinden büyük olduğu şöyle görülür. Yol 1'de x₁ araç varken bir araç daha eklensin. Yeni araç kendisi ℓ₁ kadar gecikme yaşar. Ama ayrıca yolu biraz daha kalabalıklaştırır: gecikme her araç için ℓ₁′ = 1/100 dakika artar ve bu artışı yoldaki öteki x₁ aracın hepsi yaşar. Toplamda x₁ · ℓ₁′ kadar ek gecikme doğar. Marjinal maliyet bu iki parçanın toplamıdır:

(x · ℓ(x))′ = ℓ(x) + x · ℓ′(x)

Bu formül, çarpımın türevi kuralının ((uv)′ = u′v + uv′) bu duruma uygulanmasıdır. Türev, burada “fonksiyonun girdisi bir birim artınca çıktısının ne kadar arttığı” olarak okunabilir. Doğrusal gecikmeler için hesap kolaydır:

• Yol 1: x₁ · ℓ₁ = 5x₁ + x₁²/100. 5x₁'in türevi 5'tir; x₁²/100'ün türevi 2x₁/100 = x₁/50'dir. Marjinal maliyet 5 + x₁/50.
• Yol 2: x₂ · ℓ₂ = 20x₂ + x₂²/200. Marjinal maliyet 20 + x₂/100.

Sistem optimumunda iki yolun marjinal maliyetleri eşit olmalıdır. Nedeni, dengedeki akıl yürütmenin aynısıdır ama bu kez planlayıcının gözünden: Yol 1'in marjinal maliyeti daha yüksek olsaydı, bir aracı Yol 1'den Yol 2'ye almak toplam gecikmeyi azaltırdı. Planlayıcı böyle bir iyileştirme kalmayana kadar araç taşır; durduğu yerde marjinal maliyetler eşittir.

Şekil 8.7 toplam gecikme eğrisini gösterir. Eğri bir çanak biçimindedir: uçlarda (bütün trafik tek yolda) toplam gecikme çok büyüktür, ortada bir yerde en küçük olur. Denge noktası çanağın dibinin sağında kalır.

Tablo 8.4 iki dağılımı karşılaştırır. Dengede toplam gecikme optimumdan 3.750 araç·dakika fazladır; oran olarak 75.000 / 71.250 ≈ 1,053, yani yaklaşık yüzde 5 fazla. Bencil davranışın bu “bedeli”, kuramda anarşinin bedeli (price of anarchy) adıyla incelenir.

Optimum neden kendiliğinden oluşmaz? Optimumda Yol 1'deki sürücü 20, Yol 2'deki sürücü 27,5 dakika yaşar. Yol 2'deki her sürücü Yol 1'e geçerek 7,5 dakika kazanacağını görür ve geçer. Bu yüzden optimum bir denge değildir: kendi hâline bırakılan trafik optimumda kalmaz, dengeye kayar. Optimumu korumak için Yol 2'deki 1.500 sürücünün “feda edilmeyi” kabul etmesi gerekir.

Dengedeki verimsizliğin kaynağı da marjinal maliyetle görülür. Dengede (x₁ = 2.000) Yol 1'in marjinal maliyeti 5 + 2.000/50 = 45, Yol 2'ninki 20 + 1.000/100 = 30'dur. Bir aracı Yol 1'den Yol 2'ye almak toplam gecikmeyi yaklaşık 45 − 30 = 15 araç·dakika azaltır. Ama o aracın sürücüsü bunu görmez: o yalnız kendi süresine bakar ve iki yolda da 25 dakika yaşadığı için yerinden memnundur.

8.2.5İki ayrı en aza indirme: Beckmann potansiyeli

Sistem optimumu, bir fonksiyonun (C) en küçük noktasıdır. Wardrop dengesi de bir fonksiyonun en küçük noktası olarak yazılabilir mi? Martin Beckmann, C. B. McGuire ve C. B. Winsten 1956'da bunun mümkün olduğunu gösterdi (Beckmann, McGuire, Winsten, 1956).

Formüldeki integral işareti matematik temeli zayıf okuru korkutmamalıdır. ∫₀^f_e ℓ_e(t) dt, gecikme eğrisinin altında 0 ile f_e arasında kalan alandır. Bunu bir toplam gibi düşünmek kolaydır: trafik kenara azar azar girsin. İlk gelen sürücü boş yolu, yani ℓ_e(0)'ı görür; sonrakiler biraz daha kalabalık yolu görür; en son gelen ℓ_e(f_e)'yi görür. Alan, her sürücünün girdiği anda gördüğü gecikmelerin toplamıdır. Toplam gecikme f_e · ℓ_e(f_e) ise herkese en son durumdaki gecikmeyi yükler; bu yüzden potansiyel genellikle toplam gecikmeden küçüktür.

Doğrusal bir gecikme ℓ(t) = b + a · t için alan bir yamuktur ve hesabı kolaydır: ∫₀^x (b + a t) dt = b x + a x²/2. İki yollu ağda:

Φ(x₁) = 5x₁ + x₁²/200 + 20x₂ + x₂²/400

Bu fonksiyonun x₁'e göre türevi alınır. x₂ = 3.000 − x₁ olduğundan x₁ bir birim artınca x₂ bir birim azalır. Yol 1 parçasının türevi 5 + x₁/100 = ℓ₁'dir; Yol 2 parçası ise ℓ₂ kadar azalır. Sonuç:

Φ′(x₁) = ℓ₁(x₁) − ℓ₂(x₂)

Türevin sıfır olduğu nokta, ℓ₁ = ℓ₂ olan noktadır; bu da tam Wardrop koşuludur. Potansiyelin türevi, “son gelen sürücünün” gördüğü gecikmedir. Bencil sürücü de tam olarak buna bakar: yola girerken o anki gecikmeyi görür.

Teoremin iki önemli sonucu vardır. Birincisi varlık: olası akışlar kümesi sınırlıdır ve sürekli bir fonksiyon böyle bir kümede en küçük değerini alır; demek ki Wardrop dengesi her zaman vardır. İkincisi tekillik: gecikmeler azalmayan olduğu için Φ “çanak biçimli” (dışbükey) bir fonksiyondur. Çanak biçimli bir fonksiyonun birden çok en küçük noktası olsa bile bu noktalarda kenar gecikmeleri aynıdır. 8.2.2'deki “hangi denge bulunursa bulunsun kenar gecikmeleri aynıdır” cümlesinin dayanağı budur.

Şekil 8.8 iki eğriyi yan yana koyar. Tablo 8.3'teki sayılar da aynı şeyi söyler: Φ en küçük değerini 2.000'de (52.500), C en küçük değerini 1.500'de (71.250) alır. Denge potansiyelin dibidir, optimum toplam gecikmenin dibidir. İki dip farklı yerdedir, çünkü iki fonksiyonun türevleri farklıdır:

• Φ'nin bir kenara göre türevi ℓ_e'dir: son gelen sürücünün gördüğü gecikme.
• C'nin bir kenara göre türevi ℓ_e + f_e · ℓ_e′'dir: marjinal maliyet.

Fark tek bir terimden gelir: f_e · ℓ_e′. Bu terim, bir sürücünün kendi varlığıyla ötekilere yüklediği ek gecikmedir. Sürücü bu dışsallığı (externality) hesaba katmaz. Dengede Yol 1'de bu terim 2.000 × 1/100 = 20 araç·dakikadır: Yol 1'e giren her yeni sürücü, oradaki 2.000 kişinin her birini 1/100 dakika yavaşlatır. Dışsallık kavramı 8.5.1'de ayrıca incelenir.

8.2.6Kod izleme: denge_bul()

İki yollu ağda dengeyi denklem çözerek bulmak kolaydır. Gecikmeler doğrusal değilse (örneğin BPR) denklemi elle çözmek zorlaşır. O zaman sayısal bir yöntem kullanılır. Aşağıdaki fonksiyon dengeyi ikiye bölme (bisection) yöntemiyle arar. Girdi olarak iki gecikme fonksiyonu l1, l2, toplam trafik r ve istenen hassasiyet eps alınır.

def denge_bul(l1, l2, r, eps=50):
  lo, hi = 0, r
  while hi - lo > eps:
    x = (lo + hi) / 2
    if l1(x) < l2(r - x):
      lo = x      # Yol 1 hâlâ hızlı: artır
    else:
      hi = x      # Yol 1 yavaş: azalt
  return (lo + hi) / 2

Kod şöyle çalışır:

• lo ve hi, dengenin içinde bulunduğu bilinen aralığın uçlarıdır. Başta aralık [0, r]'dir: Yol 1'deki araç sayısı 0 ile r arasında olmak zorundadır.
• Döngü, aralığın genişliği eps'ten büyük olduğu sürece döner.
• Her turda aralığın orta noktası x denenir. Yol 1'de x, Yol 2'de r - x araç vardır.
• l1(x) < l2(r - x) ise Yol 1 hâlâ daha hızlıdır. Araçlar Yol 1'e geçmek ister; denge daha sağdadır. Aralığın sol ucu x'e taşınır.
• Aksi hâlde Yol 1 fazla kalabalıktır; denge daha soldadır. Aralığın sağ ucu x'e taşınır.
• Döngü bitince aralığın ortası döndürülür.

Yöntemin doğru çalışmasının nedeni şudur: g(x) = ℓ₁(x) − ℓ₂(r − x) farkı x ile artar, çünkü x artınca Yol 1 yavaşlar, Yol 2 hızlanır. Artan bir fonksiyonun tek bir sıfırı vardır ve o sıfır dengedir. x = 0'da Yol 1 hızlıdır (g < 0), x = r'de yavaştır (g > 0); sıfır bu ikisinin arasındadır. Her tur aralığı yarıya indirdiği ve sıfırı hep aralığın içinde tuttuğu için arama sıfıra yaklaşır.

Altıncı turdan sonra (Şekil 8.9) genişlik 46,88'dir ve 46,88 ≤ 50 olduğundan döngü durur. Fonksiyon (1.968,75 + 2.015,63)/2 ≈ 1.992,19 döndürür. Gerçek denge 2.000'dir; hata yaklaşık 8 araçtır ve eps'in yarısından küçüktür.

Her tur aralığı yarıya indirdiği için k tur sonra aralığın genişliği r/2^k'dir ve hata en çok bu kadardır. 3.000 araçla 6 turda genişlik 3.000/64 ≈ 46,9'a iner. Daha hassas bir sonuç için her ek tur hatayı yarıya böler; 10 tur daha hatayı yaklaşık bin kat küçültür. Yöntem bu yüzden çok hızlıdır.

Bu yöntem yalnız iki yollu ağlarda çalışır, çünkü orada tek bir bilinmeyen (x₁) vardır. Çok yollu genel ağlarda denge, Beckmann potansiyelini en küçük yapan akıştır ve dışbükey optimizasyon yöntemleriyle bulunur. Trafik planlamasında en yaygın kullanılan yöntem Frank–Wolfe algoritmasıdır: her adımda mevcut gecikmelerle en kısa yolları (örneğin Dijkstra ile) bulur ve akışı bu yollara doğru biraz kaydırır.

8.2.7Bencil yönlendirmede sık hatalar

8.3Braess paradoksu

Alman matematikçi Dietrich Braess, 1968'de trafik planlamasıyla ilgili kısa bir makale yayımladı (Braess, 1968). Makalenin gösterdiği şey basit ama rahatsız ediciydi: bir ağa yeni bir yol eklemek, bencil rota seçimi yüzünden herkesin yolculuğunu uzatabilir. Bu kesimde paradoks önce sayılarla adım adım kurulur, sonra nedeni, gerçek hayattaki örnekleri ve tasarım açısından sonuçları incelenir.

8.3.1Braess paradoksu adım adım

Kurulum 8.1.1'deki oyunun aynısıdır, yalnız sürücü sayısı somut olarak 4.000'dir. 4.000 araç s'den t'ye gider. s→A ve B→t dar yollardır: x araç varken x/100 dakika sürerler. A→t ve s→B geniş otoyollardır: trafikten bağımsız olarak 45 dakika sürerler. Oyundaki 40 · x/N formülünde N = 4.000 yazılınca x/100 elde edilir; iki anlatım aynıdır.

Şekil 8.10, Şekil 8.11 ve Şekil 8.12 bu süreci üç anda gösterir. Tablo 8.6 aynı süreci sayılarla özetler.

Tablonun her satırında zikzak eski rotalardan daha hızlıdır (fark 25 dakikadan 5 dakikaya iner). Ama z büyüdükçe iki süre de artar: her geçen sürücü, hem zikzaktakileri hem eski rotalardakileri yavaşlatır. Sürücüler her adımda “daha hızlı” rotaya geçer, ama hep birlikte geçtikleri için sonunda herkes başlangıçtakinden daha yavaştır. Kapasite artışı ile bencil seçim birleşince daha kötü bir dengeye varılmıştır.

8.3.2Neden herkes zikzağa geçer?

4.000 araçlı örnekte herkesin zikzağa geçmesi tesadüf değildir. Zikzak rota, kalan trafik nasıl dağılırsa dağılsın eski rotalardan hızlıdır. Bunu görmek için zikzaktaki araç sayısı z ile gösterilir ve kalan 4.000 − z araç iki eski rotaya eşit bölünür.

• Her eski rotada (4.000 − z)/2 = 2.000 − z/2 araç vardır.
• s→A'daki akış, üst rotadakiler ile zikzaktakilerin toplamıdır: 2.000 − z/2 + z = 2.000 + z/2. Süre 20 + z/200 dakika. B→t için de aynısı geçerlidir.
• Eski rota: bir dar yol ve bir geniş yol, 20 + z/200 + 45 = 65 + z/200 dakika.
• Zikzak: iki dar yol ve kestirme, 2 · (20 + z/200) + 0 = 40 + z/100 dakika.

Şekil 8.13 iki doğruyu gösterir. Zikzak, eski rotalardan ancak 40 + z/100 ≥ 65 + z/200 olduğunda yavaş olurdu; bu da z/200 ≥ 25, yani z ≥ 5.000 demektir. Oysa yalnız 4.000 araç vardır. Demek ki zikzak her durumda daha hızlıdır.

Aynı sonuca daha kısa bir yoldan da varılır. Zikzağın ikinci yarısı B→t'dir; bu yol en kalabalık hâlinde bile en çok 4.000/100 = 40 dakika sürer. Eski alt rotanın ilk yarısı s→B ise her zaman 45 dakikadır. Yani s'den B'ye geçmek için A üzerinden gitmek (s→A en çok 40 dakika) her zaman doğrudan otoyoldan (45 dakika) hızlıdır. Simetrik olarak A'dan t'ye B üzerinden gitmek de her zaman hızlıdır. Zikzak, her sürücü için baskın bir seçimdir: ötekiler ne yaparsa yapsın daha iyidir.

Mahkûmun İkilemi ile benzerlik açıktır. O oyunda ihanet her oyuncu için baskın stratejidir, ama herkes ihanet edince herkes kötü duruma düşer. Burada da zikzak herkes için baskındır, ama her geçen sürücü dar yollara yük bindirir. z = 4.000'de herkes 80 dakika yaşar; kestirme hiç olmasaydı herkes 65 dakika yaşayacaktı.

8.3.3Kestirmeli ağın sistem optimumu

Kestirme yolun kendisi kötü değildir. Kötü olan, onun bencil biçimde kullanılmasıdır. Bunu görmek için kestirmeli ağın sistem optimumu hesaplanır: bir planlayıcı trafiği nasıl dağıtırsa ortalama süre en küçük olur?

Optimumda zikzağa küçük bir pay verilir (500 araç) ve ortalama süre 65'ten 64,7'ye biraz düşer. Kestirme, doğru kullanılırsa küçük de olsa bir iyileşme sağlar. Ama bu dağılım bir denge değildir: eski rotalardaki sürücüler 67,5 dakika yaşarken zikzakta 45 dakika yaşanmaktadır ve hepsi zikzağa geçmek ister. Tablo 8.7 dört durumu karşılaştırır.

Tablo, oyunun başındaki iki merak sorusunun cevabını verir. Kestirme açılınca yolculuklar kısalmaz, uzar (65 → 80). Herkes kendi en hızlı yolunu seçince ortalama süre en küçük olmaz (80 > 64,7). Kuramın cevabı iki soruya da “hayır”dır.

8.3.4Paradoksun dersi ve gerçek örnekler

Paradoksun mantığı şudur: yeni yol bireysel olarak çekici görünür, ancak kullanıcıların birlikte oluşturduğu trafik deseni daha kötü bir dengeye taşınır. Bunun tersi de doğrudur: bir yolu kapatmak bazen herkesi hızlandırabilir. Braess ağında A→B'yi kapatmak herkesin süresini 80'den 65 dakikaya indirir.

Paradoks yalnız kâğıt üzerinde kalmamıştır. Sıkça anılan birkaç örnek vardır:

• Stuttgart (1969). Şehir merkezine yapılan yeni yol yatırımından sonra trafik bozulmuş, bir cadde kapatılınca düzelmiştir (Knödel, 1969).
• New York (1990). Dünya Günü'nde 42. Cadde trafiğe kapatıldığında beklenen tıkanıklığın oluşmadığı bildirilmiştir (Kolata, 1990).
• Seul. Cheonggyecheon deresi üzerindeki yükseltilmiş otoyol 2000'lerin başında kaldırıldı ve bir kent parkına dönüştürüldü. Bundan sonra şehir trafiğinin beklenen ölçüde kötüleşmediği sıkça anılır.
• Mekanik ve elektrik ağları. Yaylardan ve dirençlerden kurulan ağlarda da benzer bir paradoks gösterilmiştir: bir yayı kesmek asılı bir ağırlığı yukarı kaldırabilir (Cohen ve Horowitz, 1991).
• Laboratuvar deneyleri. Denekler bilgisayar ortamında rota seçtiğinde, kestirme eklenince zamanla paradoksun öngördüğü daha yavaş dengeye yöneldiler (Rapoport vd., 2009).

Bu örnekler dikkatle yorumlanmalıdır. Gerçek ağlar çok daha karmaşıktır; bir cadde kapatılınca bazı sürücüler toplu taşımaya geçer, bazıları yolculuk saatini değiştirir. Bu yüzden örnekler paradoksun kesin kanıtı değil, olası olduğunun göstergesidir. Ama ders açıktır: yol yapmak ya da kapatmak, yalnız kapasiteye göre değil, sürücülerin varacağı dengeye göre değerlendirilmelidir. Paradoksun etkisini azaltmanın yolları da vardır: ücretlendirme, erişim kısıtı ya da merkezi yönlendirme. Bunlar 8.6'da ele alınır.

8.3.5Kod izleme: en_iyi_alt_ag()

Braess paradoksu, ağ tasarımcısına yeni bir soru sordurur: verilen ağdan hangi kenarlar kapatılırsa denge süresi en çok düşer? Aşağıdaki fonksiyon bu sorunun basit bir sürümünü çözer: tek bir kenar kapatmayı dener.

def en_iyi_alt_ag(ag, r):
  eniyi, sil = denge_suresi(ag, r), None
  for e in ag:
    alt = [k for k in ag if k != e]
    d = denge_suresi(alt, r)   # yol yoksa inf
    if d < eniyi:
      eniyi, sil = d, e
  return sil, eniyi

Fonksiyon, denge_suresi(ag, r) adlı yardımcı bir fonksiyonu kullanır. Bu fonksiyon, verilen alt ağdaki Wardrop dengesinde kullanılan yolların ortak süresini döndürür. Betikte bu süre Beckmann potansiyeli en aza indirilerek hesaplanmıştır (8.2.5). s'den t'ye hiç yol kalmazsa sonsuz (inf) döner. Kod satır satır şöyle çalışır:

• eniyi, şimdiye kadar bulunan en küçük denge süresidir; başta hiçbir şey silinmemiş ağın süresidir. sil hangi kenarın silindiğini tutar; başta None (hiçbiri).
• Döngü ağdaki her e kenarını sırayla dener.
• alt, e dışındaki bütün kenarlardan oluşan alt ağdır.
• d, bu alt ağın denge süresidir.
• d şimdiye kadarki en iyiden kesin küçükse aday güncellenir.
• Sonunda silinecek kenar ve yeni denge süresi döndürülür.

Tablonun iki satırı ayrıca açıklanmalıdır. A→t kapatılınca iki rota kalır: zikzak (s→A→B→t) ve alt (s→B→t). İkisi de B→t'yi kullanır; bu yüzden B→t'de 4.000 araç vardır ve 40 dakika sürer. Zikzağın ilk kısmı s→A en çok 40 dakika, alt rotanın ilk kısmı s→B ise 45 dakikadır; zikzak yine baskındır. Herkes zikzağa geçer ve süre 40 + 0 + 40 = 80 dakika olur. s→B kapatılınca da simetrik durum ortaya çıkar. Bu iki satırda d eski en iyiye eşittir; kod kesin küçüklük aradığı için aday değişmez.

Şekil 8.14 sonucu gösterir: A→B kapatılmalıdır ve denge süresi 80'den 65 dakikaya iner. Kodun bir sınırlılığı vardır: yalnız tek kenar silmeyi dener. Genel durumda birden çok kenarı birlikte silmek daha iyi olabilir. m kenarlı bir ağda bütün alt ağları denemek 2^m denge hesabı ister. 30 kenarlı bir ağda bu bir milyardan fazladır; gerçek şehir ağlarında binlerce kenar vardır. Tasarımcının “hangi kenarları açık tutayım?” sorusu, genel ağda bu yüzden zordur.

8.3.6Bencil kullanıcılar için ağ tasarımı

Bu soru biçimsel olarak şöyle yazılır: verilen ağın hangi alt ağı açık kalırsa Wardrop dengesindeki süre en küçük olur? Burada yeni yol yapmak yerine yol kapatmak da bir tasarım kararıdır. İki sonuç bu problemin zorluğunu ve sınırlarını çizer.

Zorluk. Tim Roughgarden 2006'da bu problemin hesaplama açısından zor olduğunu gösterdi (Roughgarden, 2006). Doğrusal gecikmelerde hiçbir kenarı kapatmamak bile en iyi seçimden en çok 4/3 kat kötüdür. Ama bundan daha iyisini verimli biçimde garanti etmek NP-zordur: verimli bir algoritmanın her ağda “hiçbir şeyi kapatma” seçeneğinden belirgin biçimde iyi bir alt ağ bulması beklenmez. Braess örneğinde oran tam bu sınırdadır: 80/65 ≈ 1,23, yani 4/3 ≈ 1,33'ün altında.

Topoloji. Igal Milchtaich 2006'da hangi ağlarda paradoksun hiç görülemeyeceğini belirledi (Milchtaich, 2006). Seri-paralel ağlarda (series-parallel network) Braess paradoksu, gecikmeler nasıl seçilirse seçilsin hiç görülmez. Seri-paralel ağ, kenarları ardışık (seri) ya da yan yana (paralel) bağlayarak kurulan ağdır. İki yollu örnek böyledir: iki kenar s ile t arasında paralel bağlanmıştır. Diğer ağlarda ise uygun gecikmelerle paradoks görülebilir.

Şekil 8.15 iki yapıyı karşılaştırır. Braess ağı, sağdaki Wheatstone yapısıdır (Wheatstone network); adını elektrik devrelerindeki Wheatstone köprüsünden alır. A→B köprüsü iki paralel rotayı “çaprazlar”. Seri ve paralel bağlama işlemleriyle böyle bir çapraz kurulamaz. Milchtaich'in sonucuna göre iki uçlu bir ağın paradokstan bağışık olması için gerekli ve yeterli koşul, Wheatstone yapısını içermemesidir; bu da ağın seri-paralel olmasıyla aynı şeydir. Döngülü ağlar ya da tam çizgeler genellikle Wheatstone yapısı içerir ve böyle bir güvence vermez.

8.3.7Braess paradoksunda sık hatalar

8.4Tıkanıklık oyunları

Bölünebilir trafik modeli binlerce küçük kullanıcı için uygundur. Ama bazı durumlarda oyuncu sayısı azdır ve her birinin etkisi belirgindir: birkaç büyük taşımacılık şirketi, birkaç veri merkezi ya da bir ağda paket gönderen birkaç uygulama. Bu kesimde oyuncuların sayılabildiği (atomik) modele geçilir. Bu modelde de bencil seçimlerin bir dengeye varacağını gösteren güçlü bir araç vardır: Rosenthal potansiyeli.

8.4.1Tıkanıklık oyunu: atomik ve bölünebilir

Tanımdaki önemli nokta, bir kaynağın maliyetinin kimin kullandığına değil, kaç kişinin kullandığına bağlı olmasıdır. Bir yolda Ali ile Ayşe ya da Can ile Deniz olması fark etmez; iki kişi varsa maliyet c_e(2)'dir. Oyuncular kendi gecikmelerini azaltmaya çalışırken toplam ağ maliyeti yükselebilir; Braess paradoksu atomik modelde de görülür (8.4.3).

Atomik model ile bölünebilir model aynı fikrin iki yüzüdür. Tablo 8.9 farkları özetler.

Atomik modelde bir oyuncu yol değiştirince yeni yolundaki her kenarın kullanıcı sayısı bir artar. Bu yüzden oyuncu, yeni yolun maliyetini hesaplarken kendisini de saymalıdır: şu an 2 kişinin kullandığı bir kenara geçen oyuncu c_e(2) değil c_e(3) öder. Bu küçük ayrıntı, atomik hesaplarda en sık yapılan hatanın kaynağıdır.

Robert Rosenthal 1973'te tıkanıklık oyunlarının çok önemli bir özelliğini gösterdi: sonlu her tıkanıklık oyununda bir potansiyel fonksiyonu vardır, bu yüzden saf Nash dengesi her zaman bulunur (Rosenthal, 1973). Bu dikkat çekici bir sonuçtur. Genel oyunlarda saf denge olmayabilir; Taş-Kağıt-Makas'ta yalnız karışık denge vardır. Tıkanıklık oyunlarında ise karışık stratejiye gerek kalmaz.

8.4.2Rosenthal potansiyel fonksiyonu

Her kenarda 1'den kullanıcı sayısı n_e'ye kadar maliyetler toplanır. Bu, toplam maliyet değildir. Toplam maliyette o kenardaki n_e kullanıcının her biri c_e(n_e) öder ve kenarın katkısı n_e · c_e(n_e) olur. Potansiyelde ise kullanıcılar kenara sırayla giriyormuş gibi düşünülür: birinci gelen c_e(1), ikinci gelen c_e(2), son gelen c_e(n_e) “öder”. Beckmann potansiyelindeki “eğrinin altındaki alan”ın atomik karşılığı budur: integral yerine toplam gelir.

Şekil 8.16 bu toplamı çubuklarla gösterir. Maliyeti kullanıcı sayısıyla artan s→A kenarında çubuklar merdiven gibi yükselir; maliyeti sabit A→t kenarında hepsi aynı boydadır.

Potansiyelin değerli olmasının nedeni, şu özdeşliktir.

İspatın bir sonucu daha vardır: Φ'nin bütün profiller içindeki en küçük değerini veren profil de bir saf Nash dengesidir. Çünkü orada herhangi bir oyuncunun maliyetini düşüren bir hamle Φ'yi daha da küçültürdü; bu, en küçük değerde olmakla çelişir.

8.4.3En iyi tepki dinamiği ve Φ adım adım

Teoremi işlerken görmek için Örnek 8.11'deki atomik Braess ağına en iyi tepki dinamiği uygulanır. Sürücüler 1, 2, 3, 4 sırasıyla hamle yapar. Sırası gelen sürücü, ötekiler sabitken maliyeti en küçük olan yolu seçer. Üç yol vardır: üst (s→A→t), alt (s→B→t) ve zik (s→A→B→t). Eşitlik olursa sürücü bu sıradaki ilkini seçer; ama yalnız kesin iyileşme varsa yerini değiştirir.

Şekil 8.17 başlangıç durumunu gösterir. Dinamik dört hamlede şöyle ilerler.

Her adımda Φ'nin düşüşü, hamle yapan sürücünün kazancına eşittir: 3, 2, 1. Bu, teoremin özdeşliğinin sayılarla doğrulanmasıdır. Örneğin sürücü 1'in hamlesinde s→A ve A→t kenarlarından birer terim silinir (4 ve 4, toplam 8: onun eski maliyeti); s→B ve B→t kenarlarına birer terim eklenir (4 ve 1, toplam 5: onun yeni maliyeti). ΔΦ = 5 − 8 = −3.

Şekil 8.18 dengeyi gösterir. Toplam maliyet 7 + 6 + 6 + 7 = 26'dır. A→B kenarı hiç olmasaydı sürücüler 2 + 2 bölünürdü: üst yolda 2 kişi (s→A 2, A→t 4: maliyet 6), alt yolda 2 kişi (s→B 4, B→t 2: maliyet 6). Toplam 24 olurdu. Kestirme, toplam maliyeti 24'ten 26'ya çıkarmıştır. Bu, Braess paradoksunun atomik sürümüdür.

Bir ayrıntı daha önemlidir: dinamiğin vardığı denge, oyunun tek dengesi değildir. Bütün profiller taranınca sürücü adları dışında dört saf denge bulunur: (alt, zik, zik, üst), (alt, zik, zik, zik), (zik, zik, zik, üst) ve dördünün de zik'te olduğu profil. Toplam maliyetleri sırasıyla 26, 29, 29 ve 32'dir. Dördünde de Φ = 20'dir ve bu, potansiyelin en küçük değeridir. Hangi dengeye varılacağı, hamle sırasına ve eşitlik kuralına bağlıdır.

8.4.4Potansiyel oyunlar: ne kazandık?

Rosenthal'ın fikri tıkanıklık oyunlarının ötesine genellenir. Dov Monderer ve Lloyd Shapley 1996'da bu genellemeye ad verdi (Monderer ve Shapley, 1996).

Potansiyel fonksiyonu, bütün oyuncuların bencil hamlelerini tek bir “ortak ölçü”de toplar. Her oyuncu kendi maliyetini düşürmek ister; potansiyel oyunda bunu yapan her hamle aynı ortak ölçüyü de düşürür. Oyuncular farkında olmadan aynı fonksiyonu küçültmek için çalışıyor gibidir. Bu bakış birkaç kazanç sağlar:

• Varlık. Φ'nin en küçük değerini veren durum bir saf Nash dengesidir; denge her zaman vardır.
• Yakınsama. İyileştiren hamleler dizisi sonsuza gidemez. Bu özelliğe sonlu iyileşme özelliği (finite improvement property) denir. Her en iyi tepki dinamiği durur.
• Öğrenme. Oyuncuların dengeyi “bilmesi” gerekmez. Sırayla en iyi tepki vermeleri dengeye ulaşmak için yeter. Bu, dengenin gerçek hayatta neden ortaya çıkabileceğine dair güçlü bir açıklamadır.
• Verimlilik. Φ'yi en küçük yapan denge, dengeler içinde iyi bir denge seçmenin bir yoludur; çünkü Φ toplam maliyetle yakından ilişkilidir. Ama bu bir garanti değildir: Örnek 8.13'teki ağda dört dengenin hepsinde Φ = 20'dir, toplam maliyetleri ise 26 ile 32 arasında değişir.
• Genellik. Her (tam) potansiyel oyun bir tıkanıklık oyununa denktir (Monderer ve Shapley, 1996). Yani tıkanıklık oyunları potansiyel oyunların “tipik” örneği değil, tam karşılığıdır.

Bir sınır da vardır: hız. Dinamiğin durması garantidir, hızlı durması değil. Φ her adımda en az bir miktar azalır, ama başlangıç değeri çok büyük olabilir ve adım sayısı oyuncu sayısıyla üstel olarak büyüyebilir. Alex Fabrikant, Christos Papadimitriou ve Kunal Talwar 2004'te genel tıkanıklık oyunlarında saf denge bulmanın PLS-tam (PLS-complete) olduğunu gösterdi (Fabrikant, Papadimitriou, Talwar, 2004). PLS, “yerel en iyi” bir çözüm bulma problemlerinin karmaşıklık sınıfıdır. PLS-tam olmak, bazı tıkanıklık oyunlarında dengeyi bulmak için hızlı bir yöntemin bilinmediği anlamına gelir. Basit durumlarda (örneğin bütün oyuncuların aynı kaynaktan aynı hedefe gittiği simetrik ağ oyunlarında) ise denge, bir akış problemine indirgenerek hızlı bulunabilir.

8.4.5Potansiyelde sık hatalar

8.5Ağ oluşturma

Şimdiye kadar ağ veriydi: yollar vardı ve kullanıcılar yalnız hangi yoldan gideceklerine karar veriyordu. Bu kesimde ağın kendisini oyuncular kurar. İnternette ağ işletmecileri birbirleriyle hangi bağlantıları kuracaklarına kendileri karar verir; sosyal ağlarda insanlar kiminle arkadaş olacaklarını seçer; eşler arası (P2P) dosya paylaşım ağlarında her bilgisayar hangi bilgisayarlara bağlanacağını seçer. Önce bu kararların arkasındaki temel kavram, dışsallık, incelenir.

8.5.1Ağ dışsallıkları: olumsuz ve olumlu

Olumsuz dışsallık: tıkanıklık. Bir yola giren her ek sürücü, aynı yoldaki diğer x kişinin her birini ℓ′(x) kadar yavaşlatır; toplamda x · ℓ′(x) gecikme yükler. İki yollu örnekte Yol 1'de 2.000 araç varken (ℓ₁′ = 1/100) bu yük 2.000 × 1/100 = 20 araç·dakikadır. Yeni sürücü kendi 25 dakikasını görür, ötekilere yüklediği 20 araç·dakikayı görmez. Sonuç: kalabalık yol gereğinden çok kullanılır. Bu, 8.2.4'te dengenin optimumdan sapmasının nedenidir. Çare tıkanıklık ücretidir: sürücüye ötekilere yüklediği gecikme kadar bir ücret ödetilirse, kendi hesabına bu etkiyi de katar (8.6.2).

Olumlu dışsallık: ağ etkisi. Bazı ağlara katılmanın değeri, katılan sayısıyla artar. Tek kişinin telefonu işe yaramaz; iki kişi birbirini arayabilir; yüz kişilik bir ağda her kullanıcı 99 kişiye ulaşır. Mesajlaşma uygulamaları ve sosyal ağlar da böyledir. n kullanıcılı bir ağda n(n − 1)/2 olası bağlantı vardır: 10 kullanıcıda 45, 100 kullanıcıda 4.950 bağlantı. Ağın değerinin bu yüzden n² ile büyüdüğü iddiası Metcalfe yasası olarak bilinir. Bu iddia kesin bir yasa değil, bir sezgidir: bütün bağlantılar eşit değerli değildir ve çoğu kullanıcı ağdakilerin küçük bir kısmıyla iletişim kurar.

Ağ etkisinde de dışsallık vardır: yeni bir kullanıcı ağa katılınca ötekilere de değer katar (onlar artık bir kişiye daha ulaşabilir), ama katılıp katılmamaya karar verirken yalnız kendi faydasına bakar. Bu yüzden benimseme, kritik kitle aşılana kadar yavaş kalır: az kişinin kullandığı bir ağa katılmak kimseye çekici gelmez.

Ağ oluşturma oyununda iki dışsallık bir aradadır. Bir bağ herkesin uzaklığını kısaltır: bağı kuranın yanında, o bağ üzerinden geçen herkes yararlanır (olumlu dışsallık). Ama bağın bedelini yalnız onu satın alan öder. Oyuncular bu yüzden toplum açısından en iyi olandan daha az bağ kurabilir.

8.5.2Ağ oluşturma oyunları

Ağ oluşturma modellerinde bağlantıya (link) kısaca bağ da denir. Her bağın bir kurulum maliyeti vardır; iyi bağlı olmak, yani ötekilere kısa uzaklıkta olmak ise değerlidir. Modelin temel gerilimi budur: bağ maliyeti ile erişim arasında bir denge kurmak. İki temel model vardır.

İki model gerçek hayattaki farklı durumlara karşılık gelir. Tek taraflı model, bir web sitesinin başka sitelere bağlantı vermesine ya da bir ağ işletmecisinin tek başına bir hat kiralamasına benzer: bağı kuran öder, karşı tarafın onayı gerekmez. İki taraflı model ise arkadaşlığa ya da iki ağ işletmecisinin karşılıklı internet eşlemesi (peering) anlaşmasına benzer: iki taraf da razı olmalıdır.

Her iki modelde de üç soru sorulur. Hangi ağlar dengedir? Sosyal olarak en iyi ağ hangisidir? İkisi ne kadar farklı olabilir? Bu sorular, bencil yönlendirmedeki “denge mi, optimum mu?” sorusunun ağ kurmadaki karşılığıdır.

8.5.3İki taraflı bağ: ikili kararlılık

Tanım Nash dengesinden biraz farklıdır. Nash dengesinde tek bir oyuncunun sapması incelenir. İkili kararlılıkta bağ koparmak tek kişinin kararıdır, ama bağ kurmak iki kişinin ortak kararıdır. Bu yüzden kurulmamış bir bağı değerlendirirken iki ucun da kazancına bakılır.

Somut bir örnek için n = 4 oyuncu (A, B, C, D) alınır. Bir oyuncunun faydası, ötekilere uzaklığına göre şöyle hesaplanır: uzaklığı 1 olan her oyuncudan 4, uzaklığı 2 olandan 2,2, uzaklığı 3 olandan 1 fayda. Her bağın bedeli, iki uçtaki oyuncuların her birine 2'dir. Oyuncunun net faydası, uzaklık faydalarının toplamından bağ bedellerinin çıkarılmasıyla bulunur. Şekil 8.19 karşılaştırılacak dört ağı gösterir.

Tablo 8.11 iki dersi birlikte verir. Birincisi, ikili kararlı ağlar birden fazla olabilir: hem döngü hem yıldız kararlıdır. Dört oyunculu bütün ağlar (64 olası bağ kümesi) taranınca yalnız dört yıldız (merkezi farklı) ve üç döngü (düğüm sırası farklı) ikili kararlı çıkar. İkincisi, kararlı bir ağ toplamı en yüksek ağla örtüşmek zorunda değildir. Yıldız, bütün ağlar içinde toplamı en yüksek olandır (25,2). Döngü kararlıdır ama yıldızdan 0,4 geridedir. Oyuncular döngüye varırsa oradan kendiliğinden çıkmazlar; tek bir oyuncunun ya da tek bir çiftin hamlesi döngüyü yıldıza dönüştüremez. Ağ Oluşturma oyununun “Social” senaryosu (4 düğüm) bu sayıları kullanır.

8.5.4Tek taraflı bağ: ağ oluşturma oyunu adım adım

Şimdi tek taraflı modele geçilir: n = 4 oyuncu, bağ fiyatı α = 1,5. Her oyuncu hangi bağları kendisi satın alacağını seçer; bağı kim alırsa alsın herkes kullanır. Bir oyuncunun maliyeti, aldığı bağ sayısının 1,5 katı ile ötekilere uzaklıklarının toplamıdır. Ağ kopuksa maliyet sonsuzdur; bu yüzden hiçbir oyuncu ağı koparan bir hamle yapmaz.

Şekil 8.20 başlangıç noktası olan yol ağını gösterir. Bu ağdan başlayarak birkaç aday ağ sırayla denetlenir.

Şekil 8.21, Şekil 8.22 ve Şekil 8.23 üç ağı karşılaştırır. Sonucun doğruluğu bir kaba kuvvet taramasıyla denetlenmiştir. Her oyuncunun stratejisi, öteki üç oyuncunun hangilerine bağ alacağıdır: 2³ = 8 seçenek. Dört oyuncu için 8⁴ = 4.096 strateji profili vardır. Her profilde her oyuncunun bütün sapmaları denenmiş ve α = 1,5'te denge olan ağların yalnız yıldız (sosyal maliyet 22,5) ve döngü (22) olduğu görülmüştür. Sosyal maliyeti en küçük olan tam çizge (21) bir denge değildir.

Bu sonucun anlamı, bencil yönlendirmedeki sonuçla aynıdır: denge ile optimum ayrışır. Tam çizgede her bağ, iki oyuncu arasındaki uzaklığı kısaltarak iki oyuncuya yarar (her biri ötekine 1 adım yakındır, sosyal kazanç 2). Ama bağın sahibi yalnız kendi kazancına (1) bakar ve bunu bağın fiyatıyla (1,5) karşılaştırır. Karşı tarafın kazancı dışsallıktır.

8.5.5Kod izleme: maliyet()

Bir oyuncunun maliyetini hesaplamak için ötekilere uzaklıkları bilinmelidir. Bağların hepsi eşit uzunlukta (1) olduğu için en kısa uzaklıklar genişlik öncelikli arama (BFS, breadth-first search) ile bulunur. BFS, başlangıç düğümünden başlar; önce bütün komşuları (uzaklık 1), sonra onların henüz görülmemiş komşularını (uzaklık 2) ziyaret eder ve böyle sürer.

def maliyet(i, bag, alpha):
  uz = {i: 0}; kuyruk = [i]
  while kuyruk:
    u = kuyruk.pop(0)
    for v in komsu(bag, u):
      if v not in uz:
        uz[v] = uz[u] + 1
        kuyruk.append(v)
  aldigi = sum(1 for (a, b) in bag if a == i)
  return alpha * aldigi + sum(uz.values())

Fonksiyon, komsu(bag, u) adlı yardımcı bir fonksiyon kullanır. Bu fonksiyon, u'nun komşularını kimin aldığına bakmadan döndürür: bağı kim alırsa alsın herkes kullanır. bag listesi (a, b) çiftlerinden oluşur; (a, b), bağı a'nın satın aldığı anlamına gelir. Kod satır satır şöyle çalışır:

• uz sözlüğü bilinen uzaklıkları tutar; başta yalnız i vardır (uzaklık 0). kuyruk, ziyaret edilecek düğümlerin listesidir.
• Kuyruk boşalana kadar baştaki düğüm u çıkarılır.
• u'nun her v komşusu için: v daha önce görülmemişse uzaklığı u'nunkinden 1 fazla yazılır ve v kuyruğun sonuna eklenir.
• aldigi, i'nin satın aldığı bağ sayısıdır: ilk elemanı i olan çiftler sayılır.
• Maliyet, alpha çarpı aldığı bağ sayısı artı bütün uzaklıkların toplamıdır.

Kod ağın bağlı olduğunu varsayar; bağlı değilse ulaşılamayan düğümler uz'a hiç girmez ve toplam yanlış biçimde küçük çıkar. Gerçek bir uygulamada len(uz) < n durumunda sonsuz döndürmek gerekir.

Şekil 8.24 ilk çağrının sonunu gösterir. Şimdi sapma denenir: oyuncu 1 ayrıca (1, 4) bağını satın alır. Aynı fonksiyon yeniden çağrılır.

Şekil 8.25 yeni bağla kısalan uzaklıkları gösterir. İki çağrının karşılaştırılması dengeyi denetler: 7 < 7,5 olduğundan sapma kârlıdır ve yol ağı bir Nash dengesi değildir. İkinci izlemede kuyruğun sırasına dikkat edilmelidir: 4, 3'ten önce kuyruğa girdiği için önce o çıkar. BFS'te bir düğüm ilk kez görüldüğü anda uzaklığı kesinleşir; sonradan daha kısa bir yol bulunamaz, çünkü düğümler uzaklık sırasıyla ziyaret edilir.

Bir oyuncunun bütün sapmalarını denemek için bu fonksiyon, oyuncunun her olası bağ kümesi için bir kez çağrılır. n oyunculu bir oyunda her oyuncunun 2^{n − 1} bağ kümesi vardır; bu sayı hızla büyür. Fabrikant ve arkadaşları, bir oyuncunun en iyi tepkisini bulmanın genel durumda NP-zor olduğunu da göstermiştir (Fabrikant vd., 2003). Küçük örneklerde kaba kuvvet yeter; büyük ağlarda yaklaşık yöntemler gerekir.

8.5.6Bağ fiyatı değişince denge ve optimum

Bağ fiyatı α değişince hem optimum hem dengeler değişir. Önce optimum incelenir. Dört oyunculu iki aday ağın sosyal maliyeti şöyle hesaplanır:

• Yıldız: 3 bağ. Uzaklık toplamı: merkez 1 + 1 + 1 = 3, her yaprak 1 + 2 + 2 = 5; toplam 3 + 3 · 5 = 18. Sosyal maliyet 3α + 18.
• Tam çizge: 6 bağ. Herkes ötekilere 1 uzaklıkta: 4 · 3 = 12. Sosyal maliyet 6α + 12.

İki doğru 3α + 18 = 6α + 12, yani α = 2'de kesişir (Şekil 8.26). α < 2 iken tam çizge, α > 2 iken yıldız daha ucuzdur. Bunun sezgisi açıktır: tam çizgede yıldıza göre 3 bağ fazladır (maliyet 3α) ve bu bağlar uzaklık toplamını 6 azaltır (her biri iki yaprağı birbirine 2 adım yakınlaştırır). Fazladan bağlar 3α < 6, yani α < 2 iken kârlıdır. Genel n'de de optimum α ≤ 2 için tam çizge, α ≥ 2 için yıldızdır (Fabrikant vd., 2003).

Tablo 8.14 üç bölgeyi gösterir.

• α < 1: bağ ucuz. Bir bağ en az 1 uzaklık kazandırır ve bedeli 1'den azdır. Bu yüzden herkes doğrudan bağlanır: tam çizge hem denge hem optimumdur. Yıldız ise denge değildir: α = 0,5'te yaprak başka bir yaprağa bağ alırsa 0,5 öder ve 1 kazanır.
• 1 < α < 2: arada. Optimum hâlâ tam çizgedir, ama tam çizge artık denge değildir: bağ bırakan oyuncu α kazanır, yalnız 1 kaybeder. α = 1,5'teki dengeler (yıldız 22,5, döngü 22) optimumdan (21) daha pahalıdır.
• α > 2: bağ pahalı. Optimum yıldızdır ve yıldız aynı zamanda dengedir. Ama yanında daha pahalı dengeler de çıkabilir. α = 2,5'te yol ağı (3 · 2,5 + 20 = 27,5) da bir dengedir. Bunun için bağları ortadaki iki oyuncunun alması gerekir: uçtaki bir oyuncu kendi bağına sahip olsaydı, bağını ortaya daha yakın bir düğüme taşıyarak uzaklığını azaltabilirdi.

Genel bir sonuç: α ≥ 1 olduğu sürece yıldız her zaman bir dengedir. Merkez bağ bırakırsa ağ kopar; yaprak yeni bir bağ alırsa en çok 1 uzaklık kazanır ve en az 1 öder. Ama denge çoğu zaman tek değildir ve bazı dengeler optimumdan belirgin biçimde kötüdür. Bencil davranışın bu kayıp oranı, ağ oluşturma oyunlarında da anarşinin bedeli adıyla incelenir.

8.5.7Ağ oluşturmada sık hatalar

8.6Kontrol ve teşvikler

Önceki kesimlerin ortak sonucu, bencil kullanıcıların vardığı dengenin toplum açısından en iyi durumdan ayrışabildiğidir. Bu kesimde bu ayrışmaya karşı neler yapılabileceği incelenir: kararları bir merkeze toplamak, kullanıcıların teşviklerini değiştirmek ya da kaynakları adil bir ölçütle paylaştırmak.

8.6.1Merkezi mi, dağıtık mı?

Bir ağda yönlendirme kararlarını kimin vereceği temel bir tasarım seçimidir. Tablo 8.15 iki uç yaklaşımı karşılaştırır.

Merkezi yönlendirmenin örnekleri gerçek ağlarda vardır. Yazılım tanımlı ağda (SDN, software-defined networking) yönlendiriciler kendi başlarına karar vermez; bir denetleyici yazılım bütün ağın durumunu görür ve her yönlendiriciye ne yapacağını söyler. Bir internet servis sağlayıcısı da kendi ağı içinde trafik mühendisliği yaparak trafiği hatlara dengeli dağıtır. Bu durumlarda merkez, kendi ağının sahibidir ve yönlendirdiği paketler itiraz etmez.

Dağıtık yönlendirmenin en önemli örneği ise internetin kendisidir. İnternet, binlerce bağımsız ağın birleşmesinden oluşur ve bu ağlar arasındaki rotalar BGP (Border Gateway Protocol, ağlar arası yönlendirme protokolü) ile seçilir. Her ağ, rotalarını kendi ticari çıkarına göre seçer. Şehir trafiğinde de her sürücü kendi navigasyon uygulamasını izler.

İki yaklaşımın güçlü ve zayıf yanları birbirini tamamlar. Merkezi yönlendirme optimumu hedefleyebilir, ama tüm talep ve gecikme bilgisine ihtiyaç duyar ve kullanıcıların uymasını gerektirir. Optimumda bazı kullanıcılar daha yavaş yoldadır (iki yollu örnekte Yol 2'dekiler 27,5 dakika yaşarken Yol 1'dekiler 20 dakika yaşar); bu kullanıcılar sapmak ister. Ayrıca merkez çökerse bütün sistem etkilenir. Dağıtık yönlendirme yalnız yerel bilgiyle çalışır ve uyum sorunu yoktur, çünkü herkes zaten kendi istediğini yapar; ama Braess paradoksundaki gibi verimsiz dengelere varabilir.

Bu yüzden ağlarda ara çözümler yaygındır. Merkez her şeyi kontrol etmez; yalnız bir kısmını etkiler:

• Fiyat: Merkez kullanıcılara ne yapacaklarını söylemez, ama bazı yolları daha pahalı yapar (tıkanıklık ücreti).
• Bilgi: Merkez rota önerir; kullanıcı öneriye uyup uymamakta serbesttir.
• Kısmi kontrol: Merkez trafiğin bir kısmını kendisi yönlendirir, gerisini kullanıcılar seçer. Buna Stackelberg yönlendirme (Stackelberg routing) denir. Ad, önce liderin hamle yaptığı, sonra izleyicilerin ona tepki verdiği Stackelberg oyunlarından gelir: merkez kendi trafiğini öyle yerleştirir ki bencil kullanıcıların vardığı denge daha iyi olur.

8.6.2Teşvikler, yük dengeleme ve uygulamalar

Doğru teşvikler, kullanıcıları ağ kaynaklarını dengeli kullanmaya yönlendirir ve verimliliği artırır. Trafikte ücretler ya da uyarılar yoğunluğu azaltır. Akıllı elektrik şebekelerinde zamana bağlı tarife, pik saatlerde yükü dengeler: elektrik akşam saatlerinde pahalıysa, çamaşır makinesi gece çalıştırılır. Teşviklerin en temiz örneği, 8.5.1'de anılan tıkanıklık ücretidir.

Fikir şudur: Wardrop dengesinin optimumdan sapmasının nedeni, sürücünün ötekilere yüklediği x · ℓ′(x) gecikmesini görmemesiydi. Her yola, optimumdaki bu dışsallık kadar bir ücret konursa sürücü artık “süre + ücret” toplamına bakar. Bu toplam, o yolun marjinal maliyetine eşit olur. Sürücüler bu toplamları eşitlediğinde, planlayıcının marjinal maliyetleri eşitlediği optimuma varılır.

Yanlış teşvikler ise ters etki yapar. Stratejik, bencil davranış artar ve sonuç tıkanıklık ile düşük verimliliktir. İki örnek sık görülür. Birincisi, herkese aynı “en hızlı” rotayı öneren bir navigasyon uygulaması yan yolları doldurabilir: uygulama her sürücüyü tek tek en hızlı yola gönderir, ama herkes aynı yola gidince o yol yavaşlar. İkincisi, ücret yanlış seçilirse trafik başka bir darboğaza kayar: bir köprü ücretli yapılınca bütün araçlar ücretsiz ama dar bir yan köprüye yönelebilir.

Bu bölümün kavramları üç büyük uygulama alanında kullanılır:

• İnternet. İSS'ler veri paketlerini yönlendirir; ağlar arası rota seçimi BGP ile yapılır. Yük dengeleme (ECMP) ve trafik mühendisliği tıkanıklığı azaltır.
• Trafik yönetimi. Rota optimizasyonu, akıllı sinyalizasyon ve navigasyon uygulamaları. Trafik planlamacıları yeni bir yolun etkisini, sürücülerin varacağı Wardrop dengesini hesaplayarak değerlendirir.
• Enerji. Akıllı elektrik şebekelerinde enerji dağıtımı ve yük kaydırma. Tüketicilerin elektriği ne zaman kullanacağı, tıkanıklık oyununa benzer bir yapı oluşturur: herkes aynı saatte kullanırsa şebeke zorlanır.

8.6.3Verimlilik ile adalet: bant genişliği paylaşımı

Toplam gecikmeyi en küçük yapmak tek ölçüt değildir. Bir ağın kaynakları kullanıcılar arasında paylaştırılırken adalet de önemlidir. Bunu görmek için küçük bir örnek kurulur. İki bağlantının kapasitesi 1'dir. Akış A ikisini de kullanır; akış B yalnız 1. bağlantıyı, akış C yalnız 2. bağlantıyı kullanır. Her akışa bir hız (x_A, x_B, x_C) verilecektir. Kapasite kısıtları şöyledir:

x_A + x_B ≤ 1, x_A + x_C ≤ 1

Hangi paylaşım seçilmelidir? Üç ölçüt üç farklı cevap verir (Tablo 8.16).

Üç ölçüt arasındaki fark bir değer yargısıdır. En büyük verim toplamı önemser ve bir kullanıcıyı tamamen dışarıda bırakmaya razıdır. Maksimin adalet en kötü durumdaki kullanıcıyı önemser; herkesi eşitler, ama toplamdan fedakârlık eder. Orantılı adalet (proportional fairness) ikisinin arasında durur. İki bağlantıyı birden kullanan A daha az alır, çünkü o iki kaynaktan pay tüketir; ama kimse sıfıra düşmez, çünkü sıfır pay çarpımı sıfırlar. Toplam (≈ 1,67), maksiminden yüksek, en büyük verimden düşüktür.

Orantılı adaletin Nash sosyal refahıyla aynı şey olması rastlantı değildir: iki kavram da “payların çarpımını maksimize et” der. Logaritma biçimindeki yazım, bu ölçütün “bir kullanıcının payını yüzde 10 artırmak, kimin olursa olsun aynı değerdedir” anlamına geldiğini gösterir. Frank Kelly ve arkadaşları 1998'de, internetin tıkanıklık denetimini (TCP benzeri protokolleri) bu açıdan yorumladı (Kelly vd., 1998). Her bağlantı, üzerindeki yük arttıkça bir tıkanıklık fiyatı bildirir; her akış, kendi yolundaki fiyatlara bakarak hızını ayarlar. Bu dağıtık algoritma, hiçbir merkez olmadan orantılı adil paylaşıma yakınsar.

8.6.4Tartışma soruları

Bu bölümün kavramları, kesin cevabı olmayan ama düşünmeye değer üç soruya ışık tutar.

Navigasyon uygulamaları herkese “en hızlı” rotayı önerdiğinde Wardrop dengesine mi, sistem optimumuna mı yaklaşılır? Neden? Uygulama her sürücüye o anki gecikmelere göre en hızlı rotayı öneriyorsa, her sürücü kendi en iyi tepkisini daha kolay bulur. Bu, Wardrop dengesine yaklaşmayı hızlandırır; sistem optimumuna değil. Uygulama, sürücülerin bir kısmını bilerek daha yavaş rotalara gönderirse optimuma yaklaşılabilir; ama o sürücüler öneriye uymayabilir. Tek bir uygulamanın çok sayıda kullanıcısı varsa uygulama bir tür Stackelberg lideri gibi davranabilir.

Bir şehir yeni bir köprü planlıyor. Braess etkisini önceden görmek için köprü açıldığında sürücülerin varacağı denge nasıl hesaplanır? Önce ağ modellenir: her yol için bir gecikme fonksiyonu (örneğin BPR) ve kaynak–hedef çiftleri arasındaki talepler belirlenir. Sonra köprülü ve köprüsüz iki ağda Wardrop dengesi hesaplanır; bu, Beckmann potansiyelini Frank–Wolfe gibi bir yöntemle en aza indirmek demektir. İki dengenin toplam gecikmeleri karşılaştırılır. Köprülü dengenin toplamı daha yüksekse köprü bencil kullanımla zarar verebilir; çare ücretlendirme ya da erişim kısıtı olabilir.

İnternette yönlendiriciler (BGP) bencil ajan mıdır? Kimin maliyetini en aza indirirler? Tek tek yönlendiriciler bir program izler; bencil olan, onları işleten ağlardır. Her ağ (örneğin bir İSS), rotalarını kendi ticari çıkarına göre seçer: ücret ödediği bir ağ yerine ücret aldığı ya da ücretsiz eşleme yaptığı ağları tercih eder. Bu yüzden internet rotaları çoğu zaman en kısa ya da en hızlı değildir. BGP'de minimize edilen, paketin gecikmesi değil, ağ işletmecisinin maliyetidir.

8.7Özet

• Gecikme yüke bağlıdır. Her kenarın gecikmesi, üzerindeki akışın azalmayan bir fonksiyonudur: sabit, doğrusal, BPR ya da kuyruk (1/(c − x)). Klasik en kısa yol algoritmaları (Dijkstra, Bellman–Ford) sabit ağırlık varsayar; yüke bağlı gecikme yönlendirmeyi bir oyuna dönüştürür.
• Bencil yönlendirmede her kullanıcı kendi gecikmesini küçültür. Bir yolun gecikmesi kenar gecikmelerinin toplamıdır; toplam gecikme C(f) = Σ f_e ℓ_e(f_e)'dir.
• Wardrop dengesinde kullanılan bütün yolların gecikmesi eşit ve en düşüktür. İki yollu örnekte (3.000 araç) denge 2.000 / 1.000, herkes 25 dakika, toplam 75.000 araç·dakikadır.
• Sistem optimumunda marjinal maliyetler (ℓ + x · ℓ′) eşitlenir: 1.500 / 1.500, toplam 71.250. Optimum bir denge değildir; fark, sürücünün hesaba katmadığı x · ℓ′ dışsallığından gelir.
• Beckmann potansiyeli Φ = Σ ∫ ℓ_e'nin en küçük noktası Wardrop dengesidir; denge her zaman vardır ve kenar gecikmeleri tektir. İkiye bölme (denge_bul) iki yollu ağda dengeyi her turda aralığı yarıya indirerek bulur.
• Braess paradoksu: 4.000 araçlı ağda 0 dakikalık kestirme herkesi 65'ten 80 dakikaya çıkarır; zikzak herkes için baskındır. Kestirmeli ağın optimumu ≈ 64,7'dir. Seri-paralel ağlarda paradoks görülmez; hangi yolların kapatılacağını seçmek genel ağlarda zordur.
• Tıkanıklık oyunlarında Rosenthal potansiyeli Φ = Σ_e Σ_{k ≤ ne} c_e(k), tek oyuncunun her sapmasında onun maliyet farkı kadar değişir. Bu yüzden saf Nash dengesi vardır ve en iyi tepki dinamiği durur (26 → 23 → 21 → 20); ama genel durumda hızlı durmayabilir (PLS-tam).
• Ağ oluşturmada bağ maliyeti ile erişim arasında gerilim vardır. İki taraflı modelde yıldız ve döngü ikili kararlıdır; tek taraflı modelde α = 1,5'te yıldız ve döngü dengedir, optimum olan tam çizge değildir. Optimum α ≤ 2 için tam çizge, α ≥ 2 için yıldızdır.
• Kontrol ve teşvikler: merkezi yönlendirme optimumu hedefler ama bilgi ve uyum ister; ara çözümler (tıkanıklık ücreti, rota önerisi, Stackelberg yönlendirme) yaygındır. Bant genişliği paylaşımında en büyük verim, maksimin adalet ve orantılı adalet farklı paylaşımlar seçer.

Denge ile optimum çoğu zaman ayrışır: sürücü kendi gecikmesine, planlayıcı marjinal maliyete bakar.

8.8Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• ağ tasarımı network design
• yönlendirme routing
• düğüm node
• bağlantı link
• kenar edge
• çizge graph
• kapasite capacity
• bant genişliği bandwidth
• yönlendirici router
• yıldız / halka / ağaç / tam örgü star / ring / tree / mesh topology
• OSPF Open Shortest Path First
• eşit maliyetli çok yol (ECMP) equal-cost multi-path
• gecikme fonksiyonu latency function
• BPR gecikme fonksiyonu BPR latency function
• M/M/1 kuyruğu M/M/1 queue
• bencil yönlendirme selfish routing
• bölünebilir (atomik olmayan) nonatomic
• atomik atomic
• Wardrop dengesi Wardrop equilibrium
• kullanıcı dengesi user equilibrium
• sistem optimumu system optimum
• marjinal maliyet marginal cost
• Beckmann potansiyeli Beckmann potential
• Braess paradoksu Braess's paradox
• seri-paralel ağ series-parallel network
• Wheatstone yapısı Wheatstone network
• tıkanıklık oyunu congestion game
• Rosenthal potansiyeli Rosenthal potential
• potansiyel fonksiyonu potential function
• potansiyel oyun potential game
• sonlu iyileşme özelliği finite improvement property
• PLS-tam PLS-complete
• dışsallık externality
• Metcalfe yasası Metcalfe's law
• ağ oluşturma oyunu network formation game
• ikili kararlılık pairwise stability
• internet eşlemesi peering
• tam çizge complete graph
• sosyal maliyet social cost
• yazılım tanımlı ağ (SDN) software-defined networking
• BGP (ağlar arası yönlendirme protokolü) Border Gateway Protocol
• internet servis sağlayıcısı (İSS) Internet service provider
• Stackelberg yönlendirme Stackelberg routing
• maksimin adalet max-min fairness
• orantılı adalet proportional fairness

8.9Kendini Dene

1. 5.000 araç A'dan B'ye gidiyor. Yol 1: ℓ₁ = 10 + x₁/100, Yol 2: ℓ₂ = 20 + x₂/400 (dakika). Wardrop dengesi, gecikme ve toplam gecikme nedir?

   Cevap

   Uç durumlar denge değildir: herkes Yol 1'de ise ℓ₁ = 60 > 20; herkes Yol 2'de ise ℓ₂ = 32,5 > 10. Eşitlik: 10 + x₁/100 = 20 + (5.000 − x₁)/400. 400 ile çarpılınca 4.000 + 4x₁ = 8.000 + 5.000 − x₁, 5x₁ = 9.000, x₁ = 1.800, x₂ = 3.200. Gecikmeler 10 + 18 = 28 ve 20 + 8 = 28 dakika. Toplam 5.000 × 28 = 140.000 araç·dakika.

2. Aynı ağda sistem optimumu ve toplam gecikmesi nedir? Bencil yönlendirme kaç araç·dakika fazla gecikme üretir?

   Cevap

   Marjinal maliyetler: Yol 1 10 + x₁/50, Yol 2 20 + x₂/200. Eşitlik: 10 + x₁/50 = 20 + (5.000 − x₁)/200; 200 ile çarpılınca 2.000 + 4x₁ = 4.000 + 5.000 − x₁, 5x₁ = 7.000, x₁ = 1.400, x₂ = 3.600. Gecikmeler 24 ve 29 dakika. Toplam 1.400 × 24 + 3.600 × 29 = 33.600 + 104.400 = 138.000. Fark 140.000 − 138.000 = 2.000 araç·dakika. Optimumda Yol 2'dekiler 5 dakika daha yavaştır ve Yol 1'e geçmek ister.

3. Braess ağında 3.000 araç olsun; dar yollar x/100, geniş yollar 50 dakika. Kestirme (A→B, 0 dakika) açılmadan önce ve açıldıktan sonra denge süresi nedir? Paradoks görülür mü?

   Cevap

   Önce: 1.500 / 1.500, her rota 15 + 50 = 65 dakika. Sonra: herkes zikzakta olsun; dar yollarda 3.000 araç (30 dakika), zikzak 30 + 0 + 30 = 60. Eski rotaya dönen 30 + 50 = 80 yaşar; kimse dönmez. Denge 60 dakikadır. Kestirme herkesi 5 dakika hızlandırır; paradoks görülmez. Dar yolun en kalabalık hâli (30) geniş yoldan (50) çok hızlı olduğu için kestirme gerçekten yararlıdır. Paradoks yalnız belirli bir trafik aralığında ortaya çıkar.

4. Atomik Braess ağında (s→A ve B→t: c_e(k) = k; s→B ve A→t: 4; A→B: 0) 3 sürücü (üst, alt, zik) profilindedir. Φ ve maliyetler nedir? Üst yoldaki sürücü zik'e geçerse Φ nasıl değişir?

   Cevap

   Kullanıcı sayıları: s→A 2 (üst, zik), A→t 1, s→B 1, B→t 2 (alt, zik), A→B 1. Φ = (1 + 2) + 4 + 4 + (1 + 2) + 0 = 14. Maliyetler: üst 2 + 4 = 6, alt 4 + 2 = 6, zik 2 + 0 + 2 = 4. Üst sürücü zik'e geçerse s→A'da kalır (2), A→B 0, B→t'de 3 kişi olur (3): yeni maliyet 2 + 0 + 3 = 5. Kazancı 1'dir; bu yüzden Φ 14'ten 13'e iner. Kontrol: A→t'den 4 silinir, A→B'ye 0 ve B→t'ye 3 eklenir; −4 + 3 = −1. Bu oyunun tek saf dengesi üç sürücünün de zik'te olduğu profildir (her biri 6, toplam 18); toplam maliyeti en küçük profillerden biri ise (üst, alt, zik)'tir (16).

5. Tek taraflı ağ oluşturma oyununda n = 5 oyuncu ve α = 3 olsun. Yıldızın ve tam çizgenin sosyal maliyeti nedir? Hangisi optimumdur? Yıldız bir Nash dengesi midir?

   Cevap

   Yıldız: 4 bağ, maliyet 4 · 3 = 12. Uzaklıklar: merkez 4 · 1 = 4, her yaprak 1 + 3 · 2 = 7; toplam 4 + 4 · 7 = 32. Sosyal maliyet 44. Tam çizge: 10 bağ (5 · 4/2), maliyet 30; uzaklık toplamı 5 · 4 = 20; sosyal maliyet 50. α = 3 > 2 olduğundan optimum yıldızdır. Yıldız dengedir: yaprak yeni bir bağla yalnız 1 uzaklık kazanır ve 3 öder; merkez bağ bırakırsa ağ kopar.

6. İki taraflı dört oyunculu örnekte (fayda: uzaklık 1 için 4, uzaklık 2 için 2,2, uzaklık 3 için 1) bağın her uca bedeli c olsun. c hangi aralıktayken tam çizge ikili kararlıdır? Yıldız?

   Cevap

   Tam çizge: bağ koparan c kazanır, o komşuya uzaklığı 1'den 2'ye çıkar ve 4 − 2,2 = 1,8 kaybeder. Kararlılık için c ≤ 1,8 gerekir; eklenecek bağ yoktur. Yıldız: iki yaprak bağ kurarsa her biri 1,8 kazanır ve c öder; kurulmaması için c ≥ 1,8. Merkez bir bağı koparırsa o yaprağı tamamen kaybeder (4) ve c kazanır; c ≤ 4 gerekir. Yaprak bağını koparırsa 8,4 kaybeder. Yıldız 1,8 ≤ c ≤ 4 aralığında kararlıdır. c = 1,8'de ikisi de kararlıdır.

7. İki yollu ağda (ℓ₁ = 5 + x₁/100, ℓ₂ = 20 + x₂/200, 3.000 araç) yalnız Yol 1'e bir ücret τ konacaktır (dakika karşılığı). Hangi τ değerinde ücretli denge sistem optimumuyla aynı olur?

   Cevap

   Optimum 1.500 / 1.500'dür; orada ℓ₁ = 20, ℓ₂ = 27,5. Ücretli dengenin 1.500'de olması için sürücünün iki yolu eşit görmesi gerekir: 20 + τ = 27,5, yani τ = 7,5. Daha küçük ücrette Yol 1 hâlâ fazla kalabalık, daha büyükte fazla boş kalır. Bu tek ücret, iki yola ayrı ayrı marjinal ücret (15 ve 7,5) koymakla aynı ücret farkını (7,5) verir; sürücünün kararı yalnız farka bağlıdır.

8. denge_bul(l1, l2, 3000) eps = 10 ile çağrılırsa döngü kaç tur döner ve son aralığın genişliği ne olur?

   Cevap

   Her tur genişliği yarıya indirir: k tur sonra genişlik 3.000/2^k'dir. Döngü genişlik 10'dan büyük olduğu sürece döner. 2⁸ = 256 için genişlik ≈ 11,7 > 10; 2⁹ = 512 için ≈ 5,86 ≤ 10. Döngü 9 tur döner; son genişlik yaklaşık 5,86 araçtır. eps = 50'ye göre yalnız 3 tur fazladır.

8.10İleri okuma

• T. Roughgarden, Selfish Routing and the Price of Anarchy (2005): bencil yönlendirme, Wardrop dengesi, Braess paradoksu ve ağ tasarımının zorluğunu tek bir kitapta, adım adım ispatlarla anlatır.
• N. Nisan, T. Roughgarden, É. Tardos ve V. Vazirani (ed.), Algorithmic Game Theory (2007), Bölüm 18–19: yönlendirme oyunlarını ve potansiyel fonksiyon yöntemiyle ağ oluşturma oyunlarını bilgisayar bilimi bakışıyla sunar.
• D. Easley ve J. Kleinberg, Networks, Crowds, and Markets (2010), Bölüm 8 ve 17: trafik ağlarını, Braess paradoksunu ve ağ etkilerini az matematikle, çok örnekle anlatır.
• A. R. Karlin ve Y. Peres, Game Theory, Alive (2017): trafik yönlendirmesini ve potansiyel oyunları öğrenci düzeyinde, alıştırmalarla verir.

8.11Kaynaklar

1. M. Beckmann, C. B. McGuire, C. B. Winsten, Studies in the Economics of Transportation, Yale University Press, 1956.
2. D. Braess, “Über ein Paradoxon aus der Verkehrsplanung”, Unternehmensforschung 12, 258–268, 1968.
3. J. E. Cohen, P. Horowitz, “Paradoxical behaviour of mechanical and electrical networks”, Nature 352, 699–701, 1991.
4. D. Easley, J. Kleinberg, Networks, Crowds, and Markets, Cambridge University Press, 2010 (Bölüm 8: trafik ağları ve Braess; Bölüm 17: ağ etkileri).
5. A. Fabrikant, A. Luthra, E. Maneva, C. Papadimitriou, S. Shenker, “On a network creation game”, ACM PODC, 2003.
6. A. Fabrikant, C. Papadimitriou, K. Talwar, “The complexity of pure Nash equilibria”, ACM STOC, 2004.
7. M. Jackson, A. Wolinsky, “A strategic model of social and economic networks”, Journal of Economic Theory 71(1), 44–74, 1996.
8. A. R. Karlin, Y. Peres, Game Theory, Alive, American Mathematical Society, 2017.
9. F. Kelly, “Charging and rate control for elastic traffic”, European Transactions on Telecommunications 8, 33–37, 1997.
10. F. Kelly, A. Maulloo, D. Tan, “Rate control for communication networks: shadow prices, proportional fairness and stability”, Journal of the Operational Research Society 49, 237–252, 1998.
11. W. Knödel, Graphentheoretische Methoden und ihre Anwendungen, Springer, 1969.
12. G. Kolata, “What if they closed 42d Street and nobody noticed?”, The New York Times, 25 Aralık 1990.
13. I. Milchtaich, “Network topology and the efficiency of equilibrium”, Games and Economic Behavior 57, 321–346, 2006.
14. D. Monderer, L. Shapley, “Potential games”, Games and Economic Behavior 14, 124–143, 1996.
15. N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory, Cambridge University Press, 2007 (Bölüm 18–19).
16. A. Rapoport, T. Kugler, S. Dugar, E. J. Gisches, “Choice of routes in congested traffic networks: Experimental tests of the Braess paradox”, Games and Economic Behavior 65(2), 538–571, 2009.
17. R. W. Rosenthal, “A class of games possessing pure-strategy Nash equilibria”, International Journal of Game Theory 2, 65–67, 1973.
18. T. Roughgarden, Selfish Routing and the Price of Anarchy, MIT Press, 2005.
19. T. Roughgarden, “On the severity of Braess's paradox: Designing networks for selfish users is hard”, Journal of Computer and System Sciences 72, 922–953, 2006.
20. J. G. Wardrop, “Some theoretical aspects of road traffic research”, Proceedings of the Institution of Civil Engineers, Part II, 1, 325–378, 1952.

Ders sayfaları: Roughgarden CS364A · Hoefer AGT · Dinitz AGT · © Sercan Külcü. Tüm hakları saklıdır.