Бірлескен бюджеттеу алгоритмі - Participatory budgeting algorithm

A бірлескен бюджеттеу (PB) алгоритмі жүзеге асырудың алгоритмі болып табылады бірлескен бюджеттеу.

PB алгоритмінің кірістері: мүмкін тізімі жобалар қаржыландыруды қажет ететін, жалпы қол жетімді бюджет жобаларды қаржыландыру үшін және сайлаушылардың қалауы жоба бойынша. PB алгоритмінің нәтижесі бюджеттің жобалар арасында бөлінуі болып табылады - әр жобаға қанша ақша бөлу керектігін анықтайды.

PB алгоритмі жобаларды кез-келген ретінде қарастыра алады бөлінетін немесе бөлінбейтін:

  • A бөлінетін PB алгоритмі кез-келген жобаға қандай-да бір ақша бөлуі мүмкін, егер бөлінген сома бюджетке тең болса. Ол қайырымдылық қайырымдылықтары сияқты әрбір қосымша долларды тиімді пайдалануға болатын жобаларға сәйкес келеді.
  • Ан бөлінбейтін PB алгоритмі қосымша кірістер ретінде жобалардың шығындарын алады. Ол таңдалған жобалардың жалпы құны бюджеттен аспайтындай етіп жобалардың ішкі жиынтығын қайтарады. Әрбір таңдалған жобаға барлық шығындар бөлінеді, ал әр таңдалмаған жобаларға ештеңе бөлінбейді. Бұл жаңа ғимараттар салу сияқты жұмыс жасау үшін толығымен қаржыландырылуы керек жобаларға жақсы сәйкес келеді.

Кіріс форматтары

PB алгоритмін жобалау кезінде қандай енгізу форматын қолдану маңызды болып саналады артықшылықты анықтау - әрбір сайлаушы жобаларға қарағанда өз қалауын қалай білдіруі керек.[1] Тәжірибеде қолданылатын бірнеше енгізу форматтары:

  • Дауыс беруді мақұлдау: әрбір сайлаушы «мақұлдайтын» (бағалы деп санайтын) жобалардың ішкі жиынтығын көрсетеді, ал қалғандары мақұлданбаған болып саналады. Бұл әр сайлаушы әр жобаны 1 немесе 0 деп есептей алатын екілік скоринг жүйесі сияқты.[2][3]
  • k-дауыс беру: әрбір сайлаушы өзінің жоғарғы бөлігін көрсетеді к жобалар - к олар ең құнды деп санайтын жобалар.
  • Шекті мақұлдау бойынша дауыс беру: шекті мән берілген т, әрбір сайлаушы барлық жобалардың ішкі жиынтығын олар ең аз деп бағалайды т.
  • Дауыс беру деңгейі: әрбір сайлаушы жобалардан артықшылық-қатынасты анықтайды, олар жобаны ең құнды, 2-ші орынды және т.с.с.

Бұл форматтар бөлінбейтін ПБ үшін проблемалы, өйткені олар жобалардың әртүрлі шығындарын ескермейді. Шығындарды ескеретін кейбір жаңа форматтар:[1]

  • Дорбаға дауыс беру: әрбір сайлаушы жобаның ішкі жиынтығын көрсетеді, осылайша ішкі топтағы жобалардың жалпы құны ең көп мөлшерде бюджетке тең болады (ішкі топта қанша жоба болғанына қарамастан). Осылайша, әрбір сайлаушы жеке тұлғаны шешуі керек рюкзак мәселесі - бюджеттік шектеулер кезінде олардың жеке утилитасын арттыратын ішкі жиынды табу. Рюкзак арқылы дауыс берудің артықшылығы мынада: егер алгоритм әр жобаны алған дауыстар саны бойынша бағаласа және бюджет толтырылғанша жобаларды ұпайдың кему ретімен таңдайтын болса, онда рюкзак арқылы дауыс беру ішінара болып табылады шындық механизмі.
  • Ақшаға құндылық рейтингі: әрбір сайлаушы жобаларды жалпы құнына қарай емес, олардың құны / құнының арақатынасына қарай бағалайды.

Әр түрлі енгізу форматтарын шарт бойынша салыстыруға болады жасырын утилитарлық дауыс беру - әрбір енгізу форматы утилиталар қосындысын көбейту үшін қаншалықты пайдалы. Осы тұрғыдан алғанда шекті мақұлдау бойынша дауыс беру рюкзактық дауыс беруден, мән бойынша және ақшалай құндылықтар бойынша рейтингтен жоғары: бұл теориялық жағынан да, эмпирикалық тұрғыдан да утилиталардың максималды қосындысынан бұрмалауды барынша азайтады.[4]

Жүйе азаматтардың материалдарын алғаннан кейін бюджетті есептеуі керек. Бюджетті бағалауға болатын әртүрлі критерийлер бар.

Рюкса бюджеті

Іс жүзінде кең таралған бюджеттеу әдісі - нұсқасының ашкөз шешімі рюкзак мәселесі: жобаларға тапсырыс берген дауыстардың санын азайту арқылы тапсырыс беріледі және бюджет толғанға дейін бір-бірден таңдалады. Сонымен қатар, егер жобалар саны жеткілікті аз болса, рюкзактар ​​мәселесі азаматтардың жалпы бақытының максимумына жететін жобалардың ішінара таңдау арқылы шешілуі мүмкін.[1][4] Бұл әдістің кемшілігі, жиі деп аталады жеке-үздік рюкзактық бюджеттеу, егер бұл азшылықтарға қатысты әділетсіздік болуы мүмкін: егер халықтың 51% -ы 10 жобаны қолдаса және 49% -ы басқа 10 жобаны қолдаса, ал ақша тек 10 жобаға жететін болса, бюджеттік жоспарлау 51% -дың қолдауы бар 10 жобаны таңдайды, және 49% -ды мүлдем елемеңіз.[5]

Жеке-дара рюкзактың екі баламасы:

  • Әр түрлі рюкзак - бюджетте кем дегенде бір артықшылықты бап бар азаматтардың санын барынша көбейту (ұқсас Чемберлин-Курант ережесі үшін көп жеңімпаз дауыс беру ).
  • Nash-оңтайлы рюкзак - азаматтардың коммуналдық қызметтерінің өнімін барынша арттыру.

Өкінішке орай, жалпы утилиталар үшін бұл екі ережені де есептеу қиын.[5] Алайда, әр түрлі рюкзак белгілі бір артықшылықты домендерде немесе сайлаушылар саны аз болған кезде полиномиальды түрде шешіледі.

Көпшілік бюджеттеу

Осындай критерийлердің бірі болып табылады Кондорсет критерийі: таңдалған бюджет, сайлаушылардың көпшілігінің пікірі бойынша, ұсынылған басқа бюджеттерден кем дегенде жақсы болуы керек (оған ұсынылған ешқандай өзгеріс дауыстардың көпшілігінің қолдауына ие емес). Мұндай бюджетті табудың көпмүшелік-уақыттық алгоритмі бар. Алгоритм қолданады Шварц топтама.[6]

Пропорционалды бюджеттеу

Критерийлердің тағы бір жиынтығы байланысты пропорционалды ұсыну. Бұл критерийлер негізделген өкілдік критерийлері көп жеңімпаз дауыс беру. Бұл критерийлердің идеясы, егер белгілі бір жоба бойынша келісетін сайлаушылардың жеткілікті үлкен тобы болса, онда бұл жоба бюджеттің жеткілікті үлкен бөлігін алуы керек.

Төмендегі өрнектер жағдайға арналған интуицияны рәсімдейді бөлінбейтін PB және мақұлдау бойынша дауыс беру, яғни:

  • Сонда м дискретті жобалар; әр жоба j шығындарды талап етеді вj.
  • Сонда n сайлаушылар; әр сайлаушының қалаған жобаларының жиынтығы бар.
  • Мақсат - қаржыландыру үшін жобалардың ішкі жиынтығы туралы шешім қабылдау, оның жалпы құны ең көбі L.

Төменде, L бюджет лимитін білдіреді.[3]

  • Күшті бюджеттік негізделген өкілдік (BJR) бұл дегеніміз, сайлаушылардың әрқайсысы үшін, ең болмағанда n/L, егер олардың барлығы кем дегенде бір жобаны қолдаса, онда олардың барлығы қалаған кем дегенде бір жоба қаржыландырылады.
  • Күшті бюджет-пропорционалды-негізделген-өкілдік (BPJR) бұл әрбір бүтін сан үшін к және сайлаушылар саны кем дегенде кн/L, егер олардың барлығына қолдау көрсететін жобалардың құны кем дегенде к, демек, олардың барлығымен қолдау тапқан жобалар ең болмағанда қаржыландыруға ие болуы керек к.

Өкінішке орай, BJR-дің күшті бюджеттері болмауы мүмкін (және бұл BPJR-ге қатысты болуы мүмкін, өйткені BJR - бұл BPJR-дің ерекше жағдайы к= 1). Мысалы, құны 2 болатын екі жоба бар делік, бюджет шегі 3, ал әрқайсысы бір жобаны қалайтын екі сайлаушы бар. Сонда әр сайлаушы 1> 2/3 көлеміндегі топты құрайды, сондықтан BJR әр сайлаушының жобасы қаржыландырылуын талап етеді, бірақ екі жобаның шығындарының сомасы 4> 3 құрайды. Сондықтан осы өлшемдердің әлсіз нұсқалары ұсынылды:

  • Әлсіз BJR бұл дегеніміз, сайлаушылардың әрқайсысы үшін, ең болмағанда n/L, егер олардың барлығы кем дегенде бір жобаны қолдаса құны бір (минималды шығын), содан кейін олардың барлығы қалаған кем дегенде бір жоба қаржыландырылады.
  • BPJR әлсіз бұл әрбір бүтін сан үшін к және сайлаушылар саны кем дегенде кн/L, егер олардың барлығына қолдау көрсететін жобалардың құны кем дегенде болса к, содан кейін олардың барлығына қолдау көрсететін жобалар үшін қаржыландыру, ең болмағанда өзіндік құны бар жоба-жиынтықтың максималды құны болуы керек к олардың барлығы қолдайды.

Бақытымызға орай, әлсіз BPJR бюджеттері (демек, әлсіз BJR бюджеттері) әрқашан бар және оларды супер-полиномдық алгоритммен табуға болады. BPJR әлсіз бюджетін табу NP-қиын, бірақ әлсіз BJR бюджетін көпмүшелік арқылы жасауға болады ашкөздік алгоритмі.

Тағы бір критерий, Жергілікті BPJR әлсіз, әлсіз BPJR-ге қарағанда әлсіз, бірақ әлсіз BJR-ге қарағанда күшті; оны көпмүшелік-уақыттық алгоритм бойынша табуға болады Фрагмендер реттілік ережесі.

Осы критерийлердің әрқайсысының сыртқы бюджеттік шекті орнына қарағанда әлсіз нұсқасы бар L, бөлгіш болып табылады W, бұл қаржыландыру үшін пайдаланылған нақты сома. Әдетте W<L, W-варианттарды қанағаттандыру оларға қарағанда оңайырақ L- варианттар.[3]

Негізгі бюджеттеу

Жағдайда бөлінетін PB және коммуналдық дауыс беру, негізделген бюджеттеу әдісі негізделген өзек негізгі ойын. Егер бюджет жоқ болса, бюджет «негізгі» болып саналады к сайлаушылар бюджеттен өз үлестерін ала алады (к Л. / n) және жобаның ішкі жиынтығын қаржыландырыңыз, осылайша кіші топтағы әрбір сайлаушының пайдалылығы қатаң түрде артады. Коммуналдық функциялардың кейбір табиғи кластары үшін негізгі бюджетті есептеудің тиімді алгоритмдері бар.[7]

Донорларды үйлестіру

The донорларды үйлестіру мәселе - нұсқасы бөлінетін PB онда бюджетті сайлаушылар өздері береді (алдын-ала белгіленгеннен гөрі). Үйлестіру алгоритмі қаражатты бөлудің тиімділігін арттыра алады. Мысалы, үш жоба қарастырылды делік: театр, шахмат клубы және баскетбол алаңы. Екі донор бар: Алиса және Боб, олардың әрқайсысы 3000 үлес қосқысы келеді. Алиса жабық үй-жайларда (театрда немесе шахматта), ал Боб бәсекелестік қызметті (шахматта немесе баскетболда) жақсы көреді.

  • Егер олар үйлеспейтін болса, онда әрине, Алиса үй ішіндегі әр іс-әрекетке 1500 үлес қосады, ал Боб әр бәсекеге 1500 үлес қосады. Нәтижесінде үлестіру 1500, 3000, 1500 құрайды. Әрбір донор өзінің қалаған жобаларына қайырымдылықтардан 4500 бақытты сезінеді.
  • Керісінше, егер олар үйлестіретін болса, олар шахмат клубына барлығын ұсына алады, сондықтан үлестіру 0, 6000, 0 болады. Енді әрбір донор 6000 бақытты сезінеді, сондықтан парето алдыңғы үлесте басым болады.

Қайырмалдықтар ерікті болғандықтан, үйлестіру алгоритмі әр сайлаушының алгоритмге қатысудан әлсіз пайда табуын қамтамасыз етуі маңызды, яғни ол мақұлдаған жобаларға қосқан сомасы қатысқан кезде қатысқан кезде әлсіз жоғары болады. Бұл талап сайлаушылардың коммуналдық қызметтері жалпы сызықтық функциялар болған кезде бюджетті тиімді бөлуге сәйкес келмеуі мүмкін.[8]:сек. 4.

Алайда, бұл сайлаушылардың коммуналдық қызметтері сызықтық болған кезде қол жетімді екілік, яғни мақұлдау бойынша дауыс беру модель:

  • Сонда м қайырымдылық; әрбір қайырымдылық оған салынған кез-келген ақшадан пайда көре алады.
  • Сонда n донорлар; әр донордың өзі ойлайтын қайырымдылық жиынтығы бар. Әрбір донор мен жалпы сомасын беруге дайын Cмен.
  • Мақсат - а тарату барлық донорлардан жиналған жалпы қаражаттың (сомасы Cмен) арасында м қайырымдылық. Әр агенттің берілген дистрибутивтен пайдасы оның сүйікті қайырымдылық қорларына бөлінген ақша сомасы болып табылады.

Бұл жағдайда бірнеше ережелер талданды. Олар төменде 4 қайырымдылықпен (a, b, c, d) және әрқайсысына 1-ден үлес қосатын 5 донордан тұратын және сүйікті жиынтықтары ac, ad, bc, bd, a болатын қондырғылар үшін келтірілген.[8]:сек. 5.

  • The келісілмеген ереже тек әр агенттің үлесін бөледі мен ұнаған қайырымдылық ұйымдарының арасында мен. Сонымен, қаржыландыру үлесі 2,1,1,1, ал бес агенттердің коммуналдық қызметтері 3,3,2,2,2 құрайды. Бұл механизм іске асырылатын және жеке-рационалды, бірақ тиімді емес: нәтиже, мысалы, 3,2,0,0 үлестірімі басым, мұнда коммуналдық қызметтер 3,3,2,2,3.
  • The Nash-оңтайлы ереже максималды бюджетті бөлуді табады өнім коммуналдық қызметтер. Бұл Парето оңтайлы, іске асырылатын және жеке-ұтымды. Алайда, олай емес Стратегияға төзімді не ресурстық-монотонды.
  • The Шектелген-утилитарлық ереже максималды бюджетті бөлуді табады сома барлық іске асырылатын ережелер жиынтығынан утилиталар. Ол іске асырылатын, жеке-рационалды, стратегиялық және ресурстық-монотонды. Алайда, бұл парето-оңтайлы емес.
  • Барлық бес қасиеттерді қанағаттандыратын PB ережесі жоқ, екілік теңшелімдермен де.

Пайдаланылған әдебиеттер

  1. ^ а б в Ashish Goel, Anilesh K. Krishnaswamy, Sukolsak Sakshuwong және Tanja Aitamurto (2016). «Дорбаға дауыс беру: бюджеттік жоспарлаудың дауыс беру тетіктері» (PDF). S2CID  9240674. Журналға сілтеме жасау қажет | журнал = (Көмектесіңдер)CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
  2. ^ Азиз, Харис; Богомолная, Анна; Мулен, Эрве (2017). «Әділ араласу: дихотомиялық артықшылықтардың жағдайы». arXiv:1712.02542 [cs.GT ].
  3. ^ а б в Харис Азиз, Бартон Э. Ли және Нимрод Талмон (2017). «Пропорционалды репрезентативті қатысу бюджеті: аксиомалар мен алгоритмдер» (PDF). Proc. Автономды агенттер мен мультиагенттік жүйелер жөніндегі 17-ші Халықаралық конференцияның (AAMAS 2018). arXiv:1711.08226. Бибкод:2017arXiv171108226A.
  4. ^ а б Гердус Бенаде және Сваправа Натх және Ариэль Д. Прокаччиа және Нисарг Шах (2017). «Қатысушы бюджеттеу үшін артықшылықты іздеу» (PDF). AAAI 2017 жинағы.
  5. ^ а б Флушник, дейін; Сковрон, Пиотр; Трифхаус, Мервин; Уилкер, Кай (2019-07-17). «Әділ рюкзак». Жасанды интеллект бойынша AAAI конференциясының материалдары. 33: 1941–1948. дои:10.1609 / aaai.v33i01.33011941. ISSN  2374-3468.
  6. ^ Шапиро, Эхуд; Талмон, Нимрод (2017-09-18). «Бюджеттеудің қатысымдық демократиялық алгоритмі». arXiv:1709.05839 [cs.GT ].
  7. ^ Фэйн, Брэндон; Гоэль, Ашиш; Мунагала, Камеш (2016). Цай, Ян; Ветта, Адриан (ред.) «Қатысушы бюджеттеу проблемасының өзегі». Интернет және Интернет экономикасы. Информатика пәнінен дәрістер. Springer Berlin Heidelberg. 10123: 384–399. arXiv:1610.03474. дои:10.1007/978-3-662-54110-4_27. ISBN  9783662541104. S2CID  13443635.
  8. ^ а б Флориан Брандл, Феликс Брандт, Доминик Петерс, Кристиан Стрикер, Варут Суксомпонг (2019). «Донорларды үйлестіру: жеке жарналарды ұжымдық тарату» (PDF). Жұмыс құжаты.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)