Алгоритм совместного составления бюджета

Алгоритм составления бюджета на основе участия

Алгоритм партисипативного бюджетирования (PB) - это алгоритм для реализации партисипативного бюджетирования.

Исходными данными для алгоритма PB являются: список возможных проектов, требующих финансирования, общий доступный бюджет для финансирования проектов и предпочтения избирателей в отношении проекта. Результатом работы алгоритма PB является распределение бюджета между проектами - определение того, сколько денег выделить на каждый проект.

Алгоритм PB может рассматривать проекты как разделяемые или неделимые:

Делимый алгоритм PB может выделить любую сумму денег на любой проект, если сумма ассигнований равна бюджету. Он подходит для проектов, в которых каждый дополнительный доллар может быть использован эффективно, например, для благотворительных пожертвований. Неделимый алгоритм PB принимает в качестве дополнительных входных данных затраты на проекты. Он возвращает подмножество проектов таким образом, чтобы общая стоимость выбранных проектов не превышала бюджет. Каждому выбранному проекту выделяется вся его стоимость, в то время как каждому невыбранному проекту не выделяется ничего. Он лучше подходит для проектов, которые должны быть полностью профинансированы для того, чтобы функционировать, таких как строительство новых зданий.

Входные форматы

Важным соображением при разработке алгоритма PB является то, какой формат ввода использовать для выявления предпочтений - как каждый избиратель должен выразить свои предпочтения в отношении проектов. На практике используются следующие форматы ввода::

Голосование за одобрение: каждый избиратель указывает подмножество проектов, которые они "одобряют" (считают ценными), в то время как остальные считаются неутвержденными. Это похоже на бинарную систему подсчета очков, в которой каждый избиратель может оценить каждый проект как 1 или 0.[2][3] голосование за k-одобрение: каждый избиратель определяет подмножество своих лучших k проектов - k проектов, которые они считают наиболее ценными. Голосование за утверждение порогового значения: при заданном пороговом значении t каждый избиратель указывает подмножество всех проектов, которые они оценивают как минимум t. Ранжированное голосование: каждый избиратель задает полное соотношение предпочтений по проектам, указывая проект, который он считает наиболее ценным, вторым по ценности и т.д. Эти форматы ввода являются проблематичными для неделимого PB, поскольку они игнорируют различные затраты на проекты. Некоторые новые форматы ввода, которые действительно учитывают затраты, следующие:

Голосование ранцем: каждый избиратель определяет подмножество проектов таким образом, чтобы общая стоимость проектов в подмножестве составляла не более бюджета (независимо от того, сколько проектов в подмножестве). Таким образом, каждый избиратель должен решить индивидуальную проблему с рюкзаком - найти подмножество, которое максимизирует его личную полезность при бюджетных ограничениях. Преимущество ранцевого голосования заключается в том, что если алгоритм оценивает каждый проект по количеству полученных им голосов и жадно выбирает проекты в порядке убывания баллов, пока бюджет не будет заполнен, то ранцевое голосование является частично правдивым механизмом.

Рейтинг соотношения цены и качества: каждый избиратель оценивает проекты не в соответствии с их общей стоимостью, а в соответствии с их соотношением стоимости и стоимости.

Различные форматы ввода можно сравнивать с точки зрения неявного утилитарного голосования - насколько каждый формат ввода полезен для максимизации суммы полезностей. С этой точки зрения пороговое голосование за одобрение превосходит ранговое голосование, ранжирование по стоимости и ранжирование по соотношению цены и качества: оно сводит к минимуму искажения от максимальной суммы полезностей как теоретически, так и эмпирически.[4]

После того, как система получит информацию от граждан, она должна рассчитать бюджет. Существуют различные критерии, по которым можно оценивать бюджет.

Ранцевое бюджетирование

Метод составления бюджета, наиболее распространенный на практике, представляет собой жадное решение варианта проблемы рюкзака: проекты упорядочиваются в порядке убывания количества голосов, которые они получили, и выбираются один за другим, пока бюджет не будет заполнен. В качестве альтернативы, если количество проектов достаточно мало, проблема рюкзака может быть точно решена путем выбора подмножества проектов, которые максимизируют общее счастье граждан. Недостаток этого метода, часто называемыйиндивидуально-лучшее ранцевое бюджетирование заключается в том, что оно может быть несправедливым по отношению к меньшинствам: если 51% населения поддерживает 10 проектов, а 49% поддерживают 10 других проектов, а денег хватает только на 10 проектов, то ранцевое бюджетирование выберет 10 проектов, поддерживаемых 51%, и проигнорирует 49% в целом.

Двумя альтернативами индивидуально подобранному рюкзаку являются:

Разнообразный рюкзак - максимальное количество граждан, у которых есть хотя бы одна предпочтительная статья в бюджете (аналогично правилу Чемберлина-Куранта для голосования с несколькими победителями).

Nash-оптимальный рюкзак - максимизация продукта коммунальных услуг граждан.

К сожалению, для доменов общего назначения оба эти правила NP-трудно вычислить.[5] Однако разнородный рюкзак полиномиально разрешим в определенных областях предпочтений или когда число избирателей невелико.

Составление бюджета большинством голосов

Одним из таких критериев является критерий Кондорсе: выбранный бюджет должен быть, по крайней мере, таким же хорошим, как и любой другой предлагаемый бюджет, по мнению большинства проголосовавших (ни одно предлагаемое изменение в нем не получило поддержки большинства голосов). Существует алгоритм нахождения такого бюджета за полиномиальное время. Алгоритм использует множества Шварца.

Пропорциональное бюджетирование

Другой набор критериев связан с пропорциональным представительством. Эти критерии обобщают критерии обоснованного представительства, полученные в результате голосования с несколькими победителями. Идея этих критериев заключается в том, что, если есть достаточно большая группа избирателей, которые все согласны с конкретным проектом, то этот проект должен получить достаточно большую часть бюджета.

Приведенные ниже выражения формализуют эту интуицию для случая неделимого PB и голосования за одобрение, т.е.:

Существует m отдельных проектов; каждый проект j требует затрат cj.

Есть n избирателей; у каждого избирателя есть набор проектов, которые он считает желательными.

Цель состоит в том, чтобы выбрать подмножество проектов для финансирования с общей стоимостью не более L.

Ниже L обозначает бюджетный лимит.

Сильное представительство, оправданное бюджетом (BJR), означает, что для каждой группы избирателей размером не менее n / L, если все они поддерживают хотя бы один проект, то по крайней мере один проект, желаемый всеми из них, будет профинансирован.

Сильное бюджетно-пропорциональное обоснованное представительство (BPJR) означает, что для каждого целого числа k и каждой группы избирателей размером не менее kn / L, если проекты, поддерживаемые всеми из них, стоят не менее k, то проекты, поддерживаемые всеми из них, должны получать финансирование не менее к.

К сожалению, строгие бюджеты BJR могут не существовать (и, очевидно, то же самое верно для сильного BPJR, поскольку BJR является частным случаем BPJR для k = 1). Например, предположим, что есть два проекта со стоимостью 2, бюджетный лимит равен 3, и есть два избирателя, каждый из которых желает получить один проект. Тогда каждый избиратель представляет собой группу размером 1> 2/3, поэтому BJR требует, чтобы проект каждого избирателя был профинансирован, но сумма затрат на оба проекта равна 4> 3. Поэтому были предложены более слабые варианты этих критериев:

Слабый BJR означает, что для каждой группы избирателей размером не менее n / L, если все они поддерживают хотя бы один проект стоимостью один (минимальная стоимость), то по крайней мере один проект, желаемый всеми из них, финансируется.

Слабый BPJR означает, что для каждого целого числа k и каждой группы избирателей размером не менее kn / L, если проекты, поддерживаемые всеми из них, стоят не менее k, то финансирование проектов, поддерживаемых всеми из них, должно составлять не менее максимальной стоимости подмножества проектов со стоимостью в большинство из них поддерживается всеми.

К счастью, слабые бюджеты BPJR (и, следовательно, слабые бюджеты BJR) всегда существуют и могут быть найдены с помощью суперполиномиального алгоритма. Нахождение бюджета со слабым BPJR является NP-сложной задачей, но нахождение бюджета со слабым BJR может быть выполнено с помощью полиномиального жадного алгоритма.

Другой критерий, слабый локальный BPJR, слабее, чем слабый BPJR, но сильнее, чем слабый BJR; его можно найти с помощью алгоритма с полиномиальным временем, основанного на последовательном правиле Фрагмена.

Каждый из этих критериев имеет более слабый вариант, где вместо внешнего бюджетного лимита L знаменателем является W, который представляет собой фактическую сумму, использованную для финансирования. Поскольку обычно W<L, W-варианты легче удовлетворить, чем их L-варианты.[3]

Другим строгим критерием пропорциональности является расширенное обоснованное представительство (EJR). Каждое правило, удовлетворяющее EJR, является NP-сложным для вычисления, однако существует правило, вычислимое за полиномиальное время, метод равных долей [7] [8], которое удовлетворяет небольшому смягчению аксиомы EJR-up-to-one-project.

Базовое бюджетирование

В случае делимого PB и голосования за полезность убедительным методом составления бюджета является метод, основанный на сути базовой игры. Бюджет считается "основным", если ни одно подмножество из k избирателей не может взять свою долю бюджета (k L / n) и профинансировать подмножество проектов таким образом, чтобы полезность каждого избирателя в подмножестве строго возрастала. Существуют эффективные алгоритмы вычисления основного бюджета для некоторых естественных классов функций полезности.

Координация деятельности доноров

Проблема координации доноров - это вариант делимого PB, при котором бюджет жертвуется самими избирателями (а не фиксируется заранее). Алгоритм координации может повысить эффективность распределения средств. Например, предположим, что рассматриваются три проекта: театр, шахматный клуб и баскетбольная площадка. Есть два донора: Алиса и Боб, каждый из которых хочет внести свой вклад в размере 3000 долларов. Алиса предпочитает занятия в помещении (театр или шахматы), в то время как Боб предпочитает соревновательные виды деятельности (шахматы или баскетбол).

Если они не координируют свои действия, то, естественно, Алиса вносит 1500 долларов на каждое мероприятие в помещении, в то время как Боб вносит 1500 долларов на каждое соревновательное мероприятие. Итоговое распределение составляет 1500, 3000, 1500. Каждый донор чувствует себя счастливым в размере 4500 долларов от пожертвований на его / ее любимые проекты.

Напротив, если они координируют свои действия, они могут внести все в шахматный клуб, поэтому распределение становится 0,6000,0. Теперь каждый донор чувствует счастье в 6000, поэтому это распределение по Парето доминирует над предыдущим.

Поскольку пожертвования являются добровольными, важно, чтобы алгоритм координации гарантировал, что каждый избиратель слабо выигрывает от участия в алгоритме, то есть сумма, внесенная в проекты, которые он одобряет, немного выше, когда он участвует, чем когда он этого не делает. Это требование может быть несовместимо с эффективным распределением бюджета, когда полезность избирателей является общей линейной функцией.: раздел 4

Однако это достижимо, когда полезности избирателей являются линейными и бинарными, то есть в модели голосования за одобрение:

Существует m благотворительных организаций; каждая благотворительная организация может извлечь выгоду из любой суммы вложенных в нее денег.

Есть n доноров; у каждого донора есть набор благотворительных организаций, о которых он / она заботится. Каждый донор i готов пожертвовать общую сумму ci.

Цель состоит в том, чтобы принять решение о распределении общих средств, собранных от всех доноров (сумма CI) между m благотворительными организациями. Полезность каждого агента из данного распределения - это сумма денег, выделенная его / ее любимым благотворительным организациям.

В этой настройке было проанализировано несколько правил. Они приведены ниже в качестве примера для ситуации с 4 благотворительными организациями (a, b, c, d) и 5 донорами, которые вносят по 1 от каждого, и чьи любимые наборы - ac, ad, bc, bd, a.[10]: раздел 5

Несогласованное правило просто делит вклад каждого агента i между благотворительными организациями, которые мне нравятся. Таким образом, распределение финансирования равно 2,1,1,1, а полезности пяти агентов равны 3,3,2,2,2. Этот механизм осуществим и индивидуально-рациональен, но не эффективен: в результате доминирует, например, распределение 3,2,0,0, где коммунальные услуги составляют 3,3,2,2,3.

Правило оптимального распределения бюджета по Нэшу определяет распределение бюджета, максимизирующее продукт коммунальных услуг. Он является оптимальным по Парето, реализуемым и индивидуально-рациональным. Однако он не является ни стратегически надежным, ни ресурсоемким.

Правило ограниченной утилитарности находит распределение бюджета, максимизирующее сумму полезностей из набора всех реализуемых правил. Она выполнима, индивидуально-рациональна, стратегически надежна и ресурсоемка. Однако он не является оптимальным по Парето.

Не существует правила PB, которое удовлетворяло бы всем пяти свойствам, даже с бинарными предпочтениями.

Смотрите также

Голосование с несколькими победителями - можно рассматривать как частный случай составления бюджета на основе участия, при котором "стоимость" каждого кандидата равна 1, а бюджет соответствует размеру парламента.