Ishtirok etuvchi byudjetlashtirish algoritmi - Participatory budgeting algorithm

A ishtirok etuvchi byudjet (PB) algoritmi amalga oshirish algoritmi ishtirok etish byudjetini shakllantirish.

PB algoritmiga kirishlar quyidagilar: mumkin bo'lganlar ro'yxati loyihalar mablag 'talab qiladigan, jami mavjud byudjet loyihalarni moliyalashtirish uchun va saylovchilarning afzalliklari loyiha ustida. PB algoritmining natijasi - bu loyihalar orasida byudjetning bo'linishi - har bir loyihaga qancha pul ajratilishini belgilaydi.

PB algoritmi loyihalarni ikkalasi kabi ko'rib chiqishi mumkin bo'linadigan yoki bo'linmaydigan:

  • A bo'linadigan PB algoritmi har qanday loyihaga mablag 'ajratishi mumkin, agar ajratmalar yig'indisi byudjetga teng bo'lsa. Bu har bir qo'shimcha dollardan samarali foydalanish mumkin bo'lgan loyihalar uchun javob beradi, masalan, xayriya mablag'lari.
  • An bo'linmaydigan PB algoritmi qo'shimcha ma'lumot sifatida loyihalarning xarajatlarini oladi. U tanlangan loyihalarning umumiy qiymati byudjetdan oshmasligi uchun loyihalarning bir qismini qaytaradi. Tanlangan har bir loyihaga butun qiymati ajratiladi, tanlanmagan har bir loyihaga esa hech narsa ajratilmaydi. Bu yangi binolarni qurish kabi ishlash uchun to'liq moliyalashtirilishi kerak bo'lgan loyihalar uchun yaxshiroqdir.

Kirish formatlari

PB algoritmini loyihalashda qanday kirish formatidan foydalanish muhim ahamiyatga ega afzalliklarni aniqlash - har bir saylovchi loyihalarga nisbatan o'z afzalliklarini qanday bildirishi kerakligi.[1] Amaliyotda ishlatiladigan bir nechta kirish formatlari:

  • Ovoz berishni tasdiqlash: har bir saylovchi "ma'qullaydigan" (qimmatli deb hisoblaydigan) loyihalarning kichik qismini belgilaydi, boshqalari esa tasdiqlanmagan deb hisoblanadi. Bu ikkitomonlama skorlash tizimiga o'xshaydi, unda har bir saylovchi har bir loyihani 1 yoki 0 ball bilan baholashi mumkin.[2][3]
  • k-ovoz berish: har bir saylovchi yuqori qismining pastki qismini belgilaydi k loyihalar - k ular eng qadrli deb hisoblagan loyihalar.
  • Eshikni tasdiqlash bo'yicha ovoz berish: chegara qiymati berilgan t, har bir saylovchi barcha loyihalarning quyi qismini, ular hech bo'lmaganda muhimligini belgilaydi t.
  • Ovoz berish bo'yicha reyting: har bir saylovchi loyihalarga nisbatan ustunlik munosabatini belgilaydi, ular eng qimmat, 2-o'rinni egallagan loyihani belgilaydi va hokazo.

Ushbu kirish formatlari bo'linmaydigan PB uchun muammoli, chunki ular loyihalarning har xil xarajatlarini inobatga olmaydi. Xarajatlarni hisobga oladigan ba'zi yangi formatlar:[1]

  • Xaltadan ovoz berish: har bir saylovchi loyihaning pastki qismini belgilaydi, shunda quyi qismdagi loyihalarning umumiy qiymati ko'pi bilan byudjetni tashkil etadi (qancha loyihada bo'lishidan qat'i nazar). Shunday qilib, har bir saylovchi shaxsni hal qilishi kerak xalta muammosi - byudjet cheklovi ostida ularning shaxsiy foydasini maksimal darajada oshiradigan kichik to'plamni topish. Ruxsat etilgan ovoz berishning afzalligi shundaki, agar algoritm har bir loyihani olgan ovozlari bo'yicha to'plasa va byudjet to'ldirilguniga qadar ochko'zlik bilan loyihalarni tanlasa, u holda ryukzak ovozi qisman bo'ladi haqiqat mexanizmi.
  • Pul uchun qiymat darajasi: har bir saylovchi loyihalarni umumiy qiymatiga qarab emas, balki ularning qiymati / xarajatlar nisbati bo'yicha saralaydi.

Turli xil formatlarni taqqoslash mumkin yashirin utilitar ovoz berish - har bir kirish formati kommunal xizmatlar yig'indisini maksimal darajada oshirishda qanchalik foydali. Shu nuqtai nazardan, polni tasdiqlash bo'yicha ovoz berish sumkachali ovoz berishdan, qiymat bo'yicha va pul qiymatiga qarab reytingdan ustunroqdir: u nazariy jihatdan ham, empirik jihatdan ham kommunal xizmatlarning maksimal yig'indisidan buzilishini minimallashtiradi.[4]

Tizim fuqarolarning ma'lumotlarini olganidan so'ng, byudjetni hisoblashi kerak. Byudjetni baholashning turli mezonlari mavjud.

Xaltadan byudjetlashtirish

Amaliyotda eng keng tarqalgan byudjetni shakllantirish usuli - variantining ochko'z echimi xalta muammosi: loyihalar ular olgan ovozlar sonini kamaytirish tartibida buyurtma qilinadi va byudjet to'lguniga qadar birma-bir tanlanadi. Shu bilan bir qatorda, agar loyihalar soni etarlicha kam bo'lsa, xalta muammosi fuqarolarning umumiy baxtini maksimal darajaga ko'taradigan kichik loyihani tanlash orqali aniq hal qilinishi mumkin.[1][4] Ushbu usulning nochorligi, ko'pincha chaqiriladi yakka tartibda eng yaxshi byudjetni rejalashtirish, bu ozchiliklarga nisbatan adolatsiz bo'lishi mumkinmi: agar aholining 51 foizi 10 ta loyihani qo'llab-quvvatlasa va 49% boshqa 10 ta loyihani qo'llab-quvvatlasa va pul faqat 10 ta loyihaga etar bo'lsa, unda sumkachani byudjetlashtirish 51% tomonidan qo'llab-quvvatlanadigan 10 ta loyihani tanlaydi, va 49% ni umuman e'tiborsiz qoldiring.[5]

Alohida-alohida eng yaxshi xalta uchun ikkita alternativ:

  • Turli xil sumkalar - byudjetda kamida bitta imtiyozli moddaga ega bo'lgan fuqarolar sonini maksimal darajada oshirish (shunga o'xshash tarzda Chamberlin-Courant qoidasi uchun ko'p g'olib ovoz berish ).
  • Nash-optimal sumka - fuqarolarning kommunal xizmatlari mahsulotini maksimal darajada oshirish.

Afsuski, umumiy kommunal domenlar uchun ushbu ikkala qoidani hisoblash qiyin.[5] Shu bilan birga, turli xil sumkalar, ma'lum imtiyozli domenlarda yoki saylovchilar soni kam bo'lsa, polinomial ravishda hal qilinadi.

Ko'pchilik byudjet

Bunday mezonlardan biri Kondorset mezonlari: tanlangan byudjet, saylovchilarning ko'pchiligining fikriga ko'ra, hech bo'lmaganda boshqa taklif qilingan byudjetga teng bo'lishi kerak (unga taklif qilinadigan biron bir o'zgartirish ovozlar orasida ko'pchilikni qo'llab-quvvatlamaydi). Bunday byudjetni topish uchun polinom-vaqt algoritmi mavjud. Algoritm foydalanadi Shvarts to'plami.[6]

Proportional byudjet

Boshqa bir mezon to'plami bilan bog'liq mutanosib vakillik. Ushbu mezonlar umumiylikni umumlashtiradi asosli vakillik dan mezonlar ko'p g'olib ovoz berish. Ushbu mezonlarning g'oyasi shundan iboratki, agar ma'lum bir loyihada kelishib olgan saylovchilarning etarlicha katta guruhi bo'lsa, unda ushbu loyiha byudjetning etarlicha katta qismini olishi kerak.

Quyidagi iboralar bu holat uchun ushbu sezgi rasmiylashtiriladi bo'linmaydigan PB va ovoz berish, ya'ni:

  • Lar bor m alohida loyihalar; har bir loyiha j xarajatlarni talab qiladi vj.
  • Lar bor n saylovchilar; har bir saylovchida ular kerakli deb hisoblagan bir qator loyihalar mavjud.
  • Maqsad - umumiy qiymati eng ko'pi bo'lgan mablag'larni loyihalashtirish uchun kichik guruhni tanlash L.

Quyida, L byudjet chegarasini bildiradi.[3]

  • Kuchli byudjet asosli vakolatxona (BJR) shuni anglatadiki, har bir saylovchilar guruhi uchun kamida n/L, agar ularning barchasi kamida bitta loyihani qo'llab-quvvatlasa, unda ularning barchasi xohlagan kamida bitta loyiha moliyalashtiriladi.
  • Kuchli byudjet-mutanosib-asosli vakillik (BPJR) demak, har bir butun son uchun k va kamida har bir saylovchilar guruhi kn/L, agar ularning barchasi tomonidan qo'llab-quvvatlanadigan loyihalar kamida xarajat qilsa k, keyin ularning barchasi tomonidan qo'llab-quvvatlanadigan loyihalar hech bo'lmaganda mablag 'olishlari kerak k.

Afsuski, kuchli BJR byudjetlari mavjud bo'lmasligi mumkin (va shubhasiz kuchli BPJR uchun ham xuddi shunday, chunki BJR BPJR uchun alohida holat k= 1). Masalan, qiymati 2 bo'lgan ikkita loyiha bor, byudjet chegarasi 3 ga teng va har biri bitta loyihani istagan ikkita saylovchi bor deylik. Keyin har bir saylovchi 1> 2/3 kattalikdagi guruhdir, shuning uchun BJR har bir saylovchining loyihasini moliyalashtirishni talab qiladi, ammo har ikkala loyiha xarajatlari yig'indisi 4> 3 ga teng. Shuning uchun ushbu mezonlarning zaif variantlari taklif qilingan:

  • Zaif BJR shuni anglatadiki, har bir saylovchilar guruhi uchun kamida n/L, agar ularning barchasi kamida bitta loyihani qo'llab-quvvatlasa qiymati bitta (minimal xarajat), keyin ularning barchasi xohlagan kamida bitta loyiha moliyalashtiriladi.
  • Zaif BPJR demak, har bir butun son uchun k va kamida har bir saylovchilar guruhi kn/L, agar ularning barchasi tomonidan qo'llab-quvvatlanadigan loyihalar kamida xarajat qilsa k, shunda ularning barchasi tomonidan qo'llab-quvvatlanadigan loyihalar uchun mablag 'kamida bitta loyiha kichik to'plamining maksimal qiymati bo'lishi kerak k ularning barchasi tomonidan qo'llab-quvvatlangan.

Yaxshiyamki, zaif BPJR byudjetlari (va shu sababli zaif BJR byudjetlari) har doim mavjud va ularni super-polinom algoritmi bilan topish mumkin. Zaif BPJR byudjetini topish NP-qiyin, ammo zaif BJR byudjetini topish polinom orqali amalga oshirilishi mumkin ochko'zlik algoritmi.

Boshqa mezon, Zaif mahalliy BPJR, zaif BPJRdan kuchsiz, ammo kuchsiz BJRdan kuchliroq; unga asoslangan polinom-vaqt algoritmi bilan topish mumkin Firibgarlar ketma-ket qoida.

Ushbu mezonlarning har biri tashqi byudjet chegarasi o'rniga zaifroq variantga ega L, maxraji V, bu mablag 'uchun sarflangan haqiqiy miqdor. Odatda V<L, V-variantlarni qondirish ularga qaraganda osonroq L-variantlar.[3]

Asosiy byudjet

Ishi uchun bo'linadigan PB va kommunal xizmatlarda ovoz berish, majburiy byudjetlash usuli quyidagilarga asoslangan yadro asosiy o'yin. Byudjet, agar uning tarkibiy qismi bo'lmasa, "asosiy" deb hisoblanadi k saylovchilar byudjetdan o'z ulushlarini olishlari mumkin (k L / n) va har bir saylovchining foydaliligi qat'iy ravishda oshishi uchun loyihalarning quyi qismini moliyalashtiring. Kommunal funktsiyalarning ba'zi tabiiy sinflari uchun asosiy byudjetni hisoblash uchun samarali algoritmlar mavjud.[7]

Donorlarni muvofiqlashtirish

The donorlarni muvofiqlashtirish muammo bo'linadigan PB unda byudjetni saylovchilar o'zlari xayriya qiladilar (oldindan belgilab qo'yilganidan ko'ra). Muvofiqlashtirish algoritmi mablag'larni taqsimlash samaradorligini oshirishi mumkin. Masalan, uchta loyiha ko'rib chiqildi: teatr, shaxmat klubi va basketbol maydoni. Ikkita donor bor: Elis va Bob, ularning har biri 3000 ta hissasini qo'shmoqchi. Elis yopiq mashg'ulotlarni (teatr yoki shaxmat), Bob raqobatbardosh faoliyatni (shaxmat yoki basketbol) afzal ko'radi.

  • Agar ular muvofiqlashtirmasa, tabiiy ravishda Elis har bir yopiq mashg'ulotga 1500 ta, Bob har bir raqobatbardosh faoliyatga 1500 ta hissa qo'shadi. Natijada tarqatish 1500, 3000, 1500 ni tashkil qiladi. Har bir donor o'zining afzal ko'rgan loyihalariga qilgan xayriya mablag'laridan 4500 baxtni his qiladi.
  • Aksincha, agar ular koordinatsiya qilsalar, ular hamma narsani shaxmat klubiga qo'shishlari mumkin, shuning uchun tarqatish 0, 6000, 0 ga teng bo'ladi. Endi har bir donor 6000 baxtni his qiladi, shuning uchun bu taqsimot Pareto avvalgisiga ustunlik qiladi.

Xayr-ehsonlar ixtiyoriy bo'lganligi sababli, muvofiqlashtirish algoritmi har bir saylovchining algoritmda qatnashishdan zaif yutuqqa erishishini ta'minlashi, ya'ni u ma'qullagan loyihalarga qo'shgan mablag'lari ishtirok etgandan ko'ra, u ishtirok etgandan ko'ra kuchsizroq bo'lishini ta'minlash muhimdir. Ushbu talab byudjetni samarali taqsimlash bilan mos kelmasligi mumkin, agar saylovchilarning kommunal xizmatlari umumiy chiziqli funktsiyalar bo'lsa.[8]:sek. 4

Biroq, bu saylovchilarning kommunal xizmatlari chiziqli va bo'lganda amalga oshiriladi ikkilik, ya'ni ovoz berish model:

  • Lar bor m xayriya tashkilotlari; har bir xayriya tashkiloti unga qo'yilgan har qanday miqdordagi puldan foyda ko'rishi mumkin.
  • Lar bor n donorlar; har bir donorning o'zi qiziqtirgan xayriya to'plamlari mavjud. Har bir donor men ning umumiy miqdorini xayriya qilishga tayyor Cmen.
  • Maqsad - a haqida qaror qabul qilish tarqatish barcha donorlardan yig'ilgan jami mablag'larning (summasi Cmen) orasida m xayriya tashkilotlari. Har bir agentning ma'lum tarqatishdan foydalanishi uning sevimli xayriya tashkilotlariga ajratilgan pul summasidir.

Ushbu parametrda bir nechta qoidalar tahlil qilindi. Ular quyida 4 ta xayriya (a, b, c, d) xayriya tashkilotlari va har biriga 1 ta hissa qo'shadigan 5 ta donorlar va ularning sevimli to'plamlari ac, ad, bc, bd, a bo'lgan sharoitlar uchun misol keltirilgan.[8]:sek. 5

  • The muvofiqlashtirilmagan qoida faqat har bir agentning hissasini ajratadi men tomonidan yoqqan xayriya tashkilotlari orasida men. Shunday qilib, moliyalashtirish taqsimoti 2,1,1,1 va beshta agentning kommunal xizmatlari 3,3,2,2,2 ni tashkil qiladi. Ushbu mexanizm amalga oshiriladigan va individual ravishda oqilona, ​​ammo samarali emas: natijada, masalan, 3,2,0,0 tarqatish ustunlik qiladi, bu erda kommunal xizmatlar 3,3,2,2,3.
  • The Nash-optimal qoida maksimal darajaga ko'taradigan byudjet ajratilishini topadi mahsulot kommunal xizmatlar. Bu Pareto optimal, amalga oshiriladigan va individual ravishda oqilona. Biroq, bunday emas Strategiyaga chidamli na monotonik manba.
  • The Cheklangan-utilitar qoida byudjetni maksimal darajada ajratishni topadi sum amalga oshiriladigan barcha qoidalar to'plamidan kommunal xizmatlar. U amalga oshiriladigan, individual ravishda oqilona, ​​strategik va monotonik. Biroq, bu Pareto-optimal emas.
  • Ikkala imtiyoz bilan ham beshta xususiyatni qondiradigan PB qoidasi yo'q.

Adabiyotlar

  1. ^ a b v Ashish Goel, Anilesh K. Krishnaswamy, Sukolsak Sakshuwong va Tanja Aitamurto (2016). "Xaltadan ovoz berish: Ishtirok etuvchi byudjet uchun ovoz berish mexanizmlari" (PDF). S2CID  9240674. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)
  2. ^ Aziz, Xaris; Bogomolnaia, Anna; Moulin, Herve (2017). "Adolatli aralashtirish: ikkilamchi imtiyozlar to'g'risida". arXiv:1712.02542 [cs.GT ].
  3. ^ a b v Xaris Aziz, Barton E. Li va Nimrod Talmon (2017). "Proportional ravishda vakillik asosida byudjetni shakllantirish: aksiomalar va algoritmlar" (PDF). Proc. Avtonom agentlar va multiagent tizimlar bo'yicha 17-xalqaro konferentsiyaning (AAMAS 2018). arXiv:1711.08226. Bibcode:2017arXiv171108226A.
  4. ^ a b Gerdus Benade va Swaprava Nat va Ariel D. Procaccia va Nisarg Shoh (2017). "Ishtirok etish uchun byudjetni shakllantirish uchun imtiyozli murojaat" (PDF). AAAI 2017 materiallari.
  5. ^ a b Fluschnik, To; Skovron, Pyotr; Triphaus, Mervin; Uilker, Kay (2019-07-17). "Adolatli sumka". Sun'iy intellekt bo'yicha AAAI konferentsiyasi materiallari. 33: 1941–1948. doi:10.1609 / aaai.v33i01.33011941. ISSN  2374-3468.
  6. ^ Shapiro, Ehud; Talmon, Nimrod (2017-09-18). "Ishtirok etishning demokratik byudjet algoritmi". arXiv:1709.05839 [cs.GT ].
  7. ^ Feyn, Brendon; Goel, Ashish; Munagala, Kamesh (2016). Kay, Yang; Vetta, Adrian (tahrir). "Ishtirok etuvchi byudjetni shakllantirish muammosining asosi". Internet va Internet iqtisodiyoti. Kompyuter fanidan ma'ruza matnlari. 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, Feliks Brandt, Dominik Peters, Kristian Striker, Warut Suksompong (2019). "Donorlarni muvofiqlashtirish: shaxsiy hissalarni jamoaviy taqsimlash" (PDF). Ishchi qog'oz.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)