Algorithmic Game Theory

Undergraduate, Giresun University, Computer Engineering, 2026

algorithmic game theory Algorithmic game theory studies strategic interaction through the lens of computation. It combines game-theoretic models with algorithms and complexity analysis to examine equilibria, auctions, market mechanisms, routing, online platforms, fairness, and the behavior of self-interested agents.


Ders Kitabı

📕 Algoritmik Oyun Kuramı (PDF, 15 MB)


Başlangıç Kaynakları


Kısım I: Araçlar ve Temeller

Bölüm 0: Hazırlık

Derste gerçekten kullanılan matematik, oyun örnekleri üzerinden yeniden ele alınır: küme ve fonksiyon gösterimi, toplam sembolü, max ve argmax, olasılık ve beklenen değer, karışık strateji fikri, kazanç matrisinin okunması, en iyi tepki, kayıtsızlık denkleminin çözümü ve oyun ağacında geriye doğru çıkarım.


Bölüm 1: Karar Kuramı

Stratejik etkileşimden önce tek bir karar verici incelenir. Beklenen fayda ve von Neumann–Morgenstern aksiyomları, fayda ölçeğinin hangi dönüşümlere kadar tek olduğu, Allais ve Ellsberg paradoksları, risk tutumları ve kesinlik eşdeğeri, belirsizlik altında karar ölçütleri, Bayesçi karar, karar ağaçlarında geriye doğru çıkarım ve bilginin değeri bu bölümün konularıdır.


Bölüm 2: Oyunlar ve Temsiller

Bir oyunun ne olduğu ve nasıl yazıldığı: oyuncular, stratejiler, kazançlar ve bilgi; normal form ve genişletilmiş form; oyunların sınıflandırılması; Mahkûmun İkilemi ve Pareto optimallik; klasik 2×2 oyunlar; 2/3 ortalaması oyunu ve seviye-k düşünme; kombinatoryal oyunlar ve minimaks; minimaksı hızlandıran alfa-beta budaması, derinlik sınırlı arama ve değerlendirme fonksiyonları; sıralı oyunlar, geriye doğru çıkarım, alt oyun mükemmel denge ve tetik stratejisi.


Bölüm 3: Nash Dengesi

Nash dengesi, hiçbir oyuncunun tek başına sapmakla kazançlı çıkamadığı strateji profilidir. Bölümde en iyi tepki, Cournot ve Bertrand rekabeti, baskılanan stratejilerin art arda elenmesi, karışık strateji dengeleri ve kayıtsızlık ilkesi, Nash’in varlık teoremi, denge seçimi, korelasyonlu denge, sıfır toplamlı oyunlarda minimaks, güvenlik oyunları ve denge hesaplamanın PPAD karmaşıklığı ele alınır.


Kısım II: Mekanizmalar

Bölüm 4: Mekanizma Tasarımı

Mekanizma tasarımı soruyu tersine çevirir: Hedef belli olduğunda, kendi çıkarını gözeten katılımcıları bu hedefe doğru davranmaya hangi kurallar yöneltir? Sosyal seçim fonksiyonları, açıklama ilkesi, teşvik uyumluluğu ve bireysel rasyonellik, Myerson lemması, VCG mekanizması, Gale–Shapley kararlı eşleştirme, medyan mekanizması, En İyi Takas Döngüleri (TTC) ve Bayesçi oyunlar.


Bölüm 5: Açık Artırmalar

Açık artırmalar, malların dağıtılmasında ve fiyatların belirlenmesinde en yaygın kullanılan mekanizmalardır. Dört temel biçim (İngiliz, Hollanda, birinci fiyat ve ikinci fiyat kapalı zarf), denge teklif stratejileri, gelir eşdeğerliği ve bilginin rolü, alıcıların da satıcıların da teklif verdiği çift taraflı açık artırma piyasaları.


Bölüm 6: Çevrim İçi Platformlar

Dijital platformlar kendi çıkarını gözeten kullanıcıları bir araya getirir ve aralarındaki oyunun kurallarını koyar. İki taraflı pazarlar, ağ etkisi ve kritik kitle, iki taraflı fiyatlandırma, sponsorlu arama açık artırmaları (GSP ve VCG), bütçe kısıtlı çevrim içi tahsis, itibar sistemleri ve platformlar arası rekabet.


Bölüm 7: Sosyal Seçim ve Oylama

Sosyal seçim, bireysel tercihlerin ortak bir karara nasıl dönüştürüldüğünü inceler. Aynı tercih profili üzerinde sayılan çoğunluk, çoğulluk, Borda, onay, anında ikinci tur ve Condorcet kuralları, Condorcet döngüsü, stratejik oy ile Arrow, Gibbard–Satterthwaite ve May teoremleri.


Kısım III: Ağlar ve Verimlilik

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

Her sürücü ya da paket kendi yolunu seçtiğinde ortaya çıkan sonuç, merkezî bir planlayıcının seçeceğinden farklı olabilir. Yönlendirmenin temelleri, bencil yönlendirme, Wardrop dengesi ile sistem optimumunun karşılaştırılması, Braess paradoksu, tıkanıklık oyunları ve Rosenthal potansiyeli, ağ oluşturma oyunları.


Bölüm 9: Anarşinin Bedeli

Anarşinin Bedeli, en kötü dengeyi optimumla karşılaştırarak bencil davranış yüzünden ne kadar verim kaybedildiğini ölçer; İstikrarın Bedeli aynı karşılaştırmayı en iyi denge için yapar. İki yollu ağda ve Pigou ağında bu oranlar, doğrusal gecikmelerde 4/3 sınırı, pürüzsüzlük, Braess ağı, yük dengeleme, İstikrarın Bedeli için logaritmik sınır, tıkanıklık ücreti ve öteki müdahaleler.


Kısım IV: İşbirliği ve Toplum

Bölüm 10: Çoklu Ajan Sistemleri

Çoklu ajan sistemleri, ortak bir ortamda işbirliği yapan ya da birbiriyle rekabet eden özerk ajanlardan oluşur. Ajanların özellikleri, işbirliği ve rekabet, sözleşme ağıyla görev dağıtımı, koalisyon oyunları, Shapley değeri, çekirdek ve kamu mallarında beleşçilik.


Bölüm 11: Algoritmik Adalet ve Etik

Algoritmik kararlar ve dağıtımlar bireyleri ve grupları farklı biçimlerde etkiler. Karışıklık matrisinden hesaplanan adalet ölçütleri (demografik eşitlik, eşitlenmiş olasılıklar, tahmin eşitliği, kalibrasyon) ve bu ölçütlerin neden aynı anda sağlanamadığı; kes-ve-seç, orantılılık ve kıskançsızlık ile adil bölüşüm; etik ilkeler ve algoritmik denetim.


Bölüm 12: Davranışsal ve Kolektif Karar

Gerçek insanlar rasyonel modelden sapar; gruplar da tek tek bireylerin karşılaşmadığı ikilemlerle yüz yüze gelir. Sınırlı rasyonellik, beklenti kuramı, kayıptan kaçınma ve çerçeveleme, ortak mallar trajedisi ve en iyi tepki dinamiği, vergi, kota ve yaptırım gibi kurumsal çözümler, kamu malı deneyleri ve sosyal refah ölçütleri.


Kısım V: Dinamikler ve Gelecek

Bölüm 13: Öğrenme ve Adaptasyon

Deneyimden öğrenen ajanlar dengeye nasıl ulaşır, ya da neden ulaşamaz? En iyi tepki dinamiği, kurgusal oyun, pişmanlık ve çarpımsal ağırlıklar, çok kollu haydut problemleri (ε-açgözlü ve UCB), replikatör dinamiği ve tekrarlı Mahkûmun İkilemi.


Bölüm 14: Gelecek Yönelimler

Alanın sınırındaki açık problemler: yapay zekâ ajanları ve algoritmik danışıklılık, veriden öğrenilen mekanizmalar ve örneklem karmaşıklıkları, diferansiyel mahremiyet, blokzincirlerde işlem ücreti mekanizmaları ve MEV. Bölüm, dersin genel haritasıyla kapanır.


Part I: Tools and Foundations

Chapter 0: Preliminaries

This chapter reviews the mathematics the course actually uses, always through small game examples. It covers set and function notation, the summation sign, max and argmax, probability and expected value, and the idea of a mixed strategy. Students then practice reading a payoff matrix, finding best responses, solving indifference equations and applying backward induction on a game tree.


Chapter 1: Decision Theory

Before turning to strategic interaction, we study a single decision maker. Topics include expected utility and the von Neumann–Morgenstern axioms, the transformations under which a utility scale is unique, and the Allais and Ellsberg paradoxes. The chapter continues with risk attitudes and certainty equivalents, decision criteria under uncertainty, Bayesian decision making, backward induction in decision trees and the value of information.


Chapter 2: Games and Representations

This chapter defines what a game is and how to write one down: players, strategies, payoffs and information, in normal and extensive form, along with a classification of games. It covers the Prisoner’s Dilemma and Pareto optimality, the classic 2×2 games, the guess-2/3-of-the-average game and level-k reasoning, and combinatorial games solved by minimax. Alpha-beta pruning, depth-limited search and evaluation functions show how minimax is made fast, and sequential games lead to backward induction, subgame-perfect equilibrium and trigger strategies. A supplementary deck treats minimax and alpha-beta pruning in more depth.


Chapter 3: Nash Equilibrium

A Nash equilibrium is a strategy profile from which no player can gain by deviating alone. The chapter develops best responses, Cournot and Bertrand competition, iterated elimination of dominated strategies, and mixed-strategy equilibria with the indifference principle. It then covers Nash’s existence theorem, equilibrium selection, correlated equilibrium, minimax in zero-sum games, security games and the PPAD complexity of computing an equilibrium.


Part II: Mechanisms

Chapter 4: Mechanism Design

Mechanism design turns the question around: once the goal is fixed, which rules lead self-interested participants to act toward it? We study social choice functions, the revelation principle, incentive compatibility and individual rationality, Myerson’s lemma and the VCG mechanism. Applications include Gale–Shapley stable matching, the median mechanism and Top Trading Cycles (TTC), and the chapter closes with Bayesian games.


Chapter 5: Auctions

Auctions are the most widely used mechanisms for allocating goods and setting prices. We compare the four basic formats (English, Dutch, first-price and second-price sealed-bid), derive equilibrium bidding strategies, and examine revenue equivalence and the role of information. The chapter ends with double-auction markets, in which both buyers and sellers submit bids.


Chapter 6: Online Platforms

Digital platforms bring self-interested users together and set the rules of the game they play. The chapter covers two-sided markets, network effects and critical mass, and two-sided pricing. It then analyzes sponsored-search auctions (GSP and VCG), budget-constrained online allocation, reputation systems and competition between platforms.


Chapter 7: Social Choice and Voting

Social choice studies how individual preferences are turned into a collective decision. Working from a single preference profile, we count the majority, plurality, Borda, approval, instant-runoff and Condorcet rules and see how their winners differ. The chapter then examines Condorcet cycles and strategic voting, and closes with the theorems of Arrow, Gibbard–Satterthwaite and May.


Part III: Networks and Efficiency

Chapter 8: Network Design and Routing

When every driver or packet picks its own route, the outcome can differ from what a central planner would choose. We start with the basics of routing and selfish routing, then compare Wardrop equilibrium with the system optimum. Braess’s paradox, congestion games with Rosenthal’s potential, and network formation games complete the chapter.


Chapter 9: The Price of Anarchy

The price of anarchy measures how much efficiency selfish behavior costs by comparing the worst equilibrium with the optimum; the price of stability makes the same comparison for the best equilibrium. We compute both ratios on a two-road network and on Pigou’s network, prove the 4/3 bound for linear latencies and introduce smoothness arguments. The chapter also covers the Braess network, load balancing, the logarithmic bound on the price of stability, congestion pricing and other interventions.


Part IV: Cooperation and Society

Chapter 10: Multi-Agent Systems

Multi-agent systems consist of autonomous agents that cooperate or compete in a shared environment. The chapter describes the properties of agents, cooperation and competition, and task allocation with the contract net protocol. It then introduces coalitional games, the Shapley value and the core, and closes with free riding in public goods.


Chapter 11: Algorithmic Fairness and Ethics

Algorithmic decisions and allocations affect individuals and groups in different ways. We define fairness criteria computed from the confusion matrix (demographic parity, equalized odds, predictive parity and calibration) and show why they cannot all hold at once. The chapter then treats fair division through cut-and-choose, proportionality and envy-freeness, and ends with ethical principles and algorithmic auditing.


Chapter 12: Behavioral and Collective Decisions

Real people depart from the rational model, and groups face dilemmas that no single individual meets on their own. Topics include bounded rationality, prospect theory, loss aversion and framing, and the tragedy of the commons with best-response dynamics. We then look at institutional remedies such as taxes, quotas and sanctions, public goods experiments and measures of social welfare.


Part V: Dynamics and the Future

Chapter 13: Learning and Adaptation

How do agents that learn from experience reach an equilibrium, and why do they sometimes fail to? The chapter studies best-response dynamics, fictitious play, regret and multiplicative weights. It continues with multi-armed bandit problems (epsilon-greedy and UCB), replicator dynamics and the repeated Prisoner’s Dilemma.


Chapter 14: Future Directions

The final chapter surveys open problems at the frontier of the field: AI agents and algorithmic collusion, mechanisms learned from data and their sample complexity, and differential privacy. It also covers transaction-fee mechanisms on blockchains and MEV. The course closes with an overall map that ties its topics together.