Algoritmik Oyun Kuramında Önemli İsimler

Önemi: Borda sayımı klasik puanlama kuralıdır. Condorcet kaybedenini hiçbir zaman seçmez ama Condorcet kazananını seçemeyebilir.

Borda yöntemini 1770'te Akademiye sundu; yöntem 1784'te yayımlandı. Güçlü rakipler listenin sonuna gömülerek kural kolayca manipüle edilebilir. Bu zayıflık daha sonra Gibbard–Satterthwaite teoremiyle kesin bir biçim kazandı.

Önemi: Condorcet kazananı ve oylama paradoksu, sosyal seçim kuramının ve Arrow'un imkânsızlık teoreminin çıkış noktasıdır.

Jüri teoremine göre her seçmen birbirinden bağımsız olarak p > 1/2 olasılıkla doğru karar veriyorsa seçmen sayısı arttıkça çoğunluk kararının doğru olma olasılığı 1'e yaklaşır. Condorcet, Fransız Devrimi sırasında hapiste öldü.

Önemi: Bouton'un kuralı, minimaksın bütün oyun ağacını gezerek bulduğu sonucu tek bir XOR işlemiyle verir. Kombinatoryal oyun kuramının ilk tam sonuçlarındandır.

Kazandıran hamle, nim toplamını 0 yapan hamledir. Sprague (1935) ve Grundy (1939) bu fikri bütün tarafsız oyunlara genişletti.

Önemi: Borel, simetrik sıfır toplamlı oyunlar için minimaks sorusunu sordu. Genel minimaks teoremini 1928'de von Neumann kanıtladı.

Borel küçük durumları çözdü ama minimaks özelliğinin her oyunda geçerli olduğundan kuşkuluydu. Borel ile von Neumann arasındaki öncelik tartışması 1953'te Econometrica dergisinde yeniden ele alındı.

Önemi: Sonuç, geriye doğru çıkarımın (backward induction) ve mükemmel bilgili sonlu iki oyunculu oyunların belirlenmişliğinin temelidir.

Zermelo daha çok küme kuramı aksiyomlarıyla (1908) tanınır. Satranç makalesi, ders laboratuvarlarında XOX, Nim ve Dörtlü Bağla için kullanılan oyun ağacı aramasının atasıdır.

Önemi: Pigou örneği bencil yönlendirmenin standart örneğidir. Doğrusal gecikmelerde Anarşinin Bedeli (price of anarchy) 4/3'tür. Roughgarden ve Tardos bunun en kötü durum olduğunu kanıtladı.

Pigou, olumsuz dışsallık yaratan etkinliklerin vergilendirilmesini önerdi. Tıkanıklık fiyatlandırması (marjinal maliyet ücreti) bu fikrin ağdaki karşılığıdır ve Wardrop dengesini optimum yapar.

Önemi: Üç oyuncu için orantılı bir yöntem verdi. n oyuncu için Banach–Knaster son azalan (last diminisher) protokolünü de duyurdu.

Adil bölüşüm iki tür paylaşım arar: orantılı (herkes kendi değerlemesine göre en az 1/n alır) ya da kıskançsız. Algoritmik kuramı daha sonra Brams, Taylor, Procaccia ve başkaları geliştirdi.

Önemi: von Neumann–Morgenstern beklenen fayda aksiyomları, oyuncuları beklenen kazancı maksimize eden karar vericiler olarak modellemeyi haklı çıkarır.

Fayda aksiyomları (tamlık, geçişlilik, süreklilik, bağımsızlık) 1947'deki ikinci baskıya eklendi. Allais, Kahneman ve Tversky'nin davranışsal çalışmaları bu aksiyomları daha sonra sınadı.

Önemi: Minimaks, stratejik optimizasyonu doğrusal programlamadaki dualiteye ve çekişmeli aramaya bağlar.

Her sonlu iki oyunculu sıfır toplamlı oyunda karışık stratejilerle max-min değeri min-max değerine eşittir. 1944 kitabı işbirlikçi oyunları (kararlı kümeler) tanıttı; 1947 baskısı beklenen fayda aksiyomlarını ekledi.

Önemi: Vickrey açık artırması ilk VCG mekanizmasıdır ve dürüst mekanizma tasarımının şablonudur.

Aynı makale, standart açık artırma biçimlerinin gelir eşdeğerliğini önceden sezdi. Vickrey yollar ve toplu taşıma için tıkanıklık fiyatlandırmasını da savundu.

Önemi: Sınırlı rasyonellik, ajanların hesaplama sınırlarını öne çıkarır. Bu konu algoritmik oyun kuramında ve çok ajanlı yapay zekâda sık sık karşımıza çıkar.

“A Behavioral Model of Rational Choice” (1955) makalesi, arama maliyetleri yüzünden tam optimizasyonun gerçekçi olmadığını savundu. Simon yapay zekânın kurucuları arasındadır (Logic Theorist, 1956).

Önemi: Satrançtaki olası oyun sayısı için verdiği kaba tahmin (yaklaşık 10¹²⁰), kaba kuvvetle tam aramanın neden imkânsız olduğunu gösteren standart sayıdır ve Shannon sayısı olarak bilinir.

Makalede her hamleyi aynı derinlikte inceleyen tam genişlikli arama (A tipi) ile yalnızca umut verici hamleleri inceleyen seçici arama (B tipi) ayrımını yaptı. Bilgi kuramını kuran “A Mathematical Theory of Communication” (1948) makalesi de ona aittir.

Önemi: Kurgusal oyun, oyunlar için ilk öğrenme dinamiğidir. Julia Robinson 1951'de bu dinamiğin iki oyunculu sıfır toplamlı oyunlarda yakınsadığını kanıtladı.

Shapley (1964), kurgusal oyunun döngüye girdiği 3×3'lük bir oyun verdi. Böylece basit öğrenmenin genel oyunlarda Nash dengesine ulaşmak zorunda olmadığı görüldü.

Önemi: Mekanizma tasarımı oyun kuramını tersine çevirir: kurallar, kendi çıkarını gözeten davranış istenen sonucu üretecek biçimde seçilir.

Hurwicz, değişim ekonomilerinde verimli ve bireysel rasyonel hiçbir mekanizmanın baskın stratejide teşvik uyumlu olamayacağını gösterdi. Bu sonuç, alanın incelediği ödünleşimlerin çerçevesini çizdi.

Önemi: Hedge ve pişmanlık eşleştirme gibi pişmanlıksız algoritmalar bu sonuçlardan türer ve kaba korelasyonlu dengelere yakınsar.

Blackwell teoremi, bir oyuncunun ortalama vektör kazancını hangi dışbükey kümelere yaklaştırmaya zorlayabileceğini belirler. Hannan tutarlılığı ve kalibrasyon bu teoremin sonuçları olarak elde edilir.

Önemi: Bayesçi oyunlar (Bayesian games), ortak bir ön olasılıktan (common prior) çekilen özel tipleri (değerler, maliyetler) modeller. Açık artırma ve mekanizma kuramı bu modele dayanır.

Harsanyi dönüşümü, her oyuncunun tipini çeken bir şans hamlesi (“Doğa”) ekler. Böylece eksik bilgi, mükemmel olmayan bilgiye dönüşür. Arındırma teoremi (1973) karışık stratejilere yeni bir yorum getirir.

Önemi: ESS ve replikatör dinamiği (Taylor ve Jonker, 1978), oyun kuramını rasyonel oyuncu varsaymayan popülasyonlara taşır.

Bir popülasyonun benimsediği stratejiyi küçük bir mutant grubu istila edemiyorsa bu strateji evrimsel kararlıdır. Her ESS simetrik bir Nash dengesidir. Kitap: Evolution and the Theory of Games (1982).

Önemi: Ertelenmiş kabul, O(n²) teklifle her zaman kararlı bir eşleştirme bulur. Bulunan eşleştirme teklif veren taraf için en iyisidir ve algoritma bu taraf için stratejiye dayanıklıdır (strategy-proof).

Gale 2008'de öldü; kararlı tahsis kuramı 2012'de Nobel Ekonomi Ödülü ile ödüllendirildi. Doğrusal programlamadaki dualiteye ve Hex oyununa da katkı yaptı. Hex'in berabere bitemeyeceğinin bilinen ispatlarından birini Gale verdi ve bu sonucu Brouwer sabit nokta teoremine bağladı.

Önemi: Üç ya da daha fazla seçenek varsa oybirliğini (Pareto) ve ilgisiz alternatiflerden bağımsızlığı (independence of irrelevant alternatives, IIA) sağlayan her kural bir diktatörlüktür.

Arrow teoremi aksiyomatik sosyal seçimi başlattı. Arrow, rekabetçi dengenin varlığını da Debreu ile birlikte kanıtladı (Arrow–Debreu, 1954). Bu ispat, Nash'inkine benzer sabit nokta argümanlarına dayanır.

Önemi: Ayrışma modeli (1969–71), hafif bireysel tercihlerin güçlü bir toplu ayrışma doğurabildiğini gösterdi. Bu model ajan tabanlı simülasyonun ilk örneklerindendir.

Schelling, kişinin kendi seçeneklerini kısıtlamasının (köprüleri yakmanın) stratejik değer taşıyabileceğini gösterdi. Bu fikir caydırma ve pazarlık kuramında sık geçer.

Önemi: Wardrop dengesinde kullanılan her yolun gecikmesi eşit ve en küçüktür. Anarşinin Bedeli bu dengeyi sistem optimumuyla karşılaştırır.

Beckmann, McGuire ve Winsten (1956), Wardrop dengelerinin bir potansiyel fonksiyonunu minimize ettiğini gösterdi. Bu yüzden dengeler dışbükey optimizasyonla hesaplanabilir.

Önemi: Shapley değeri; verimlilik, simetri, toplamsallık ve kukla oyuncu aksiyomlarını birlikte sağlayan tek paylaşım kuralıdır.

Bu değer, bir oyuncunun tüm geliş sıralarındaki marjinal katkısının ortalamasıdır. Bugün maliyet paylaşımında ve makine öğrenmesi tahminlerini açıklamada (SHAP) kullanılır. Bondareva–Shapley teoremi, çekirdeği boş olmayan oyunları belirler.

Önemi: Zermelo'nun satranç sonucu Kuhn'un çerçevesinde genel bir teoreme dönüşür. Minimaks ağacındaki değer, mükemmel bilgili oyunun saf stratejili değeridir.

Atama problemini çözen Macar yöntemini 1955'te yayımladı. Karush–Kuhn–Tucker koşulları da onun adını taşır. Nash'in yakın arkadaşı ve meslektaşıydı.

Önemi: Nash dengesi, işbirlikçi olmayan oyun kuramının temel çözüm kavramıdır. Varlık ispatı bir sabit nokta teoremine dayanır.

1950 ispatı Kakutani'nin, 1951 ispatı Brouwer'in sabit nokta teoremini kullanır. İspat yapıcı değildir; dengeyi hesaplamanın PPAD-tam olduğu çok sonra gösterildi. Nash ayrıca Nash pazarlık çözümünü tanıttı (1950).

Önemi: Bu iyileştirmeler, inandırıcı olmayan tehditlere dayanan Nash dengelerini eler.

Alt oyun mükemmel denge her alt oyunda bir Nash dengesi oluşturur. Sonlu mükemmel bilgili oyunlarda geriye doğru çıkarımla bulunur. Selten zincir mağaza paradoksunu da (1978) ortaya koydu; deneysel iktisadın öncülerindendir.

Önemi: Korelasyonlu dengeler, doğrusal programlamayla hesaplanabilen bir çokyüzlü oluşturur. İç pişmanlığı sıfıra indiren öğrenme bu dengelere yakınsar.

Korelasyonlu dengede bir aracı bir eylem profili çeker ve her oyuncuya kendi eylemini gizlice önerir. Öneriye uymamak hiçbir oyuncuya kazanç sağlamaz. Halk teoremi, sonsuz kez tekrarlanan oyunlarda işbirliğini açıklar.

Önemi: Beklenti kuramı, beklenen faydanın yerine referans noktasına bağlılığı, kayıptan kaçınmayı ve olasılık ağırlıklandırmasını koyar. Davranışsal oyun kuramı bu temele dayanır.

Çerçeveleme etkileri, rasyonel seçim modellerinin varsaydığı değişmezliği bozar. Kahneman'ın Thinking, Fast and Slow (2011) kitabı ikili süreç görüşünü geniş kitlelere tanıttı.

Önemi: Kreps ile ardışık dengeyi (sequential equilibrium) tanımladı (1982). Milgrom ile, ABD Federal İletişim Komisyonunun (FCC) 1994'ten beri kullandığı spektrum açık artırmalarını tasarladı.

Wilson, Milgrom'un doktora danışmanıdır; Roth ve Rosenthal'ın da danışmanlığını yaptı. Nonlinear Pricing (1993) kitabı elektrik piyasalarının tasarımını etkiledi.

Önemi: Braess paradoksu, ek kapasitenin bencil yönlendirmeye zarar verebileceğinin standart örneğidir. Doğrusal gecikmelerde bu örneğin Anarşinin Bedeli 4/3'tür.

Makale (“Über ein Paradoxon aus der Verkehrsplanung”, Unternehmensforschung, 1968) 2005'te İngilizceye çevrildi. Braess'in asıl alanı sayısal analizdir (sonlu elemanlar).

Önemi: Hamleler en iyi sırayla incelendiğinde alfa-beta, b dallanmalı ve d derinlikli düzgün ağaçta b^⌈d/2⌉ + b^⌊d/2⌋ − 1 yaprağa bakar. Aynı sürede yaklaşık iki kat derine inilebilmesi bu sonuçtan gelir.

Alfa-beta fikri 1950'ler ve 1960'larda birkaç araştırmacı tarafından birbirinden bağımsız olarak bulunmuştu. Knuth ve Moore yöntemi kesin biçimde yazıp çözümledi. Knuth daha çok The Art of Computer Programming dizisi ve TeX ile tanınır.

Önemi: VCG (Vickrey 1961, Clarke 1971, Groves 1973), sosyal refahı (social welfare) maksimize eden sonucu seçer. Her ajan, başkalarına yüklediği dışsallık kadar öder. Böylece dürüst bildirim baskın strateji olur.

Green ve Laffont (1977), kısıtsız yarı doğrusal tercihler altında baskın stratejide verimli mekanizmaların yalnızca Groves mekanizmaları olduğunu gösterdi. VCG bütçe açığı verebilir ve danışıklılığa karşı savunmasızdır.

Önemi: Gibbard ve Satterthwaite teoremi birbirinden bağımsız kanıtladı. Teorem, stratejiye dayanıklılığı mekanizma tasarımında temel bir kısıt hâline getirir.

Çıkış yolları şunlardır: kısıtlı tercih alanları (tek tepeli tercihler ve medyan kuralı), para (VCG), rastgeleleştirme ve manipülasyonun hesaplama açısından zor olması.

Önemi: “The Evolution of Cooperation” (W. D. Hamilton ile, Science 1981; kitap 1984), karşılıklılığın işbirliğini nasıl sürdürdüğünü açıkladı.

Başarılı stratejiler iyi niyetli, misilleme yapan, affedici ve anlaşılırdı. Sonuçlar ajan tabanlı modellemeye ve evrimsel dinamiklere ilham verdi.

Önemi: Myerson–Satterthwaite teoremi (1983), iki taraflı ticarette aynı anda verimli, teşvik uyumlu, bireysel rasyonel ve bütçe dengeli bir mekanizma olmadığını gösterir.

Bu iki imkânsızlık sonucu, gerçek piyasaların ve seçimlerin neden bazı istenen özelliklerden vazgeçmek zorunda olduğunu açıklar.

Önemi: Rosenthal potansiyeli, en iyi tepki dinamiğinin sonlanacağını garanti eder. Yönlendirme oyunlarının ve İstikrarın Bedeli sınırlarının temel aracıdır.

Monderer ve Shapley (1996), her tam potansiyel oyunun bir tıkanıklık oyununa izomorf olduğunu gösterdi. Rosenthal kırkayak oyununu da tanıttı (1981).

Önemi: Genelleştirilmiş ikinci fiyat (generalized second-price, GSP) açık artırmasının simetrik Nash dengeleri, reklam fiyatlarını tıklanma oranlarına ve teklifçi değerlerine bağlar.

Varian 2002'de Google'a katıldı; şirketin reklam açık artırmasının ve rezerv fiyat politikalarının tasarımına katkı verdi. Intermediate Microeconomics ders kitabı yaygın olarak okutulur.

Önemi: FCC'nin eşzamanlı çok turlu açık artırmasının (1994) ve 2016–17 teşvik açık artırmasının tasarımcıları arasındadır.

Bağlantı ilkesi, değerler ilişkili olduğunda açık ve artan fiyatlı açık artırmaların neden daha çok gelir getirdiğini açıklar. Kitap: Putting Auction Theory to Work (2004).

Önemi: Daskalakis ve Goldberg ile Nash dengesi hesaplamanın PPAD-tam olduğunu kanıtladı (2006).

PPAD, çözümünün varlığı yönlü çizgeler üzerindeki bir eşlik argümanıyla (yolun sonu, end-of-the-line) garanti edilen toplam arama problemlerini kapsar. 2001'deki “Algorithms, Games, and the Internet” başlıklı STOC konuşması, algoritmik oyun kuramının doğuşuna katkı verdi.

Önemi: İç pişmanlığı sıfıra indiren öğrenme korelasyonlu dengelere, dışsal pişmanlığı sıfıra indiren öğrenme kaba korelasyonlu dengelere götürür.

Hart ve Mas-Colell, “bağlantısız” (uncoupled) dinamiklerin her oyunda Nash dengesine yakınsamayı garanti edemeyeceğini de gösterdi (2003).

Önemi: Maskin monotonluğu Nash uygulaması için gereklidir. Üç ya da daha fazla ajan varsa ve hiçbir ajanın veto gücü yoksa yeterlidir de.

Uygulama kuramı (implementation theory), tasarlanan oyunun yalnızca bazı dengelerinin değil, tüm dengelerinin istenen sonucu verip vermediğini sorar.

Önemi: Piyasa tasarımı (market design), piyasaları mühendislik ürünü sistemler olarak ele alır. İyi bir piyasa kalabalık olmalı, tıkanmamalı ve dürüst katılımı güvenli kılmalıdır.

Roth, iki taraf için birden stratejiye dayanıklı olan kararlı bir eşleştirme mekanizması olmadığını gösterdi (1982). Kitap: Who Gets What — and Why (2015).

Önemi: Sanal değerler (virtual values), gelir maksimizasyonunu refah maksimizasyonuna indirger. Değerler bağımsız, aynı dağılımlı ve düzenliyse optimal açık artırma, rezerv fiyatlı ikinci fiyat açık artırmasıdır.

Myerson lemması: tek parametreli bir tahsis kuralı ancak ve ancak monotonsa uygulanabilir; bu durumda ödeme kuralı tek türlü belirlenir. Satterthwaite ile iki taraflı ticaret imkânsızlık teoremini kanıtladı (1983).

Önemi: Platformlar iki tarafa da fiyat koyar ve bir tarafı çekmek için diğer tarafı sübvanse edebilir. Uygulama mağazalarının, kart ağlarının ve pazar yerlerinin fiyatlandırması bu çerçeveyle açıklanır.

Tirole, Nobel'i piyasa gücü ve düzenleme üzerine çözümlemeleriyle aldı. Drew Fudenberg ile Game Theory (1991) ders kitabını yazdı.

Önemi: Stratejik akıl yürütmeyi, müzakereyi ve öğrenmeyi otonom ajanların hesaplamalı modellerine taşıdı.

AI Index raporunun ve AI21 Labs şirketinin kurucuları arasındadır.

Önemi: Doğrusal gecikmelerde Wardrop dengesinin maliyeti, ağ ne olursa olsun optimumun en çok 4/3 katıdır.

Algorithmic Game Theory (2007) kitabının editörlerindendir. Kleinberg ile Algorithm Design (2005) kitabını yazdı. Son çalışmaları, açık artırmalarda ve yönlendirmede pişmanlıksız öğrenen oyuncuları inceler.

Önemi: Çevrim içi iki parçalı eşleştirme (Karp–Vazirani–Vazirani, 1990) ve onun AdWords genellemesi, reklam platformlarının sorguları reklamverenlere nasıl atadığını modeller.

Nisan, Roughgarden ve Tardos ile Algorithmic Game Theory (2007) kitabının editörlüğünü yaptı. Fisher piyasası dengeleri için kombinatoryal algoritmalar da tasarladı.

Önemi: Zermelo teoremine göre damanın sonucu en iyi oyunda belirlidir. Dama, bu sonucun bilgisayarla gerçekten bulunabildiği en büyük oyunlardandır.

Çözüm zayıf bir çözümdür: başlangıç konumunun değerini ve bu değeri koruyan oyunu verir, her konum için en iyi hamleyi vermez. Arama, alfa-beta türevleri ile çok büyük son oyun veritabanlarını birleştirdi.

Önemi: Bireysel adalet, benzer bireylere benzer davranılmasını ister. Diferansiyel mahremiyetten yaklaşık dürüst mekanizmalar da elde edilir (McSherry–Talwar, 2007).

Çalışmaları mahremiyeti ve adaleti, doğrulukla ödünleşebilen matematiksel güvenceler olarak ele alır. Web için sıralama birleştirme yöntemleri üzerine çalışması (Kumar, Naor ve Sivakumar ile, 2001) oylama kuramıyla bağlantılıdır.

Önemi: Deep Blue, derinlik sınırlı alfa-beta aramasının özel donanımla bir dünya şampiyonunu yenebileceğini gösterdi. 1997 sürümü saniyede yaklaşık 200 milyon konum değerlendiriyordu.

1996'daki ilk maçı Kasparov 4–2 kazanmıştı. Hsu (d. 1959) sistemin baş tasarımcısıdır ve süreci Behind Deep Blue (2002) kitabında anlattı. Üçlü sistemi “Deep Blue” (Artificial Intelligence, 2002) makalesinde tanıttı.

Önemi: Mekanizmalar hem teşvik uyumlu hem de hesaplama açısından verimli olmalıdır. Yaklaşık bir algoritmayla çalıştırılan VCG genelde dürüst değildir.

Algorithmic Game Theory (2007) kitabının editörlerindendir. Kombinatoryal açık artırmalar üzerine çalışmaları, verimli tahsis için ne kadar iletişim gerektiğini ölçer.

Önemi: Her oyuncunun kazancı yalnızca komşularına bağlıysa grafiksel oyunlar büyük oyunları kısa biçimde temsil eder.

Aaron Roth ile, algoritmalara adalet ve mahremiyet yerleştirmeyi anlatan The Ethical Algorithm (2019) kitabını yazdı.

Önemi: Anarşinin Bedeli, bencil davranışın sistem başarımını en kötü durumda ne kadar düşürdüğüne bir güvence verir.

İlk model, paralel bağlantılar üzerinde bencil işlerin yük dengelemesiydi. Koutsoupias çevrim içi algoritmalar üzerine de çalıştı (iş fonksiyonu algoritması için k-sunucu sanısı).

Önemi: İndirgeme, aritmetik devreleri oyunlar olarak kodlar. Böylece her denge bir yolun sonu örneğini çözer.

Goldberg yaklaşık dengelerin ve Lemke–Howson gibi yol izleyen yöntemlerin karmaşıklığını da inceler.

Önemi: Oyun yaklaşık 4,5 · 10¹² yasal konum içerir. Çözüm kaba kuvvetle değil, oyuna özgü kurallar ve güçlü aramayla elde edildi.

Allis yüksek lisans tezinde dokuz kurala dayanan bilgiye dayalı bir yaklaşım kullandı. 1994'teki doktora tezinde kanıt sayısı aramasını (proof-number search) tanıttı.

Önemi: Bu imkânsızlık sonucu, adalet ölçütlerinin birbiriyle çatıştığını gösterir. Algoritmik adalet bu yüzden açık tercihler yapmayı gerektirir.

HITS algoritması web sayfalarını merkezler (hubs) ve otoriteler (authorities) olarak sıralar. Easley ile yazdığı Networks, Crowds, and Markets (2010) kitabı sponsorlu aramayı, eşleştirme piyasalarını ve Braess paradoksunu da kapsar.

Önemi: Pürüzsüzlük argümanları, Anarşinin Bedeli sınırlarını karışık, korelasyonlu ve pişmanlıksız sonuçlara genişletir.

Twenty Lectures on Algorithmic Game Theory (2016) kitabı yaygın bir ders kaynağıdır. Son çalışmaları blokzincir işlem ücreti mekanizmalarını inceler.

Önemi: Basit açık artırmaların (örneğin anonim rezerv fiyatlı ikinci fiyat açık artırması) ne zaman yaklaşık optimal olduğunu gösterir. Böylece Myerson kuramıyla uygulama arasında köprü kurar.

Mechanism Design and Approximation kitabı, Bayesçi mekanizma tasarımını algoritmik bir bakışla geliştirir.

Önemi: Go'da dallanma etkeni yaklaşık 250'dir ve iyi bir değerlendirme fonksiyonu elle yazılamaz. AlphaGo değerlendirmeyi ve hamle seçimini öğrenilmiş ağlara bıraktı.

Ardından gelen AlphaZero, insan oyunu kullanmadan, yalnızca kendi kendine oynayarak Go, satranç ve şogi öğrendi. Arama fikri yine minimaksla aynıdır: rakibin en iyi cevabını varsayarak ileriye bakmak.

Önemi: Bir mala kadar kıskançsızlık (envy-free up to one good, EF1), en büyük Nash sosyal refahı ve leksimin tahsisleri, adalet güvencelerini uygulanabilir kılar.

Kurayla temsilî yurttaş meclisleri seçmek için de algoritmalar tasarladı.

Önemi: PPAD kolay değilse genel oyunlarda Nash dengesini bulan verimli bir algoritma yoktur. Bu sonuç, dengenin bir öngörü olarak kullanılmasını sorgulatır.

DGP ispatı üç ve daha fazla oyunculu oyunları kapsar. Chen ve Deng (2006) zorluğu iki oyunculu oyunlara genişletti. Son çalışmaları min-max optimizasyonunda öğrenme dinamiklerini ve çok ajanlı öğrenmeyi inceler.

Önemi: GSP dürüst değildir. Yine de en düşük gelirli yerel kıskançsız dengesi, VCG ile aynı yerleşimleri ve ödemeleri verir.

Varian'dan bağımsız olarak, dürüst teklif baskın strateji olmadığı hâlde GSP fiyatlarının uygulamada neden kararlı kaldığını açıkladılar.

Önemi: MCTS, iyi bir değerlendirme fonksiyonu yazılamayan oyunlarda konumları rastgele oyunların sonuçlarıyla değerlendirir. Güçlü Go programlarının ve AlphaGo'nun arama iskeleti bu yöntemdir.

Coulom'un Crazy Stone programı 2006 Bilgisayar Olimpiyatı'nda 9×9 Go turnuvasını kazandı. UCT, her düğümde hamle seçimini çok kollu haydut problemi gibi ele alır.