Katılımcı bütçeleme algoritması - Participatory budgeting algorithm

Bir katılımcı bütçeleme (PB) algoritması uygulamak için bir algoritmadır katılımcı bütçeleme.

Bir PB algoritmasının girdileri şunlardır: olası bir liste projeler finansman gerektiren, mevcut toplam bütçe projeleri finanse etmek için ve seçmenlerin tercihleri proje üzerinde. Bir PB algoritmasının çıktısı, projeler arasında bütçenin bir bölümüdür - her projeye ne kadar para tahsis edileceğini belirler.

Bir PB algoritması, projeleri şu şekilde ele alabilir: bölünebilir veya bölünmez:

  • Bir bölünebilir PB algoritması, tahsislerin toplamı bütçeye eşit olduğu sürece herhangi bir projeye herhangi bir miktarda para tahsis edebilir. Yardım bağışları gibi her ek doların etkin bir şekilde kullanılabileceği projeler için uygundur.
  • Bir bölünmez PB algoritması ek girdi olarak projelerin maliyetini alır. Seçilen projelerin toplam maliyeti bütçeyi aşmayacak şekilde projelerin bir alt kümesini döndürür. Seçilen her projeye tüm maliyeti tahsis edilirken, seçilmeyen her projeye hiçbir şey tahsis edilmez. Yeni binalar inşa etmek gibi faaliyet göstermesi için tamamen finanse edilmesi gereken projeler için daha uygundur.

Giriş biçimleri

Bir PB algoritması tasarlarken önemli bir husus, hangi giriş formatının kullanılacağıdır. tercih ortaya çıkarma - her seçmenin projeler üzerindeki tercihlerini nasıl ifade etmesi gerektiği.[1] Pratikte kullanılan birkaç girdi biçimi şunlardır:

  • Onay oylaması: her seçmen "onayladıkları" (değerli olarak kabul ettikleri) projelerin bir alt kümesini belirtirken diğerleri onaylanmamış olarak değerlendirilir. Bu, her seçmenin her projeyi 1 veya 0 olarak puanlayabildiği ikili bir puanlama sistemi gibidir.[2][3]
  • k-onay oylaması: her seçmen, en üst düzeyinin bir alt kümesini belirtir k projeler - the k en değerli olduğunu düşündükleri projeler.
  • Eşik onay oylaması: bir eşik değeri verildiğinde ther seçmen, en az değer verdiği tüm projelerin alt kümesini belirtir. t.
  • Dereceli oylama: her seçmen, projeler üzerinde tam bir tercih ilişkisini belirtir, en değerli, 2'nci-en değerli olduğunu düşündükleri projeyi vb. belirtir.

Bu girdi formatları, projelerin farklı maliyetlerini göz ardı ettikleri için bölünmez PB için sorunludur. Maliyetleri dikkate alan bazı yeni girdi biçimleri şunlardır:[1]

  • Sırt çantası oylama: her seçmen, alt kümedeki projelerin toplam maliyetinin (alt kümede kaç proje olduğuna bakılmaksızın) en fazla bütçe olacak şekilde projelerin bir alt kümesini belirtir. Bu nedenle, her seçmen bir bireyi çözmek zorundadır sırt çantası sorunu - bütçe kısıtı altında kişisel faydalarını maksimize eden alt kümenin bulunması. Sırt çantası oylamasının bir avantajı, algoritmanın her projeyi aldığı oy sayısına göre puanlaması ve bütçesi dolana kadar azalan puan sırasına göre açgözlülükle projeleri seçmesi durumunda sırt çantası oylamasının kısmen doğru mekanizma.
  • Paranın karşılığı sıralaması: Her seçmen projeleri toplam değerine göre değil, değer / maliyet oranına göre sıralar.

Çeşitli girdi biçimleri, aşağıdakilere göre karşılaştırılabilir: zımni faydacı oylama - her girdi formatının, yardımcı programların toplamını maksimize etmede ne kadar yararlı olduğu. Bu perspektiften, eşik onay oylaması sırt çantasıyla oylama, değere göre sıralama ve paranın değerine göre sıralamadan daha üstündür: hem teorik hem de ampirik olarak maksimum fayda toplamından kaynaklanan bozulmayı en aza indirir.[4]

Sistem vatandaşların girdilerini aldıktan sonra bir bütçe hesaplamalıdır. Bir bütçenin değerlendirilebileceği çeşitli kriterler vardır.

Sırt çantası bütçeleme

Uygulamada en yaygın olan bütçeleme yöntemi, bir varyantına açgözlü bir çözümdür. sırt çantası sorunu: Projeler, aldıkları oy sayısının azaltılmasıyla sıralanır ve bütçe dolana kadar tek tek seçilir. Alternatif olarak, proje sayısı yeterince küçükse, vatandaşların toplam mutluluğunu en üst düzeye çıkaran bir proje alt kümesi seçilerek sırt çantası sorunu tam olarak çözülebilir.[1][4] Bu yöntemin dezavantajı, genellikle bireysel olarak en iyi sırt çantası bütçelemeazınlıklara karşı haksızlık olabilir: nüfusun% 51'i 10 projeyi ve% 49'u diğer 10 projeyi destekliyorsa ve para sadece 10 projeye yetiyorsa, sırt çantası bütçeleme% 51'in desteklediği 10 projeyi seçecektir, ve% 49'u tamamen görmezden gelin.[5]

Bireysel olarak en iyi sırt çantasına iki alternatif:

  • Çeşitli sırt çantası - Bütçede en az bir tercih edilen kalemi olan vatandaşların sayısını maksimize etmek (aynı şekilde Chamberlin-Courant kuralı için çok kazananlı oylama ).
  • Nash'e uygun sırt çantası - vatandaşların hizmetlerinin ürününü maksimize etmek.

Ne yazık ki, genel fayda alanları için bu kuralların her ikisinin de hesaplanması NP açısından zordur.[5] Bununla birlikte, çeşitli sırt çantaları, belirli tercih alanlarında veya seçmen sayısı az olduğunda polinomik olarak çözülebilir.

Çoğunluk bütçeleme

Böyle bir kriter, Condorcet kriteri: Seçmenlerin çoğunluğuna göre, seçilen bütçe en az önerilen diğer bütçe kadar iyi olmalıdır (önerilen hiçbir değişiklik oylar arasında çoğunluk desteğine sahip değildir). Böyle bir bütçeyi bulmak için polinom zaman algoritması vardır. Algoritma kullanır Schwartz setleri.[6]

Orantılı bütçeleme

Başka bir kriter grubu şunlarla ilgilidir orantılı temsil. Bu kriterler genelleştirir haklı temsil kriterler çok kazanan oylama. Bu kriterlerin fikri şudur ki, hepsi belirli bir proje üzerinde hemfikir olan yeterince büyük bir seçmen grubu varsa, o zaman bu projenin bütçenin yeterince büyük bir bölümünü alması gerekir.

Aşağıdaki ifadeler bu sezgiyi şu durum için resmileştirir: bölünmez PB ve onay oylaması, yani:

  • Var m ayrık projeler; her proje j bir maliyet gerektirir cj.
  • Var n seçmenler; her seçmenin arzu edeceğini düşündüğü bir dizi proje vardır.
  • Amaç, en fazla toplam maliyeti olan bir proje alt kümesine karar vermektir. L.

Altında, L bütçe limitini gösterir.[3]

  • Güçlü Bütçe Gerekçeli Temsil (BJR) en azından her büyüklükteki seçmen grubu için n/Lhepsi en az bir projeyi destekliyorsa, hepsinin istediği en az bir proje finanse edilir.
  • Güçlü Bütçe-Orantılı-Gerekçeli-Temsil (BPJR) her tam sayı için k ve her seçmen grubu en az kn/Ltümü tarafından desteklenen projeler en az maliyetli ise ktümünün desteklediği projelere en azından bir finansman sağlanmalıdır. k.

Ne yazık ki, Güçlü BJR bütçeleri mevcut olmayabilir (ve açıkçası aynı durum güçlü BPJR için de geçerlidir, çünkü BJR, k= 1). Örneğin, maliyeti 2 olan iki proje olduğunu, bütçe sınırının 3 olduğunu ve her biri tek bir proje isteyen iki seçmen olduğunu varsayalım. Daha sonra, her seçmen 1> 2/3 büyüklüğünde bir gruptur, bu nedenle BJR her seçmenin projesinin finanse edilmesini gerektirir, ancak her iki projenin toplam maliyetinin 4> 3 olması gerekir. Bu nedenle, bu kriterlerin daha zayıf varyantları önerilmiştir:

  • Zayıf BJR en azından her büyüklükteki seçmen grubu için n/L, hepsi en az bir projeyi destekliyorsa maliyet bir (minimum maliyet)tümünün istediği en az bir proje finanse edilir.
  • Zayıf BPJR her tam sayı için k ve her seçmen grubu en az kn/Ltümü tarafından desteklenen projeler en az maliyetli ise k, bu durumda tümü tarafından desteklenen projeler için fonlar, en az bir proje alt kümesinin maksimum maliyeti olmalıdır k hepsi tarafından destekleniyor.

Neyse ki, Zayıf BPJR bütçeleri (ve dolayısıyla zayıf BJR bütçeleri) her zaman mevcuttur ve süper polinom algoritması ile bulunabilir. Zayıf bir BPJR bütçesi bulmak NP-zordur, ancak zayıf bir BJR bütçesi bulmak bir polinom ile yapılabilir Açgözlü algoritma.

Başka bir kriter, Zayıf Yerel BPJRzayıf BPJR'den daha zayıf, ancak zayıf BJR'den daha güçlüdür; bir polinom zaman algoritması ile bulunabilir. Phragmen sıralı kuralı.

Bu kriterlerin her birinin, harici bütçe limiti yerine daha zayıf bir varyantı vardır. Lpayda W, fonlama için kullanılan gerçek tutardır. Genellikle beri W<L, Wvaryantları tatmin etmek onlarınkinden daha kolaydır L-çeşitli.[3]

Temel bütçeleme

Durum için bölünebilir PB ve faydalı oylama, ikna edici bir bütçeleme yöntemi, çekirdek temeldeki oyunun. Hiçbir alt kümesi yoksa bir bütçe "temelde" kabul edilir k seçmenler bütçeden paylarını alabilir (k L / n) ve projelerin bir alt kümesini, alt kümedeki her bir seçmenin faydası kesinlikle artacak şekilde finanse edin. Bazı doğal sınıf fayda fonksiyonları için çekirdek bütçeyi hesaplamak için etkili algoritmalar vardır.[7]

Donör koordinasyonu

donör koordinasyonu problem bir çeşididir bölünebilir PB bütçenin seçmenlerin kendileri tarafından bağışlandığı (önceden belirlenmek yerine). Bir koordinasyon algoritması, fonların dağıtımının verimliliğini artırabilir. Örneğin, üç projenin değerlendirildiğini varsayalım: tiyatro, satranç kulübü ve basketbol sahası. İki bağışçı var: Alice ve Bob, her biri 3000 katkıda bulunmak istiyor. Alice kapalı alan aktivitelerini (tiyatro veya satranç) tercih ederken, Bob rekabetçi aktiviteleri (satranç veya basketbol) tercih ediyor.

  • Koordine etmezlerse, o zaman doğal olarak Alice her iç mekan aktivitesine 1500, Bob ise her rekabetçi aktiviteye 1500 katkıda bulunur. Ortaya çıkan dağıtım 1500, 3000, 1500'dür. Her bağışçı, bağışlarından tercih ettiği projelere 4500'lük bir mutluluk duyar.
  • Aksine, eğer koordine ederlerse, satranç kulübüne her şeye katkıda bulunabilirler, böylece dağılım 0, 6000, 0 olur. Şimdi, her bağışçı 6000'lik bir mutluluk hissediyor, bu nedenle bu dağılım bir öncekine Pareto hakim.

Bağışlar gönüllü olduğu için, koordinasyon algoritmasının, her seçmenin algoritmaya katılmaktan zayıf bir şekilde kazanç elde etmesini sağlaması önemlidir, yani onayladığı projelere katkıda bulunan miktar, katıldığında katılmadığına göre zayıf bir şekilde daha yüksektir. Seçmenlerin hizmetleri genel doğrusal işlevler olduğunda, bu gereklilik verimli bütçe tahsisi ile uyumsuz olabilir.[8]:saniye 4

Ancak, seçmenlerin faydaları doğrusal olduğunda ve ikiliyani onay oylaması model:

  • Var m hayır kurumları; her hayır kurumu, kendisine konulan herhangi bir miktardaki paradan yararlanabilir.
  • Var n bağışçılar; her bağışçının önemsediği bir dizi hayır kurumu vardır. Her donör ben toplam miktarda bağış yapmaya hazır Cben.
  • Amaç bir karar vermektir dağıtım Tüm bağışçılardan toplanan toplam fonların oranı (toplam Cben) arasında m hayır kurumları. Her bir temsilcinin belirli bir dağıtımdan faydası, sevdiği hayır kurumlarına tahsis edilen paranın toplamıdır.

Bu ortamda çeşitli kurallar analiz edilmiştir. Aşağıda 4 hayır kurumu (a, b, c, d) ve her biri 1'er katkıda bulunan 5 bağışçı içeren ve en sevdikleri setler ac, ad, bc, bd, a olan bir ortam için örneklenmiştir.[8]:saniye 5

  • koordine edilmemiş kural sadece her temsilcinin katkısını böler ben tarafından beğenilen hayır kurumları arasında ben. Dolayısıyla, finansman dağılımı 2,1,1,1 ve beş temsilcinin hizmetleri 3,3,2,2,2'dir. Bu mekanizma uygulanabilir ve bireysel olarak rasyoneldir, ancak verimli değildir: sonuca, örneğin, hizmetlerin 3,3,2,2,3 olduğu 3,2,0,0 dağıtımı hakimdir.
  • Nash-optimal kuralı en üst düzeye çıkaran bir bütçe tahsisi bulur ürün yardımcı programlar. Bu Pareto optimal, uygulanabilir ve bireysel rasyonel. Ancak, öyle değil Strategyproof ne de kaynak monoton.
  • Kısıtlı-faydacı kural, bütçeyi en üst düzeye çıkaran bir bütçe tahsisi bulur. toplam tüm uygulanabilir kurallar kümesindeki yardımcı programlar. Uygulanabilir, bireysel rasyonel, stratejik öneme sahip ve kaynak monotondur. Bununla birlikte, Pareto-optimal değildir.
  • İkili tercihlerde bile beş özelliğin tümünü karşılayan bir PB kuralı yoktur.

Referanslar

  1. ^ a b c Ashish Goel, Anilesh K. Krishnaswamy, Sukolsak Sakshuwong ve Tanja Aitamurto (2016). "Sırt Çantası Oylama: Katılımcı Bütçeleme için Oylama Mekanizmaları" (PDF). S2CID  9240674. Alıntı dergisi gerektirir | günlük = (Yardım)CS1 bakım: birden çok isim: yazarlar listesi (bağlantı)
  2. ^ Aziz, Haris; Bogomolnaia, Anna; Moulin, Hervé (2017). "Adil karıştırma: ikili tercihler durumu". arXiv:1712.02542 [cs.GT ].
  3. ^ a b c Haris Aziz, Barton E. Lee ve Nimrod Talmon (2017). "Orantılı Temsili Katılımcı Bütçeleme: Aksiyomlar ve Algoritmalar" (PDF). Proc. 17. Uluslararası Otonom Ajanlar ve Çok Ajanlı Sistemler Konferansı (AAMAS 2018). arXiv:1711.08226. Bibcode:2017arXiv171108226A.
  4. ^ a b Gerdus Benade ve Swaprava Nath ve Ariel D.Procaccia ve Nisarg Shah (2017). "Katılımcı Bütçeleme İçin Tercih Ortaya Çıkarma" (PDF). AAAI 2017 Tutanakları.
  5. ^ a b Fluschnik, Till; Skowron, Piotr; Triphaus, Mervin; Wilker, Kai (2019-07-17). "Adil Sırt Çantası". AAAI Yapay Zeka Konferansı Bildirileri. 33: 1941–1948. doi:10.1609 / aaai.v33i01.33011941. ISSN  2374-3468.
  6. ^ Shapiro, Ehud; Talmon, Nemrut (2017-09-18). "Katılımcı Demokratik Bütçeleme Algoritması". arXiv:1709.05839 [cs.GT ].
  7. ^ Fain, Brandon; Goel, Ashish; Munagala, Kamesh (2016). Cai, Yang; Vetta, Adrian (editörler). "Katılımcı Bütçeleme Probleminin Özü". Web ve İnternet Ekonomisi. Bilgisayar Bilimlerinde Ders Notları. Springer Berlin Heidelberg. 10123: 384–399. arXiv:1610.03474. doi:10.1007/978-3-662-54110-4_27. ISBN  9783662541104. S2CID  13443635.
  8. ^ a b Florian Brandl, Felix Brandt, Dominik Peters, Christian Stricker, Warut Suksompong (2019). "Bağışçı Koordinasyonu: Bireysel Katkıların Toplu Dağılımı" (PDF). Çalışma kağıdı.CS1 bakım: birden çok isim: yazarlar listesi (bağlantı)