Bölüm 9: Anarşinin Bedeli

9.1Temel kavramlar

Oyun kuramının temel denge kavramı olan Nash dengesi bir kararlılık tanımıdır: dengede kimse tek başına seçimini değiştirmek istemez. Bu tanım dengenin iyi bir sonuç olduğunu söylemez. Mahkûmun İkilemi'nde iki oyuncu da ihanet eder ve ikisi birden sessiz kalsalardı alacakları sonuçtan daha kötüsünü alırlar. Bu bölüm, “denge ne kadar kötü olabilir?” sorusunu sayıya çevirir. Önce soruyu küçük bir oyunla somutlaştırıyoruz, sonra ölçütü tanımlıyoruz.

9.1.1Bir oyunla başlangıç: yük dengeleme

Bir sunucu kümesinde üç sunucu vardır: A, B ve C. Sunucuların hızları farklıdır; A'nın hızı 2, B ile C'nin hızı 1'dir. İşler sırayla gelir ve her iş sunuculardan birine yerleşir. Bir işin bitiş süresi, yerleştiği sunucunun toplam yükünün sunucu hızına bölümüdür. Örneğin A'da 4 birim iş varsa A'daki her iş 4 / 2 = 2 birim sürede biter. B'de 2 birim iş varsa B'deki işler 2 / 1 = 2 sürede, C'de 1 birim iş varsa C'deki iş 1 / 1 = 1 sürede biter.

Şekil 9.1'de yeni bir iş gelmiştir. İş yalnız kendi bitiş süresini düşünür. A'ya giderse A'nın yükü 5 olur ve iş 5/2 = 2,5 sürede biter. B'ye giderse 3/1 = 3, C'ye giderse 2/1 = 2 sürede biter. Bencil iş C'yi seçer. Bu seçim o iş için en iyisidir; ama sistemin toplam maliyeti için en iyisi olmak zorunda değildir. Oyun iki soru sorar:

• Her iş kendi bitiş süresini en aza indirirse sistemin toplam maliyeti de en küçük olur mu?
• Olmuyorsa, bencil işlerin vardığı denge en iyi atamadan en çok ne kadar kötü olabilir?

Birinci sorunun cevabı genelde “hayır”dır. İkinci sorunun cevabı ise oyuna göre değişen bir sayıdır ve bu bölümün asıl konusudur. Aynı oyun 9.4.8'de ayrıntılı olarak çözülür: orada en kötü dengenin toplam süresi 13, en iyi atamanınki 12,5 çıkar ve oran 1,04 olur.

9.1.2Anarşinin Bedeli: bencilliğin faturası

Anarşinin Bedeli (Price of Anarchy, PoA), bencil davranışın oluşturduğu en kötü denge ile sosyal optimum arasındaki verimlilik kaybını ölçer. Bu tanımdaki iki kavram şunlardır:

• Sosyal optimum (social optimum), sistemin ortak hedefi açısından en iyi sonuçtur. Maliyet problemlerinde sosyal optimum toplam maliyeti en aza indiren durumdur. Trafikte bu, bütün sürücülerin toplam yolculuk süresinin en küçük olduğu dağılımdır.
• Denge, herkesin kendi maliyetine bakarak seçim yaptığı ve kimsenin tek başına seçimini değiştirmek istemediği durumdur.

Trafik ağı iki kavram arasındaki gerilimi iyi gösterir. Her sürücü kendi yolculuk süresini azaltmaya çalışır. Ancak bir sürücünün yola girmesi o yoldaki herkesi biraz yavaşlatır ve sürücü bu etkiyi hesaba katmaz. Sonuçta herkes kendi açısından akıllıca davranırken toplam gecikme gereğinden büyük olabilir.

Kavramın tarihi kısadır. Elias Koutsoupias ve Christos Papadimitriou 1999'da paralel makinelere iş dağıtan bencil oyuncuları incelerken en kötü dengenin optimuma oranını “koordinasyon oranı” (coordination ratio) adıyla tanımladılar (Koutsoupias ve Papadimitriou, 1999). “Anarşinin bedeli” adını Papadimitriou 2001'de verdi (Papadimitriou, 2001). Ad bir karşılaştırmayı anlatır: her şeye karar veren merkezi bir “diktatör” yerine herkesin kendi başına karar vermesinin, yani anarşinin, bedeli.

Bu bölümde iki sayısal örnek sık sık karşımıza çıkar. Birincisi iki yollu bir ağdır: 3.000 araç iki yol arasında bölünür; bencil dengede toplam gecikme 75.000 araç·dk, en iyi dağılımda 71.250 araç·dk'dır. Oran 75.000 / 71.250 ≈ 1,053'tür; yani bencillik toplam gecikmeyi yaklaşık %5 artırır. İkincisi Braess ağıdır: 4.000 aracın kullandığı bir ağa yeni bir yol eklenince herkesin yolculuk süresi 65 dakikadan 80 dakikaya çıkar. Anarşinin Bedeli bu tür farkları tek bir sayıyla ölçer ve daha önemlisi, bütün bir oyun sınıfı için bu sayıya bir üst sınır koyar.

9.1.3Nash dengesi ve sosyal optimum

Oran iki ayrı sonucu karşılaştırır. Önce bu iki sonucu yan yana koymak yararlıdır.

Nash dengesinin tanımını kısaca hatırlayalım. n oyuncu vardır. Her oyuncu i bir s_i stratejisi seçer; seçimlerin tamamı s = (s₁, …, s_n) bir strateji profilidir. Oyuncu i'nin bu profildeki maliyeti C_i(s) ile gösterilir. s_−i, i dışındaki oyuncuların stratejileridir. Bir s profili, her oyuncu i ve her alternatif s_i′ için C_i(s) ≤ C_i(s_i′, s_−i) sağlanıyorsa bir Nash dengesidir. Sözle: ötekiler yerinde dururken hiçbir oyuncu kendi seçimini değiştirerek maliyetini düşüremez. Bu bölümde oyuncular kazanç değil maliyet taşır; bu yüzden eşitsizlik “küçük ya da eşit” yönündedir.

Dengenin optimumdan ayrışmasının üç tipik nedeni vardır:

1. Bireysel rasyonellik. Herkes kendi faydasına bakar. Sistemin toplam maliyeti kimsenin amaç fonksiyonunda yer almaz.
2. Dışsallıklar. Bir oyuncunun seçimi başkalarının maliyetini değiştirir, ama oyuncu bu etkiyi hesaba katmaz. Yola giren sürücü ötekileri yavaşlatır; bu yavaşlama sürücünün kendi faturasında görünmez. Başkasına yüklenen ve karar verenin hesaba katmadığı bu maliyete dışsallık (externality) denir.
3. Bilgi eksikliği. Oyuncular sistemin bütününü görmeyebilir; en iyi düzeni bilseler bile ona uymak için güvence yoktur.

Bu iki sonuç arasındaki oran Anarşinin Bedeli ile ölçülür. Oranın payında denge, paydasında optimum vardır.

9.1.4Tanımlar: PoA ve PoS

Bir oyunda birden çok Nash dengesi olabilir. Bu durumda “dengenin maliyeti” tek bir sayı değildir. İki doğal seçim vardır: en kötü dengeye bakmak ya da en iyi dengeye bakmak. İlki Anarşinin Bedeli'ni, ikincisi İstikrarın Bedeli'ni verir. Gösterim şöyledir: NE, oyunun Nash dengelerinin kümesidir; C(s), s durumundaki toplam maliyettir; OPT, toplam maliyeti en küçük durumdur (sosyal optimum).

İki tanım yalnız bir sözcükte ayrılır: max ya da min. PoA kötümser bir garantidir: oyuncular hangi dengeye giderse gitsin kayıp en çok bu kadardır. PoS ise iyimser bir senaryodur: biri oyuncuları en iyi dengeye yönlendirebilirse kayıp bu kadara iner. PoS'un adındaki “istikrar”, sonucun kararlı (dengede) olma şartından gelir: optimumun kendisi kararlı değilse, kararlı sonuçların en iyisi optimumdan ne kadar uzaktır?

Şekil 9.2 tanımı bir eksen üzerinde gösterir. Maliyet sağa doğru artar. Optimum tanım gereği en soldadır, çünkü hiçbir durum ondan ucuz olamaz. Dengeler optimumun sağında ya da tam üstündedir. En soldaki denge PoS'u, en sağdaki denge PoA'yı belirler. Bu resimden doğrudan şu sonuç okunur:

Fayda problemlerinde oran ters çevrilir. Bazı oyunlarda oyuncular maliyet değil fayda taşır ve sistem hedefi sosyal refahı (social welfare, kısaca SW) en büyük yapmaktır. Bu durumda en kötü denge, refahı en küçük olan dengedir. Oran SW(OPT) / SW(denge) olarak yazılır; yani optimum paya geçer. Böylece oran yine 1'den büyük ya da 1'e eşit olur ve “büyük değer daha kötü verimlilik demektir” kuralı korunur. Örneğin optimumun refahı 100, en kötü dengenin refahı 80 ise PoA 100/80 = 1,25'tir.

9.1.5Verimlilik ölçütleri ve oranın okunması

Oranın anlamı, sosyal maliyetin nasıl tanımlandığına bağlıdır. Bu bölümde iki ölçüt kullanılır:

• Toplam maliyet: tüm kullanıcıların gecikme ya da kaynak kullanım maliyetlerinin toplamı. Trafik örneklerinde ölçüt budur; birimi araç·dk'dır (her aracın dakika cinsinden süresi toplanır).
• En büyük yük (makespan): bir iş dağıtımında en yüklü makinenin yükü, yani tüm işlerin bitiş anı. Yük dengelemede kullanılan klasik ölçüt budur.

Maliyet problemlerinde PoA, en kötü denge maliyetinin sosyal optimum maliyetine oranıdır. PoA'nın 1 olması verimlilik kaybı bulunmadığını gösterir: en kötü denge bile optimum kadar iyidir. Oran büyüdükçe stratejik davranışın oluşturduğu kayıp artar. Oran yüzdeye kolayca çevrilir: PoA = 1,25 ise en kötü denge optimumdan %25 daha pahalıdır.

Neden en kötü durum? İlk bakışta en kötü dengeye bakmak fazla karamsar görünebilir. Ama PoA'nın değeri tam da buradan gelir. Oyuncuların hangi dengeye gideceğini çoğu zaman bilemeyiz: başlangıç durumuna, hamle sırasına ve rastlantıya bağlıdır. PoA bu bilgiye gerek duymayan bir garanti verir: “Ne olursa olsun kayıp en fazla bu kadar.” Bir ağ tasarımcısı PoA'nın küçük olduğunu biliyorsa merkezi bir denetime yatırım yapmadan da sistemin makul çalışacağından emin olabilir. Bu fikir, algoritmalardaki yaklaşım oranı fikrinin oyun kuramındaki karşılığıdır.

9.1.6İki kötü durum oranı: PoA ve yaklaşım oranı

Algoritma derslerinde NP-zor problemler için yaklaşım algoritmaları incelenir. Böyle bir problemde optimumu polinom zamanda bulmak (bilinen yöntemlerle) mümkün değildir; bunun yerine hızlı bir algoritma iyi bir çözüm bulur. Algoritmanın kalitesi yaklaşım oranı (approximation ratio) ile ölçülür: algoritmanın bulduğu çözümün maliyeti ile optimumun maliyeti arasındaki en kötü durum oranı. Anarşinin Bedeli de bir en kötü durum oranıdır. İkisinin farkı, optimuma ulaşmayı neyin engellediğindedir.

İki oran aynı problem üzerinde karşılaştırılabilir. Özdeş m makineye işleri dağıtıp en büyük yükü küçültmek NP-zor bir problemdir. Ronald Graham'ın 1966'da incelediği açgözlü liste algoritması işleri verilen sırayla alır ve her işi o anda en az yüklü makineye koyar (Graham, 1966). Bu algoritmanın bulduğu en büyük yük optimumun en çok 2 − 1/m katıdır. Aynı problemde işler bencil oyuncular olursa, saf Nash dengelerinin en büyük yükü optimumun en çok 2 − 2/(m + 1) katıdır (Finn ve Horowitz, 1979). m = 2 için iki sayı 3/2 ve 4/3'tür.

Analizin sınırları. PoA, oyuncuları tamamen bencil ve rasyonel kabul eder. Gerçek oyuncular yalnız bencil değildir: güven, sosyal normlar, itibar ve tekrarlanan etkileşim işbirliğini artırabilir. Bu yüzden PoA bir tahmin değil, kötümser bir garantidir. Gözlenen kayıp çoğu zaman PoA'nın verdiği sınırdan küçüktür; ama sınırın aşılmayacağı bilinir.

9.1.7Tanımlarda sık hatalar

9.2Pigou ağı

Anarşinin Bedeli'ni gösteren en küçük örnek, İngiliz iktisatçı Arthur Cecil Pigou'nun 1920'de verdiği iki yollu ağdır (Pigou, 1920). Örnek o kadar sadedir ki bütün hesap bir kâğıda sığar; ama doğrusal gecikmeli ağlardaki en kötü durumu tam olarak yakalar. Bu kesimde önce bölünebilir trafiğin dengesini tanımlıyoruz, sonra Pigou ağında dengeyi ve optimumu bulup oranı hesaplıyoruz.

9.2.1Kurulum: bölünebilir trafik ve Wardrop dengesi

Trafik ağları bir çizge ile modellenir: düğümler kavşaklar, kenarlar (bağlantılar) yollardır. Her kenarın bir gecikme fonksiyonu (latency function) vardır: ℓ_e(x), e kenarından x miktarda trafik geçerken o kenarı kullanan her sürücünün harcadığı süredir. Gecikme trafikle artar ya da sabit kalır; yoğun yol yavaştır. Sürücüler bir başlangıç düğümü s'den bir hedef düğümü t'ye gider ve her biri bir yol (ardışık kenarlar dizisi) seçer. Bir yolun gecikmesi üzerindeki kenarların gecikmelerinin toplamıdır.

Pigou ağında ve trafik örneklerinin çoğunda sürücü sayısı çok büyüktür ve tek bir sürücünün etkisi yok sayılacak kadar küçüktür. Bu durumda trafik bölünebilir (nonatomic) kabul edilir: toplam trafik 1 birim ise bu bir, sonsuz çok küçük sürücüden oluşan bir “akışkan” gibi düşünülür ve istenen oranda bölünebilir. Örneğin trafiğin 0,3'ü bir yolda, 0,7'si ötekinde olabilir. Tek bir sürücü yol değiştirdiğinde yolların gecikmeleri değişmez; çünkü bir sürücünün payı sıfıra yakındır.

Bu tanım, Nash dengesinin bölünebilir trafikteki karşılığıdır. Bir sürücü daha yavaş bir yoldaysa daha hızlı yola geçerek kazanırdı; dengede böyle bir sürücü yoktur. Tanım, İngiliz ulaştırma mühendisi John Glen Wardrop'un 1952'de ifade ettiği ilkeden adını alır. Wardrop'un ikinci ilkesi ise sistem optimumudur: toplam gecikmenin en küçük olduğu dağılım. Bu bölümde sistem optimumu ile sosyal optimum aynı şeydir.

Toplam gecikme şöyle hesaplanır. f_e, e kenarındaki trafik olsun. Bu kenardaki her sürücü ℓ_e(f_e) süre harcar ve kenarda f_e kadar trafik vardır; kenarın toplam maliyete katkısı “trafik × gecikme”dir:

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

9.2.2Pigou ağında denge

Pigou ağında s'den t'ye 1 birim trafik gider ve iki yol vardır. Trafiğin üst yoldaki payı x, alt yoldaki payı 1 − x olsun.

• Üst yol: gecikme ℓ(x) = x. Yol boşken hızlıdır, doldukça yavaşlar; herkes üstteyse gecikme 1'dir. Dar bir şehir içi yolu düşünülebilir.
• Alt yol: gecikme her zaman 1. Ne kadar araç girerse girsin süre değişmez. Geniş ama uzun bir çevre yolu düşünülebilir.

Dengeyi bulmak için bir sürücünün gözünden bakılır. Alt yolda süre 1'dir. Üst yolda süre x'tir ve x bir pay olduğundan hiçbir zaman 1'i aşmaz. Demek ki üst yol hiçbir zaman alttan yavaş değildir. Alt yolda bir sürücü varsa ve x < 1 ise o sürücü üste geçip kazanır. Bu geçişler x = 1'e kadar sürer. x = 1'de üst yolun gecikmesi 1 olur ve alt yolla eşitlenir; artık kimse geçerek kazanamaz.

9.2.3Sosyal optimum: toplam maliyetin en küçüğü

Şimdi merkezi bir planlayıcının gözünden bakılır. Planlayıcı x'i seçer ve toplam gecikmeyi en küçük yapmak ister. Üst yolda x kadar trafik, her biri x dk; alt yolda 1 − x kadar trafik, her biri 1 dk bekler:

C(x) = x · x + (1 − x) · 1 = x² − x + 1

Bu fonksiyonun en küçük değeri türev yardımıyla bulunur. Türev, bir eğrinin her noktadaki eğimidir. Bir çukurun en alt noktasında eğim sıfırdır: noktanın solunda eğri iner (eğim eksi), sağında çıkar (eğim artı). Bu bölümde gereken türev kuralları şunlardır: x^k'nın türevi k · x^k−1'dir (örneğin x²'nin türevi 2x); c · x'in türevi c'dir; sabit sayının türevi 0'dır; toplamın türevi türevlerin toplamıdır. Türev C′(x) ile gösterilir.

Optimumda trafiğin yarısı alt yola “feda edilir”. Bu sürücüler 1 dk bekler; üsttekiler ise yalnız 1/2 dk bekler. Optimum adil değildir ve kararlı değildir: alttaki sürücüler üste geçmek ister, çünkü orada yarım dakika beklerlerdi. Merkezi bir zorlama olmadan bu dağılım kendiliğinden ortaya çıkmaz.

Şekil 9.3 iki sonucu aynı grafikte gösterir. Sağdaki parabolün sağ ucu dengedir (kırmızı nokta, maliyet 1); en alt noktası optimumdur (mavi nokta, maliyet 3/4). Denge, eğrinin en kötü noktalarından birine oturmuştur.

9.2.4Oran: PoA = 4/3

Pigou ağının tek dengesi vardır; bu yüzden en kötü denge ile en iyi denge aynıdır ve PoA ile PoS eşittir:

PoA = C(denge) / C(optimum) = 1 / (3/4) = 4/3 ≈ 1,33

Bencil yönlendirme, merkezi planlamaya göre %33 daha fazla toplam gecikme üretir. Bu sayı küçük bir örnekten çıktı, ama önemi büyüktür: doğrusal gecikmeli her ağda, her trafik miktarında oranın 4/3'ü aşmadığı ispatlanmıştır (9.3.4). Pigou ağı bu sınıfın en kötü örneğidir.

9.2.5Özel maliyet ve marjinal maliyet

Denge ve optimum neden farklı yerlere düşer? Cevap, sürücünün baktığı maliyet ile toplumun baktığı maliyetin farklı olmasıdır.

• Sürücü özel maliyetine bakar. Üst yolda kendi gecikmesi x'tir; bunu alt yolun 1'iyle karşılaştırır. x < 1 olduğu sürece üstü seçer. Sonuç x = 1'dir.
• Toplum marjinal maliyete bakar. Üst yolun toplam maliyeti x · x = x²'dir. Üst yola küçük bir trafik eklenince bu toplam ne kadar artar? Türevi kadar: 2x. Alt yolun toplam maliyeti (1 − x) · 1'dir ve oraya eklenen her birim toplamı tam 1 artırır. Planlayıcı iki artışı eşitler: 2x = 1 ⇒ x = 1/2.

Tanımdaki formül çarpımın türevi kuralından gelir, ama sözle de anlaşılabilir. Bir kenarda f araç varken bir araç daha girer. Bu araç kendisi ℓ(f) kadar bekler. Ayrıca kenarın gecikmesi ℓ′(f) kadar artar ve bu artış kenardaki f aracın her birine yansır; toplam ek yük f · ℓ′(f)'dir.

Şekil 9.4 iki kesişimi gösterir. Kırmızı doğru ile düz mavi doğrunun kesiştiği yer dengedir; kırmızı doğru ile kesikli doğrunun kesiştiği yer optimumdur. İki mavi doğru arasındaki dikey uzaklık x · ℓ′(x) = x · 1 = x'tir: bir sürücünün diğerlerine yüklediği gecikme. Sürücü bu farkı görmez; bu yüzden fazla sayıda sürücü üst yola girer.

Bu gözlem genelleşir:

• Dengede kullanılan yolların gecikmeleri eşitlenir.
• Optimumda kullanılan yolların marjinal maliyetleri eşitlenir; yani “kendi gecikmem + benim yüzümden ötekilere eklenen gecikme” eşitlenir.

İki koşul arasındaki fark tam olarak f · ℓ′(f) terimidir. Bu fark, PoA'yı azaltmanın en doğrudan aracı olan tıkanıklık ücretinin dayanağıdır: sürücüye bu dışsallık kadar ücret ödetilirse sürücünün gördüğü maliyet marjinal maliyete eşit olur ve bencil seçim optimumla çakışır (9.6.2).

9.2.6İki yollu ağ: 3.000 araç

Aynı iki koşul daha gerçekçi bir ağda da uygulanabilir. 3.000 araç iki yol arasında bölünür. Yol 1 kısa ama dardır: ℓ₁ = 5 + x₁/100 dk. Yol 2 uzun ama geniştir: ℓ₂ = 20 + x₂/200 dk. Burada x₁ + x₂ = 3.000'dir. Gecikmeler doğrusaldır: ax + b biçimindedir; b boş yoldaki süre, a her ek aracın getirdiği yavaşlamadır.

Bu örnek iki şey gösterir. Birincisi, gerçekçi ağlarda kayıp çoğu zaman en kötü durum sınırından küçüktür. İkincisi, optimum dağılım her zaman bazı kullanıcıları daha uzun beklemeye zorlar. Bu sürücülerin optimuma gönüllü uyması beklenemez; onları yönlendirmek için ücret gibi bir teşvik gerekir. Aynı ağdaki ücret hesabı 9.6.1'de yapılır.

9.2.7Pigou ağında sık hatalar

9.3Doğrusal gecikme ve Braess

Pigou ağında oran 4/3 çıktı. Bu sayı tesadüf müdür, yoksa genel bir yasanın parçası mı? Bu kesim üç soruyu cevaplar. Gecikme fonksiyonu değişince oran nasıl değişir? Doğrusal gecikmede oran neden hiçbir ağda 4/3'ü aşmaz? Aynı ispat fikri başka oyunlara nasıl taşınır? Kesim, ünlü Braess ağında PoA hesabıyla kapanır.

9.3.1Gecikme dikleşince PoA büyür

Pigou ağında üst yolun gecikmesini ℓ(x) = x yerine ℓ(x) = x^p alalım; p ≥ 1 bir tamsayıdır. Alt yolun gecikmesi yine 1'dir. p büyüdükçe eğri “dikleşir”: x 1'den küçükken x^p çok küçüktür, x 1'e yaklaşınca birden 1'e çıkar. Örneğin 0,5¹ = 0,5, ama 0,5⁴ = 0,0625. Bu tür gecikme, kapasitesine yaklaşana kadar neredeyse boş gibi davranan, sonra aniden tıkanan bir yolu anlatır.

Denge değişmez. 0 ≤ x ≤ 1 iken x^p ≤ 1'dir; üst yol yine hiçbir zaman alttan yavaş değildir. Herkes üste geçer ve herkes 1 dk bekler: C(denge) = 1.

Optimum iyileşir. Toplam maliyet C(x) = x · x^p + (1 − x) · 1 = x^p+1 + 1 − x'tir. Optimumu bulmak için türev sıfıra eşitlenir:

1. x^p+1'in türevi (p + 1)x^p, 1 − x'in türevi −1'dir: C′(x) = (p + 1)x^p − 1.
2. (p + 1)x^p = 1 ⇒ x^p = 1/(p + 1).
3. İki yanın p'inci kökü alınır: x^OPT = (p + 1)^−1/p. Negatif üs “bir bölü” demektir; kesirli üs 1/p ise p'inci köktür. Örneğin p = 2 için 3^−1/2 = 1/√3 ≈ 0,577.
4. Optimum maliyet sadeleşir: x^p = 1/(p + 1) olduğundan x^p+1 = x/(p + 1) ve C(OPT) = x/(p + 1) + 1 − x = 1 − x · p/(p + 1).

Tablo 9.4 bir eğilimi gösterir. Gecikme dikleştikçe planlayıcı üst yola daha çok trafik koyabilir, çünkü üst yol kapasitesine yaklaşana kadar çok hızlıdır. Optimumda üst yoldaki pay artar (0,5'ten 0,838'e), optimum maliyet düşer (0,75'ten 0,212'ye). Denge ise yerinde durur: herkes üstte, herkes 1 dk. Oran bu yüzden büyür.

Büyüme yavaştır ama sınırsızdır. p sonsuza giderken x^OPT 1'e yaklaşır ve C(OPT) sıfıra iner; payda sıfıra yaklaşınca oran sınırsız büyür. Sayısal olarak p = 10'da PoA yaklaşık 3,51, p = 100'de yaklaşık 18,3'tür. Oran kabaca p / ln p hızında büyür. Buradan çıkan ders şudur: 4/3 evrensel bir sabit değildir; doğrusal gecikmeye özgüdür. Sınırı belirleyen ağın biçimi değil, gecikme fonksiyonlarının ne kadar “dik” olabileceğidir.

9.3.2Etkileşimli: gecikme üssü ve PoA

Şekil 9.6 aynı hesabı canlı yapar. Kaydırıcı üs p'yi 1'den 10'a kadar değiştirir. Soldaki grafik PoA'nın p'ye göre nasıl büyüdüğünü, sağdaki çubuklar dengede ve optimumda trafiğin iki yola nasıl bölündüğünü gösterir. Altta dört sayı yazılıdır: x* = (p + 1)^−1/p, C(OPT), C(denge) = 1 ve PoA.

Grafikte 4/3 düzeyi kesikli bir çizgiyle işaretlidir. Yalnız p = 1 noktası bu çizginin üstündedir; diğer bütün noktalar onun üzerindedir. Kaydırıcı sağa çekildikçe dengedeki çubuk değişmez (trafiğin %100'ü üstte), optimumdaki çubukta üst yolun payı büyür. Dengenin “katılığı” ile optimumun “esnekliği” arasındaki fark, oranın büyümesinin kaynağıdır.

9.3.3Kod izleme: pigou_poa(p)

Tablodaki sayılar kısa bir Python fonksiyonuyla üretilir. Fonksiyon p'yi alır ve Pigou ağının PoA'sını döndürür.

def pigou_poa(p):          # üst yol x**p, alt yol 1
  x = (p + 1) ** (-1 / p)  # C'(x) = 0 noktası
  opt = x ** (p + 1) + (1 - x)
  return 1 / opt           # denge maliyeti 1

for p in [1, 2, 4, 8, 16]:
  print(p, round(pigou_poa(p), 3))

Kod satır satır şöyle çalışır:

• x = (p + 1) ** (-1 / p): türevin sıfır olduğu nokta, yani optimumdaki üst yol payı. Python'da ** üs alma işlecidir; -1 / p kesirli bir üstür.
• opt = x ** (p + 1) + (1 - x): bu noktadaki toplam maliyet. Birinci terim üst yolun katkısı (x · x^p), ikinci terim alt yolun katkısıdır.
• return 1 / opt: denge maliyeti her p için 1 olduğundan oran 1 / C(OPT)'dir.
• Son iki satır fonksiyonu p = 1, 2, 4, 8, 16 için çağırır ve sonucu üç basamağa yuvarlayarak yazar.

Her satırda x^p+1 = x/(p + 1) özdeşliği de denetlenebilir. Örneğin p = 4 için 0,6687 / 5 ≈ 0,1337 ✓. Çıktı sütununda ondalık ayırıcı noktadır, çünkü Python sayıları İngilizce yazımla basar.

9.3.4Doğrusal gecikmede 4/3 üst sınırı

Pigou ağında oranın tam 4/3 olduğunu gördük. Tim Roughgarden ve Éva Tardos 2002'de bunun bir rastlantı olmadığını gösterdiler: doğrusal gecikmeli hiçbir ağda oran 4/3'ü aşmaz (Roughgarden ve Tardos, 2002).

İspat üç adımdır ve her adım küçük bir fikre dayanır. Gösterim şöyledir: f_e dengede e kenarındaki trafik, f_e^OPT optimumdaki trafiktir. Toplam gecikme her kenarda “trafik × gecikme” toplamıdır: C(f) = Σ_e ℓ_e(f_e) · f_e.

1. adım: denge koşulu. Dengede herkes o anki gecikmelere göre en kısa yolu kullanır. Bir düşünce deneyi yapalım: gecikmeleri dengedeki değerlerinde “donduralım” ve sürücüleri optimumdaki yollara taşıyalım. Dondurulmuş gecikmelerle hiçbir sürücü dengedeki yolundan daha kısa bir yol bulamaz; çünkü dengedeki yolu zaten en kısasıdır. Bu yüzden optimumun dağılımı, dondurulmuş gecikmelerle ölçülünce dengenin kendisinden ucuz olamaz:

Σ_e ℓ_e(f_e) · f_e ≤ Σ_e ℓ_e(f_e) · f_e^OPT

Sol yan dengenin gerçek maliyeti C(f)'dir. Sağ yan bir düşünce deneyidir: yollar dengedeki kadar yavaş, ama trafik optimumdaki gibi dağılmış. Geriye bu sağ yanı optimumun gerçek maliyeti C(f^OPT) ile sınırlamak kalır. Bunu 2. adım her kenar için ayrı ayrı yapar.

9.3.5Kenar eşitsizliği ve toplama

2. adım: kenar eşitsizliği. Doğrusal gecikmeli her kenar için şu eşitsizlik doğrudur:

ℓ_e(f_e) · f_e^OPT ≤ ℓ_e(f_e^OPT) · f_e^OPT + ¼ · ℓ_e(f_e) · f_e

Sözle: düşünce deneyindeki bedel (sol yan), optimumun o kenardaki kendi bedelini en çok dengenin o kenardaki bedelinin dörtte biri kadar aşar.

Neden doğru? Kenar indisini bırakıp kısaca f ve f^OPT yazalım ve ℓ(x) = ax + b'yi yerine koyalım. İfadeler iki gruba ayrılır:

• b'li terimler. Solda b · f^OPT, sağda b · f^OPT + ¼ · b · f vardır. Sağdaki ek terim negatif olamaz (b, f ≥ 0); sağ yan büyüktür.
• a'lı terimler. Solda a · f · f^OPT, sağda a · (f^OPT)² + a · f²/4 vardır. Gereken eşitsizlik a · f · f^OPT ≤ a · (f^OPT)² + a · f²/4'tür. Her şey sağa toplanırsa 0 ≤ a · ((f^OPT)² − f · f^OPT + f²/4) = a · (f^OPT − f/2)² çıkar. Bir karenin negatif olmaması ve a ≥ 0 yeterlidir.

Son adımdaki tam kare açılımla denetlenebilir: (u − v)² = u² − 2uv + v²; burada u = f^OPT, v = f/2 alınırsa 2uv = f · f^OPT ve v² = f²/4 olur. Eşitlik ancak f^OPT = f/2 iken (ya da a = 0 ve b · f = 0 iken) sağlanır. ¼ sabiti bu tam karenin katsayısından gelir.

3. adım: topla. 2. adımdaki eşitsizlik bütün kenarlar için toplanır. Sol yanların toplamı 1. adımdaki sağ yandır. Sağ yanların toplamı C(f^OPT) + ¼ · C(f)'dir. 1. adımla birleştirilince:

C(f) ≤ Σ_e ℓ_e(f_e) f_e^OPT ≤ C(f^OPT) + ¼ · C(f)

¼ · C(f) sola geçirilir: ¾ · C(f) ≤ C(f^OPT). İki yan ¾ · C(f^OPT)'ye bölünür: C(f) / C(f^OPT) ≤ 4/3. □

Pigou ağında eşitlik olduğu için sınır sıkıdır (tight bound): 4/3'ten küçük bir sayı yazılamaz. Üstelik Roughgarden 2003'te daha güçlü bir şey gösterdi: bir gecikme sınıfında en kötü örnek her zaman Pigou gibi iki paralel bağlantılı bir ağdır (Roughgarden, 2003). Yani ağın karmaşıklığı PoA'yı büyütmez; PoA'yı yalnız gecikme fonksiyonlarının sınıfı belirler. Doğrusal sınıf için bu 4/3, x^p gibi polinomlar için Tablo 9.4'teki değerlerdir.

9.3.6Sınırın sayısal sınanması

Bir sınırın ne söylediğini anlamanın iyi yolu, onu bilinen örneklerle karşılaştırmaktır. Tablo 9.6 bu bölümün örneklerini bir araya getirir.

Kuramsal üst sınır, bir sınıftaki (örneğin doğrusal gecikmeli bütün ağlardaki) en kötü durumdur. Belirli bir örnekte gözlenen oran çoğu zaman daha küçüktür. Tablodaki rastgele deneyde bir betik 2–4 paralel bağlantılı, gecikme katsayıları a, b ve trafik talebi rastgele seçilmiş 20.000 ağda dengeyi ve optimumu hesapladı. Oran hiçbir örnekte 4/3'ü aşmadı; Pigou'ya benzeyen örneklerde (bir bağlantı neredeyse sabit, öteki sıfırdan başlayan doğrusal) 4/3'e yaklaştı. Bu notun hesaplarında yinelenen deney de en büyük oranı yaklaşık 1,333 buldu.

Son satırdaki örnek farklı bir sınıftandır. Oradaki oyuncular bölünebilir trafik değil, tek tek işlerdir; bu tür oyunların sınırı 5/2'dir ve 9.3.9'da ele alınır.

9.3.7Tek bir reçete: pürüzsüzlük

4/3 ispatının yapısına dikkatle bakılırsa yalnız iki malzeme kullanıldığı görülür: dengenin tanımı ve her kenarda geçerli bir eşitsizlik. Roughgarden 2009'da bu yapıyı bir reçeteye dönüştürdü (Roughgarden, 2009). Reçetenin adı pürüzsüzlüktür (smoothness) ve birçok oyunun PoA sınırı aynı kalıpla ispatlanabilir.

Düşünce deneyi. s bir durum olsun (her oyuncunun bir stratejisi var), s^OPT optimum. Ötekiler s'de kalırken yalnız oyuncu i, s^OPT'deki stratejisine geçseydi ne öderdi? Bu, i'nin deneme maliyetidir.

Gösterim. s_−i: i dışındaki oyuncuların stratejileri. C_i(s_i^OPT, s_−i): i'nin deneme maliyeti. C(s) = Σ_i C_i(s): toplam maliyet.

Sözle: deneme maliyetlerinin toplamı, optimumun maliyetinin λ katı ile s'nin maliyetinin μ katının toplamını aşmaz. Eşitsizlik her durum s için istenir; yalnız dengeler için değil. Bu, koşulu güçlü ama kullanışlı yapar. λ ve μ küçüldükçe elde edilen sınır iyileşir.

4/3 ispatındaki kenar eşitsizliği tam olarak bir pürüzsüzlük koşuludur. Sol yanı “dengedeki gecikmelerle, optimumdaki trafiğin bedeli”dir; bölünebilir trafikte bu, deneme maliyetlerinin toplamıdır. Sağ yanı 1 · C(f^OPT) + ¼ · C(f)'dir. Demek ki doğrusal gecikmeli bölünebilir yönlendirme (1, ¼)-pürüzsüzdür.

9.3.8Pürüzsüzlükten PoA sınırına

Tanıdık örnekler. 4/3 ispatının kenar eşitsizliği λ = 1, μ = ¼ demektir: 1 / (1 − ¼) = 1 / (3/4) = 4/3. Atomik (bölünemez oyunculu) doğrusal tıkanıklık oyunlarında λ = 5/3, μ = 1/3 alınabilir: (5/3) / (2/3) = 5/2.

Neden önemli? İspat yalnız “kimse tek başına sapmaz” koşulunu, üstelik yalnız tek bir sapma için (optimumdaki stratejiye geçiş) kullanır. Bu koşul daha gevşek denge türlerinde de ortalama olarak sağlanır. Örneğin oyuncuların olasılıklı seçim yaptığı karışık dengelerde 1. adım beklenen değerlerle yazılabilir ve aynı sınır çıkar. Pürüzsüzlükle elde edilen ve bu şekilde geniş denge türlerine taşınan sınıra sağlam PoA (robust Price of Anarchy) denir.

9.3.9Atomik tıkanıklık oyunları: PoA ≤ 5/2

Bölünebilir trafikte tek bir sürücünün etkisi yok sayılır. Oysa birçok sistemde oyuncu sayısı azdır ve her oyuncu kaynağı fark edilir ölçüde yükler: birkaç büyük veri aktarımı, birkaç sunucu işi. Bu tür oyunlara atomik (atomic) tıkanıklık oyunları denir. Model şöyledir:

• Her oyuncu bir birim yük taşır ve bir kenar kümesi (yol) seçer.
• Kenar maliyeti doğrusaldır: kenarı x oyuncu kullanıyorsa her biri c_e(x) = a_ex + b_e öder.
• z_e: dengede e kenarını kullanan kişi sayısı; y_e: optimumda kullanan kişi sayısı.

Fark tek bir noktadadır. Bölünebilir trafikte yol değiştiren sürücü yeni yolun gecikmesini değiştirmez. Atomik oyunda tek başına optimumdaki yoluna geçen bir oyuncu, e kenarında en çok z_e + 1 kişi bulur: dengede orada olan z_e kişi ve kendisi. Bu “+1”, oyuncunun kendi eklediği gecikmedir.

Anahtar eşitsizlik. c(x) = x olan bir kenar için deneme maliyetlerinin toplamı en çok y(z + 1)'dir: optimumda kenarı kullanan y oyuncunun her biri en çok z + 1 öder. Optimumun o kenardaki maliyeti y · y = y², dengenin maliyeti z²'dir. Gereken pürüzsüzlük eşitsizliği, her y, z ≥ 0 tamsayısı için:

y(z + 1) ≤ 5/3 · y² + 1/3 · z²

Şekil 9.8 eşitsizliği küçük değerlerde tek tek sınar. Hücre değeri 3 · (5/3 · y² + 1/3 · z² − y(z + 1)) = 5y² + z² − 3y(z + 1)'dir. Hiçbir hücre negatif değildir; bir betik y, z ≤ 60 için bütün değerleri denedi ve negatif değer bulmadı. Turuncu 0'lar eşitlik noktalarıdır: (y, z) = (0, 0), (1, 1) ve (1, 2).

Genel doğrusal maliyet a x + b için de aynı sonuç çıkar: a'lı kısım yukarıdaki eşitsizliğin a katıdır, b'li kısım ise (sabit maliyet kalabalıktan etkilenmediği için) b · y ≤ 5/3 · b · y biçiminde kendiliğinden sağlanır. 5/2 sınırı da sıkıdır; bunu Awerbuch, Azar ve Epstein ile Christodoulou ve Koutsoupias 2005'te birbirinden bağımsız gösterdiler (Awerbuch vd., 2005; Christodoulou ve Koutsoupias, 2005).

Karşılaştırma öğreticidir: bölünebilir trafikte sınır 4/3, bölünemez oyuncularda 5/2'dir. Aradaki farkın kaynağı z + 1'deki “+1”dir: oyuncunun kendi eklediği gecikme. (y, z) = (1, 1)'de sol yan 2'dir; daha küçük bir λ ile, örneğin (1, 1/3) ile, sağ yan 1 + 1/3 = 4/3 < 2 olurdu ve eşitsizlik bozulurdu. Bu yüzden büyük oyuncuların oyunlarında kayıp daha büyük olabilir.

9.3.10Braess ağında PoA

Braess paradoksu bencil yönlendirmenin en şaşırtıcı sonucudur: bir ağa yeni bir yol eklemek herkesin yolculuk süresini artırabilir. Alman matematikçi Dietrich Braess 1968'de bu olguyu gösterdi. Bu notta paradoksun PoA açısından nasıl okunacağı incelenir.

Ağda s'den t'ye 4.000 araç gider. Dört eski bağlantı vardır: s→A ve B→t trafiğe bağlıdır (x/100 dk), A→t ve s→B sabittir (45 dk). Yeni yol açılmadan önce iki rota vardır ve simetri nedeniyle trafik eşit bölünür: her rotada 2.000 araç, süre 2.000/100 + 45 = 65 dk. Bu dağılım hem denge hem optimumdur; PoA = 1'dir.

Şimdi A→B arasına gecikmesi 0 olan bir yol açılır. Artık üçüncü bir rota vardır: s→A→B→t (zikzak).

Denge. Şekil 9.9'da herkes zikzaktadır. Denetleyelim: s→A ve B→t'de 4.000'er araç vardır, her biri 4.000/100 = 40 dk'dır. Zikzak 40 + 0 + 40 = 80 dk sürer. Eski rotaya geçen bir sürücü 40 + 45 = 85 dk bekler; 85 > 80 olduğundan kimse geçmez. Denge maliyeti 4.000 · 80 = 320.000 araç·dk'dır. Yeni yol herkesin süresini 65'ten 80 dakikaya çıkarmıştır.

Sık yapılan kıyas: 80/65 ≈ 1,23. Bu oran yeni ağın dengesini eski ağın dengesiyle karşılaştırır ve Braess kaybını ölçer. Ama PoA'nın paydası aynı ağın optimumudur. Soru şudur: yeni yollu ağda planlayıcı 65 dakikadan daha iyi bir ortalama elde edebilir mi?

Planlayıcı zikzağı kullanır mı? Eski dağılımda (her eski rotada 2.000, zikzak boş) marjinal maliyetlere bakılır. s→A'da 2.000 araç vardır ve gecikme 20 dk'dır. Marjinal maliyet ℓ + x · ℓ′ = 20 + 2.000 · (1/100) = 40 dk'dır. Zikzak bu türden iki kenar kullanır: 40 + 0 + 40 = 80. Eski rota ise 40 + 45 = 85'tir (sabit kenarın marjinal maliyeti kendi gecikmesine eşittir). 80 < 85: planlayıcı bile birkaç aracı zikzağa yollar.

Şekil 9.10 optimum dağılımı gösterir. Yeni yol optimumu biraz iyileştirmiştir (260.000'den 258.750'ye), ama dengeyi çok kötüleştirmiştir (260.000'den 320.000'e). PoA bu iki etkiyi aynı ağın içinde ölçer.

Normalleştirilmiş Braess ağı. Ders kitaplarında ağ genellikle 1 birim trafikle ve sade gecikmelerle verilir: s→A: x, A→t: 1, s→B: 1, B→t: x, A→B: 0. Dengede herkes zikzaktadır: 1 + 0 + 1 = 2; eski rotaya geçen 1 + 1 = 2 bekler ve kazanmaz. Optimum, zikzağı kapatıp trafiği yarı yarıya bölmektir: her sürücü 1/2 + 1 = 3/2 bekler. Oran 2 / (3/2) = 4/3'tür: bu ağ da 4/3 sınırına tam olarak ulaşır. 4.000 araçlı ağda sabit ve değişken kenarların süreleri bu kadar uyumlu değildir; bu yüzden oran sınırın altında, 1,237'de kalır.

9.3.11Sınırlarda sık hatalar

9.4Yük dengeleme

Anarşinin Bedeli ilk kez trafik ağlarında değil, paralel makinelere iş dağıtan bir modelde tanımlandı (Koutsoupias ve Papadimitriou, 1999). Bu model bugün sunucu kümelerinde, bulutta görev yerleştirmede ve işlemci çekirdeklerine iş dağıtmada karşımıza çıkar. Trafikten iki farkı vardır: oyuncular bölünemez (her iş tek bir makineye gider) ve sosyal maliyet çoğu zaman toplam değil, en büyük yüktür.

9.4.1Yük dengeleme oyunu

Bu modelde iş j, k makinesinden h makinesine geçerse yeni maliyeti yük(h) + w_j olur; çünkü h'deki mevcut yüke kendi boyunu ekler. Geçiş, bu sayı şimdiki maliyeti yük(k)'dan küçükse kârlıdır. Bir atama, hiçbir iş için kârlı bir geçiş yoksa Nash dengesidir:

her j ve her h için: yük(h) + w_j ≥ yük(k_j)

Burada k_j, j'nin şu anki makinesidir. Kendi makinesine “geçiş” anlamsızdır: h = k_j iken sol yan yük(k_j) + w_j olur ve sağ yandan hep büyüktür.

Saf Nash dengesi her zaman vardır. Bu, her oyunda doğru değildir; örneğin Taş-Kâğıt-Makas'ta saf denge yoktur. Yük dengelemede ise şu akıl yürütme dengenin varlığını gösterir. Herhangi bir atamadan başlanır. Bir dengede değilsek kârlı bir geçiş vardır: iş j, k'den h'ye geçer ve yük(h) + w_j < yük(k)'dır. Geçişten sonra k'nin yükü azalır, h'nin yükü artar; ama h'nin yeni yükü k'nin eski yükünden küçüktür. Makine yükleri büyükten küçüğe sıralanıp bir liste yapılırsa, bu liste geçişten sonra “küçülür”: iki liste soldan karşılaştırıldığında ilk farklı yerde yeni listede daha küçük bir sayı vardır. Sözlükteki sıralamaya benzeyen bu karşılaştırmada liste sonsuza dek küçülemez, çünkü işlerin makinelere dağılımı sonlu sayıdadır ve hiçbir liste tekrar edemez. Demek ki kârlı geçişler bir yerde biter; bittiği yer bir Nash dengesidir.

9.4.2Adım adım: {2, 2, 1, 1} örneği

Dört iş (boylar 2, 2, 1, 1) ve iki özdeş makine. Her iş kendi bitiş süresini, yani makinesinin toplam yükünü küçültmek ister. Sosyal maliyet en büyük yüktür.

Bu örnekte kötü dengenin oluşma nedeni Şekil 9.12'de görülür. M1 fazla yüklüdür, ama oradaki işler büyüktür; M2'ye geçince kendi boyları yüzünden yine 4 beklerler. M2'deki küçük işler ise M1'e gitmek için hiçbir neden görmez. Kimse “yükü dengelemek” için kendini feda etmez. Eşitlikte (4 < 4 yanlış) iş yerinde kalır; bu kural tanımdaki kesin küçüklükten gelir.

9.4.3Kod izleme: nash_mi()

Bir atamanın denge olup olmadığını denetleyen fonksiyon şöyledir. boy iş boylarının listesi, atama her işin makine indisidir (0 = M1, 1 = M2), m makine sayısıdır.

def nash_mi(boy, atama, m):
  yuk = [0] * m
  for j, k in enumerate(atama):
    yuk[k] += boy[j]
  for j, k in enumerate(atama):
    for h in range(m):
      if yuk[h] + boy[j] < yuk[k]:
        return False      # j kaçar
  return True             # kimse kaçmaz

Fonksiyon iki aşamada çalışır:

• Yükleri hesapla. yuk = [0] * m, m tane sıfırdan oluşan bir liste kurar. İlk döngüde enumerate(atama) her iş için indisi j ve makinesini k verir; işin boyu o makinenin yüküne eklenir.
• Sapmaları dene. İkinci döngü her iş j ve her makine h için yuk[h] + boy[j] < yuk[k] koşulunu sınar. Koşul doğruysa iş j h'ye geçerek kazanır; fonksiyon hemen False döndürür. Hiçbir sapma kârlı değilse True döner.

nash_mi([2, 2, 1, 1], (0, 0, 1, 1), 2) çağrısının izlemesi Tablo 9.7'de verilmiştir. h = k (kendi makinesi) için koşul hep yanlıştır, çünkü yuk[k] + boy[j] < yuk[k] olamaz; tabloda yalnız h ≠ k adımları gösterilir.

Hiçbir iş kârlı bir makineye kaçamadı; fonksiyon True döndürür: {2, 2} | {1, 1} bir Nash dengesidir. Aynı fonksiyon (0, 0, 0, 1) atamasıyla çağrılsaydı yükler [5, 1] olurdu ve ilk sapma denemesinde (i1 için 1 + 2 = 3 < 5) False dönerdi. Fonksiyonun maliyeti n iş ve m makine için O(nm) karşılaştırmadır.

9.4.4Kaba kuvvet: 16 atamanın hepsi

Dört işin her biri iki makineden birini seçebildiğinden 2⁴ = 16 atama vardır. Makineler özdeş olduğu için M1 ile M2'nin yer değiştirmesi aynı bölüşümü verir; bu yüzden 16 atama beş bölüşüme ayrılır.

Atama sayıları şöyle bulunur. {2, 1} | {2, 1} için 2'lik işlerden biri (2 yol) ve 1'lik işlerden biri (2 yol) M1'e gider: 2 · 2 = 4. {2, 2} | {1, 1} için büyükler ya M1'de ya M2'de: 2. Toplam 4 + 4 + 2 + 4 + 2 = 16 ✓.

Dengesiz bölüşümlerin her birinde kaçan bir iş vardır. {2, 1, 1} | {2}'de M1'deki 1'lik iş M2'ye geçerse 2 + 1 = 3 < 4 bekler. {2, 2, 1} | {1}'de 2'lik iş geçerse 1 + 2 = 3 < 5. Hepsi tek makinede ise herhangi bir iş boş makineye geçerek kazanır. Dengeler en büyük yükü 3 ve 4 olanlardır: PoA = 4/3 (en kötü denge), PoS = 1 (en iyi denge = optimum).

En iyi tepki dinamiği. Oyuncuların sırayla kârlı geçiş yaptığı sürece en iyi tepki dinamiği (best-response dynamics) denir. Bu oyunda dinamik her zaman bir dengede durur, çünkü her kârlı geçiş sıralanmış yük listesini küçültür (9.4.1). Ama varılan denge başlangıca ve hamle sırasına bağlıdır. Örnek 9.11'deki sıra (3, 3)'e vardı; başta büyük işler M1'de, küçükler M2'deyse süreç hiç başlamaz ve (4, 2)'de kalır.

9.4.5Kod izleme: poa_pos()

Tablo elle kuruldu; aynı işi bütün atamaları tarayan bir fonksiyon yapar. Fonksiyon, nash_mi'yi her atama için çağırır.

from itertools import product
def poa_pos(boy, m):
  opt, dengeler = float("inf"), []
  for atama in product(range(m), repeat=len(boy)):
    yuk = [0] * m
    for j, k in enumerate(atama):
      yuk[k] += boy[j]
    opt = min(opt, max(yuk))
    if nash_mi(boy, atama, m):       # denge testi
      dengeler.append(max(yuk))
  return max(dengeler) / opt, min(dengeler) / opt
r = poa_pos([2, 2, 1, 1], 2)
print(round(r[0], 3), r[1])

• product(range(m), repeat=len(boy)), her işe bir makine indisi veren bütün demetleri sırayla üretir: (0, 0, 0, 0), (0, 0, 0, 1), …, (1, 1, 1, 1). Dört iş ve iki makinede 16 demet vardır.
• Her demet için yükler hesaplanır ve opt, şimdiye kadar görülen en küçük en büyük yük olarak güncellenir. float("inf") sonsuz büyük bir başlangıç değeridir; ilk karşılaştırmada mutlaka yerini gerçek bir sayıya bırakır.
• Atama dengeyse en büyük yükü dengeler listesine eklenir.
• Sonunda en kötü dengenin ve en iyi dengenin optimuma oranı döndürülür: (PoA, PoS).

Tarama bitince dengeler = [4, 3, 3, 3, 3, 4] ve opt = 3'tür. Fonksiyon (4/3, 3/3) = (1.333…, 1.0) döndürür; son satır bunu 1.333 1.0 olarak yazar. Yöntemin bedeli yüksektir: n iş ve m makinede mⁿ atama vardır. 30 iş ve 2 makinede bu sayı bir milyarı aşar. Kaba kuvvet küçük örnekleri doğrulamak için iyidir; büyük oyunlarda PoA'yı analizle sınırlamak gerekir.

9.4.6Genel sonuç: 2 − 2/(m + 1)

{2, 2, 1, 1} örneğinde PoA 4/3 çıktı. Bu, iki makine için olabilecek en kötü değerdir. Genel sonuç şudur (Finn ve Horowitz, 1979; Koutsoupias ve Papadimitriou, 1999):

Değerler: m = 1 için 1 (tek makinede seçim yoktur), m = 2 için 4/3, m = 3 için 3/2, m = 9 için 1,8. m büyüdükçe oran 2'ye yaklaşır ama hiçbir zaman 2'ye ulaşmaz. Bencil iş dağılımı, makine sayısı ne olursa olsun, en iyi dağılımın iki katından kötü olamaz.

Sınırın neden 2'nin altında kaldığı kısa bir akıl yürütmeyle görülür. Bir dengede en yüklü makinenin yükü L olsun. O makinede tek iş varsa L bu işin boyudur ve optimum da bu işi bir makineye koymak zorundadır; oran 1'dir. Birden çok iş varsa oradaki en küçük işin boyu w olsun. Dengede bu iş başka bir makineye geçmek istemez: her makine h için yük(h) + w ≥ L, yani her makinenin yükü en az L − w'dir. Toplam iş miktarı bu yüzden en az L + (m − 1)(L − w)'dir. Optimum, toplam işin makine sayısına bölümünden (ortalama yükten) küçük olamaz: OPT ≥ L − w(m − 1)/m. Ayrıca en yüklü makinede en az iki iş ve en küçüğü w olduğundan w ≤ L/2'dir. İkinci bilgi birinciye konunca OPT ≥ L − (L/2)(m − 1)/m = L · (m + 1)/(2m) çıkar. İki yan düzenlenince L / OPT ≤ 2m/(m + 1) = 2 − 2/(m + 1) elde edilir. Örnek 9.13 bu sınıra ulaşıldığını, yani sınırın sıkı olduğunu gösterir.

Karışık dengeler. İşler makineyi olasılıkla seçebilirse (karışık strateji) durum değişir. Bu durumda sosyal maliyet olarak beklenen en büyük yük kullanılır ve PoA artık sabit bir sayıyla sınırlanamaz: m ile çok yavaş ama sınırsız büyür. Büyüme hızı log m / log log m düzeyindedir (Koutsoupias vd., 2003; Czumaj ve Vöcking, 2002). Bu, “toplar ve kutular” problemine benzer: m top m kutuya rastgele atılınca en dolu kutuda beklenenden fazla top birikir. Rastgelelik, dengede bile şanssız çakışmalara yol açar.

9.4.7Farklı hızlı (ilişkili) makineler

Gerçek sunucular aynı hızda değildir. İlişkili makineler (related machines) modelinde makine i'nin hızı s_i'dir ve bir işin bitiş süresi, makinesinin toplam yükünün s_i'ye bölümüdür. Hızlı makine aynı yükü daha kısa sürede bitirir. Bu modelde de saf Nash dengesi her zaman vardır (aynı “sıralı liste küçülür” fikri bitiş süreleriyle çalışır).

Oran 2'dir ve bu, özdeş üç makinenin sınırı 2 − 2/4 = 1,5'ten büyüktür. Özdeş makinelerde saf dengenin kaybı hep 2 katın altında kalır. Hızlar farklıysa kayıp, makine sayısı arttıkça (çok yavaş da olsa) sınırsız büyür; büyüme log m / log log m düzeyindedir (Czumaj ve Vöcking, 2002). Yük Dengeleme oyununun 2. ve 3. seviyeleri bu modeli kullanır.

9.4.8Oyuna dönüş: toplam bitiş süresi

Bölümün başındaki Yük Dengeleme oyununun ölçüsü farklıdır. Oyunda sosyal maliyet en büyük yük değil, bütün işlerin bitiş sürelerinin toplamıdır. Seviye 2'de (CPU Scheduling) boyu 1 olan 7 iş vardır ve sunucu hızları A = 2, B = 1, C = 1'dir. Bir sunucuda L iş varsa her biri L / s sürede biter; o sunucunun toplama katkısı L · L / s'dir.

Bencil yerleşim nereye varır? Oyunda işler sırayla gelir. Her iş, geldiği anda kendi bitiş süresi en kısa olacak sunucuyu seçerse (eşitlikte alfabede önce gelen) ne olur? Tablo 9.12 bu süreci adım adım izler.

Sıra A, A, B, C, A, A, B olur ve sonuç tam olarak en kötü dengelerden biri olan (4, 2, 1)'dir. Oyundaki bencil denge gösterimi (Selfish equilibrium) bu açgözlü yerleşimle kurulur. Açgözlü yerleşim her adımda yeni iş için en iyisini seçer, ama sonradan gelen işlerin etkisini öngöremez; 6. işin A'ya gitmesi, 7. iş için A'yı pahalı hâle getirir.

Seviye 1'de (6 iş, özdeş üç sunucu) tek denge (2, 2, 2)'dir ve bu optimumdur: PoA = 1. Kayıp, sunucular farklılaşınca ortaya çıkar. Son olarak bir karşılaştırma: {2, 2, 1, 1} örneğindeki 4/3 en büyük yükü ölçer, oyun ise toplam süreyi ölçer. PoA'nın değeri ölçülen sosyal maliyete bağlıdır; “bu oyunun PoA'sı” denirken hangi maliyetin kastedildiği her zaman belirtilmelidir.

9.4.9Yük dengelemede sık hatalar

9.5İstikrarın Bedeli

Şimdiye kadarki örneklerin çoğunda PoA ile PoS aynıydı ya da PoS 1'di. Bu kesimde iki oranın çok farklı olabildiği bir oyun ailesi incelenir: oyuncuların bağlantı kiralayıp bedeli kullananlar arasında eşit böldüğü ağ tasarımı oyunları. Bu oyunlarda en kötü denge çok kötü olabilir, ama her zaman iyi bir denge de vardır. İyi dengenin ne kadar iyi olduğunu gösteren araç, potansiyel fonksiyonudur.

9.5.1Aynı oyunda PoA ≠ PoS

Bu oyunda tıkanıklığın tersi bir etki vardır: bir bağlantıyı ne kadar çok kişi kullanırsa kişi başı bedel o kadar düşer. Oyuncular birbirini itmez, çeker. Bu yüzden oyuncuların aynı bağlantıda toplanması iyidir; sorun hangi bağlantıda toplanacaklarıdır.

Şekil 9.13 ile Şekil 9.14 aynı oyunun iki dengesidir. Kötü dengede herkes birlikte A'ya geçse herkes kazanırdı (1,5 yerine 0,5 TL). Ama tek başına geçen 2 TL öder ve kaybeder. Sorun bir koordinasyon sorunudur: oyuncuların hepsi aynı anda hareket edebilse kayıp ortadan kalkar. PoS, bu iyimser senaryonun ölçüsüdür. Biri oyunculara “hepiniz A'yı kullanın” derse ve bu öneri bir denge olduğu için kimse ondan sapmak istemezse kayıp yoktur. PoA ise öneri yapılmazsa ne kadar kaybedilebileceğini söyler.

PoA ne kadar büyük olabilir? Aynı yapı daha uç sayılarla kurulabilir. n oyuncu, bedeli 1 olan bir bağlantı ve bedeli n olan bir bağlantı olsun. Herkes pahalı bağlantıdaysa her biri n/n = 1 öder. Ucuz bağlantıya tek başına geçen de 1 öderdi; geçiş kârlı değildir. Bu profil bir dengedir ve toplam maliyeti n'dir; optimum 1'dir. Demek ki adil paylaşım oyunlarında PoA n kadar büyük olabilir. Oyuncu sayısı arttıkça en kötü denge sınırsız kötüleşir.

9.5.2Adım adım: H_n örneği

PoA kötü olabildiğine göre soru PoS'a döner: en iyi denge her zaman optimuma yakın mıdır? Cevap “evet, ama tam değil”dir. Aşağıdaki örnek, en iyi dengenin bile optimumdan belirli bir oranda kötü olmak zorunda kaldığını gösterir. Örnekte harmonik sayı (harmonic number) ortaya çıkar:

H_n = 1 + 1/2 + 1/3 + … + 1/n

Örneğin H₁ = 1, H₂ = 3/2, H₃ = 11/6 ≈ 1,83, H₄ = 25/12 ≈ 2,08'dir. H_n çok yavaş büyür ve yaklaşık ln n'dir; H₁₀₀ ≈ 5,19'dur.

Kurulum. 4 oyuncu vardır ve her biri t'ye iki yoldan biriyle gider: yalnız kendisinin kullandığı, bedeli 1/i olan yol (oyuncu 1 için 1, oyuncu 2 için 1/2, oyuncu 3 için 1/3, oyuncu 4 için 1/4) ya da herkesin ortak kullanabildiği, bedeli 1 + ε = 1,1 olan yol. Burada ε küçük bir ek bedeldir (0,1). Ortak yolun bedeli kullananlarca eşit bölünür.

Optimum. Herkes ortak yolu kullanırsa toplam 1,1'dir. Herkes kendi yolunu kullanırsa toplam 1 + 1/2 + 1/3 + 1/4 = 25/12 ≈ 2,083'tür. Karışık seçimler de denenebilir, ama ortak yol kullanılıyorsa bedeli bir kez ödenir ve kendi yollarını ekleyenler toplamı yalnızca artırır. Optimum herkesin ortak yolda olduğu durumdur: toplam 1,1, kişi başı 0,275.

Örnekteki çözülme bir zincir tepkimedir. Ortak yoldan en ucuz alternatifi olan oyuncu ayrılır; bu, kalanların payını artırır ve bir sonrakini ayrılmaya iter. ε sıfıra yaklaşırken n oyunculu aynı yapıda PoS H_n = 1 + 1/2 + … + 1/n'ye yaklaşır: optimum 1'e, tek denge H_n'ye gider. Dört oyuncuda bu sınır 25/12 ≈ 2,08'dir; ε = 0,1 ile 1,894 bulduk.

9.5.3Rosenthal potansiyeli

H_n örneği PoS'un en az H_n'ye yaklaşabildiğini gösterdi. Bunun bir üst sınır olduğunu, yani hiçbir adil paylaşım oyununda PoS'un H_n'yi aşmadığını göstermek için bir yardımcı fonksiyon gerekir.

Gösterim. c_e: e bağlantısının bedeli; n_e: e'yi kullanan oyuncu sayısı (her biri c_e/n_e öder). H(k) = 1 + 1/2 + … + 1/k ve H(0) = 0; H_n = H(n). Toplam maliyet C(s): kullanılan bağlantıların bedelleri toplamı.

Tanım bir hayalî sayımdan gelir. Oyuncular bir bağlantıya tek tek eklenmiş gibi düşünülür: 1. kişi tek başına olduğu için c_e yazar, 2. kişi c_e/2, …, k'ıncı kişi c_e/k yazar. Bu sayıların toplamı c_e · (1 + 1/2 + … + 1/k) = c_e · H(k)'dir. Her kişi “geldiği andaki” payını yazmıştır; potansiyel bu payların bütün bağlantılar üzerinden toplamıdır.

Potansiyelin anahtar özelliği. Bir oyuncu yolunu değiştirdiğinde, kendi maliyetindeki değişim potansiyeldeki değişime tam olarak eşittir. Nedeni şudur: oyuncu bir e bağlantısından ayrılınca o bağlantının sayısı n_e'den n_e − 1'e iner ve potansiyelden tam olarak c_e/n_e düşer (toplamın son terimi), bu da oyuncunun orada ödediği paydır. Oyuncu yeni bir e′ bağlantısına katılınca o bağlantının sayısı bir artar ve potansiyele c_e′/(n_e′ + 1) eklenir; bu da oyuncunun orada ödeyeceği yeni paydır. Bu yüzden sapan oyuncu kazanıyorsa (maliyeti düşüyorsa) potansiyel de aynı miktarda düşer. Böyle bir fonksiyonu olan oyunlara potansiyel oyun (potential game) denir.

9.5.4PoS ≤ H_n: optimumdan bir dengeye yürümek

H_n örneğinde zincirin sayıları şöyledir: C(s) ≈ 2,08, Φ(s) ≈ 2,08, Φ(OPT) ≈ 2,29, H₄ · C(OPT) = 25/12 · 1,1 ≈ 2,29. Yani 2,08 ≤ 2,08 ≤ 2,29 ≤ 2,29. Birinci ve üçüncü eşitsizlikler eşitlikle sağlanır; örneğin sınırı neredeyse tam kullanması bu yüzdendir.

İspatın gücü, hangi dengeye varılacağını bilmeye gerek duymamasıdır. Yalnız “potansiyel düşer” bilgisi yeter. Aynı yöntem PoA için çalışmaz: en kötü denge, optimumdan dinamikle ulaşılamayan bir yerde olabilir ve potansiyeli optimumunkinden büyük olabilir. Nitekim bu oyunlarda PoA n'ye kadar çıkabilirken PoS en çok H_n ≈ ln n'dir. 100 oyuncuda bu fark 100'e karşı yaklaşık 5,19'dur.

9.5.5İstikrarın Bedeli'nde sık hatalar

9.6PoA'yı azaltma

PoA'yı ölçmek ilk adımdır; ikinci adım onu küçültmektir. Kayıp dışsallıktan geliyorsa çözüm, dışsallığı oyuncunun kendi hesabına sokmaktır. Bu kesimde en doğrudan araç olan tıkanıklık ücreti iki ağda adım adım incelenir, ardından diğer araçlar özetlenir.

9.6.1Tıkanıklık ücreti dengeyi kaydırır

9.2.6'daki iki yollu ağ ele alınır: ℓ₁ = 5 + x₁/100, ℓ₂ = 20 + x₂/200, toplam 3.000 araç. Ücret yokken denge x₁ = 2.000, toplam 75.000 araç·dk; optimum x₁ = 1.500, toplam 71.250 araç·dk'dır.

Şimdi Yol 1'e bir tıkanıklık ücreti (congestion toll) τ konur. Hesabı basit tutmak için ücret, sürücü için dakika cinsinden bir ek maliyet sayılır: τ = 2,5, sürücünün gözünde 2,5 dakikalık ek gecikmeyle aynıdır. Sürücü artık Yol 1'de ℓ₁ + τ görür ve dengede ℓ₁ + τ = ℓ₂ olur:

1. 5 + τ + x₁/100 = 20 + (3.000 − x₁)/200.
2. İki yan 200 ile çarpılır: 1.000 + 200τ + 2x₁ = 7.000 − x₁.
3. 3x₁ = 6.000 − 200τ ⇒ x₁ = (6.000 − 200τ)/3.

Şekil 9.17'de ücretin etkisi iki biçimde görülür. Soldaki grafikte Yol 1'in eğrisi τ kadar yukarı kayar ve iki eğrinin kesişimi (denge) sola gider: daha az sürücü Yol 1'i seçer. Sağdaki çubuklar toplam gecikmeyi gösterir. Ücret arttıkça bazı sürücüler geniş Yol 2'ye geçer ve toplam düşer.

τ = 7,5'te optimum bir denge olur. x₁ = (6.000 − 1.500)/3 = 1.500, tam optimumun dağılımıdır. 7,5 sayısı rastgele değildir. Marjinal maliyet ücreti her yola o yoldaki dışsallığı koyar: Yol 1'e x₁ · ℓ₁′ = 1.500 · 1/100 = 15 dk, Yol 2'ye x₂ · ℓ₂′ = 1.500 · 1/200 = 7,5 dk. Bu iki ücret konursa sürücü Yol 1'de 20 + 15 = 35, Yol 2'de 27,5 + 7,5 = 35 görür; eşittir, yani optimum dengedir. Ama sürücünün kararını yalnız iki yol arasındaki fark etkiler: 15 − 7,5 = 7,5. Bu yüzden yalnız Yol 1'e konan 7,5 dk'lık ücret aynı sonucu verir.

Ücret bir transferdir. Ücret sürücüden toplanıp başka bir yere (belediyeye, yol yapımına) gider; kimsenin süresini uzatmaz. Bu yüzden tablodaki toplam gecikmeye eklenmez. Ama sürücülerin gözünden durum farklıdır: τ = 7,5'te Yol 1'deki 1.500 sürücü toplam 1.500 · 7,5 = 11.250 dk'lık ücret öder. Sürücülerin “gecikme + ücret” toplamı 71.250 + 11.250 = 82.500'dür ve ücretsiz dengedeki 75.000'den büyüktür. Toplanan gelir sürücülere geri dağıtılmazsa sürücüler bir bütün olarak kaybeder; kazanç topluma (gelirin kullanıldığı yere) geçer.

Fazla ücret aşırıya kaçar. τ = 10'da x₁ ≈ 1.333'e iner ve Yol 2 gereğinden fazla dolar; toplam gecikme yine yaklaşık 71.667'ye çıkar. Doğru ücret, dışsallığa eşit olandır; “ne kadar çok o kadar iyi” değildir.

9.6.2Marjinal maliyet ücreti Pigou'yu düzeltir

Pigou ağında amaç, optimumu (x = 1/2) bir denge yapmaktır. Ücretsizken herkes üst yoldadır ve toplam gecikme 1'dir.

Sabit ücret de yeter. Ücretin trafikle değişmesi gerekmez. Üst yola sabit τ = 1/2 konursa sürücü üstte x + 1/2 görür; denge x + 1/2 = 1 ⇒ x = 1/2. Sabit ücretin doğru değeri, optimumdaki marjinal maliyet ücretinin değeridir. Bu sonuç genelleşir:

Ücretin adı da Pigou'dan gelir: dışsallığı fiyatlandıran vergiye Pigou vergisi denir. Uygulamada zorluk ücretin hesaplanmasında değil, dışsallığın ölçülmesindedir: gecikme fonksiyonlarını ve trafiği bilmek gerekir.

9.6.3PoA'yı azaltmanın diğer yolları

Ücret tek araç değildir. Literatürde ve uygulamada kullanılan başlıca araçlar şunlardır:

Tıkanıklık fiyatlandırması

Kullanıcıların başkalarına yüklediği dışsal maliyeti karara dahil eder. Londra (2003), Stockholm (2006'da deneme, 2007'den beri kalıcı) ve Singapur (1975'ten beri) şehir merkezlerine girişi ücretlendirir.

Merkezi (Stackelberg) yönlendirme

Trafiğin bir kısmını bir merkez yönlendirir, gerisi bencil seçer. Merkez önce hareket eder, bencil kullanıcılar onun seçimini görerek tepki verir; bu “önce lider, sonra izleyiciler” yapısı Stackelberg oyunlarından adını alır. Kontrol edilen pay arttıkça oran 1'e yaklaşır (Roughgarden, 2004).

Kapasite planlama

Roughgarden ve Tardos şunu da gösterdi: r birim trafiğin bencil dengesi, 2r birim trafiğin en iyi yönlendirilmesinden daha pahalı değildir. Sonuç doğrusal olmayanlar dahil her artan gecikme için geçerlidir. Başka bir okuyuşla, her bağlantıyı iki kat hızlandırmak koordinasyonun yerini tutar: kapasiteyi artırmak ücretin yerini tutabilir.

Rota önerisi ve bilgi

Navigasyon uygulamalarının önerileri dengeyi daha düşük toplam maliyete yönlendirebilir; ama uyum gönüllüdür. Öneri bir dengeyse (kimse sapmak istemiyorsa) uyum kendiliğinden olur.

Mekanizma tasarımı

Kuralları, iyi sonuç tek denge olacak biçimde kurmak. Örneğin A/B bağlantı oyununda B'nin kiralanmasını yasaklamak ya da A'ya katılana küçük bir indirim vermek kötü dengeyi ortadan kaldırır.

Maliyeti hesaba katmak

Müdahalenin bilgi, uygulama ve adalet maliyetleri, elde edilen verimlilik kazancıyla birlikte değerlendirilmelidir. %5'lik bir kaybı gidermek için kurulan ücret sistemi kendisi %5'ten pahalıysa anlamsızdır.

9.6.4Gerçek hayat ve tartışma

Trafik ağlarında ücretli şeritler, internette ağlar arası rota seçimi, enerji şebekesinde zamana bağlı tarifeler: üçünde de soru aynıdır. Bencil denge ne kadar kötü, hangi müdahale onu optimuma yaklaştırır? İnternette her ağ işletmecisi trafiği kendi maliyetine göre yönlendirir; bu, bencil yönlendirmenin büyük ölçekli bir örneğidir. Enerji şebekesinde tüketiciler elektriği en ucuz saatte kullanır; zamana bağlı tarife, şebekenin yoğun saatlerdeki dışsallığını fiyata yansıtır.

Bu bölümün kavramları birkaç tartışma sorusuyla pekişir:

• Bireysel çıkarlar neden her zaman sosyal optimuma ulaşmaz? Pigou örneğinde hangi dışsallık var? Pigou'da üst yola giren sürücü oradaki herkesi ℓ′ = 1 oranında yavaşlatır; bu ek gecikme (x · ℓ′ = x) onun hesabında yoktur. Optimumun kendisi de kararlı değildir: alttakiler üste geçmek ister.
• PoA'yı azaltmak için hangi teşvikler uygulanabilir? Hangisi daha adil? Ücret verimli ama gerileyici olabilir: aynı ücret düşük gelirli sürücüye daha ağır gelir. Bonus (alt yolu kullanana ödeme) aynı dağılımı sağlayabilir, ama bir bütçe gerektirir. Merkezi yönlendirme bazılarını uzun yola “zorlar”. Adalet tartışması, verimlilik kazancının kimin cebine gittiği sorusuna dayanır.
• Braess paradoksu günlük hayatta nerede görülebilir? Bir yolu kapatmak ne zaman mantıklıdır? Yeni bir bağlantının herkesi aynı darboğaza yönlendirdiği her ağda görülebilir. Seul'de Cheonggyecheon üzerindeki otoyolun 2003'te başlayan yıkımından sonra kent trafiğinin beklendiği kadar kötüleşmemesi sık anılan bir örnektir. Bir yolu kapatmak, dengeyi optimuma yaklaştırıyorsa mantıklıdır; bunu anlamak için denge ve optimum birlikte hesaplanmalıdır.

9.6.5Ücretlendirmede sık hatalar

9.7Çözümlü problemler

Bu kesimdeki problemler bölümün bütün yöntemlerini bir arada kullanır: Pigou tipi ağlarda türevle optimum, yük dengelemede sapma denetimi, Braess ağında denge, H_n örneği, pürüzsüzlük ve kod izleme. Her çözüm ara adımlarıyla verilir.

9.7.1Örnek problemler

9.7.2İzlemeler ve yeni konular

Pürüzsüzlükle ilgili iki alıştırma, (1, ½)-pürüzsüz oyunun sınırı (2) ve (y, z) = (2, 3) için anahtar eşitsizliğin denetimi (8 ≤ 29/3), Örnek 9.8 ve Örnek 9.9'da çözülmüştür.

9.8Özet

• Anarşinin Bedeli en kötü Nash dengesinin maliyetini sosyal optimumun maliyetine böler: PoA = max_s∈NE C(s) / C(OPT). İstikrarın Bedeli aynı oranı en iyi denge için yazar. Her zaman 1 ≤ PoS ≤ PoA; tek denge varsa ikisi eşittir. Fayda problemlerinde oran ters çevrilir.
• PoA, hangi dengeye varılacağını bilmeden verilen kötümser bir garantidir. Yaklaşım oranının oyun kuramındaki karşılığıdır: yaklaşım oranında hesaplama gücü, PoA'da koordinasyon eksiktir.
• Pigou ağında (üst yol x, alt yol 1) denge herkesi üste yollar ve maliyeti 1'dir; optimum trafiği yarıya böler ve maliyeti 3/4'tür: PoA = 4/3.
• Dengede yolların gecikmeleri, optimumda marjinal maliyetleri (ℓ + f · ℓ′) eşitlenir. Aradaki f · ℓ′ terimi, bir sürücünün ötekilere yüklediği dışsallıktır.
• Gecikme x^p gibi dikleşince PoA sınırsız büyür (p = 16'da ≈ 4,73). Doğrusal gecikmede her ağda ve her talepte PoA ≤ 4/3'tür (Roughgarden–Tardos); ispat denge koşulu, kenar eşitsizliği ve toplamadan oluşur; sınır Pigou'da sıkıdır.
• (λ, μ)-pürüzsüz oyunlarda PoA ≤ λ/(1 − μ); bölünebilir doğrusal trafik (1, ¼) ile 4/3, atomik doğrusal tıkanıklık oyunları (5/3, 1/3) ile 5/2 verir. Sınır karışık dengelere de taşınır (sağlam PoA).
• Braess ağında (4.000 araç) denge 320.000, aynı ağın optimumu 258.750 araç·dk'dır: PoA ≈ 1,237. 80/65 Braess kaybıdır, PoA değildir.
• Yük dengeleme oyununda saf denge her zaman vardır. {2, 2, 1, 1} örneğinde PoA = 4/3, PoS = 1; m özdeş makinede sıkı değer 2 − 2/(m + 1)'dir. Farklı hızlı makinelerde ve karışık dengelerde oran m ile yavaşça büyür. PoA'nın değeri ölçülen sosyal maliyete bağlıdır.
• Adil maliyet paylaşımında PoA n'ye kadar çıkabilir, ama Rosenthal potansiyeli Φ = Σ c_e H(n_e) sayesinde PoS ≤ H_n ≈ ln n'dir; H_n örneği sınırın sıkı olduğunu gösterir.
• Marjinal maliyet ücreti τ_e = f_e · ℓ_e′(f_e) optimumu denge yapar (Pigou'da τ = x ya da sabit 1/2; iki yollu ağda Yol 1'e 7,5 dk). Ücret bir transferdir; fazla ücret yeniden kayıp yaratır. Stackelberg yönlendirme, kapasite artırımı, bilgi ve mekanizma tasarımı diğer araçlardır.

9.9Kavram listesi

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

• Anarşinin Bedeli Price of Anarchy (PoA)
• İstikrarın Bedeli Price of Stability (PoS)
• koordinasyon oranı coordination ratio
• en kötü denge worst-case equilibrium
• sosyal optimum social optimum
• sosyal maliyet social cost
• verimlilik kaybı efficiency loss
• yaklaşım oranı approximation ratio
• sıkı sınır tight bound
• Pigou ağı Pigou network
• gecikme fonksiyonu latency function
• bölünebilir (atomik olmayan) nonatomic
• atomik atomic
• Wardrop dengesi Wardrop equilibrium
• sistem optimumu system optimum
• bencil yönlendirme selfish routing
• marjinal maliyet marginal cost
• dışsallık externality
• tıkanıklık oyunu congestion game
• pürüzsüzlük, (λ, μ)-pürüzsüz oyun smoothness
• sağlam PoA robust Price of Anarchy
• Braess paradoksu Braess's paradox
• yük dengeleme load balancing
• en büyük yük makespan
• ilişkili (farklı hızlı) makineler related machines
• en iyi tepki dinamiği best-response dynamics
• adil maliyet paylaşımı fair cost sharing
• ağ tasarımı network design
• harmonik sayı H_n harmonic number
• potansiyel oyun potential game
• Rosenthal potansiyeli Rosenthal potential
• tıkanıklık ücreti congestion toll
• marjinal maliyet ücreti marginal-cost toll
• tıkanıklık fiyatlandırması congestion pricing
• Pigou vergisi Pigouvian tax
• Stackelberg yönlendirme Stackelberg routing
• kapasite artırımı capacity augmentation

9.10Kendini Dene

1. 1 birim trafik iki paralel yol arasında bölünür: Yol 1'in gecikmesi ℓ₁(x) = x, Yol 2'ninki ℓ₂(x) = x + 1/2. Wardrop dengesi, sosyal optimum ve PoA nedir?

   Cevap

   Denge: gecikmeler eşit, x₁ = (1 − x₁) + 1/2 ⇒ x₁ = 3/4, x₂ = 1/4; herkes 3/4 bekler, C = 3/4. Optimum: marjinal maliyetler eşit, 2x₁ = 2x₂ + 1/2 ve x₁ + x₂ = 1 ⇒ x₁ = 5/8, x₂ = 3/8. C = (5/8)² + (3/8)(3/8 + 1/2) = 25/64 + 21/64 = 23/32. PoA = (3/4)/(23/32) = 24/23 ≈ 1,043, 4/3'ün çok altında.

2. Pigou ağında (üst yol x, alt yol 1; burada x üst yoldaki trafik miktarıdır) toplam trafik r = 1/2 ve r = 2 olsun. Her iki durumda PoA nedir?

   Cevap

   r = 1/2: üst yolun gecikmesi en çok 1/2'dir, herkes üsttedir; C = 1/2 · 1/2 = 1/4. Optimum C(x) = x² + (1/2 − x), türev 2x − 1 aralıkta hep ≤ 0 olduğundan en küçük değer x = 1/2'de: yine 1/4. PoA = 1; az trafikte dışsallık önemsizdir. r = 2: denge üst yolda 1 birim (gecikme 1), altta 1 birim; C = 1 + 1 = 2. Optimum C(x) = x² + 2 − x, x = 1/2, C = 7/4. PoA = 8/7 ≈ 1,143.

3. Kenar eşitsizliği ℓ(f) · f^OPT ≤ ℓ(f^OPT) · f^OPT + ¼ · ℓ(f) · f için ℓ(x) = x ve f = 1 alınsın. f^OPT = 1/4 için iki yan nedir? Hangi f^OPT değerinde eşitlik olur?

   Cevap

   Sol 1 · 1/4 = 1/4; sağ 1/16 + 1/4 = 5/16. 1/4 ≤ 5/16 ✓; fark (1/4 − 1/2)² = 1/16. Fark her zaman (f^OPT − f/2)²'dir; eşitlik yalnız f^OPT = f/2 = 1/2'de olur. Pigou ağı tam bu noktayı kullanır.

4. Bir oyunun (2, 1/3)-pürüzsüz olduğu biliniyor. PoA için hangi sınır çıkar? Aynı oyun (1, 1)-pürüzsüz olsaydı bu bilgi işe yarar mıydı?

   Cevap

   PoA ≤ 2/(1 − 1/3) = 2/(2/3) = 3. (1, 1) tanımda izin verilen bir çift değildir (μ < 1 gerekir). İspatın 4. adımında (1 − μ) · C(s) ≤ λ · C(OPT) eşitsizliği 0 ≤ C(OPT)'ye döner; bu her zaman doğrudur ve hiçbir sınır vermez.

5. İşler {5, 4, 3, 2}, 2 özdeş makine, sosyal maliyet en büyük yük. Optimum nedir? {5, 4} | {3, 2} bir Nash dengesi midir? PoA ve PoS nedir?

   Cevap

   Toplam 14, en büyük yük en az 7; {5, 2} | {4, 3} = 7 | 7: OPT = 7. {5, 4} | {3, 2}'de yükler 9 ve 5. 5'lik iş geçerse 5 + 5 = 10, 4'lük iş geçerse 5 + 4 = 9 (eşit, kazanmaz) bekler; M2'dekiler geçerse 12 ya da 11. Denge ✓, en büyük yük 9. 16 atamanın taranması dengelerin en büyük yüklerinin 7, 8 ve 9 olduğunu gösterir: PoA = 9/7 ≈ 1,286 ≤ 4/3, PoS = 1 (7 | 7 de denge).

6. 3 oyuncu s'den t'ye bağlantı kiralar: A 1 TL, B 2 TL; bedeli kullananlar eşit böler. Saf dengeler hangileridir? PoA ve PoS kaçtır?

   Cevap

   Hepsi A: kişi başı 1/3; B'ye geçen 2 öder, denge. Hepsi B: kişi başı 2/3; A'ya geçen 1 öder (1 > 2/3), denge. 1 A, 2 B: B'deki 1 öder, A'ya geçerse 1/2; kaçar. 2 A, 1 B: B'deki 2 öder, A'ya geçerse 1/3; kaçar. Dengeler “hepsi A” (toplam 1 = OPT) ve “hepsi B” (toplam 2): PoA = 2, PoS = 1.

7. H_n örneği iki oyuncuyla kurulur: kendi yolları 1 ve 1/2, ortak yol 1,2 (ε = 0,2). Optimum, tek denge ve PoS nedir? Φ(OPT) ile Φ(denge) nasıl ilişkilidir?

   Cevap

   Optimum: ikisi ortakta, toplam 1,2 (diğer seçenekler 1,5, 1,7 ve 2,2). Optimumdan: oyuncu 2 ortakta 0,6 öder, kendi yolu 0,5 < 0,6, ayrılır; oyuncu 1 ortak yolu tek başına 1,2'ye öder, kendi yolu 1 < 1,2, ayrılır. Denge: herkes kendi yolunda, C = 1,5. PoS = 1,5/1,2 = 1,25 ≤ H₂ = 1,5. Potansiyel: Φ(OPT) = 1,2 · H(2) = 1,8, Φ(denge) = 1 + 1/2 = 1,5; dinamik boyunca potansiyel 1,8'den 1,5'e düşmüştür.

8. 2.000 araç iki yol arasında bölünür: ℓ₁ = 10 + x₁/100, ℓ₂ = 15 + x₂/100 (dk). Denge ve optimum toplam gecikmesi nedir? Yol 1'e hangi sabit ücret optimumu denge yapar?

   Cevap

   Denge: 10 + x₁/100 = 15 + (2.000 − x₁)/100 ⇒ x₁ = 1.250, herkes 22,5 dk; toplam 45.000 araç·dk. Optimum: 10 + x₁/50 = 15 + x₂/50 ⇒ x₁ − x₂ = 250, x₁ = 1.125, x₂ = 875; gecikmeler 21,25 ve 23,75; toplam 1.125 · 21,25 + 875 · 23,75 = 44.687,5. PoA ≈ 1,007. Ücret: 21,25 + τ = 23,75 ⇒ τ = 2,5 dk; marjinal ücretlerin farkıyla aynıdır (11,25 − 8,75 = 2,5).

9.11İleri okuma

• T. Roughgarden, Twenty Lectures on Algorithmic Game Theory (2016), Ders 11–15: Pigou ve Braess örneklerinden pürüzsüzlüğe ve ağ tasarımında H_n sınırına kadar bu bölümün bütün konularını kısa ve açık derslerle anlatır.
• N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory (2007), Bölüm 17–20: yük dengeleme, bencil yönlendirme, ağ oluşturma ve İstikrarın Bedeli için kapsamlı başvuru bölümleridir.
• D. Easley ve J. Kleinberg, Networks, Crowds, and Markets (2010), Bölüm 8: trafikte denge ve Braess paradoksunu matematik bilgisi az olan okur için örneklerle anlatır.
• A. R. Karlin ve Y. Peres, Game Theory, Alive (2017), Bölüm 8: Anarşinin Bedeli'ni potansiyel oyunlar ve tıkanıklık oyunlarıyla birlikte öğrenci düzeyinde ispatlarla verir.

9.12Kaynaklar

1. E. Anshelevich vd., “The Price of Stability for Network Design with Fair Cost Allocation”, IEEE FOCS, 2004.
2. B. Awerbuch, Y. Azar, A. Epstein, “The Price of Routing Unsplittable Flow”, ACM STOC, 2005.
3. D. Braess, “Über ein Paradoxon aus der Verkehrsplanung”, Unternehmensforschung 12, 258–268, 1968.
4. G. Christodoulou, E. Koutsoupias, “The Price of Anarchy of Finite Congestion Games”, ACM STOC, 2005.
5. A. Czumaj, B. Vöcking, “Tight Bounds for Worst-Case Equilibria”, ACM-SIAM SODA, 2002.
6. D. Easley, J. Kleinberg, Networks, Crowds, and Markets, Cambridge, 2010 (Bölüm 8: trafik ve Braess).
7. G. Finn, E. Horowitz, “A Linear Time Approximation Algorithm for Multiprocessor Scheduling”, BIT 19, 1979.
8. R. L. Graham, “Bounds for Certain Multiprocessing Anomalies”, Bell System Technical Journal 45(9), 1966.
9. A. R. Karlin, Y. Peres, Game Theory, Alive, AMS, 2017 (Bölüm 8: Anarşinin Bedeli).
10. E. Koutsoupias, M. Mavronicolas, P. Spirakis, “Approximate Equilibria and Ball Fusion”, Theory of Computing Systems 36(6), 2003.
11. E. Koutsoupias, C. Papadimitriou, “Worst-case Equilibria”, STACS, 1999.
12. N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory, Cambridge University Press, 2007 (Bölüm 17–20).
13. C. Papadimitriou, “Algorithms, Games, and the Internet”, ACM STOC, 2001.
14. A. C. Pigou, The Economics of Welfare, Macmillan, 1920.
15. T. Roughgarden, “The Price of Anarchy Is Independent of the Network Topology”, Journal of Computer and System Sciences, 2003.
16. T. Roughgarden, “Stackelberg Scheduling Strategies”, SIAM Journal on Computing 33(2), 2004.
17. T. Roughgarden, “Intrinsic Robustness of the Price of Anarchy”, ACM STOC, 2009.
18. T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016 (Ders 11–15).
19. T. Roughgarden, É. Tardos, “How Bad Is Selfish Routing?”, Journal of the ACM, 2002.
20. J. G. Wardrop, “Some Theoretical Aspects of Road Traffic Research”, Proceedings of the Institution of Civil Engineers 1(3), 325–362, 1952.

Ders sayfası: Roughgarden CS364A (Stanford, 2013), Ders 11–15 notları · © Sercan Külcü. Tüm hakları saklıdır.