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

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

Комбинаторное ПБ можно рассматривать как обобщение голосования в комитетах : голосование в комитетах — это частный случай ПБ, в котором «стоимость» каждого кандидата равна 1, а «бюджет» — это размер комитета. Это допущение часто называют допущением удельной стоимости . Условия, при которых проекты являются делимыми (- можно получить любую сумму денег), также называют порционированием. или дробный социальный выбор .

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

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

Правила максимизации благосостояния

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

При голосовании за одобрение возникает дополнительная сложность: нам необходимо сопоставить одобрения агентов с коммунальными предприятиями. Такая карта известна как функция удовлетворения . Известны несколько функций удовлетворения:

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

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

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

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

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

Флюшник, Сковрон, Трифаус и Вилкер изучайте максимизацию утилитарного благосостояния, благосостояния Чемберлена-Куранта и благосостояния Нэша, предполагая кардинальные полезности.

Наиболее распространенный на практике метод бюджетирования представляет собой жадное решение варианта задачи о рюкзаке : проекты упорядочиваются в порядке убывания количества полученных ими голосов и отбираются один за другим до тех пор, пока бюджет не будет исчерпан. В качестве альтернативы, если количество проектов достаточно мало, проблему с рюкзаком можно решить точно, выбрав подмножество проектов, которое максимизирует общее счастье граждан. Поскольку этот метод (называемый «индивидуально лучший рюкзак») может быть несправедливым по отношению к группам меньшинств, они предлагают две более справедливые альтернативы:

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

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

Пропорциональное голосование за одобрение

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

Правила последовательной покупки

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

Правило последовательного фрагмента

Правило последовательных фрагменов обобщает правила Фрагмена для выборов комитетов . Лос, Кристофф и Гросси опишите это для бюллетеней по утверждению как непрерывный процесс:

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

Правило поддержки Максимина

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

Метод равных долей

Этот метод обобщает метод равных долей для выборов в комитеты. Обобщение ПБ с кардинальным голосованием было сделано Перчинским, Петерсом и Скоуроном.

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

Другие правила

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

Сковрон, Слинько, Шуфа и Тальмон представить правило под названием «Минимальные трансферты сверх затрат» , которое особенно подходит для кумулятивного голосования . Его можно рассматривать как адаптацию единого передаваемого голоса .

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

Соображения справедливости

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

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

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

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

На основе этих определений были определены многие понятия справедливости; увидеть Рей и Мали для таксономии различных понятий справедливости. Ниже выбранное распределение бюджета (набор проектов, выбранных для финансирования) X. обозначено

Сильное расширенное обоснованное представление

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

Это свойство слишком сильное даже в частном случае голосования по одобрению и проектов с удельной стоимостью (выборы в комитеты). Например, предположим, что 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 проекта. Обратите внимание, что это справедливо для любой функции удовлетворения.

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

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

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

Распределение бюджета FJR существует всегда. Например, в приведенном выше примере {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|\cdot B/n\geq {\text{cost}}(P)$. Общее число удаленных избирателей не превышает n ; следовательно, общая стоимость добавленных проектов не превышает $n\cdot B/n=B$.

Чтобы увидеть, что GCR удовлетворяет FJR, рассмотрим любую группу N , которая может позволить себе набор P и имеет потенциальную полезность u(N,P). Пусть я буду участником группы 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 сложно, даже если есть один избиратель. Доказательство проводится путем редукции задачи о рюкзаке . Учитывая задачу о рюкзаке, определите экземпляр PB с одним избирателем, в котором бюджетом является вместимость рюкзака, и для каждого предмета с весом w и значением v существует проект со стоимостью w и полезностью v . Пусть P — оптимальное решение для экземпляра ранца. Поскольку стоимость( P )=вес( P ) не превышает бюджета, она доступна для одного избирателя. Следовательно, его полезность при распределении бюджета EJR должна быть не ниже значения ( P ). Таким образом, нахождение распределения бюджета FJR дает решение для случая с рюкзаком. Та же сложность существует даже с бюллетенями для одобрения и удовлетворением на основе затрат за счет сокращения проблемы суммы подмножества .

Расширенное обоснованное представление

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

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

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

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

Остается открытым вопрос, может ли распределение бюджета EJR или FJR быть найдено за полиномиальное от n и B время (то есть псевдополиномиальное время ).

Расширенное обоснованное представление до одного проекта

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), то без этого единственного проекта N i равна как минимум u( ,П).

Перчинский, Сковрон и Петерс доказать, что метод равных долей, работающий за полиномиальное время, всегда находит распределение бюджета EJR-1; следовательно, с помощью бюллетеней одобрения и удовлетворения на основе количества элементов он всегда находит бюджетное распределение EJR (даже для неединичных затрат).

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

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

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

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

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

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

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

Местные условия JR

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

Порядковые условия JR

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

Основная справедливость

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

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

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

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

• и1(а) > и1(б) > 0; и2(б) > и2(в) > 0; и3(в) > и3(а) > 0;
• и4(д) > и4(е) > 0; и5(е) > и5(е) > 0; и6(е) > и6(г) > 0.

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

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

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

Цзян, Мунагала и Ван рассмотрим другое понятие аппроксимации, называемое аппроксимацией прав ; они доказывают, что 32-приблизительное ядро ​​по этому понятию всегда существует.

Ценовая доступность

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

Ценовое распределение рассчитывается по правилам равных долей (для кардинального голосования), Последовательные фрагменты (для бюллетеней утверждения), и поддержка максимина (для бюллетеней для одобрения).

При голосовании за одобрение ценовая политика подразумевает PJR-x для удовлетворения, основанного на затратах. Более того, несколько более строгое понятие ценообразования предполагает PJR-x одновременно для всех функций удовлетворения DNS. Это более сильное понятие удовлетворяется равными долями с удовлетворением мощности, последовательными фрагментами и поддержкой максимина.

Ламинарная справедливость

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

Справедливая доля

Мали, Рей, Эндрисс и Лакнер определил новое понятие справедливости для ПБ с одобрительным голосованием, которое зависит только от равенства ресурсов, а не от конкретной функции удовлетворения. Идею впервые представил Рональд Дворкин . Они объясняют обоснование этого нового понятия следующим образом: «мы не стремимся к справедливому распределению удовлетворения , но вместо этого мы стремимся вложить одинаковые усилия в удовлетворение каждого избирателя. Преимущество состоит в том, что количество затраченных ресурсов — это величина, которую мы может измерить объективно». Они определяют долю агента i в множестве P финансируемых проектов как: ${\text{share}}(P,i):=\sum _{x\in P\cap A_{i}}{\frac {{\text{cost}}(x)}{|\{j:x\in A_{j}\}|}}$. Интуитивно эта величина представляет собой количество ресурсов, которые общество вложило в удовлетворение i . Для каждого финансируемого проекта x стоимость x в равной степени распределяется между всеми агентами, которые одобряют x . В качестве примера предположим, что бюджет равен 8, есть три проекта x,y,z со стоимостью 6,2,2, четыре агента с бюллетенями для одобрения xy, xy, y, z.

• Если выбрано {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 , доля( 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 . Локальная ФС может быть удовлетворена вариантом метода равных долей , при котором вклад каждого агента в финансирование проекта x пропорционален доле({ x }, i ), а не u _i ( x ).

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

Районная справедливость

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

Гершковиц, Кан, Петерс и Прокачча изучить проблему максимизации благосостояния при условии соблюдения районной справедливости. Они показывают, что найти оптимальное детерминированное распределение NP-сложно, но найти оптимальное рандомизированное распределение, которое по ожиданиям будет справедливым для округа, можно сделать эффективно. Более того, если позволить перерасход (до 65%), можно найти распределение, которое максимизирует социальное благосостояние и гарантирует справедливость округа - до одного проекта.

Свойства монотонности

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

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

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

Стратегические объекты

Правило ПБ называется защищенным от стратегии , если ни один избиратель не может увеличить свою полезность, сообщив о ложных предпочтениях. В случае удельных издержек правило, максимизирующее утилитарное благосостояние (выбор проектов категории B с наибольшим числом одобрений), является неэффективным. Это не обязательно справедливо в отношении общих затрат. Гоэл, Кришнасвами, Сакшувонг и Айтамурто Определите приближение к «устойчивому к стратегии», устойчивому к стратегии до одного проекта , что означает, что ни один избиратель не может увеличить свою полезность больше, чем удовлетворение от добавления одного проекта. Они доказывают, что при наличии бюллетеней одобрения и удовлетворении затрат жадный алгоритм, отбирающий проекты по количеству одобрений, является стратегически устойчивым вплоть до одного проекта. Результат не справедлив для удовлетворения мощности.

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

Ограничения на распределение

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

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

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

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

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

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

Чен, Лакнер и Мали Предположим, что проекты принадлежат к возможно перекрывающимся категориям с верхней и нижней квотой для каждой категории.

Мотамед, Соетеман, Рей и Эндрисс покажите, как справиться с категориальными ограничениями путем сокращения до PB с несколькими ресурсами.

Расширения

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

Этап отбора кандидатов

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

Повторный ПБ

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

Неаддитивные утилиты

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

Непостоянные затраты

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

Неопределенные затраты

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

Различные степени финансирования

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

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

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

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

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

См. также

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

Внешние ссылки

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

Платформы с открытым исходным кодом для совместного бюджетирования

• PBS Стэнфорд
• мы решаем
• АдхократияПлюс