Bölüm 10: Çoklu Ajan Sistemleri

10.1Ajanlar ve çoklu ajan sistemleri

Önceki konularda oyuncular çoğu zaman insanlardı: açık artırmada teklif veren alıcılar, oy veren seçmenler, pazar yerinde alışveriş yapan kullanıcılar. Bu bölümde oyuncuların önemli bir kısmı yazılımdır: robotlar, drone'lar, otonom araçlar, alım satım programları. Bu yazılımlara ajan denir. Ajanlar insan gibi düşünmez, ama insan gibi kendi hedefini izler ve başka ajanların kararlarından etkilenir. Bu yüzden oyun kuramının araçları ajanlara da doğrudan uygulanır. Bu kesimde önce bir oyunla bölümün ana sorusunu somutlaştırıyoruz, sonra ajanı, çoklu ajan sistemini, ajanların karar mimarilerini ve gerçek uygulamaları tanımlıyoruz.

10.1.1Bir oyunla başlangıç: Shapley koalisyon oyunu

Üç oyuncu, A, B ve C, birlikte çalışarak bir değer üretecektir. Her oyuncunun tek başına üretebileceği bir değer vardır. İki oyuncu birlikte çalışınca, tek başına değerlerinin toplamına ek olarak bir sinerji bonusu doğar. Oyunun kuralı şöyledir: bir koalisyonun (birlikte çalışan grubun) değeri, üyelerin tek başına değerleri ile koalisyonun içindeki her ikilinin sinerji bonusunun toplamıdır. Sonunda üç oyuncunun tamamından oluşan koalisyonun değeri, v(N), oyunculara paylaştırılır.

Şekil 10.1'de oyunun örnek bir turu görülür. Tek başına değerlerin toplamı 6 + 4 + 5 = 15, sinerjilerin toplamı 4 + 2 + 0 = 6'dır. Üçü birlikte çalışınca v(ABC) = 15 + 6 = 21 birim üretilir. Oyun iki merak sorusu sorar:

• 21 birim eşit bölünürse herkes 7 alır. Bu paylaşımda A haksızlığa uğrar mı?
• Tek başına en değerli oyuncu her zaman en büyük payı mı almalıdır?

Eşit bölüşüm ilk bakışta adil görünür. Ancak A hem tek başına en değerli oyuncudur (6) hem de iki sinerjinin (4 ve 2) ortağıdır. B ise yalnız bir sinerjiye (4) katkı verir, C de yalnız bir sinerjiye (2). Bir paylaşımın “adil” sayılması için her oyuncunun katkısını ölçen bir kural gerekir. Bu kural Shapley değeridir ve 10.4.5'te tanımlanır. Oyunun cevabı 10.4.8'de hesaplanır: A'nın Shapley payı 9'dur, yani eşit bölüşüm A'ya katkısının 2 birim altında bir pay verir. İkinci sorunun cevabı da genel olarak “hayır”dır. Paylaşımı belirleyen şey tek başına değer değil, oyuncunun bütün olası gruplara kattığı değerin ortalamasıdır.

Bu oyun, bölümün iki büyük temasını birleştirir. Birincisi, ajanların birlikte çalışarak tek başlarına üretemeyecekleri bir değer üretmesidir (işbirliği). İkincisi, bu değerin ajanlar arasında nasıl bölüşüleceğidir (paylaşım). Paylaşım kötü yapılırsa bazı ajanlar gruptan ayrılmak ister ve işbirliği dağılır. Bölümün geri kalanı bu iki temanın üzerine kuruludur.

10.1.2Çoklu ajan sistemi nedir?

Tanımın üç parçası önemlidir. Birincisi “birden fazla”dır: tek bir ajanın sorunu bir karar sorunudur, birden fazla ajanın sorunu bir oyundur. İkincisi “otonom”dur: ajanlar kararlarını bir merkezden emir alarak değil, kendileri verir. Üçüncüsü “aynı çevre”dir: bir ajanın eylemi çevreyi değiştirir ve bu değişiklik diğer ajanların algısını ve kazancını etkiler.

Şekil 10.2 bu yapıyı özetler. Her ajanın çevreyle iki yönlü bir bağı vardır: algı ve eylem. Ajanlar ayrıca birbirleriyle mesajlaşabilir. Bu şeklin önemli bir özelliği, hiçbir ajanın çevrenin tamamını görmemesidir. Her ajanın bilgisi yereldir. Bir depo robotu yalnız kendi çevresindeki rafları görür. Bir drone yalnız kendi uçtuğu bölgeyi tarar. Bir otonom araç yalnız yakınındaki araçları algılar. Bu yüzden çoklu ajan sistemlerinde iki tasarım sorunu her zaman ortaya çıkar:

• Koordinasyon: Ajanların kararları birbiriyle uyumlu olmalıdır. İki robot aynı rafa gitmemeli, iki drone aynı bölgeyi taramamalıdır.
• İletişim: Ajanlar eksik bilgilerini mesajlarla tamamlar. Ancak mesajlaşmanın bir maliyeti (zaman, enerji, bant genişliği) vardır ve mesajlar gecikebilir ya da kaybolabilir.

Çoklu ajan sistemlerinin tipik örnekleri robot takımları, otonom araç filoları, dağıtık sensör ağları ve trafik ya da ekonomi simülasyonlarıdır. Bu örneklerin hepsinde ajan sayısı fazladır, bilgi dağınıktır ve tek bir merkezin her şeyi hesaplaması ya imkânsız ya da çok pahalıdır.

Oyun kuramı bağlantısı. Ajanlar birbirinin kararından etkileniyorsa aralarındaki etkileşim bir oyundur. Bir oyunun dört öğesi çoklu ajan sisteminde doğrudan karşılık bulur: oyuncular ajanlardır, stratejiler ajanların eylem seçenekleridir, kazançlar ajanların hedeflerini ölçen fayda fonksiyonlarıdır, bilgi yapısı da kimin neyi gözlediğidir. Ajanları tasarlayan kişi ise iki rol üstlenir. Ajanların içini (karar kuralını) programlar, ama ajanların karşılaştığı kuralları da (kim neyi alır, kim ne öder) belirler. İkinci rol, kuralları koyan mekanizma tasarımcısının rolüdür. Mekanizma tasarımı, istenen sonucu oyuncuların kendi çıkarlarıyla seçeceği biçimde oyunun kurallarını kurmaktır.

10.1.3Ajan kavramı ve dört özelliği

“Ajan” kelimesi gündelik dilde “birinin adına iş yapan” anlamına gelir. Yapay zekâda ajan, bir çevrede kendi başına hareket eden bir yazılım ya da makinedir. Wooldridge ve Jennings (1995), bir sistemin ajan sayılması için gereken en temel özellikleri dört maddede toplar. Bu tanıma zayıf ajan tanımı denir; “zayıf” kelimesi, tanımın ajanın bilinç ya da niyet gibi insana özgü yönlerini içermediğini, yalnız gözlenebilir davranışını tarif ettiğini belirtir.

Dört özellik en iyi tek bir ajan üzerinde görülür. Bir arama-kurtarma drone'u düşünelim. Tablo 10.1 her özelliği bu drone'un bir davranışıyla eşler.

Reaktivite ile proaktivite arasındaki fark ince ama önemlidir. Reaktif davranış bir olayla tetiklenir: engel belirir, drone frenler. Olay olmasaydı davranış da olmazdı. Proaktif davranış ise bir hedefle tetiklenir: drone şarjının yolun geri kalanına yetmeyeceğini hesaplar ve henüz hiçbir uyarı yokken istasyona yönelir. Proaktif ajan geleceği öngörür, reaktif ajan şimdiye cevap verir. İyi bir ajan ikisini dengeler. Yalnız reaktif bir ajan uzun vadeli hedefleri kaçırır. Yalnız proaktif bir ajan ise planına o kadar bağlı kalabilir ki beklenmedik bir engele zamanında tepki veremez.

Sosyal yetenek, çoklu ajan sistemini tek ajanlı sistemden ayıran özelliktir. Sosyal yeteneği olmayan ajanlar aynı çevrede bulunsalar da birbirlerini yalnız çevre üzerinden etkiler. Sosyal yetenekli ajanlar ise mesajlaşır, teklif verir, anlaşma yapar. Görev tahsisi (10.3) ve koalisyon oluşumu (10.4) bu yeteneğe dayanır.

Oyun kuramında ajan. Oyun kuramı ajanın bu dört özelliğinden yalnız birini ayrıntılı modeller: ajanın kararını. Oyun kuramında ajan rasyonel bir oyuncudur. Tercihleri bir fayda fonksiyonuyla ifade edilir ve ajan beklenen faydasını maksimize etmeye çalışır. Burada “beklenen” kelimesi, sonucun belirsiz olduğu durumlarda her olası sonucun faydasının olasılığıyla ağırlıklandırılıp toplanmasını anlatır. Örneğin bir drone, yarı yarıya olasılıkla 10 ya da 4 birim fayda getirecek bir rotayı, kesin 6 birim getiren bir rotaya tercih eder; çünkü ilk rotanın beklenen faydası 0,5 · 10 + 0,5 · 4 = 7'dir.

10.1.4Ajan nasıl karar verir? Mimariler

Dört özellik ajanın ne yaptığını anlatır. Ajanın kararını nasıl verdiğini ise ajan mimarisi belirler. Mimari, algıdan eyleme giden iç yoldur. Tablo 10.2 beş yaygın mimariyi karşılaştırır.

Reaktif mimari en basit olanıdır. Ajanın içinde bir kural tablosu vardır: “önün boşsa ilerle, duvara çarptıysan rastgele dön.” Ajan çevrenin bir modelini tutmaz, geleceği hesaplamaz. Bu yüzden çok hızlıdır ve algılayıcı hatalarına karşı sağlamdır. Ev süpürge robotları bu mimariye yakındır. Sürü davranışı da reaktif kuralların ürünüdür: Reynolds (1987) her kuşun yalnız üç yerel kurala (komşulara çarpma, komşularla aynı yöne uç, komşuların merkezine yaklaş) uymasıyla gerçekçi kuş sürülerinin ortaya çıktığını göstermiştir.

Planlayan mimari çevrenin bir modelini tutar ve bu model üzerinde arama yaparak bir eylem dizisi (plan) üretir. Bir keşif robotu haritayı belleğinde tutar ve hedefe en kısa yolu hesaplar. Planlama uzun vadeli hedeflere ulaşmayı sağlar, ama yavaştır. Çevre plan bitmeden değişirse plan geçersiz kalabilir.

BDI mimarisi planlamayı insan akıl yürütmesine benzeyen üç kavramla düzenler. İnançlar ajanın çevre hakkında doğru kabul ettiği bilgilerdir (“3. pist boş”). Arzular ajanın ulaşmak istediği durumlardır (“uçak indirilsin”, “yakıt tasarrufu olsun”). Arzular birbiriyle çelişebilir. Niyetler ise ajanın arzular arasından seçip gerçekleştirmeye bağlandığı hedeflerdir (“uçağı 3. piste indir”). Niyet, ajanın her an fikir değiştirmesini önler: ajan yeni bir bilgi önemli bir değişiklik gösterene kadar niyetine bağlı kalır.

Öğrenen mimari kuralları önceden yazmaz; hangi durumda hangi eylemin iyi sonuç verdiğini deneyimden çıkarır. Öğrenilen kural bir politikadır: her duruma bir eylem (ya da eylemler üzerinde bir olasılık dağılımı) atayan fonksiyon. Bu mimari bilinmeyen çevrelere uyum sağlar. Oyun oynayan ajanlar çoğunlukla böyle çalışır.

Hibrit mimari katmanları birleştirir. Bir otonom aracın alt katmanı reaktiftir: önüne aniden bir yaya çıkarsa planlayıcıyı beklemeden fren yapar. Üst katmanı planlayıcıdır: rotayı ve şerit değiştirmeyi önceden hesaplar. Böylece hız ve öngörü birlikte sağlanır.

Bir ayrımı akılda tutmak gerekir: mimari, ajanın içini anlatır; oyun kuramı ise ajanlar arasındaki etkileşimi inceler. Bir oyun kuramı modeli ajanın içinde reaktif kurallar mı yoksa BDI mantığı mı olduğuyla ilgilenmez. Yalnız ajanın hangi stratejileri seçebildiğine ve her sonuçtan ne kazandığına bakar. Bu bölümün geri kalanında ajanlar bu soyut düzeyde, yani stratejileri ve kazançlarıyla ele alınır.

10.1.5Gerçek hayat uygulamaları

Çoklu ajan sistemleri bugün birçok alanda kullanılır. Her uygulama, bölümün ilerleyen kesimlerindeki bir oyun kuramı sorusuna bağlanır.

Otonom araçlar

Kavşakta geçiş sırası, şerit değiştirme ve konvoy sürüşü için koordinasyon gerekir. İki araç aynı anda aynı şeride geçmeye çalışırsa çarpışma riski doğar. Bu bir koordinasyon oyunudur (10.2.5).

Drone takımları

Arama-kurtarmada bölgeleri paylaşmak gerekir: hangi drone hangi bölgeyi tarayacak? Bu bir görev tahsisi problemidir (10.3).

Depo robotları

Yüzlerce robot sipariş toplar. Rotalar çarpışmasız olmalı, işler robotlara dengeli dağıtılmalıdır.

Çevrimiçi pazar yerleri

Alıcı ve satıcı ajanlar fiyat teklifi verir ve otomatik pazarlık yapar. Bu, açık artırma ve mekanizma tasarımının alanıdır.

Akıllı şebeke

Evler, enerji depoları ve üreticiler arasında enerji alışverişi yapılır ve talep yönetilir. Herkes enerjiyi pik saatte çekerse şebeke zorlanır; bu bir teşvik sorunudur (10.2.6).

Simülasyon

Trafik, salgın ve ekonomi modellerinde bireyler ajan olarak canlandırılır. Bireylerin basit kuralları sistem düzeyinde beklenmedik örüntüler üretebilir (10.2.7).

Bu uygulamaların hepsi aynı soruyu sorar: kendi hedefi olan ajanlar bir araya geldiğinde sistem düzeyinde iyi bir sonuç nasıl elde edilir? “İyi sonuç” bağlama göre değişir. Depoda toplam teslim süresinin kısa olması, şebekede toplam enerji maliyetinin düşük olması, koalisyonda kazancın adil paylaşılması iyi sonuçtur. Oyun kuramı iki soruyu ayırır. Analiz sorusu, ajanların kendi çıkarlarıyla hareket ettiğinde nereye varacağıdır (denge). Tasarım sorusu ise kuralların, varılan noktanın iyi olacağı biçimde nasıl kurulacağıdır (mekanizma).

10.1.6Ajan kavramında sık hatalar

10.2İşbirliği ve koordinasyon

Ajanların hedefleri ne kadar örtüşür? Bu soru, bir çoklu ajan sisteminde hangi sorunun çözülmesi gerektiğini belirler. Hedefler tamamen aynıysa sorun yalnız koordinasyondur: herkes aynı şeyi ister, ama kararları uyumlu hâle getirmek gerekir. Hedefler tamamen zıtsa sorun stratejidir: her ajan rakibinin hamlesini tahmin etmeye ve kendisini tahmin edilemez kılmaya çalışır. Gerçek sistemlerin çoğu bu iki uç arasındadır. Bu kesimde önce sistem türlerini, sonra bu türleri temsil eden üç küçük oyunu inceliyoruz. Ardından merkezi ve dağıtık kontrolü, konvansiyonları, teşvikleri ve öğrenmeyi ele alıyoruz.

10.2.1İşbirliği, rekabet ve karma sistemler

Çoklu ajan sistemleri, ajanların hedefleri arasındaki ilişkiye göre üç türe ayrılır.

İşbirlikçi MAS

Ajanların ortak bir hedefi vardır. Bilgi, görev ve kaynak paylaşırlar. Temel sorun koordinasyondur: kim neyi, ne zaman yapacak? Örnek: bir arama-kurtarma drone takımı. Her drone kayıp kişiyi bulmak ister; hangi drone'un bulduğu önemli değildir.

Rekabetçi MAS

Ajanların amaçları farklıdır. Her ajan diğerlerinin davranışını hesaba katarak kendi kazancını artırmaya çalışır. Temel sorun stratejidir. Örnek: bir açık artırmadaki teklifçi ajanlar. Bir teklifçinin kazandığı nesneyi diğeri kaybeder.

Karma güdülü MAS

Bazı hedefler ortak, bazı kaynaklar rekabet konusudur (mixed-motive). Örnek: aynı elektrik şebekesini paylaşan evler. Hepsi şebekenin çökmemesini ister (ortak hedef), ama ucuz saatlerdeki sınırlı enerji için yarışır (rekabet). Gerçek sistemlerin çoğu bu türdendir.

Hangi yapının daha verimli olduğu sorusunun tek bir cevabı yoktur. Tablo 10.3 iki ucun hangi koşullarda verimli olduğunu özetler.

İşbirliği, ağır bir yükü birlikte taşıyan drone'lar gibi tek ajanın yapamayacağı işlerde vazgeçilmezdir. Rekabetin üstünlüğü ise bilgiyle ilgilidir. Her ajanın maliyeti yalnız kendisi tarafından biliniyorsa, merkez bu bilgiyi doğrudan göremez. Bir açık artırma ya da ihale, ajanları bu bilgiyi teklifleriyle açığa vurmaya iter: en düşük maliyetli ajan en düşük teklifi verir ve işi alır. Rekabet böylece bilgiyi toplayan bir araç olur. Mekanizma tasarımı da tam olarak bu işi yapar: rekabeti iyi sonuca yönlendiren kuralları kurar. Sonuçta yanıt, sistemin amacına ve kaynak yapısına bağlıdır.

10.2.2Çıkar yelpazesi: üç küçük oyun

Üç sistem türü, üç küçük iki oyunculu oyunla temsil edilebilir. Her oyun bir kazanç matrisiyle verilir: satırlar 1. oyuncunun, sütunlar 2. oyuncunun seçenekleridir; her hücrede (1. oyuncunun kazancı, 2. oyuncunun kazancı) yazılıdır. Bir hücrenin Nash dengesi olması, iki oyuncunun da o hücrede en iyi tepkide olması demektir. Yani karşı tarafın seçimi sabitken hiçbir oyuncu tek başına seçimini değiştirerek kazancını artıramaz.

Şekil 10.3 üç oyunu, tam işbirliğinden tam rekabete uzanan bir yelpazenin üzerine yerleştirir. Her oyun bir sorun türünü temsil eder.

Solda: saf koordinasyon. İki oyuncunun kazancı her hücrede aynıdır (u₁ = u₂). Çıkarlar tamamen ortaktır. İkisi de Sağ'ı seçerse ikisi de 2, ikisi de Sol'u seçerse ikisi de 1 alır; farklı seçerlerse ikisi de 0 alır. Çatışma yoktur, ama bir sorun vardır: oyuncular hangi tarafı seçeceğini bilmezse uyumsuz seçimler yapabilir. Çözüm iletişim ya da ortak bir kuraldır (konvansiyon, ör. “herkes sağdan”).

Ortada: Mahkûmun İkilemi. Çıkarlar kısmen çatışır. İki oyuncu da sessiz kalırsa ikisi de −1 alır. Biri ihanet eder, diğeri sessiz kalırsa ihanet eden 0, sessiz kalan −3 alır. İkisi de ihanet ederse ikisi de −2 alır. Burada bireysel teşvik ortak iyiye ters düşer ve çözüm için teşvik tasarımı gerekir (10.2.3).

Sağda: Yazı-Tura Eşleştirme. Çıkarlar tamamen zıttır: bir oyuncunun kazancı diğerinin kaybıdır (u₁ + u₂ = 0, sıfır toplamlı oyun). İki oyuncu aynı yüzü seçerse 1. oyuncu, farklı yüzü seçerse 2. oyuncu kazanır. Burada önemli olan öngörülemez olmaktır. Bunun yolu karışık stratejidir (mixed strategy): her seçeneği belirli bir olasılıkla, ör. bir yazı-tura atarak seçmek.

Örnek 10.1 yelpazenin üç noktasında üç ayrı sorunu ortaya koyar. Koordinasyon oyununda denge çoktur ve sorun seçimdir. Mahkûmun İkilemi'nde denge tektir ama verimsizdir. Yazı-Tura'da saf denge yoktur ve rasgelelik gerekir. Bir çoklu ajan sistemini tasarlayan kişi, sistemin bu yelpazenin neresinde olduğunu anlamadan doğru aracı seçemez. Koordinasyon sorunu ortak bir kuralla çözülür. Teşvik sorununda ise ortak kural yetmez; kazançları değiştiren bir düzenleme gerekir.

10.2.3Bireysel rasyonellik ve ortak kötü sonuç

Mahkûmun İkilemi çoklu ajan sistemlerinin en önemli uyarısını taşır. Oyunda İhanet baskın stratejidir: karşı taraf ne yaparsa yapsın İhanet daha yüksek kazanç verir. Bu yüzden iki rasyonel oyuncu da İhanet'i seçer ve denge (−2, −2) olur. Oysa (Sessiz, Sessiz) ikisine de (−1, −1) verirdi. Her oyuncu kendi açısından en iyisini yapar, ama sonuç ikisi için de daha kötüdür. Bireysel rasyonellik ortak kötü sonuç doğurur.

Bu durum Pareto optimallik kavramıyla ifade edilir. Bir sonuç, hiç kimsenin durumunu kötüleştirmeden en az bir kişinin durumunu iyileştiren başka bir sonuç yoksa Pareto optimaldir. (İhanet, İhanet) Pareto optimal değildir: (Sessiz, Sessiz)'e geçmek iki oyuncuyu da iyileştirir. Mahkûmun İkilemi'nin dersi, Nash dengesinin Pareto optimal olmak zorunda olmadığıdır.

Çoklu ajan sistemlerinde bu yapının birçok karşılığı vardır.

Bant genişliği

Her ajan kendi veri akışını artırınca kendi aktarımı hızlanır gibi görünür, ama ağ tıkanır ve herkes için yavaşlar.

Ortak kaynak

Paylaşılan işlemci, enerji ya da veri havuzu aşırı kullanılır. Her ajan kendi işini öne alır, ortak kaynak tükenir.

Bilgi paylaşımı

Bilgi paylaşmak ortak modeli iyileştirir, ama bilgiyi saklamak ajana kısa vadede avantaj sağlar.

Bu yapının çok oyunculu sürümü kamu malı oyunudur ve 10.5'te sayılarla incelenir. Ortak bir kaynağın aşırı kullanılarak tükenmesi ise ortak mallar trajedisi (tragedy of the commons) adını alır. İkisinde de mantık aynıdır: bireyin kazancı ile grubun kazancı ters yönde hareket eder.

10.2.4Karar alma: merkezi mi, dağıtık mı?

Ajanlar çevresel bilgiye göre plan yapar. Kararı kim verir: tek bir merkez mi, her ajan kendisi mi? Bu, bir çoklu ajan sistemi tasarlanırken verilen ilk büyük karardır. Tablo 10.4 iki seçeneği karşılaştırır.

Merkezi kontrolün en büyük gücü, tüm bilgiye sahip bir merkezin optimumu hesaplayabilmesidir. Ancak üç zayıflığı vardır. Birincisi tek nokta hatasıdır: merkez bozulursa bütün sistem durur. İkincisi ölçeklenme sorunudur: ajan sayısı arttıkça merkeze gelen mesajlar ve merkezin çözmesi gereken problem büyür. 10.3.5'te görüleceği gibi, n ajanı n göreve atamanın tüm yollarını denemek n! işlem gerektirir; bu sayı n = 10'da 3.628.800'e ulaşır. Üçüncüsü dürüstlük sorunudur: merkez, maliyet gibi özel bilgiyi ajanların bildirmesine muhtaçtır. Bencil bir ajan maliyetini yüksek bildirerek daha kolay bir iş almaya çalışabilir.

Dağıtık kontrol bu zayıflıkları giderir: bir ajan bozulsa da diğerleri çalışır, yeni ajan eklemek kolaydır ve her ajan yerel olaylara anında tepki verir. Ama kendi zayıflıkları vardır. Yerel bilgiyle alınan kararlar uyumsuz olabilir (10.2.5). Bencil ajanlar da Mahkûmun İkilemi'ndeki gibi verimsiz bir dengeye varabilir. Bencil davranışın sistem düzeyindeki maliyeti, en kötü dengenin maliyetinin optimum maliyete oranıyla ölçülür. Bu orana Anarşinin Bedeli (Price of Anarchy) denir.

Çoğu gerçek çoklu ajan sistemi hibrittir: ajanlar otonom karar verir, ama bir merkez kuralları, fiyatları ya da ihaleleri belirler. Merkez her ajanın ne yapacağına karar vermez; yalnız oyunun kurallarını koyar. 10.3.2'de anlatılan sözleşme ağı buna bir örnektir: bir yönetici görevleri ihaleye çıkarır, ama maliyetleri bilmez ve kimin işi yapacağını tekliflere bırakır.

10.2.5Dağıtık koordinasyon ve konvansiyonlar

Dağıtık koordinasyonda ajanlar merkez olmadan, yerel bilgi ve mesajlaşma ile karar verir. Bunu sağlayan bir protokol üç şeyi birlikte ele almalıdır. İletişim gecikmesi: mesaj ulaşana kadar durum değişmiş olabilir. Hata toleransı: bir mesaj kaybolursa ya da bir ajan yanıt vermezse sistem kilitlenmemelidir. Ölçeklenebilirlik: ajan sayısı arttıkça mesaj sayısı kontrolden çıkmamalıdır.

Dağıtık sistemin en tipik sorunu ortak bilgi eksikliğidir. İki robot dar bir koridorda karşılaşsın. Her biri karşıdakine yol vermek için bir tarafa kaçacaktır. İkisi de kendi sağına kaçarsa yollar ayrılır ve geçerler. Biri sağına, öteki soluna kaçarsa aynı tarafa yönelirler ve yine burun buruna gelirler. Bu durum Tablo 10.5'te bir oyun olarak yazılmıştır.

(Sağ, Sağ)'da tek başına Sol'a geçen robot −1'e düşer; bu yüzden kimse sapmaz. (Sol, Sol) için de aynısı geçerlidir. Diğer iki hücrede ikisi de −1 alır ve taraf değiştiren robot 1'e çıkar; bu hücreler denge değildir. İki denge de eşit iyidir. Sorun hangisinin daha iyi olduğu değil, hangisinin oynanacağıdır.

Konvansiyonun gücü, kendini zorlamasıdır. Herkes sağdan gidiyorsa sağdan gitmek her ajanın en iyi tepkisidir; kuralı çiğneyen ajan yalnız kendine zarar verir. Bu yüzden konvansiyonu denetleyecek bir polise gerek yoktur. Konvansiyonun bir dengeyi seçtiğine dikkat etmek gerekir; denge olmayan bir sonucu seçen kural kendini zorlamaz.

Örnek 10.2'nin son adımı önemli bir kavramı gösterir. Trafik ışığı herkese ortak bir sinyal verir ve iki dengeden hangisinin oynanacağını seçer. Sinyale uymanın her oyuncu için en iyi tepki olduğu bu tür dengelere korelasyonlu denge (correlated equilibrium) denir. Korelasyonlu denge, oyunculara dışarıdan bir “tavsiye” verildiğinde ortaya çıkar ve tavsiyeye uymak her oyuncunun kendi çıkarınadır. Bir kavşaktaki trafik ışığı bu dengenin gündelik bir örneğidir.

10.2.6Oyun kuramı ve teşvikler

Oyun kuramı çoklu ajan sistemlerinde iki ayrı iş görür.

Analiz: Nash dengesi

Ajanların stratejik kararları dengede nereye varır? Denge verimli mi? Bu, sistemin kuralları verildiğinde sonucu öngörmektir.

Tasarım: mekanizma

Kurallar, ödemeler ve açık artırmalar ajanları dürüst bildirime ve işbirliğine nasıl yönlendirir? Bu, istenen sonucu verecek kuralları seçmektir.

Tasarımın gücü iki örnekte görülür.

Enerji paylaşımı. Bir akıllı şebekede evlerin bir kısmı güneş panelleriyle enerji üretir. Teşvik dengeli kurulursa, ör. şebekeye verilen fazla üretime adil bir ödeme yapılırsa, evler fazla enerjiyi şebekeye verir ve herkes yeterli enerji alır. Teşvik yanlış kurulursa, ör. her saatte aynı fiyat uygulanırsa, herkes enerjiyi kendisine en uygun saatte, yani akşam pik saatinde çeker ve şebeke zorlanır.

Dağıtık ağ kaynakları. Bant genişliği ve hesaplama gücü paylaşılan kaynaklardır. Kullanım ücreti ya da kota olmazsa her ajan kaynağı kendi işi için sonuna kadar kullanır ve aşırı kullanım ortaya çıkar. Ücret ya da kota, her ajanın kendi kullanımının başkalarına yüklediği maliyeti hissetmesini sağlar.

İki örnekten çıkan sonuç şudur. Doğru teşvik işbirliğini artırır ve çatışmayı azaltır. Yanlış teşvik bencil davranış, aşırı risk ve beleşçilik doğurur. Teşvik tasarımı, ajanların bencil olmamasını beklemek yerine, bencil davranışın sistem için de iyi olacağı kuralları kurmaktır.

10.2.7İletişim, öğrenme ve ortaya çıkan davranış

Oyun kuramının temel modellerinde oyuncular oyunu bilir ve dengeyi bir anda oynar. Çoklu ajan sistemlerinde ise üç gerçek durum bu basit resmi karmaşıklaştırır.

İletişim ve bilgi. Ajanların bilgisi farklıdır. Bir robot bir rafın boş olduğunu bilir, diğeri bilmez. Kimin neyi bildiği, yani bilgi yapısı, dengeyi değiştirir. Oyuncuların birbirinin kazancı ya da tipi hakkında eksik bilgiye sahip olduğu oyunlara eksik bilgili oyunlar denir. Ajanların bilgi alışverişi yapabilmesi için ortak bir dil ve bir mesajlaşma protokolü gerekir. Sözleşme ağı (10.3.2) böyle bir protokoldür.

Öğrenme ve uyum. Ajanlar dengeyi önceden hesaplamak yerine, geri bildirimle stratejilerini adım adım güncelleyebilir. Üç yaygın yöntem vardır. En iyi tepki dinamiğinde her ajan, diğerlerinin son hamlesine en iyi tepkiyi verir. Kurgusal oyunda (fictitious play) her ajan, rakibinin geçmiş hamlelerinin ortalamasına en iyi tepkiyi verir. Pekiştirmeli öğrenmede ajan, iyi sonuç veren eylemleri daha sık seçer. Ancak bir sorun vardır: diğer ajanlar da öğrendiği için her ajanın çevresi sürekli değişir. Böyle bir çevreye durağan olmayan (non-stationary) çevre denir. Durağan olmayan bir çevrede öğrenmenin bir dengeye yakınsaması garanti değildir.

Örnek 10.3 durağan olmayan çevrenin sonucunu somut gösterir. Her robot için çevre, öteki robotun davranışıdır; öteki robot da öğrendiği için bu çevre her turda değişir. Güncellemeleri sıraya koymak (ya da robotlara küçük bir rastgele bekleme eklemek) bu döngüyü kırar. Ağ protokollerinde çarpışan mesajların rastgele bir süre bekleyip yeniden gönderilmesi aynı fikre dayanır.

Ortaya çıkan davranış. Basit yerel kurallar sistem düzeyinde beklenmedik örüntüler doğurabilir. Buna ortaya çıkan davranış (emergent behavior) denir. En ünlü örnek Schelling'in (1971) ayrışma modelidir. Bir ızgaraya iki gruptan bireyler yerleştirilir. Her birey, komşularının küçük bir kısmından fazlası farklı gruptansa (ör. üçte birinden fazlası) boş bir yere taşınır. Hiçbir birey ayrışma istemez; herkes karışık bir mahallede yaşamaya razıdır. Yine de taşınmalar zincirleme ilerler ve sonunda belirgin biçimde ayrışmış mahalleler oluşur. Hafif bir komşu tercihi, kimsenin istemediği güçlü bir ayrışmayı üretir.

Bu örnek bir yöntem dersi taşır: sistemin davranışı tek tek ajanlara bakarak okunamaz. Bu yüzden çoklu ajan sistemlerinde denge analizi ile simülasyon birlikte kullanılır. Denge analizi sistemin varabileceği durağan noktaları verir; simülasyon da sistemin bu noktalara nasıl gittiğini ya da gidip gitmediğini gösterir. Trafik sıkışıklığı ve fiyat dalgalanmaları da ajanlar arası etkileşimden doğan bu tür örüntülerdir.

10.2.8Koordinasyonda sık hatalar

10.3Görev tahsisi

Bir çoklu ajan sisteminin en sık karşılaştığı somut problem, işleri ajanlara dağıtmaktır. Hangi drone hangi bölgeyi tarayacak, hangi robot hangi siparişi toplayacak, hangi sunucu hangi hesaplamayı yapacak? Bu kesimde önce görev tahsisi problemini ve çözüm yöntemlerini tanıtıyoruz. Sonra en eski dağıtık yöntemlerden biri olan sözleşme ağı protokolünü küçük bir örnek üzerinde adım adım çalıştırıyor, kodunu izliyor ve sonucu merkezi optimumla karşılaştırıyoruz.

10.3.1Görev ve kaynak tahsisi

Problem kâğıt üzerinde basit görünür: her ajanın her işi ne kadar sürede yapacağı bir tabloya yazılır ve toplamı en küçük atama aranır. Gerçekte üç zorluk vardır.

• Özel bilgi. Maliyetleri çoğu zaman yalnız ajanın kendisi bilir. Bir robotun bir siparişi kaç dakikada toplayacağı, robotun konumuna, şarjına ve yüküne bağlıdır. Merkez bu tabloyu göremez.
• Ölçek. Ajan sayısı büyüktür. Yüzlerce robot ve binlerce sipariş olabilir.
• Zaman. Görevler zamanla gelir. Bütün görevler baştan bilinmez; yeni sipariş geldikçe karar vermek gerekir.

İyi bir yöntem, çözüm kalitesini iletişim ve hesaplama maliyetiyle dengeler. Mükemmel bir atama bulmak için saatlerce hesap yapmak ya da binlerce mesaj göndermek, biraz daha kötü bir atamayı anında bulmaktan pahalı olabilir. Tablo 10.6 dört yaygın yöntemi karşılaştırır.

Merkezi optimizasyon tüm maliyetleri bir merkezde toplar ve atama problemini çözer: n görevi n ajana, her ajana tam bir görev düşecek ve toplam maliyet en küçük olacak biçimde atamak. Bu problemin klasik çözümü Macar algoritmasıdır (Hungarian algorithm). Macar algoritması yaklaşık n³ adımda optimumu bulur; yani n = 10 için yaklaşık bin adım yeter. Yöntemin eksiği hesap değil, bilgidir: merkezin bütün maliyet tablosunu bilmesi gerekir.

Sözleşme ağı bilgiyi merkezde toplamaz; görevleri tek tek ihaleye çıkarır. Açık artırma yöntemleri bu fikri genelleştirir. Kombinatoryal açık artırmada (combinatorial auction) ajanlar tek tek görevlere değil, görev paketlerine teklif verir: “G1 ile G2'yi birlikte 5 dakikada yaparım.” Paket teklifleri, görevler arasındaki tamamlayıcılığı (iki yakın siparişi birlikte toplamak gibi) yakalar. Pazar tabanlı yöntemlerde her görevin ya da kaynağın bir fiyatı vardır. Fiyat, talep fazlaysa artar, azsa düşer; ajanlar da fiyata bakarak hangi görevi alacağına karar verir. Bu yöntem çok büyük sistemlere ölçeklenir, ama fiyatların dengeye oturması zaman alabilir.

10.3.2Sözleşme ağı protokolü

Sözleşme ağı protokolü (Contract Net Protocol), Smith (1980) tarafından dağıtık problem çözme için önerilmiştir. Protokol, inşaat sektöründeki ihale sürecini taklit eder: bir iş sahibi işi duyurur, müteahhitler teklif verir, iş en iyi teklife verilir. Daha sonra FIPA (2002) adlı ajan standartları kuruluşu protokolü bir standart olarak tanımlamıştır.

Şekil 10.4 mesajların sırasını gösterir. Sıra değiştirilemez: duyurulmamış bir göreve teklif verilemez, teklifler toplanmadan ödül verilemez. Roller sabit değildir; görev başına değişebilir. Bir görevi yüklenici olarak alan robot, bu görevin bir alt parçasını başka robotlara ihaleye çıkararak o alt görev için yönetici olabilir. Böylece büyük bir iş, iç içe ihalelerle parçalara bölünür.

Protokolün en önemli özelliği bilgiyle ilgilidir. Yönetici maliyetleri bilmez; teklifler bu özel bilgiyi açığa çıkarır. Yönetici bütün maliyet tablosunu öğrenmek zorunda değildir; her görev için yalnız o görevin tekliflerini görür. Teklif verme, bir ters açık artırmadır: alışılmış açık artırmada en yüksek teklif kazanır, burada ise iş en düşük maliyeti bildirene gider. Bu yapı, teklifçilerin dürüst olup olmayacağı sorusunu doğurur; bu soru 10.3.6'da ele alınır.

10.3.3Sözleşme ağı adım adım

Protokolü küçük bir örnekte çalıştıralım. Bir yönetici üç görevi (G1, G2, G3) sırayla ihaleye çıkaracaktır. Üç robot (R1, R2, R3) vardır. Her robot en çok bir görev alabilir. Her robotun her görev için tahmini süresi (dakika) Şekil 10.5'te verilmiştir. Bu süreler robotların maliyetidir ve robotlar bunları dürüstçe teklif olarak bildirir. Önemli bir ayrıntı: tabloyu yalnız robotlar bilir, yönetici tabloyu görmez. Her robot yalnız kendi sütununu bilir.

Tabloda bir dikkat noktası vardır: R1 hem G1 için (2) hem G2 için (3) en ucuz robottur. R1 yalnız bir görev alabileceğine göre, hangi göreve gideceği toplam süreyi belirleyecektir.

Şekil 10.6 ve Şekil 10.7 ilk ihalenin teklif ve ödül adımlarını gösterir. Sonraki iki ihale aynı biçimde ilerler; tek fark, her ödülden sonra boştaki robot sayısının bir azalmasıdır. Tablo 10.7 üç ihaleyi bir arada özetler.

Şekil 10.8 sonucu optimumla karşılaştırır. Tüm atamaları deneyen bir merkez G1'i R3'e (6), G2'yi R1'e (3), G3'ü R2'ye (4) verir ve toplam 6 + 3 + 4 = 13 dakika elde eder. Sözleşme ağının 18 dakikası optimumdan 5 dakika fazladır. Oran olarak 18/13 ≈ 1,385, yani sözleşme ağı yaklaşık %38 daha pahalıdır.

Fark nereden doğar? Sözleşme ağı her adımda o anki en iyi kararı verir: G1'i en ucuz robota, R1'e verir. Bu karar G1 için doğrudur, ama R1'i G2 için harcar. G2'nin en ucuz robotu R1 olduğu hâlde G2, 7 dakikalık R2'ye gider. Optimum ise G1'de biraz pahalı bir seçim yapar (R3, 6 dk), ama R1'i G2'ye saklar. Her adımda yerel olarak en iyi görünen seçimi yapan yöntemlere açgözlü (greedy) yöntem denir. Açgözlü yöntemler hızlıdır, ama geleceği hesaba katmadıkları için toplam optimumu kaçırabilir.

10.3.4Kod izleme: sozlesme_agi()

Sözleşme ağının sıralı ihale mantığı birkaç satırlık bir Python fonksiyonuyla yazılabilir. Fonksiyon iki girdi alır. gorevler, ihaleye çıkış sırasıyla görevlerin listesidir: ["G1", "G2", "G3"]. maliyet ise iç içe bir sözlüktür: maliyet[r][g], r robotunun g görevi için maliyetidir. Örnekte maliyet["R1"] = {"G1": 2, "G2": 3, "G3": 5}'tir.

def sozlesme_agi(gorevler, maliyet):
  bos = set(maliyet)
  atama, toplam = {}, 0
  for g in gorevler:
    teklif = {r: maliyet[r][g] for r in bos}
    kazanan = min(teklif, key=teklif.get)
    atama[g] = kazanan
    toplam += teklif[kazanan]
    bos.remove(kazanan)
  return atama, toplam

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

1. bos = set(maliyet): Bir sözlükten küme oluşturulunca sözlüğün anahtarları alınır. bos başlangıçta bütün robotları içerir: {R1, R2, R3}.
2. atama, toplam = {}, 0: Atamalar boş bir sözlükte tutulur, toplam süre 0'dan başlar.
3. for g in gorevler: Görevler sırayla ihaleye çıkar. Her tur bir duyurudur.
4. teklif = {r: maliyet[r][g] for r in bos}: Yalnız boştaki robotlar teklif verir. Her robot g görevi için kendi maliyetini bildirir. Bu satır, protokolün teklif adımıdır.
5. kazanan = min(teklif, key=teklif.get): min, sözlüğün anahtarları (robotlar) arasından teklif.get değeri en küçük olanı seçer. Bu satır ödül adımıdır.
6. atama[g] = kazanan ve toplam += teklif[kazanan]: Görev kazanana yazılır, kazanan teklif toplama eklenir.
7. bos.remove(kazanan): Kazanan robot meşgul olur ve sonraki ihalelere katılmaz.

Tablo 10.8 ve Şekil 10.9 kodun örnekteki çalışmasını özetler. İzlemenin en öğretici satırı ikincisidir: G2 turunda bos kümesinde R1 yoktur. G1'i ucuza alan R1, G2 için de en ucuz adaydı (3), ama artık meşguldür. Fonksiyon her adımda yerel en iyi kararı verir, ama sonuç toplam optimum değildir. Kodun maliyeti de düşüktür: m görev ve n robot için her turda en çok n teklif karşılaştırılır; toplam iş yaklaşık m · n adımdır.

Kodda dikkat edilecek bir ayrıntı daha vardır: min fonksiyonu eşitlik durumunda sözlükte ilk karşılaştığı robotu seçer. İki robot aynı teklifi verirse kazanan, kümenin iç sırasına bağlıdır. Gerçek bir protokolde eşitlik kuralı (ör. küçük numaralı robot kazanır) açıkça belirtilmelidir. Bu örnekte eşitlik çıkmaz.

10.3.5Merkezi optimum: optimum()

Sözleşme ağının sonucunu değerlendirmek için optimumu bilmek gerekir. Tüm maliyetleri bilen bir merkez, robotların görevlere bütün atamalarını deneyebilir. Üç görev ve üç robot için atama, robotların bir sıralamasıdır: sıralamanın ilk robotu G1'i, ikincisi G2'yi, üçüncüsü G3'ü alır. Üç robotun 3! = 3 · 2 · 1 = 6 farklı sıralaması vardır.

def optimum(gorevler, maliyet):
  en_iyi = None
  for p in permutations(maliyet):
    t = sum(maliyet[r][g]
            for g, r in zip(gorevler, p))
    if en_iyi is None or t < en_iyi[0]:
      en_iyi = (t, p)
  return en_iyi

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

1. en_iyi = None: Henüz hiçbir atama denenmemiştir.
2. for p in permutations(maliyet): permutations (Python'un itertools modülünden) robotların bütün sıralamalarını üretir. p = ("R3", "R1", "R2"), G1'in R3'e, G2'nin R1'e, G3'ün R2'ye atanması demektir.
3. zip(gorevler, p): Görevleri sıralamadaki robotlarla eşler: (G1, R3), (G2, R1), (G3, R2).
4. t = sum(maliyet[r][g] for g, r in ...): Bu atamanın toplam süresini hesaplar.
5. if en_iyi is None or t < en_iyi[0]: İlk atama ya da şimdiye kadarkinden daha iyi bir atama bulunursa en_iyi güncellenir. Eşit süreli bir atama mevcut en iyiyi değiştirmez.

Tablo 10.9 ve Şekil 10.10 sonucu gösterir: optimum 13 dakikadır ve G1→R3, G2→R1, G3→R2 atamasıyla elde edilir. Sözleşme ağının bulduğu atama, listenin ilk satırıdır (18 dk). Tablodan bir şey daha görülür: altı atamanın ikisi 18 dakikadır, yani sözleşme ağı bu örnekte mümkün olan en kötü toplamı bulmuştur.

Bu yöntemin sorunu ölçektir. n robot için n! sıralama vardır ve bu sayı çok hızlı büyür. Tablo 10.10 birkaç değeri gösterir.

n = 10'da üç buçuk milyondan fazla atama vardır; n = 15'te bu sayı bir trilyonu geçer. Tüm atamaları denemek küçük örnekler dışında pratik değildir. Macar algoritması aynı optimumu O(n³) zamanda bulur: n = 10'da yaklaşık bin, n = 15'te yaklaşık üç bin adım. Ancak hangi algoritma kullanılırsa kullanılsın, merkezi çözümün asıl engeli hesap değil bilgidir: merkezin bütün maliyetleri bilmesi gerekir.

10.3.6Teklifler ve dürüstlük

Şimdiye kadar robotların maliyetlerini dürüstçe teklif ettiği varsayıldı. Robotlar bencil ajanlarsa bu varsayım geçerli midir? Cevap, kazanana ne ödendiğine bağlıdır. Sözleşme ağında teklif verme bir ters açık artırmadır: en düşük teklif kazanır ve kazanan, işi yaptığı için bir ödeme alır. Robotun kazancı, aldığı ödeme ile gerçek maliyeti arasındaki farktır.

Örnek 10.5 genel bir sonucun örneğidir. Kazanana kendi teklifi ödenirse yüklenici maliyetini şişirmek ister. İkinci en düşük teklif ödenirse (Vickrey kuralı) dürüst teklif en iyisidir: robotun teklifi yalnız kazanıp kazanmadığını belirler, ödemeyi belirlemez. Ödeme başkalarının teklifine bağlı olduğu için robotun yalan söyleyerek ödemeyi artırma olanağı yoktur. Robotun yapabileceği tek şey, kazanmanın kârlı olup olmadığına karar vermektir; dürüst teklif bu kararı her zaman doğru verir.

Bu sonuç tek bir görevin ihalesi için geçerlidir. Görevler sırayla ihaleye çıktığında bir robot, sonraki bir görevi almak için bir ihaleyi bilerek kaybetmek isteyebilir. Tüm atamayı birlikte ele alan dürüstlük, her robota diğerlerine verdiği kaybı ödeten genel kuralla, yani VCG mekanizmasıyla sağlanır. VCG, Vickrey kuralının çok nesneli genellemesidir.

10.3.7Güçlü yanlar, zayıf yanlar ve iyileştirmeler

Örnekteki sonuç sözleşme ağının hem gücünü hem zayıflığını gösterir.

Güçlü yanlar.

• Dağıtık: yönetici maliyet tablosunu bilmeden iyi bir atama yapar. Bilgi robotlarda kalır ve yalnız gerektiği kadar paylaşılır.
• Az mesaj: n robotlu bir sistemde görev başına mesaj sayısı O(n)'dir: bir duyuru (yayın), en çok n teklif ve bir ödül.
• Esneklik: yeni robot eklemek kolaydır; robot duyuruları dinlemeye başlar. Bozulan bir robotun görevi yeniden ihaleye çıkarılır.

Zayıf yanlar.

• Açgözlü ve sıralı: örnekte 18 dk, optimum 13 dk (%38 fazla). G1'i ucuza alan R1, G2 için en iyi aday olduğu hâlde meşgul kalmıştır.
• Stratejik teklif: robotlar maliyetlerini stratejik olarak şişirebilir (10.3.6).
• Sıra bağımlılığı: görevlerin ihaleye çıkış sırası sonucu değiştirir.

Sıra bağımlılığı en açık biçimde, aynı maliyet tablosuyla altı farklı ihale sırası denenerek görülür. Tablo 10.11 sonuçları verir.

Altı sıranın ikisi optimuma (13) ulaşır, biri en kötü sonucu (18) verir. G1'in en sona bırakıldığı sıralarda optimum bulunur: G1'in birkaç iyi adayı (R1 2, R2 3, R3 6) vardır, bu yüzden en son ihaleye çıkması fazla bir kayba yol açmaz. Buna karşılık G1 ilk sıradaysa onu kapan R1, G2 için de ve G3 için de iyi bir adaydır. Kıt robotu ilk ihalede harcamak, sonraki ihaleleri pahalılaştırır.

Sözleşme ağının zayıflıkları üç iyileştirmeyle azaltılır.

Yeniden ihale (atamaları takasla düzeltme)

İlk atamadan sonra robotlar ikili takas önerir. İki robot görevlerini değiştirince toplam süre azalıyorsa takas yapılır. Yerel düzeltmeler açgözlü kararların bir kısmını geri alır.

Kombinatoryal açık artırma

Robotlar tek görevlere değil görev paketlerine teklif verir. Böylece bir robot, “G1'i alırsam G2'yi alamam” gibi görevler arasındaki bağı teklifine yansıtabilir.

İkinci fiyat ya da VCG ödemeleri

Kazanana ikinci en iyi teklif (ya da genel olarak diğerlerine verdiği kayıp) ödenir. Dürüst teklif en iyi strateji olur (10.3.6).

Örnek 10.6 yeniden ihalenin gücünü gösterir, ama bir uyarı da gerekir: ikili takaslar her örnekte optimuma ulaşmayabilir. Hiçbir ikili takasın kazandırmadığı ama optimum olmayan atamalar vardır. Bu yüzden takas, açgözlü sonucu iyileştiren pratik bir araçtır; optimumun garantisi değildir.

10.3.8Görev tahsisinde sık hatalar

10.4Koalisyon oyunları

Görev tahsisinde her robot işini tek başına yapıyordu. Birçok işte ise ajanlar birlikte çalışarak tek başlarına üretemeyecekleri bir değer üretir. Bu kesim, grupların oluşmasını ve grubun ürettiği değerin üyeler arasında paylaşılmasını inceler. Oyun kuramının bu dalına işbirlikçi oyun kuramı ya da koalisyon oyunları denir. Bu kesimde önce koalisyon oluşumunu ve koalisyon yapılarını, sonra karakteristik fonksiyonu tanımlıyoruz. Ardından adalet ölçütü olarak Shapley değerini, kararlılık ölçütü olarak çekirdeği ve oylamadaki gücü ölçen güç endekslerini adım adım hesaplıyoruz.

10.4.1Koalisyon oluşumu

Tek başına hedefe ulaşamayan ajanlar geçici ya da kalıcı koalisyonlar kurabilir. Kargo firmaları araç paylaşır: yarı boş giden iki kamyon yerine tek bir dolu kamyon gönderilir. Drone'lar tek başına kaldıramayacakları ağır bir yükü birlikte taşır. Hesaplama sunucuları bir işi parçalara bölüp birlikte çözer. Her durumda grup, üyelerinin tek başına üretebileceğinden fazlasını üretir.

Bu oyunlar önceki kesimdeki oyunlardan bir noktada ayrılır: işbirlikçidir. Mahkûmun İkilemi'nde oyuncular “ikimiz de sessiz kalalım” diye anlaşsa bile anlaşmanın bir yaptırımı yoktu; her oyuncu anlaşmayı bozmak isterdi. Koalisyon oyunlarında ise bağlayıcı anlaşma yapılabildiği varsayılır: bir sözleşme, bir yasa ya da bir yazılım protokolü, koalisyonun üyelerine verdiği sözü tutmalarını sağlar. Bu yüzden soru değişir. Soru artık “her oyuncu hangi stratejiyi seçecek?” değil, şudur: kim kiminle birleşir ve kazanç nasıl paylaşılır?

İki soru birbirine bağlıdır. Paylaşım adil değilse koalisyon dağılır: kendini haksızlığa uğramış hisseden ajanlar ayrılıp başka bir grup kurar. Kararlılık doğrudan paylaşım kuralına bağlıdır. Bu yüzden bu kesim iki ölçütü ayrıntılı inceler.

Shapley değeri

Adalet ölçütüdür: herkes ortalama marjinal katkısı kadar alır (10.4.5).

Çekirdek

Kararlılık ölçütüdür: hiçbir alt grup ayrılarak daha fazlasını alamaz (10.4.9).

10.4.2Koalisyon yapıları

Ajanlar tek bir büyük grupta birleşmek zorunda değildir. Üç lojistik firması A, B ve C düşünelim. Üçü ayrı çalışabilir, ikisi birleşip üçüncüsü ayrı kalabilir ya da üçü birden birleşebilir.

Şekil 10.11 üç ajanın bütün yapılarını gösterir. Değerler Tablo 10.12'de verilen karakteristik fonksiyondan gelir. Herkes tek başına çalışırsa toplam 10 + 20 + 30 = 60'tır. {B, C} birleşir ve A ayrı kalırsa toplam 70 + 10 = 80'dir. {A, C} ile {B}: 60 + 20 = 80. {A, B} ile {C}: 50 + 30 = 80. Üçü birlikte 120 üretir. Toplum açısından soru şudur: toplam değeri en büyük yapı hangisidir? Bu örnekte cevap büyük koalisyondur.

Yapı sayısı. n ajanı boş olmayan ayrık gruplara bölmenin yol sayısına Bell sayısı denir ve B_n ile gösterilir. Üç ajan için 5 yapı vardır. Bell sayıları şu ilişkiyle adım adım hesaplanabilir: (n + 1). ajanı içeren grubun, ilk n ajandan kaç tanesini içerdiğine göre sayım yapılır. Bu grup ilk n ajandan k tanesini içeriyorsa, bu k ajanı seçmenin C(n, k) yolu vardır; geri kalan n − k ajan da B_n−k yolla bölünür. Toplam:

B_n+1 = Σ_k=0ⁿ C(n, k) · B_n−k, B₀ = 1.

Bu ilişkiyle B₁ = 1, B₂ = 1 + 1 = 2, B₃ = B₂ + 2B₁ + B₀ = 2 + 2 + 1 = 5 bulunur. Dört ajan için B₄ = C(3,0)·B₃ + C(3,1)·B₂ + C(3,2)·B₁ + C(3,3)·B₀ = 5 + 6 + 3 + 1 = 15'tir. Sayı çok hızlı büyür: n = 8 için 4.140, n = 10 için 115.975 yapı vardır. Genel durumda en iyi yapıyı bulmak NP-zordur (Sandholm vd., 1999); yani ajan sayısı büyüdükçe bilinen hiçbir algoritma bunu her örnekte hızlı çözemez.

Örnekteki oyunda bu zorluk ortaya çıkmaz, çünkü oyun süperadditiftir: birleşmek hiçbir zaman zarar vermez. Bu durumda en iyi yapı her zaman büyük koalisyondur ve geriye tek bir soru kalır: büyük koalisyonun ürettiği 120 nasıl paylaşılacak?

10.4.3Karakteristik fonksiyon

Karakteristik fonksiyon oyunun bütün bilgisini tek bir tabloda toplar. Oyuncuların hangi eylemleri seçtiği, nasıl çalıştıkları tabloda görünmez; yalnız her grubun sonunda ne kadar değer ürettiği görünür. Bu soyutlama işbirlikçi oyun kuramının temelidir: grup içi ayrıntılar bağlayıcı anlaşmalarla çözüldüğü için yalnız grupların gücü önemlidir.

Bölümün ana örneği üç lojistik firmasıdır. Firmalar birlikte 120 bin TL kâr eder, en iyi ikili 70, tek başına en fazla 30 kazanır. Karakteristik fonksiyonun bütün değerleri Tablo 10.12'de verilmiştir.

Süperadditiflik her oyunda sağlanmaz. Bir koalisyon büyüdükçe koordinasyon maliyeti artabilir: çok büyük bir kargo ortaklığında araç planlaması zorlaşır. Böyle bir oyunda iki ayrı grup, birleşik gruptan fazla üretebilir ve en iyi yapı büyük koalisyon olmayabilir.

10.4.4120 nasıl paylaşılmalı?

Büyük koalisyon 120 üretir. Bu değer nasıl paylaşılmalıdır? Önce her makul paylaşımın sağlaması gereken iki koşul yazılır.

Bu iki koşulu sağlayan sonsuz sayıda paylaşım vardır. Tablo 10.13 dört öneriyi karşılaştırır.

Dört önerinin hepsi bir paylaşımdır: toplamları 120'dir ve herkes en az tek başına değerini alır. Örneğin C'nin önerisinde A tam olarak 10 alır, yani tek başına değerinin altına düşmez. Yine de öneriler çok farklıdır.

Eşit bölüşüm en basit kuraldır, ama C'nin her gruba daha fazla değer kattığını yok sayar. Orantılı paylaşım 120'yi tek başına değerler oranında böler: toplam tek başına değer 10 + 20 + 30 = 60 olduğu için her oyuncu tek başına değerinin 120/60 = 2 katını alır. Bu kural sinerjileri görmez: A'nın B ile 20, C ile 20 birimlik ek değer yarattığı (50 − 30 ve 60 − 40) hesaba katılmaz. Güçlü C'nin önerisi C'ye 85 verir. Ancak A ve B bu durumda birlikte 10 + 25 = 35 alır; oysa ikisi ayrılıp kendi koalisyonlarını kursa v(AB) = 50 kazanırlar. Bu öneri kabul edilmez. Shapley değeri ise her oyuncunun bütün olası gruplara kattığı değerin ortalamasını verir.

Tablo iki ayrı ölçütü ortaya koyar: paylaşım adil mi (Shapley değeri) ve kararlı mı (çekirdek)? C'nin önerisi kararlı değildir, çünkü bir alt grup ayrılmak ister. Eşit bölüşüm kararlı olabilir ama katkıları yansıtmaz. İki ölçüt sırayla incelenir.

10.4.5Shapley değeri: tanım ve aksiyomlar

Shapley değerinin fikri basit bir hikâyeyle anlatılır. Oyuncular rastgele bir sırayla tek tek gelip koalisyona katılır. Her oyuncuya, geldiği anda koalisyona kattığı değer verilir. Örneğin sıra A → B → C ise A önce gelir ve boş koalisyona v(A) − v(∅) = 10 katar. B gelince koalisyon {A}'dan {A, B}'ye büyür ve B'nin katkısı v(AB) − v(A) = 50 − 10 = 40'tır. C en son gelir ve v(ABC) − v(AB) = 120 − 50 = 70 katar. Bir oyuncunun bir koalisyona kattığı bu değere marjinal katkı (marginal contribution) denir.

Tek bir sıra adil değildir: son gelen oyuncu çoğu zaman en büyük sinerjiyi toplar. Bu yüzden Shapley değeri bütün sıraların ortalamasını alır.

Aynı değer, sıralar yerine koalisyonlar üzerinden de yazılabilir. i'den önce gelenlerin kümesi S olan sıra sayısı, S'nin üyelerinin kendi aralarında dizilişi (|S|!) ile i'den sonra gelenlerin dizilişinin ((n − |S| − 1)!) çarpımıdır. Bu yüzden

φ_i = Σ_{S ⊆ N∖{i}} [ |S|! · (n − |S| − 1)! / n! ] · [ v(S ∪ {i}) − v(S) ]

yazılır. Bu formül n! sıra yerine i'yi içermeyen 2ⁿ⁻¹ koalisyon üzerinden toplam alır. Üç oyunculu oyunda ağırlıklar şöyledir: |S| = 0 için 0! · 2!/3! = 2/6 = 1/3, |S| = 1 için 1! · 1!/3! = 1/6, |S| = 2 için 2! · 0!/3! = 2/6 = 1/3. Ağırlıkların toplamı 1/3 + 2 · 1/6 + 1/3 = 1'dir.

Hesap maliyeti. Kesin hesap ya n! sırayı ya da 2ⁿ⁻¹ alt kümeyi gerektirir. Her ikisi de n büyüdükçe çok hızlı artar. Büyük n için Shapley değeri örnekleme ile yaklaşık hesaplanır: rastgele birkaç bin sıra seçilir ve bu sıralardaki marjinal katkıların ortalaması alınır. Örnek sayısı arttıkça ortalama gerçek değere yaklaşır.

Shapley değerinin önemi, yalnız sezgisel bir kural olmasından gelmez. Shapley (1953), bu değerin dört doğal koşulu sağlayan tek kural olduğunu göstermiştir. Bu koşullara aksiyom denir.

Teoremin kanıtı bu notun kapsamı dışındadır. Ancak tanımın aksiyomları neden sağladığı kolayca görülür. Verimlilik: her sırada marjinal katkıların toplamı, boş koalisyondan büyük koalisyona kadar adım adım eklenen değerlerin toplamıdır ve teleskopik olarak v(N) − v(∅) = v(N)'ye eşittir. Ortalama alınca da toplam v(N) kalır. Kukla oyuncu: her sırada katkısı 0 olan oyuncunun ortalaması da 0'dır. Simetri: i ile j'nin yerini değiştiren bir eşleme, i'nin her sıradaki katkısını j'nin başka bir sıradaki katkısıyla eşler; ortalamalar eşit çıkar. Toplamsallık: marjinal katkı v'ye göre doğrusaldır; toplamın katkısı, katkıların toplamıdır.

Shapley değeri bugün oyun kuramının dışında da kullanılır. Makine öğrenmesinde bir modelin tek bir kararını, girdi özelliklerinin katkılarına bölen SHAP yöntemi, özellikleri “oyuncu”, modelin tahminini “koalisyon değeri” sayar ve her özelliğe Shapley değerini atar.

10.4.6Shapley değeri adım adım

Lojistik oyununda Shapley değeri, altı geliş sırasının her birinde marjinal katkılar yazılarak hesaplanır.

Tablo 10.14 hesabı tek bakışta gösterir. Tablodaki iki düzen, hesabın doğruluğunu denetlemeye yarar. Birincisi, her satırın toplamı 120'dir; bir satır 120 tutmuyorsa o satırda bir çıkarma hatası vardır. İkincisi, bir oyuncunun ilk geldiği sıralarda katkısı her zaman tek başına değeridir: A'nın ilk iki satırı 10, B'nin üçüncü ve dördüncü satırları 20, C'nin son iki satırı 30'dur.

Koalisyon formülüyle denetim. Aynı sonuç 10.4.5'teki ağırlıklı formülle de bulunur. A için i'yi içermeyen dört koalisyon vardır: ∅ (ağırlık 1/3), {B} ve {C} (ağırlık 1/6), {B, C} (ağırlık 1/3).

φ_A = (1/3)·10 + (1/6)·(50 − 20) + (1/6)·(60 − 30) + (1/3)·(120 − 70) = 10/3 + 5 + 5 + 50/3 = 30

B için: (1/3)·20 + (1/6)·(50 − 10) + (1/6)·(70 − 30) + (1/3)·(120 − 60) = 20/3 + 20/3 + 20/3 + 20 = 40. C için: (1/3)·30 + (1/6)·(60 − 10) + (1/6)·(70 − 20) + (1/3)·(120 − 50) = 10 + 25/3 + 25/3 + 70/3 = 50. İki yöntem aynı sonucu verir.

Sonucun yorumu. C en büyük payı (50) alır, çünkü hem tek başına en değerli oyuncudur (30) hem de her gruba en çok değeri katar. A en az payı (30) alır. Yine de A'nın payı tek başına değerinin (10) üç katıdır, çünkü A'nın gruplara kattığı sinerji büyüktür: A, {B, C}'ye 50 katar. Shapley değeri, her oyuncuya tek başına değerini ve buna ek olarak yarattığı sinerjilerden ortalama payını verir.

10.4.7Kod izleme: shapley()

Shapley değerinin tanımı doğrudan koda dönüştürülebilir. Fonksiyon iki girdi alır: oyuncu listesi N = ["A", "B", "C"] ve karakteristik fonksiyon v. v, anahtarları frozenset olan bir sözlüktür: v[frozenset()] = 0, v[frozenset({"A"})] = 10, …, v[frozenset({"A", "B", "C"})] = 120. frozenset, değiştirilemeyen bir kümedir; sıradan küme sözlük anahtarı olamaz, değiştirilemeyen küme olabilir.

def shapley(N, v):
  phi = {i: 0 for i in N}
  siralar = list(permutations(N))
  for sira in siralar:
    S = frozenset()
    for i in sira:
      katki = v[S | {i}] - v[S]
      phi[i] += katki
      S = S | {i}
  return {i: phi[i] / len(siralar) for i in N}

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

1. phi = {i: 0 for i in N}: Her oyuncunun toplam katkısı 0'dan başlar.
2. siralar = list(permutations(N)): permutations bütün geliş sıralarını üretir: üç oyuncu için 3! = 6 sıra.
3. for sira in siralar: Her sıra ayrı ayrı işlenir. S = frozenset() ile koalisyon boş başlar.
4. for i in sira: Oyuncular sıradaki dizilişleriyle gelir.
5. katki = v[S | {i}] - v[S]: i'nin marjinal katkısı. S | {i}, S'ye i'nin eklenmiş hâlidir; frozenset ile sıradan kümenin birleşimi yine frozenset olduğu için sözlük anahtarı olarak kullanılabilir.
6. phi[i] += katki ve S = S | {i}: Katkı i'nin toplamına eklenir, i koalisyona katılır.
7. return {i: phi[i] / len(siralar) for i in N}: Toplamlar sıra sayısına (6) bölünür.

Tablo 10.15 ve Şekil 10.12 izlemeyi gösterir. Döngüler bitince phi = {A: 180, B: 240, C: 300} olur. Son satır her toplamı 6'ya böler ve {A: 30.0, B: 40.0, C: 50.0} döndürür. İzleme Tablo 10.14'ün sütunlarını satır satır biriktirir; her sıranın sonunda phi'nin toplamı 120 artar (ilk sıradan sonra 120, ikinciden sonra 240, …, altıncıdan sonra 720 = 6 · 120).

Kodun maliyeti n! · n adımdır: n! sıranın her birinde n oyuncu işlenir. n = 10 için bu yaklaşık 36 milyon adımdır ve bir bilgisayar için hâlâ yapılabilir; n = 20 için ise 20! · 20 ≈ 4,9 · 10¹⁹ adımdır ve yapılamaz. Büyük oyunlarda siralar listesi yerine rastgele seçilmiş birkaç bin sıra kullanılır; geri kalan kod değişmez.

10.4.8Oyuna dönüş: ikili sinerji modeli

Açılıştaki Shapley Koalisyon Oyunu'na (10.1.1) dönelim. Oyunda bir koalisyonun değeri, üyelerin tek başına değerleri ile içindeki her ikilinin sinerji bonusunun toplamıdır. Örnek turda tek başına değerler A 6, B 4, C 5; sinerjiler A–B 4, A–C 2, B–C 0'dır. Karakteristik fonksiyon şöyledir: v(A) = 6, v(B) = 4, v(C) = 5, v(AB) = 6 + 4 + 4 = 14, v(AC) = 6 + 5 + 2 = 13, v(BC) = 4 + 5 + 0 = 9, v(ABC) = 15 + 6 = 21.

Bu modelde altı sırayı tek tek hesaplamaya gerek yoktur; Shapley değeri kısa bir kurala iner.

Artık açılıştaki iki soru cevaplanabilir. Eşit bölüşüm A'yı haksızlığa uğratır mı? Katkıya göre ölçülürse evet: A'nın Shapley payı 9'dur, eşit bölüşüm ise 7 verir. A, katkısının 2 altında kalır; B ve C ise katkılarının 1'er üstünde alır. Tek başına en değerli oyuncu her zaman en büyük payı mı almalıdır? Bu turda A hem tek başına en değerli hem de en büyük payı alan oyuncudur, ama bu bir rastlantıdır. Pay, tek başına değere sinerjilerin yarısı eklenerek bulunur. Tek başına değeri düşük ama büyük sinerjilerin ortağı olan bir oyuncu, tek başına değeri yüksek ama kimseyle sinerjisi olmayan bir oyuncudan fazla alabilir. Örneğin sinerjiler A–B 10, A–C 0, B–C 0 olsaydı B'nin payı 4 + 5 = 9, C'nin payı 5 olurdu; tek başına değeri daha yüksek olan C daha az alırdı.

Oyun, sonucu bir eşit bölüşüm hatası ile ölçer: eşit bölüşümün Shapley değerinden toplam sapması. Örnek turda bu hata |7 − 9| + |7 − 6| + |7 − 6| = 2 + 1 + 1 = 4'tür.

Gerçekte insanlar nasıl paylaşır? Deneyler kuramın tek başına yeterli olmadığını gösterir. Üç kişilik koalisyon oyunlarında başkaları için “adil” paylaşım öneren deneklerin seçimleri, Shapley değeri ile eşit bölüşümün bir karışımı olarak en iyi açıklanmıştır (de Clippel ve Rozen, 2022). İnsanlar katkıyı önemser, ama eşitliği de önemser. Örnekte yarı yarıya bir karışım ½ · (9, 6, 6) + ½ · (7, 7, 7) = (8; 6,5; 6,5) verir. Katkıya göre paylaşım (Shapley) ile eşit paylaşım çoğu zaman ayrışır; hangisinin adil sayılacağı bağlama bağlıdır. Bir ortaklıkta yatırımcılar katkıya göre, bir ailede ise kardeşler eşit paylaşımı adil bulabilir.

10.4.9Çekirdek

Shapley değeri bir adalet ölçütüdür: her oyuncuya katkısının ortalamasını verir. Ancak adil bir paylaşım kararlı olmayabilir. Bir alt grup, büyük koalisyondan ayrılıp kendi değerini kendi aralarında paylaşırsa daha fazlasını alıyorsa, paylaşım ne kadar adil görünürse görünsün o grup ayrılır. Kararlılığı ölçen kavram çekirdektir.

“Engelleme” fikri şöyle somutlaşır. S'nin üyeleri x'te toplam 35 alıyor, ama ayrılırlarsa birlikte 50 kazanabiliyorsa, 50'yi öyle paylaşabilirler ki her biri x'te aldığından fazlasını alır (ör. fazladan 15'i eşit bölerek). Bu yüzden S'nin x'i kabul etmesi için bir neden yoktur. Çekirdek, hiçbir grubun böyle bir itirazının olmadığı paylaşımların kümesidir.

Tanımdaki eşitsizlikler tek oyunculu S'ler için bireysel rasyonelliği, büyük koalisyon için verimliliği içerir. Bu yüzden çekirdekteki her ödeme vektörü bir paylaşımdır. Lojistik oyununda çekirdeği tanımlayan kısıtlar şunlardır:

Tekli kısıtlar

x_A ≥ 10, x_B ≥ 20, x_C ≥ 30

İkili kısıtlar

x_A + x_B ≥ 50, x_A + x_C ≥ 60, x_B + x_C ≥ 70

Verimlilik

x_A + x_B + x_C = 120

Çekirdek bir doğrusal eşitsizlikler sistemidir (Gillies, 1959). Doğrusal eşitsizliklerin çözüm kümesi bir çokgen (genel olarak çokyüzlü) bölgedir. Bu yüzden çekirdek boş olabilir, tek bir noktadan oluşabilir ya da bir bölge olabilir. Üç durumun üçü de bu kesimde örneklerle görülür.

İkili kısıtların kısa yolu. Verimlilik eşitliği kullanılarak ikili kısıtlar tek oyunculu üst sınırlara çevrilir. x_A + x_B ≥ 50 ve x_A + x_B = 120 − x_C olduğundan 120 − x_C ≥ 50, yani x_C ≤ 70 bulunur. Aynı yolla x_B ≤ 120 − 60 = 60 ve x_A ≤ 120 − 70 = 50 çıkar. Genel olarak üç oyunculu bir oyunda her oyuncu en çok v(N) − v(N ∖ {i}) alabilir. Bu değer, i'nin büyük koalisyona son katılan olarak kattığı değerdir; i bundan fazlasını alırsa geri kalan ikisi ayrılıp kendi değerlerini alır.

Shapley ile çekirdek. Shapley değeri adalet, çekirdek kararlılık ölçütüdür; ikisi her zaman örtüşmez. Shapley değeri çekirdeğin dışında kalabilir, çekirdek boşken de Shapley değeri her zaman vardır. Ancak bir oyun sınıfında ikisi uyumludur.

Teoremin kanıtı bu notun kapsamı dışındadır, ama lojistik oyununun dışbükey olduğu kolayca denetlenir. Tablo 10.17 her oyuncunun dört koalisyona kattığı değeri listeler. Her satırda değerler soldan sağa artar: koalisyon büyüdükçe katkı büyür. Örneğimiz dışbükey bir oyundur; bu yüzden Shapley paylaşımı (30, 40, 50) çekirdektedir. Bu, 10.4.11'deki kısıt denetimiyle de doğrulanır.

Dışbükeylik yeterli bir koşuldur, gerekli değildir: dışbükey olmayan bir oyunda da Shapley değeri çekirdekte olabilir. Çekirdeğin boş olup olmadığını kesin olarak belirleyen koşul Bondareva–Shapley teoremidir (Bondareva, 1963; Shapley, 1967): çekirdek ancak ve ancak oyun dengeli (balanced) ise boş değildir. Genel tanım teknik olsa da üç oyunculu oyunlarda koşul somut bir hâl alır. Üç oyunculu bir oyunda çekirdek ancak ve ancak şu iki koşul sağlanırsa boş değildir:

• Her koalisyon yapısının toplam değeri v(N)'yi aşmaz: v(N) ≥ v(A) + v(B) + v(C) ve her i için v(N) ≥ v({i}) + v(N ∖ {i}).
• İkililerin değerlerinin yarısının toplamı v(N)'yi aşmaz: v(N) ≥ ½ · [v(AB) + v(AC) + v(BC)].

İkinci koşulun neden gerekli olduğu kolayca görülür: çekirdekteki bir x için üç ikili kısıt toplanırsa 2(x_A + x_B + x_C) ≥ v(AB) + v(AC) + v(BC) bulunur; sol taraf 2v(N)'dir. Lojistik oyununda ½ · (50 + 60 + 70) = 90 ≤ 120 ve her yapının değeri en çok 80'dir; iki koşul da sağlanır.

10.4.10Çekirdeğin geometrisi

Üç oyunculu bir oyunda paylaşımlar bir üçgen üzerinde çizilebilir. Verimlilik eşitliği x_A + x_B + x_C = 120 sayesinde üç sayıdan ikisi seçilince üçüncüsü belirlenir; bu yüzden paylaşımlar iki boyutlu bir bölgede yaşar.

Şekil 10.13 başlangıç durumunu gösterir. Her oyuncu önce tek başına değerini alır: 10 + 20 + 30 = 60. Geriye 120 − 60 = 60 birimlik bir fazla kalır. Bu fazlanın üç oyuncu arasında her bölünüşü üçgenin bir noktasıdır. Köşelerde fazlanın tamamı tek bir oyuncuya gider. Örneğin C köşesinde C, kendi 30'una ek olarak 60'ın hepsini alır ve (10, 20, 90) paylaşımı elde edilir.

Çekirdek, bu üçgenden ikili kısıtların kestiği parçalar çıkarılarak bulunur.

1. {A, B} kısıtı. x_A + x_B ≥ 50 ⇔ x_C ≤ 70. C'ye 70'ten fazlası verilirse A ve B birlikte 50'den az alır; ayrılıp kendi 50'lerini alırlar. Bu kısıt, C köşesinin çevresindeki küçük üçgeni keser.
2. {A, C} kısıtı. x_A + x_C ≥ 60 ⇔ x_B ≤ 60. B köşesi kesilir.
3. {B, C} kısıtı. x_B + x_C ≥ 70 ⇔ x_A ≤ 50. A köşesi de kesilir.

Şekil 10.14'te kalan bölge altı köşeli bir çokgendir. Köşeleri, her oyuncunun payının alt sınırında (tek başına değer) ya da üst sınırında (v(N) − v(N ∖ {i})) olduğu noktalardır: x_A ∈ [10, 50], x_B ∈ [20, 60], x_C ∈ [30, 70]. Bir oyuncu alt sınırında, bir başkası üst sınırındaysa üçüncünün payı verimlilikten belirlenir. Örneğin A 10, B 60 alırsa C 120 − 70 = 50 alır. Altı köşe şunlardır: (10, 40, 70), (10, 60, 50), (30, 20, 70), (30, 60, 30), (50, 20, 50), (50, 40, 30).

Şekildeki üç nokta çekirdeğin üç farklı durumunu gösterir. Shapley değeri altıgenin içindedir: üç sınırın hiçbirine dayanmaz. Eşit bölüşüm de içeridedir: 40 ≤ 50, 40 ≤ 60, 40 ≤ 70. C'nin önerisi y ise C köşesinin kesilen parçasındadır: x_C = 85 > 70. Geometri, “hangi koalisyon engeller?” sorusunu da cevaplar: y'nin dışarıda kaldığı kenar {A, B} kısıtının kenarıdır; y'yi engelleyen koalisyon {A, B}'dir.

10.4.11Çekirdek kontrolü adım adım

Bir paylaşımın çekirdekte olup olmadığı, yedi kısıtın her biri tek tek denetlenerek bulunur. Bir paylaşım çekirdekteyse hiçbir koalisyon ayrılıp kendi değerini (v(S)) alarak daha iyi duruma geçemez.

Tablo 10.18 iki paylaşımın denetimini özetler. Tek bir ✗ paylaşımı çekirdek dışına atmaya yeter. Bir paylaşımı çekirdekten çıkarmak için engelleyen bir koalisyon bulmak yeterlidir; çekirdekte olduğunu göstermek için ise bütün kısıtların denetlenmesi gerekir.

Kısa yolla denetim. 10.4.9'daki üst sınırlar (x_A ≤ 50, x_B ≤ 60, x_C ≤ 70) ve alt sınırlar (tek başına değerler) bilinirse, toplamı 120 olan bir paylaşım altı sayı karşılaştırılarak denetlenir. Örneğin orantılı paylaşım (20, 40, 60) için: 10 ≤ 20 ≤ 50, 20 ≤ 40 ≤ 60, 30 ≤ 60 ≤ 70. Hepsi sağlanır; orantılı paylaşım da çekirdektedir. Lojistik oyununda çekirdek geniştir ve Tablo 10.13'teki dört önerinin üçü (eşit, orantılı, Shapley) çekirdekte yer alır. Çekirdek bu oyunda tek bir paylaşım seçmez; yalnız kabul edilemez paylaşımları eler.

10.4.12Çekirdeği boş bir oyun: çoğunluk oyunu

Lojistik oyununda çekirdek geniş bir altıgendi. Her oyunda böyle bir kararlı paylaşım bulunmaz.

Çekirdeğin boş olmasının ne anlama geldiği bir pazarlık dizisiyle görülür. Diyelim ki A ve B anlaşıp ödülü (½, ½, 0) paylaştı. Dışarıda kalan C, A'ya (0,6; 0; 0,4) önerir: A 0,5 yerine 0,6, C 0 yerine 0,4 alır; ikisi de kazanır. Bu kez dışarıda kalan B, C'ye (0; 0,3; 0,7) önerir: C 0,4 yerine 0,7, B 0 yerine 0,3 alır. Şimdi de A dışarıdadır ve B'ye daha iyi bir teklif yapabilir. Her paylaşımda en az bir çift toplam en çok 2/3 alır (çünkü üç çiftin toplamı 2'dir) ve bu çift üçüncüyü dışlayıp 1'i paylaşmak ister. Pazarlık hiç bitmez.

Ders: kararlı paylaşım her oyunda yoktur. Bu durumda kuralı gevşetmek gerekir. “Hiçbir grup ayrılarak hiçbir şey kazanamasın” yerine “hiçbir grup ayrılarak çok fazla kazanamasın” denir. Bu fikir ε-çekirdek kavramıyla ifade edilir: hiçbir koalisyon ayrılarak ε'dan fazla kazanamaz, yani her S için Σ_i∈S x_i ≥ v(S) − ε. Çoğunluk oyununda ikili kısıtlar x_i + x_j ≥ 1 − ε olur. Üçü toplanınca 2 ≥ 3(1 − ε), yani ε ≥ 1/3 çıkar. ε = 1/3 için (1/3, 1/3, 1/3) paylaşımı her ikili kısıtı tam eşitlikle sağlar: 2/3 = 1 − 1/3. ε'u en küçük yapan paylaşımlar kümesine en küçük çekirdek denir. Bu fikri adım adım sürdürerek her oyunda tek bir paylaşım seçen çözüme çekirdekçik (nucleolus) denir; çoğunluk oyununda çekirdekçik de (1/3, 1/3, 1/3)'tür.

10.4.13Ağırlıklı oylama ve güç endeksleri

Koalisyon oyunlarının önemli bir uygulaması oylamadır. Bir mecliste partilerin sandalye sayıları, bir şirkette ortakların hisse oranları, bir ağda düğümlerin oy hakları farklı olabilir. Ağırlığı fazla olanın gücü de fazla mıdır? Bu kesim cevabın “her zaman değil” olduğunu gösterir.

Bir oyuncunun oylamadaki gücü, kararları ne sıklıkla belirlediğiyle ölçülür. Bunu ölçen iki klasik endeks vardır.

Shapley–Shubik endeksi (Shapley ve Shubik, 1954), ağırlıklı oylama oyununun Shapley değeridir. Oylama oyununda marjinal katkı yalnız 0 ya da 1 olabilir: oyuncu kotayı geçiren kişiyse katkısı 1, değilse 0'dır. Bu yüzden i'nin Shapley değeri, i'nin kilit olduğu sıraların oranıdır.

Banzhaf endeksi ise sıralara değil koalisyonlara bakar. Her kazanan koalisyonda hangi üyelerin kritik olduğu sayılır. Bir oyuncunun Banzhaf endeksi, kritik üyelik sayısının bütün oyuncuların kritik üyelik sayıları toplamına oranıdır.

Şekil 10.15 sonucun çarpıcılığını gösterir. B ile C arasında 48 sandalye fark vardır, ama iki parti eşit güçtedir. Neden? Kazanmanın tek yolu A'yı içeren bir koalisyondur ve A'ya kotayı geçmek için tek bir sandalye yeter. B'nin fazladan 48 sandalyesi hiçbir koalisyonun sonucunu değiştirmez. Güç, ağırlıkla değil, oyuncunun sonucu değiştirebildiği durumların sayısıyla ölçülür. Ağırlık ≠ güç.

İki endeks farklı sayılar verir, çünkü farklı şeyleri sayar. Shapley–Shubik endeksi koalisyonların hangi sırayla kurulduğunu önemser ve büyük koalisyonun oluşum sürecini modeller. Banzhaf endeksi sıraya bakmaz; her kazanan koalisyonu eşit sayar. İkisi de A'yı en güçlü, B ile C'yi eşit bulur. Bu, sıralama açısından iki endeksin bu oyunda anlaştığını gösterir.

Tarihsel bir örnek: 1958 AET Bakanlar Konseyi. Avrupa Ekonomik Topluluğu'nun kuruluşunda Bakanlar Konseyi'nde oylar şöyle dağıtılmıştı: Fransa, Almanya ve İtalya 4'er; Belçika ve Hollanda 2'şer; Lüksemburg 1 oy. Nitelikli çoğunluk için 12 oy gerekiyordu: oyun [12; 4, 4, 4, 2, 2, 1]'dir. Lüksemburg'un oyu hiçbir koalisyonun sonucunu değiştiremiyordu. Nedeni bir çift-tek sayı gözlemidir: Lüksemburg dışındaki bütün ağırlıklar çifttir, bu yüzden Lüksemburg'suz her koalisyonun toplamı çifttir. Lüksemburg'un 1 oyu bir koalisyonu kotanın altından kotaya ancak toplam tam 11 iken taşıyabilirdi; ama 11 tek sayıdır ve hiçbir koalisyonun toplamı 11 olamaz. Bu yüzden Lüksemburg hiçbir sırada kilit değildir ve gücü 0'dır. Diğer ülkelerin Shapley–Shubik endeksi büyük üçlü için 7/30, Belçika ve Hollanda için 3/20'dir.

10.4.14Kod izleme: guc_endeksi()

Shapley–Shubik endeksi, Shapley değerinin kodundan daha basit bir kodla hesaplanır: koalisyon değerine bakmak yerine ağırlıklar toplanır ve kotayı geçen oyuncu kaydedilir. Fonksiyon üç girdi alır: oyuncu listesi N, ağırlık sözlüğü w = {"A": 50, "B": 49, "C": 1} ve kota q = 51.

def guc_endeksi(N, w, q):
  kilit = {i: 0 for i in N}
  siralar = list(permutations(N))
  for sira in siralar:
    toplam = 0
    for i in sira:
      toplam += w[i]
      if toplam >= q:
        kilit[i] += 1
        break
  return {i: kilit[i] / len(siralar) for i in N}

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

1. kilit = {i: 0 for i in N}: Her oyuncunun kilit olduğu sıra sayısı 0'dan başlar.
2. siralar = list(permutations(N)): Bütün geliş sıraları (3! = 6) üretilir.
3. toplam = 0: Her sıra boş koalisyonla, yani 0 oyla başlar.
4. toplam += w[i]: Gelen oyuncunun ağırlığı toplama eklenir.
5. if toplam >= q: Toplam kotaya ilk kez ulaştıysa gelen oyuncu kilittir; kilit[i] bir artırılır.
6. break: Bu sırada kilit bulundu; sıranın geri kalanı önemli değildir. İç döngü kesilir ve bir sonraki sıraya geçilir. Her sırada tam bir kilit oyuncu vardır.
7. return {i: kilit[i] / len(siralar) for i in N}: Kilit sayıları sıra sayısına bölünür.

Tablo 10.19, Şekil 10.16 ve Şekil 10.17 izlemeyi gösterir. Sonuçta kilit = {A: 4, B: 1, C: 1} olur ve fonksiyon (2/3, 1/6, 1/6) döndürür. B'nin 49 sandalyesi C'nin 1 sandalyesinden fazla güç getirmez. İzlemenin break satırı önemlidir: B → C → A sırasında B ve C gelince toplam 50 olur; A gelince 100'e çıkar ve A kilittir. break olmasaydı kod, kota geçildikten sonra gelen oyunculara da kilit sayardı ve sonuç yanlış olurdu.

10.4.15Koalisyon oyunlarında sık hatalar

10.5Kamu malı oyunu

Koalisyon oyunlarında bağlayıcı anlaşma yapılabildiği varsayılıyordu. Birçok çoklu ajan sisteminde ise böyle bir anlaşma yoktur: her ajan ortak bir kaynağa ne kadar katkı vereceğine kendi başına karar verir ve kimse onu katkı vermeye zorlayamaz. Bu kesim, Mahkûmun İkilemi'nin çok oyunculu sürümü olan kamu malı oyununu inceler. Oyun, ortak iyinin neden kendiliğinden ortaya çıkmadığını sayılarla gösterir.

10.5.1Kamu malı nedir?

Açık kaynak yazılım iyi bir örnektir. Kodu yazan da yazmayan da yazılımı indirip kullanabilir (dışlanamazlık). Bir kişinin yazılımı kullanması başkasının kullanımını azaltmaz (rakip olmama). Temiz hava ve ortak bir veri kümesi de kamu malıdır. Bir ekmek ise kamu malı değildir: parasını ödemeyen alamaz, bir kişinin yediği ekmeği başkası yiyemez.

Kamu mallarının sorunu, dışlanamazlıktan doğar. Mal herkese açık olduğu için her kişi şunu düşünebilir: “Ben katkı vermesem de başkaları verir, ben de yararlanırım.” Herkes böyle düşünürse kimse katkı vermez ve mal hiç üretilmez.

10.5.2Oyunun kuralları

Kazanç formülü iki parçadan oluşur. e − k_i, oyuncunun cebinde tuttuğu jetonlardır. (r/n) · Σ k_j, havuzdan aldığı paydır. Bu pay, oyuncunun kendi katkısına değil, herkesin toplam katkısına bağlıdır. Katkı vermeyen oyuncu da havuzdan aynı payı alır; dışlanamazlık formülün içindedir.

Bölümün örneği şu sayıları kullanır: n = 4 oyuncu, her biri e = 10 jeton, çarpan r = 1,6. Kişi başı marjinal getiri r/n = 1,6/4 = 0,4'tür. Bir jeton katkının iki ayrı sonucu vardır.

Bireysel sonuç

1 jeton katkı veren oyuncunun cebinden 1 jeton çıkar, havuzdan kendisine 0,4 döner. Net etki −1 + 0,4 = −0,6'dır.

Sosyal sonuç

1 jeton havuzda 1,6'ya dönüşür ve dört oyuncuya 0,4'er dağıtılır. Grubun toplam kazancı −1 + 1,6 = +0,6 artar.

Bireysel ve sosyal sonucun işaretleri terstir. Katkı oyuncuya zarar verir, ama gruba fayda sağlar. İkilemin özü budur.

Tablo 10.20 ikilemi açıkça gösterir. O1 için en iyi durum, başkaları verirken kendisinin vermemesidir (22). En kötü durum, başkaları vermezken kendisinin vermesidir (4). Grup için ise en iyi durum herkesin vermesidir (64), en kötü durum kimsenin vermemesidir (40). Toplam sütunu bir kural daha gösterir: grubun toplamı n · e + (r − 1) · Σk = 40 + 0,6 · Σk'dır. Havuza giren her jeton grubun toplamını 0,6 artırır.

10.5.3Neden beleşçilik?

O1'in kazancı, diğer üç oyuncunun toplam katkısı K ile yazılırsa

u₁ = 10 − k₁ + 0,4 · (k₁ + K) = 10 + 0,4K − 0,6 k₁

olur. O1 bir jeton daha verirse cebinden 1 jeton çıkar, havuzdan 0,4 geri gelir: net −0,6. Bu değer K'ye bağlı değildir. Diğerleri ne yaparsa yapsın, her jeton katkı O1'e 0,6 kaybettirir.

Örnekte tek Nash dengesi herkesin 0 vermesidir ve kişi başı kazanç 10'dur. Oysa herkes 10 verse kişi başı 16 olurdu. Denge Pareto optimal değildir. Katkı vermeden ortak maldan yararlanan oyuncuya beleşçi (free rider), bu davranışa beleşçilik (free riding) denir.

Şekil 10.18 ikilemi iki doğruyla çizer. Kırmızı doğru O1'in bireysel bakışıdır: diğerleri 10 verirken u₁ = 10 + 0,4 · 30 − 0,6k = 22 − 0,6k. O1'in her jetonu kazancını 0,6 düşürür; en iyisi hiç vermemektir. Mavi doğru grubun bakışıdır: herkes k verirse u = 10 − k + 0,4 · 4k = 10 + 0,6k. Herkesin her jetonu kişi başı kazancı 0,6 artırır; en iyisi herkesin tam vermesidir. İki doğrunun eğimleri zıt işaretlidir: bireysel teşvik (−0,6) ile sosyal refah (+0,6) ters yöndedir. Bu, Mahkûmun İkilemi'nin n kişilik hâlidir.

10.5.4İkilem ne zaman vardır?

İkilemin varlığı iki koşula bağlıdır. Bir jetonluk katkı, katkıyı verene r/n, gruba toplam r olarak döner.

• Bireysel koşul: r/n < 1, yani r < n. Katkı bireysel olarak zararlıdır; vermemek baskındır.
• Sosyal koşul: r > 1, yani r/n > 1/n. Her jeton grubun toplamını r − 1 > 0 artırır; katkı sosyal olarak faydalıdır.

İki koşul birlikte, yani 1 < r < n (eşdeğer olarak 1/n < r/n < 1), ikilemi oluşturur. Koşulun dışındaki iki durumda ikilem yoktur.

Örnek 10.14 tasarım açısından önemli bir sonuç verir. İkilemi ortadan kaldırmanın bir yolu, katkının bireye dönen kısmını 1'in üstüne çıkarmaktır. Bunun için çarpanı grup büyüklüğünden büyük yapmak çoğu zaman gerçekçi değildir. Ama katkıya bağlı bir ödül (ör. katkı verene öncelik) aynı etkiyi yaratır: katkı verenin kişisel getirisi artar.

10.5.5Çoklu ajan sistemlerindeki karşılıklar

Kamu malı oyunu soyut bir laboratuvar oyunu değildir; çoklu ajan sistemlerinde doğrudan karşılıkları vardır.

Dosya paylaşım ağları

Eşler arası (P2P) bir ağda her eş dosya indirir ve başkalarına dosya yükler. Yükleme bant genişliği harcar, ama ağın bütününe fayda sağlar. Yükleme yapmadan yalnızca indiren eş beleşçidir. Herkes böyle davranırsa ağda indirilecek dosya kalmaz.

Federe öğrenme

Birçok istemci (telefon, hastane, şirket) ortak bir makine öğrenmesi modelini birlikte eğitir. Her istemci kendi verisiyle hesapladığı güncellemeyi gönderir. Güncelleme göndermek işlemci, enerji ve veri gizliliği açısından maliyetlidir. Güncelleme göndermeden ortak modeli kullanan istemci beleşçidir.

Ortak hesaplama ve veri havuzları

Bir topluluk ortak bir veri kümesi ya da açık kaynak bir kütüphane oluşturur. Katkı vermeden kullanan çoktur; katkı veren az sayıda kişi yükün tamamını taşır.

Bu sistemlerin tasarımcıları beleşçiliği azaltmak için oyunun kazançlarını değiştirir. Katkıyı ödüllendirmek (yükleme yapan eşe daha hızlı indirme hakkı vermek), katkı vermeyeni dışlamak (malı kısmen dışlanabilir yapmak) ya da etkileşimi tekrarlı kılıp itibar kaydı tutmak yaygın yollardır. Hepsinin ortak fikri, katkının bireysel getirisini artırarak bireysel teşviki sosyal refahla aynı yöne çevirmektir. Bu, 10.2.6'daki teşvik tasarımı ilkesinin kamu malına uygulanmasıdır.

10.5.6Kamu malında sık hatalar

10.6Özet

• Ajan, otonom, reaktif, proaktif ve sosyal yetenekli bir sistemdir (Wooldridge ve Jennings, 1995). Çoklu ajan sistemi, aynı çevrede algılayan ve eylem yapan birden fazla ajandan oluşur; her ajanın bilgisi yereldir. Oyun kuramında ajan, beklenen faydasını maksimize eden rasyonel bir oyuncudur.
• Mimari (reaktif, planlayan, BDI, öğrenen, hibrit) ajanın içini; oyun kuramı ajanlar arasındaki etkileşimi anlatır.
• Sistemler işbirlikçi (sorun koordinasyon), rekabetçi (sorun strateji) ya da karma güdülü olabilir. Üç küçük oyun bu yelpazeyi temsil eder: koordinasyon oyununda iki denge, Mahkûmun İkilemi'nde verimsiz tek denge, Yazı-Tura'da yalnız karışık denge (½, ½).
• Çoğu gerçek sistem hibrit kontrol kullanır: ajanlar otonom karar verir, merkez kuralları, fiyatları ya da ihaleleri belirler. Konvansiyon, koordinasyon oyununda bir dengeyi önceden seçer; trafik ışığı gibi ortak bir sinyal korelasyonlu denge üretir.
• Öğrenen ajanların çevresi durağan değildir; eşzamanlı en iyi tepki koridor oyununda sonsuz döngüye girebilir. Basit yerel kurallar ortaya çıkan davranış üretir (Schelling'in ayrışma modeli).
• Sözleşme ağı: duyuru → teklif → ödül. Dağıtık ve basittir, görev başına O(n) mesaj gerektirir, ama açgözlü ve sıralıdır: örnekte 18 dk, optimum 13 dk (%38 fazla). Görev sırası sonucu değiştirir; yeniden ihale (takas) örnekte iki adımda optimuma ulaşır.
• Tüm atamaları denemek n! iş gerektirir (n = 10'da 3.628.800); Macar algoritması O(n³)'tür. Kazanana kendi teklifi ödenirse yüklenici maliyetini şişirir; ikinci en düşük teklif ödenirse dürüst teklif en iyisidir.
• Karakteristik fonksiyon v(S) her koalisyonun değerini verir. Süperadditif oyunda büyük koalisyon oluşur. Koalisyon yapılarının sayısı Bell sayısıdır (3 ajan 5, 4 ajan 15, 10 ajan 115.975).
• Shapley değeri = ortalama marjinal katkı; dört aksiyomu (verimlilik, simetri, kukla oyuncu, toplamsallık) sağlayan tek kuraldır. Lojistik örneğinde φ = (30, 40, 50). İkili sinerji modelinde φ_i = tek başına değer + sinerjilerin yarısı: oyunun örnek turunda (9, 6, 6), eşit bölüşüm hatası 4.
• Çekirdek: hiçbir koalisyonun ayrılmak istemediği paylaşımlar. Lojistik örneğinde altı köşeli bir çokgendir ve Shapley değerini içerir (oyun dışbükeydir). y = (10, 25, 85)'i {A, B} engeller. Çoğunluk oyununda çekirdek boştur; en küçük ε-çekirdek ε = 1/3 ile (1/3, 1/3, 1/3)'tür.
• Ağırlıklı oylamada güç ≠ ağırlık: [51; 50, 49, 1]'de Shapley–Shubik (2/3, 1/6, 1/6), Banzhaf (3/5, 1/5, 1/5). 1958 AET Konseyi'nde Lüksemburg'un gücü 0'dı.
• Kamu malı oyununda r/n < 1 ise katkı vermemek baskındır: denge kişi başı 10, herkes tam katkı verirse 16. İkilem 1 < r < n iken vardır. Beleşçi (yalnızca indiren eş, güncelleme göndermeyen istemci) bireysel olarak kazanır, sistem kaybeder.

10.7Kavram listesi

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

• ajan agent
• çoklu ajan sistemi multi-agent system (MAS)
• otonomi autonomy
• reaktivite reactivity
• proaktivite pro-activeness
• sosyal yetenek social ability
• planlayan ajan deliberative agent
• inanç–arzu–niyet (BDI) belief–desire–intention (BDI)
• karma güdü mixed-motive
• koordinasyon oyunu coordination game
• konvansiyon / sosyal yasa convention / social law
• korelasyonlu denge correlated equilibrium (CE)
• durağan olmayan non-stationary
• kurgusal oyun fictitious play
• ortaya çıkan davranış emergent behavior
• görev tahsisi task allocation
• kaynak tahsisi resource allocation
• sözleşme ağı protokolü Contract Net Protocol
• yönetici / yüklenici manager / contractor (contract net)
• duyuru / teklif / ödül task announcement / bid / award
• açgözlü greedy (algorithm)
• Macar algoritması Hungarian algorithm
• yeniden ihale re-auction (re-tendering)
• kombinatoryal açık artırma combinatorial auction
• koalisyon coalition
• büyük koalisyon grand coalition
• koalisyon oluşumu coalition formation
• koalisyon yapısı coalition structure
• Bell sayısı Bell number
• karakteristik fonksiyon characteristic function
• aktarılabilir faydalı (TU) oyun transferable-utility (TU) game
• süperadditif superadditive
• paylaşım imputation
• marjinal katkı marginal contribution
• Shapley değeri Shapley value
• verimlilik aksiyomu efficiency axiom
• simetri aksiyomu symmetry axiom
• kukla oyuncu dummy (null) player
• toplamsallık additivity
• çekirdek core
• engellemek to block (a coalition blocks)
• dışbükey oyun convex game
• dengeli oyun balanced game
• Bondareva–Shapley teoremi Bondareva–Shapley theorem
• çoğunluk oyunu majority game
• ε-çekirdek ε-core
• çekirdekçik nucleolus
• ağırlıklı oylama oyunu weighted voting game
• kota quota
• kilit oyuncu pivotal player
• kritik üye critical (swing) member
• güç endeksi power index
• Shapley–Shubik endeksi Shapley–Shubik index
• Banzhaf endeksi Banzhaf index
• kamu malı public good
• kamu malı oyunu public goods game
• kişi başı marjinal getiri (MPCR) marginal per-capita return (MPCR)
• beleşçi free rider
• beleşçilik free riding
• ortak mallar trajedisi tragedy of the commons

10.8Kendini Dene

1. Saf koordinasyon oyununda (Sağ, Sağ) her iki oyuncuya 2, (Sol, Sol) her ikisine 1, farklı seçimler 0 verir. Saf Nash dengeleri nelerdir? Karışık dengede her oyuncu Sağ'ı hangi olasılıkla seçer ve beklenen kazanç nedir? Bu kazancı saf dengelerle karşılaştırın.

   Cevap

   Saf dengeler (Sağ, Sağ) = (2, 2) ve (Sol, Sol) = (1, 1)'dir; ikisinde de taraf değiştiren oyuncu 0'a düşer. Karışık denge: 2. oyuncu Sağ'ı q ile oynasın. 1. oyuncu için Sağ 2q, Sol 1 − q verir; kayıtsızlık 2q = 1 − q ⇒ q = 1/3. Simetriden p = 1/3. Beklenen kazanç 2 · (1/3)(1/3) + 1 · (2/3)(2/3) = 2/9 + 4/9 = 2/3'tür. Bu, iki saf dengenin de (2 ve 1) altındadır: oyuncular sık sık uyumsuz seçim yapar. Bir konvansiyon (“herkes sağdan”) kazancı 2'ye çıkarır.

2. Bir yönetici G1, G2, G3 görevlerini bu sırayla ihaleye çıkarıyor. Maliyetler (dk): G1 için R1 4, R2 5, R3 6; G2 için R1 2, R2 3, R3 6; G3 için R1 7, R2 4, R3 9. Her robot en çok bir görev alır. Sözleşme ağının atamasını ve toplamını, merkezi optimumu ve aradaki farkı (yüzde) bulun.

   Cevap

   G1: teklifler 4, 5, 6 → R1 (4). G2: R2 3, R3 6 → R2 (3). G3: yalnız R3 kalır → 9. Toplam 4 + 3 + 9 = 16 dk. Altı atama: (R1, R2, R3) 16; (R1, R3, R2) 4 + 6 + 4 = 14; (R2, R1, R3) 5 + 2 + 9 = 16; (R2, R3, R1) 5 + 6 + 7 = 18; (R3, R1, R2) 6 + 2 + 4 = 12; (R3, R2, R1) 6 + 3 + 7 = 16. Optimum 12 dk: G1→R3, G2→R1, G3→R2. Sözleşme ağı (16 − 12)/12 ≈ %33 fazladır. Kayıp yine açgözlülükten doğar: G1'i alan R1, G2 için en ucuz robottu (2).

3. Bir görev için robotların gerçek maliyetleri R1 5, R2 7, R3 9'dur ve en düşük teklif kazanır. (a) Kazanana kendi teklifi ödenirse dürüst teklifle R1'in kazancı nedir; R1 teklifini 6,5'e çıkarırsa ne olur? (b) Kazanana ikinci en düşük teklif ödenirse dürüst R1 ne kazanır? (c) Bu kuralda R2 işi almak için 4 teklif ederse ne olur?

   Cevap

   (a) Dürüst teklifle R1 kazanır, 5 alır, kazancı 5 − 5 = 0. 6,5 teklif ederse (diğerleri dürüstse) yine en düşük tekliftir; kazanır ve 6,5 − 5 = 1,5 kazanır. Bu kuralda şişirmek kârlıdır. (b) R1 kazanır ve ikinci en düşük teklif olan 7'yi alır: kazanç 7 − 5 = 2. 7'nin altındaki her teklif aynı sonucu verir. (c) R2 kazanır, ama ödeme ikinci en düşük teklif olan R1'in 5'idir; maliyeti 7 olduğu için kazancı 5 − 7 = −2'dir. Dürüst teklifle kaybeder ve 0 alır; dürüstlük daha iyidir.

4. Üç ajanlı bir oyunda v(A) = 0, v(B) = 0, v(C) = 10, v(AB) = 30, v(AC) = 40, v(BC) = 40, v(ABC) = 60'tır. Shapley değerini altı sıra üzerinden hesaplayın. Oyun süperadditif midir, dışbükey midir?

   Cevap

   Marjinal katkılar (A, B, C): A→B→C (0, 30, 30); A→C→B (0, 20, 40); B→A→C (30, 0, 30); B→C→A (20, 0, 40); C→A→B (30, 20, 10); C→B→A (20, 30, 10). Toplamlar A 100, B 100, C 160; φ = (100/6, 100/6, 160/6) = (50/3, 50/3, 80/3) ≈ (16,67; 16,67; 26,67), toplam 60 ✓. Süperadditiftir: 30 ≥ 0, 40 ≥ 10, 40 ≥ 10 ve her ikili artı tekli en çok 40 + 0 = 40 ya da 30 + 10 = 40'tır, 60'ı aşmaz. Dışbükey değildir: A'nın {B}'ye katkısı 30, daha büyük {B, C}'ye katkısı 60 − 40 = 20'dir; katkı koalisyon büyüyünce azalmıştır.

5. 4. sorudaki oyunda Shapley değeri çekirdekte midir? (20, 20, 20) ve (30, 10, 20) paylaşımlarını da sınayın; dışarıdaysa engelleyen koalisyonu belirtin.

   Cevap

   Üst sınırlar x_i ≤ v(N) − v(N ∖ {i}): x_A ≤ 60 − 40 = 20, x_B ≤ 20, x_C ≤ 60 − 30 = 30; alt sınırlar 0, 0, 10. Shapley (16,67; 16,67; 26,67) bütün sınırların içindedir: çekirdektedir. Oyun dışbükey olmadığı hâlde Shapley değeri çekirdektedir; dışbükeylik yeterli koşuldur, gerekli değildir. (20, 20, 20): sınırların içinde (A ve B tam üst sınırda), çekirdektedir. (30, 10, 20): x_A = 30 > 20; {B, C} yalnız 10 + 20 = 30 < 40 alır ve ayrılıp 40'ı paylaşır. {B, C} engeller.

6. Ağırlıklı oylama oyunu [7; 4, 3, 2, 1]'dir (A 4, B 3, C 2, D 1). Kazanan en küçük koalisyonları, Banzhaf endeksini ve Shapley–Shubik endeksini bulun. C ile D'nin gücünü karşılaştırın.

   Cevap

   Toplam ağırlık 10'dur. Kazanan koalisyonlar: AB (7), ABC (9), ABD (8), ACD (7), ABCD (10). A'sız en iyi koalisyon BCD = 6 < 7, yani A her kazanan koalisyonda vardır. Kritik üyelikler: AB'de A, B; ABC'de A, B (C ayrılınca 7 kalır); ABD'de A, B; ACD'de A, C, D; ABCD'de A. Sayılar A 5, B 3, C 1, D 1, toplam 10: Banzhaf (1/2, 3/10, 1/10, 1/10). Shapley–Shubik (24 sıra): kilit sayıları A 14, B 6, C 2, D 2 ⇒ (7/12, 1/4, 1/12, 1/12). Örneğin C, ancak önünde tam olarak A ve D varsa (toplam 5) kilittir; bu 2! · 1! = 2 sırada olur. C'nin ağırlığı D'nin iki katıdır, ama iki endekste de güçleri eşittir.

7. Kamu malı oyununda n = 3, e = 20, r = 1,5'tir. Herkes 20 verirse, kimse vermezse ve O1 beleşçi olup diğerleri 20 verirse kazançlar nedir? Kişi başı marjinal getiri, bir jetonun bireysel ve sosyal net etkisi nedir? İkilem var mı?

   Cevap

   Herkes 20: havuz 60 · 1,5 = 90, kişi başı 30; herkes 30 alır. Kimse: herkes 20. O1 beleşçi: havuz 40 · 1,5 = 60, kişi başı 20; O1 20 + 20 = 40, diğerleri 0 + 20 = 20. MPCR r/n = 0,5: bir jeton katkı bireye −1 + 0,5 = −0,5, gruba −1 + 1,5 = +0,5 net etki yapar. 1 < 1,5 < 3 olduğu için ikilem vardır: vermemek baskın, denge kişi başı 20; herkes verirse 30.

8. Dört ajan 1 birimlik ödülü paylaşacaktır; en az üç ajan anlaşırsa ödülü alır: v(S) = 1 (|S| ≥ 3), aksi hâlde 0. Çekirdek boş mudur? Shapley değeri nedir?

   Cevap

   Dört üçlü kısıt vardır: her üçlünün payları toplamı en az 1. Her ajan dört üçlünün üçünde yer alır; kısıtlar toplanınca 3(x_A + x_B + x_C + x_D) ≥ 4, yani toplam ≥ 4/3 çıkar. Ama toplam 1 olmalıdır: çekirdek boştur. Dört ajan simetriktir; simetri ve verimlilikten φ = (1/4, 1/4, 1/4, 1/4). Her üçlü bu paylaşımda yalnız 3/4 alır ve dördüncüyü dışlayarak 1'i paylaşmak ister.

10.9İleri okuma

• M. Wooldridge, An Introduction to MultiAgent Systems (2. baskı, 2009): ajan kavramını, ajan mimarilerini (reaktif, BDI, hibrit), sözleşme ağı gibi iletişim protokollerini ve koalisyon oluşumunu az matematikle, bilgisayar mühendisliği bakışıyla anlatan temel ders kitabıdır.
• G. Chalkiadakis, E. Elkind ve M. Wooldridge, Computational Aspects of Cooperative Game Theory (2011): karakteristik fonksiyon, Shapley değeri, çekirdek, çekirdekçik ve ağırlıklı oylama oyunlarını hesaplama karmaşıklığı açısından inceleyen kısa ve düzenli bir kitaptır.
• A. R. Karlin ve Y. Peres, Game Theory, Alive (2017), koalisyonlar ve Shapley değeri bölümü: Shapley aksiyomlarını ve teklik kanıtını çok sayıda örnekle, adım adım verir.
• Y. Shoham ve K. Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (2009), Bölüm 12: işbirlikçi oyun kuramının çözüm kavramlarını (çekirdek, Shapley değeri, çekirdekçik) ve Bondareva–Shapley teoremini biçimsel olarak anlatır; kitabın PDF'i yazarların sitesinde ücretsiz yayımlanmıştır.

10.10Kaynaklar

1. O. N. Bondareva, “Some applications of linear programming methods to the theory of cooperative games”, Problemy Kibernetiki 10, 1963.
2. G. Chalkiadakis, E. Elkind, M. Wooldridge, Computational Aspects of Cooperative Game Theory, Morgan & Claypool, 2011.
3. G. de Clippel, K. Rozen, “Fairness through the lens of cooperative game theory: An experimental approach”, American Economic Journal: Microeconomics 14(3), 2022.
4. FIPA, Contract Net Interaction Protocol Specification (SC00029H), 2002.
5. D. B. Gillies, “Solutions to general non-zero-sum games”, Contributions to the Theory of Games IV, Princeton, 1959.
6. A. R. Karlin, Y. Peres, Game Theory, Alive, American Mathematical Society, 2017.
7. N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory, Cambridge University Press, 2007 (Bölüm 15: maliyet paylaşımı, çekirdek ve Shapley değeri).
8. C. W. Reynolds, “Flocks, herds and schools: A distributed behavioral model”, SIGGRAPH '87, 1987.
9. T. Sandholm, K. Larson, M. Andersson, O. Shehory, F. Tohmé, “Coalition structure generation with worst case guarantees”, Artificial Intelligence 111, 1999.
10. T. C. Schelling, “Dynamic models of segregation”, Journal of Mathematical Sociology 1(2), 1971.
11. L. S. Shapley, “A value for n-person games”, Contributions to the Theory of Games II, Princeton, 1953.
12. L. S. Shapley, “On balanced sets and cores”, Naval Research Logistics Quarterly 14(4), 1967.
13. L. S. Shapley, “Cores of convex games”, International Journal of Game Theory 1, 1971.
14. L. S. Shapley, M. Shubik, “A method for evaluating the distribution of power in a committee system”, American Political Science Review 48(3), 1954.
15. Y. Shoham, K. Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2009 (Bölüm 12).
16. R. G. Smith, “The contract net protocol: High-level communication and control in a distributed problem solver”, IEEE Transactions on Computers C-29(12), 1980.
17. M. Wooldridge, An Introduction to MultiAgent Systems, 2. baskı, Wiley, 2009.
18. M. Wooldridge, N. R. Jennings, “Intelligent agents: Theory and practice”, Knowledge Engineering Review 10(2), 1995.

Ders sayfaları: N. Shah, CSC304 (Toronto) · A. Procaccia, 15-896 (CMU) · T. Roughgarden, CS364A (Stanford) · M. Hoefer, AGT (Frankfurt) · © Sercan Külcü. Tüm hakları saklıdır.