Комбинаторное партисипативное бюджетирование

Часть серии «Политика»
Прямая демократия
Типы референдумов Необязательный референдум Законодательное направление Народная инициатива Референдум об отзыве Народный референдум Обязательный референдум
Референдумы по странам Австралия Канада Чехия Евросоюз Франция Германия Италия Иран Израиль Кения Литва Нидерланды Новая Зеландия Польша Филиппины Швеция Словакия Швейцария Турция Тайвань Великобритания Украина США
Референдумы по вопросам Гражданские права Финансы Добыча полезных ископаемых Война Независимость Евросоюз
Референдумы по методу Электронный референдум
История прямой демократии Афинская демократия в США
Связанный Прямые выборы Собрание граждан Народное собрание Гражданское жюри Партисипаторное бюджетирование Список партий прямой демократии Название бюллетеня Жеребьевка
Политический портал
в т е

Комбинаторное партиципаторное бюджетирование [ ^1], также называемое неделимым партиципаторным бюджетированием ^[2] или бюджетным социальным выбором ^[3] , является проблемой в социальном выборе . Существует несколько проектов- кандидатов , каждый из которых имеет фиксированные затраты. Существует фиксированный бюджет , который не может покрыть все эти проекты. У каждого избирателя разные предпочтения относительно этих проектов. Цель состоит в том, чтобы найти распределение бюджета — подмножество проектов с общей стоимостью не более бюджета, которое будет финансироваться. Комбинаторное партиципаторное бюджетирование является наиболее распространенной формой партиципаторного бюджетирования .

Комбинаторное ПБ можно рассматривать как обобщение голосования в комитете : голосование в комитете является особым случаем ПБ, в котором «стоимость» каждого кандидата равна 1, а «бюджет» — размер комитета. Это предположение часто называют предположением о стоимости единицы . Обстановка, в которой проекты делятся (могут получить любую сумму денег), называется порционированием, ^{[4] [5]} дробным общественным выбором или агрегацией бюджетных предложений .

Правила PB имеют и другие применения помимо надлежащего бюджетирования. Например: ^[6]

• Выбор валидаторов в консенсусных протоколах, таких как блокчейн ;
• Выбор веб-страниц, которые должны отображаться в ответ на запросы пользователей;
• Размещение общественных объектов ;
• Повышение качества генетических алгоритмов.

Один класс правил направлен на максимизацию заданной функции общественного благосостояния . В частности, утилитаристское правило направлено на поиск распределения бюджета, которое максимизирует сумму полезностей агентов. ^[7] При кардинальном голосовании нахождение утилитарного распределения бюджета требует решения задачи о рюкзаке , которая является NP-трудной в теории, но может быть легко решена на практике. Существуют также жадные алгоритмы , которые достигают приближения максимального благосостояния с постоянным множителем.

Существует множество возможных функций полезности для данного рейтингового бюллетеня : ^{[2] [8]}

• Удовлетворенность Чемберлина-Куранта предполагает, что полезность агента равна 1, если хотя бы один из его одобренных проектов финансируется, и 0 в противном случае.
• Удовлетворенность на основе кардинальности предполагает, что полезность агента является функцией общего балла, присвоенного финансируемым проектам.
• Удовлетворенность на основе затрат предполагает, что полезность агента представляет собой общую стоимость финансируемых проектов, умноженную на оценку, присвоенную данному проекту.
• Функции убывающей нормализованной удовлетворенности (DNS) — это функции удовлетворенности, которые слабо растут с ростом стоимости, но скорость роста не быстрее стоимости. ^{[ необходимо разъяснение ] [8]} Удовлетворенность по мощности — это одна крайность, при которой удовлетворенность не меняется с ростом стоимости; основанная на стоимости — это другая крайность, при которой удовлетворенность растет точно так же, как стоимость. Между ними существуют функции полезности, такие как квадратный корень стоимости или логарифм стоимости. Удовлетворенность на основе одобрения предполагает, что существует функция sat , которая отображает набор проектов в положительное число, а полезность агента равна sat (одобренные-финансируемые-проекты). Все предыдущие полезности являются частными случаями функций удовлетворенности на основе одобрения.

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

Аник Ларуэль изучает максимизацию благосостояния при слабом порядковом голосовании, где правило подсчета очков используется для перевода рейтинга в полезность. Она изучает жадное приближение к утилитаристскому благосостоянию и для благосостояния Чемберлина-Куранта. Она тестирует три алгоритма на реальных данных из PB в Португалете в 2018 году; результаты показывают, что алгоритм, включающий стоимость проекта в бюллетень, работает лучше, чем два других. ^[10]

Флашник, Сковрон, Трипхаус и Уилкер изучают максимизацию утилитаристского благосостояния, благосостояния Чемберлина-Куранта и благосостояния Нэша, предполагая кардинальную полезность. ^[11]

Метод бюджетирования, наиболее распространенный на практике, — это жадное решение варианта задачи о рюкзаке : проекты упорядочиваются в порядке убывания числа полученных ими голосов и выбираются по одному, пока бюджет не будет исчерпан. В качестве альтернативы, если число проектов достаточно мало, задача о рюкзаке может быть решена точно, путем выбора подмножества проектов, которое максимизирует общее счастье граждан. ^{[12] [13]} Поскольку этот метод (называемый «индивидуально лучшим рюкзаком») может быть несправедливым по отношению к группам меньшинств, они предлагают две более справедливые альтернативы:

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

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

Пропорциональное одобрительное голосование — это правило для голосования с несколькими победителями, которое было адаптировано для ПБ Пирчинским, Петерсом и Сковроном. ^[6] Оно выбирает правило, которое максимизирует общий балл , который определяется гармонической функцией удовлетворения на основе кардинальности. Оно не очень популярно, поскольку в контексте ПБ оно не удовлетворяет сильным гарантиям пропорциональности, как в контексте голосования с несколькими победителями. ^[14]

В правилах последовательной покупки каждый проект-кандидат должен быть «куплен» избирателями, используя некоторую виртуальную валюту. Известно несколько таких правил.

Этот метод правил Фрагмена для выборов в комитет . Лос, Кристофф и Гросси описывают его для бюллетеней одобрения как непрерывный процесс: ^[14]

• Каждый избиратель начинает с 0 виртуальных денег и получает деньги с постоянной скоростью 1 в секунду.
• В каждый момент времени t мы определяем еще не выбранный проект x как доступный, если общая сумма денег, имеющихся у избирателей, одобривших x, составляет по крайней мере стоимость x .
• В первый раз, когда какой-то проект доступен, мы произвольно выбираем один доступный проект y . Мы добавляем y в бюджет и обнуляем виртуальные деньги избирателей, которые одобряют y (поскольку они «использовали» свои виртуальные деньги для финансирования y ).
• Избиратели продолжают зарабатывать виртуальные деньги и финансировать проекты до тех пор, пока следующий финансируемый проект не принесет общую стоимость, превышающую общий доступный бюджет; в этот момент алгоритм останавливается.

Это правило является адаптацией последовательного правила Фрагмена, которое позволяет перераспределять нагрузки в каждом раунде. Впервые оно было введено как правило голосования с несколькими победителями Санчесом-Фернандесом, Фернандесом-Гарсией, Фистеусом и Бриллом. ^[15] Оно было адаптировано к PB Азизом, Ли и Талмоном (хотя они называют его «правилом Фрагмена»). ^[16] Они также представляют эффективный алгоритм для его вычисления.

Этот метод обобщает метод равных долей для выборов в комитет. Обобщение для PB с кардинальными бюллетенями было сделано Перчинским, Петерсом и Сковроном. ^[6]

• Каждый избиратель начинает с B / n виртуальных денег, где B — доступный бюджет, а n — количество избирателей.
• Проект x называется r-доступным, если его стоимость можно покрыть, взяв деньги у агентов таким образом, что каждый агент i платит min(current-money-of- i , r * u _i ( x )). То есть: каждый агент участвует в финансировании x пропорционально u _i ( x ). Число r представляет собой «цену за единицу полезности» (обратите внимание, что полезности нормализованы до диапазона [0,1]).
  • В особом случае бюллетеней одобрения полезность равна 0 или 1, поэтому проект является r -доступным, если его стоимость можно покрыть, взяв деньги у агентов, которые одобряют x , так что каждый агент i платит min(current-money-of- i , r ). Агенты с деньгами менее r платят только свой текущий баланс.
• Мы итеративно добавляем в бюджет r -доступный проект для минимально возможного значения r и уменьшаем виртуальный баланс агентов, которые поддерживают этот проект.
• Когда больше r -доступных проектов не найдено ни для одного r , процесс останавливается.

Шапиро и Талмон ^[17] представляют полиномиальный алгоритм для поиска распределения бюджета, удовлетворяющего критерию Кондорсе : выбранное распределение бюджета должно быть по крайней мере таким же хорошим, как любой другой предложенный бюджет, по мнению большинства избирателей (ни одно из предложенных изменений не имеет поддержки большинства избирателей). Их алгоритм использует множества Шварца .

Сковрон, Слинко, Шуфа и Талмон предлагают правило, называемое минимальными трансфертами по расходам , которое распространяет единый передаваемый голос на партисипативное бюджетирование. ^[18]

Азиз и Ли представляют правило, называемое правилом расширяющегося одобрения , которое использует . ^[19] Перчински, Питерс и Сковрон представляют вариант метода равных долей для слабопорядковых бюллетеней и показывают, что это правило расширяющегося одобрения.

Важным соображением при составлении бюджета является справедливость как по отношению к большинству, так и к меньшинству. Чтобы проиллюстрировать проблему, предположим, что 51% населения живет на севере, а 49% — на юге, и что каждый возможный бюджет... предположим, что есть 10 проектов на севере и 10 проектов на юге, каждый из которых стоит 1 единицу, а доступный бюджет составляет 10. Голосование по бюджету по правилу простого большинства приведет к тому, что будут выбраны 10 проектов на севере, и ни одного проекта на юге, что несправедливо по отношению к южанам. ^[11]

Чтобы частично решить эту проблему, многие муниципалитеты проводят отдельный процесс PB в каждом районе, чтобы гарантировать, что каждый район получит пропорциональное представительство. Но это создает другие проблемы. Например, проекты на границе двух районов могут быть поддержаны только одним районом, и, таким образом, могут не финансироваться, даже если их поддерживают многие люди из другого района. Кроме того, проекты без определенного местоположения, которые приносят пользу всему городу, не могут быть обработаны. Более того, есть группы, которые не являются географическими, например: родители или велосипедисты. ^[6]

Понятие справедливости по отношению к группам формально фиксируется путем расширения критериев обоснованного представительства из голосования с несколькими победителями . Идея этих критериев заключается в том, что если есть достаточно большая группа избирателей, которые все согласны с достаточно большой группой проектов, то эти проекты должны получить достаточно большую часть бюджета. Формально, учитывая группу N избирателей и набор P проектов, мы определяем:

• N может позволить себе P , если : N достаточно велико, чтобы финансировать проекты в P за счет их пропорциональной доли бюджета.${\displaystyle |N|\cdot B/n\geq {\text{стоимость}}(P)}$
• Потенциальная полезность N из P равна . ^{[2] : Раздел 5} В частности, в случае голосования по одобрению и кардинального удовлетворения потенциальная полезность — это просто количество проектов в P, одобренных всеми членами в N .${\displaystyle \sum _{x\in P}\min _{i\in N}u_{i}(x)}$

На основе этих определений были определены многие понятия справедливости; см. Rey и Maly ^[2] для таксономии различных понятий справедливости. Ниже выбранное распределение бюджета (набор проектов, выбранных для финансирования) обозначается как X.

Сильное расширенное обоснованное представительство (SEJR) означает, что для каждой группы избирателей N , которые могут позволить себе набор проектов P , полезность каждого члена N из X по крайней мере так же высока, как потенциальная полезность N из P. В частности, при голосовании по одобрению и кардинальном удовлетворении, если N может позволить себе P и все члены в N одобряют P , то для каждого члена i в N должно быть профинансировано по крайней мере | P | проектов, одобренных i .

Это свойство слишком сильное, даже в особом случае бюллетеней одобрения и проектов с единичной стоимостью (выборы комитета). Например, предположим, что n = 4 и B = 2. Есть три проекта с единичной стоимостью {x, y, z}. Бюллетени одобрения: {1:x, 2:y, 3:z, 4:xyz}. Группа N = {1,4} может позволить себе P = {x}, и их потенциальная полезность от {x} равна 1; аналогично, {2,4} могут позволить себе {y}, а {3,4} могут позволить себе {z}. Поэтому SEJR требует, чтобы полезность каждого из 4 агентов была не менее 1. Это можно сделать, только профинансировав все 3 проекта; но бюджета достаточно только для 2 проектов. Обратите внимание, что это справедливо для любой функции удовлетворения. ^{[2] : Раздел 5, сноска 5}

Полностью обоснованное представительство (FJR) означает, что для каждой группы избирателей N , которые могут позволить себе набор проектов P , полезность по крайней мере одного члена N из X по крайней мере так же высока, как потенциальная полезность N из P. В частности, при голосовании по одобрению и кардинальном удовлетворении, если N может позволить себе P , и каждый член в N одобряет по крайней мере k элементов P , то по крайней мере для одного члена i из N должно быть профинансировано по крайней мере k проектов, одобренных i .

Пункт «по крайней мере один член» может сделать свойство FJR слабым. Но обратите внимание, что оно должно быть верным для каждой группы N избирателей, которые могут позволить себе некоторый набор P проектов, поэтому оно подразумевает гарантии справедливости для многих индивидуальных избирателей.

Распределение бюджета FJR существует всегда. ^{[6] : Раздел 4} Например, в приведенном выше примере {a,b,c} удовлетворяет FJR: в {1,2,3} и {3,4,5} и {5,6,7} все агенты имеют полезность не менее 1, а в {7,8,9} избиратель №7 имеет полезность не менее 1. Доказательство существования основано на правиле, называемом правилом жадной сплоченности (GCR) :

• Проведите итерацию по всем 2 ⁿ группам избирателей. Для каждой группы N найдите набор P проектов, такой, что N может позволить себе P , и при этом потенциальная полезность N от P максимальна.
• Если такая пара (N,P) найдена, все проекты в P финансируются, все избиратели в N удаляются, и процесс повторяется.
• Если пара (N,P) не найдена, алгоритм останавливается.

Легко видеть, что GCR всегда выбирает осуществимое распределение бюджета: всякий раз, когда он финансирует набор P проектов, он удаляет набор N избирателей, удовлетворяющих . Общее число удаленных избирателей не превышает n ; следовательно, общая стоимость добавленных проектов не превышает .${\displaystyle |N|\cdot B/n\geq {\text{cost}}(P)}$${\displaystyle n\cdot B/n=B}$

Чтобы увидеть, что GCR удовлетворяет FJR, рассмотрим любую группу N , которая может позволить себе набор P и имеет потенциальную полезность u(N,P). Пусть i будет членом N , который был удален первым. Избиратель i был удален как член некоторой другой группы избирателей M , которая могла позволить себе набор Q с потенциальной полезностью u(M,Q). Когда M была удалена, N была доступна; поэтому порядок алгоритма подразумевает, что u(M,Q) ≥ u(N,P). Поскольку весь Q финансируется, каждый агент в M , включая агента i , получает полезность не менее u(M,Q), что не менее u(N,P). Таким образом, условие FJR выполняется для i . Обратите внимание, что доказательство справедливо даже для неаддитивных монотонных полезностей.

GCR выполняется за время, экспоненциальное по n . Действительно, нахождение распределения бюджета FJR является NP-трудным даже при наличии одного избирателя. Доказательство заключается в сокращении из задачи о рюкзаке . Для задачи о рюкзаке определите экземпляр PB с одним избирателем, в котором бюджет равен вместимости рюкзака, и для каждого элемента с весом w и значением v существует проект со стоимостью w и полезностью v . Пусть P будет оптимальным решением для экземпляра рюкзака. Поскольку стоимость ( P )=вес( P ) не больше бюджета, он доступен для одного избирателя. Следовательно, его полезность в распределении бюджета EJR должна быть не менее значения ( P ). Следовательно, нахождение распределения бюджета FJR дает решение для экземпляра рюкзака. Та же сложность существует даже с бюллетенями одобрения и удовлетворением на основе затрат путем сокращения из задачи о сумме подмножества .

Расширенное обоснованное представительство (EJR) — свойство немного слабее, чем FJR. Это означает, что условие FJR должно применяться только к группам, которые достаточно «сплочены». В частности, при голосовании по одобрению, если N может позволить себе P , и каждый член в N одобряет все элементы P , то по крайней мере для одного члена i в N удовлетворение от одобренного проекта i в X должно быть по крайней мере таким же высоким, как удовлетворение от P. В частности:

• с кардинальной удовлетворенностью это означает, что по крайней мере | P | проектов, одобренных i, должны быть профинансированы;
• с учетом удовлетворенности на основе затрат это означает, что некоторые проекты, одобренные i , с общей стоимостью не менее cost( P ), должны быть профинансированы.

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

Более того, проверка того, удовлетворяет ли данное распределение бюджета условию EJR, является coNP-сложной даже с учетом удельных затрат. ^[20]

Остается открытым вопрос, можно ли найти распределение бюджета EJR или FJR за время, полиномиальное по n и B (то есть псевдополиномиальное время ). ^{[2] : 5.1.1.2}

EJR до одного проекта (EJR-1) означает, что для каждой группы избирателей N , которые могут позволить себе набор проектов P , существует по крайней мере один член i в N , такой что выполняется одно из следующих условий:

• Полезность i от X равна по крайней мере потенциальной полезности N от P , или -
• Существует проект y в P , такой что полезность i из X + y строго больше потенциальной полезности N из P.

С кардинальными бюллетенями EJR-1 слабее EJR; с бюллетенями одобрения и кардинальным удовлетворением EJR-1 эквивалентен EJR. Это потому, что полезность всех проектов равна 0 или 1. Следовательно, если добавление одного проекта делает полезность i строго больше, чем u(N,P), то без этого одного проекта полезность i будет не менее u(N,P).

Перчинский, Сковрон и Петерс ^{[6] : Теория 2} доказывает, что метод равных долей, который выполняется за полиномиальное время, всегда находит распределение бюджета EJR-1; следовательно, с помощью бюллетеней одобрения и удовлетворения на основе мощности он всегда находит распределение бюджета EJR (даже для неединичных затрат).

EJR до любого проекта (EJR-x) означает, что для каждой группы N избирателей, которые могут позволить себе набор P проектов, и для каждого нефинансируемого проекта y в P полезность i из X + y строго больше , чем потенциальная полезность N из P. Очевидно, что EJR подразумевает EJR-x, что подразумевает EJR-1. Брилл, Форстер, Лакнер, Мэйли и Питерс ^[21] доказывают, что для бюллетеней одобрения и для любой функции удовлетворения с убывающей нормализованной удовлетворенностью (DNS), если метод равных долей применяется с этой функцией удовлетворения, результатом будет EJR-x.

Однако может оказаться невозможным удовлетворить EJR-x или даже EJR-1 одновременно для разных функций удовлетворения: существуют случаи, в которых ни одно распределение бюджета не удовлетворяет EJR-1 одновременно как для удовлетворения затрат, так и для удовлетворения мощности. ^[21]

Пропорциональное оправданное представительство (PJR) означает, что для каждой группы избирателей N , которые могут позволить себе набор проектов P , групповая полезность N из бюджетных ассигнований, определяемая как , составляет по крайней мере потенциальную полезность N из P. В частности, при голосовании по одобрению, если N может позволить себе P , и каждый член в N одобряет все элементы P , то удовлетворение от набора всех финансируемых проектов, которые одобрены по крайней мере одним членом N, должно быть по крайней мере таким же высоким, как удовлетворение от P. В частности:${\displaystyle \sum _{x{\text{ is funded }}}\max _{i\in N}u_{i}(x)}$

• с кардинальной удовлетворенностью это означает, что по крайней мере |P| проектов из союза одобрения-сех всех членов в N должны быть профинансированы;
• с удовлетворением, основанным на затратах, это означает, что проекты с общей стоимостью не менее cost(P), из объединения одобрений всех членов в N , должны финансироваться (PJR для голосований по одобрению с удовлетворением, основанным на затратах, эквивалентно свойству, называемому BPJR-L Азизом, Ли и Талмоном ^[16] ).

Поскольку EJR подразумевает PJR, распределение бюджета PJR всегда существует. Однако, подобно EJR, NP-трудно найти распределение PJR даже для одного избирателя (используя то же сокращение от ранца). Более того, проверка того, удовлетворяет ли данное распределение бюджета PJR, является coNP-трудной даже с учетом удельных затрат и бюллетеней одобрения. ^[20]

Аналогично EJR-x можно определить PJR-x , что означает PJR вплоть до любого проекта. Брилл, Форстер, Лакнер, Мали и Петерс ^[21] доказывают, что для бюллетеней одобрения последовательное правило Фрагмена, правило максиминной поддержки и метод равных долей с кардинальностью-удовлетворением гарантируют PJR-x одновременно для каждой функции удовлетворения DNS .

Азиз, Ли и Талмон ^[16] представляют локальные варианты вышеуказанных критериев JR, которые могут быть удовлетворены за полиномиальное время. Для каждого из этих критериев они также представляют более слабый вариант, где вместо внешнего бюджетного ограничения B знаменателем является W , что является фактической суммой, использованной для финансирования. Поскольку обычно W < B , W -варианты легче удовлетворить, чем их B -варианты. ^[16]

Азиз и Ли ^[19] расширяют понятие обоснованного представительства до слабопорядковых бюллетеней, которые содержат бюллетени одобрения как особый случай. Они расширяют понятие сплоченной группы до прочной коалиции и определяют два несопоставимых понятия пропорциональности: Сравнительная пропорциональность для прочных коалиций (CPSC) и Пропорциональность включения для прочных коалиций (IPSC). CPSC может существовать не всегда, но IPSC всегда существует и может быть найдена за полиномиальное время. Равные доли удовлетворяют PSC — более слабому понятию, чем IPSC и CPSC. ^[6]

Один из способов оценить как справедливость, так и стабильность распределения бюджета — проверить, может ли какая-либо заданная группа избирателей достичь более высокой полезности, взяв свою долю бюджета и разделив ее другим способом. Это отражено в понятии ядра из теории кооперативных игр. Формально распределение бюджета X находится в слабом ядре , где нет группы избирателей N , и альтернативное распределение бюджета Z из , такое, что все члены N строго предпочитают Z X .${\displaystyle |N|\cdot B/n}$

Справедливость ядра сильнее, чем FJR, которая сильнее, чем EJR. Чтобы увидеть связь между этими условиями, обратите внимание, что для слабого ядра достаточно, чтобы для каждой группы избирателей N полезность хотя бы одного члена N из X была как минимум такой же высокой, как потенциальная полезность N из P ; не требуется, чтобы N была сплоченной.

Для настройки делимых ПБ и кардинальных бюллетеней существуют эффективные алгоритмы расчета основного бюджетного распределения для некоторых естественных классов функций полезности. ^[22]

Однако для неделимого PB слабое ядро ​​может быть пустым даже при удельных затратах. Например: ^[6] предположим, что есть 6 избирателей и 6 проектов с удельной стоимостью, а бюджет равен 3. Утилиты удовлетворяют следующим неравенствам:

• u1(a) > u1(b) > 0; u2(b) > u2(c) > 0; u3(c) > u3(a) > 0;
• и4(д) > и4(е) > 0; и5(е) > и5(е) > 0; и6(е) > и6(г) > 0.

Все остальные полезности равны 0. Любое возможное распределение бюджета содержит либо максимум один проект {a,b,c}, либо максимум один проект {d,e,f}. Wlog предположим первое и предположим, что b и c не финансируются. Тогда избиратели 2 и 3 могут взять свою пропорциональную долю бюджета (которая равна 1) и профинансировать проект c, что даст им обоим более высокую полезность. Обратите внимание, что в приведенном выше примере требуется только 3 значения полезности (например, 2, 1, 0).

При наличии только двух значений полезности (т. е. бюллетеней одобрения) остается открытым вопрос о том, всегда ли существует распределение со слабым ядром, с удельными затратами или без них; как с удовлетворением мощности, так и с удовлетворением затрат. ^[6]

Некоторые приближения к ядру могут быть достигнуты: равные доли достигают мультипликативного приближения . ^[6] Мунагала, Шен, Ван и Ван ^[23] доказывают, что для произвольных монотонных полезностей существует 67-приближенное распределение ядра, которое может быть вычислено за полиномиальное время. Для аддитивных полезностей существует 9,27-приближенное распределение ядра, но неизвестно, может ли оно быть вычислено за полиномиальное время.${\displaystyle 4\log(2{\frac {u_{\max }}{u_{\min }}})}$

Цзян, Мунагала и Ван ^{[24] [25]} рассматривают другое понятие приближения, называемое приближением прав ; они доказывают, что 32-приближенное ядро ​​согласно этому понятию всегда существует.

Ценообразование означает, что ^[6] можно назначить фиксированный бюджет каждому избирателю и разделить бюджет каждого избирателя между кандидатами, которых он одобряет, так что каждый избранный кандидат «покупается» кандидатами, которые его одобряют, и ни один неизбранный кандидат не может быть куплен оставшимися деньгами избирателей, которые его одобряют. MES можно рассматривать как реализацию равновесия Линдаля в дискретной модели с предположением, что клиенты, разделяющие товар, должны платить одинаковую цену за товар. ^[26] Определение для кардинальных бюллетеней такое же, как и для бюллетеней одобрения.

Ценовое распределение рассчитывается по правилам равных долей (для кардинальных голосований), ^[6] последовательной фразы (для голосований по утверждению) ^[14] и максиминной поддержки (для голосований по утверждению) ^{[21] .}

С бюллетенями одобрения ценообразование подразумевает PJR-x для удовлетворения на основе затрат. Более того, немного более сильное понятие ценообразования подразумевает PJR-x одновременно для всех функций удовлетворения DNS. Это более сильное понятие удовлетворяется равными долями с удовлетворением кардинальности, последовательным Phragmen и поддержкой максимина. ^[21]

Ламинарная справедливость ^{[27] [14]} — это условие для экземпляров определенной структуры, называемых ламинарными экземплярами . Частным случаем ламинарного экземпляра является экземпляр, в котором население разделено на две или более непересекающихся групп, так что каждая группа поддерживает непересекающийся набор проектов. Равные доли и последовательные Phragmen ламинарно-пропорциональны удельным затратам, ^[27] но не общим затратам. ^[14]

Maly, Rey, Endriss и Lackner ^{[28] [29]} определили новое понятие справедливости для PB с бюллетенями одобрения, которое зависит только от равенства ресурсов, а не от конкретной функции удовлетворения. Идея была впервые представлена ​​Рональдом Дворкиным . ^{[30] [31]} Они объясняют обоснование этого нового понятия следующим образом: «мы не стремимся к справедливому распределению удовлетворения , но вместо этого мы стремимся вкладывать одинаковые усилия в удовлетворение каждого избирателя. Преимущество состоит в том, что объем потраченных ресурсов является величиной, которую мы можем измерить объективно». Они определяют долю агента i из множества P финансируемых проектов как: . Интуитивно, эта величина представляет собой объем ресурсов, которые общество вкладывает в удовлетворение i . Для каждого финансируемого проекта x стоимость x в равной степени вносится всеми агентами, которые одобряют x . В качестве примера предположим, что бюджет составляет 8, есть три проекта x, y, z со стоимостью 6, 2, 2, четыре агента с бюллетенями одобрения xy, xy, y, z.${\displaystyle {\text{share}}(P,i):=\sum _{x\in P\cap A_{i}}{\frac {{\text{cost}}(x)}{|\{j:x\in A_{j}\}|}}}$

• Если выбрано {x,y}, то доля избирателей 1,2 равна 6/3+2/2=3; доля избирателя 3 равна 6/3=2; а доля избирателя 4 равна 0.
• Если выбрано {x,z}, то доля избирателей 1,2,3 составляет 6/3=2, а доля избирателя 4 составляет 2/1=2, поэтому все избиратели получили одинаковую долю.

Распределение бюджета удовлетворяет справедливой доле (FS), если доля каждого агента составляет не менее min( B / n , share( A _i , i )). Очевидно, что справедливое распределение может не существовать, например, когда есть два агента, каждый из которых хочет свой проект, но бюджета достаточно только для одного проекта. Более того, даже справедливое распределение до одного проекта (FS-1) может не существовать. Например, предположим, что B = 5, есть 3 проекта стоимостью 3, а бюллетени для одобрения — это xy, yz, zx. Справедливая доля составляет 5/3. Но в любом возможном распределении финансируется не более одного проекта, поэтому есть агент без одобренного финансируемого проекта. Для этого агента даже добавление одного проекта увеличит его долю до 3/2=1,5, что меньше 5/3. Проверка того, существует ли распределение FS или FS-1, является NP-трудной. На практических примерах из pabulib можно дать каждому агенту от 45% до 75% его справедливой доли; правила MES дают большую долю, чем последовательный Phragmen.

Более слабое ослабление, называемое локальной справедливой долей (Local-FS) , требует, чтобы для каждого нефинансируемого проекта y существовал по крайней мере один агент i , который одобряет y и имеет долю ( X + y , i) > B / n . Local-FS может быть удовлетворено вариантом метода равных долей , в котором вклад каждого агента в финансирование проекта x пропорционален доле ({ x }, i ), а не u _i ( x ).

Другим послаблением является Extended Justified Share (EJS) : это означает, что для любой группы агентов N , которые могут позволить себе набор проектов P , такой, что каждый член в N одобряет все элементы P , есть по крайней мере один член i в N , для которого share( X , i ) ≥ share( P , i ). Это похоже на EJR, но они независимы: есть случаи, в которых некоторые распределения являются EJS и не EJR, в то время как другие распределения являются EJR и не EJS. Распределение EJS всегда существует и может быть найдено с помощью правила Greedy Cohesive Rule с экспоненциальным временем за время ; поиск распределения EJS является NP-трудным. Но приведенный выше вариант MES удовлетворяет EJS до одного проекта (EJS-1). Открыто, может ли EJS до любого проекта (EJS-x) быть удовлетворено за полиномиальное время.${\displaystyle O(n\cdot 2^{m})}$

Справедливость округа — это понятие справедливости, которое фокусируется на заранее определенных округах города. Каждый округ i заслуживает бюджет B _i (часть всего городского бюджета), который обычно пропорционален численности населения округа. Во многих городах существует отдельный процесс ПБ в каждом округе. Может быть более эффективно провести единый общегородской процесс ПБ, но важно сделать это таким образом, чтобы не навредить округам. Таким образом, распределение бюджета по городу является справедливым округом , если оно дает каждому округу i по крайней мере то благосостояние, которое он мог бы получить при оптимальном распределении B _i .

Hershkowitz, Kahng, Peters и Procaccia ^[32] изучают проблему максимизации благосостояния в зависимости от справедливости округа. Они показывают, что поиск оптимального детерминированного распределения является NP-трудным, но поиск оптимального рандомизированного распределения, которое в ожидание справедливо для округа, может быть выполнен эффективно. Более того, если разрешено перерасходовать средства (до 65%), можно найти распределение, которое максимизирует общественное благосостояние и гарантирует справедливость для округа вплоть до одного проекта.

Естественно ожидать, что при изменении некоторых параметров экземпляра PB результат правила PB изменится предсказуемым образом. В частности:

• Монотонность скидки говорит о том, что если правило выбирает проект x , и x становится дешевле, а все остальные данные не меняются, правило все равно выберет x .
• Предельная монотонность (вдохновленная ресурсной монотонностью и монотонностью дома ) гласит, что если правило выбирает проект x , а общий бюджет увеличивается, то правило все равно выберет x .
• Монотонность слияния гласит, что если правило выбирает набор X проектов и все эти проекты объединяются в один проект y (такой, что cost( y )=cost( X ), и каждый агент одобряет y тогда и только тогда, когда он одобряет все проекты в X ), то правило выбирает y .
• Монотонность расщепления гласит, что если правило выбирает проект x , и этот проект разбивается на набор проектов Y (таким образом, что стоимость (Y) = стоимость (x), и каждый агент одобряет x , если он одобряет все проекты в Y), то правило выбирает по крайней мере один проект из Y.

Свойства монотонности были изучены для правил максимизации благосостояния и для их жадных вариантов. ^{[7] [33] [34]}

Правило PB называется стратегически защищенным, если ни один избиратель не может увеличить свою полезность, сообщая о ложных предпочтениях. При удельных затратах правило, которое максимизирует утилитарное благосостояние (выбор проектов B с наибольшим числом одобрений), является стратегически защищенным. Это не обязательно верно для общих затрат. При бюллетенях одобрения и удовлетворении затрат жадный алгоритм, который выбирает проекты по числу одобрений, является стратегически защищенным вплоть до одного проекта. Результат не сохраняется для кардинальности-удовлетворения. ^[35]

Правило утилитаризма не пропорционально даже с единичными издержками и бюллетенями одобрения. Действительно, даже при голосовании в комитете существует фундаментальный компромисс между стратегической устойчивостью и пропорциональностью; см. multiwinner approval vote#strategy .

Часто существуют ограничения, которые запрещают некоторым подмножествам проектов быть результатом ПБ. Например:

• некоторые проекты несовместимы и не могут финансироваться вместе;
• некоторые проекты зависят от других проектов.

Рей, Эндрисс и де Хаан ^[36] разрабатывают общую структуру для обработки любых ограничений, которые могут быть описаны пропозициональной логикой , путем кодирования случаев ПБ как агрегации суждений . ^[37] Их структура допускает ограничения зависимости, а также ограничения категории, с возможным перекрытием категорий.

Файн, Мунагала и Шах ^[38] изучают обобщение ПБ: распределение неделимых общественных благ с возможными ограничениями на распределение. Они рассматривают ограничения матроида , ограничения соответствия и ограничения упаковки (которые соответствуют бюджетным ограничениям).

Джейн, Сорнат, Талмон и Зехави ^[39] предполагают, что проекты разделены на непересекающиеся категории, и для каждой категории существует бюджетный предел, в дополнение к общему бюджетному пределу. Они изучают вычислительную сложность максимизации общественного благосостояния с учетом этих ограничений. В целом проблема сложная, но эффективные алгоритмы даны для настроек с небольшим количеством категорий.

Патель, Хан и Луис ^[40] также предполагают, что проекты разделены на непересекающиеся категории, с верхними и нижними квотами для каждой категории. Они представляют алгоритмы аппроксимации с использованием динамического программирования.

Чен, Лакнер и Мали ^[41] предполагают, что проекты относятся к потенциально пересекающимся категориям, с верхними и нижними квотами для каждой категории.

Мотамед, Соетеман, Рей и Эндрисс ^[42] показывают, как справляться с категориальными ограничениями путем сведения к ПБ с несколькими ресурсами.

В последнее время были изучены несколько расширений базовой модели ПБ.

Рей, Эндрисс и де Хаан рассматривают важный этап, который происходит в реальных реализациях ПБ перед этапом голосования: выбор короткого списка проектов, которые будут представлены избирателям. Они моделируют этот этап короткого списка как процесс голосования с несколькими победителями , в котором нет ограничений на общий размер или стоимость результата. Они анализируют несколько правил, которые могут использоваться на этом этапе, чтобы гарантировать разнообразие выбранных проектов. Они также анализируют возможные стратегические манипуляции на этапе короткого списка. ^[43]

Лакнер, Мали и Рей отмечают, что в действительности ПБ — это не одноразовый процесс, а скорее повторяющийся процесс, который происходит ежегодно. Они распространяют некоторые понятия справедливости с постоянного голосования на ПБ. В частности, они предполагают, что избиратели разделены на типы, и пытаются достичь справедливости по отношению к типам с течением времени. ^[44]

Джейн, Сорнат и Талмон предполагают, что проекты могут быть взаимозаменяемыми товарами или взаимодополняющими товарами , и поэтому полезность, которую агент получает от набора проектов, не обязательно является суммой полезностей каждого проекта. Они анализируют вычислительную сложность максимизации благосостояния в этой расширенной обстановке. В этой работе структура взаимодействия между проектами фиксирована и одинакова для всех избирателей; ^[45] Джейн, Талмон и Булто расширяют модель дальше, позволяя избирателям указывать индивидуальные структуры взаимодействия. ^[46]

Лу и Бутилье рассматривают модель бюджетного общественного выбора, которая очень похожа на ПБ. ^[3] В их условиях стоимость каждого проекта представляет собой сумму фиксированной стоимости и переменной стоимости, которая увеличивается с числом агентов, «назначенных» на проект. Мотамед, Соетеман, Рей и Эндрисс рассматривают многомерные затраты, например, затраты в денежном выражении, времени и других ресурсах. ^[42] Они распространяют некоторые свойства справедливости и стратегические свойства на эту установку и рассматривают вычислительную сложность максимизации благосостояния.

Баумайстер, Боэс и Лауссманн предполагают, что затраты неопределенны: каждая стоимость имеет распределение вероятностей, и ее фактическая стоимость раскрывается только после ее завершения. ^[47] Чтобы снизить риск, можно реализовывать проекты один за другим, так что если первый проект стоит слишком дорого, некоторые последующие проекты можно будет исключить. Но это может привести к тому, что некоторые проекты будут реализованы с большим опозданием. Они показывают, что невозможно одновременно поддерживать низкий риск перерасхода средств и гарантировать, что все проекты будут завершены в положенное время. Они адаптируют критерии справедливости, а также метод равных долей к этой обстановке.

Проекты, которые могут финансироваться в разных степенях. ^[1] Например, новое здание для молодежных мероприятий может иметь 1, 2 или 3 этажа; оно может быть маленьким или большим; оно может быть построено из дерева или камня и т. д. Это можно рассматривать как промежуточное звено между неделимым PB (который допускает только два уровня) и делимым PB (который допускает непрерывно много уровней). Формально каждый проект j может быть реализован в любой степени между 0 и t _j , где 0 означает «вообще не реализован», а tj — максимально возможная реализация. Каждая степень реализации имеет свою стоимость. Бюллетени представляют собой бюллетени ранжированного одобрения , то есть: каждый избиратель дает для каждого проекта минимальную и максимальную сумму денег, которая должна быть вложена в этот проект.

Сридурга ^[48] рассматривает утилитаристскую максимизацию благосостояния в этой обстановке. Он рассматривает четыре функции удовлетворения:

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

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

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

• Голосование с несколькими победителями — можно рассматривать как особый случай партисипаторного бюджетирования, при котором «стоимость» каждого кандидата равна 1, а бюджет равен размеру парламента.
• Агрегация бюджетных предложений — особый случай ПБ, при котором каждый избиратель представляет полное бюджетное предложение, а правило объединяет все предложения в единое бюджетное распределение.
• Дробный общественный выбор — может использоваться для моделирования делимого ПБ, в котором возможно любое разделение имеющегося бюджета между проектами.
• Координация доноров — расширение модели ПБ, в которой часть или все деньги поступают от избирателей, а не от правительства.
• Краудфандинг

• Pabulib — онлайн-коллекция реальных примеров партисипаторного бюджетирования.
• Демонстрация Javascript различных комбинаторных правил PB на сайте pref.tools.

• PBStanford
• Децидим
• AdhocracyPlus