Bölüm 7: Oylama

7.1Sosyal seçim

Oyun kuramındaki pek çok oyunda her oyuncu kendi kazancını büyütmeye çalışıyordu ve sonuç, oyuncuların seçimlerinin bir araya gelmesiyle oluşuyordu. Oylamada da durum benzerdir: her seçmen kendi tercihini bildirir, bir kural bu bildirimleri toplar ve herkes için geçerli tek bir sonuç üretir. Fark, sonucun bir “kural” tarafından açıkça belirlenmesidir. Bu bölümün sorusu şudur: bu kural nasıl seçilmeli ve seçilen kuralın hangi iyi ve kötü özellikleri vardır?

7.1.1Bir oyunla başlangıç: Condorcet paradoksu

Bölüm, sınıfta oynanan küçük bir oyunla açılır. Üç seçmen A, B ve C adlı üç adayı kendi zevklerine göre sıralar. Ardından her aday çifti ikili çoğunlukla karşılaştırılır: A ile B karşılaştırılırken her seçmen bu ikisinden kendi sıralamasında hangisi daha yukarıdaysa ona oy verir. Bütün rakiplerini bu şekilde yenen adaya Condorcet kazananı (Condorcet winner) denir. Ad, bu tür karşılaştırmaları 18. yüzyılda inceleyen Fransız matematikçi Marquis de Condorcet'den gelir.

Oyunun ilk seviyesinde seçmenlerin sıralamaları şöyledir: birinci seçmen A ≻ B ≻ C, ikinci seçmen B ≻ C ≻ A, üçüncü seçmen C ≻ A ≻ B. Burada “≻” işareti “daha çok tercih edilir” anlamına gelir; A ≻ B ≻ C, “A'yı B'ye, B'yi de C'ye tercih ederim” diye okunur. Şekil 7.1'de üç sıralama sütunlar hâlinde gösterilmiştir; üstteki aday daha çok tercih edilir. Sağdaki üçgende her kenar bir ikili karşılaştırmadır ve soru işareti, o karşılaştırmayı kimin kazandığının henüz bilinmediğini gösterir.

Oyun iki merak sorusu sorar. Birincisi: her seçmenin sıralaması kendi içinde tutarlıysa, topluluğun tercihi de tutarlı olmak zorunda mıdır? İkincisi: oylamaların sırasını belirleme yetkisi bir kişide olsaydı, o kişi istediği adayı kazandırabilir miydi? İki sorunun cevabı da bu bölümün ilk büyük sonucudur ve 7.3'te ayrıntılı olarak hesaplanır. Kısaca: topluluğun tercihi tutarsız olabilir ve oylama sırasını belirleyen kişi sonucu seçebilir. Bu iki gözlem, “halkın iradesi” denen şeyin her zaman kendiliğinden belli olmadığını gösterir.

7.1.2Sosyal seçim nedir?

Sosyal seçim (social choice), bireysel tercihleri toplu bir karara ya da toplumsal bir sıralamaya dönüştüren kuralları inceleyen alandır. Alanın amacı tek bir evrensel adalet tanımı bulmak değildir. Amaç, kuralların hangi ölçütleri sağladığını ve hangi ödünleşimleri yarattığını anlamaktır. Bir kural bazı iyi özellikleri sağlarken başka iyi özellikleri bozar; hangi özelliğin daha önemli olduğu ise kararın bağlamına göre değişir.

Uygulama alanları geniştir: genel seçimler, komite ve kulüp kararları, bir sınıfın hangi etkinliğe gideceğinin seçilmesi, ortak bir kaynağın nasıl kullanılacağı ve çevrimiçi anketler. Bilgisayar biliminde de aynı sorular karşımıza çıkar. Birden çok arama motorunun sonuç listelerini tek listede birleştirmek, birden çok sınıflandırıcının kararlarını oylatmak ya da kullanıcı puanlarından bir sıralama üretmek, hep bireysel sıralamalardan toplu bir sıralama çıkarma sorunlarıdır.

Sosyal seçimin temel nesnesi tercihtir. Bir seçmenin tercihi, adayları en çok sevdiğinden en az sevdiğine doğru dizen bir sıralamadır. Bu sıralamanın iki özelliği olduğu varsayılır.

Tamlık, seçmenin her iki adayı karşılaştırabildiğini söyler; “bilmiyorum” cevabı yoktur. Geçişlilik ise sıralamanın kendi içinde çelişkisiz olmasıdır. A'yı B'ye, B'yi de C'ye tercih eden biri C'yi A'ya tercih ederse, bu kişiye A, B ve C arasında hangisini seçeceği sorulduğunda tutarlı bir cevap veremez: hangisini seçerse seçsin daha çok sevdiği başka bir aday vardır. Bu bölümde her seçmenin tercihinin tam ve geçişli olduğu varsayılır. Bölümün şaşırtıcı sonuçlarından biri, bu varsayım bireyler için sağlansa bile topluluk için sağlanmayabileceğidir.

Pusula ile gerçek tercih aynı şey değildir. Seçmen gerçekte A ≻ B ≻ C düşünürken pusulaya B ≻ A ≻ C yazabilir. Oyun kuramı açısından pusula, seçmenin stratejisidir: seçmen pusulasını, kuralın sonucunu kendi gerçek tercihine göre en iyi yapacak şekilde seçebilir. Bu bakış açısı 7.4'teki stratejik oy konusunun temelidir.

Bir oylama kuralı tercih profilini girdi olarak alır ve bir sonuç üretir. Sonucun türüne göre iki tür kural ayrılır.

Şekil 7.2 bu yapıyı özetler. Solda girdi olan tercih profili vardır; her sütun bir seçmen grubunun sıralamasıdır. Ortada profile sonuç atayan kural f durur. Sağda iki tür çıktı görülür: üstte tek bir kazanan (SCF), altta tam bir toplumsal sıralama (SWF). Şekildeki örnekte kural Borda sayımıdır; kazanan B, sıralama ise B ≻ D ≻ A ≻ C'dir. Bu sayıların nereden geldiği 7.2.3'te adım adım hesaplanır.

Şeklin altındaki “oy pusulası = strateji” notu bu bölümün mekanizma tasarımıyla bağını gösterir. Mekanizma tasarımında bir tasarımcı, oyuncuların özel bilgilerini (tercihlerini) bildirmesini ister ve bu bildirimlere göre bir sonuç seçer; çoğu zaman oyunculardan ödeme de alır ya da onlara ödeme yapar. Oylama, mekanizma tasarımının parasız özel hâlidir: ödeme yoktur, yalnızca sıralamalar vardır. Para olmadığı için bir seçmenin yalan söylemesini “cezalandırmak” ya da doğruyu söylemesini “ödüllendirmek” mümkün değildir. Bu kısıtın sonuçları 7.5.4'teki Gibbard–Satterthwaite teoreminde açıkça görülür.

7.1.3Örnek tercih profili

Bu bölümdeki kuralların çoğu tek bir tercih profili üzerinde karşılaştırılır. Böylece farklı kuralların aynı oylardan farklı sonuçlar çıkardığı açıkça görülür. Profil Tablo 7.1'de verilmiştir.

Tabloyu okumayı bir kez açıkça yapalım. Aynı sıralamayı veren seçmenler bir sütunda toplanmıştır; sütun başlığı o sıralamayı kaç seçmenin verdiğini söyler. Birinci sütun “4 seçmen A ≻ D ≻ B ≻ C sıralamasını verdi” demektir. Bu dört seçmen için A en iyi, C en kötü adaydır. İkinci sütundaki dört seçmen C ≻ B ≻ D ≻ A, üçüncü sütundaki üç seçmen D ≻ B ≻ C ≻ A, dördüncü sütundaki iki seçmen A ≻ B ≻ C ≻ D sıralamasını verir. Not boyunca bu dört sütundan sırasıyla 1. grup, 2. grup, 3. grup ve 4. grup (kısaca G1–G4) diye söz edilir.

Toplam seçmen sayısı 4 + 4 + 3 + 2 = 13'tür. Bazı kurallarda bir adayın kazanması için oyların yarısından fazlasını alması gerekir. 13'ün yarısı 6,5'tir; yarısından fazla demek en az 7 oy demektir. Bu sayıya mutlak çoğunluk eşiği denir ve bu profilde 7'dir.

Profilde dikkat çeken birkaç özellik önceden not edilebilir. A, altı seçmenin (G1 ve G4) birinci tercihidir ama yedi seçmenin (G2 ve G3) son tercihidir: A seçmenleri kutuplaştıran bir adaydır. B'yi hiçbir seçmen birinci sıraya koymamıştır, ama dokuz seçmen onu ikinci sıraya koymuştur ve kimse onu sona koymamıştır: B herkesin “idare eder” dediği uzlaşmacı adaydır. D ise üç seçmenin birinci, dört seçmenin ikinci tercihidir. Bu özellikler, ileride her kuralın neden farklı bir adayı seçtiğini anlamayı kolaylaştırır. Sunum bu durumu tek cümleyle özetler: aynı profile uygulanan kurallar dört farklı kazanan verir.

7.2Oylama kuralları

Bu kısımda en çok kullanılan oylama kuralları tanıtılır ve hepsi Tablo 7.1'deki aynı profile uygulanır. Her kural için önce seçmenin ne bildirdiği, sonra sayımın nasıl yapıldığı, en sonda da kuralın bu profilde kimi seçtiği anlatılır.

7.2.1Temel oylama kurallarına genel bakış

Kurallar iki soruya göre ayrılır. Birincisi: seçmen pusulada ne bildirir? Bazı kurallarda yalnızca tek bir aday yazılır; bazılarında adayların tam sıralaması, bazılarında ise kabul edilen adayların kümesi istenir. İkincisi: bildirimler nasıl sayılır ve kazanan nasıl belirlenir? Tablo 7.2 altı temel kuralı bu iki soruya göre özetler.

Tablodaki kuralların bir kısmı sıralamanın yalnızca bir parçasını kullanır. Mutlak çoğunluk ve çoğulluk yalnızca birinci tercihe bakar; seçmenin ikinci, üçüncü tercihleri hiç sayılmaz. Borda, IRV ve Condorcet ise bütün sıralamayı kullanır. Daha çok bilgi kullanmak her zaman daha “adil” bir sonuç vermez, ama sonucun hangi bilgiye duyarlı olduğunu değiştirir.

7.2.2Mutlak çoğunluk, çoğulluk ve iki turlu sistem

İki kural da aynı sayımı kullanır; fark yalnızca kazananın nasıl ilan edildiğindedir. Mutlak çoğunlukta en az n/2'den fazla oy şartı vardır. Bu şart sağlandığında kazananın arkasında seçmenlerin çoğunluğu olduğu kesindir. Ama şart her zaman sağlanmaz; o zaman kural kazanan üretemez ve ek bir yönteme (ikinci tur gibi) ihtiyaç duyulur. Çoğulluk ise her zaman bir kazanan üretir (eşitlik bozma kuralıyla birlikte), ama kazananın arkasında seçmenlerin küçük bir azınlığı olabilir.

Mutlak çoğunluğun sağlanamadığı durumlar için uygulamada en yaygın çözüm iki turlu sistemdir (two-round system, runoff). Türkiye ve Fransa'daki cumhurbaşkanlığı seçimleri bu sistemi kullanır. İlk turda mutlak çoğunluğu sağlayan aday yoksa ilk turda en çok oy alan iki aday ikinci tura kalır. İkinci turda yalnızca bu iki aday yarışır; seçmenler ikisinden hangisini tercih ediyorsa ona oy verir.

Bu örnek, iki turlu sistemin çoğulluktan neden farklı sonuç verebildiğini gösterir: ikinci tur, elenen adayların seçmenlerine kalan adaylar arasında tercih yapma imkânı verir. Ama bu imkân sınırlıdır. İlk turda üçüncü veya dördüncü olan bir aday, başa baş bir yarışta herkesi yenebilecek olsa bile ikinci tura kalamaz. Bu profilde tam olarak bu olur: 7.2.7'de görüleceği gibi D bütün rakiplerini ikili karşılaştırmada yener, ama ilk turda yalnızca 3 oy aldığı için ikinci tura kalamaz.

7.2.3Borda sayımı

Çoğulluk, seçmenin ikinci tercihini hiç dikkate almaz. Bir aday herkesin ikinci tercihi olsa bile sıfır oy alır. 18. yüzyılda Fransız denizci ve matematikçi Jean-Charles de Borda bu sorunu fark edip her sıraya puan veren bir sayım önermiştir.

Borda puanının sade bir yorumu vardır: bir seçmenin sıralamasında x'in aldığı puan, o seçmenin x'in altına koyduğu aday sayısıdır. Birinci sıradaki aday m − 1 adayı geride bırakır, sonuncu hiçbirini. Dolayısıyla bir adayın toplam Borda puanı, bütün seçmenler üzerinden “x'in yendiği aday” sayılarının toplamıdır. Bu yorum 7.2.7'deki ikili karşılaştırmalarla bağ kurmaya yarar: Borda puanı, bir adayın ikili karşılaştırma tablosundaki satır toplamına eşittir.

Dört aday için puanlar 1. sıra 3, 2. sıra 2, 3. sıra 1, 4. sıra 0'dır. Bir grubun bir adaya katkısı “seçmen sayısı × puan”dır. Sayım grup grup yapılır.

Sonucun en ilginç yanı, B'yi hiçbir seçmenin birinci sıraya koymamış olmasıdır. B'nin gücü, hiçbir seçmenin onu sona koymaması ve dokuz seçmenin onu ikinci sıraya koymasıdır. Borda bu tür uzlaşmacı adayları öne çıkarır. Bu bir erdem olarak da görülebilir (herkesin kabul edebileceği aday) bir kusur olarak da (kimsenin gerçekten istemediği aday).

Hesabı kontrol etmenin kolay bir yolu vardır. Her seçmen toplamda 3 + 2 + 1 + 0 = 6 puan dağıtır. 13 seçmen toplam 13 × 6 = 78 puan dağıtmalıdır. Gerçekten 18 + 22 + 17 + 21 = 78'dir. Toplam tutmazsa bir yerde katkı yanlış hesaplanmıştır.

7.2.4Onay oylaması

Onay oylamasında seçmenin bildirdiği şey sıralama değil, bir kümedir. Seçmen “bu adaylar benim için kabul edilebilir, ötekiler değil” der. Bu yüzden onay oylamasının sonucu yalnızca seçmenlerin sıralamasına değil, her seçmenin nerede çizgi çektiğine de bağlıdır. Tercih profili tek başına onay kazananını belirlemez; her seçmenin kaç adayı onayladığı da bilinmelidir. Bu yüzden onay oylaması hesaplanırken bir varsayım yapılması gerekir.

Örnek iki önemli noktayı gösterir. Birincisi, herkes ilk iki adayını onayladığında onay oylaması ileride tanımlanacak 2-onay kuralına dönüşür; herkes yalnızca ilk adayını onayladığında ise çoğulluğa dönüşür. Onay oylaması bu iki uç arasında esnek bir yerde durur. İkincisi, sonuç onay eşiğine bağlıdır: aynı tercihlerle eşik değişince kazanan A'dan B'ye geçer. Eşiği seçmenin kendisi belirlediği için onay eşiği de stratejik bir karardır. Örneğin A'yı destekleyen bir seçmen, B'nin güçlü bir rakip olduğunu biliyorsa ikinci tercihi B'yi onaylamaktan vazgeçebilir.

Onay oylaması bazı bilimsel dernek seçimlerinde ve “hangi saatler uygun?” türü toplantı anketlerinde kullanılır. Toplantı anketinde her katılımcı uygun olduğu saatlerin hepsini işaretler ve en çok kişiye uyan saat seçilir; bu, onay oylamasının tam kendisidir.

7.2.5Pozisyonel puanlama kuralları

Çoğulluk, Borda ve (herkesin aynı sayıda aday onayladığı) onay oylaması aslında aynı fikrin farklı hâlleridir: her sıraya sabit bir puan verilir ve puanlar toplanır. Bu ortak yapı tek bir tanımla yazılabilir.

Puanların azalan sırada olması, seçmenin daha çok sevdiği adaya daha az puan vermemesi içindir. Veto kuralının adı yorumundan gelir: her seçmen yalnızca bir adayı “veto eder”, yani reddeder; bir adayın veto puanı, onu sona koymayan seçmen sayısıdır. Veto kuralı herkesin en az itiraz ettiği adayı arar.

Şekil 7.3 ve Şekil 7.4 aynı profilin iki farklı puan vektörüyle sayımını gösterir. Solda profil vardır; turuncu hücreler puan alan sıralardır. Sağda her adayın toplam puanı bir çubukla çizilmiştir; turuncu çubuk kazananı gösterir.

Beş farklı vektörün sonuçları Tablo 7.4'te toplanmıştır. Hesapların hepsi aynı yöntemle yapılır: her grubun her adaya katkısı “seçmen sayısı × o sıranın puanı”dır.

Bu tablo bölümün ana mesajlarından birini sayılarla verir: aynı oylarla yalnızca puan vektörü değişince kazanan A, B ve D arasında değişir. Hangi puan vektörünün “doğru” olduğuna dair matematiksel bir cevap yoktur. Birinci sıraya çok ağırlık veren vektörler çoğulluğa benzer ve kutuplaştıran adayları (A) öne çıkarır; sıralar arasında eşit aralık bırakan vektörler uzlaşmacı adayları (B) öne çıkarır.

Puanlama kurallarının ortak bir iyi özelliği vardır: monotondurlar. Bir seçmen kazanan adayı kendi pusulasında bir sıra yukarı taşırsa o aday ya aynı puanı ya da daha fazla puan alır, çünkü puan vektöründe üst sıra en az alt sıra kadar puan verir. Yukarı taşınan adayın yer değiştirdiği öteki aday ise en fazla aynı puanı alır. Dolayısıyla kazananın öndeliği azalmaz ve kazanan kazanmaya devam eder. Bu gözlem önemlidir, çünkü 7.3.7'de anında ikinci turun bu özelliği sağlamadığı görülecektir.

7.2.6Anında ikinci tur

İki turlu sistemin bir sorunu, seçmenleri iki kez sandığa götürmesidir. Bir başka sorunu, ikinci tura yalnızca iki aday kalması ve birinci turda üçüncü olan adayın şansının hemen bitmesidir. Anında ikinci tur (instant-runoff voting, IRV; tercihli oy diye de bilinir) iki soruna birlikte çözüm arar: seçmenden bir kez tam sıralama alınır ve turlar bu sıralamalar üzerinden bilgisayarla ya da elle “anında” yapılır.

Bu kuralda hiçbir pusula boşa gitmez: seçmenin favorisi elenirse oyu sıralamasındaki bir sonraki adaya aktarılır. İki turlu sistemden farkı, adayların tek tek elenmesi ve her elemeden sonra oyların yeniden dağılmasıdır.

Bu profilde IRV'nin sonucu iki turlu sistemle aynıdır: C. Bu bir rastlantı değildir; dört adaydan ikisi elendikten sonra kalan iki aday, iki turlu sistemin ikinci turuna kalan adaylarla aynıdır. Ama genel olarak iki kural farklı sonuç verebilir, çünkü IRV'de eleme sırası oyların aktarılmasıyla değişebilir. Dikkat çeken bir başka nokta: IRV, Condorcet kazananı olan D'yi ikinci turda eler. D'nin birinci tercih sayısı az olduğu için D, bütün rakiplerini başa baş yarışta yenebilecek olsa da yarışın erken bir aşamasında çıkar.

7.2.7Condorcet: ikili karşılaştırmalar

Şimdiye kadarki kurallar adayları hep birlikte değerlendirdi. Condorcet'nin önerisi farklıdır: her aday çifti ayrı ayrı, sanki yalnızca bu iki aday yarışıyormuş gibi karşılaştırılır. İki aday arasındaki yarışı, iki adaydan hangisini daha üstte gören seçmenlerin sayısı belirler.

Condorcet kazananı fikri sezgisel olarak çok güçlüdür. Bir aday her rakibine karşı seçmenlerin çoğunluğu tarafından tercih ediliyorsa, onun yerine başka bir adayın seçilmesi o başka aday yerine bu adayı isteyen bir çoğunluğu memnuniyetsiz bırakır. Ama Condorcet kazananı her profilde bulunmayabilir; bu durum 7.3'ün konusudur.

Dört aday için 4 · 3 / 2 = 6 çift vardır. Genel olarak m aday için çift sayısı m(m − 1)/2'dir. Sonuçlar bir tabloya yazılır: (x, y) hücresi, x'i y'ye tercih eden seçmen sayısı N(x, y)'dir.

Tablo 7.5 tamamlanınca sonuç açıktır: D üç rakibini de 7–6 yener ve Condorcet kazananıdır. A ise herkese 6–7 yenilir ve Condorcet kaybedenidir. Şaşırtıcı olan, çoğulluğun tam olarak bu Condorcet kaybedeni A'yı seçmiş olmasıdır. A'nın birinci tercih sayısı en yüksektir, ama A'yı birinci koymayan yedi seçmenin hepsi onu son sıraya koyar; bu yedi seçmen, A'ya karşı yarışan her adayı destekler.

Tablonun satır toplamları da bir şey söyler: A satırı 6 + 6 + 6 = 18, B satırı 7 + 9 + 6 = 22, C satırı 7 + 4 + 6 = 17, D satırı 7 + 7 + 7 = 21'dir. Bunlar tam olarak Borda puanlarıdır. 7.2.3'teki yorumun bir sonucudur bu: Borda puanı, bir adayın bütün ikili karşılaştırmalarda topladığı oyların toplamıdır. Borda ile Condorcet arasındaki fark da buradan görülür. Condorcet yalnızca kimin kazandığına bakar (7, 6'dan büyük mü?), Borda ise farkın büyüklüğünü de sayar. B'nin C'ye karşı 9–4'lük büyük farkı, D'ye karşı 6–7'lik küçük yenilgisini Borda toplamında telafi eder.

7.2.8İkili çoğunluk çizgesi ve Copeland

İkili karşılaştırmaların sonuçlarını göstermenin görsel bir yolu bir çizge çizmektir. Bu çizgede her aday bir düğümdür. x, y'yi ikili çoğunlukla yeniyorsa x'ten y'ye bir ok çizilir. Bu çizgeye ikili çoğunluk çizgesi (pairwise majority graph) denir.

Seçmen sayısı tek olduğunda iki aday arasında eşitlik olamaz; bu yüzden her çift arasında tam olarak bir ok vardır. Böyle bir çizgeye turnuva (tournament) denir; adı, her takımın her takımla bir kez karşılaştığı lig maçlarından gelir. Şekil 7.5'te D'den üç ok çıkar ve D'ye hiç ok girmez. Genel kural şudur:

• Condorcet kazananı = hiç ok almayan düğüm (D).
• Condorcet kaybedeni = bütün okları alan, hiç ok vermeyen düğüm (A).

Her aday en az bir ok alıyorsa, yani hiç ok almayan düğüm yoksa, Condorcet kazananı yoktur. Bu durumda çizgede bir döngü vardır: bir adaydan başlayıp okları izleyerek aynı adaya dönülebilir. Bütün adayları kapsayan bir döngü, Condorcet kazananının bulunmamasına yol açar.

Örnek profilde Copeland skorları D 3, B 2, C 1, A 0'dır; bu skorlar Tablo 7.5'in son sütunuyla aynıdır. Copeland, D ≻ B ≻ C ≻ A sıralamasını verir ve kazanan D'dir. Copeland kuralının iyi bir özelliği, Condorcet kazananı varsa onu her zaman seçmesidir: Condorcet kazananı m − 1 galibiyetle en yüksek mümkün skoru alır ve başka hiçbir aday bu skora ulaşamaz, çünkü her öteki aday en az bir kez (Condorcet kazananına) yenilir. Condorcet kazananı yoksa Copeland yine de bir sıralama verir, ama bu sıralamada eşitlikler sık görülür.

7.2.9Aynı profil, dört farklı kazanan

Bu noktaya kadar aynı 13 seçmenin oyları sekiz farklı yolla sayıldı. Sonuçlar Tablo 7.6'da yan yana konulmuştur. Tablodaki Kemeny satırı 7.3.4'te hesaplanır.

Tablodan iki ders çıkar. Birincisi: “halkın iradesi” kurala bağlıdır. Seçmenlerin oyları değişmediği hâlde kural değişince kazanan A, B, C ya da D olabilmektedir; yani kural, seçmenler kadar sonucu belirler. Bu yüzden bir oylamada hangi kuralın kullanılacağı, oylamadan önce açıkça kararlaştırılması gereken önemli bir karardır. İkincisi: bazı kurallar sezgisel olarak kötü sonuçlar verebilir. Çoğulluk, herkese yenilen Condorcet kaybedeni A'yı seçebilir; IRV ise herkesi yenen Condorcet kazananı D'yi erken eleyebilir.

Her kuralın neden farklı aday seçtiği, profilin 7.1.3'te not edilen özellikleriyle açıklanır. Çoğulluk yalnızca birinci sıraya baktığı için en çok “sadık” seçmeni olan A'yı seçer. İki tur ve IRV, birinci tercihleri güçlü olan adaylar arasında son yarışı yaptırır ve C'yi seçer. Borda ve 2-onay, ikinci sıraları da saydığı için uzlaşmacı B'yi seçer. Condorcet ve Kemeny ise ikili yarışlara baktığı için, her başa baş yarışı kazanan D'yi seçer.

7.2.10Kod izleme: borda()

Oylama kurallarının sayımı birkaç satırlık programlarla yapılabilir. Bu kısımda Borda sayımını yapan kısa bir Python fonksiyonu satır satır izlenir. Fonksiyonun girdisi oylar adlı bir listedir. Listenin her elemanı (adet, sira) biçiminde bir çifttir: adet o sıralamayı veren seçmen sayısı, sira ise adayları en çok tercih edilenden başlayarak dizen bir dizgedir. Örnek profil şöyle yazılır:

oylar = [(4, "ADBC"), (4, "CBDA"), (3, "DBCA"), (2, "ABCD")]

def borda(oylar):
  puan = {}
  for adet, sira in oylar:
    m = len(sira)
    for k, aday in enumerate(sira):
      p = adet * (m - 1 - k)
      puan[aday] = puan.get(aday, 0) + p
  kazanan = max(puan, key=puan.get)
  return kazanan, puan

Kod şöyle çalışır:

• puan boş bir sözlüktür; her adayın birikmiş puanı burada tutulacaktır.
• Dış döngü her seçmen grubunu bir kez dolaşır: adet grubun büyüklüğü, sira grubun sıralamasıdır.
• m = len(sira) aday sayısıdır; burada 4.
• İç döngü sıralamadaki her adayı yeriyle birlikte dolaşır. enumerate, sıradaki yeri 0'dan başlayarak k'ya verir: birinci sıra k = 0, sonuncu k = m − 1'dir.
• p = adet * (m - 1 - k) grubun bu adaya katkısıdır. k = 0 için puan m − 1 = 3, k = 3 için 0'dır. Bu, tanımdaki puan ölçeğinin 0'dan başlayan indisle yazılışıdır.
• puan.get(aday, 0), aday sözlükte henüz yoksa 0 döndürür; böylece ilk kez görülen adayın puanı 0'dan başlar.
• max(puan, key=puan.get), puanı en büyük olan anahtarı (adayı) döndürür.

Tablo 7.7 ilk grubun iç döngüsünü adım adım, öteki grupları ise toplu olarak izler.

Fonksiyon ("B", {"A": 18, "D": 21, "B": 22, "C": 17}) döndürür. Şekil 7.6 bu son durumu gösterir. Puanı en yüksek aday B'dir (22) ve hiçbir seçmen B'yi birinci sıraya koymamıştır.

Kodun bir inceliği eşitlik durumudur. İki aday aynı en yüksek puanı alırsa max, sözlükte önce gördüğünü döndürür. Bu bir oylama kuralı açısından keyfi bir seçimdir: sonucu adayların sözlüğe hangi sırayla girdiği, yani girdi listesinin düzeni belirler. Gerçek kurallarda bunun yerine önceden ilan edilmiş bir eşitlik bozma kuralı (tie-breaking rule) gerekir: kura çekmek, belirli bir aday sırası ya da ikinci bir ölçüt (örneğin birinci tercih sayısı).

Karmaşıklık açısından fonksiyon her grup için her adayı bir kez işler. n seçmen grubu ve m aday varsa iç döngü toplam n · m kez çalışır; çalışma süresi O(nm)'dir. Sayım kolaydır; zor olan, kuralın hangi özellikleri sağladığını anlamaktır.

7.2.11Kod izleme: ikinci_tur()

Anında ikinci turun kodu Borda'dan biraz daha uzundur, çünkü sayım turlar hâlinde tekrarlanır. Fonksiyon oylar listesini ve aday listesini alır.

def ikinci_tur(oylar, adaylar):
  kalan = set(adaylar)
  while True:
    say = {a: 0 for a in kalan}
    for adet, sira in oylar:
      ilk = next(a for a in sira if a in kalan)
      say[ilk] += adet
    lider = max(say, key=say.get)
    if 2 * say[lider] > sum(say.values()):
      return lider
    kaybeden = min(say, key=say.get)
    kalan.remove(kaybeden)

Kod şöyle çalışır:

• kalan, yarışta kalan adayların kümesidir; başta bütün adaylar yarıştadır.
• while True döngüsünün her dönüşü bir turdur. Döngüden yalnızca return ile, yani bir kazanan bulununca çıkılır.
• say, her yarışan aday için 0'dan başlayan bir sayaçtır. Sayaçlar her turda sıfırlanır; oylar her turda baştan sayılır.
• next(a for a in sira if a in kalan), sıralamayı baştan sona tarar ve hâlâ yarışan ilk adayı döndürür. Oyların aktarılması bu satırda kendiliğinden gerçekleşir: elenen adaylar kalan'da olmadığı için atlanır.
• lider, en çok oyu alan adaydır. Koşul 2 * say[lider] > sum(say.values()), liderin oyunun toplamın yarısından fazla olup olmadığını sınar. İki tarafı 2 ile çarpmak, 6,5 gibi kesirli eşiklerle uğraşmayı önler.
• Çoğunluk yoksa min(say, key=say.get) en az oylu adayı bulur ve kalan.remove onu yarıştan çıkarır.

Birinci turda dört pusula grubu sırayla işlenir: ADBC grubunun yarışan ilk adayı A'dır ve say[A] += 4; CBDA için say[C] += 4; DBCA için say[D] += 3; ABCD için say[A] += 2. Sonuç A 6, B 0, C 4, D 3'tür. Lider A'dır ama 2 × 6 = 12 ≤ 13 olduğu için çoğunluk yoktur. En az oylu B (0) elenir. İkinci turda sayaçlar sıfırlanır ve sayım tekrarlanır; B'yi birinci sıraya koyan olmadığı için sayılar değişmez. D (3) elenir. Üçüncü turda DBCA grubunun taraması D'yi ve B'yi atlar ve C'de durur: say[C] += 3. Bu, D'nin oylarının C'ye geçmesidir. 2 × 7 = 14 > 13 olduğu için C döndürülür.

Her turda n grup için sıralama en fazla m adımda taranır, yani bir tur O(nm) sürer. En fazla m − 1 tur olduğundan toplam süre O(nm²)'dir. Bu da hızlı bir hesaptır; IRV'nin zorlukları sayımda değil, özelliklerindedir.

7.3Condorcet paradoksu

Örnek profilde Condorcet kazananı vardı: D. Ama her profilde böyle bir aday bulunmaz. Bu kısımda bunun neden olduğu, bu durumun hangi sorunlara yol açtığı ve bu sorunlara karşı geliştirilen Kemeny kuralı incelenir. Ardından kuralların hangi ölçütleri sağladığı bir tabloda toplanır ve anında ikinci turun monotonluk ihlali gösterilir.

7.3.1Condorcet döngüsü

Dokuz seçmen ve üç adaylı şu profil ele alınsın: 4 seçmen A ≻ B ≻ C, 3 seçmen B ≻ C ≻ A, 2 seçmen C ≻ A ≻ B. Her seçmenin sıralaması tek başına tutarlıdır, yani geçişlidir.

Şekil 7.8 durumu ikili çoğunluk çizgesiyle gösterir. Üç ok bir daire oluşturur: her düğüme bir ok girer, bu yüzden Condorcet kazananı yoktur. Bu olguya Condorcet paradoksu ya da Condorcet döngüsü (Condorcet paradox / cycle) denir.

Paradoksun önemi şudur: bireylerin tutarlı olması topluluğun tutarlı olmasını garanti etmez. “Çoğunluk A'yı B'ye tercih ediyor” ve “çoğunluk B'yi C'ye tercih ediyor” cümlelerindeki “çoğunluk” aynı insanlar değildir. İlk çoğunluk 1. ve 3. sütunlardan, ikincisi 1. ve 2. sütunlardan oluşur. Farklı çoğunluklar farklı kararlar verir ve bu kararlar bir araya getirildiğinde döngü oluşabilir.

7.3.2Gündem sırası kazananı belirler

Döngünün pratik bir sonucu vardır. Pek çok komite ve meclis kararlarını ikili elemeli oylama (sequential pairwise voting) ile verir: önce iki seçenek oylanır, kazanan bir sonraki seçenekle karşılaşır ve bu, bütün seçenekler bitene dek sürer. Seçeneklerin hangi sırayla oylanacağına gündem (agenda) denir. Döngü profilinde üç farklı gündem mümkündür (hangi çiftin önce oylanacağı seçilir; kalan aday sona kalır).

Örnekteki örüntü genel bir kuraldır: üç adaylı bir döngüde sona bırakılan aday kazanır. Nedeni şudur: ilk oylamada iki aday karşılaşır ve kazanan, sona bırakılan adayla karşılaşır. Üç adaylı bir döngüde her aday tam bir adayı yener ve tam bir adaya yenilir. İlk oylamanın kazananı yenebildiği tek adayı ilk oylamada yenmiştir; demek ki yenildiği tek aday sona bırakılan adaydır ve son oylamayı kaybeder. Örneğin gündem 1'de A, B'yi yener; döngüde A'yı yenen aday C'dir ve C sondadır.

Bu, gündemi belirleyen kişiye (örneğin bir komite başkanına) büyük bir güç verir. Başkan, kazanmasını istediği adayı sona koyarak sonucu seçebilir; üstelik her oylama kendi içinde dürüst bir çoğunluk oylamasıdır. Bu duruma gündem manipülasyonu (agenda manipulation) denir. Condorcet kazananı olan bir profilde ise bu güç yoktur: Condorcet kazananı hangi sırayla oylanırsa oylansın karşılaştığı her adayı yener ve sonunda kazanır.

7.3.3Oyuna dönüş: döngü ne kadar sık?

Bölümün başındaki oyunun merak sorularına artık cevap verilebilir. Oyunun birinci seviyesindeki profil (A ≻ B ≻ C, B ≻ C ≻ A, C ≻ A ≻ B) bir döngüdür: A – B 2 – 1, B – C 2 – 1, C – A 2 – 1. Toplumsal tercih döngüseldir, Condorcet kazananı yoktur. Birinci sorunun cevabı “hayır”dır: bireyler tutarlı olsa da topluluk tutarlı olmak zorunda değildir. İkinci sorunun cevabı “evet”tir: gündemi kuran kişi, kazanmasını istediği adayı sona bırakarak sonucu seçer. Gündemlerin sonuçları Tablo 7.10'daki ile aynı örüntüyü izler: (A – B) sonra C gündeminde C, (B – C) sonra A gündeminde A, (A – C) sonra B gündeminde B kazanır.

Doğal bir soru, döngülerin ne kadar sık görüldüğüdür. Bunun için bir olasılık modeli gerekir. En basit model, her seçmenin altı olası sıralamadan birini eşit olasılıkla ve ötekilerden bağımsız olarak seçmesidir. Üç seçmen ve üç aday için olası profil sayısı 6 × 6 × 6 = 6³ = 216'dır. Bu profillerin kaçında döngü olduğu sayılabilir: döngü yalnızca seçmenlerin sıralamaları A ≻ B ≻ C, B ≻ C ≻ A, C ≻ A ≻ B üçlüsünün ya da bunun tersi olan A ≻ C ≻ B, C ≻ B ≻ A, B ≻ A ≻ C üçlüsünün bir dizilişi olduğunda oluşur. Her üçlü üç seçmene 3! = 6 farklı şekilde dağıtılabilir; toplam 2 × 6 = 12 döngülü profil vardır. Olasılık 12/216 ≈ 0,056, yani yaklaşık %5,6'dır.

Seçmen sayısı çok büyüdükçe, aynı rastgele modelde üç adaylı döngü olasılığı yaklaşık %8,8'e yükselir (Guilbaud, 1952). Aday sayısı arttıkça bu oran da hızla artar. Bu sayılar endişe verici görünebilir, ama gerçek seçim ve anket verilerinde döngüler bu “rastgele tercih” hesabının öngördüğünden de seyrek görülür (Regenwetter vd., 2006). Nedeni, gerçek tercihlerin rastgele olmamasıdır: insanların tercihleri birbirine benzer ve çoğu zaman bir ortak eksene (örneğin sol–sağ) göre düzenlenir. Bu tür düzenli tercihlerde döngünün neden oluşmadığı 7.5.6'da açıklanır.

7.3.4Kemeny kuralı

Döngü olduğunda Condorcet fikri bir kazanan veremez. Yine de bir karar verilmesi gerekir. John Kemeny (1959) bu sorunu şöyle çözmeyi önerdi: seçmenlerin ikili tercihleriyle en çok uyuşan toplumsal sıralamayı seç.

Uyum skorunun bir yorumu daha vardır. Bir seçmenin sıralaması ile σ arasında bazı çiftlerde anlaşma, bazılarında anlaşmazlık vardır. Uyum skoru, bütün seçmenler üzerinden anlaşılan çift sayısının toplamıdır. Uyumu en büyük yapmak, anlaşılmayan çift sayısını (sıralamalar arasındaki toplam “uzaklığı”) en küçük yapmakla aynıdır. Kemeny sıralaması, bu anlamda seçmenlerin sıralamalarına “ortalama olarak en yakın” sıralamadır.

Örnek genel bir gözlemi gösterir: ikili çoğunluk ilişkisi geçişliyse (döngü yoksa), bu ilişkiyi izleyen sıralama her çiftte en büyük katkıyı alır ve Kemeny sıralamasıdır. Özellikle Condorcet kazananı varsa Kemeny sıralamasında başa yerleşir. Bunun nedeni şudur: Condorcet kazananı bir sıralamada başta değilse, onun hemen önündeki adayla yer değiştirmesi, o çiftin katkısını küçük sayıdan büyük sayıya çıkarır ve başka hiçbir çifti değiştirmez; bu da uyumu artırır.

Döngüde de Kemeny bir karar verir. Döngü profilinde üç ikili çoğunluk birlikte sağlanamaz; en az birinin bozulması gerekir. Kemeny, bozulduğunda en az uyum kaybettiren çoğunluğu, yani en zayıf çoğunluğu bozar.

Şekil 7.9'da döngünün üç kenarı ve oy sayıları görülür: A ≻ B 6 – 3, B ≻ C 7 – 2, C ≻ A 5 – 4. En dar farklı kenar C ≻ A'dır. Bu kenar bozulunca kalan iki kenar A ≻ B ≻ C sıralamasını verir. Bu sıralamanın uyumu N(A, B) + N(A, C) + N(B, C) = 6 + 4 + 7 = 17'dir. Ayrıntılı karşılaştırma bir sonraki kod izlemesinde yapılır.

Kemeny kuralının güçlü özellikleri vardır, ama bir bedeli de vardır: en iyi sıralamayı bulmak NP-zordur (Bartholdi, Tovey ve Trick, 1989). NP-zor bir problem için, bilinen bütün algoritmalar en kötü durumda girdinin büyüklüğüyle üstel olarak artan zaman alır. Aday sayısı küçükken bütün sıralamalar denenebilir, ama 15–20 adayda bu artık pratik değildir. Kemeny kuralının önemli bir uygulaması sıralama birleştirmedir (rank aggregation; Dwork vd., 2001): birden çok arama motorunun sonuç listelerini tek listede birleştirmek, yarışma jürilerinin ve komitelerin sıralamalarını birleştirmek.

7.3.5Kod izleme: kemeny()

Az sayıda aday için Kemeny sıralaması bütün sıralamalar denenerek bulunabilir. Aşağıdaki fonksiyon tam olarak bunu yapar. Fonksiyon, Python'un standart kütüphanesindeki permutations fonksiyonunu kullanır; bu yüzden programın başında from itertools import permutations satırı bulunmalıdır. permutations(adaylar), adayların bütün sıralamalarını tek tek üretir.

def kemeny(oylar, adaylar):
  en_iyi, en_skor = None, -1
  for sira in permutations(adaylar):
    skor = 0
    for i, x in enumerate(sira):
      for y in sira[i + 1:]:
        skor += sum(n for n, oy in oylar
                    if oy.index(x) < oy.index(y))
    if skor > en_skor:
      en_iyi, en_skor = sira, skor
  return en_iyi, en_skor

Kod şöyle çalışır:

• en_iyi o ana kadar bulunan en iyi sıralamayı, en_skor onun uyum skorunu tutar. Başlangıç değeri −1'dir; böylece ilk denenen sıralama (skoru en az 0) her zaman en iyi kabul edilir.
• Dış döngü her sira sıralamasını dener.
• İki iç döngü sıralamadaki bütün (x, y) çiftlerini dolaşır; sira[i + 1:] yalnızca x'ten sonra gelen adayları verir. Böylece her çift bir kez ve “sıralamada x önce” yönüyle ele alınır.
• oy.index(x) < oy.index(y), o seçmen grubunun x'i y'den önce koyup koymadığını sınar. Koşulu sağlayan grupların büyüklükleri n toplanır; bu N(x, y)'dir.
• Bir sıralamanın skoru önceki en iyiden kesin büyükse en iyi güncellenir. Eşit skorlu sıralamalardan ilk bulunan korunur.

Döngü profili oylar = [(4, "ABC"), (3, "BCA"), (2, "CAB")] için izleme Tablo 7.11'de verilmiştir. Üç aday için 3! = 6 sıralama vardır ve her sıralamada 3 · 2 / 2 = 3 çift bulunur.

Fonksiyon (("A", "B", "C"), 17) döndürür. Kemeny sıralaması A ≻ B ≻ C'dir ve yalnızca en zayıf çoğunluk olan C ≻ A (5 – 4) bozulmuştur. İkinci en iyi sıralama B ≻ C ≻ A'dır (15); bu sıralama A ≻ B çoğunluğunu (6 – 3) bozar ve 2 puan daha fazla uyum kaybeder. Tablonun bir simetrisi de dikkat çeker: bir sıralamanın skoru ile tersinin skoru toplanınca her zaman 3 × 9 = 27 eder (17 + 10, 12 + 15, 14 + 13). Nedeni, her çiftte bir seçmenin iki sıralamadan tam biriyle anlaşmasıdır.

Bu kaba kuvvet yönteminin maliyeti hızla büyür. m aday için m! sıralama denenir; her sıralamada m(m − 1)/2 çift vardır ve her çift için n grup taranır. Toplam iş m! · m(m − 1)/2 · n düzeyindedir. 4 aday için 24, 10 aday için 3 628 800, 20 aday için yaklaşık 2,4 × 10¹⁸ sıralama vardır. Kemeny'nin NP-zor olması, bu üstel büyümeden genel olarak kaçmanın bilinen bir yolunun olmadığını söyler.

7.3.6Kurallar hangi ölçütleri sağlar?

Farklı kuralların farklı kazananlar seçtiğini gördük. Hangisinin “daha iyi” olduğunu tartışmak için ölçütlere ihtiyaç vardır. Sosyal seçim kuramında kuralları karşılaştırmak için kullanılan ölçütlere aksiyom da denir. Bu kısımda dört ölçüt tanımlanır ve kuralların bunları sağlayıp sağlamadığı bir tabloda toplanır.

Tablo satır satır okunabilir. Çoğulluk örnek profilde Condorcet kazananı D'yi değil A'yı seçer; A aynı zamanda Condorcet kaybedenidir, yani çoğulluk iki Condorcet ölçütünü de bozar. Borda, Condorcet kazananı D yerine B'yi seçer. Ama Borda hiçbir zaman Condorcet kaybedenini seçmez. Bunun nedeni 7.2.7'deki gözlemdir: Borda puanı, ikili karşılaştırmalarda alınan oyların toplamıdır. Condorcet kaybedeni her karşılaştırmada oyların yarısından azını alır; bu yüzden Borda puanı, adayların ortalama Borda puanının altında kalır. Örnek profilde ortalama 78 / 4 = 19,5'tir ve A'nın puanı 18'dir. Ortalamanın altında kalan bir aday en yüksek puanı alamaz.

IRV, Condorcet kazananı D'yi ikinci turda eler ve C'yi seçer. IRV Condorcet kaybedenini seçmez: son turda iki aday başa baş kalır ve Condorcet kaybedeni bu son yarışı kaybeder. Ama IRV monoton değildir; bu, bir sonraki kısımda bir örnekle gösterilir. Onay oylamasında sonuç onay eşiklerine bağlı olduğundan hiçbir Condorcet ölçütü garanti edilemez. Copeland ve Kemeny ikili karşılaştırmalara dayandıkları için iki Condorcet ölçütünü de sağlar.

Son sütundaki “hayır”ların hepsinin ortak bir nedeni vardır: üç ya da daha fazla adayda, diktatörlük dışında hiçbir makul kural stratejiye dayanıklı değildir. Bu genel sonuç Gibbard–Satterthwaite teoremidir ve 7.5.4'te ele alınır.

Condorcet yöntemlerinin bir eksiği, döngüde kazanan bulamamalarıdır. Döngüde Copeland skorları eşit çıkar (örneğin döngü profilinde üç adayın da birer galibiyeti vardır) ve bir eşitlik bozma kuralı gerekir. Bu eksiği gideren kurallardan biri maksimindir.

Maksimin, Condorcet kazananı varsa onu seçer: Condorcet kazananı her karşılaştırmada oyların yarısından fazlasını alır, öteki her aday ise en az bir karşılaştırmada (Condorcet kazananına karşı) yarısından azını alır. Döngüde de karar verir: kazanan, en kötü yenilgisi en hafif olan adaydır.

7.3.7Anında ikinci turda monotonluk ihlali

Monotonluk, bir oylama kuralından beklenecek en temel özelliklerden biri gibi görünür: bir adaya daha çok destek vermek ona zarar vermemelidir. Puanlama kuralları bu özelliği her zaman sağlar (7.2.5). IRV ise sağlamaz. Bu kısımda 17 seçmenli bir örnekle bu gösterilir.

İhlalin mekanizması şudur. IRV'de bir adayın kazanıp kazanmaması yalnızca kendi oylarına değil, son turda kiminle karşılaşacağına da bağlıdır. İlk profilde A son turda B ile karşılaşır ve C'nin seçmenleri A'yı B'ye tercih ettiği için A kazanır. Kampanyada A'ya geçen 2 seçmen B'den alınmıştır; B'nin birinci tercih sayısı 6'dan 4'e düşer ve B, C'nin altına iner. Eleme sırası değişir: bu kez B elenir ve A son turda C ile karşılaşır. B'nin seçmenleri C'yi A'ya tercih ettiği için C kazanır. Yukarı taşıma, eleme sırasını değiştirmiştir.

Bu profilde ikili karşılaştırmalar da ilginçtir: ilk profilde A, B'yi 11 – 6, B, C'yi 12 – 5, C de A'yı 11 – 6 yener. Profil bir Condorcet döngüsüdür. Monotonluk ihlalleri çoğunlukla böyle, Condorcet kazananının olmadığı ya da yarışın çok yakın olduğu profillerde görülür.

7.4Stratejik oy

Şimdiye kadar her seçmenin pusulasına gerçek tercihini yazdığı varsayıldı. Ama 7.1.2'de belirtildiği gibi pusula bir stratejidir. Bir seçmen, kuralın nasıl işlediğini ve öteki seçmenlerin nasıl oy vereceğini bildiğinde, gerçek tercihinden farklı bir pusula yazarak kendi gerçek tercihine göre daha iyi bir sonuç elde edebilir. Buna stratejik oy (strategic voting) ya da manipülasyon denir. Bu kısımda iki tür stratejik oy, örnek profil üzerinde sayısal olarak gösterilir.

7.4.1Çoğullukta taktik oy

Dürüst oylamada çoğulluk kazananı A'dır: A 6, C 4, D 3, B 0. Bu sonuç 3. grubu (D ≻ B ≻ C ≻ A) en çok rahatsız eden sonuçtur, çünkü A onların en kötü adayıdır.

Bu davranışa taktik oy (tactical voting) ya da “boşa oy vermeme” davranışı denir: seçmen favorisi yerine kazanma şansı olan ve daha az kötü bulduğu adaya oy verir. Taktik oyun nedeni oy bölünmesidir (vote splitting): A'ya karşı olan yedi seçmenin oyları C ve D arasında bölündüğü için A, seçmenlerin azınlığının desteğiyle kazanabilmiştir.

Taktik oyun uzun vadeli bir sonucu da vardır. Seçmenler küçük adaylara oy vermenin boşa gideceğini düşündükçe oylar en güçlü iki adayda toplanır. Siyaset biliminde bu gözleme Duverger yasası (Duverger's law) denir: tek turlu çoğulluk sistemi iki partili bir siyasi yapıya doğru iter. Birleşik Krallık ve ABD'deki tek üyeli seçim bölgeleri bu yasanın sık verilen örnekleridir.

7.4.2Borda'da gömme

Borda sayımı daha çok bilgi kullanır ve oy bölünmesinden daha az etkilenir. Ama o da stratejik davranışa açıktır, üstelik farklı bir yolla. Dürüst Borda sayımında B = 22, D = 21'dir. 3. grubun favorisi D, yalnızca 1 puan farkla kaybetmektedir.

Bu manipülasyona gömme (burying) denir: seçmen, favorisinin asıl rakibini pusulasında gerçek yerinden daha aşağıya “gömer”. Borda'da gömme çok etkilidir, çünkü her sıra farkı doğrudan puan farkına dönüşür. Bir rakibi en alta itmek, ona verilen puanı olabildiğince azaltır.

Gömmenin bir riski vardır: geri tepebilir. Rakibi aşağı itmek, onun yerine yukarı çıkan başka bir adayın puanını artırır. Bu başka aday gömen seçmenler için daha kötü bir adaysa ve yeterince yükselirse kazanan o olur. Örneğin 9 seçmenli şu profilde: 4 × A ≻ B ≻ C, 3 × C ≻ B ≻ A, 2 × B ≻ C ≻ A, dürüst Borda (2, 1, 0) puanları A 8, B 11, C 8'dir ve B kazanır. A seçmenleri B'yi gömüp A ≻ C ≻ B bildirirse C 4 puan kazanır, B 4 puan kaybeder: A 8, B 7, C 12 ve C kazanır. C, A seçmenlerinin en kötü adayıdır; gömme onların durumunu kötüleştirmiştir. Başarılı bir gömme, öteki seçmenlerin oyları hakkında doğru bilgi gerektirir.

7.4.3Stratejik oy sistemi ne kadar bozar?

Stratejik davranışın etkisi kurala göre farklıdır:

• Çoğulluk: oy bölünmesi temel sorundur. Benzer iki aday oyları paylaşır, üçüncüsü kazanır. Taktik oy yaygın ve basittir; seçmenin yalnızca kimin önde olduğunu bilmesi yeter.
• Borda: rakibi en alta gömmek çok etkilidir. Herkes gömerse bildirilen sıralamalar seçmenlerin gerçek tercihlerinden uzaklaşır ve sonuç, kimsenin gerçekten istemediği bir aday olabilir.
• Anında ikinci tur: manipülasyonu hesaplamak daha zordur ama mümkündür; ayrıca kural monoton değildir. “IRV stratejik oya kapalıdır” yaygın ama yanlış bir kanıdır.
• Hesaplama bariyeri: bazı kurallarda (örneğin IRV ve Copeland'in bir türevinde) kârlı bir manipülasyonu bulmak NP-zordur (Bartholdi vd., 1989–91). Bu zorluk, manipülasyonu imkânsız değil ama en kötü durumda hesaplama açısından pahalı kılar.

Stratejik oyun etkisi tercih dağılımına bağlıdır. Yakın yarışlarda birkaç seçmenin stratejik davranışı kazananı değiştirebilir; büyük farklı yarışlarda ise küçük grupların manipülasyonu sonuç üzerinde etkisizdir. Şeffaf kurallar ve anlaşılır bilgi bazı manipülasyonları azaltır, ama hiçbir genel kural stratejik davranışı her durumda ortadan kaldıramaz. Bu son cümle bir gözlem değil, bir teoremdir; teoremin kendisi bir sonraki kısımda ele alınır.

7.5İmkânsızlık teoremleri

Önceki kısımlarda her kuralın bir kusuru bulundu: çoğulluk Condorcet kaybedenini seçebilir, Borda manipülasyona açıktır, IRV monoton değildir, Condorcet yöntemleri döngüde karar veremez. Doğal soru şudur: bütün bu kusurlardan arınmış, daha akıllıca tasarlanmış bir kural var mıdır? Bu kısımdaki teoremlerin cevabı, üç ya da daha fazla aday olduğunda “hayır”dır. Bu sonuçlar, kural aramayı bırakmayı değil, hangi özellikten ödün verileceğini bilinçli olarak seçmeyi öğretir.

7.5.1Arrow'un koşulları

Kenneth Arrow (1951) soruyu çok genel bir biçimde sordu. Toplumsal sıralama üreten bir kural, yani bir sosyal refah fonksiyonu (SWF) düşünülsün. Böyle bir kuraldan beklenebilecek, ilk bakışta çok makul görünen dört koşul vardır.

Koşulların her birinin neden makul olduğu kısaca şöyle açıklanabilir. Evrensel alan, kuralın seçmenlerin ne düşündüğünü önceden kısıtlamamasını ve her durumda tutarlı bir sonuç vermesini ister; Condorcet döngüsü bu koşulun “geçişli sonuç” kısmını çoğunluk sıralaması için bozar. Pareto, oybirliğine saygıdır: bütün seçmenler aynı şeyi istiyorsa toplumun başka türlü karar vermesi için hiçbir neden yoktur. IIA, iki aday arasındaki kararın üçüncü bir adayın varlığından ya da yerinden etkilenmemesini ister; örneğin bir restoranda “balık ile tavuk arasında balığı seçerim” diyen birinin, menüye bir de makarna eklenince tavuğa geçmesi tuhaf olurdu. Diktatör yok koşulu ise en temel adalet beklentisidir.

Teoremin ispatı bu notun kapsamı dışındadır; okunabilir ispatlar İleri okuma kısmındaki kaynaklarda bulunur. Teoremin iki aday için geçerli olmadığına dikkat edilmelidir: iki adayda basit çoğunluk dört koşulu da sağlar. Bu durum 7.5.5'teki May teoreminin konusudur.

7.5.2Borda ve ilgisiz alternatifler

Borda sayımı evrensel alanı sağlar (her profilde puanlar toplanır ve bir sıralama çıkar), Pareto'yu sağlar (herkes x'i y'nin üstüne koyuyorsa her seçmen x'e daha çok puan verir) ve diktatörlük değildir. Arrow teoremine göre IIA'yı bozmak zorundadır. Bu kısımda bozulmanın nasıl gerçekleştiği örnek profil üzerinde gösterilir.

Neden böyle olur? 7.2.3'teki yoruma göre bir adayın Borda puanı, seçmenlerin onun altına koyduğu adayların sayısıdır. C çekilince her aday, C'yi kendi altına koyan her seçmenden 1 puan kaybeder. C'yi B'nin altına koyan seçmenler G1, G3 ve G4'tür: 4 + 3 + 2 = 9 kişi; B 22 − 9 = 13'e iner. C'yi D'nin altına koyanlar yalnızca G1 ve G3'tür: 7 kişi; D 21 − 7 = 14'e iner. A'nın altına C'yi koyanlar G1 ve G4'tür: 6 kişi; A 18 − 6 = 12'ye iner. C, B'ye D'den daha çok “ara puan” kazandırıyordu; C çekilince bu fark kaybolur. Borda puanı, iki aday arasındaki mesafeyi (aralarında kaç aday olduğunu) ölçer; bu mesafe de öteki adaylara bağlıdır. IIA ise yalnızca iki adayın göreli sırasına bakılmasını ister.

IIA, aday kümesi değişmeden de bozulabilir. 4 kişilik A ≻ D ≻ B ≻ C grubu yalnızca C ile B'nin yerini değiştirsin ve A ≻ D ≻ C ≻ B desin. Bu seçmenlerin B–D sırası değişmez (D hâlâ B'nin önündedir). Ama B'nin puanı her biri için 1'den 0'a düşer: B 22'den 22 − 4 = 18'e iner. D 21'de kalır; C ise 17 + 4 = 21'e çıkar. B–D toplumsal sırası yine döner. Değişen tek şey C'nin yeri olduğu hâlde B ile D'nin toplumsal sırası değişmiştir.

7.5.3Arrow teoreminin pratik anlamı

Arrow teoremi sık sık yanlış yorumlanır. Söyledikleri ile söylemedikleri ayrılmalıdır.

• Söylediği: toplu karar kuralları bütün makul ölçütleri aynı anda sağlayamaz; her kural bir koşuldan ödün verir.
• Söylemediği: oylamanın anlamsız olduğunu söylemez. Belirli bir kuralı yasaklamaz ya da önermez. Kuralların çoğu profilde makul sonuç verdiğini de inkâr etmez; yalnızca bir koşulun bazı profillerde bozulacağını söyler.
• Kim neyden ödün verir? Borda IIA'dan ödün verir (7.5.2). Condorcet ya da çoğunluk sıralaması geçişlilikten, dolayısıyla evrensel alanın “geçişli sonuç” şartından ödün verir (döngü). Diktatörlük ise adaletten ödün verir.
• Kurumlar için: hangi ölçüte öncelik verildiği açıkça belirlenmeli ve belgelenmelidir. Bir kural seçmek, hangi kusuru kabul edeceğini seçmektir.

Teoremden kaçış yolları koşulları gevşetmektir. Birincisi tercih alanını kısıtlamaktır: bütün profillere değil, yalnızca belirli bir yapıya sahip profillere izin verilirse olumlu sonuçlar mümkündür. Bunun en önemli örneği tek tepeli tercihlerdir (7.5.6). İkincisi sıralama yerine yoğunluk bilgisi kullanmaktır. Arrow'un çerçevesinde seçmen yalnızca sıralama bildirir; “A'yı B'ye biraz tercih ederim” ile “A'yı B'ye çok tercih ederim” arasında fark yoktur. Puanlamalı oylama ya da para gibi yoğunluk bilgisi taşıyan araçlar bu çerçevenin dışındadır.

7.5.4Gibbard–Satterthwaite teoremi

Arrow teoremi toplumsal sıralamalar hakkındadır ve stratejik davranışla doğrudan ilgilenmez. Stratejik oy sorusunu ise Allan Gibbard (1973) ve Mark Satterthwaite (1975) birbirinden bağımsız olarak yanıtladı. Teoremin ifadesi için iki koşul gerekir.

Stratejiye dayanıklılık tanımı oyun kuramı diliyle şöyle okunur: dürüst pusula her seçmen için baskın stratejidir. Öteki seçmenler ne bildirirse bildirsin, seçmenin gerçeği söylemesi en az yalan söylemesi kadar iyidir. Teorem, bu güçlü özelliğin üç ya da daha fazla adayda yalnızca diktatörlükte mümkün olduğunu söyler. Diktatörlük gerçekten stratejiye dayanıklıdır: diktatörün birinci tercihi kazanır, diktatör yalan söylemekle bir şey kazanmaz, öteki seçmenlerin pusulası ise sonucu hiç etkilemez.

Örnek profil teoremi somutlaştırır. Çoğullukta 3. grubun C'ye verdiği taktik oy (7.4.1) ve Borda'da B'nin gömülmesi (7.4.2) bu iki kuralın stratejiye dayanıklı olmadığının kanıtlarıdır. Teorem, bunun bu kuralların bir kusuru olmadığını, diktatörlük dışındaki her örten kuralın bir profilde manipüle edilebildiğini söyler.

Arrow ile ilişkisi: Arrow teoremi sıralamalar, Gibbard–Satterthwaite tek kazanan hakkındadır. İki teorem yakından bağlıdır; Gibbard–Satterthwaite teoremi Arrow teoreminden türetilebilir. Mekanizma tasarımı açısından anlamı şudur: parasız ortamda, üç ve daha fazla seçenek arasında seçim yapan genel bir teşvik uyumlu kural yoktur. Para kullanılabildiğinde durum değişir; ödemeler, yalan söylemenin bedelini ayarlamaya izin verir ve VCG mekanizması gibi stratejiye dayanıklı mekanizmalar mümkün olur.

Tasarımın hedefi, bu yüzden, stratejik davranışı yok etmek değil sınırlandırmaktır. Bunun üç yolu sık kullanılır: seçmenlerin öteki oylar hakkında az bilgiye sahip olması (manipülasyon için profil bilgisi gerekir), manipülasyonu hesaplamanın zor olması (7.6.1) ve tercih alanının kısıtlanması (7.5.6).

7.5.5May teoremi: iki aday için basit çoğunluk

Arrow ve Gibbard–Satterthwaite teoremlerinin ikisi de en az üç aday gerektirir. İki aday olduğunda durum çok daha iyidir. Kenneth May (1952), iki aday (x ve y) varken hangi kuralın “adil” olduğunu sordu ve üç koşulu sağlayan tek kuralın basit çoğunluk olduğunu gösterdi. Basit çoğunlukta (simple majority) daha çok oy alan aday kazanır; oylar eşitse sonuç beraberliktir.

Teoremin bir yönü kolayca görülür: basit çoğunluk üç koşulu da sağlar. Anonimdir, çünkü sonuç yalnızca her adayın kaç oy aldığına bağlıdır; hangi seçmenin hangi oyu verdiği sayıları değiştirmez. Tarafsızdır, çünkü her seçmen x ile y'yi yer değiştirince iki adayın oy sayıları da yer değiştirir ve kazanan da yer değiştirir. Pozitif duyarlıdır, çünkü beraberlikte bir seçmenin x'e geçmesi x'i bir oy öne geçirir; x zaten öndeyse farkı büyütür. Teoremin asıl gücü öteki yöndedir: bu üç koşulu sağlayan başka bir kural yoktur. Her koşulun neden gerekli olduğu, onu bozan kurallarla görülür.

Nitelikli çoğunluk (qualified majority) kuralları anayasa değişikliği gibi önemli kararlarda bilinçli olarak kullanılır; amaç, statükoyu kolayca değiştirilemez kılmaktır. May teoremi bunun bir bedeli olduğunu söyler: böyle bir kural iki seçeneğe eşit davranmaz. “Her zaman yazı-tura” kuralı ise oylara hiç tepki vermez; “tek sayıda oy alan kazanır” kuralında bir seçmenin x'e geçmesi x'in oy sayısını çiftten teke ya da tekten çifte çevirerek onu kaybettirebilir.

May teoreminin mesajı şudur: iki adayda kural tartışması biter, basit çoğunluk açık ara en doğal seçimdir. Zorluklar (döngü, Arrow, Gibbard–Satterthwaite) üç ve daha fazla adayla başlar.

7.5.6Kaçış yolu: tek tepeli tercihler

Arrow ve Gibbard–Satterthwaite teoremlerinin ortak varsayımı evrensel alandır: her olası tercih profiline izin verilir. Ama pek çok gerçek durumda tercihler rastgele değildir; belirli bir yapıları vardır. Bu yapılardan en önemlisi tek tepeliliktir.

Şekil 7.11'de her eğrinin tek bir zirvesi vardır ve eğri zirveden iki yana doğru alçalır. Örneğin bir belediye meclisinin parka ayıracağı bütçeyi oyladığı düşünülsün. Her üyenin aklında ideal bir miktar vardır; ondan çok fazla ya da çok az olan teklifler onu daha az memnun eder. Bu tür tercihler doğal olarak tek tepelidir.

Teoremin iki önemli sonucu vardır. Birincisi, tek tepeli profillerde Condorcet döngüsü olmaz; bu da gerçek tercihlerin çoğu zaman bir eksene göre düzenli olmasının döngüleri neden seyrek kıldığını açıklar. İkincisi, “tepeleri bildir, medyanı seç” kuralı stratejiye dayanıklıdır. Bir seçmen yanlış bir tepe bildirerek medyanı ancak kendi tepesinden uzaklaştırabilir. Tepesi medyanın solunda olan bir seçmen, tepesini daha sola bildirirse medyan değişmez; sağa, medyanın ötesine bildirirse medyan sağa, yani ondan uzağa kayar. Kendi tepesine yaklaştıracak hiçbir yalan yoktur.

Medyan seçmen teoremi Gibbard–Satterthwaite teoremini çiğnemez; varsayımlarından birini, evrensel alanı ortadan kaldırır. Teorem bütün profiller için konuşur; alan tek tepeli profillerle kısıtlanınca geçerliliğini yitirir. Mekanizma tasarımında tesis yerleşimi için kullanılan medyan mekanizması (median mechanism) bu fikrin uygulamasıdır: bir kütüphane ya da hastane bir caddeye yerleştirilecekse ve herkes en yakın konumu istiyorsa, bildirilen konumların medyanı seçilir ve kimse yanlış konum bildirerek kazanç sağlayamaz.

7.5.7Dört sonuç yan yana

Bu kısımdaki dört sonuç Tablo 7.17'de karşılaştırılmıştır.

Tablodaki “rastgele diktatör” kuralı açıklamaya değer: seçmenlerden biri kurayla seçilir ve onun birinci tercihi kazanır. Bu kural stratejiye dayanıklıdır (seçilen seçmen için yalan söylemek yalnızca kendi favorisini kaybettirir) ve hiçbir seçmen önceden diktatör değildir. Gibbard–Satterthwaite teoremi yalnızca belirlenimci (rastgelelik içermeyen) kurallar için geçerli olduğu için bu kural teoremin dışında kalır.

Arrow ve Gibbard–Satterthwaite teoremlerinde diktatörlük, varsayımların hepsi birlikte istendiğinde ortaya çıkar. Bir varsayım gevşeyince olumlu sonuçlar mümkün olur: iki aday (May), tek tepeli tercihler (Black), rastgelelik ya da para. Bu teoremlerin pratik değeri, tasarımcıya hangi kapıların kapalı, hangilerinin açık olduğunu göstermeleridir.

7.6Hesaplamalı sosyal seçim ve uygulamalar

Bu son kısım, sosyal seçimin bilgisayar bilimiyle buluştuğu noktayı ve kuramın gerçek kurumlardaki karşılıklarını ele alır: kuralların hesaplama maliyeti, önermeler üzerinde toplu karar verme, gerçek seçimlerde kullanılan kurallar ve birden çok sandalyenin dağıtıldığı nispi temsil.

7.6.1Hesaplamalı sosyal seçim

Hesaplamalı sosyal seçim (computational social choice), bilgisayar bilimi, ekonomi ve sosyal seçimin kesişimidir. Bu alanda kurallar yalnızca hangi ölçütleri sağladıklarına göre değil, hesaplama maliyetine göre de incelenir. Üç tür soru öne çıkar: kazananı hesaplamak ne kadar zordur, manipülasyonu hesaplamak ne kadar zordur ve kazananı belirlemek için seçmenlerden ne kadar bilgi toplamak gerekir?

Kazananı hesaplamak. Çoğulluk ve Borda, n seçmen ve m aday için O(nm) sürede hesaplanır; her pusula bir kez okunur (7.2.10). Copeland için önce ikili karşılaştırma tablosu doldurulur: m(m − 1)/2 çiftin her biri için n pusula taranır; süre O(nm²)'dir. Buna karşılık Kemeny kuralında ve Dodgson kuralında kazananı bulmak NP-zordur (Bartholdi, Tovey ve Trick, 1989). Dodgson kuralı (Dodgson rule), Alice Harikalar Diyarında'nın yazarı Lewis Carroll (gerçek adıyla Charles Dodgson) tarafından önerilmiştir: bir adayı Condorcet kazananı yapmak için pusulalarda en az sayıda komşu yer değiştirmesi (sıralamada yan yana iki adayın yerini değiştirmek) gereken aday kazanır. Condorcet kazananı varsa ona sıfır değişiklik gerekir ve o kazanır. Fikir doğaldır, ama bu en küçük sayıyı hesaplamak genel olarak çok zordur.

Burada bir ironi vardır: Condorcet ölçütlerini sağlayan ve döngüde de makul karar veren bazı kurallar (Kemeny, Dodgson), hesaplama açısından en pahalı kurallardır. Pratikte küçük aday sayılarında bu bir sorun değildir; büyük aday sayılarında ise yaklaşık algoritmalar ve tamsayılı programlama çözücüleri kullanılır.

Manipülasyonu hesaplamak. Gibbard–Satterthwaite teoremi manipülasyonun mümkün olduğunu söyler, ama kârlı bir yalan pusulayı bulmanın ne kadar zor olduğu ayrı bir sorudur. Tek bir manipülatör, çoğulluk ve Borda'da kârlı pusulayı açgözlü bir algoritmayla polinom sürede bulur: favorisini başa koyar, kalan sıraları da favorisini en az tehdit edecek biçimde doldurur. IRV'de ise bu sorun NP-zordur (Bartholdi ve Orlin, 1991). Bu zorluk, manipülasyona karşı bir “bariyer” sayılabilir. Ama bariyer yalnızca en kötü durum içindir: NP-zor bir problemin bazı örnekleri zor olsa da gerçek seçimlerde karşılaşılan örneklerin çoğu kolay çözülebilir.

Tercih çıkarımı. Bir seçmenin tam sıralamasını öğrenmek ne kadar bilgi gerektirir? m aday için m! farklı sıralama vardır. Her evet/hayır sorusu (bir bit) olası sıralamaların sayısını en iyi durumda yarıya indirir. Bu yüzden tam sıralama için en az log₂(m!) bit gerekir. m = 10 için 10! = 3 628 800 ve log₂(3 628 800) ≈ 21,8, yani yaklaşık 22 bittir. Büyük seçimlerde ya da çok adaylı çevrimiçi sistemlerde bu iletişim maliyeti önemlidir. Tercih çıkarımı (preference elicitation), seçmenlere adım adım sorular sorup yalnızca kazananı belirlemeye yetecek bilgiyi toplamayı inceler. Örneğin çoğullukta yalnızca birinci tercih yeterlidir; tam sıralamayı sormak gereksizdir.

Alanın iki konusu daha vardır: adil bölüşüm (bölünebilir ya da bölünemez kaynakları kıskançlık yaratmadan paylaştırmak) ve yargı birleştirme. İkincisi bir sonraki kısımda kısaca ele alınır.

7.6.2Yargı birleştirme: doktrin paradoksu

Oylama yalnızca adaylar arasında seçim yapmak için kullanılmaz. Bir mahkeme heyeti, bir yönetim kurulu ya da bir bilim kurulu çoğu zaman önermeler hakkında karar verir: “sözleşme geçerli mi?”, “sözleşme ihlal edildi mi?”. Bireysel yargıları toplu bir yargıya dönüştürmeye yargı birleştirme (judgment aggregation) denir.

Üç yargıçlı bir mahkeme düşünülsün. Davalı, ancak p (sözleşme geçerli) ve q (sözleşme ihlal edildi) önermelerinin ikisi de doğruysa tazminat öder. Sonuç önermesi p ∧ q'dur (“p ve q”).

Her yargıç kendi içinde tutarlıdır: 1. yargıç iki gerekçeyi de kabul eder ve tazminata hükmeder; 2. ve 3. yargıçlar gerekçelerden birini reddeder ve tazminata karşı çıkar. Ama önermeler tek tek oylanınca çoğunluk “p doğru, q doğru, p ∧ q yanlış” der. Bu mantıksal olarak tutarsız bir toplu yargıdır. Bu duruma doktrin paradoksu (doctrinal paradox, discursive dilemma; Kornhauser ve Sager, 1986) denir.

Paradoksun pratik sonucu, kararın usule bağlı olmasıdır. Mahkeme gerekçelere göre karar verirse (önce p ve q ayrı ayrı oylanır, sonuç bunlardan çıkarılır) davalı öder. Sonuca göre karar verirse (doğrudan p ∧ q oylanır) davalı ödemez. Aynı yargılardan iki farklı karar çıkar. Bu durum, Condorcet döngüsünün yargılardaki karşılığıdır: bireyler tutarlıdır, çoğunluk tutarsızdır.

List ve Pettit (2002) bu gözlemi bir teoreme dönüştürdü: anonim, sistematik (her önerme aynı yöntemle ve yalnızca o önermeye verilen oylara göre karara bağlanır) ve her zaman tutarlı bir toplu yargı üreten bir birleştirme kuralı yoktur. Bu, Arrow teoreminin yargılar için karşılığıdır.

7.6.3Gerçek dünyada oylama kuralları

Bu bölümdeki kuralların hepsi gerçek kurumlarda kullanılır:

• İki turlu sistem: Türkiye ve Fransa'da cumhurbaşkanlığı seçimleri. İlk turda mutlak çoğunluk sağlanamazsa ilk iki aday ikinci turda yarışır.
• Anında ikinci tur: Avustralya Temsilciler Meclisi seçimleri ve bazı ABD şehirleri. Seçmen tam sıralama verir.
• Çoğulluk: Birleşik Krallık ve ABD'de tek üyeli seçim bölgeleri. Her bölgede en çok oyu alan aday seçilir.
• Borda benzeri puanlama: Eurovision şarkı yarışmasında her ülke beğendiği şarkılara 12, 10, 8, 7, … puan verir; spor ödüllerinde (örneğin en değerli oyuncu oylamalarında) da benzer puanlama kullanılır.
• Onay: bazı bilimsel dernek seçimleri; “uygun olduğum saatler” anketleri.
• Çevrimiçi: Reddit ve forum oylamaları, topluluk anketleri, sınıf ve kulüp kararları.

Eurovision'un puan vektörü (12, 10, 8, 7, 6, 5, 4, 3, 2, 1, 0, …) bir pozisyonel puanlama kuralıdır. Birinci sıraya ikinciden 2 puan fazla verilmesi, birinci tercihi Borda'dan biraz daha çok ödüllendirmek içindir. Bu tasarım seçimi de 7.2.5'teki tartışmanın bir örneğidir: puan vektörü, uzlaşmacı adaylar ile güçlü bir taban desteği olan adaylar arasındaki dengeyi belirler.

7.6.4Birden çok sandalye: nispi temsil ve D'Hondt

Şimdiye kadar tek bir kazanan seçildi. Meclis seçimlerinde ise bir seçim çevresinden birden çok, örneğin S sandalye dağıtılır. Bu durumda amaç bir kazanan bulmak değil, sandalyeleri partiler arasında paylaştırmaktır. Nispi temsil (proportional representation) ilkesine göre her partinin sandalye payı oy payına yakın olmalıdır. Sandalyeler tamsayı olduğu için tam orantı genellikle mümkün değildir ve yuvarlamanın nasıl yapılacağı bir yöntem seçimidir.

Türkiye'de milletvekili seçimlerinde her seçim çevresinde D'Hondt yöntemi uygulanır; buna ek olarak ülke genelinde bir baraj vardır.

Bölme işleminin bir yorumu vardır: bir partinin k. bölümü, o partinin zaten k − 1 sandalyesi varken bir sandalye daha alırsa “sandalye başına düşen oy” miktarıdır. Her sandalye, o an sandalye başına en çok oyu temsil edecek partiye verilir. Sonuçta A %42 oyla sandalyelerin %50'sini alır; D %12 oyla hiç sandalye alamaz. D'Hondt büyük partileri hafifçe kayırır.

Başka bir yöntem en büyük kalan (largest remainder; Hare) yöntemidir. Her partinin “hak ettiği” sandalye sayısı, oy payı × S olarak hesaplanır: A 0,42 × 6 = 2,52, B 0,31 × 6 = 1,86, C 0,15 × 6 = 0,90, D 0,12 × 6 = 0,72. Her parti önce bu sayının tam kısmı kadar sandalye alır: A 2, B 1, C 0, D 0; toplam 3. Kalan 3 sandalye, küsuratı en büyük olan partilere birer birer verilir: C (0,90), B (0,86), D (0,72). A'nın küsuratı (0,52) en küçüğüdür. Sonuç: A 2, B 2, C 1, D 1. Aynı oylarla D'Hondt A'ya 3, en büyük kalan yöntemi ise D'ye 1 sandalye verir.

Tek kazananlı kurallardaki gibi burada da her yöntem bir ödünleşimdir. D'Hondt hükümet kararlılığını, yani büyük partilerin çoğunluk kurabilmesini öne çıkarır; en büyük kalan yöntemi küçük partilerin temsilini öne çıkarır.

7.6.5Hangi oylama kuralı adil?

Bölümün bütün sonuçları bu soruya tek bir cevap olmadığını gösterir. Adalet değerlendirmesi temsil, çoğunluk desteği, azınlıkların korunması ve stratejik dayanıklılık gibi ölçütlere bağlıdır ve bu ölçütler birbiriyle çatışır.

• Çoğulluk basittir ve hızlıdır, ancak oy bölünmesine ve çoğunluk desteği olmayan bir kazanana yol açabilir (örnek profilde A, oyların 6/13'üyle).
• Borda daha fazla tercih bilgisi kullanır ve uzlaşmacı adayı öne çıkarır (B), ancak stratejik sıralamaya, özellikle gömmeye açıktır.
• Anında ikinci tur çoğunluk desteği arar, fakat monotonluk ve stratejik oy sorunlarını tamamen çözmez.
• Condorcet yöntemleri ikili çoğunluğa saygı gösterir, ama döngüde ek bir kurala ihtiyaç duyar; Kemeny gibi döngüde de karar verenlerin hesaplanması zordur.

Kural seçimi kararın bağlamına ve öncelikli ölçütlere göre yapılmalıdır. Bir kulüp başkanlığı için hızlı ve anlaşılır bir çoğulluk yeterli olabilir; aday sayısı fazla olan bir sınıf etkinliği seçimi için sıralamalı bir kural (Borda ya da bir Condorcet yöntemi) daha dengeli sonuç verebilir. Önemli olan, kuralın oylamadan önce açıkça belirlenmesi ve hangi kusurların kabul edildiğinin bilinmesidir.

7.7Özet

• Sosyal seçim, bireysel tercihleri (tercih profili) toplu bir karara (SCF) ya da toplumsal bir sıralamaya (SWF) dönüştüren kuralları inceler. Oy pusulası seçmenin stratejisidir; oylama parasız bir mekanizma tasarımı problemidir.
• Kurallar: mutlak çoğunluk, çoğulluk, iki turlu sistem, Borda, onay, pozisyonel puanlama, anında ikinci tur, Condorcet, Copeland, maksimin ve Kemeny. 13 seçmenli örnek profilde bu kurallar dört farklı kazanan verir: çoğulluk A, iki tur ve IRV C, Borda ve 2-onay B, Condorcet ve Kemeny D.
• Condorcet paradoksu: geçişli bireysel tercihler döngüsel bir toplumsal tercih üretebilir (A ≻ B ≻ C ≻ A). Döngüde gündemi kontrol eden sonucu seçer; sona bırakılan aday kazanır. Kemeny en zayıf çoğunluğu bozar, ama hesaplanması NP-zordur.
• Ölçütler: çoğulluk Condorcet kaybedenini seçebilir; Borda ve IRV Condorcet kazananını seçmeyebilir; IRV monoton değildir; Copeland ve Kemeny Condorcet tutarlıdır.
• Stratejik oy: çoğullukta taktik oy (oy bölünmesinden kaçmak), Borda'da gömme. Dürüstlük her kuralda en iyi strateji değildir; gömme geri de tepebilir.
• Arrow: en az 3 adayda evrensel alan, Pareto, IIA ve diktatör yok koşulları birlikte sağlanamaz. Borda IIA'yı bozar.
• Gibbard–Satterthwaite: en az 3 adayda stratejiye dayanıklı ve örten her kural diktatörlüktür.
• May ve tek tepelilik: 2 adayda basit çoğunluk, anonimlik, tarafsızlık ve pozitif duyarlılığı sağlayan tek kuraldır. Tek tepeli tercihlerde medyan seçmenin tepesi Condorcet kazananıdır ve medyan kuralı stratejiye dayanıklıdır.
• Hesaplamalı sosyal seçim: çoğulluk ve Borda O(nm), Copeland O(nm²); Kemeny ve Dodgson NP-zor; IRV'de manipülasyon NP-zor. Doktrin paradoksu, döngünün yargılardaki karşılığıdır. D'Hondt büyük partileri hafifçe kayırır.

7.8Kavram listesi

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

• sosyal seçim social choice
• tercih profili preference profile
• oy pusulası ballot
• geçişlilik transitivity
• sosyal refah fonksiyonu social welfare function (SWF)
• mutlak çoğunluk majority rule
• çoğulluk plurality rule
• iki turlu sistem two-round (runoff) system
• Borda sayımı Borda count
• onay oylaması approval voting
• pozisyonel puanlama kuralı positional scoring rule
• k-onay k-approval
• 2-onay 2-approval
• veto kuralı veto rule
• anında ikinci tur instant-runoff voting (IRV)
• Condorcet kazananı Condorcet winner
• Condorcet kaybedeni Condorcet loser
• ikili çoğunluk çizgesi pairwise majority graph
• turnuva tournament
• Copeland kuralı Copeland rule
• eşitlik bozma kuralı tie-breaking rule
• Condorcet paradoksu / döngüsü Condorcet paradox / cycle
• ikili elemeli oylama sequential pairwise voting
• gündem (manipülasyonu) agenda (manipulation)
• Kemeny kuralı Kemeny rule
• sıralama birleştirme rank aggregation
• monotonluk monotonicity
• maksimin (Simpson) kuralı maximin (Simpson) rule
• stratejik oy strategic voting
• taktik oy tactical voting (plurality)
• oy bölünmesi vote splitting
• Duverger yasası Duverger's law
• gömme burying
• Arrow'un imkânsızlık teoremi Arrow's impossibility theorem
• evrensel alan unrestricted domain
• Pareto (oybirliği) koşulu Pareto (unanimity) condition
• ilgisiz alternatiflerden bağımsızlık independence of irrelevant alternatives (IIA)
• diktatör yok non-dictatorship
• Gibbard–Satterthwaite teoremi Gibbard–Satterthwaite theorem
• örtenlik surjectivity (onto)
• May teoremi May's theorem
• basit çoğunluk simple majority
• anonimlik anonymity
• tarafsızlık neutrality
• pozitif duyarlılık positive responsiveness
• nitelikli çoğunluk qualified majority
• tek tepeli tercihler single-peaked preferences
• medyan seçmen teoremi median voter theorem
• medyan mekanizması median mechanism
• hesaplamalı sosyal seçim computational social choice
• Dodgson kuralı Dodgson rule
• tercih çıkarımı preference elicitation
• yargı birleştirme judgment aggregation
• doktrin paradoksu doctrinal paradox
• nispi temsil proportional representation
• D'Hondt yöntemi D'Hondt method
• en büyük kalan (Hare) yöntemi largest remainder (Hare) method

7.9Kendini Dene

1. 11 seçmen: 5 × A ≻ B ≻ C, 4 × B ≻ C ≻ A, 2 × C ≻ B ≻ A. Mutlak çoğunluk, çoğulluk, IRV, Borda (2, 1, 0) ve Condorcet kazananları kimdir? Profilde Condorcet kaybedeni var mı?

   Cevap

   Birinci tercihler A 5, B 4, C 2. Eşik 6'dır; 5 < 6 olduğundan mutlak çoğunluk kazananı yoktur. Çoğulluk A'yı seçer. IRV: C (2) elenir, oyları sıradaki B'ye geçer; B 4 + 2 = 6, A 5; B kazanır. Borda: A 5 × 2 = 10, B 5 × 1 + 4 × 2 + 2 × 1 = 15, C 4 × 1 + 2 × 2 = 8; B kazanır. İkili: B – A 6 – 5, B – C 9 – 2, C – A 6 – 5. B Condorcet kazananıdır. A her iki rakibine 5 – 6 yenilir: Condorcet kaybedenidir ve çoğulluk tam olarak onu seçmiştir.

2. Aynı profilde s = (1, a, 0) puanlama kuralları (0 ≤ a ≤ 1) ele alınsın. Her adayın puanı a cinsinden nedir? Hangi a değerlerinde A kazanır? C hiç kazanabilir mi?

   Cevap

   A hiçbir sıralamada ikinci değildir: A = 5. B, 4 seçmenin birinci, 5 + 2 = 7 seçmenin ikinci tercihidir: B = 4 + 7a. C, 2 seçmenin birinci, 4 seçmenin ikinci tercihidir: C = 2 + 4a. A'nın B'yi geçmesi için 5 > 4 + 7a, yani a < 1/7 gerekir (a = 1/7'de A ile B eşittir). Bu aralıkta A, C'yi de geçer (5 > 2 + 4a). C hiçbir a için kazanamaz, çünkü her a ≥ 0 için 4 + 7a > 2 + 4a'dır.

3. Aynı profilde dürüst çoğulluk kazananı A'dır. (a) C ≻ B ≻ A diyen 2 seçmen çoğullukta nasıl oy vererek kendi tercihlerine göre daha iyi bir sonuç alır? (b) Borda (2, 1, 0) kullanılıyorsa, A seçmenleri asıl rakip B'yi gömüp A ≻ C ≻ B bildirirse ne olur?

   Cevap

   (a) C'nin (2 oy) kazanma şansı yoktur. Bu iki seçmen B'ye oy verirse B 4 + 2 = 6, A 5 olur ve B kazanır. Gerçek sıralamaları C ≻ B ≻ A'ya göre B, A'dan iyidir: taktik oy kârlıdır. (b) Her A seçmeni için B 1 yerine 0, C 0 yerine 1 puan alır: B 15 − 5 = 10, C 8 + 5 = 13, A 10. C kazanır. C, A seçmenlerinin en kötü adayıdır; gömme geri tepmiştir.

4. 7 seçmen: 3 × A ≻ B ≻ C, 2 × B ≻ C ≻ A, 2 × C ≻ A ≻ B. İkili karşılaştırmaların sonuçları, Kemeny sıralaması ve maksimin kazananı nedir? İkili elemeli oylamada B'nin kazanması için gündem nasıl kurulmalıdır?

   Cevap

   A – B: 3 + 2 = 5 – 2, A ≻ B. B – C: 3 + 2 = 5 – 2, B ≻ C. C – A: 2 + 2 = 4 – 3, C ≻ A. Bir döngü vardır. Uyum skorları: A ≻ B ≻ C 5 + 3 + 5 = 13, B ≻ C ≻ A 11, C ≻ A ≻ B 11, A ≻ C ≻ B 10, B ≻ A ≻ C 10, C ≻ B ≻ A 8. Kemeny sıralaması A ≻ B ≻ C'dir; en zayıf çoğunluk C ≻ A (4 – 3) bozulur. Maksimin: A'nın en kötü karşılaştırması 3 (C'ye karşı), B'ninki 2, C'ninki 2; A kazanır. B'nin kazanması için B sona bırakılır: önce A – C (C 4 – 3 kazanır), sonra C – B (B 5 – 2 kazanır).

5. İki seçenekli (x ve y) kararlar için üç kural önerilir: (i) “Başkanın oyu iki sayılır, en çok oy alan kazanır”; (ii) “y'nin kabulü için oyların en az ⅗'ü gerekir, yoksa x kalır”; (iii) “x'e verilen oy sayısı çiftse x, tekse y kazanır”. Her biri May teoreminin hangi koşulunu ihlal eder?

   Cevap

   (i) Anonimlik: başkan ile başka bir üyenin oyları yer değiştirince sonuç değişebilir. (ii) Tarafsızlık: iki seçenek simetrik değildir. Örneğin 11 üyede 6 üye y, 5 üye x derse 6/11 < 3/5 olduğundan x kalır. Oylar ters çevrilince (6 üye x, 5 üye y) yine x kalır; sonuç ters dönmez. (iii) Pozitif duyarlılık: x kazanırken bir seçmenin x'e geçmesi sayıyı tekleştirir ve x'i kaybettirir.

6. Tek tepeli tercihli 7 seçmenin tepeleri bir eksende 1, 1, 2, 4, 6, 9, 10'dur. Condorcet kazananı hangi konumdur? Tepelerin ortalaması nedir? “Tepeleri bildir, medyanı seç” kuralında tepesi 10 olan seçmen tepesini 20 ya da 3 diye bildirirse sonuç ne olur?

   Cevap

   Medyan, sıralı listenin dördüncü değeridir: 4. Medyan seçmen teoremine göre Condorcet kazananı 4'tür. Ortalama 33/7 ≈ 4,71'dir; 4 ile 4,71 karşılaştırılınca tepeleri 1, 1, 2, 4 olan 4 seçmen 4'ü seçer. Seçmen 20 bildirirse liste 1, 1, 2, 4, 6, 9, 20 olur ve medyan yine 4'tür; abartma işe yaramaz. 3 bildirirse liste 1, 1, 2, 3, 4, 6, 9 olur ve medyan 3'e iner; sonuç bu seçmenin tepesinden daha da uzaklaşır. Yalan söylemek kazandırmaz.

7. 7 sandalye; oylar A 47 000, B 33 000, C 20 000. D'Hondt ve en büyük kalan (Hare) yöntemleriyle sandalye dağılımı nedir?

   Cevap

   D'Hondt bölümleri: A 47 000, 23 500, 15 667, 11 750; B 33 000, 16 500, 11 000; C 20 000, 10 000. En büyük yedi bölüm 47 000 (A), 33 000 (B), 23 500 (A), 20 000 (C), 16 500 (B), 15 667 (A), 11 750 (A): A 4, B 2, C 1. Hare: hak edilen sayılar A 0,47 × 7 = 3,29, B 2,31, C 1,40; tam kısımlar 3, 2, 1 (toplam 6). Kalan 1 sandalye en büyük küsurata (C, 0,40) gider: A 3, B 2, C 2. D'Hondt büyük partiye bir sandalye fazla verir.

8. 8 adaylı bir Kemeny sayımı kaba kuvvetle yapılacaktır. Kaç sıralama denenir ve her sıralamada kaç çift incelenir? Bir seçmenin tam sıralamasını öğrenmek için en az kaç bit gerekir?

   Cevap

   8! = 40 320 sıralama denenir. Her sıralamada 8 · 7 / 2 = 28 çift vardır; toplam 40 320 × 28 = 1 128 960 çift değerlendirmesi (her biri n grup taraması) gerekir. Tam sıralama log₂(8!) = log₂(40 320) ≈ 15,3, yani en az 16 bit gerektirir (bit sayısı tamsayı olmalıdır).

7.10İleri okuma

• F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. D. Procaccia (ed.), Handbook of Computational Social Choice, Cambridge University Press, 2016. Hesaplamalı sosyal seçimin temel kaynağıdır; Kemeny, Dodgson, manipülasyonun karmaşıklığı ve yargı birleştirme bölümleri bu notun konularını ayrıntılandırır.
• D. Easley, J. Kleinberg, Networks, Crowds, and Markets, Cambridge University Press, 2010, Bölüm 23 (Voting). Arrow teoreminin kısa ve okunabilir bir ispatını ve tek tepeli tercihleri az matematikle anlatır.
• A. Karlin, Y. Peres, Game Theory, Alive, AMS, 2017. Sosyal seçim ve oylama bölümü Arrow ve Gibbard–Satterthwaite teoremlerinin ispatlarını verir.
• N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory, Cambridge University Press, 2007, Bölüm 9. Sosyal seçimi mekanizma tasarımı çerçevesine yerleştirir ve Gibbard–Satterthwaite teoreminin ispatını içerir.

7.11Kaynaklar

1. K. J. Arrow, Social Choice and Individual Values, Wiley, 1951.
2. M. Balinski, H. P. Young, Fair Representation, Yale University Press, 1982.
3. J. J. Bartholdi, J. B. Orlin, “Single transferable vote resists strategic voting”, Social Choice and Welfare 8(4), 1991.
4. J. J. Bartholdi, C. A. Tovey, M. A. Trick, “The computational difficulty of manipulating an election”, Social Choice and Welfare 6, 1989.
5. J. J. Bartholdi, C. A. Tovey, M. A. Trick, “Voting schemes for which it can be difficult to tell who won the election”, Social Choice and Welfare 6, 1989.
6. D. Black, “On the rationale of group decision-making”, Journal of Political Economy 56(1), 1948.
7. F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. D. Procaccia (ed.), Handbook of Computational Social Choice, Cambridge University Press, 2016.
8. C. Dwork, R. Kumar, M. Naor, D. Sivakumar, “Rank aggregation methods for the web”, WWW, 2001.
9. D. Easley, J. Kleinberg, Networks, Crowds, and Markets, Cambridge University Press, 2010 (Bölüm 23).
10. A. Gibbard, “Manipulation of voting schemes: a general result”, Econometrica 41(4), 1973.
11. G.-Th. Guilbaud, “Les théories de l'intérêt général et le problème logique de l'agrégation”, Économie appliquée 5(4), 1952.
12. A. Karlin, Y. Peres, Game Theory, Alive, AMS, 2017.
13. J. G. Kemeny, “Mathematics without numbers”, Daedalus 88(4), 1959.
14. L. A. Kornhauser, L. G. Sager, “Unpacking the court”, Yale Law Journal 96(1), 1986.
15. C. List, P. Pettit, “Aggregating sets of judgments: an impossibility result”, Economics and Philosophy 18(1), 2002.
16. K. O. May, “A set of independent necessary and sufficient conditions for simple majority decision”, Econometrica 20(4), 1952.
17. N. Nisan, T. Roughgarden, É. Tardos, V. Vazirani (ed.), Algorithmic Game Theory, Cambridge University Press, 2007 (Bölüm 9).
18. M. Regenwetter, B. Grofman, A. A. J. Marley, I. M. Tsetlin, Behavioral Social Choice, Cambridge University Press, 2006.
19. M. A. Satterthwaite, “Strategy-proofness and Arrow's conditions”, Journal of Economic Theory 10, 1975.

Ders sayfaları: Procaccia 15-896 (CMU) · Shah CSC304 (Toronto) · © Sercan Külcü. Tüm hakları saklıdır.