Алгоритм совместного составления бюджета
Алгоритм составления бюджета на основе участия
Алгоритм партисипативного бюджетирования (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, а бюджет соответствует размеру парламента.