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

4.1Temel kavramlar

Bu bölümün sorusu şudur: bir toplulukta herkes kendi çıkarını gözetiyorsa ve herkesin bildiği bir şeyi başkaları bilmiyorsa, topluluk için iyi bir kararı hangi kurallarla verebiliriz? Önce küçük bir pazarlık oyunuyla kuralların davranışı nasıl biçimlendirdiği görülür. Sonra mekanizma tasarımının ne olduğu, oyun kuramıyla ilişkisi ve teşvik kavramı açıklanır.

4.1.1Bir oyunla başlangıç: Ültimatom Oyunu

İki oyuncu 10 jetonu bölüşecektir. Birinci oyuncuya teklif eden, ikinci oyuncuya yanıtlayan denir. Teklif eden, yanıtlayana bir pay önerir: örneğin “sana 3 jeton, bana 7 jeton”. Yanıtlayan bu teklifi ya kabul eder ya da reddeder. Kabul ederse bölüşüm uygulanır. Reddederse ikisi de 0 alır. Pazarlık yoktur; teklif tek seferliktir. Oyunun adı da buradan gelir: teklif bir “ültimatom”dur, al ya da bırak.

Oyunun yapısı Şekil 4.1'de görülür. Önce teklif eden (T) bir x sayısı seçer; bu, yanıtlayana önerilen jeton sayısıdır. Sonra yanıtlayan (Y) bu sayıyı görerek karar verir. Kabul edilirse kazançlar (10 − x, x) olur; burada ilk sayı teklif edenin, ikinci sayı yanıtlayanın kazancıdır. Ret durumunda kazançlar (0, 0)'dır.

Oyunu oynayan biri iki soruyla karşılaşır. Yanıtlayan olsaydınız 1 jetonluk teklifi kabul eder miydiniz? Teklif eden olsaydınız kaç jeton önerirdiniz? İki sorunun cevabı da oyuncunun neyi önemsediğine bağlıdır. Yalnız jeton sayısını önemseyen bir yanıtlayan için 1 jeton, 0 jetondan iyidir; bu yüzden reddetmek mantıksız görünür. Oysa birçok insan 1 jetonluk teklifi hakaret sayar ve reddeder. Bu gerilim bölüm boyunca karşımıza çıkacak temel bir soruyu öne çıkarır: kurallar oyuncuların davranışını nasıl etkiler ve bir kural koyucu bu etkiyi hesaba katarak kuralları nasıl seçmelidir?

Ültimatom oyunu küçük bir mekanizmadır: teklif eden, yanıtlayana “şu bölüşüm ya da hiçbir şey” kuralını sunar. Oyunun kuramsal çözümü 4.2.5'te verilir.

4.1.2Mekanizma tasarımı nedir?

Oyun kuramının alışılmış yaklaşımında oyun verilir: oyuncular, stratejileri ve kazançları bellidir. Soru, bu oyunda ne olacağıdır. Mekanizma tasarımı (mechanism design) bu yaklaşımı tersine çevirir. Oyun verilmez; oyunu tasarımcı kurar. Tasarımcının elinde istenen bir sonuç vardır ve bu sonucu doğuracak kuralları arar. Kurallar iki şeyi belirler: kim ne alır (tahsis) ve kim ne öder (ödeme).

Bu iş, ilk bakışta göründüğünden zordur. Tasarımcı oyuncuların özel bilgisini bilmez. Bir nesneyi en çok değer veren kişiye vermek isteyen bir satıcı, kimin ne kadar değer verdiğini bilmez. Bir belediye, sakinlerin bir parka ne kadar değer verdiğini bilmez. Bu bilgiler yalnızca oyuncuların kendisinde vardır. Tasarımcı bu bilgiyi oyunculara sormak zorundadır; oyuncular ise kendi çıkarları gerektiriyorsa yanlış söyleyebilir.

Mekanizma tasarımının amacı bu yüzden şöyle özetlenir: oyuncular bencil ve stratejik davranırken, yani kendi çıkarlarını gözetirken bile istenen sonuca ulaşmak. Tasarımcı oyunculara “doğruyu söyleyin” diye emir veremez. Yalnızca kuralları seçebilir. Kuralları öyle seçmelidir ki doğruyu söylemek ya da istenen davranışı göstermek oyuncunun kendi çıkarına olsun.

Şekil 4.2 bu durumu gösterir. Üç kişi bir nesneye sırasıyla 70, 55 ve 85 değer verir. Bu sayılar oyuncuların kafasındadır; tasarımcı bunları göremez (“tasarımcı görür: ?, ?, ?”). Mekanizma, oyuncuların bildirdiği b sayılarından sonucu ve ödemeleri hesaplar. Bildirimler gerçek değerlere eşit olmak zorunda değildir. İyi bir mekanizma, bildirimin gerçek değere eşit olmasını oyuncunun kendi çıkarına uygun hâle getirir.

Alanın önemi bilimsel ödüllerle de tescil edilmiştir. 2007 Nobel Ekonomi Ödülü, “mekanizma tasarımı kuramının temellerini attıkları için” Leonid Hurwicz, Eric Maskin ve Roger Myerson'a verildi. 2012'de Alvin Roth ve Lloyd Shapley kararlı eşleştirme ve piyasa tasarımı çalışmalarıyla ödüllendirildi.

4.1.3Analiz ve sentez

Oyun kuramı ile mekanizma tasarımı arasındaki ilişki, bir yönün tersine çevrilmesiyle anlatılabilir. Oyun kuramı bir analiz aracıdır: kurallar verilir, oyuncuların davranışı (denge stratejileri) bulunur ve bu davranıştan çıkan sonuç tahmin edilir. Mekanizma tasarımı ise bir sentez aracıdır: istenen sonuç (hedef) verilir, oyuncuların bu hedefe götürecek biçimde davranacağı kurallar aranır.

Şekil 4.3 iki yönü yan yana koyar. Üst satır şu soruyu sorar: “Bu kurallar altında oyuncular ne yapar ve kim kazanır?” Alt satır şu soruyu sorar: “Bu sonucu dengede elde etmek için hangi mekanizma gerekir?” Kısaca, oyun kuramında akış kurallar → sonuç; mekanizma tasarımında sonuç → kurallar yönündedir.

Sentez yönünde çalışmanın önemli bir sonucu vardır. Tasarımcı oyuncuları zorlayamaz. Hangi stratejiyi oynayacaklarına oyuncular kendileri karar verir. Tasarımcının tek aracı kurallardır. Bu yüzden mekanizma tasarımında her öneri bir denge sorusuyla sınanır: önerilen kurallar altında oyuncular gerçekten istenen biçimde davranır mı? Davranmıyorlarsa kurallar ne kadar iyi niyetli olursa olsun hedefe ulaşılmaz.

4.1.4Teşvikler

Mekanizma tasarımının dayandığı gözlem basittir: insanlar teşviklere (incentives) göre davranır. Kurallar belli bir davranışı kârlı yaparsa oyuncular o davranışa yönelir. Bir otopark ücreti yükselirse insanlar daha az araba kullanır. Bir sınavda yanlış cevaplar puan götürürse öğrenciler emin olmadıkları soruları boş bırakır. Kural koyucu her durumda “bu kural hangi davranışı ödüllendiriyor?” diye sormalıdır.

İyi bir mekanizma dürüst davranışı ödüllendirir ve stratejik yalanı caydırır. Doğruyu söylemenin oyuncunun kendi çıkarına olduğu mekanizmalara teşvik uyumlu (incentive compatible) mekanizma denir. Kavramın biçimsel tanımı 4.2.4'te verilir. Burada iki tanıdık örnekle teşvik uyumsuzluğunun neye yol açtığı görülür.

Beleşçi sorunu. Bir mahallede park yapılacak ve maliyet sakinlerin parka verdiği değere göre paylaştırılacak olsun. Sakin, parka ne kadar değer verdiğini kendisi söyler. Değerini düşük gösteren sakin daha az öder ama park yine de yapılırsa ondan aynı ölçüde yararlanır. Bu durumda herkes değerini düşük göstermeye eğilimlidir. Başkalarının ödemesinden yararlanmak isteyen kişiye beleşçi (free-rider) denir. Herkes beleşçi gibi davranırsa toplam bildirim maliyeti karşılamayabilir ve herkesin istediği park hiç yapılmaz.

Stratejik oy. Bir seçimde seçmen en çok desteklediği adayın kazanma şansı yoksa oyunu kazanma şansı olan ikinci tercihine verebilir. Bu, seçmenin gerçek tercihini gizlemesidir. Kural (en çok oy alan kazanır) bu davranışı ödüllendirir. Sonuçta seçim sonucu, seçmenlerin gerçek tercihlerini yansıtmayabilir.

İki örnekte de aynı zincir işler: teşvik uyumsuzluğu oyuncuları yanlış bilgi vermeye iter; yanlış bilgi de verimsiz ya da adil olmayan sonuçlara yol açar. Mekanizma tasarımının görevi bu zinciri baştan kırmaktır: oyuncunun doğru bilgiyi vermesini kendi çıkarına uygun kılmak.

4.1.5Gerçek hayattan uygulamalar

Mekanizma tasarımının sorunları günlük hayatın birçok alanında karşımıza çıkar. Aşağıdaki örneklerin hepsinde bir kurum, bireylerin özel bilgisine dayanarak bir karar verir.

• Vergi sistemleri. Bir kişinin geliri onun özel bilgisidir. Devlet geliri doğrudan göremez; beyana ve denetime dayanır. Vergi oranları ve denetim kuralları dürüst beyanı teşvik etmelidir.
• Kamu malı finansmanı. Park, yol ya da kütüphane gibi herkesin yararlandığı mallarda iki soru vardır: proje yapılmalı mı ve kim ne kadar ödemeli? İki soru da sakinlerin gizli değerlerine bağlıdır. Bu sorunun mekanizmayla çözümü 4.3'te VCG ile verilir.
• İhale ve açık artırmalar. Kamu alımları, frekans lisansları ve sanat eserleri açık artırmayla satılır. Satıcı, alıcıların ödemeye razı olduğu en yüksek fiyatı bilmez; kurallar bu bilgiyi açığa çıkarmaya çalışır.
• Çevrimiçi reklam. Bir arama motorunda her sorguda, milisaniyeler içinde, reklam yerleri için açık artırma yapılır. Reklamverenlerin bir tıklamaya verdiği değer gizlidir.
• Eşleştirme piyasaları. Okul yerleştirme, tıp ihtisası ve yurt odası değişimi gibi durumlarda para kullanılmaz; ama kurallar yine de önemlidir. Öğrencilerin tercih listeleri özel bilgidir ve kurallar dürüst liste yazmayı ödüllendirmelidir. Bu konular 4.4'te incelenir.
• Grup projesi notlama. Bir grup projesinde öğrenciler katkılarını kendileri bildirirse, notlama kuralı abartmayı caydırmalıdır.

Bu örneklerin ortak yapısı, notun geri kalanındaki biçimsel modelin temelini oluşturur: oyuncular, oyuncuların özel bilgisi (tip), olası sonuçlar ve tasarımcının hedefi. Bu dört öğe 4.2.1'de tanımlanır.

4.2Doğrudan mekanizmalar

Bu kısımda mekanizma tasarımının biçimsel dili kurulur. Önce oyuncuların özel bilgisi (tip) ve tasarımcının hedefi (sosyal seçim fonksiyonu) tanımlanır. Sonra oyuncuların yalnızca tiplerini bildirdiği doğrudan mekanizmalar ve bu mekanizmalara odaklanmayı haklı çıkaran açıklama ilkesi anlatılır. Ardından bir mekanizmanın iyi olup olmadığını sınamak için kullanılan ölçütler gelir: teşvik uyumluluğu, bireysel rasyonellik, verimlilik ve bütçe dengesi. Kısım, tek parametreli ortamlarda teşvik uyumlu mekanizmaları tam olarak betimleyen Myerson lemmasıyla biter.

4.2.1Tip ve sosyal seçim fonksiyonu

Bir mekanizmada n oyuncu vardır ve oyuncular 1, 2, …, n diye numaralanır. Her oyuncunun yalnızca kendisinin bildiği bir özel bilgisi vardır: bir nesneye verdiği değer, seçenekler arasındaki tercih sırası ya da bir işi yapmanın maliyeti. Bu özel bilgiye oyuncunun tipi (type) denir.

Tanımdaki semboller ilk okumada yabancı gelebilir. Θ Yunan alfabesinin “teta” harfinin büyüğüdür ve bir kümeyi gösterir; küçük θ o kümeden seçilmiş bir elemandır. Θ₁ × … × Θ_n ifadesindeki × işareti kartezyen çarpımdır: her oyuncudan bir tip seçilerek oluşturulabilecek bütün listelerin kümesi. Örneğin iki oyuncunun her biri “düşük” ya da “yüksek” tipte olabiliyorsa dört tip profili vardır: (düşük, düşük), (düşük, yüksek), (yüksek, düşük), (yüksek, yüksek). Sosyal seçim fonksiyonu bu dört profilin her birine bir sonuç atar.

Sonuç kümesi O probleme göre değişir. Tek bir nesne satılıyorsa sonuç “nesneyi kim alır?” sorusunun cevabıdır: O = {Ayşe, Bora, Cem, kimse}. Bir belediye birkaç projeden birini seçiyorsa sonuç seçilen projedir: O = {Park, Kütüphane, Spor salonu}. Bir okul yerleştirmesinde sonuç, her öğrencinin hangi okula gittiğini söyleyen bir atamadır.

Sosyal seçim fonksiyonu tasarımcının hedefini ifade eder. Tasarımcı “tipleri bilseydim ne yapmak isterdim?” sorusunu cevaplar. En sık kullanılan hedef verimliliktir: sonuç, oyuncuların değerlerinin toplamını en büyük yapmalıdır. Tek nesne satışında bu, nesneyi ona en çok değer verene vermek demektir.

Örnek, mekanizma tasarımının temel sorusunu açıkça ortaya koyar: f'yi, oyuncular kendi çıkarlarını gözetirken de uygulayan kurallar var mıdır? Bu sorunun cevabı bazen evet, bazen hayırdır. Tek nesne satışında cevap evettir: kazananın ödediği fiyatı doğru seçmek yeterlidir (4.2.4). Bazı ortamlarda ise hiçbir kural istenen her şeyi birden sağlayamaz (4.2.7).

4.2.2Doğrudan mekanizma ve yarı doğrusal fayda

Tasarımcı bilgiyi oyunculardan almalıdır. En dolaysız yol, her oyuncudan tipini söylemesini istemektir. Bu tür mekanizmalara doğrudan mekanizma denir.

Şekil 4.5 doğrudan mekanizmayı bir kutu olarak gösterir. Kutunun girdisi bildirimler, çıktısı sonuç ve ödemelerdir. Kutunun içindeki kurallar herkes tarafından bilinir. Oyuncular bu kuralları bilerek ne bildireceklerine karar verir.

“Yarı doğrusal” ne demektir? Faydanın para kısmı doğrusaldır: 1 TL daha fazla ödemek faydayı tam 1 birim azaltır. Değer kısmı ise v_i(x) herhangi bir fonksiyon olabilir. Bu varsayım, değerin ve paranın aynı birimle ölçülmesini sağlar. Değer 85 bin TL olan bir nesneyi 70 bin TL'ye alan oyuncunun faydası 15 bin TL'dir; nesneyi hiç almayan ve hiçbir şey ödemeyen oyuncunun faydası 0'dır. Yarı doğrusal fayda paranın kişiden kişiye aktarılabildiği ortamların standart modelidir. Bu bölümde para kullanılan bütün mekanizmalar bu varsayıma dayanır.

Dolaylı mekanizmalar. Her mekanizma oyunculardan tiplerini istemez. Bir İngiliz açık artırmasında fiyat yavaş yavaş yükselir ve oyuncular el kaldırarak oyunda kalıp kalmadıklarını gösterir. Bir pazarlıkta taraflar sırayla teklif verir. Bu tür mekanizmalara dolaylı mekanizma (indirect mechanism) denir: oyuncunun stratejisi tipini söylemek değil, başka bir eylemdir (el kaldırmak, teklif vermek, bir sıra yazmak). Dolaylı mekanizmalar uygulamada çok yaygındır; ama kuramsal olarak doğrudan mekanizmalara indirgenebilirler. Bu indirgemeyi açıklama ilkesi sağlar.

4.2.3Açıklama ilkesi

Mekanizma tasarımcısının önünde sonsuz sayıda olası kural vardır: açık artırmalar, sıralı teklifler, karmaşık oylama usulleri… Bunların hepsini incelemek imkânsızdır. Açıklama ilkesi bu arama alanını büyük ölçüde daraltır: yalnızca doğrudan ve dürüst bildirimli mekanizmalara bakmak yeterlidir.

İlkenin arkasındaki düşünce Şekil 4.6'da görülür. M bir dolaylı mekanizma olsun ve oyuncuların denge stratejileri s₁, …, s_n olsun. Her strateji bir kuraldır: tipi θ_i olan oyuncu s_i(θ_i) eylemini seçer. Tasarımcı şu yeni mekanizmayı kurar: “Bana tipini söyle; ben senin yerine, o tipte senin oynayacağın denge stratejisini oynarım.” Bu yeni mekanizma M* doğrudandır, çünkü oyuncudan yalnızca tipini ister.

Bu basit gözlem çok güçlü bir sonuç verir: “Bu hedefi uygulayan bir mekanizma var mı?” sorusunu cevaplamak için yalnızca dürüst bildirimin denge olduğu doğrudan mekanizmalara bakmak yeterlidir. Böyle bir doğrudan mekanizma yoksa hiçbir dolaylı mekanizma da yoktur.

İlkenin sınırlarını da doğru anlamak gerekir. Açıklama ilkesi “her mekanizmada dürüst bildirim baskın stratejidir” demez. İlke yalnızca, kurulan M* mekanizmasında dürüst bildirimin bir denge olduğunu söyler. Hangi tür denge olduğu ise M'de kullanılan denge kavramına bağlıdır. M'de stratejiler baskın stratejiyse M*'de dürüstlük baskın stratejidir. M'de stratejiler yalnızca bir Bayes–Nash dengesi oluşturuyorsa (4.5.1) M*'de dürüstlük de yalnızca bir Bayes–Nash dengesidir. Bu iki durum aşağıda iki ayrı teşvik koşuluyla tanımlanır.

4.2.4Teşvik uyumluluğu ve bireysel rasyonellik

Bir doğrudan mekanizmanın iyi işlemesi için iki koşul aranır. Birincisi oyuncunun doğruyu söylemesinin kendi çıkarına olmasıdır. İkincisi oyuncunun mekanizmaya katılmayı istemesidir. Birinci koşula teşvik uyumluluğu, ikincisine bireysel rasyonellik denir.

Gösterimi kolaylaştırmak için u_i(θ_i; b_i, b_−i) yazılır. Bu ifade şunu anlatır: gerçek tipi θ_i olan oyuncu b_i bildirir, diğerleri b_−i bildirir; oyuncunun gerçek faydası budur. b_−i, “i dışındaki herkesin bildirimleri” demektir. Noktalı virgülden önceki θ_i faydanın hangi gerçek değere göre ölçüldüğünü, sonrası ise bildirimleri gösterir.

DSIC çok güçlü bir koşuldur. Oyuncunun diğerleri hakkında hiçbir şey bilmesine ya da tahmin etmesine gerek yoktur. Diğerleri dürüst de olsa yalancı da olsa, akıllı da olsa hatalı da olsa, dürüst bildirim oyuncu için en iyisidir. Dürüst bildirim baskın strateji olur. Bu yüzden DSIC mekanizmalar oyunculara basit bir öğüt verir: “Ne düşündüğünü söyle, gerisini düşünme.”

BIC koşulu DSIC'ten iki yönden zayıftır. Birincisi, yalnızca diğerleri dürüstken doğruyu söylemenin en iyi olduğunu ister; diğerleri yalan söylüyorsa bir şey söylemez. İkincisi, faydanın her durumda değil, ortalamada (beklenen değer olarak) en büyük olmasını ister. Beklenen değer, her olası durumun faydasının o durumun olasılığıyla çarpılıp toplanmasıdır. Örneğin rakibin değeri yarı yarıya 4 ya da 8 ise ve oyuncu bir bildirimle ilk durumda 6, ikinci durumda 0 alıyorsa beklenen faydası ½ · 6 + ½ · 0 = 3'tür.

Tersinin neden doğru olmadığı Bayesçi oyunlar ele alınınca (4.5.4) birinci fiyat açık artırmasıyla görülür.

IR koşulu katılımla ilgilidir. Bir mekanizma insanları zorla katılmaya zorlayamıyorsa, katılanların zarar etmemesi gerekir. Katılmak zarar ettiriyorsa oyuncu dışarıda kalır ve mekanizma onun bilgisini hiç almaz. Örneğin bir açık artırmada kazanan, değerinden fazla ödemek zorunda kalıyorsa IR bozulur.

Teşvik uyumluluğunu bir sayısal örnekle görmek en kolay yoldur. Bir nesne iki teklifçi arasında satılsın. Teklifçinin değeri 10, rakibin teklifi 6 olsun. İki ödeme kuralı karşılaştırılır. Birinci fiyat kuralında kazanan kendi teklifini öder. İkinci fiyat kuralında kazanan rakibin teklifini öder. İki kuralda da en yüksek teklif kazanır.

Örnekteki rakip teklif 6 keyfî bir seçimdir. Rakip teklif r ne olursa olsun ikinci fiyat kuralında aynı mantık işler. r < 10 ise dürüst teklif kazanır ve 10 − r > 0 fayda verir; daha düşük bir teklif ya yine aynı faydayı verir ya da kaybettirir. r > 10 ise dürüst teklif kaybeder ve 0 verir; r'nin üstüne çıkan bir teklif kazandırır ama 10 − r < 0 fayda verir. Her durumda dürüst teklif en iyisidir; ikinci fiyat kuralı DSIC'tir. Ayrıca kazanan hiçbir zaman değerinden fazla ödemez ve kaybeden ödemez; kural IR'dir.

4.2.5Ültimatom oyununa dönüş

Teşvik uyumluluğu ve bireysel rasyonellik tanımlandığına göre Ültimatom Oyunu yeniden ele alınabilir. Oyunda teklif eden, yanıtlayana bir “al ya da bırak” mekanizması sunar. Yanıtlayanın IR koşulu, kabul ettiğinde aldığının reddettiğinde aldığından az olmamasıdır.

Kuramın cevabı. Yanıtlayan yalnızca jeton sayısını önemsiyorsa, x jetonluk teklifi kabul etmek x, reddetmek 0 verir. x ≥ 0 olduğu sürece kabul etmek en iyi tepkidir; bu yanıtlayanın IR koşuludur. x = 0'da kabul de ret de 0 verdiği için yanıtlayan kayıtsızdır; iki seçenek de en iyi tepkidir.

Teklif eden, yanıtlayanın bu davranışını önceden görür ve buna göre teklif seçer. Oyun sıralı olduğu için çözüm geriye doğru çıkarımla bulunur: önce yanıtlayanın her teklife ne diyeceği belirlenir, sonra teklif eden bunu bilerek kendi seçimini yapar. Bu yolla bulunan dengelere alt oyun mükemmel denge (subgame perfect equilibrium) denir. Teklifler tam sayıysa iki alt oyun mükemmel denge vardır.

Gerçekte ne olur? Oyunun ilk deneyinden (Güth, Schmittberger ve Schwarze, 1982) bu yana yüzlerce deneyde benzer bir tablo ortaya çıkmıştır. En sık teklif pastanın %40–50'sidir. %20'nin altındaki tekliflerin yaklaşık yarısı reddedilir (Camerer, 2003). Yani insanlar adaletsiz buldukları teklifi, kendi kazançları pahasına cezalandırır. Bu davranış, “yalnız jetonu önemseyen” oyuncu modeline uymaz.

Etkileşimli Ültimatom oyununda bilgisayar yanıtlayan üç farklı düzeyde oynar. Her düzeyde yanıtlayanın kabul ettiği en küçük teklif farklıdır. Teklif edenin en iyi tepkisi her seferinde yanıtlayanın kabul ettiği en küçük teklifi önermektir. Tablo 4.1 bu durumları karşılaştırır.

Tablonun “Kuram” satırı, yanıtlayanın 0'ı reddettiği (9, 1) dengesine karşılık gelir; yanıtlayan 0'ı da kabul ederse teklif eden 0 önerip 10 alır. Adalete duyarlı yanıtlayana karşı teklif eden 5'ten azını öneremez; önerirse ret gelir ve 0 alır. Teklif edenin kazancı, yanıtlayanın kabul eşiği yükseldikçe düşer.

Mekanizma tasarımı için çıkan ders şudur: teşvik uyumlu bir mekanizma tasarlarken oyuncunun fayda fonksiyonu doğru seçilmelidir. Oyuncu adaleti de önemsiyorsa IR koşulu “x ≥ 0” değil, “x, oyuncunun adil bulduğu payı aşıyor” olur. Yanlış bir fayda modeliyle kurulan mekanizma kâğıt üstünde IR görünür ama gerçekte reddedilir. Bu konuya, davranış ve etik tartışmasında (4.6.1) yeniden dönülür.

4.2.6Orantılı maliyet paylaşımı adım adım

Beleşçi sorunu (4.1.4) şimdi sayılarla incelenir. Üç sakin, Ayşe, Bora ve Cem, ortak bir park yapılmasını istiyor. Parkın maliyeti 60 bin TL'dir. Sakinlerin parka verdiği gerçek değerler sırasıyla 30, 25 ve 20 bin TL'dir. Değerlerin toplamı 75'tir. 75 > 60 olduğu için parkın yapılması verimlidir: park, maliyetinden fazla değer yaratır.

Belediye şu kuralı uygular. Her sakin parka verdiği değeri bildirir. Bildirimlerin toplamı 60 ya da daha fazlaysa park yapılır ve maliyet bildirimlerle orantılı paylaşılır: sakin i'nin ödemesi 60 · b_i / (b₁ + b₂ + b₃)'tür. Toplam 60'tan azsa park yapılmaz ve kimse ödemez. Kural adil görünür: parka çok değer veren çok öder. Soru, kuralın teşvik uyumlu olup olmadığıdır.

Sorunun kaynağı açıktır: bir sakinin bildirimi, sonuç değişmese bile kendi ödemesini doğrudan etkiler. Cem 20 yerine 5 dediğinde park yine yapılır; yani Cem'in yalanı sonucu değiştirmez, yalnızca kendi ödemesini düşürür. Teşvik uyumlu bir kural için çözüm fikri şudur: oyuncunun bildirimi ödemesini yalnızca seçilen sonucu değiştirerek etkileyebilmelidir. Sonuç aynı kalıyorsa ödeme de aynı kalmalıdır. Bu fikir VCG mekanizmasının (4.3) temelidir.

4.2.7Tasarım ölçütleri ve ödünleşimler

Bir mekanizmayı değerlendirmek için dört temel ölçüt kullanılır. İlk ikisi teşviklerle, son ikisi sonucun niteliğiyle ilgilidir.

• Teşvik uyumluluğu (IC): gerçek bilgiyi açıklamak en iyi seçenektir. Baskın strateji düzeyinde (DSIC) ya da Bayesçi düzeyde (BIC) istenebilir.
• Bireysel rasyonellik (IR): katılmak, dışarıda kalmaktan kötü değildir.
• Verimlilik (efficiency): dürüst bildirimde seçilen sonuç sosyal refahı en yüksek sonuçtur. Bir x sonucunun sosyal refahı SW(x) = Σ_i v_i(x), yani oyuncuların o sonuca verdiği değerlerin toplamıdır.
• Bütçe dengesi: ödemelerin toplamıyla ilgilidir. Zayıf bütçe dengesi ödemelerin toplamının en az 0 olmasıdır: mekanizma dışarıdan para gerektirmez. Tam bütçe dengesi ödemelerin toplamının tam 0 olmasıdır: ne dışarıdan para gerekir ne de para artar.

Σ sembolü “topla” demektir. Σ_i v_i(x) ifadesi, i'nin bütün oyuncuları dolaştığı ve her birinin v_i(x) değerinin toplandığı anlamına gelir. Üç oyuncu için v₁(x) + v₂(x) + v₃(x) yazmakla aynıdır.

Şekil 4.8 dört mekanizmayı bu ölçütlerle karşılaştırır. VCG ve orantılı pay kamu projesi örneğinden, sabit fiyat ve orta nokta ise iki taraflı ticaretten (bilateral trade) alınmıştır. İki taraflı ticarette bir satıcı ve bir alıcı vardır. Satıcının malı elinde tutmanın kendisine maliyeti c, alıcının mala verdiği değer v'dir. İkisi de özel bilgidir. Ticaret yalnızca v ≥ c olduğunda verimlidir: mal, ona daha çok değer verenin eline geçmelidir.

Örneklerdeki ödünleşim tesadüf değildir. Myerson ve Satterthwaite (1983) bunun genel bir sonuç olduğunu gösterdi.

Teoremin ispatı bu notun kapsamı dışındadır. Önemli olan sonucun anlamıdır: dört ölçütün hepsini birden isteyen bir tasarımcı imkânsızı ister. Mekanizma tasarımı bu yüzden çoğu zaman bir ödünleşim (trade-off) problemidir. Tasarımcı hangi ölçütten ne kadar vazgeçeceğine karar verir. Örneğin VCG verimliliği ve DSIC'i korur, karşılığında bütçe fazlası verir; sabit fiyat bütçeyi ve teşvikleri korur, karşılığında bazı verimli ticaretleri kaçırır.

4.2.8Uygulama kuramı: dürüstlük tek denge mi?

Açıklama ilkesi, dürüst bildirimin bir denge olduğunu söyler. Ama bir oyunda birden çok denge olabilir. Aynı mekanizmada istenmeyen başka dengeler de bulunabilir. Kurallar iyi bir dengeyi mümkün kılar; ama oyuncuların o dengede buluşacağını garanti etmez.

Bir mekanizmanın bütün dengelerinin istenen sonuca götürmesi daha güçlü bir istektir. Bu tür mekanizmaları inceleyen alana uygulama kuramı (implementation theory) denir. Alanın temel sonuçlarından biri, Nash dengesiyle uygulanabilen sosyal seçim fonksiyonlarını karakterize eden Maskin'in çalışmasıdır (Maskin, 1999). Burada yalnızca sorunun neden önemli olduğu bir örnekle gösterilir.

Bu kötü denge, mekanizmanın DSIC olmasıyla çelişmez. Dürüst teklif hâlâ her iki oyuncu için baskın stratejidir. Kötü denge, zayıf baskılanan tekliflerle kurulmuştur: Bora'nın 100 teklifi, dürüst teklif 5'e göre hiçbir durumda daha iyi değildir ve bazı durumlarda (örneğin Ayşe 50 teklif ederse) daha kötüdür. Ayşe'nin 0 teklifi de dürüst teklif 10'a göre zayıf baskılanır.

Çıkan ders iki yönlüdür. DSIC mekanizmalarda oyuncunun rakibini tahmin etmesi gerekmez; dürüstlük her durumda güvenli bir seçimdir. Bu yüzden DSIC tasarımlar, yalnızca Nash dengesine dayanan tasarımlardan daha sağlamdır. Yine de DSIC tek denge garantisi vermez. Oyuncular baskın stratejilerini oynamazsa garip dengeler ortaya çıkabilir.

4.2.9Tek parametreli ortamlar: Myerson lemması

Birçok önemli problemde her oyuncunun özel bilgisi tek bir sayıdır. Tek nesne satışında bu sayı nesneye verilen değerdir. Birden çok özdeş nesnenin satıldığı ve her oyuncunun en fazla bir nesne istediği durumda yine tek bir sayı yeterlidir. Bu tür ortamlara tek parametreli ortam (single-parameter environment) denir.

Tek parametreli ortamda her oyuncunun bir birim değeri v_i vardır. Mekanizma bildirimler b'den her oyuncu için bir tahsis x_i(b) ve bir ödeme p_i(b) seçer. Tahsis, oyuncunun ne kadar “mal” aldığını gösterir: tek nesnede 0 ya da 1'dir; nesne kurayla veriliyorsa 0 ile 1 arasında bir olasılık olabilir. Oyuncunun faydası v_i · x_i − p_i'dir.

Myerson (1981), tek parametreli ortamlarda DSIC mekanizmaları tam olarak betimleyen bir sonuç kanıtladı. Sonuç iki soruya cevap verir: hangi tahsis kuralları DSIC bir mekanizmada kullanılabilir ve bu durumda ödemeler ne olmalıdır?

Formüldeki integral işareti (∫) korkutucu görünebilir, ama burada yalnızca bir alanı ifade eder. ∫₀^b_i x_i(z, b_−i) dz, yatay eksende 0'dan b_i'ye kadar, x_i eğrisinin altında kalan alandır. Bu bölümdeki bütün örneklerde eğri basamak biçimindedir. Basamaklı bir eğrinin altındaki alan, dikdörtgenlerin alanları toplanarak bulunur: her dikdörtgen için genişlik × yükseklik.

Formülün geometrik okuması şöyledir. b_i · x_i(b), genişliği b_i, yüksekliği x_i(b) olan dikdörtgenin alanıdır. Bu dikdörtgenden eğrinin altındaki alan çıkarılınca, eğrinin solunda, 0 ile x(b) yükseklikleri arasında kalan alan elde edilir. Ödeme bu boyalı alandır. Eğrinin altındaki alan ise oyuncunun faydasıdır: dürüst bildirimde v_i x_i − p_i = ∫₀^v_i x_i(z) dz.

Basamak formülünün nedeni şudur: tahsisteki her sıçrama, oyuncunun o eşiği geçerek fazladan bir “mal parçası” almasıdır. Oyuncu bu parçanın her birimi için tam eşik kadar öder. 3'ü geçerek 0,4 birim mal alır ve her birim için 3 öder; 5'i geçerek 0,6 birim daha alır ve her birim için 5 öder.

Kritik teklif. Tahsis yalnızca 0 ya da 1 olabiliyorsa tek bir sıçrama vardır. Bu durumda ödeme, oyuncunun kazanması için gereken en düşük tekliftir. Bu teklife kritik teklif (critical bid) denir. Tek nesne satışında kritik teklif, diğerlerinin en yüksek teklifidir. Myerson lemması bu yüzden şunu söyler: tek nesnede en yüksek teklife veren ve DSIC olan tek ödeme kuralı, kazananın ikinci en yüksek teklifi ödediği Vickrey kuralıdır (kaybedenler 0 öder).

Ödeme kritik teklif olmazsa ne olur? Eşik 50, kazananın ödemesi ise sabit 20 olsun. Değeri 35 olan bir oyuncu dürüst teklif verirse eşiğin altında kalır ve 0 alır. 50'yi aşan bir teklif verirse nesneyi alır ve 20 öder; faydası 35 − 20 = 15'tir. Değerini abartmak kazandırdı. Genel olarak, değeri ödeme ile eşik arasında kalan (burada 20 ile 50 arasında) her oyuncu abartmak ister; IC bozulur. Ödeme eşikten büyük olsaydı bu kez değeri eşik ile ödeme arasında kalan kazananlar zarar ederdi ve teklifini eşiğin altına indirmek isterdi.

Monotonluk neden gereklidir? Kısa bir akıl yürütme bunu gösterir. Değeri y olan bir oyuncunun dürüst bildirimi, z bildirmekten kötü olmamalıdır; değeri z olan bir oyuncunun dürüst bildirimi de y bildirmekten kötü olmamalıdır:

y · x(y) − p(y) ≥ y · x(z) − p(z) ve z · x(z) − p(z) ≥ z · x(y) − p(y)

İki eşitsizlik taraf tarafa toplanınca ödemeler sadeleşir ve y · x(y) + z · x(z) ≥ y · x(z) + z · x(y) kalır. Bu, (z − y)(x(z) − x(y)) ≥ 0 biçiminde yazılabilir. z > y ise x(z) ≥ x(y) olmalıdır: daha yüksek teklif daha az tahsis veremez. Yani DSIC, monotonluğu zorunlu kılar. Lemmanın öteki yönü, yani her monoton tahsisin formüldeki ödemeyle DSIC olduğu, Roughgarden'ın (2016) ders notlarında adım adım ispatlanır.

4.3VCG mekanizması

Orantılı maliyet paylaşımının başarısızlığı (4.2.6) bir çözüm fikri bırakmıştı: oyuncunun bildirimi ödemesini yalnızca seçilen sonucu değiştirerek etkilemelidir. Vickrey–Clarke–Groves (VCG) mekanizması bu fikri genel bir kurala dönüştürür. Mekanizma, William Vickrey'nin (1961) tek nesne açık artırması, Edward Clarke'ın (1971) kamu malı çalışması ve Theodore Groves'un (1973) genel çerçevesinin birleşimidir. Bu kısımda VCG'nin tanımı, bir kamu projesi örneğinde adım adım hesabı, Python kodu, yalanın neden kazandırmadığı ve sınırları anlatılır.

4.3.1Verimli seçim ve Clarke pivot ödemesi

VCG iki adımda çalışır. Birinci adımda sonuç seçilir, ikinci adımda ödemeler hesaplanır. Sonuç seçimi verimlidir: bildirilen değerlere göre sosyal refahı en yüksek sonuç seçilir. Ödeme ise her oyuncunun varlığının diğerlerine verdiği zarara eşittir.

İki formülü sözle okumak yararlıdır. argmax, en büyük değeri veren seçeneği döndürür; max ise en büyük değeri döndürür. x*, bütün oyuncuların bildirdiği değerlerin toplamını en büyük yapan sonuçtur. Ödeme formülünde Σ_j≠i, “i dışındaki bütün oyuncular üzerinden topla” demektir. Formülün iki parçası şunlardır:

• Birinci terim: i hiç olmasaydı, diğer oyuncular kendi aralarında en iyi sonucu seçer ve bu sonuçtan şu kadar refah alırlardı. Kısaca, “i olmasaydı diğerlerinin en iyi refahı”.
• İkinci terim: i varken seçilen x* sonucunda diğerlerinin aldığı refah. Kısaca, “i varken diğerlerinin refahı”.

Fark, i'nin katılımının diğerleri üzerinde yarattığı dışsallıktır (externality). Dışsallık, bir kişinin kararının başkalarına verdiği ama kendisinin ödemediği zarardır (ya da sağladığı yarardır). Bir fabrikanın havayı kirletmesi olumsuz bir dışsallıktır. VCG, her oyuncuya kendi yarattığı olumsuz dışsallığı ödetir. Oyuncu sonucu kendi lehine değiştirmiyorsa birinci ve ikinci terim eşittir ve oyuncu hiçbir şey ödemez. Sonucu değiştiren, yani “pivot” olan oyuncu, değişikliğin diğerlerine maliyetini öder. Kuralın adı buradan gelir.

Şekil 4.10 bu fikri bir sütun çiftiyle gösterir. Soldaki sütun Bora yokken diğerlerinin alacağı refahı, sağdaki sütun Bora varken aldıkları refahı gösterir. Bora'nın varlığı seçimi Park'tan Spor salonuna kaydırır ve diğerlerinin refahını 50'den 45'e düşürür. Bora bu 5 birimlik zararı öder. Örneğin bütün sayıları 4.3.2'de verilir.

VCG neden DSIC'tir? Ödeme formülünün birinci terimi yalnızca diğerlerinin bildirimlerine bağlıdır; i ne bildirirse bildirsin değişmez. Bu terime h_i diyelim. Diğerleri b_−i bildirsin ve i'nin bildirimi sonucu x yapsın. i'nin gerçek faydası şöyledir:

u_i = v_i(x) − p_i = v_i(x) + Σ_j≠i b_j(x) − h_i

İspatın ana fikri tek bir cümleyle söylenebilir: VCG'de oyuncunun faydası, sosyal refahtan kendisinden bağımsız bir terimin çıkarılmasıyla elde edilir. Dolayısıyla her oyuncu sosyal refahın en büyük olmasını ister ve mekanizma da tam olarak bunu yapar. Oyuncunun çıkarı ile toplumun çıkarı aynı hizaya getirilmiştir.

4.3.2Kamu projesi seçimi adım adım

Üç sakin, Ayşe, Bora ve Cem, üç projeden biri için oy kullanacak: Park, Kütüphane ve Spor salonu. Yalnızca bir proje yapılacak. Her sakin her projeye değerini (bin TL) bildiriyor. Herkesin dürüst bildirdiği varsayılır.

Sonuçları yorumlamak, mekanizmanın mantığını pekiştirir. Ayşe en çok Park'ı istiyordu ama onun tercihi sonucu değiştirmedi; Ayşe ödemez. Bora ve Cem'in her biri tek başına pivottur: biri olmasa Park seçilirdi. Bu yüzden ikisi de öder. Cem'in ödemesi daha büyüktür, çünkü Cem'in varlığı seçimi daha pahalı bir biçimde değiştirir: Cem olmadan Ayşe ve Bora'nın Park'tan alacağı 40 yerine Spor'da yalnızca 20 alırlar.

Toplanan 25 birim kimseye geri dağıtılmaz. Bu, VCG'nin bir bütçe fazlası verdiği anlamına gelir. Para sakinlere geri dağıtılsaydı, dağıtılan pay oyuncuların bildirimine bağlı olacağı için teşvikler bozulabilirdi. Ödemeler negatif olmadığı için mekanizma dışarıdan para gerektirmez: zayıf bütçe dengesi sağlanır, tam bütçe dengesi sağlanmaz.

4.3.3Kod izleme: vcg()

VCG'nin bütün hesabı kısa bir Python fonksiyonuyla yazılabilir. Fonksiyon iki girdi alır. v bir sözlüktür: v[i][a], oyuncu i'nin a sonucuna bildirdiği değerdir. A olası sonuçların listesidir. Fonksiyon seçilen sonucu ve ödemeleri döndürür.

def vcg(v, A):
  N = list(v)            # oyuncular
  def w(a, S):           # S'nin a'daki refahı
    return sum(v[i][a] for i in S)
  x = max(A, key=lambda a: w(a, N))
  p = {}
  for i in N:
    D = [j for j in N if j != i]
    yok = max(w(a, D) for a in A)  # i yokken
    var = w(x, D)                  # i varken
    p[i] = yok - var
  return x, p

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

• N = list(v) sözlüğün anahtarlarından oyuncu listesini çıkarır: ['Ayşe', 'Bora', 'Cem'].
• İç fonksiyon w(a, S), S kümesindeki oyuncuların a sonucuna verdiği değerlerin toplamıdır. w(a, N) herkesin refahı, w(a, D) ise yalnız D kümesinin refahıdır.
• x = max(A, key=lambda a: w(a, N)), A'daki sonuçlardan w(a, N)'yi en büyük yapanı seçer. Bu, argmax işleminin Python karşılığıdır.
• p = {} boş bir ödeme sözlüğüdür.
• Döngüde her oyuncu i için D, i dışındaki oyuncuların listesidir. yok, D'nin bütün sonuçlar arasındaki en büyük refahıdır: ödeme formülünün birinci terimi. var, D'nin seçilen x sonucundaki refahıdır: ikinci terim. Ödeme yok − var'dır.

Kamu projesi örneğinde girdi v = {'Ayşe': {'P': 40, 'K': 5, 'S': 0}, 'Bora': {'P': 0, 'K': 30, 'S': 20}, 'Cem': {'P': 10, 'K': 20, 'S': 45}} ve A = ['P', 'K', 'S']'dir. Tablo 4.4 döngünün her adımını gösterir.

İzleme, elle yapılan hesapla birebir örtüşür. Kodun sadeliği VCG'nin genel bir mekanizma olmasından gelir: sonuçlar ne olursa olsun (projeler, nesnelerin dağılımları, yollar) aynı fonksiyon çalışır. Tek koşul, her oyuncunun her sonuca bir değer bildirebilmesidir.

Kodla ilgili iki ayrıntı önemlidir. Birincisi, max eşitlikte listede ilk gelen sonucu seçer; bu sabit eşitlik bozma kuralı DSIC'i etkilemez. İkincisi, kod |A| sonuç ve n oyuncu için x'i bulmak üzere |A| · n toplama yapar; her oyuncunun ödemesi için de yaklaşık aynı işi tekrarlar. Toplam iş O(n² · |A|)'dır. Sonuç kümesi küçükken bu çok hızlıdır. Ama sonuçlar kombinatoryal olarak çoksa, örneğin 30 nesnenin oyunculara her türlü dağılımı söz konusuysa, |A| astronomik büyür. Bu sorun 4.3.6'da ele alınır.

4.3.4VCG'de yalan kazandırır mı?

Teorem, VCG'de yalanın kazandırmadığını söylüyor. Bunu kamu projesi örneğinde birkaç yalanla doğrudan sınamak, ispatın ne anlattığını somutlaştırır. Her satırda yalnızca bir oyuncu yalan söyler; diğerleri dürüsttür. Son sütun, yalancının gerçek değerine göre faydasıdır.

Bora'nın yalanı ilginçtir. Bora gerçekten de Kütüphane'yi Spor'a tercih ediyordu (30 > 20). Yalanla en sevdiği projeyi yaptırdı. Ama bunun bedeli, diğerlerine verdiği zarar kadar arttı: Kütüphane diğerleri için Spor'dan 20 birim daha kötüdür. Bora'nın kazancı (Kütüphane'de 10 birim daha fazla değer) bu bedeli karşılamaz. VCG'nin işleyişi tam olarak budur: sonucu değiştirmek serbesttir, ama değişikliğin başkalarına maliyeti ödenir. Değişiklik toplum için iyi değilse yalancı için de iyi değildir.

Bu dört durum yalnızca örnektir. Her oyuncu için her projeye 0, 10, …, 100 değerlerinden biri bildirilerek oluşturulan bütün bildirimler bilgisayarla denendiğinde hiçbir oyuncunun dürüst bildirimden daha yüksek fayda elde edemediği görülür. Bu, Teorem 4.5'in sayısal bir doğrulamasıdır.

4.3.5Tek nesnede VCG: Vickrey açık artırması

VCG genel bir mekanizmadır; tek nesne satışı onun özel bir durumudur. Bu özel durumda VCG'nin tam olarak ikinci fiyat (Vickrey) açık artırmasına dönüştüğü gösterilebilir. Bunun için aynı vcg() fonksiyonu tek nesneye uygulanır.

Tek nesnede bir sonuç “nesneyi kim alır?” sorusunun cevabıdır. Sonuçlar oyuncuların kendisidir: A = ['Ayşe', 'Bora', 'Cem']. Oyuncu i'nin a sonucuna değeri, a = i ise (nesne kendisine gidiyorsa) nesneye verdiği değer, değilse 0'dır. Değerler 70, 55, 85 olsun. Örneğin v['Ayşe'] = {'Ayşe': 70, 'Bora': 0, 'Cem': 0}'dır.

Sonucun genel nedeni açıktır. Kazanan olmasaydı nesne ikinci en yüksek değerli oyuncuya giderdi ve diğerlerinin refahı bu ikinci en yüksek değer olurdu. Kazanan varken diğerleri hiçbir şey almaz. Fark, ikinci en yüksek değerdir. Kaybeden bir oyuncu olmasaydı ise nesne yine aynı kişiye giderdi; kaybedenin dışsallığı sıfırdır. Bu sonuç, Myerson lemmasıyla (4.2.9) da tutarlıdır: tek nesnede DSIC ödeme kritik tekliftir ve kritik teklif ikinci en yüksek tekliftir.

4.3.6VCG'nin özellikleri ve sınırları

VCG kuramsal olarak çok çekici bir mekanizmadır. Güçlü yönleri şöyle sıralanır:

• DSIC: dürüst bildirim baskın stratejidir; oyuncuların birbirini tahmin etmesi gerekmez.
• Verimlilik: sosyal refahı en yüksek sonuç seçilir.
• IR ve negatif olmayan ödemeler: Clarke pivotu kullanıldığında ve değerler negatif olmadığında katılan kimse zarar etmez, mekanizma kimseye para ödemez.
• Genellik: tek nesnede Vickrey açık artırmasına, birden çok özdeş nesnede “kaybedenlerin en yüksek değerini öde” kuralına dönüşür.

Buna karşın VCG uygulamada az kullanılır. Bunun birkaç nedeni vardır:

• Tam bütçe dengesi yoktur. Kamu projesi örneğinde 25 birim fazla kalır. Mekanizma açık vermez (zayıf bütçe dengesi), ama fazla parayı oyunculara geri dağıtamaz. Kamu malı örneklerinde bu para “yakılmış” gibidir.
• Hesaplama zor olabilir. argmax hesabı, sonuçların çok olduğu kombinatoryal problemlerde NP-zor olabilir. Örneğin birçok nesnenin, her biri farklı nesne demetleri isteyen teklifçilere dağıtıldığı bir açık artırmada en iyi dağılımı bulmak, bilinen en zor optimizasyon problemleri sınıfındadır. Hesap tam yapılamaz da yaklaşık yapılırsa VCG'nin teşvik özellikleri bozulabilir.
• Danışıklılık ve sahte kimlik. Oyuncular gizlice anlaşırsa ya da bir oyuncu birden çok sahte kimlikle katılırsa yalan kârlı hâle gelebilir. VCG'nin teşvik garantisi yalnızca tek tek sapmalar içindir.
• Gelir düşük kalabilir. Ödemeler dışsallıklara eşit olduğu için, rekabetin az olduğu durumlarda satıcının geliri çok düşük, hatta sıfır olabilir.
• Mahremiyet. Oyuncular her sonuca verdikleri değeri açıklamak zorundadır. Bir şirket, bir ürüne ödemeye razı olduğu en yüksek fiyatı rakiplerine ve satıcıya açıklamak istemeyebilir.

Bu sınırlar nedeniyle gerçek uygulamalarda VCG yerine daha basit kurallar tercih edilir. Örneğin sponsorlu arama reklamlarında çoğunlukla genelleştirilmiş ikinci fiyat (generalized second price, GSP) kuralı kullanılır: reklamlar tekliflere göre sıralanır ve her reklamveren kendisinin bir altındaki teklifi öder. GSP DSIC değildir, ama basittir ve gelir açısından avantajlıdır. VCG ise kuramsal bir referans noktası olarak önemini korur: bir problemde verimli ve teşvik uyumlu bir sonucun mümkün olup olmadığını ve bunun bedelini gösterir.

4.4Parasız mekanizmalar

Şimdiye kadarki mekanizmalarda teşvikler ödemelerle düzeltildi. VCG, oyuncunun yarattığı dışsallığı ona ödeterek dürüstlüğü kârlı kıldı. Ancak birçok önemli problemde para kullanmak ya yasaktır ya da uygunsuzdur. Bu kısımda para olmadan çalışan mekanizmalar incelenir: kararlı eşleştirme için Gale–Shapley, tesis yerleşimi için medyan kuralı, okul yerleştirmede seri diktatörlük ve Boston mekanizması, oda takası için TTC.

4.4.1Para olmadan tasarım

Okul yerleştirmede öğrencilerden okula girmek için para istenmez. Yurt odası değişiminde öğrenciler birbirine para ödemez. Bir seçimde oy satın alınamaz. Organ naklinde organ alım satımı yasaktır. Bu ortamlarda tasarımcının elinde yalnızca bir araç kalır: sonuç kuralı. Ödeme ile teşvik düzeltilemez; kural öyle seçilmelidir ki doğruyu söylemek sonucu oyuncu için kötüleştirmesin.

Para olmadan teşvik uyumluluğu için kullanılan terim stratejiye dayanıklılıktır (strategy-proofness). Bir kural stratejiye dayanıklıysa hiçbir oyuncu, diğerleri ne bildirirse bildirsin, gerçek tercihleri yerine başka bir şey bildirerek daha iyi bir sonuç elde edemez. Bu, parasız ortamda DSIC'in karşılığıdır.

Genel tercihler için kötü bir haber vardır. Gibbard (1973) ve Satterthwaite (1975) birbirinden bağımsız olarak şunu gösterdi:

Diktatörlük elbette kabul edilebilir bir kural değildir. Teorem, genel tercihlerde dürüstlüğü garanti eden makul bir oylama kuralının bulunmadığını söyler. Bu yüzden parasız mekanizma tasarımı teoremin varsayımlarından birini gevşeterek ilerler. İki çıkış yolu vardır:

• Tercihlerin yapısını kullanmak. Tercihler her türlü sıralama olamıyorsa teorem geçerli olmaz. Örneğin seçenekler bir doğru üzerinde diziliyse ve her oyuncunun tek bir en sevdiği nokta varsa (tek tepeli tercihler), medyan kuralı stratejiye dayanıklıdır (4.4.7).
• Hedefi değiştirmek. “En iyi” seçeneği bulmak yerine başka bir ölçüt aranabilir. İki taraflı piyasalarda hedef kararlılıktır (Gale–Shapley). Herkesin elinde bir mal varken hedef takastır (TTC).

4.4.2Kararlı eşleştirme problemi

Bir bölümde üç öğrenci (A, B, C) ve üç bitirme projesi (X, Y, Z) vardır. Her proje tek öğrenci alır. Her öğrenci projeleri, her proje danışmanı da öğrencileri bir tercih sırasıyla sıralar. Tercih sıraları Tablo 4.7'de verilmiştir. “X ≻ Y ≻ Z” yazımı, “X'i Y'ye, Y'yi de Z'ye tercih eder” demektir.

Bir eşleştirme, her öğrenciyi farklı bir projeye atayan bir listedir. Üç öğrenci ve üç proje için 3! = 3 · 2 · 1 = 6 farklı eşleştirme vardır. Bunların hangisinin “iyi” olduğu sorusu, bir eşleştirmenin dağılıp dağılmayacağı sorusuyla yanıtlanır.

Engelleyici çift, eşleştirmeyi bozma gücüne sahiptir. Öğrenci ve danışman ikisi de mevcut durumdan memnun değildir ve birbirlerini istemektedir; kuralı bir yana bırakıp kendi aralarında anlaşabilirler. Kararlı bir eşleştirmede ise kimse anlaşmayı bozup kaçmak istemez. Bir çiftin engelleyici olması için iki koşul birlikte sağlanmalıdır: öğrenci projeyi şu anki projesine tercih etmeli ve proje öğrenciyi şu anki öğrencisine tercih etmelidir. Yalnızca biri istiyorsa çift engelleyici değildir.

Kararlı bir eşleştirme her zaman var mıdır? Varsa nasıl bulunur? Altı eşleştirmenin hepsini denetlemek küçük örnekte mümkündür. Ama n öğrenci için n! eşleştirme vardır; 20 öğrenci için bu sayı 2 · 10¹⁸'i aşar. Daha akıllıca bir yöntem gerekir. Gale ve Shapley (1962) iki soruyu birden cevaplayan bir algoritma verdi.

4.4.3Gale–Shapley: ertelenmiş kabul

Gale–Shapley algoritmasında (Gale–Shapley algorithm) bir taraf teklif verir, öteki taraf teklifleri değerlendirir. Burada öğrenciler teklif verir, projeler kabul ya da ret eder. Algoritma turlar hâlinde ilerler:

1. Her serbest öğrenci, henüz kendisini reddetmemiş en iyi projesine teklif verir.
2. Her proje, gelen teklifler ve elinde tuttuğu aday arasından en iyisini geçici olarak tutar, diğerlerini reddeder.
3. Reddedilen öğrenciler serbest kalır. Serbest öğrenci kalmayınca algoritma durur ve geçici eşleşmeler kesinleşir.

Algoritmanın öteki adı ertelenmiş kabuldür (deferred acceptance). Ad, ikinci adımdaki “geçici” sözcüğünden gelir. Proje bir teklifi kabul ettiğinde kesin söz vermez; daha iyi bir aday gelirse eskisini bırakabilir. Kesin kabul algoritmanın sonuna ertelenir. Bu ayrıntı, algoritmanın kararlı bir sonuç vermesinin anahtarıdır.

Kararlılık “herkes en sevdiğini alır” demek değildir. C son tercihi Z'ye kaldı; ama C'yi isteyen tek proje Z'dir. X ve Y, C'den daha çok sevdikleri öğrencilerle eşleşmiştir.

4.4.4Kod izleme: gale_shapley()

Algoritmanın Python sürümü turlar yerine bir kuyrukla çalışır. Her adımda kuyruktan bir serbest öğrenci çıkar ve bir teklif verir. Girdi olarak ogr sözlüğü her öğrencinin tercih listesini (en iyiden kötüye), proj sözlüğü ise her projenin öğrencilere verdiği sırayı tutar: proj[p][s], p projesinin s öğrencisine verdiği sıradır ve 0 en iyi demektir. Örneğin proj['X'] = {'B': 0, 'A': 1, 'C': 2}'dir.

def gale_shapley(ogr, proj):
  serbest, es = list(ogr), {}
  sira = {s: 0 for s in ogr}
  while serbest:
    s = serbest.pop(0)
    p = ogr[s][sira[s]]        # sıradaki
    sira[s] += 1
    r = es.get(p)              # p'deki aday
    if r is None or proj[p][s] < proj[p][r]:
      es[p] = s                # kabul
      if r: serbest.append(r)
    else: serbest.append(s)    # red
  return es

Kodun parçaları şunlardır:

• serbest serbest öğrencilerin kuyruğudur; başta herkes buradadır. es sözlüğü her projenin geçici olarak tuttuğu öğrenciyi saklar.
• sira[s], öğrenci s'nin tercih listesinde sıradaki indistir. Başta 0'dır, yani en sevilen proje.
• Döngüde kuyruğun başındaki öğrenci s çıkarılır, sıradaki tercihi p'ye teklif verir ve sira[s] bir artırılır. Böylece bir öğrenci aynı projeye iki kez teklif vermez.
• r, p'nin şu anda tuttuğu adaydır; proje boşsa None'dır.
• Proje boşsa ya da p, s'yi r'ye tercih ediyorsa (sıra sayısı küçükse) s kabul edilir. Eski aday r varsa kuyruğa döner.
• Aksi hâlde s reddedilir ve kuyruğa geri döner.

Kuyruk boşalınca algoritma 6 teklifle biter. Sonuç es = {'X': 'B', 'Y': 'A', 'Z': 'C'}'dir; bu, eşzamanlı turlarla bulunan A–Y, B–X, C–Z eşleştirmesiyle aynıdır. Tekliflerin işlenme sırası farklı olsa da (turlarda A ile B aynı anda teklif verirken kodda sırayla verir) sonuç değişmez. Gale–Shapley'in sonucu tekliflerin hangi sırayla işlendiğine bağlı değildir; bu, algoritmanın bilinen bir özelliğidir.

Kaç teklif? Her öğrenci her projeye en fazla bir kez teklif verir, çünkü sira[s] yalnızca artar. n öğrenci ve n proje için toplam teklif sayısı en fazla n · n = n²'dir. Her teklif sabit sürede işlendiği için algoritmanın çalışma süresi O(n²)'dir. 20 öğrencilik bir örnekte 400'den az teklif yeterlidir; 20! eşleştirmeyi tek tek denetlemekle kıyaslanamayacak kadar hızlıdır.

4.4.5Gale–Shapley'in özellikleri

Algoritmanın öteki önemli özellikleri şunlardır:

• Teklif veren tarafa en iyi. Bir problemde birden çok kararlı eşleştirme olabilir. Gale–Shapley'de teklif veren her oyuncu, bütün kararlı eşleştirmeler içinde alabileceği en iyi eşi alır. Teklif alan taraf ise her kararlı eşleştirme içinde en kötü eşini alır. Hangi tarafın teklif verdiği bu yüzden önemli bir tasarım kararıdır.
• Teklif verenler için DSIC. Teklif veren taraf için gerçek tercih sırasını bildirmek baskın stratejidir (Roth, 1982). Teklif alan taraf ise bazen yalan söyleyerek kazanabilir (4.4.6).
• Uygulamalar. ABD'de tıp fakültesi mezunlarının ihtisas yerlerine yerleştirilmesi (NRMP) bu algoritmanın bir sürümüyle yapılır. Boston ve New York okul seçimi sistemleri de ertelenmiş kabule dayanır. Roth ve Shapley 2012 Nobel Ekonomi Ödülü'nü bu çalışmalarla aldı.

Örnekteki tercihlerde altı eşleştirmenin hepsi denendiğinde yalnızca bir kararlı eşleştirme bulunur: A–Y, B–X, C–Z. Bu yüzden projeler teklif verseydi de sonuç aynı olurdu. Projeler teklif verdiğinde X'in ilk tercihi B'dir, Y'nin ve Z'nin ilk tercihi A'dır. A, Y ile Z arasında Y'yi tutar; Z reddedilir ve sıradaki B'ye teklif verir. B, X'i Z'ye tercih ettiği için Z'yi reddeder; Z son olarak C'ye teklif verir. Sonuç yine A–Y, B–X, C–Z'dir.

4.4.6Teklif alan taraf yalanla kazanabilir

Gale–Shapley teklif verenler için DSIC'tir; teklif alan taraf için değildir. Bunu görmek için yeni bir örnek ele alınır. Öğrenciler yine teklif verir. Tercihler şöyledir: A: X ≻ Y ≻ Z, B: Y ≻ X ≻ Z, C: X ≻ Y ≻ Z. Projelerin gerçek tercihleri X: B ≻ A ≻ C; Y ve Z: A ≻ B ≻ C'dir.

Yalanın nasıl işlediği Şekil 4.17 ile Şekil 4.18 karşılaştırılınca görülür. X, A'yı reddederek bir ret zinciri başlatır. Reddedilen A, Y'ye gider ve Y'de B'nin yerini alır. Yerinden olan B ise sıradaki tercihi X'e gelir. X'in yalanı, istediği öğrenciyi kendisine geri getiren bir zincir kurmuştur.

Altı eşleştirme denetlendiğinde bu tercihlerde iki kararlı eşleştirme olduğu görülür: öğrencilere en iyi gelen A–X, B–Y, C–Z ve projelere en iyi gelen A–Y, B–X, C–Z. Öğrenci önerili Gale–Shapley birincisini bulur. X'in yalanı sonucu ikincisine, yani projelere en iyi gelene taşır. Bu, genel bir sonucun özel bir hâlidir: hiçbir kararlı mekanizma iki taraf için birden DSIC olamaz (Roth, 1982). Tasarımcı, dürüstlüğü hangi tarafa garanti edeceğini seçmek zorundadır. Okul yerleştirmede genellikle öğrenciler teklif veren taraf yapılır; okulların tercihleri ise çoğunlukla yasal öncelik kurallarından gelir ve stratejik olarak değiştirilemez.

4.4.7Tesis yerleşimi: ortalama mı, medyan mı?

Beş köy, A, B, C, D ve E, düz bir yol üzerinde sırasıyla 2, 5, 9, 14 ve 20. kilometrelerde bulunur. Yol üzerinde tek bir tesis, örneğin bir hastane, kurulacaktır. Her köy tesisin kendisine yakın olmasını ister; bir köyün maliyeti tesise uzaklığıdır. Köylerin konumu özel bilgi gibi düşünülür: her köy kendi konumunu (ya da en çok istediği noktayı) bildirir ve tesis bildirimlere göre yerleştirilir.

Bu ortamda tercihler özel bir yapıya sahiptir. Her köyün yol üzerinde tek bir en sevdiği noktası (kendi konumu) vardır ve bu noktadan uzaklaştıkça memnuniyeti azalır. Bu tür tercihlere tek tepeli tercihler (single-peaked preferences) denir: memnuniyet grafiği tek bir tepeye sahiptir. Gibbard–Satterthwaite teoremi bu yapıyı varsaymaz; bu yüzden burada stratejiye dayanıklı ve diktatörlük olmayan bir kural bulunabilir.

İki kural karşılaştırılır. Ortalama mekanizması tesisi bildirimlerin ortalamasına kurar. Medyan mekanizması bildirimleri sıralar ve ortadakini seçer. Beş bildirimde medyan, sıralamadaki üçüncü sayıdır.

Ortalamanın zayıflığı, her bildirimin sonucu doğrudan etkilemesinden gelir. Bir köy bildirimini 5 birim artırırsa ortalama 1 birim artar. Uçtaki bir köy, konumunu abartarak ortalamayı istediği yere kadar çekebilir. Medyan ise yalnızca sıralamaya bakar. Medyanın sağındaki bir köy, bildirimini ne kadar büyütürse büyütsün sağda kalır ve sıralamadaki orta eleman değişmez.

Medyanın bir üstünlüğü daha vardır. Toplam uzaklık medyanda 7 + 4 + 0 + 5 + 11 = 27, ortalamada 8 + 5 + 1 + 4 + 10 = 28'dir. Medyan, toplam uzaklığı en aza indiren noktadır. Nedeni şudur: tesis medyanın sağındaki bir noktadaysa, onu bir birim sola kaydırmak soldaki köylerin her birine bir birim yaklaştırır ve sağdakilerin her birinden bir birim uzaklaştırır. Medyanın sağında, solda kalan köy sayısı sağdakinden fazladır; kaydırma toplamı azaltır. Aynı akıl yürütme soldan da yapılır. Toplam ancak medyanda daha fazla azaltılamaz. Yani medyan hem stratejiye dayanıklıdır hem de toplam maliyet açısından en iyi sonucu verir. Her köy için 0 ile 60 arasındaki bütün bildirimler bilgisayarla denendiğinde medyanda hiçbir yalanın kazandırmadığı görülür.

4.4.8Medyan neden stratejiye dayanıklı?

İspat, köyün medyana göre nerede olduğuna bakan üç durumdan oluşur. Köy i'nin gerçek konumu x_i, diğerleri dürüstken medyan m, köyün yalan bildirimi r olsun. Akıl yürütme diğerlerinin bildirimleri ne olursa olsun geçerlidir; somutlaştırmak için örnekteki köyler kullanılır.

Üç grafikte de uzaklık eğrisi dürüst bildirimin altına hiçbir yerde inmez: düz kısımlar yalanın hiçbir şey değiştirmediği, yükselen kısımlar yalanın zarar verdiği bildirimlerdir.

Aynı fikir oylamaya da taşınır. Seçenekler bir doğru üzerinde sıralanabiliyorsa (örneğin solcu–sağcı ekseninde adaylar ya da bütçe büyüklükleri) ve her seçmenin tek tepeli bir tercihi varsa, medyan seçmenin en sevdiği seçenek her başka seçeneği ikili oylamada yener. Bu sonuç Duncan Black'in medyan seçmen teoremi olarak bilinir. Gibbard–Satterthwaite'in kötü haberinden kaçmanın bir yolu, tercihlerin bu tür bir yapıya sahip olduğu durumları tanımaktır.

4.4.9Seri diktatörlük ve Boston mekanizması

Okul yerleştirmede öğrenciler okulları sıralar ve her okulun sınırlı kontenjanı vardır. Okulların öğrenciler üzerinde öncelik sıraları da olabilir: örneğin okula yakın oturanlar ya da kardeşi okulda olanlar öncelikli olabilir. Bu bölümde iki basit mekanizma karşılaştırılır.

Seri diktatörlük (serial dictatorship). Öğrenciler bir sıraya dizilir. Sırası gelen öğrenci, kalan okullar içinden en sevdiğini alır. Öğrenci, kendinden öncekilerin seçimini etkileyemez; kendi seçimi ise yalnızca kendi tercih listesine bağlıdır. Bu yüzden gerçek tercihleri bildirmek baskın stratejidir: mekanizma DSIC'tir. Sonuç ayrıca Pareto optimaldir: başka hiçbir atama, kimseyi kötüleştirmeden birini daha iyi duruma getiremez. Sıra kurayla belirlenirse mekanizmaya rastgele seri diktatörlük (random serial dictatorship, RSD) denir. Gibbard–Satterthwaite'in diktatörlüğünden farkı, “diktatörün” tek kişi olmaması ve sıranın herkese sırayla seçim hakkı vermesidir.

Boston mekanizması ya da doğrudan kabul (immediate acceptance). Her turda yerleşmemiş öğrenciler tercih listelerindeki sıradaki okula başvurur. Her okul, o turda kendisine başvuran öğrencilere boş koltuklarını öncelik sırasına göre verir. Verilen koltuk sonraki turlarda geri alınmaz. Ertelenmiş kabulle farkı buradadır: kabul geçici değil, kesindir. Bu yüzden ilk tercihini kaybeden bir öğrenci, ikinci tercihine başvurduğunda onu dolmuş bulabilir.

Örnekte üç öğrenci (A, B, C) ve her biri tek koltuklu üç okul (X, Y, Z) vardır. Tercihler A: X ≻ Y ≻ Z, B: X ≻ Y ≻ Z, C: Y ≻ X ≻ Z'dir. Öncelikler X ve Z için A, B, C; Y için B, A, C'dir.

Yalanın nedeni kesin kabuldür. B, X'i zaten alamayacağını tahmin ederse ilk turu “boşa harcamak” istemez; çünkü ilk turda Y'nin koltuğu dolacaktır. Boston mekanizmasında öğrenciler, kazanma şanslarını tahmin edip tercih listelerini buna göre düzenlemek zorunda kalır. Bu, bilgiye ve danışmanlığa erişimi olan ailelere avantaj sağlar; tercihlerini olduğu gibi yazan aileler ise zarar görebilir.

Aynı profilde öğrenci önerili Gale–Shapley dürüst bildirimle A–X, B–Y, C–Z verir. Tur 1'de A ve B X'e, C Y'ye teklif verir; X, A'yı tutar ve B'yi reddeder. B, Y'ye teklif verir; Y'nin önceliğinde B, C'den önde olduğu için B tutulur ve C reddedilir. C, X'te A'ya yenilir ve Z'ye yerleşir. Ertelenmiş kabulde C'nin tur 1'deki Y koltuğu geçici olduğu için B, dürüst kalarak Y'yi alabilir. Abdulkadiroğlu ve Sönmez (2003), Boston mekanizmasında tercihleri olduğu gibi yazmanın öğrenciye zarar verebildiğini gösterdi ve okul seçimine mekanizma tasarımı bakışını getirdi. Boston şehri 2005'te okul yerleştirmesinde öğrenci önerili ertelenmiş kabule geçti.

4.4.10Yurt odası takası: TTC

Bu kez her öğrencinin elinde bir yurt odası vardır ve para kullanılmaz. Öğrenciler başkalarının odalarını kendi odalarıyla birlikte sıralar. Amaç, gönüllü takaslarla herkesin elindekinden daha iyi ya da aynı durumda olduğu bir yeniden dağıtım bulmaktır. Bu probleme ev takası (housing market) problemi denir; Shapley ve Scarf (1974) tarafından tanımlanmıştır. Aşağıdaki algoritmayı David Gale'e atfederler.

En İyi Takas Döngüleri (Top Trading Cycles, TTC) algoritması şöyle çalışır:

1. Kalan her kişi, kalan odalar içinde en sevdiği odanın sahibini gösterir (bir ok çizer). Kendi odasını en çok seviyorsa kendini gösterir.
2. Her kişiden tam bir ok çıktığı için bu çizgede en az bir döngü vardır. Döngüdeki herkes gösterdiği odayı alır ve odasıyla birlikte oyundan çıkar.
3. Kimse kalmayana kadar tekrarlanır.

İkinci adımdaki döngü iddiası basit bir gözleme dayanır. Herhangi bir kişiden başlanıp okları izlenirse sonlu sayıda kişi olduğundan bir noktada daha önce ziyaret edilmiş birine dönülür. Bu dönüş bir döngü oluşturur. Döngü tek kişiden de oluşabilir: kendi odasını gösteren kişi kendi odasında kalır.

TTC'nin üç önemli özelliği vardır:

• DSIC. Dürüst tercih bildirmek her kişi için baskın stratejidir (Roth, 1982). Bir kişi, döngüye girdiği turda kalan odalar içinde en sevdiğini alır. Daha önce çıkanların odaları onun bildirimiyle değiştirilemez; çünkü o döngüler kişinin okundan bağımsız oluştu.
• Pareto optimallik. Hiçbir başka atama, kimseyi kötüleştirmeden birini daha iyi duruma getiremez. İlk turda çıkanlar en sevdikleri odayı aldı; onları iyileştirmek imkânsızdır. Sonraki turda çıkanlar, kalanlar içinde en sevdiklerini aldı; onları iyileştirmek için daha önce çıkan birinin odasını almak gerekir, bu da o kişiyi kötüleştirir.
• Çekirdek. Sonuç çekirdektedir (core): hiçbir grup, kendi odalarını yalnız aralarında takas ederek her üyesi için en az aynı derecede iyi ve en az bir üyesi için daha iyi bir sonuç elde edemez (Roth ve Postlewaite, 1977). Özellikle her kişi en az kendi odası kadar iyi bir oda alır; IR sağlanır.

Örnekte her kişinin olası bütün yalan tercih listeleri bilgisayarla denendiğinde hiçbirinin daha iyi bir oda getirmediği görülür. Aynı kural nöbet ya da vardiya takasına da uyar. Gerçek dünyada en etkileyici uygulaması böbrek nakli eşleştirmeleridir: uyumsuz bir vericisi olan hastalar, vericilerini döngüler hâlinde takas eder (Roth, Sönmez ve Ünver, 2004).

4.4.11Kod izleme: ttc()

TTC'nin Python sürümü her turda okları bir sözlükte toplar, bir kişiden başlayıp okları izleyerek döngüyü bulur ve döngüdekileri çıkarır. Girdi pref sözlüğüdür: pref[i], i'nin oda sahiplerini en iyiden kötüye sıralayan listesidir ve kendi adı da listededir.

def ttc(pref):
  kalan, atama = list(pref), {}
  while kalan:
    g = {i: next(j for j in pref[i]
             if j in kalan) for i in kalan}
    i, yol = kalan[0], []
    while i not in yol:          # okları izle
      yol.append(i); i = g[i]
    dongu = yol[yol.index(i):]
    for k in dongu:              # takas
      atama[k] = g[k]; kalan.remove(k)
  return atama

Kodun parçaları şunlardır:

• kalan henüz takas etmemiş kişilerin listesi, atama ise sonuç sözlüğüdür: atama[k], k'nin aldığı odanın sahibidir.
• g sözlüğü bu turun oklarıdır: her kalan kişi i için, pref[i] listesinde kalanlar arasında bulunan ilk kişi. next(...), koşulu sağlayan ilk elemanı döndürür.
• i = kalan[0] ile ilk kalan kişiden başlanır. İç döngü, i daha önce yola eklenmemişken onu yola ekler ve okunu izler (i = g[i]). Daha önce görülmüş birine ulaşınca durur.
• dongu = yol[yol.index(i):], yolun döngü kısmıdır: tekrar edilen kişinin ilk göründüğü yerden sona kadar. Yolun başındaki kişiler döngüye bağlanan ama döngüde olmayan kişiler olabilir; bu dilimleme onları dışarıda bırakır.
• Döngüdeki her kişi gösterdiği odayı alır ve kalan'dan çıkarılır.

Bu örnekte yol her turda doğrudan döngüyle başladı. Başka bir girdide yol, döngüde olmayan birinden başlayabilir. Örneğin tur 1'de izlemeye D'den başlansaydı yol D → C → B → A → C olurdu; C ikinci kez görülünce durulur ve yol.index('C') ile döngü [C, B, A] olarak ayrılır. D döngüde değildir ve kalır. Her turda en az bir kişi çıktığı için en fazla n tur yapılır; her turda okları kurmak en fazla n² iş gerektirir. Algoritma bu basit sürümüyle O(n³) sürede biter.

4.5Bayesçi oyunlar

Şimdiye kadar özel bilgi tasarımcı ile oyuncular arasındaydı: tasarımcı tipleri bilmiyordu. Oysa oyuncular da çoğu zaman birbirlerinin tipini bilmez. Bir açık artırmada teklifçi rakiplerinin değerlerini, bir pazarlıkta alıcı satıcının maliyetini bilmez. Bu tür eksik bilgili durumları incelemek için oyun kuramı Bayesçi oyunları kullanır. Bayesçi oyunlar BIC kavramının (4.2.4) da dayandığı çerçevedir.

4.5.1Eksik bilgi ve Bayesçi oyun

Eksik bilgili bir oyunu çözmek ilk bakışta imkânsız görünür: oyuncu, rakibinin hangi oyunu oynadığını bile bilmez. John Harsanyi (1967–68) bu sorunu zarif bir fikirle çözdü. Oyuna, oyuncuların dışında bir “şans” ya da “Doğa” hamlesi eklenir. Oyunun başında Doğa her oyuncunun tipini bir olasılık dağılımına göre seçer. Her oyuncu yalnızca kendi tipini görür. Dağılımın kendisi ise herkesçe bilinir. Böylece “bilinmeyen oyun” sorunu, “bilinen ama içinde şans olan bir oyun” sorununa dönüşür. Bu yönteme Harsanyi dönüşümü denir.

Bayesçi oyunda strateji kavramı değişir. Oyuncu kendi tipini öğrendikten sonra karar verir; ama analizi yapan kişi (ve rakipler) oyuncunun tipini bilmez. Bu yüzden strateji, her tip için hangi eylemin seçileceğini söyleyen bir kuraldır. Örneğin iki tipli bir oyuncunun stratejisi “B tipindeysem K, Ç tipindeysem M” gibi bir eşlemedir. Rakip bu kuralı bilir, ama hangi satırın uygulanacağını bilmez.

Tanım, Nash dengesinin doğal bir genişlemesidir. Nash dengesinde “kimse tek başına sapmak istemez” denir. Bayes–Nash dengesinde de aynısı söylenir, yalnızca sapmanın faydası beklenen değerle ölçülür ve her tip ayrı ayrı denetlenir. Bir oyuncunun iki tipi varsa, iki tipin her biri kendi en iyi tepkisini oynamalıdır.

Bölümün örneği bir buluşma oyunudur. P1 akşam konsere (K) ya da maça (M) gidecektir ve konseri tercih eder. P2 iki tipten biridir: B tipi P1 ile buluşmak ister, Ç tipi P1'den kaçınmak ister. P1, P2'nin tipini bilmez; iki tipin olasılığı da 1/2'dir. P2 kendi tipini bilir.

Şekil 4.26 oyunun ağacını gösterir. Kesikli elips, P1'in iki düğümü birbirinden ayıramadığını anlatır: P1, hangi tipteki P2 ile oynadığını bilmeden aynı eylemi seçmek zorundadır. Buna P1'in bilgi kümesi denir. P2 ise her dalda ayrı karar verir; bu yüzden tipe bağlı bir stratejisi olabilir.

Mekanizma tasarımıyla bağlantı açıklama ilkesinin Bayesçi sürümüdür. Bayes–Nash dengesinde uygulanabilen her sonuç, dürüst bildirimin bir Bayes–Nash dengesi olduğu, yani BIC olan bir doğrudan mekanizmayla da uygulanabilir. İspat 4.2.3'tekiyle aynıdır; tek fark, “sapma kârlı değil” cümlesinin beklenen kazanç için kurulmasıdır.

4.5.2Bayes–Nash dengesini bulmak

Oyunun kazançları iki matrisle verilir: biri P2 B tipindeyken, öteki Ç tipindeyken. Hücrelerde (P1 kazancı, P2 kazancı) yazılıdır. P1'in kazançları iki matriste aynıdır: P1 her durumda konserde ya da maçta P2 ile buluşmak ister ve konseri tercih eder (K'de buluşma 2, M'de buluşma 1, buluşamama 0). Değişen, P2'nin kazançlarıdır.

Saf stratejileri saymak, aramanın ne kadar büyük olduğunu gösterir. P1'in iki saf stratejisi vardır: K ya da M. P2'nin her tipi K ya da M seçebildiği için P2'nin 2 × 2 = 4 saf stratejisi vardır: (B→K, Ç→K), (B→K, Ç→M), (B→M, Ç→K), (B→M, Ç→M). Toplam 2 × 4 = 8 saf strateji profili vardır. Hepsini tek tek denetlemek yerine daha kısa bir yol izlenir: P1'in her seçimi için P2'nin her tipinin en iyi tepkisi bulunur, sonra P1'in bu tepkilere karşı sapıp sapmadığına bakılır.

Yorum ilginçtir. P1 M'ye giderse B tipi onu izler ve Ç tipi konsere kaçar. Ama Ç tipinin kaçtığı konser, P1'in daha çok sevdiği yerdir. P1, buluşma şansı aynıyken (iki adayda da yarı yarıya) konseri tercih ettiği için K'de kalmak ister. Dengede P2'nin davranışı tipini ele verir: konserde görülen P2 B tipindedir, maçta görülen Ç tipindedir.

4.5.3Olasılık değişince denge

Ön olasılık değişirse denge de değişebilir. P2'nin B tipinde olma olasılığı genel bir π sayısı olsun; Ç tipinin olasılığı 1 − π'dir. P2'nin en iyi tepkileri π'ye bağlı değildir, çünkü P2 kendi tipini bilir. Değişen yalnızca P1'in beklenen kazançlarıdır.

• Aday 1 (P1 = K; B→K, Ç→M). P1 K'de kalırsa π · 2 + (1 − π) · 0 = 2π, M'ye geçerse π · 0 + (1 − π) · 1 = 1 − π alır. Denge için 2π ≥ 1 − π, yani π ≥ 1/3 gerekir.
• Aday 2 (P1 = M; B→M, Ç→K). P1 M'de kalırsa π · 1 = π, K'ye geçerse (1 − π) · 2 alır. Denge için π ≥ 2(1 − π), yani π ≥ 2/3 gerekir.

π = 1/2, ikinci satıra düşer; bu yüzden örnekte tek bir saf denge bulundu. B tipi çok az olasıysa (π < 1/3), P1 nereye giderse gitsin P2'nin çoğunluğu (Ç tipleri) ondan kaçar ve P1 her seferinde öbür yere geçmek ister. Bu durumda saf denge yoktur; Nash'in varlık teoremi gereği karışık stratejili bir denge vardır. B tipi çok olasıysa (π ≥ 2/3) oyun neredeyse bir koordinasyon oyununa döner ve iki saf denge ortaya çıkar.

Eşik değerleri π = 1/3 ve π = 2/3'te P1 iki eylemi arasında kayıtsızdır. Örneğin π = 1/3'te aday 1'de K de M de 2/3 verir. Eşitlik durumunda P1'in K'de kalması en iyi tepkidir; bu yüzden eşitsizlikler “≥” ile yazılmıştır.

4.5.4Bayesçi bakışla mekanizmalar

Bayesçi oyunlar mekanizma tasarımında DSIC'in yetmediği ya da fazla katı kaldığı yerlerde kullanılır. Dört örnek bu bakışın neden gerekli olduğunu gösterir.

Birinci fiyat açık artırması. Birinci fiyatta dürüst teklif, kazanınca faydayı 0 bırakır (4.2.4). Bu yüzden dengede herkes değerinin altında teklif verir. Ne kadar altında? Cevap rakiplerin değerleri hakkındaki inanca bağlıdır; denge bu yüzden Bayesçidir. Standart bir örnekte iki teklifçinin değerleri 0 ile 1 arasında tekdüze (her değer eşit olasılıkla) dağılır. Rakip değerinin yarısını teklif ederse, değeri v olan teklifçinin b teklifiyle kazanma olasılığı, rakibin değerinin 2b'den küçük olma olasılığıdır, yani 2b'dir (b ≤ 1/2 için). Beklenen fayda (v − b) · 2b'dir. Bu ifade b = v/2'de en büyük olur. Yani “değerinin yarısını teklif et” stratejisi iki oyuncu için birbirine en iyi tepkidir: bir Bayes–Nash dengesidir.

DSIC mi, BIC mi? DSIC, oyuncuların inançlarından bağımsızdır ve sağlamdır: tip dağılımı yanlış tahmin edilse bile dürüstlük en iyisi kalır. BIC daha zayıftır, ama daha fazla hedefe izin verir. Örneğin VCG kamu malı probleminde tam bütçe dengesini sağlayamaz; oysa BIC düzeyinde hem verimli hem tam bütçe dengeli bir kamu malı mekanizması vardır (d'Aspremont ve Gérard-Varet, 1979; Arrow, 1979). Bu mekanizmada ödemeler, her oyuncunun bildiriminin diğerlerine beklenen etkisine göre ayarlanır ve toplanan para oyunculara geri dağıtılır.

En yüksek gelir. Satıcının beklenen gelirini maksimize eden açık artırma da Bayesçi bir sorudur; çünkü “beklenen gelir” alıcıların değer dağılımına bağlıdır. Myerson (1981) bu soruyu çözdü. Standart koşullarda cevap, rezerv fiyatlı bir açık artırmadır: satıcı bir en düşük fiyat belirler; bu fiyatın altında satış yapılmaz. Rezerv fiyat bazen hiç satış olmamasına yol açar, yani verimliliği bozar; ama karşılığında beklenen geliri artırır. Verimlilik ile gelir arasındaki bu ödünleşim, açık artırma tasarımının temel konularından biridir.

Poker ve blöf. Pokerde rakibin eli (tipi) gizlidir. Blöf, yani zayıf elle büyük bahis, karışık bir Bayesçi stratejinin parçasıdır: güçlü eller hep büyük bahisle oynanırsa bahis büyüklüğü eli ele verir.

4.6Değerlendirme

Bölümün son kısmı, mekanizma tasarımının varsayımlarını ve sınırlarını tartışır, bölümde görülen mekanizmaları bir tabloda toplar ve öğrenilenleri birkaç kısa problemle sınar.

4.6.1Davranış, adalet ve etik

İnsanlar her zaman teşviklere göre mi davranır? Kuram, oyuncuların faydalarını maksimize ettiğini varsayar. Gerçekte duygular, ahlak, alışkanlık ve adalet duygusu da kararları etkiler. Ültimatom oyununda düşük tekliflerin reddedilmesi (4.2.5) bunun en bilinen örneğidir. Teşvikler güçlüdür ama tek belirleyici değildir. Bu gözlem mekanizma tasarımını geçersiz kılmaz; aksine iki uyarı getirir. Birincisi, fayda fonksiyonu insanların gerçekten neyi önemsediğini yansıtmalıdır. İkincisi, kurallar basit ve anlaşılır olmalıdır. Örneğin İngiliz açık artırması Vickrey ile aynı sonucu verir, ama dürüst davranışın neden en iyisi olduğu orada çok daha kolay görülür.

Mekanizma tasarımında etik sorunlar. İyi kurallar bile kötü sonuçlara yol açabilir:

• Manipülasyon ve bilgi saklama. DSIC olmayan kurallarda bilgiye ve danışmanlığa erişimi olanlar avantaj sağlar. Boston mekanizmasında stratejik liste yazmayı bilen aileler, tercihlerini olduğu gibi yazan ailelerin önüne geçebilir.
• Güçlü oyuncuların avantajı. Danışıklılık ve sahte kimlikler, organize gruplara kuralın öngörmediği güç verir.
• Adil olmayan gelir dağılımı. Verimlilik, değerlerin toplamını en büyük yapar; ama değer, ödeme gücüne bağlıdır. Zengin bir oyuncunun “yüksek değeri” çoğu zaman yalnızca daha çok parası olduğunu gösterir.
• Ödeme gücü olmayanların dışlanması. Para kullanan mekanizmalar, ödeme yapamayanları baştan dışarıda bırakır. Okul yerleştirme ve organ nakli gibi alanlarda paranın kullanılmamasının nedeni budur.

Bu yüzden etik sınırlar toplum ve kurumlarca belirlenmelidir. İyi bir mekanizma yalnızca verimli değil, adil ve etik de olmalıdır. Mekanizma tasarımı bu tartışmada bir araçtır: hangi hedefin hangi kurallarla ve hangi bedelle sağlanabileceğini açıkça gösterir; hangi hedefin seçileceğine ise toplum karar verir.

4.6.2Bölümün mekanizmaları bir arada

Bölümde görülen mekanizmalar Tablo 4.17'de karşılaştırılır. Tablo iki ayrımı birlikte gösterir: paranın kullanılıp kullanılmadığı ve teşvik özelliğinin hangi düzeyde sağlandığı.

Tablonun ana dersi şudur: açıklama ilkesi sayesinde doğrudan ve dürüst bildirimli mekanizmalara odaklanmak yeterlidir; ama IC, IR, verimlilik ve bütçe dengesi her zaman birlikte sağlanamaz. Para varsa VCG verimliliği ve DSIC'i sağlar, karşılığında bütçe dengesinden vazgeçer. Para yoksa Gibbard–Satterthwaite genel bir çözüme izin vermez; çözüm, tercihlerin yapısından (medyan) ya da hedefin değiştirilmesinden (kararlılık, takas) gelir.

4.6.3Örnek problemler

Aşağıdaki beş problem, bölümün hesap yöntemlerini kısa durumlarda bir araya getirir.

4.7Özet

• Mekanizma tasarımı, oyun kuramının ters yönüdür: istenen sonuç verilir, bu sonucu dengede doğuracak kurallar (tahsis ve ödeme) aranır. Zorluk, oyuncuların tiplerinin (değer, tercih, maliyet) tasarımcıdan gizli olmasıdır.
• Sosyal seçim fonksiyonu f, her tip profiline istenen sonucu atar. Doğrudan mekanizmada oyuncular tiplerini bildirir; mekanizma sonucu x(b) ve ödemeleri p(b) hesaplar; fayda yarı doğrusaldır: u_i = v_i(x) − p_i.
• Açıklama ilkesi: dolaylı bir mekanizmada dengede uygulanan sonuç, dürüst bildirimin denge olduğu bir doğrudan mekanizmayla da uygulanabilir. Denge kavramı baskın stratejiyse DSIC, Bayes–Nash ise BIC elde edilir; DSIC ⇒ BIC.
• IR, katılımın dışarıda kalmaktan kötü olmamasıdır. IC ile IR farklı koşullardır. Ültimatom oyununda kuram (10, 0) ve (9, 1) dengelerini verir; deneylerde ise düşük teklifler reddedilir: fayda modeli adaleti de içermelidir.
• Orantılı maliyet paylaşımı IC değildir: park örneğinde Cem 5 bildirerek faydasını 4'ten 15'e çıkarır; herkes yarısını bildirirse park yapılmaz. Myerson–Satterthwaite: iki taraflı ticarette verimlilik, BIC, IR ve bütçe dengesi birlikte sağlanamaz.
• Uygulama kuramı: dürüstlük tek denge olmayabilir; Vickrey'de (0, 100) teklifleri, nesneyi değeri düşük olana veren bir Nash dengesidir.
• Myerson lemması: tek parametreli ortamda tahsis DSIC'te kullanılabilir ⇔ monoton. Ödeme tek biçimde belirlenir: p = b · x(b) − ∫₀^b x(z) dz; 0/1 tahsiste kritik teklif.
• VCG sosyal refahı en yüksek sonucu seçer ve her oyuncuya dışsallığını ödetir: p_i = (i olmasaydı diğerlerinin en iyi refahı) − (i varken diğerlerinin refahı). DSIC, verimli ve (Clarke pivotuyla) IR'dir; tam bütçe dengesi yoktur. Kamu projesi örneğinde Spor salonu seçilir, ödemeler 0, 5, 20'dir. Tek nesnede VCG = Vickrey.
• Parasız tasarımda Gibbard–Satterthwaite genel tercihlerde yalnızca diktatörlüğe izin verir. Gale–Shapley her zaman kararlı eşleştirme bulur (O(n²)), teklif verenler için en iyi ve DSIC'tir; teklif alan taraf yalanla kazanabilir.
• Medyan tek tepeli tercihlerde stratejiye dayanıklıdır ve toplam uzaklığı en aza indirir; ortalama manipüle edilebilir. Boston mekanizması DSIC değildir; seri diktatörlük ve TTC DSIC'tir. TTC Pareto optimal ve çekirdektedir.
• Bayesçi oyunda Doğa tipleri ortak ön olasılıkla seçer; strateji tipten eyleme bir kuraldır; Bayes–Nash dengesinde her tip beklenen kazancını maksimize eder. Buluşma oyununda P(B) = 1/2 için tek saf denge (K; B→K, Ç→M)'dir.

4.8Kavram listesi

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

• mekanizma tasarımı mechanism design
• tip type
• sosyal seçim fonksiyonu social choice function
• doğrudan mekanizma direct mechanism
• yarı doğrusal fayda quasi-linear utility
• açıklama ilkesi revelation principle
• teşvik uyumluluğu incentive compatibility
• baskın stratejide teşvik uyumlu (DSIC) dominant-strategy IC
• Bayesçi teşvik uyumlu (BIC) Bayesian IC
• bireysel rasyonellik individual rationality
• beleşçi free-rider
• sosyal refah social welfare
• bütçe dengesi budget balance
• Myerson–Satterthwaite teoremi Myerson–Satterthwaite theorem
• uygulama kuramı implementation theory
• Myerson lemması Myerson's lemma
• kritik teklif critical bid
• VCG mekanizması VCG mechanism
• Clarke pivot kuralı Clarke pivot rule
• dışsallık externality
• Vickrey açık artırması Vickrey auction
• stratejiye dayanıklı strategy-proof
• Gibbard–Satterthwaite teoremi Gibbard–Satterthwaite theorem
• kararlı eşleştirme stable matching
• engelleyici çift blocking pair
• Gale–Shapley (ertelenmiş kabul) algoritması deferred acceptance
• tek tepeli tercihler single-peaked preferences
• medyan mekanizması median mechanism
• seri diktatörlük serial dictatorship
• Boston mekanizması Boston mechanism
• En İyi Takas Döngüleri (TTC) Top Trading Cycles
• çekirdek core
• Pareto optimal Pareto optimal
• Bayesçi oyun Bayesian game
• ortak ön olasılık common prior
• Bayes–Nash dengesi Bayes–Nash equilibrium

4.9Kendini Dene

1. Bir oyun alanının maliyeti 40 bin TL'dir. Değerler Ayşe 20, Bora 16, Cem 14'tür. Kural orantılı maliyet paylaşımıdır: bildirimlerin toplamı en az 40 ise alan yapılır ve maliyet bildirimlerle orantılı paylaşılır. Herkes dürüstken ödemeler ve faydalar nedir? Bora ve Cem dürüstken Ayşe'nin en kârlı bildirimi nedir?

   Cevap

   Toplam 50 ≥ 40. Ödemeler 40 · 20/50 = 16, 40 · 16/50 = 12,8, 40 · 14/50 = 11,2; faydalar 4; 3,2; 2,8 (IR sağlanır). Bora ve Cem'in toplamı 30'dur; alanın yapılması için Ayşe en az 10 bildirmelidir. Ayşe 10 bildirirse toplam 40 olur ve 40 · 10/40 = 10 öder; faydası 20 − 10 = 10 > 4. Kural IC değildir.

2. Üç sakin, üç projeye (Park, Kütüphane, Spor salonu) şu değerleri bildiriyor: Ayşe (20, 5, 10), Bora (0, 25, 15), Cem (15, 10, 30). VCG hangi projeyi seçer? Her sakinin ödemesi ve faydası nedir?

   Cevap

   Toplamlar Park 35, Kütüphane 40, Spor 55: Spor salonu seçilir. Ayşe olmadan toplamlar 15, 35, 45; en iyisi 45, Spor'da diğerleri 45 alır: ödeme 0. Bora olmadan 35, 15, 40; en iyisi 40, Spor'da 40: ödeme 0. Cem olmadan 20, 30, 25; en iyisi Kütüphane (30), Spor'da diğerleri 10 + 15 = 25 alır: ödeme 30 − 25 = 5. Faydalar Ayşe 10 − 0 = 10, Bora 15 − 0 = 15, Cem 30 − 5 = 25. Bütçe fazlası 5'tir.

3. Tek nesne için dört teklifçinin değerleri 40, 65, 50 ve 30'dur. Vickrey açık artırmasında kim kazanır, kaç öder? 65 ve 50 değerli teklifçiler anlaşır ve 50'lik teklifçi 0 teklif ederse sonuç nasıl değişir?

   Cevap

   Dürüst tekliflerde 65 kazanır ve ikinci en yüksek teklif olan 50'yi öder; faydası 15'tir. Anlaşmada teklifler 40, 65, 0, 30 olur. 65 yine kazanır ama ikinci en yüksek teklif 40'tır; 40 öder ve faydası 25'e çıkar. Grup 10 birim kazanır, satıcının geliri 50'den 40'a düşer. Tek başına sapma kazandırmasa da danışıklılık kazandırır.

4. Tek parametreli bir ortamda, diğerlerinin teklifleri sabitken bir oyuncunun tahsisi şöyledir: teklif 3'ün altında 0, 3 ile 6 arasında 1/4, 6 ve üstünde 1. Myerson ödemesine göre p(4) ve p(8) nedir? Değeri 8 olan oyuncu dürüst teklif verirse faydası kaçtır?

   Cevap

   Tahsis monotondur. ∫₀⁴ x = ¼ · 1 = 0,25, p(4) = 4 · ¼ − 0,25 = 0,75 (kontrol: sıçrama × eşik = ¼ · 3). ∫₀⁸ x = ¼ · 3 + 1 · 2 = 2,75, p(8) = 8 − 2,75 = 5,25 (kontrol: ¼ · 3 + ¾ · 6 = 0,75 + 4,5 = 5,25). Fayda 8 − 5,25 = 2,75, yani eğrinin altındaki alandır.

5. Öğrenci tercihleri A: Y ≻ X ≻ Z, B: X ≻ Y ≻ Z, C: Y ≻ Z ≻ X; proje tercihleri X: A ≻ B ≻ C, Y: B ≻ C ≻ A, Z: C ≻ A ≻ B. Öğrenciler teklif verdiğinde Gale–Shapley kaç teklif yapar ve sonuç nedir? Projeler teklif verseydi?

   Cevap

   Öğrenciler teklif verir: A→Y, B→X, C→Y; Y, C'yi tutar ve A'yı reddeder (C ≻ A). A→X; X, A'yı tutar ve B'yi reddeder. B→Y; Y, B'yi tutar ve C'yi reddeder. C→Z: kabul. 6 teklifle sonuç A–X, B–Y, C–Z. Projeler teklif verirse X→A, Y→B, Z→C ve üçü de kabul edilir: 3 teklifle aynı sonuç. Bu eşleştirme tek kararlı eşleştirmedir. Her öğrenci ikinci tercihini, her proje ilk tercihini almıştır.

6. Beş köy 1, 4, 6, 11 ve 18. km'dedir. Ortalama ve medyan kuralında tesis nereye kurulur ve toplam uzaklık kaçtır? Ortalama kuralında 18. km'deki köy tesisi tam kendine çekmek için ne bildirmelidir?

   Cevap

   Medyan 6: toplam 5 + 2 + 0 + 5 + 12 = 24. Ortalama 40/5 = 8: toplam 7 + 4 + 2 + 3 + 10 = 26. Ortalamanın 18 olması için (1 + 4 + 6 + 11 + x)/5 = 18, yani x = 90 − 22 = 68. Medyanda 68 bildirimi medyanı 6'da bırakır.

7. Dört öğrencinin oda tercihleri: A: B ≻ C ≻ A, B: C ≻ A ≻ B, C: B ≻ D ≻ C, D: A ≻ B ≻ D. TTC'yi uygulayın. Kim hangi odayı alır?

   Cevap

   Tur 1 okları: A→B, B→C, C→B, D→A. A'dan başlanınca yol A → B → C → B olur; döngü B ↔ C'dir. B, C'nin; C, B'nin odasını alır. Tur 2: A'nın ilk iki tercihi gitti, A kendini gösterir; D'nin ilk iki tercihinden A kalmıştır, D→A. Döngü A → A: A kendi odasında kalır. Tur 3: D kendini gösterir ve kendi odasında kalır. Sonuç B ← C, C ← B, A ← A, D ← D.

8. Buluşma oyununda B tipinin olasılığı 2/5 olsun. (K; B→K, Ç→M) ve (M; B→M, Ç→K) Bayes–Nash dengesi midir?

   Cevap

   Birinci aday: K → 2/5 · 2 = 4/5, M → 3/5 · 1 = 3/5; K daha iyi, denge ✓. İkinci aday: K → 3/5 · 2 = 6/5, M → 2/5 · 1 = 2/5; P1 K'ye sapar, denge değil. 1/3 ≤ 2/5 < 2/3 olduğu için tek saf denge vardır.

4.10İleri okuma

• T. Roughgarden, Twenty Lectures on Algorithmic Game Theory (2016), Ders 2–4, 7 ve 10: Myerson lemmasının tam ispatını, VCG'yi, böbrek takasını ve kararlı eşleştirmeyi bilgisayar bilimi bakışıyla kısa derslerle anlatır.
• N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory (2007), Bölüm 9 ve 10: paralı mekanizma tasarımını ve para olmadan tasarımı (medyan, ev takası, kararlı eşleştirme) ayrıntılı ve ispatlarıyla sunar.
• D. Easley ve J. Kleinberg, Networks, Crowds, and Markets (2010), Bölüm 10 ve 15: eşleştirme piyasalarını ve VCG'nin sponsorlu arama reklamlarıyla ilişkisini az matematikle, sezgisel örneklerle açıklar.
• A. E. Roth, Who Gets What — and Why (2015): okul yerleştirme, tıp ihtisası ve böbrek takası gibi gerçek piyasaların nasıl tasarlandığını, bu tasarımları yapan araştırmacının kendi anlatımıyla aktarır.

4.11Kaynaklar

1. A. Abdulkadiroğlu, T. Sönmez, “School choice: A mechanism design approach”, American Economic Review 93(3), 2003.
2. K. J. Arrow, “The property rights doctrine and demand revelation under incomplete information”, M. Boskin (ed.), Economics and Human Welfare, Academic Press, 1979.
3. D. Black, “On the rationale of group decision-making”, Journal of Political Economy 56(1), 1948.
4. C. F. Camerer, Behavioral Game Theory, Princeton University Press, 2003.
5. E. H. Clarke, “Multipart pricing of public goods”, Public Choice 11, 1971.
6. C. d'Aspremont, L.-A. Gérard-Varet, “Incentives and incomplete information”, Journal of Public Economics 11(1), 1979.
7. D. Easley, J. Kleinberg, Networks, Crowds, and Markets, Cambridge, 2010 (Bölüm 10 ve 15).
8. D. Gale, L. S. Shapley, “College admissions and the stability of marriage”, American Mathematical Monthly 69(1), 1962.
9. A. Gibbard, “Manipulation of voting schemes: A general result”, Econometrica 41(4), 1973.
10. T. Groves, “Incentives in teams”, Econometrica 41(4), 1973.
11. W. Güth, R. Schmittberger, B. Schwarze, “An experimental analysis of ultimatum bargaining”, Journal of Economic Behavior and Organization 3(4), 1982.
12. J. C. Harsanyi, “Games with incomplete information played by ‘Bayesian’ players, I–III”, Management Science 14, 1967–68.
13. A. R. Karlin, Y. Peres, Game Theory, Alive, AMS, 2017 (mekanizma tasarımı, kararlı eşleştirme).
14. E. Maskin, “Nash equilibrium and welfare optimality”, Review of Economic Studies 66(1), 1999.
15. H. Moulin, “On strategy-proofness and single peakedness”, Public Choice 35(4), 1980.
16. R. B. Myerson, “Optimal auction design”, Mathematics of Operations Research 6(1), 1981.
17. R. B. Myerson, M. A. Satterthwaite, “Efficient mechanisms for bilateral trading”, Journal of Economic Theory 29(2), 1983.
18. N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory, Cambridge University Press, 2007.
19. M. J. Osborne, An Introduction to Game Theory, Oxford University Press, 2004 (Bayesçi oyunlar).
20. A. E. Roth, “Incentive compatibility in a market with indivisible goods”, Economics Letters 9(2), 1982.
21. A. E. Roth, “The economics of matching: Stability and incentives”, Mathematics of Operations Research 7(4), 1982.
22. A. E. Roth, Who Gets What — and Why, Houghton Mifflin Harcourt, 2015.
23. A. E. Roth, A. Postlewaite, “Weak versus strong domination in a market with indivisible goods”, Journal of Mathematical Economics 4(2), 1977.
24. A. E. Roth, T. Sönmez, M. U. Ünver, “Kidney exchange”, Quarterly Journal of Economics 119(2), 2004.
25. T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
26. M. A. Satterthwaite, “Strategy-proofness and Arrow's conditions”, Journal of Economic Theory 10(2), 1975.
27. L. Shapley, H. Scarf, “On cores and indivisibility”, Journal of Mathematical Economics 1(1), 1974.
28. Y. Shoham, K. Leyton-Brown, Multiagent Systems, Cambridge University Press, 2009.
29. W. Vickrey, “Counterspeculation, auctions, and competitive sealed tenders”, Journal of Finance 16(1), 1961.

Ders sayfaları: Roughgarden CS364A · Shah CSC304 · Procaccia 15-896 · Dinitz AGT · © Sercan Külcü. Tüm hakları saklıdır.