Bölüm 14: Gelecek Yönelimler

14.1Giriş

Bu bölüm yeni bir kuram kurmaz; önceki bölümlerde öğrenilen araçları yeni ortamlara taşır. Geriye doğru çıkarım, tekrarlanan oyunlarda tetik stratejisi, teşvik uyumluluğu, gelir maksimizasyonu, ikinci fiyat fikri, oylama kuralları ve anarşinin bedeli burada yeniden karşımıza çıkar. Değişen, oyuncuların ve kuralların doğasıdır. Bu yüzden her başlıkta iki soru birlikte sorulur: dersin aracı bu durumda ne söyler, ve hangi varsayımı artık tutmaz?

Bölüm hızla değişen alanlara değinir. Belirli ürünler, sürümler ve güncel uygulamalar birkaç yıl içinde değişir. Bu yüzden not, örnekleri ürün adlarına değil kalıcı ilkelere bağlar: sabır pazarlık gücüdür, aynı veride seçilen ve ölçülen bir şey başarısını abartır, herkesin gördüğü bir sıralama gücü değer taşır. Bu ilkeler, uygulamanın biçimi değişse de geçerli kalır.

14.1.1Bir oyunla başlangıç: yapay zekâ ajan turnuvası

Bölüm küçük bir turnuvayla açılır. Dört basit ajan seçilen bir oyunu birbirine karşı oynar. Her maç 60 ya da 120 tur sürer. Tam turnuvada her ajan her ajanla bir kez karşılaşır; dört ajan için bu, 4 · 3 / 2 = 6 maç demektir. Sıralama, ajanların bütün maçlarda topladığı kazanca göre yapılır.

Ajanlar şunlardır:

• Rastgele: her turda iki hamleden birini yarı yarıya olasılıkla seçer.
• Hep İşbirliği: her turda işbirliği yapar; rakibe hiç bakmaz.
• Hep İhanet: her turda ihanet eder.
• En İyi Tepki: rakibin şimdiye kadar en sık yaptığı hamleyi gelecek hamle olarak tahmin eder ve ona en iyi tepkiyi verir. Geçmiş yokken, yani ilk turda, işbirliği yapar.

Şekil 14.1'de eşleşmeler görülür. Turnuvanın merak uyandıran iki sorusu vardır. Birincisi, bu dört ajandan hangisi birinci olur? İkincisi, bir oyunda birinci olan ajan başka bir oyunda da birinci olur mu? İlk sorunun cevabı oyunun yapısından hesaplanabilir; ikinci sorunun cevabı ise bölümün ana derslerinden biridir. İki soru da tekrarlanan oyunlar ve en iyi tepki kavramlarına dayanır ve 14.2.7'de sayılarla cevaplanır.

Bu turnuvanın önemi, ajanların “akıllı” olup olmamasından gelmez. Ajanlar çok basittir. Önemli olan, bir ajanın başarısının yalnız kendi kuralına değil rakiplerine ve oynanan oyuna bağlı olmasıdır. Bu, oyun kuramının temel gözlemidir ve yazılım ajanları yaygınlaştıkça daha da önem kazanır.

14.1.2Gelişen bir alan

Algoritmik oyun kuramı, bilgisayar bilimi ile ekonominin kesişiminde doğmuş, uygulamaları hızla artan bir alandır. Endüstride ve akademide otonom araçlar, çevrimiçi platformlar ve enerji ağları gibi alanlarda kullanılır. Bu büyümeyi üç teknolojik eğilim besler:

• Yapay zekâ ve makine öğrenmesi: karar verenlerin bir kısmı artık öğrenen yazılımlardır.
• Büyük veri ve gerçek zamanlı karar: fiyatlar, teklifler ve rotalar saniyeler içinde güncellenir.
• Blokzincir ve akıllı sözleşmeler: kurallar herkese açık kodla otomatik uygulanır.

Bu eğilimlerden dört araştırma ekseni doğar. Her biri dersin bir bölümüyle doğrudan ilgilidir.

Bu bölümün amacı, dersin araçlarının bu yeni alanlarda nasıl kullanıldığını ve nerede yetersiz kaldığını göstermektir. Yetersizlik de öğreticidir. Örneğin klasik mekanizma tasarımı, tasarımcının ilan ettiği kurala sonradan bağlı kalacağını varsayar. Akıllı sözleşmeler bu varsayımı kodla sağlar ama yeni bir sorun yaratır: bekleyen işlemler herkese görünür ve bu görünürlük istismar edilebilir. Benzer biçimde klasik kuram oyuncuların rasyonel olduğunu varsayar. Dil modeli tabanlı ajanlar ise sorunun nasıl çerçevelendiğine duyarlı olabilir ve bu varsayımdan sapabilir.

14.1.3Uygulama alanları

Oyun kuramının bugün en çok kullanıldığı dört alan şöyle özetlenebilir.

Finans

Algoritmik ticaret ve portföy yönetimi. Alım-satım algoritmaları birbirine karşı oynar: bir algoritmanın kârı, ötekilerin emirlerine ve hızına bağlıdır. Bu, tek kişilik bir optimizasyon değil bir oyundur.

Trafik ve lojistik

Otonom araç ağları ve rota seçimi. Her araç kendi süresini kısaltmak ister; bu bencil yönlendirme, ağa yol eklemenin herkesi yavaşlattığı Braess paradoksu gibi sonuçlar doğurabilir.

Çevrimiçi platformlar

Öneri sistemleri, reklam açık artırmaları ve sosyal ağ analizi. Arama sonuçlarının yanındaki reklam yuvaları, her arama için ayrı bir açık artırmayla satılır.

Enerji şebekeleri

Yük dengeleme, talep yanıtı ve elektrik piyasaları. Tüketiciler fiyat sinyaline göre tüketimlerini kaydırır; üreticiler piyasaya teklif verir.

Bu alanların ortak noktası, karar verenlerin giderek daha çok yazılım olmasıdır. Bir alım-satım algoritması, bir rota uygulaması ya da bir reklam teklif aracı, sahibinin adına oynayan bir ajandır. Bölümün geri kalanı bu gözlemle başlar.

14.2Yapay zekâ ajanları

Bu kısım, yazılım ajanlarının oyuncu olarak ortaya çıkmasıyla gündeme gelen soruları inceler. İlk alt başlık ajanların yarattığı yeni sorunları sıralar. Ardından iki klasik model yeniden ele alınır: ajanlar arası pazarlık (sonlu ve sonsuz ufuk) ve fiyatlandırma algoritmalarının danışıklılığı. Kısım, giriş turnuvasının sonuçlarıyla kapanır.

14.2.1Stratejik yapay zekâ ajanları

Büyük dil modeli tabanlı ajanlar, kullanıcı adına alışveriş, pazarlık, planlama ve kaynak paylaşımı gibi işleri üstlenebilir. Bu durumda ajan artık yalnızca bir araç değildir; hedefi, bilgisi ve stratejisi olan bir aktördür. Yani oyun kuramı anlamında bir oyuncudur. Oyuncunun ne istediği, ne bildiği ve neyi seçebildiği sorulabilir. Bu da oyun kuramının eski sorularını yeniden gündeme getirir.

Şekil 14.2 tipik yapıyı gösterir. Bir kullanıcı ajan A'yı, bir satıcı ajan B'yi görevlendirir. İki ajan bir mekanizmada, örneğin bir pazarda ya da açık artırmada, karşılaşır. Bu zincirin her halkasında ayrı bir oyun kuramı sorusu vardır.

Bu sorun yapay zekâ ajanlarından çok eskidir. Ev sahibi ile emlakçı, hissedar ile yönetici, hasta ile doktor arasındaki ilişkiler aynı yapıdadır. Örneğin komisyonla çalışan bir emlakçı, evi biraz daha yüksek fiyata satmak için haftalarca uğraşmak istemeyebilir; çünkü fiyattaki artışın küçük bir kısmı kendisine gelir, uğraşın tamamı ise kendisinedir. Yazılım ajanlarında sorun dört biçimde ortaya çıkar.

Hedef uyumu

Ajanın hedefi kullanıcınınkiyle aynı mı? Ajanın hedefi, kullanıcının söylediği sözlerden ya da eğitim verisinden çıkarılır. Kullanıcı “en ucuzunu bul” der ama aslında hızlı teslimatı da önemsiyor olabilir. Ajan söylenen hedefi kelimesi kelimesine izlerse kullanıcının gerçek faydasını kaçırabilir. Bu, asil–vekil sorununun en doğrudan biçimidir.

Rasyonellik varsayımı

Klasik oyun kuramı oyuncuların kazançlarını maksimize ettiğini varsayar. Dil modeli tabanlı bir ajanın davranışı ise sorunun nasıl sunulduğuna, yani çerçevelemeye (framing) duyarlı olabilir. Aynı oyunun iki farklı anlatımında farklı hamle seçebilir. Bu nedenle Nash dengesi tahmini bu ajanlar için her zaman iyi bir tahmin olmayabilir. Davranışsal oyun kuramında insanlar için yapılan gözlemler burada ajanlar için de geçerlidir.

Manipülasyon

Ajan, karşı tarafın yazdığı metni okur. Karşı ajan mesajına gizli talimatlar ekleyerek ajanı kendi lehine yönlendirmeye çalışabilir. Buna istem enjeksiyonu (prompt injection) denir. Oyun kuramı açısından bu, karşı tarafın yalnız hamle seçmekle kalmayıp rakibin karar kuralını da etkileyebildiği yeni bir strateji türüdür.

Kimlik ve sorumluluk

Ajan kimin adına konuşuyor, bir hata olursa kim sorumlu, yapılan bir anlaşma nasıl doğrulanır? Mekanizma tasarımı, oyuncuların kim olduğunun ve bir sözleşmenin uygulanabilir olduğunun bilindiğini varsayar. Bu varsayımlar ajanlar için ayrıca kurulmalıdır.

Bu dört soru bir arada şunu söyler: ajanlar oyun kuramını gereksiz kılmaz, aksine onun sorularını daha önemli hâle getirir. Ajanın hangi oyunu oynadığı, kimin adına oynadığı ve oyunun kurallarının neler olduğu açıkça modellenmelidir. Aşağıdaki iki model, pazarlık ve fiyatlandırma, bu modellemenin somut örnekleridir.

14.2.2Ajanlar arası pazarlık: sonlu ufuk

İki ajanın bir miktarı paylaşması gerektiğini düşünelim. Örneğin bir alıcı ajanı ile satıcı ajanı, bir işlemden doğan 100 TL'lik kazancın nasıl bölüşüleceğini pazarlık eder. Pazarlık sırayla yapılan önerilerle ilerler.

δ = 0,9, her turda değerin %10 azalması demektir. Bunun iki yorumu vardır. Birincisi, gerçekten bir kayıp vardır: örneğin bozulan bir ürün ya da kaçan bir fırsat. İkincisi, oyuncular sabırsızdır: bir tur sonra alınacak 100 TL, bugün alınacak 90 TL kadar değerlidir. İki yorumda da δ büyüdükçe oyuncu daha sabırlıdır.

Oyun sonlu olduğu için geriye doğru çıkarım (backward induction) ile çözülür. Son turdan başlanır ve her turda “öneren, karşı tarafı kabul ile red arasında kayıtsız bırakacak en küçük payı önerir” kuralı uygulanır. Karşı taraf reddederse bir sonraki turda ne alacaksa, bunun bugünkü değeri onun için alt sınırdır.

Şekil 14.3 çözümü sağdan sola okur. İlk bakışta şaşırtıcı bir sonuç vardır: A ilk öneriyi yaptığı hâlde payın yalnızca %18,1'ini alır. Nedeni son söz hakkının B'de olmasıdır. Tur 4'te B her şeyi alabilir ve bu tehdit geriye doğru bütün turlara yayılır. Her tur geriye gidildiğinde son sözün avantajı δ ile küçülür ama tamamen kaybolmaz.

Aynı hesap farklı tur sayıları için yapılabilir. Hesabı kısaltan bir gözlem vardır. x_T, T turluk oyunda ilk önerenin (A'nın) payı olsun. İlk turda A, karşı tarafı bekleme değeri kadar tatmin etmelidir. B için ikinci turdan başlayan oyun, ilk önerenin kendisi olduğu T − 1 turluk bir oyundur; orada B, x_T−1 payını alır. Bu yüzden:

x₁ = 100,   x_T = 100 − δ · x_T−1

Bu kural tek turluk oyunla başlar: tek tur varsa A her şeyi önerir ve B kabul eder (red ikisine de 0 verir). Kuralı ardışık uygulamak şu tabloyu verir.

Tabloda her değer bir öncekinden hesaplanır. Örneğin x₂ = 100 − 0,9 · 100 = 10, x₃ = 100 − 0,9 · 10 = 91, x₄ = 100 − 0,9 · 91 = 18,1, x₅ = 100 − 0,9 · 18,1 = 83,71. Değerler salınır: tur sayısı tekse son söz A'dadır ve A büyük pay alır; çiftse son söz B'dedir ve A küçük pay alır. T = 1 durumu ültimatom oyunudur: tek bir öneri vardır, karşı taraf ya kabul eder ya da ikisi de 0 alır. Kuramsal tahmin, önerenin hemen hemen her şeyi aldığıdır.

Salınımın genliği tur sayısı arttıkça küçülür ve değerler 52,6 civarına yaklaşır. Bu sınır bir sonraki alt başlıkta türetilir. Ajan tasarımı için iki ders çıkar. Birincisi, sabır (δ'nın büyüklüğü) ve son söz hakkı pazarlık gücüdür. İkincisi, son tarih son teklifin kimde olduğunu belirlediği için ufuk bilgisi de stratejiktir. Bir ajan, pazarlığın ne zaman biteceğini bilmekle ya da bunu belirleyebilmekle güç kazanır.

14.2.3Sonsuz ufuk: Rubinstein çözümü

Pazarlığın bir son turu yoksa geriye doğru çıkarım başlayamaz; başlangıç noktası olan son tur yoktur. Rubinstein (1982), bu durumda da tek bir alt oyun mükemmel denge olduğunu gösterdi. Çözüm durağan stratejilerle (stationary strategies) bulunur. Durağan strateji, geçmişe bakmadan her turda aynı teklifi yapmaktır. A önerirken kendine hep x* payını, B önerirken A'ya hep y* payını bırakır. Payları 1'e (bütün miktara) oranla yazalım.

Dengenin iki koşulu vardır.

1. B, A'nın önerisinde kayıtsızdır. A'nın önerisi B'ye 1 − x* bırakır. B reddederse bir sonraki turda kendisi önerir ve 1 − y* alır; bunun bugünkü değeri δ_B(1 − y*)'dır. A, B'ye tam bu kadar bırakır: 1 − x* = δ_B · (1 − y*).
2. A, B'nin önerisinde kayıtsızdır. B'nin önerisi A'ya y* bırakır. A reddederse bir sonraki turda x* alır; bugünkü değeri δ_A x*'dır. Buradan y* = δ_A · x*.

İkinci denklem birinciye konur: 1 − x* = δ_B(1 − δ_A x*) = δ_B − δ_Aδ_B x*. x* içeren terimler bir tarafa toplanır: x* − δ_Aδ_B x* = 1 − δ_B, yani x*(1 − δ_Aδ_B) = 1 − δ_B. Her iki taraf 1 − δ_Aδ_B'ye bölünür.

Simetrik formül genel formülden şöyle çıkar: 1 − δ² = (1 − δ)(1 + δ) olduğu için (1 − δ)/(1 − δ²) = 1/(1 + δ). δ = 0,9 için 100/1,9 ≈ 52,6 TL bulunur. Bu, Tablo 14.2'deki salınımın yaklaştığı değerdir. Bağlantı açıktır: sonlu ufuktaki x_T = 100 − δ x_T−1 kuralının sabit noktası, yani x = 100 − δx denkleminin çözümü, x = 100/(1 + δ)'dır. Ufuk uzadıkça son turun etkisi her adımda δ ile çarpılarak söner ve pay bu sabit noktaya yaklaşır.

Şekil 14.4 ilk önerenin avantajını gösterir. Sabırsız oyuncular arasında (küçük δ) ilk öneri çok değerlidir; çünkü karşı taraf reddederse bir sonraki turu beklemek ona pahalıya mal olur. Sabır arttıkça bekleme ucuzlar ve ilk öneren avantajı küçülür. Çok sabırlı oyuncular yaklaşık eşit paylaşır.

Sabırlar farklıysa sonuç daha çarpıcıdır. Tablo 14.3, formülün dört örnekte verdiği payları gösterir.

Tablonun son satırı uç bir durumdur: δ_A = 0,99 çok sabırlı bir A'yı temsil eder ve A payın %91,7'sini alır. Ajan tasarımı açısından ders şudur: sabır güçtür. Gerçekten aceleci (düşük δ'lı) bir ajan daha az pay alır. Eksik bilgide durum biraz daha inceliklidir: karşı taraf ajanın gerçek sabrını bilmiyorsa, aceleci görünmek de rakibin inancını değiştirerek benzer bir etki yapar. Bu yüzden bir pazarlık ajanının, kullanıcının son tarihini ya da aciliyetini karşı tarafa sızdırmaması önemlidir.

14.2.4Fiyatlandırma algoritmaları danışabilir mi?

Çevrimiçi satıcıların çoğu fiyatlarını algoritmalarla belirler. Bu algoritmalar birbirinin fiyatını izler ve kendi fiyatını buna göre günceller. Burada rekabet hukukunu ilgilendiren bir soru doğar: birbirleriyle hiç konuşmayan algoritmalar, rakiplerin anlaşarak yaptığı gibi yüksek fiyatta buluşabilir mi?

Model şöyledir. İki firma aynı ürünü satar. İkisi de tekel fiyatını koyarsa toplam kâr 100 olur ve her biri 50 alır. Biri fiyatı biraz kırarsa, Bertrand rekabetinde olduğu gibi ucuz olan bütün pazarı alır: o dönem 100 kazanır, öteki 0. Fiyatlar sonunda maliyete kadar inerse kâr sıfırlanır. Tek dönemlik oyun Mahkûmun İkilemi'dir: karşı taraf ne yaparsa yapsın fiyat kırmak daha kârlıdır, denge ise iki firmaya da 0 bırakır.

Oyun her dönem tekrarlanırsa durum değişir. Firmalar şu stratejiyi kullanabilir:

Bu strateji işbirliğini bir tehditle korur. Sapmak bugün kazandırır ama geleceğin bütün kârlarını yok eder. Sapmanın kârlı olup olmadığı, firmanın geleceğe ne kadar değer verdiğine, yani iskonto faktörü δ'ya bağlıdır.

İki yolun bugünkü değerleri karşılaştırılır. İşbirliği yolunda firma her dönem 50 alır. Bugünkü değeri bir geometrik seridir:

50 + 50δ + 50δ² + … = 50 / (1 − δ)

Bu toplam şöyle bulunur. Seri S olsun. δS = 50δ + 50δ² + … olduğu için S − δS = 50'dir; buradan S = 50/(1 − δ) çıkar. Sapma yolunda firma bugün 100 alır, sonra tetik stratejisi devreye girer ve sonsuza dek 0 alır. Bugünkü değeri 100'dür. İşbirliğinin sürmesi için işbirliğinin değeri sapmanınkinden küçük olmamalıdır:

50/(1 − δ) ≥ 100 ⟺ 50 ≥ 100(1 − δ) ⟺ 1 − δ ≤ 1/2 ⟺ δ ≥ 1/2

İkinci adımda iki taraf (1 − δ) ile çarpılmıştır; δ < 1 olduğu için bu sayı pozitiftir ve eşitsizliğin yönü değişmez. Sonuç: firmalar geleceğe yeterince değer veriyorsa (δ ≥ 1/2), kimse fiyat kırmak istemez ve yüksek fiyat sürer. Bu yapı tekrarlanan Mahkûmun İkilemi ile aynıdır.

Bu kuramsal sonucun algoritmalar için ne anlama geldiğini Calvano ve diğ. (2020) bir benzetimle inceledi. Pekiştirmeli öğrenen (her dönem kâr sinyaline göre fiyat kuralını güncelleyen) fiyatlandırma ajanları, birbirleriyle hiç mesajlaşmadan rekabetçi düzeyin üstünde fiyatlar öğrenebildi. Dahası, bir ajan fiyat kırdığında öteki geçici bir fiyat savaşıyla karşılık verdi; yani ajanlar tetik stratejisine benzeyen bir cezalandırma davranışını kendiliğinden öğrendi.

Bu bulgu bir düzenleme sorusu doğurur. Rekabet hukuku geleneksel olarak insanlar arası anlaşma kavramı üzerine kuruludur: rakiplerin bir araya gelip fiyat konuşması yasaktır. Açıkça iletişim kurmadan yüksek fiyatı öğrenen algoritmalar bu çerçeveyi zorlar. Anlaşma yoksa danışıklılık var mıdır? Sorumlu kimdir: algoritmayı yazan mı, kullanan mı? Bu sorular oyun kuramının sonuçlarına dayanır: tekrarlanan etkileşim ve gelecek değeri, açık bir anlaşma olmadan da işbirliğini sürdürebilir.

14.2.5Kod izleme: karsilastir()

Tetik koşulunu sayılarla görmek için iki yolun birikimli değeri dönem dönem hesaplanabilir. Aşağıdaki fonksiyon, her dönem 50 ile işbirliği yapan yolu ve s döneminde fiyat kırıp o dönem 100 alan, sonra 0 alan sapma yolunu T dönem boyunca karşılaştırır.

def karsilastir(delta, s, T):
    ib, sp = 0.0, 0.0            # işbirliği / sapma yolu
    for t in range(T):
        ib += delta**t * 50
        if t < s:
            sp += delta**t * 50
        elif t == s:
            sp += delta**t * 100   # A fiyat kırar
        # t > s: tetik devrede, kâr 0
    return round(ib, 2), round(sp, 2)
print(karsilastir(0.6, 2, 6))
print(karsilastir(0.4, 2, 6))

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

• ib işbirliği yolunun, sp sapma yolunun birikimli bugünkü değeridir; ikisi de 0 ile başlar.
• Döngü t = 0, 1, …, T − 1 dönemlerini dolaşır. Her dönemin kârı delta**t ile çarpılır; bu, t dönem sonraki kârın bugünkü değeridir.
• İşbirliği yolu her dönem 50 ekler.
• Sapma yolu, sapma anından önce (t < s) işbirliği yapar ve 50 ekler. Sapma anında (t == s) bütün pazarı alır ve 100 ekler. Sonra (t > s) tetik devrededir ve hiçbir şey eklenmez.
• Fonksiyon iki değeri iki basamağa yuvarlayarak döndürür.

İlk çağrı δ = 0,6, s = 2, T = 6 içindir. İzleme Tablo 14.4'te verilmiştir.

İlk iki dönemde iki yol aynıdır. t = 2'de sapan firma pazarın tümünü alır: 0,36 · 100 = 36; işbirliği yolu yalnızca 0,36 · 50 = 18 ekler ve sapma 18 öne geçer. Sonra tetik devreye girer; sapma yolu artık bir şey eklemez, işbirliği yolu ise her dönem eklemeye devam eder. t = 4'te fark 0,72'ye iner, t = 5'te işbirliği öne geçer: 119,17 > 116. Kısa vadeli 18'lik kazanç, kaybedilen gelecek kârlarla geri ödenmiştir.

Şekil 14.5 altı dönemlik pencereyi gösterir. Sonsuz ufukta fark daha da büyüktür: işbirliğinin değeri 50/(1 − 0,6) = 125'tir, sapmanınki ise 116'da kalır (sapma anından sonra hiçbir şey eklenmez). Yani δ = 0,6'da sapma kârlı değildir; bu, δ ≥ 1/2 koşuluyla tutarlıdır.

İkinci çağrı δ = 0,4 içindir. Bu kez gelecek daha hızlı değer kaybeder.

Şekil 14.6'da işbirliği yolu 50, 20, 8, 3,2, 1,28 ve 0,51 ekleyerek 82,99'a ulaşır. Sapma yolu 50, 20 ve 16 ekleyip 86'da kalır. Sonsuz ufukta işbirliğinin değeri 50/0,6 ≈ 83,3'tür; bu da 86'dan küçüktür. Sapma kârlıdır ve danışıklılık çöker. Eşik δ = 1/2'dir: bu değerde iki yol sonsuzda eşit olur (50/0,5 = 100).

14.2.6Danışıklılığı kolaylaştıran ve zorlaştıran koşullar

Tetik koşulu, danışıklılığın hangi piyasalarda daha olası olduğunu da söyler. İlk etken firma sayısıdır. n firma tekel kârını eşit paylaşıyorsa her biri dönem başına 100/n alır. Sapan firma yine bir dönem bütün pazarı (100) alır, sonra 0. Koşul şöyle olur:

(100/n) / (1 − δ) ≥ 100 ⟺ 1/n ≥ 1 − δ ⟺ δ ≥ 1 − 1/n

Firma çoğaldıkça işbirliği payı küçülür, sapmanın getirisi ise aynı kalır. Bu yüzden kalabalık piyasada danışıklılığı sürdürmek için çok daha fazla sabır gerekir. İki firmada yeten δ = 0,6, beş firmalı bir piyasada yetmez.

Firma sayısı dışında üç etken daha önemlidir. Bunlar algoritmik fiyatlandırmanın danışıklılığı neden kolaylaştırabileceğini açıklar.

Sık fiyat güncelleme

δ bir dönemin uzunluğuna bağlıdır. Fiyatlar yılda bir değişiyorsa bir dönem sonraki kâr bugüne göre epey değer kaybeder. Fiyat dakikada bir güncelleniyorsa bir dakika sonraki kâr neredeyse bugünkü kadar değerlidir; dönem başına δ ≈ 1 olur. Ayrıca sapanın kazancı, rakip tepki verene kadar geçen birkaç dakikayla sınırlı kalır. İki etki de danışıklılığı kolaylaştırır.

Şeffaf fiyatlar

Rakip fiyatı anında görülebiliyorsa sapma hemen fark edilir ve ceza gecikmez. Sapma ancak birkaç dönem sonra fark edilebilseydi sapan o dönemlerin hepsinde 100 alırdı ve eşik yükselirdi.

Fiyat eşleme garantisi

“Rakip daha ucuzsa farkı öderiz” garantisi ilk bakışta tüketici dostu görünür. Oysa bu garanti, fiyat kırmanın kazancını sıfırlar: rakip fiyat kırarsa müşteri yine de garantiyi veren firmadan alır. Fiyat kırmak kimseye müşteri kazandırmadığı için kimse kırmaz ve danışıklılık korunur.

Düzenleme önerileri

Bir fiyatlandırma algoritmasını piyasaya sürmeden önce benzetim ortamında başka algoritmalarla karşılaştırıp sınamak; algoritmanın karar kayıtlarını denetime açmak. Bu öneriler, danışıklılığın bir anlaşmadan değil bir dinamikten doğabileceği gözlemine dayanır.

14.2.7Turnuvaya dönüş

Giriş turnuvasının ilk oyunu Mahkûmun İkilemi'dir. Kazançlar karşılıklı işbirliğinde (3, 3), işbirliği yapan ile ihanet eden arasında (0, 5) ya da (5, 0), karşılıklı ihanette (1, 1)'dir. Her maç 60 turdur. Rastgele ajan her turda yarı yarıya karar verdiği için onun maçları beklenen değerle hesaplanır. En İyi Tepki ajanı ilk turda işbirliği yapar. Sonra rakibin en sık hamlesine en iyi tepki verir. Mahkûmun İkilemi'nde ihanet baskın strateji olduğu için rakip ne yaparsa yapsın en iyi tepki ihanettir. Yani En İyi Tepki ajanı ilk turdan sonra hep ihanet eder.

İlk sorunun cevabı Hep İhanet'tir. En İyi Tepki çok yakından ikinci olur; ikisinin farkı yalnızca ilk turdaki işbirliğinden doğar. Bu turnuvada karşılıklı işbirliği neredeyse hiç görülmez, çünkü hiçbir ajan geçmişe göre ödül ya da ceza vermez. İşbirliğini sürdürecek bir tehdit olmadığından baskın strateji kazanır.

İkinci soru için oyun değiştirilir. Yazı-Tura Eşleştirme'de bir oyuncu iki seçim aynıysa, öteki farklıysa kazanır; sıfır toplamlıdır ve saf dengesi yoktur. Burada sıralama değişir. Hep aynı hamleyi yapan iki sabit ajan kolayca sömürülür: En İyi Tepki ajanı onların hamlesini öğrenir ve ilk turdan sonra hep kazanır. Bu sayede yaklaşık +118 ile birinci olur. Rastgele ajan ise hiçbir rakibe karşı sömürülemez; her maçta beklenen kazancı 0'dır. Bu, Yazı-Tura'nın karışık dengesinin (yarı yarıya oynamak) güvence değeridir.

Gerçek turnuvalar da aynı dersi verir. Axelrod'un (1980) tekrarlanan Mahkûmun İkilemi turnuvasını Tit-for-Tat (ilk turda işbirliği yap, sonra rakibin son hamlesini tekrarla) kazandı. Karşılıklılık ve ceza tehdidi işbirliğini korudu. Buradaki dört ajanda geçmişe göre cezalandırma yoktur; bu yüzden işbirliği doğmaz. Calvano ve diğ. (2020) çalışmasındaki fiyat ajanları ise önceki dönemi hatırlar ve cezalandırmayı öğrenip yüksek fiyatı sürdürebilir. Fark hafızadadır.

Turnuvanın genel dersi şudur: evrensel en iyi strateji yoktur. Bir stratejinin başarısı oynanan oyuna, rakip kitlesine, gürültüye ve hafızaya bağlıdır. Bir ajanı tek bir ortamda sınayıp her yerde iyi olacağını varsaymak yanlıştır. Bu gözlem, ajanları değerlendirmek için birden çok oyunda ve birden çok rakiple yapılan, tekrarlanabilir deneylerin neden gerekli olduğunu da açıklar (14.12.3).

14.3Öğrenen mekanizmalar

Mekanizma tasarımında kural, istenen sonucu verecek şekilde tasarımcı tarafından seçilir. Klasik yolda bu seçim bir ispatla yapılır. Bu kısım ikinci bir yolu inceler: kuralı bir optimizasyon probleminin çözümü olarak ya da doğrudan veriden öğrenmek. Öğrenmenin getirdiği iki yeni sorun da ele alınır: az veride kendi başarısını abartma ve tek tek kişilerin verisinin mahremiyeti.

14.3.1Otomatik mekanizma tasarımı

Mekanizma tasarımının klasik yolu şöyledir. Bir insan bir kural önerir: ikinci fiyat (Vickrey) açık artırması, VCG mekanizması ya da Myerson'un gelir optimal açık artırması gibi. Sonra kuralın teşvik uyumlu olduğu ve belirli bir amaç için optimal olduğu elle ispatlanır. Bu yol tek nesne gibi yapılı problemlerde çok başarılıdır. Ama çok nesneli ve çok alıcılı durumlarda gelir optimal mekanizma çoğu zaman bilinmez; elle ispat edilecek bir aday bile yoktur.

Otomatik yolda mekanizma bir optimizasyon probleminin çözümüdür. Problemin bir amacı (gelir ya da sosyal refah) ve iki tür kısıtı vardır.

Otomatik tasarımın iki temel biçimi vardır.

• Doğrusal programlama. Oyuncuların tipleri sonlu bir kümeden geliyorsa, her tip için satış olasılığı ve ödeme birer değişkendir. Amaç ve kısıtlar bu değişkenlerde doğrusal olur. Problem doğrusal programlamayla çözülür (Conitzer ve Sandholm, 2002). Sonraki alt başlıktaki örnek bu türdendir.
• Sinir ağı ile açık artırma. Tipler sürekli ve çok boyutluysa, mekanizma bir sinir ağıyla temsil edilir: ağ teklifleri alır, dağıtımı ve ödemeleri verir. IC kısıtı doğrudan yazılamaz; onun yerine bir pişmanlık cezası eklenir (Dütting ve diğ., 2019). Burada pişmanlık, bir teklifçinin yalan söyleyerek elde edebileceği en büyük ek faydadır. Eğitim, geliri artırırken pişmanlığı sıfıra yaklaştırmaya çalışır.

Otomatik yolun üç sınırı vardır:

Yaklaşık IC

Öğrenilen kural tam teşvik uyumlu olmayabilir; eğitimden sonra küçük bir pişmanlık kalır. Bu duruma yaklaşık teşvik uyumluluğu denir. Küçük bir yalan kazancı, çok sayıda katılımcının hesap yapmaya değer bulmayacağı kadar küçükse pratikte sorun olmayabilir; ama ispatlanmış bir garanti değildir.

Genelleme

Kural, eğitim verisindeki değer dağılımına göre öğrenilir. Gerçek dağılım değişirse (örneğin bir ekonomik şokla) kural etkisizleşebilir.

Açıklanabilirlik

Bir katılımcı “Neden bu fiyatı ödedim?” diye sorduğunda, sinir ağının ağırlıkları anlaşılır bir cevap vermez. Vickrey kuralı ise tek cümleyle açıklanabilir: “ikinci en yüksek teklifi ödersin”.

14.3.2Kod izleme: gelir()

Otomatik tasarımın en küçük örneği tek alıcı ve tek nesneyle kurulur. Alıcının iki olası tipi vardır: L tipi nesneye 1 değer verir ve olasılığı q_L'dir; H tipi 3 değer verir ve olasılığı 1 − q_L'dir. Satıcı alıcının tipini bilmez; alıcıdan tipini bildirmesini ister. Mekanizma her bildirilen tip için bir satış olasılığı ve bir ödeme belirler. H tipine her zaman satılır. L tipine satış olasılığı x_L'dir. Ödemeler p_L ve p_H'dir.

Gelir maksimize edilirken iki kısıt sıkı (eşitlikle) sağlanır. Bunlar şöyle türetilir.

1. L'nin katılım kısıtı (IR). L tipinin faydası 1 · x_L − p_L ≥ 0 olmalıdır. Satıcı geliri artırmak için p_L'yi bu sınıra kadar çıkarır: p_L = x_L. L'ye fiyat, L'nin ödemeye razı olduğu en yüksek değerdir.
2. H'nin doğruluk kısıtı (IC). H tipi “L'yim” derse nesneyi x_L olasılıkla alır ve p_L öder: faydası 3x_L − p_L. Doğruyu söylerse faydası 3 − p_H'dir. Doğruyu söylemek en az yalan kadar iyi olmalıdır: 3 − p_H ≥ 3x_L − p_L. Satıcı p_H'yi bu sınıra kadar çıkarır: p_H = p_L + 3(1 − x_L).
3. Beklenen gelir. G = q_L p_L + (1 − q_L) p_H.

Ödemeler yerine konunca gelir yalnız x_L'ye bağlı kalır:

G(x_L) = q_L x_L + (1 − q_L)(3 − 2x_L) = 3(1 − q_L) + x_L(3q_L − 2)

Bu ifade x_L'de doğrusaldır. L'ye satmanın bir bedeli vardır: L'ye ucuza satmak, H'ye de bir yalan seçeneği açar ve H'nin fiyatını düşürür. Aşağıdaki kod geliri üç x_L değeri ve iki q_L için hesaplar.

def gelir(xL, qL, vL=1, vH=3):
    pL = xL * vL                 # L'nin IR kısıtı sıkı
    pH = pL + vH * (1 - xL)      # H'nin IC kısıtı sıkı
    return qL * pL + (1 - qL) * pH
for qL in [0.5, 0.75]:
    G = [gelir(x, qL) for x in [0, 0.5, 1]]
    print(qL, G)

Kod satır satır şöyle çalışır. pL, L'nin katılım kısıtını sıkı yapan ödemedir. pH, H'nin doğruluk kısıtını sıkı yapan ödemedir. Fonksiyon iki tipin olasılıklarıyla ağırlıklı ortalamayı döndürür. Döngü q_L = 0,5 ve 0,75 için x_L ∈ {0; 0,5; 1} değerlerini dener.

x_L = 0,5 satırı ödünleşimi açıkça gösterir. L'ye yarı olasılıkla 0,5'ten satmak, H'ye “L desem 3 · 0,5 − 0,5 = 1 kazanırım” seçeneğini açar. H'yi doğruyu söylemeye razı etmek için onun fiyatı 3'ten 2'ye inmelidir. q_L = 0,5'te bu kayıp, L'den gelen ek gelirden büyüktür.

Şekil 14.7'de iki doğru görülür. q_L = 0,5'te en iyisi x_L = 0'dır: yalnız H'ye 3'ten satılır, gelir 1,5. q_L = 0,75'te L tipi çoğunluktadır; yalnız H'ye satmak artık az kazandırır (0,75) ve en iyisi herkese 1'den satmaktır, gelir 1. Gelir formülündeki x_L katsayısı 3q_L − 2'dir. Bu katsayı q_L = 0,5'te −0,5, q_L = 0,75'te +0,25'tir.

Önemli bir gözlem vardır: gelir x_L'de doğrusal olduğu için optimum her zaman bir uçtadır. Bu, doğrusal programlamanın genel bir özelliğidir: optimum, olurlu bölgenin bir köşesindedir. İki çözüm de aslında ilan edilmiş bir fiyattır: ya “fiyat 3” ya da “fiyat 1”. Yani bu küçük örnekte otomatik tasarım, Myerson kuramının tek nesne için verdiği sonucu yeniden bulur: gelir optimal mekanizma, doğru seçilmiş bir rezerv fiyatıdır. Otomatik tasarımın asıl değeri, böyle bir kuramın bulunmadığı çok nesneli durumlarda ortaya çıkar.

14.3.3Veriden rezerv fiyatı öğrenmek

Önceki örnekte satıcı tip dağılımını biliyordu. Gerçekte dağılım bilinmez; elde yalnızca geçmişte gözlenen değerler vardır. Bu durumda doğal bir yol, geçmiş veride en çok geliri getirecek fiyatı seçmektir.

Hangi fiyatların denenmesi gerektiği şöyle bulunur. İki ardışık örnek değerin arasında bir fiyat seçilirse, alıcı sayısı değişmeden fiyat yükseltilebilir; bu da geliri artırır. Bu yüzden en iyi fiyat her zaman örnek değerlerden biridir. Değerler büyükten küçüğe sıralanır. k'inci en büyük değer fiyat olursa tam k alıcı satın alır (eşitlik yoksa). Bu yüzden yalnız n aday fiyatı denemek yeter.

def en_iyi_fiyat(orn):
  v = sorted(orn, reverse=True)
  n = len(v)
  fiyat, gelir = 0, 0
  for k in range(1, n + 1):
    p = v[k - 1]        # k. en yüksek
    g = p * k / n       # k alıcı alır
    if g > gelir:
      fiyat, gelir = p, g
  return fiyat, gelir

Kod satır satır şöyle çalışır. v, örneklerin büyükten küçüğe sıralı hâlidir. fiyat ve gelir, şimdiye kadarki en iyi fiyatı ve onun deneysel gelirini tutar. Döngü k = 1, …, n için k'inci en büyük değeri fiyat olarak dener. Bu fiyatta k alıcı satın alır ve deneysel gelir p · k / n olur. Gelir öncekinden büyükse en iyi fiyat güncellenir.

Örnekte geçmişte gözlenen 8 alıcı değeri 0,62; 0,15; 0,91; 0,47; 0,33; 0,78; 0,55; 0,08'dir. Sıralanınca 0,91; 0,78; 0,62; 0,55; 0,47; 0,33; 0,15; 0,08 olur.

Şekil 14.8 öğrenilen fiyatı gösterir. Fiyat düştükçe alıcı sayısı artar ama her alıcıdan alınan para azalır. İlk beş adımda alıcı artışının etkisi ağır basar; altıncı adımda (0,33) fiyat düşüşünün etkisi ağır basmaya başlar. Öğrenilen fiyat 0,47, deneysel gelir yaklaşık 0,294'tür.

14.3.4Deneysel ve gerçek gelir

Öğrenilen fiyatın gelecekte gerçekten ne kazandıracağı, değerlerin geldiği gerçek dağılıma bağlıdır. Örneğin değerlerin U[0, 1] dağılımından geldiğini varsayalım. Bu, 0 ile 1 arasındaki her değerin eşit olasılıklı olması demektir. Bu dağılımda bir alıcının değerinin p'den büyük olma olasılığı 1 − p'dir. Bu yüzden fiyat p'nin alıcı başına gerçek geliri şudur:

G(p) = p · (1 − p)

Bu fonksiyon bir paraboldür. En büyük değeri ortadaki noktadadır: p = 0,5'te G = 0,5 · 0,5 = 0,25. Öğrenilen fiyat için gerçek gelir 0,47 · 0,53 ≈ 0,249'dur. Yani öğrenilen fiyat neredeyse en iyisi kadar iyidir. Ama deneysel gelir (0,294), gerçek gelirden (0,249) belirgin biçimde yüksektir.

Şekil 14.9 iki eğriyi karşılaştırır. Deneysel eğri bir testere dişi gibidir: iki örnek değer arasında fiyatla doğrusal artar, bir örnek değeri geçince o alıcı kaybedildiği için aşağı düşer. Gerçek eğri ise düzgün bir paraboldür. Deneysel eğri bazı fiyatlarda gerçeğin üstünde, bazılarında altındadır.

Seçilen fiyatın deneysel başarısının abartılı olması bir rastlantı değildir. Fiyat, deneysel eğrinin en yüksek noktası olarak seçilmiştir. Deneysel eğrinin gerçeğin üstüne çıktığı yerler, örneklerin şans eseri bol olduğu yerlerdir. En yüksek nokta seçilince bu şanslı dalgalanmalardan biri de seçilmiş olur. Ölçülen ve seçilen aynı veri olduğu için bir iyimser yanlılık oluşur. Gerçek en iyi gelirle (0,25) seçilen fiyatın gerçek geliri (0,249) arasındaki fark küçüktür; ama örnek azaldıkça hem bu fark hem de iyimser yanlılık büyür.

14.3.5Kaç örnek yeter? Örneklem karmaşıklığı

Örnek sayısı arttıkça deneysel eğri gerçeğe yaklaşır. Bunu görmek için benzetim yapılabilir: U[0, 1]'den n değer çekilir, deneysel gelir maksimize edilir, seçilen fiyatın deneysel ve gerçek geliri kaydedilir. Bu işlem her n için yüzlerce kez tekrarlanıp ortalaması alınır.

Tablo iki şey gösterir. Birincisi, aşırı uyum (overfitting): az örnekte deneysel gelir gerçeğinden çok yüksek görünür (n = 10'da 0,311'e karşı 0,224). Öğrenilen fiyat, gerçek dağılımın değil o belirli örneklerin özelliklerine uymuştur; bir anlamda örneklere “ezberlenmiştir”. İkincisi, örnek arttıkça iki sütun birbirine ve 0,25'e yaklaşır. Gerçek gelirdeki kayıp her on kat örnekte kabaca beşte birine iner.

Cole ve Roughgarden (2014) bu soruyu açık artırmalar için inceledi. Sonuç kabaca şöyledir: değer dağılımı çok uç değerler üretmiyorsa, iyi bir mekanizma için gereken örnek sayısı teklifçi sayısı ve istenen doğrulukla ölçülü (polinom) biçimde artar. Yani “biraz daha doğruluk” için örnek sayısı patlamaz. Uç değerli dağılımlarda ise böyle bir garanti verilemeyebilir. Bunun nedeni sezgiyle anlaşılır: çok nadir ama çok büyük değerler gelirin önemli bir kısmını oluşturuyorsa, bu değerleri yeterince görmek için çok fazla örnek gerekir.

Bu alt başlığın dersi makine öğrenmesinden tanıdıktır: veriden öğrenilen bir mekanizma, az veride kendi başarısını abartır. Eğitim ve değerlendirme verisini ayırmak, makine öğrenmesinde olduğu kadar mekanizma tasarımında da gereklidir.

14.3.6Seçmek ve ölçmek için ayrı veri

İyimser yanlılığı önlemenin en basit yolu veriyi ikiye ayırmaktır. Eğitim verisi fiyatı seçmek için, doğrulama verisi seçilen fiyatı ölçmek için kullanılır. Doğrulama verisi seçimde kullanılmadığı için onun üzerinde yapılan ölçüm yanlı değildir.

Bu yöntemin bir bedeli vardır: fiyat artık 8 değil yalnız 4 örnekle seçildiği için daha gürültülüdür. Çapraz doğrulama, bütün veriyi hem seçim hem ölçüm için sırayla kullanarak bu bedeli azaltır.

Mekanizmalara özgü bir risk daha vardır. Makine öğrenmesinde veri genellikle doğadan gelir; veriyi üretenler modelin ne yapacağını umursamaz. Açık artırmada ise veri, teklif veren alıcılardan gelir. Alıcılar geçmiş tekliflerinin gelecekteki fiyatı belirlediğini bilirse, bugün bilerek düşük teklif verebilir: biraz kaybeder ama gelecekte daha düşük bir rezerv fiyatıyla karşılaşır. Yani veri de stratejik olabilir. Bu durumda öğrenme algoritmasının kendisi de bir mekanizmadır ve onun da teşvik uyumlu olması gerekir.

14.3.7Diferansiyel mahremiyet ve üstel mekanizma

Veriden öğrenmenin bir başka sorunu mahremiyettir. Öğrenilen fiyat ilan edilince, bu fiyat geçmiş alıcıların değerleri hakkında bir şeyler sızdırır. Örneğin yalnız bir alıcının verisi eklenince fiyat çok değişiyorsa, fiyattan o alıcının değeri çıkarılabilir.

Sade dille: tek bir kişinin verisi eklense ya da çıkarılsa da her sonucun olasılığı ancak biraz değişir. ε mahremiyetin ölçüsüdür. Küçük ε daha çok mahremiyet demektir: olasılıklar en fazla e^ε kat değişebilir. ε = 0 tam mahremiyettir ama sonuç veriye hiç bağlı olamaz; ε büyüdükçe sonuç veriye daha çok uyar ama mahremiyet azalır. Tanımın rastgele bir mekanizma istediğine dikkat edilmelidir. Kesin (rastgele olmayan) bir kural, bir kişinin verisiyle bir sonuçtan ötekine atlayabilir; o sonucun olasılığı 1'den 0'a düşer ve oran sonsuz olur.

McSherry ve Talwar (2007) bu tanımı sağlayan genel bir araç verdi.

Mekanizma en iyi fiyatı kesin olarak seçmez, bir kura çeker. İyi fiyatlar üstel olarak daha yüksek olasılık alır; kötü fiyatlar küçük ama sıfır olmayan bir olasılık alır. Formüldeki 2'nin nedeni şudur: bir kişi çıkarılınca hem payın (seçilen adayın ağırlığı) hem de paydanın (bütün ağırlıkların toplamı) değişebilir. Her biri en çok e^ε/2 kat değişir; ikisi birlikte en çok e^ε kat değişim üretir. Bu da tanımdaki sınırdır.

Bu mekanizmanın oyun kuramıyla güçlü bir bağı vardır. Tek bir kişinin raporu sonucu az etkilediği için, o kişinin yalan söyleyerek elde edebileceği kazanç da azdır. Yani diferansiyel mahremiyet yaklaşık teşvik uyumluluğu sağlar; üstelik mahremiyetle birlikte. Bu, mahremiyetin ve teşviklerin aynı matematiksel araçla ele alınabildiği şaşırtıcı bir sonuçtur.

Şekil 14.11 tanımın ne söylediğini görselleştirir. Bir alıcı veriden çıkarılınca seçim olasılıkları değişir ama çok az değişir. Bu örnekte en büyük değişim 1,44 kattır; tanımın izin verdiği sınır ise e² ≈ 7,39'dur. Olasılıkların nasıl hesaplandığı bir sonraki kod izlemesinde adım adım gösterilir.

14.3.8Kod izleme: ustel()

Aşağıdaki kod, veriden fiyat öğrenme örneğindeki 8 alıcı değeriyle üstel mekanizmayı uygular. Aday rezerv fiyatları 0,2; 0,4; 0,6; 0,8'dir. Puan, fiyat ile o fiyattan satın alacak alıcı sayısının çarpımıdır (toplam gelir). Fiyatlar 1'den küçük olduğu için bir alıcı çıkarılınca bir fiyatın puanı en çok 1 değişir; bu yüzden Δ = 1'dir. ε = 2 seçilince ağırlık formülü exp(2R/2) = e^R'ye sadeleşir.

import math
def ustel(v, fiyatlar, eps):
    R = [p * sum(x >= p for x in v) for p in fiyatlar]
    w = [math.exp(eps * r / 2) for r in R]   # Δ = 1
    W = sum(w)
    return [x / W for x in w]
v = [0.62, 0.15, 0.91, 0.47, 0.33, 0.78, 0.55, 0.08]
P = [0.2, 0.4, 0.6, 0.8]
q = ustel(v, P, 2)
print([round(x, 3) for x in q])
q = ustel(v[1:], P, 2)          # 0.62 çıkarıldı
print([round(x, 3) for x in q])

Kod satır satır şöyle çalışır. R, her aday fiyatın puanını hesaplar; sum(x >= p for x in v), değeri fiyata eşit ya da büyük olan alıcıları sayar. w, ağırlıklardır. W, ağırlıkların toplamıdır. Fonksiyon her ağırlığı toplama bölerek olasılıkları döndürür. Kod önce bütün veriyle, sonra ilk alıcı (0,62) çıkarılmış veriyle çalıştırılır.

Bütün veriyle en olası fiyat p = 0,4'tür (%38,9); ama tek başına değildir, kötü fiyat 0,8'in bile %11,7 şansı vardır. Ağırlıklar arasındaki farklar üsteldir: puan 0,8'den 2'ye çıkınca ağırlık 2,23'ten 7,39'a çıkar. 0,62 değerli alıcı çıkarılınca p = 0,2, 0,4 ve 0,6'nın puanları düşer; en çok p = 0,6'nınki düşer (0,6). p = 0,8'in puanı değişmez, çünkü 0,62 zaten 0,8'in altındaydı. Toplam ağırlık küçüldüğü için p = 0,8'in olasılığı artar.

Son sütun iki dağılımın oranıdır (büyüğün küçüğe oranı). En büyük oran 1,44'tür ve e² ≈ 7,39 sınırının çok altındadır. Tek kişinin verisi sonucu sınırlı etkiler; mekanizma ε-diferansiyel mahremiyetlidir. Sınır en kötü durum içindir; tipik bir veri kümesinde gerçek değişim çoğu zaman çok daha küçüktür.

14.4Blokzincir mekanizmaları

Blokzincirler, kuralları herkese açık kodla uygulayan sistemlerdir. Bu kısım onları bir teknoloji olarak değil, bir mekanizma tasarımı ortamı olarak inceler. Üç mekanizma ele alınır: kıt blok alanını dağıtan işlem ücreti açık artırmaları, fiyatı bir formülle belirleyen otomatik piyasa yapıcı ve işlemlerin sırasını belirleme gücünden doğan değer (MEV). Bu alanda kullanılan somut kurallar ve araçlar sık değişir; not, değişmeyen ilkeleri öne çıkarır.

14.4.1Blokzincir ve akıllı sözleşmeler

Bu tanımın oyun kuramı için önemi şudur. Mekanizma tasarımı, tasarımcının ilan ettiği kurallara sonradan bağlı kalacağını, yani bir taahhüt (commitment) olduğunu varsayar. Örneğin ikinci fiyat açık artırmasında satıcı, teklifleri gördükten sonra “aslında birinci fiyatı ödeyeceksiniz” diyemez. Gerçek hayatta bu varsayım bir güvene ya da hukuka dayanır. Akıllı sözleşmede ise taahhüt kodla sağlanır: kural yayımlandıktan sonra kimse onu değiştiremez.

Ama bu ortam yeni bir sorun da getirir. Bekleyen işlemler, bloğa girmeden önce herkese görünür. Bir işlemin ne yapacağını önceden görmek, ondan kâr etmenin yolunu açar. Ayrıca işlemleri bloklara yerleştiren bir blok üreticisi vardır. Üretici hangi işlemin bloğa gireceğine ve hangi sırayla gireceğine karar verir. Blok alanı sınırlıdır; yani kıt bir kaynaktır ve kıt kaynak doğal olarak açık artırmayla dağıtılır.

Şekil 14.12 süreci gösterir. Kullanıcılar işlemlerini bekleme havuzuna (mempool) gönderir. Blok üreticisi havuzdan işlem seçip sıralar. Bu yapıda üç mekanizma tasarımı sorusu doğar:

• İşlem ücreti açık artırması: Kısıtlı blok alanı, işlem ücreti teklif eden kullanıcılara nasıl dağıtılmalı?
• Merkeziyetsiz borsa: Alım satımın karşı tarafı bir insan yerine bir formül olabilir mi? Bu, otomatik piyasa yapıcı (AMM, automated market maker) fikridir.
• Zincir üstü yönetişim: Bir sistemin kurallarını değiştirmek için jeton (token) ağırlıklı oylama yapılır. Oylama kurallarının bilinen sorunları (stratejik oy, Condorcet döngüleri, büyük oy sahiplerinin gücü) burada da geçerlidir.

14.4.2İşlem ücreti açık artırmaları

Bir bloğa sığabilecek işlem sayısı sınırlıdır. Daha fazla işlem bekliyorsa hangilerinin gireceğine bir kuralla karar verilir. Bu kurala işlem ücreti mekanizması (transaction fee mechanism) denir. İki tasarım karşılaştırılır.

Birinci fiyat tasarımı. İlk blokzincirlerin kullandığı tasarımda her işlem bir ücret teklif eder. Üretici en yüksek teklifleri alır ve herkes kendi teklifini öder. Bu, bildiğimiz birinci fiyat açık artırmasıdır. Örnekte bekleyen beş işlemin değerleri 9, 7, 6, 4, 2 ve blok kapasitesi 3'tür. Herkes dürüst teklif verirse en yüksek üç işlem girer ve üreticiye 9 + 7 + 6 = 22 ödenir.

Ama birinci fiyat açık artırmasında dürüst teklif en iyi strateji değildir. Değeri 9 olan kullanıcı 9 teklif ederse fayda elde etmez; girmeye yetecek en küçük teklifi vermek ister. Bu yüzden herkes teklifini kırpar. Kırpma miktarı, ötekilerin ne teklif edeceğine dair tahmine bağlıdır. Sonuç olarak her kullanıcı “ne kadar vermeliyim?” sorusuyla uğraşır. Bu yorucudur ve tahmin yapamayan kullanıcılar ya fazla öder ya da dışarıda kalır.

Taban ücret + bahşiş tasarımı. Literatürde EIP-1559 adıyla bilinen tasarımda protokol, her blok için bir taban ücret (base fee) r belirler. Taban ücreti ödemeye razı olan her işlem girer. Taban ücret yakılır: kimseye ödenmez ve dolaşımdan çıkar. Üreticiye yalnızca kullanıcının eklediği küçük bir bahşiş (tip) gider.

Şekil 14.13 iki tasarımı aynı veride karşılaştırır. Taban ücret tasarımının asıl üstünlüğü basitliktir: talep kapasiteyi aşmıyorsa en iyi strateji “taban ücret + küçük bahşiş” ödemektir ve fiyat tahmini gerekmez. Bu, bir ilan edilmiş fiyatta satın almaya benzer. Talep kapasiteyi aşınca ise tasarım yeniden bir açık artırmaya döner: kullanıcılar bahşiş üzerinden yarışır.

Roughgarden (2021), iyi bir işlem ücreti mekanizmasının hedeflerini biçimsel olarak tanımladı: kullanıcı için basit teklif, üretici için dürüst davranış ve danışıklılığa direnç. Bu hedeflerin hepsini tam olarak sağlayan bir kural bulmak zordur. Bu hedefler 14.4.4'te ayrıntılı ele alınır.

14.4.3Taban ücret talebe göre ayarlanır

Taban ücret sabit değildir; talebi izler. Genel ilke basittir: blok hedeflenen dolulukun üstündeyse ücret artar, altındaysa düşer. Tasarımın ilk parametreleriyle güncelleme kuralı şöyledir:

r_t+1 = r_t · (1 + ⅛ · (g_t − g_hedef) / g_hedef)

Burada g_t, t bloğunda kullanılan alan; g_hedef ise blok kapasitesinin yarısıdır. Formülün parçaları şöyle okunur. (g_t − g_hedef)/g_hedef, doluluğun hedeften göreli sapmasıdır. Blok tam doluysa g_t = 2g_hedef ve sapma +1'dir. Blok boşsa sapma −1'dir. Hedefteyse sapma 0'dır. Sapma ⅛ ile çarpıldığı için ücret bir blokta en çok %12,5 artar ya da azalır.

Şekil 14.14 ücretin talebi nasıl izlediğini gösterir. Taban ücret, talebi izleyen bir ilan edilmiş fiyat gibi çalışır. Talep yükselince fiyat da yükselir ve bloklar yeniden hedef doluluğa iner. Ama ayarlama zaman alır: ani bir talep patlamasında ücret yalnızca %12,5'lik adımlarla yükselebilir. Bu arada bloklar doludur ve sistem geçici olarak yeniden bahşişe dayalı bir açık artırmaya döner.

Değişimin çarpımsal olduğuna dikkat edilmelidir. Dört dolu bloktan sonra ücret 100 · 1,125⁴ ≈ 160,2'dir, 100 + 4 · 12,5 = 150 değil. Ayrıca bir artışı aynı oranda bir azalış tam geri almaz: 1,125 · 0,875 ≈ 0,984 olduğu için bir dolu ve bir boş blok ücreti %1,6 düşürür.

14.4.4Neden yakılır?

Taban ücretin üreticiye verilmek yerine yakılması ilk bakışta israf gibi görünür. Bu tercihin nedeni, iyi bir ücret mekanizmasının üç özelliğiyle açıklanır.

Kullanıcı teşvik uyumu

Talep kapasiteyi aşmıyorsa kullanıcı için en iyi teklif taban ücret ile küçük bir bahşiştir. Kullanıcı “teklifimi ne kadar kırpmalıyım?” diye düşünmez.

Üretici teşvik uyumu

Üretici kurala uyarak en çok kazanır. Sahte işlem eklemek ya da gerçek işlemleri saklamak ona kazandırmaz.

Danışıklılığa dayanıklılık

Üretici ve bazı kullanıcılar zincir dışında anlaşıp ortak kazançlarını artıramaz. Örneğin “bahşişi zincir dışında öde, taban ücreti düşük tutalım” gibi bir yan anlaşma kazandırmamalıdır.

Yakmanın gerekçesi Şekil 14.15'te görülür. Taban ücret üreticiye gitseydi, üreticinin bloğa kendi sahte işlemlerini eklemesi bedava olurdu: ödediği ücret yine kendisine dönerdi. Bu sahte işlemler bloğu doldurur ve taban ücretin bir sonraki blokta yükselmesine yol açar. Üretici böylece ücreti istediği gibi şişirebilirdi. Ücret yakılınca her sahte işlem r kadar gerçek bir kayıptır: 5 sahte işlem 5r yakar. Sahte talep yaratmak artık pahalıdır.

Yakmak bütün sorunları çözmez. Blok doluyken kullanıcılar yine bahşiş üzerinden yarışır ve birinci fiyat davranışı geri gelir. Bu, kuramsal bir sınırın yansımasıdır. Üç özellik Roughgarden (2021) tarafından biçimselleştirildi. Daha sonraki çalışmalar, blok alanı kıtken üç özelliğin aynı anda tam olarak sağlanamayacağını gösterdi (Chung ve Shi, 2023; Chung, Roughgarden ve Shi, 2024). İki çalışma, danışıklılığa dayanıklılığın farklı tanımlarını kullanır; sonuç iki tanımda da bir imkânsızlıktır. Yani her işlem ücreti mekanizması bu üç hedef arasında bir ödünleşim yapmak zorundadır.

14.4.5Otomatik piyasa yapıcı: sabit çarpım kuralı

Klasik bir borsada alım satım, alıcı ve satıcı emirlerinin eşleşmesiyle olur. Merkeziyetsiz borsaların çoğunda ise karşı taraf bir insan değil bir havuzdur. Havuzda iki varlık bulunur ve fiyat bir formülle belirlenir.

Formül şöyle türetilir. İşlemden sonra havuzda x + Δx A ve y − Δy B vardır ve çarpım değişmez. İki taraf x + Δx'e bölünür: y − Δy = xy/(x + Δx). Buradan Δy = y − xy/(x + Δx) = y(x + Δx − x)/(x + Δx) = yΔx/(x + Δx).

Havuzun anlık fiyatı y/x'tir (bir A kaç B eder). Havuz (1000; 1000) ise başlangıç fiyatı 1 A = 1 B'dir. Ama büyük bir işlem bu fiyattan yapılamaz; çünkü işlem sürdükçe havuzdaki B azalır ve B pahalanır. Kullanıcının başlangıç fiyatına göre eksik aldığı orana kayma (slippage) denir.

Tablodan bir genel kural çıkar: kayma, Δx/(x + Δx)'e eşittir; yani işlemin havuza göre büyüklüğüne bağlıdır. 10 A için 10 B yerine 9,90 B alınır, kayma %1'dir. Havuzun yarısı kadar (500 A) satan kullanıcı ise üçte bir kayıpla işlem yapar. Gerçek havuzlar ayrıca küçük bir işlem ücreti alır. %0,3 ücretle 100 A'nın yalnızca 99,7'si havuza işler: 1000 · 99,7 / 1099,7 ≈ 90,66 B alınır. Ücret havuzda kalır ve havuza varlık koyan likidite sağlayıcılarına gider.

Şekil 14.16 işlemin havuzu eğri boyunca nasıl hareket ettirdiğini gösterir. 100 A'lık işlemden sonra yeni fiyat 1100 / 909,09 ≈ 1,21 A'dır: 1 B artık 1,21 A eder. Büyük işlem fiyatı kendi aleyhine kaydırır; buna fiyat etkisi denir. Bu yapının üç sonucu vardır:

• Havuz fiyatı ile dış piyasa fiyatı arasında fark açılınca, ucuzdan alıp pahalıdan satan arbitrajcılar havuzu yeniden dengeler. Havuz fiyatı böylece dış fiyatı izler.
• Fiyat etkisi formülle, önceden ve kesin olarak hesaplanabilir. Bekleyen bir işlemin havuzu nereye götüreceği herkesçe bilinir.
• Bu yüzden bekleyen büyük bir işlemin önüne geçmek kârlıdır. Bu, bir sonraki alt başlığın konusudur.

14.4.6MEV ve sandviç saldırısı

Bekleyen işlemlerin görünür olması ile fiyat etkisinin önceden hesaplanabilmesi birleşince, işlemlerin sırasını belirleyebilen biri kâr edebilir. En bilinen yol sandviç saldırısıdır. Örnek, sabit çarpımlı havuz (1000; 1000) ile kurulur; x · y = 1 000 000. Bir kullanıcı 100 A satmak istiyor. Tek başına işlem yapsa 90,91 B alırdı.

Saldırının iki yarısı bir “sandviç” oluşturur: kullanıcının işlemi, saldırganın iki işleminin arasında kalır. Saldırganın kârı, kullanıcıya kötü fiyattan işlem yaptırmaktan gelir. Saldırgan kullanıcı adına fiyatı önceden yukarı iter, sonra kullanıcının yükselttiği fiyattan satar.

Sandviç saldırısı MEV'nin bir örneğidir. Arbitraj (havuzlar arası fiyat farkını ilk kapatan olmak) ve tasfiye (teminatı yetersiz kalan bir borcu ilk kapatan olmak) gibi başka MEV kaynakları da vardır. Ortak noktaları, sıranın değer taşımasıdır. Mekanizma tasarımı açısından temel soru şudur: sıralama gücü kimde ve bu gücün bedelini kim ödüyor? Sandviç örneğinde bedeli kullanıcı öder.

14.4.7Kod izleme: sandvic()

Kullanıcının elinde basit bir koruma vardır: kayma toleransı. Kullanıcı “en az şu kadar B almalıyım” diye bir sınır koyar. Fiyat bu sınırın altına inerse işlem iptal edilir. Aşağıdaki kod, sandviç saldırısını bu sınırla birlikte uygular.

cikti = lambda x, y, dx: y - x * y / (x + dx)  # xy=k
def sandvic(x, y, a, u, min_out):
    b1 = cikti(x, y, a)          # öne geç: a A sat
    x, y = x + a, y - b1
    b2 = cikti(x, y, u)          # kullanıcı: u A sat
    if b2 < min_out:
        return None              # işlem iptal
    x, y = x + u, y - b2
    a2 = cikti(y, x, b1)         # arkadan: b1 B sat
    return round(a2 - a, 2)
for a in [20, 50, 80]:
    print(a, sandvic(1000, 1000, a, 100, 82))

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

• cikti(x, y, dx), havuza dx birim ilk varlık satınca alınan ikinci varlık miktarıdır: y − xy/(x + dx). Bu, Tanım 14.11'deki formülün aynısıdır.
• b1: saldırgan a A satıp b1 B alır. Havuz güncellenir.
• b2: kullanıcı u A satıp b2 B alır. b2, kullanıcının sınırı min_out'tan küçükse işlem iptal edilir ve fonksiyon None döndürür.
• a2: saldırgan b1 B'yi geri satar. Bu kez havuza B girer ve A çıkar; bu yüzden fonksiyon argümanların yeri değiştirilerek çağrılır: cikti(y, x, b1).
• Fonksiyon saldırganın kârını, yani a2 − a'yı döndürür.

Kullanıcı 100 A satacak ve en az 82 B istiyor. Saldırgan öne geçme miktarı a için üç değer dener.

Şekil 14.17 sonucu özetler. Daha büyük bir öne geçme, fiyatı daha çok iter ve daha çok kâr getirir. Ama kullanıcının kayma sınırı bunu keser: a = 80'de kullanıcı yalnızca 78,47 B alacağı için işlem iptal olur ve saldırgan hiçbir şey kazanamaz. Bu yüzden saldırganın en iyi hamlesi, kullanıcının sınırını tam zorlayan öne geçme miktarıdır. Sıkı bir tolerans, saldırganın alanını daraltır ve MEV'ye karşı basit bir korumadır.

14.4.8MEV'ye karşı önlemler

MEV'ye karşı önerilen yöntemler beş fikirde toplanabilir. Her birinin bir bedeli vardır.

İlk üç yöntem saldırganın ya bilgisini ya da alanını kısıtlar. Taahhüt–açıklama ve şifreli havuz, işlemin içeriğini sıra belirlenene kadar gizler; saldırgan neyin önüne geçeceğini bilemez. Bu fikir, kapalı zarf açık artırmasının mantığına benzer: teklifler, herkes teklifini verdikten sonra açılır.

Toplu açık artırma sandviçi tamamen etkisiz kılar. Bir zaman dilimindeki bütün alış ve satış emirleri tek bir fiyattan eşleşir. Saldırganın “önden alış” ve “arkadan satış” emirleri kullanıcınınkiyle aynı partide, aynı fiyattan gerçekleşir. Alış ile satış fiyatı aynı olduğu için kâr 0'dır. Sıra artık değer taşımaz.

Son yöntem farklı bir yaklaşımdır: MEV'yi ortadan kaldırmaya çalışmak yerine onu açıkça fiyatlar. Sıralama hakkı bir açık artırmayla satılınca, MEV'den elde edilecek değer rekabet yoluyla bu hakkın fiyatına yansır. Ama bu yöntem gücün az sayıda büyük aktörde toplanmasına yol açabilir.

Bu önlemlerin uygulamadaki biçimleri sık değişir. Kalıcı fikir şudur: sıralama gücü değer taşır ve bu değer ya azaltılmalı (gizleme, toplu eşleştirme) ya da açıkça fiyatlanmalıdır (açık artırma). Bu, mekanizma tasarımının genel bir dersidir: bir kaynak (burada sıra) değerliyse ve bedelsiz dağıtılıyorsa, onu ele geçirmek için gizli bir rekabet doğar.

14.5Ölçek ve açık sorular

Önceki kısımlardaki örnekler birkaç oyuncu ve birkaç seçenekle çalıştı. Gerçek uygulamalarda oyuncu, nesne ve strateji sayıları çok büyüktür. Bu kısım ölçeğin getirdiği hesaplama sorunlarını, bunlara karşı geliştirilen yaklaşık yöntemleri ve alanın açık sorularını ele alır.

14.5.1Hesaplama ve ölçek

Oyun kuramının kavramları hesaplanabilir olmalıdır. Bir dengenin var olduğunu bilmek, onu bulabileceğimiz anlamına gelmez. Bu konuda dört gözlem öne çıkar.

• Denge bulmak zor olabilir. Genel oyunlarda Nash dengesi bulmak PPAD-tam bir problemdir. Yani büyük oyunlar için verimli (polinom zamanlı) bir algoritma beklenmez. Pratikte kesin denge yerine yaklaşık denge ve öğrenme dinamikleri kullanılır: oyuncular tekrar tekrar oynayıp pişmanlıklarını azaltacak biçimde stratejilerini günceller.
• Öğrenme ve arama birlikte güçlüdür. Çok oyunculu pokerde insan üstü sonuçlar, pişmanlığı en aza indiren algoritmalar ile aramanın birleştirilmesiyle elde edildi (Brown ve Sandholm, 2019). Poker eksik bilgili, çok oyunculu ve devasa bir oyundur; kesin denge hesaplanamaz ama iyi bir yaklaşık strateji bulunabilir.
• Kombinatoryal açık artırma zordur. Birden çok nesnenin paketler hâlinde satıldığı açık artırmalarda kazananı belirlemek NP-zordur. Bu yüzden teklif dili (teklifçilerin hangi paketlere nasıl değer bildirebileceği) dikkatle tasarlanır ve yaklaşık algoritmalar kullanılır.
• Kuram dışı maliyetler de önemlidir. Kuramsal bir garanti kadar gecikme, veri erişimi ve enerji maliyeti de bir mekanizmanın uygulanabilirliğini belirler. Bir reklam açık artırması milisaniyeler içinde bitmelidir; daha iyi ama yavaş bir kural işe yaramaz.

Ölçek sorununun kaynağı, olasılıkların üstel büyümesidir. m nesnelik bir açık artırmada her nesne bir pakette ya vardır ya yoktur. Bu yüzden alt küme sayısı 2^m'dir; boş paket çıkarılınca 2^m − 1 paket kalır.

Her teklifçi her pakete bir değer bildirirse, girdi nesne sayısıyla üstel büyür. 30 nesnede bir teklifçinin bildireceği değer sayısı bir milyarı aşar. Aynı patlama oyunlarda da görülür: iki eylemli n oyunculu bir oyunda strateji profili sayısı 2ⁿ'dir; n = 20 için 1.048.576 profil vardır. Bir kazanç matrisini tablo olarak yazmak bile mümkün olmayabilir. Bu yüzden büyük oyunlar, tıkanıklık oyunlarında olduğu gibi, kısa bir yapıyla (örneğin yol başına bir gecikme fonksiyonuyla) tanımlanır.

14.5.2Kombinatoryal açık artırmada kazanan belirleme

Kombinatoryal açık artırmada teklifçiler tek tek nesnelere değil, nesne paketlerine teklif verir. Örneğin bir telekomünikasyon firması iki komşu bölgenin frekans lisansını birlikte istiyor olabilir; tek başına bir bölge ona az değer ifade eder. Açık artırmacı hangi tekliflerin kazanacağına karar vermelidir.

Bu problem, bilgisayar biliminde ağırlıklı küme paketleme (weighted set packing) olarak bilinen problemle aynıdır. NP-zordur ve genel durumda iyi yaklaştırılamaz: verimli bir algoritmanın her girdide optimuma belirli bir oranda yakın kalacağı garanti edilemez. Kaba kuvvet yöntemi n teklif için 2ⁿ alt kümeyi dener. Pratikte bu aramayı akıllıca budayan (umut vermeyen dalları erken kesen) tam sayılı programlama çözücüleri kullanılır.

Kazanan belirlemenin zorluğu VCG mekanizmasını da etkiler. VCG'de her kazanan, varlığıyla ötekilere verdiği zararı öder. Bunu hesaplamak için problem bir kez bütün tekliflerle, sonra her teklifçi bir kez çıkarılarak çözülür; toplam n + 1 çözüm gerekir. Problem yaklaşık çözülürse VCG'nin doğruluk garantisi bozulabilir. Çünkü bir teklifçi, yalan söyleyerek yaklaşık algoritmanın hatasından yararlanabilir ve kendi lehine daha iyi bir dağıtım elde edebilir.

14.5.3Kod izleme: acgozlu()

NP-zor problemlerde sık kullanılan bir yaklaşım açgözlü (greedy) seçimdir: teklifler bir anahtara göre sıralanır ve sırayla, öncekilerle çakışmayan her teklif alınır. Sonucu belirleyen, hangi anahtarın kullanıldığıdır.

def acgozlu(teklifler, anahtar):
    sirali = sorted(teklifler, key=anahtar, reverse=True)
    toplam, kullanilan = 0, set()
    for S, v in sirali:
        if not (S & kullanilan):  # çakışma yok
            toplam += v
            kullanilan |= S
    return toplam
T = [({'a','b','c'}, 10), ({'a'}, 4), ({'b'}, 4), ({'c'}, 3)]
print(acgozlu(T, lambda t: t[1]))
print(acgozlu(T, lambda t: t[1] / len(t[0])))

Kod satır satır şöyle çalışır. sirali, teklifleri verilen anahtara göre büyükten küçüğe sıralar. toplam seçilenlerin değerini, kullanilan seçilen paketlerdeki nesneleri tutar. Döngü her teklif için paketin kullanılmış nesnelerle kesişimine bakar (S & kullanilan). Kesişim boşsa teklif alınır: değeri toplama eklenir, nesneleri kullanılmış kümeye katılır (|=). Kod iki anahtarla çalıştırılır: önce teklifin değeri, sonra nesne başına değer.

Şekil 14.18 ilk anahtarın sonucunu gösterir. Değere göre sıralama, büyük paketi erken alır ve küçük tekliflerin hepsini dışarıda bırakır. Sonuç 10'dur; optimum 11 idi. Değere göre açgözlü seçim büyük paketlere aldanır, çünkü bir paketin değerini kullandığı kaynakla karşılaştırmaz.

Şekil 14.19'da ikinci anahtar kullanılır. Nesne başına değerler t2 ve t3 için 4, t1 için 10/3 ≈ 3,33, t4 için 3'tür. t2 ile t3 eşittir; Python'un sorted fonksiyonu eşitlikte ilk sırayı korur. Bu sıralama, değeri kaynağa göre ölçtüğü için optimumu bulur.

Ama bu anahtar da yanılabilir. ({a, b}, 10) ve ({a}, 6) tekliflerini düşünelim. Nesne başına değerler 5 ve 6'dır; açgözlü seçim önce 6'yı alır, sonra 10'u çakıştığı için atlar ve 6'da kalır. Oysa 10'luk teklif tek başına daha iyidir. Her iki anahtarın da kötü örnekleri vardır. Lehmann, O'Callaghan ve Shoham (2002), değeri paket büyüklüğünün kareköküne bölen bir anahtar önerdi: v / √|S|. Bu anahtarla açgözlü seçim, en kötü durumda bile optimumun en az 1/√m'i kadar değer garanti eder (m nesne sayısı). Ayrıca bu açgözlü algoritma, uygun ödeme kuralıyla birleşince teklifçilerin tek fikirli olduğu durumda doğruluğu korur.

14.5.4Diğer araştırma yönleri

Bölümün ana konuları dışında dört araştırma yönü daha öne çıkar.

Sosyal ağlarda etki maksimizasyonu. Bir firma k kişiye ücretsiz ürün verecek ve bu kişilerin ürünü arkadaşlarına yaymasını umuyor. Yayılmayı en büyük yapacak k “tohum” kişi kimdir (Kempe, Kleinberg ve Tardos, 2003)? Yayılma bir modelle tanımlanır.

En iyi tohum kümesini bulmak NP-zordur. Ama problemin bir yapısı vardır: beklenen yayılım alt modülerdir (submodular), yani azalan marjinal getirilidir. Bir kişiyi tohum yapmanın ek katkısı, tohum kümesi büyüdükçe azalır; çünkü onun ulaşacağı kişilere başka tohumlar zaten ulaşmış olabilir. Bu yapı sayesinde basit bir açgözlü algoritma iyi çalışır: her adımda beklenen yayılıma en çok katkı yapan kişiyi ekle. Bu algoritma, en iyi yayılımın en az 1 − 1/e ≈ %63'ünü garanti eder. Kazanan belirleme probleminin aksine burada yapı, açgözlü seçime güçlü bir garanti verir.

Çok ajanlı pekiştirmeli öğrenme

Her ajanın ortamı, öğrenen diğer ajanları da içerir. Bir ajan öğrenirken ötekiler de değiştiği için ortam durağan değildir. Tek ajanlı öğrenmedeki yakınsama garantileri, ortamın sabit olduğunu varsayar; bu yüzden burada geçerli değildir. Algoritmik danışıklılık bu sorunun bir örneğidir.

Sürdürülebilir sistemler

Karbon emisyon izni piyasaları ve elektrikte talep yanıtı gibi mekanizmalar, dışsallığı fiyatlar. Bir oyuncunun başkalarına yüklediği maliyet ona bir vergiyle ödetilir (Pigou vergisi). Bu, tıkanıklık ücretlendirmesindeki fikrin aynısıdır.

Dayanıklılık

Saldırgan, hatalı ya da sınırlı rasyonel oyunculara rağmen iyi çalışan mekanizmalar. Klasik kuram herkesin rasyonel olduğunu varsayar; gerçek sistemlerde bazı katılımcılar bu varsayıma uymaz.

Bunlara ek olarak şu yönler de etkindir: bilgi tasarımı ya da Bayesçi ikna (bilgiyi açıklama kuralını seçerek alıcının kararını yönlendirmek); yapay zekâ hizalamasında insan tercihlerini toplamak (birçok kişinin tercihlerinden tek bir hedef üretmek bir sosyal seçim problemidir); tahmin piyasaları; ve doğrulanamayan raporları, başkalarının raporlarıyla karşılaştırarak ödüllendiren eşler arası tahmin yöntemleri.

14.5.5Açık araştırma soruları

Alanın bugün cevabı aranan soruları altı başlıkta toplanabilir. Bu sorular belirli bir teknolojiye değil, bölüm boyunca görülen kalıcı gerilimlere dayanır.

İnsan + yapay zekâ pazarları

İnsanlar ve ajanlar aynı pazarda etkileştiğinde kurallar nasıl değişmeli? Ajanlar hızlı ve yorulmazdır; insanlar yavaş ve sınırlı dikkatlidir. Aynı kural iki gruba farklı etki edebilir.

Ödünleşimleri ölçmek

Verimlilik, mahremiyet ve adalet arasındaki ödünleşimler nasıl ölçülmeli? Üstel mekanizmada ε küçüldükçe mahremiyet artar ama gelir düşer; bu tür ödünleşimlerin ortak bir dili yoktur.

Uyarlanabilir dayanıklılık

Stratejiye dayanıklı mekanizmalar, değişen davranışlara nasıl uyarlanır? Bir mekanizma öğrenerek uyarlanırsa, öğrenme sürecinin kendisi manipüle edilebilir.

Kuram ve veri

Modellerin varsayımları gerçek platform verileriyle nasıl sınanır? Kuram belirli değer dağılımları ve rasyonellik varsayar; veriler bu varsayımları doğrulamayabilir.

Öğrenen ajanların dengesi

Birbirine karşı öğrenen algoritmalar hangi sonuca yakınsar ve danışıklılık nasıl önlenir?

Doğrulanabilir mekanizma

Öğrenilmiş bir kuralın teşvik uyumlu olduğu nasıl kanıtlanır ya da denetlenir? Elle tasarlanan kurallar için ispat vardır; sinir ağı kuralları için yalnızca ölçülmüş pişmanlık vardır.

14.6Değerlendirme: sık hatalar ve örnek problemler

Bu kısım bölümün sayısal sonuçlarını bir tabloda toplar, en sık hataları bir arada listeler ve sunumdaki örnek problemleri çözümleriyle verir.

Aşağıdaki altı örnek problem, bölümün hesaplarını kısa biçimde tekrar eder.

Bölümün konuları iki etkileşimli oyunla da çalışılabilir. Yapay Zekâ Ajan Turnuvası, sabit, uyarlanabilir ve öğrenen ajanları Mahkûmun İkilemi, Yazı-Tura Eşleştirme, Koordinasyon Oyunu ve Taş-Kağıt-Makas'ta yarıştırır; 14.2.7'deki sonuçlar burada farklı oyunlarda denenebilir. Age of Çotanak, bir öğrenci projesinden doğan bölge kontrol oyunudur; yapay zekâ rakibi düşmanca arama kullanır. Proje için basit bir başlangıç noktası ise pizza oylamasıdır: üç arkadaş tek pizzada anlaşmalıdır, her biri malzeme önerir ve sonra oylarlar. Küçük bir konsol uygulaması bile oylama kuralını ve stratejik oyu gösterir (14.12.4).

14.7Özet

• Yazılım ajanları artık oyuncudur: hedefi, bilgisi ve stratejisi vardır. Asil–vekil sorunu, çerçevelemeye duyarlılık, istem enjeksiyonu ve sorumluluk, ajanlarla birlikte yeniden önem kazanan oyun kuramı sorularıdır.
• Sonlu ufuklu sırayla teklif pazarlığı geriye doğru çıkarımla çözülür; son söz hakkı güçtür. 100 TL, δ = 0,9 ve dört turda ilk öneren yalnızca 18,1 alır.
• Sonsuz ufukta Rubinstein çözümü ilk önerene (1 − δ_B)/(1 − δ_Aδ_B) payını verir; simetrik sabırda 1/(1 + δ). Sabır pazarlık gücüdür.
• Kinci tetik stratejisi, δ ≥ 1 − 1/n ise danışıklılığı sürdürür. Sık fiyat güncelleme, şeffaf fiyatlar ve fiyat eşleme garantisi danışıklılığı kolaylaştırır; öğrenen fiyat algoritmaları açık anlaşma olmadan yüksek fiyat öğrenebilir.
• Evrensel en iyi strateji yoktur: bir ajanın başarısı oyuna, rakiplere, gürültüye ve hafızaya bağlıdır.
• Otomatik mekanizma tasarımı, kuralı IC ve IR kısıtlı bir optimizasyonun çözümü olarak bulur. İki tipli örnekte optimum doğrusal programın bir köşesidir ve bir ilan edilmiş fiyata karşılık gelir.
• Deneysel gelir maksimizasyonu, aynı veride seçilip ölçüldüğü için başarısını abartır (0,294'e karşı gerçek 0,249). Örneklem karmaşıklığı, iyi bir fiyat için kaç örnek gerektiğini sorar; seçim ve ölçüm için ayrı veri gerekir.
• Üstel mekanizma, adayları exp(ε · R / 2Δ) ile orantılı olasılıkla seçer; ε-diferansiyel mahremiyet ve yaklaşık teşvik uyumluluğu sağlar.
• Akıllı sözleşme taahhüdü kodla sağlar ama bekleyen işlemleri görünür kılar. Taban ücret + bahşiş kuralı, kullanıcı için teklifi basitleştirir; taban ücret talebe göre blok başına en çok %12,5 değişir ve sahte talebi pahalı kılmak için yakılır.
• Kullanıcı, üretici ve danışıklılık hedeflerinin üçü birlikte, blok alanı kıtken tam sağlanamaz.
• Sabit çarpımlı piyasa yapıcıda fiyat etkisi önceden hesaplanabilir; bu, sandviç saldırısını mümkün kılar. MEV, sıralama gücünün değeridir; önlemler bu değeri ya azaltır ya da açıkça fiyatlar. Sıkı kayma toleransı en basit korumadır.
• Kombinatoryal açık artırmada kazanan belirleme NP-zordur; açgözlü kurallar yaklaşıktır ve anahtar seçimi sonucu belirler. Etki maksimizasyonunda ise alt modülerlik, açgözlü seçime 1 − 1/e garantisi verir.

14.8Kavram listesi

• asil–vekil sorunu principal–agent problem
• çerçeveleme etkisi framing effect
• istem enjeksiyonu prompt injection
• geriye doğru çıkarım backward induction
• alt oyun mükemmel denge subgame perfect equilibrium
• iskonto faktörü discount factor
• Rubinstein pazarlık modeli Rubinstein bargaining model
• durağan strateji stationary strategy
• danışıklılık collusion
• algoritmik danışıklılık algorithmic collusion
• kinci tetik stratejisi grim trigger strategy
• pekiştirmeli öğrenme reinforcement learning
• otomatik mekanizma tasarımı automated mechanism design
• yaklaşık teşvik uyumluluğu approximate incentive compatibility
• deneysel gelir empirical revenue
• aşırı uyum overfitting
• örneklem karmaşıklığı sample complexity
• çapraz doğrulama cross-validation
• diferansiyel mahremiyet differential privacy
• üstel mekanizma exponential mechanism
• akıllı sözleşme smart contract
• taahhüt commitment
• bekleme havuzu mempool
• işlem ücreti mekanizması transaction fee mechanism
• taban ücret base fee
• bahşiş tip
• ücret yakma fee burning
• otomatik piyasa yapıcı automated market maker
• kayma toleransı slippage tolerance
• fiyat etkisi price impact
• MEV (maksimum elde edilebilir değer) maximal extractable value
• sandviç saldırısı sandwich attack
• öne geçme front-running
• arkadan gelme back-running
• toplu açık artırma batch auction
• kombinatoryal açık artırma combinatorial auction
• kazanan belirleme problemi winner determination problem
• NP-zor NP-hard
• PPAD-tam PPAD-complete
• etki maksimizasyonu influence maximization
• bağımsız çağlayan modeli independent cascade model
• alt modülerlik submodularity
• çok ajanlı pekiştirmeli öğrenme multi-agent reinforcement learning
• Pigou vergisi Pigouvian tax
• bilgi tasarımı (Bayesçi ikna) information design
• tahmin piyasası prediction market
• eşler arası tahmin peer prediction
• tekrarlanabilirlik reproducibility
• güven aralığı confidence interval
• Borda sayımı Borda count
• Condorcet kazananı Condorcet winner

14.9Kendini Dene

1. İki ajan 100 TL'yi üç turda paylaşacak: A 1. ve 3. turlarda, B 2. turda önerir; δ = 0,8. Geriye doğru çıkarımla dengedeki paylaşımı bulun. Sonsuz ufukta, A'nın sabrı δ_A = 0,8 ve B'ninki δ_B = 0,9 olsaydı A'nın payı ne olurdu?

   Cevap

   Tur 3'te son söz A'dadır: A 100. Tur 2'de B, A'ya bekleme değeri 0,8 · 100 = 80'i önerir: A 80, B 20. Tur 1'de A, B'ye 0,8 · 20 = 16 önerir: A 84, B 16 ve öneri hemen kabul edilir. Sonsuz ufukta x* = (1 − 0,9)/(1 − 0,72) = 0,1/0,28 ≈ 0,357: A 35,7 alır. Son sözü kaybedip daha sabırsız olan A, ilk öneren olduğu hâlde azınlıkta kalır.

2. İki firma tekel fiyatında her dönem 50'şer kâr ediyor. Fiyat kıran firma her dönem 100 alıyor; ancak rakip fiyat kırıldığını iki dönem sonra fark ediyor, yani sapan iki dönem boyunca 100 alıyor, sonra sonsuza dek 0. Kinci tetik stratejisi hangi δ için işbirliğini sürdürür? Anında fark edilen duruma göre eşik nasıl değişti?

   Cevap

   İşbirliği 50/(1 − δ), sapma 100 + 100δ değerindedir. Koşul 50/(1 − δ) ≥ 100(1 + δ) ⟺ 50 ≥ 100(1 − δ)(1 + δ) = 100(1 − δ²) ⟺ δ² ≥ 1/2 ⟺ δ ≥ 0,707. Anında fark edilince eşik 0,5 idi. Gecikmeli fark etme sapmayı daha kârlı kılar ve gereken sabrı artırır; şeffaf fiyatların danışıklılığı kolaylaştırmasının nedeni budur.

3. Geçmişte gözlenen 5 alıcı değeri 0,8; 0,7; 0,3; 0,25; 0,1'dir. Deneysel geliri maksimize eden fiyat ve gelir nedir? Değerler gerçekte U[0, 1]'den geliyorsa bu fiyatın gerçek geliri kaçtır?

   Cevap

   Gelirler 0,8 · 1/5 = 0,16; 0,7 · 2/5 = 0,28; 0,3 · 3/5 = 0,18; 0,25 · 4/5 = 0,2; 0,1 · 5/5 = 0,1. En iyisi p = 0,7, deneysel gelir 0,28. Gerçek gelir 0,7 · 0,3 = 0,21'dir; en iyi 0,25'in altında kalır. Beş örnek, fiyatı gerçek en iyiden (0,5) uzağa götürmüştür ve deneysel gelir yine iyimserdir.

4. Üstel mekanizmada üç aday fiyatın puanları 0, 1 ve 2'dir; ε = 1, Δ = 1. Seçim olasılıklarını bulun. En iyi adayın olasılığı en kötününkünün kaç katıdır?

   Cevap

   Ağırlıklar exp(R/2): e⁰ = 1, e^0,5 ≈ 1,649, e¹ ≈ 2,718; toplam ≈ 5,367. Olasılıklar ≈ 0,186; 0,307; 0,506. En iyi aday, en kötünün e¹ ≈ 2,72 katı olasılık alır; puan oranı (2/0) ile ilgisi yoktur.

5. Taban ücret 200'dür. Sıradaki dört blok %100, %100, %0, %0 doludur. Dördüncü bloktan sonra taban ücret kaç olur? Ücret neden 200'e geri dönmez?

   Cevap

   200 → 200 · 1,125 = 225 → 253,125 → 253,125 · 0,875 ≈ 221,48 → ≈ 193,80. Değişim çarpımsaldır ve 1,125 · 0,875 ≈ 0,984 < 1'dir; eşit sayıda dolu ve boş blok ücreti biraz düşürür.

6. Sabit çarpımlı havuz (2000; 2000)'dir. Bir kullanıcı 200 A satıyor. Kaç B alır ve kayma yüzde kaçtır? Bu sonucu, (1000; 1000) havuzunda 100 A satmakla karşılaştırın.

   Cevap

   Δy = 2000 · 200 / 2200 ≈ 181,82 B; kayma 1 − 181,82/200 ≈ %9,1. (1000; 1000) havuzunda 100 A satmak da %9,1 kayma verir. Kayma Δx/(x + Δx)'e, yani işlemin havuza göre büyüklüğüne bağlıdır; derin havuz aynı işlemi daha az kaymayla taşır.

7. Dört paket teklifi: t1 = ({a, b}, 6), t2 = ({b, c}, 6), t3 = ({a}, 4), t4 = ({c}, 4). Değere göre ve nesne başına değere göre açgözlü seçim hangi toplamları verir? Optimum nedir?

   Cevap

   Değere göre sıra t1, t2, t3, t4: t1 alınır (a, b); t2 b yüzünden, t3 a yüzünden atlanır; t4 alınır. Toplam 10. Nesne başına değer t3 ve t4 için 4, t1 ve t2 için 3'tür: t3 ve t4 alınır, t1 (a) ve t2 (c) çakışır. Toplam 8. Optimum 10'dur ({t1, t4} ya da {t2, t3}). Bu kez nesne başına değer küçük paketlere aldanır.

8. Bir ajan turnuvasında bir eşleşme 25 kez tekrarlanıyor; ortalama skor 3,1, standart sapma 0,5. Yaklaşık %95 güven aralığı nedir? Tekrar sayısı 100'e çıkarılırsa aralığın genişliği nasıl değişir?

   Cevap

   Yarı genişlik 1,96 · 0,5 / √25 = 1,96 · 0,1 ≈ 0,196; aralık yaklaşık [2,90; 3,30]. 100 tekrarda √100 = 10 olur ve yarı genişlik ≈ 0,098'e iner: dört kat tekrar, aralığı yarıya daraltır.

14.10İleri okuma

• T. Roughgarden, Twenty Lectures on Algorithmic Game Theory (2016): mekanizma tasarımı, kombinatoryal açık artırmalar ve öğrenme dinamiklerini bilgisayar bilimi bakışıyla, kısa derslerle anlatır.
• T. Roughgarden, “Transaction Fee Mechanism Design” (2021): işlem ücreti mekanizmalarının hedeflerini (kullanıcı ve üretici teşvik uyumu, danışıklılığa dayanıklılık) biçimsel olarak tanımlar ve taban ücret kuralını bu hedeflerle çözümler.
• E. Calvano, G. Calzolari, V. Denicolò, S. Pastorello, “Artificial Intelligence, Algorithmic Pricing, and Collusion” (2020): öğrenen fiyat ajanlarının iletişim kurmadan yüksek fiyat öğrenip sapmaları cezalandırdığı benzetimleri ayrıntılı verir.
• D. Easley, J. Kleinberg, Networks, Crowds, and Markets (2010): ağlarda yayılma, pazarlık ve piyasaları az matematikle, çok örnekle anlatır.

14.11Kaynaklar

1. R. Axelrod, “Effective choice in the Prisoner's Dilemma”, Journal of Conflict Resolution 24(1), 1980.
2. N. Brown, T. Sandholm, “Superhuman AI for multiplayer poker”, Science, 2019.
3. E. Calvano, G. Calzolari, V. Denicolò, S. Pastorello, “Artificial Intelligence, Algorithmic Pricing, and Collusion”, American Economic Review, 2020.
4. H. Chung, E. Shi, “Foundations of transaction fee mechanism design”, ACM-SIAM SODA, 2023.
5. H. Chung, T. Roughgarden, E. Shi, “Collusion-resilience in transaction fee mechanism design”, ACM EC, 2024.
6. R. Cole, T. Roughgarden, “The Sample Complexity of Revenue Maximization”, ACM STOC, 2014.
7. V. Conitzer, T. Sandholm, “Complexity of Mechanism Design”, UAI, 2002.
8. P. Daian ve diğ., “Flash Boys 2.0: Frontrunning in Decentralized Exchanges, Miner Extractable Value, and Consensus Instability”, IEEE S&P, 2020.
9. P. Dütting, Z. Feng, H. Narasimhan, D. Parkes, S. Ravindranath, “Optimal Auctions through Deep Learning”, ICML, 2019.
10. D. Easley, J. Kleinberg, Networks, Crowds, and Markets, Cambridge University Press, 2010.
11. R. A. Hearn, E. D. Demaine, Games, Puzzles, and Computation, A K Peters, 2009.
12. A. R. Karlin, Y. Peres, Game Theory, Alive, AMS, 2017.
13. D. Kempe, J. Kleinberg, É. Tardos, “Maximizing the Spread of Influence through a Social Network”, KDD, 2003.
14. D. Lehmann, L. I. O'Callaghan, Y. Shoham, “Truth revelation in approximately efficient combinatorial auctions”, Journal of the ACM 49(5), 2002.
15. F. McSherry, K. Talwar, “Mechanism Design via Differential Privacy”, IEEE FOCS, 2007.
16. N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory, Cambridge University Press, 2007.
17. T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
18. T. Roughgarden, “Transaction Fee Mechanism Design”, ACM EC, 2021.
19. A. Rubinstein, “Perfect Equilibrium in a Bargaining Model”, Econometrica 50(1), 1982.

14.12Ek: dersin haritası ve proje

Bu ek, dersin bütün bölümlerini tek bir haritada birleştirir ve bir dönem projesinin nasıl kurulacağını kısaca özetler.

14.12.1Dersin haritası

Şekil 14.20 konular arasındaki bağları gösterir. Her düğüm bir bölümdür; bir ok, sonraki konunun öncekinin hangi fikrine dayandığını belirtir.

Haritanın ana omurgası şöyle okunabilir: denge → tasarım → uygulama → öğrenme → gelecek. Tek kişilik karardan oyunlara, oyunlardan dengeye geçilir. Denge kavramı iki yöne açılır: kuralları tasarlamak (mekanizma, açık artırma, oylama) ve var olan kuralların sonucunu ölçmek (ağlar, anarşinin bedeli). Öğrenme, dengeye nasıl ulaşıldığını sorar. Bu bölümün konuları, bu dalların birleştiği yerdedir. Örneğin algoritmik danışıklılık hem tekrarlanan oyunlara hem öğrenmeye, işlem ücreti mekanizmaları hem açık artırmalara hem tıkanıklık fiyatlamasına dayanır.

14.12.2Proje yönergesi ve konu önerileri

Bir dönem projesi beş aşamada kurulur.

1. Konu: bir oyun, mekanizma ya da platform seçilir ve haritadaki bir konuya bağlanır.
2. Model: oyuncular, stratejiler, kazançlar ve bilgi yapısı (kim neyi biliyor) açıkça yazılır.
3. Analiz: Nash dengesi, Pareto optimallik, teşvik uyumluluğu ya da anarşinin bedeli hesaplanır; sonuçlar hem elle hem kodla doğrulanır.
4. Uygulama: etkileşimli bir web uygulaması yapılır; kullanıcı oynar ve sonucu görür.
5. Anlatım: model, algoritma ve gerçek dünya bağlantısını anlatan bir blog yazısı ya da rapor yazılır; kod açık bir depoda paylaşılır.

Araç olarak Python ve Jupyter ya da JavaScript yeterlidir; dengeler Nashpy veya Gambit ile doğrulanabilir. Geliştirme aşamalı olmalıdır: basit bir konsol sürümü modeli erkenden sınar, özellikler sonra eklenir ve her adım test edilir. Proje genişletilmek istenirse kazançları girip dengeyi görsel izleten bir simülatör yapılabilir ya da kısa bir makale özetlenip kodlanabilir.

İyi bir projenin dört özelliği vardır: doğru model, test edilmiş hesap (denge ve ödemeler betikle doğrulanmış), anlaşılır arayüz ve açık anlatım.

14.12.3Tekrarlanabilir deney protokolü

Dil modeli ajanlarının hamleleri rastgeledir: aynı eşleşme iki kez farklı skor verebilir. Bir sonuç, başka biri aynı deneyi tekrarlayıp aynı sonucu alabiliyorsa güvenilirdir. Buna tekrarlanabilirlik (reproducibility) denir. Bir ajan turnuvası deneyinde şunlar kayda geçirilir:

• sabit rastgele tohum (random seed);
• istemin (prompt) tam metni;
• kullanılan modelin sürümü ve sıcaklık (temperature) değeri;
• rakip sırası ve tur sayısı: sabit tutulur ve raporda yazılır.

Raporda ise şunlar verilir:

• her eşleşme en az N kez tekrarlanır (örneğin N = 30);
• ortalama ile birlikte yayılım: standart sapma ya da %95 güven aralığı;
• kod ve oyun kayıtları açık bir depoda paylaşılır.

Güven aralığı (confidence interval), tek bir ortalama yerine, gerçek ortalamanın büyük olasılıkla içinde bulunduğu bir aralık verir. N tekrarın ortalaması m ve standart sapması s ise yaklaşık %95 güven aralığı m ± 1,96 · s / √N'dir. Burada s/√N, ortalamanın kendi belirsizliğidir; tekrar sayısı arttıkça küçülür.

14.12.4Örnek proje: pizza oylaması

Küçük bir örnek, proje aşamalarının hepsini taşıyabilir. Üç arkadaş tek bir pizzada anlaşmalıdır. Tercihleri şöyledir:

Bu bulgu, Borda sayımında gömme stratejisinin (güçlü rakibi sıralamanın sonuna atmak) bir örneğidir ve Gibbard–Satterthwaite teoreminin küçük bir yansımasıdır. Projenin uygulama aşaması şöyle kurulabilir. Konsol sürümü sıralamaları alır ve çoğunluk, iki turlu, Borda, Condorcet ve onay oylaması kurallarını yan yana sayar. Web sürümünde kullanıcı bir oyuncunun bildirimini değiştirir ve kazananın nasıl kaydığını görür. Rapor bulguyu (Borda'da gömme stratejisi), kodu ve beraberlik kuralının etkisini anlatır. Küçük bir örnek bile modelleme, analiz, kod ve anlatım aşamalarının hepsini taşır; ölçek sonra büyütülür.

Ders sayfaları: Roughgarden CS364A · Shah CSC304 · Araçlar: Gambit, Nashpy · Networks, Crowds, and Markets · © Sercan Külcü. Tüm hakları saklıdır.