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

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

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

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

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

Форматы ввода

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

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

Эти входные форматы проблематичны для неделимого PB, так как они игнорируют различную стоимость проектов. Вот некоторые новые форматы ввода, которые учитывают затраты:[1]

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

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

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

Составление бюджета на рюкзак

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

Две альтернативы индивидуально лучшему рюкзаку:

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

Бюджетирование большинства

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

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

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

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

  • Есть м дискретные проекты; каждый проект j требует затрат cj.
  • Есть п избиратели; у каждого избирателя есть набор проектов, которые он считает желательными.
  • Цель состоит в том, чтобы выбрать подмножество проектов для финансирования с общей стоимостью не более L.

Ниже, L обозначает предел бюджета.[3]

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

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

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

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

Еще один критерий, Слабый местный BPJR, слабее слабого BPJR, но сильнее слабого BJR; его можно найти с помощью полиномиального алгоритма, основанного на Phragmen Последовательное правило.

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

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

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

Координация доноров

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

  • Если они не координируют свои действия, то, естественно, Алиса вносит 1500 на каждое занятие в помещении, а Боб вносит 1500 на каждое соревнование. В результате получится 1500, 3000, 1500. Каждый жертвователь чувствует себя счастливым в 4500 от пожертвований на его / ее любимые проекты.
  • Напротив, если они координируют свои действия, они могут внести все в шахматный клуб, поэтому распределение становится 0, 6000, 0. Теперь каждый донор чувствует счастье 6000, так что это распределение по Парето преобладает над предыдущим.

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

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

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

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

  • В несогласованное правило просто делит вклад каждого агента я среди благотворительных организаций, любимых я. Таким образом, распределение финансирования составляет 2,1,1,1, а полезности пяти агентов - 3,3,2,2,2. Этот механизм реализуем и рационально индивидуально, но неэффективен: в результате преобладает, например, распределение 3,2,0,0, где полезности 3,3,2,2,3.
  • В Оптимальное правило Нэша находит бюджетные ассигнования, максимизирующие товар коммунальных услуг. это Оптимальный по Парето, реализуемый и индивидуально-рациональный. Однако это не так Стратегия защиты ни ресурсо-монотонный.
  • В Сдержанно-утилитарный Правило находит распределение бюджета, максимизирующее сумма утилит из набора всех реализуемых правил. Она реализуема, индивидуально рациональна, стратегически обоснована и ресурсо-монотонна. Однако он не является оптимальным по Парето.
  • Не существует правила PB, которое удовлетворяло бы всем пяти свойствам, даже с двоичными предпочтениями.

Рекомендации

  1. ^ а б c Ашиш Гоэль, Анилеш К. Кришнасвами, Суколсак Сакшувонг и Таня Айтамурто (2016). «Голосование за рюкзак: механизмы голосования для составления бюджета с участием» (PDF). S2CID  9240674. Цитировать журнал требует | журнал = (помощь)CS1 maint: несколько имен: список авторов (ссылка на сайт)
  2. ^ Азиз, Харис; Богомольная, Анна; Мулен, Эрве (2017). «Справедливое смешение: случай дихотомических предпочтений». arXiv:1712.02542 [cs.GT ].
  3. ^ а б c Харис Азиз, Бартон Э. Ли и Нимрод Талмон (2017). «Пропорционально репрезентативное совместное бюджетирование: аксиомы и алгоритмы» (PDF). Proc. 17-й Международной конференции по автономным агентам и многоагентным системам (AAMAS 2018). arXiv:1711.08226. Bibcode:2017arXiv171108226A.
  4. ^ а б Гердус Бенаде и Сваправа Нат, Ариэль Д. Прокачча и Нисарг Шах (2017). «Выявление предпочтений для совместного бюджетирования» (PDF). Труды AAAI 2017.
  5. ^ а б Флушник, Тилль; Сковрон, Петр; Трипхаус, Мервин; Вилкер, Кай (17.07.2019). «Ярмарка ранца». Материалы конференции AAAI по искусственному интеллекту. 33: 1941–1948. Дои:10.1609 / aaai.v33i01.33011941. ISSN  2374-3468.
  6. ^ Шапиро, Эхуд; Талмон, Нимрод (18.09.2017). «Алгоритм совместного демократического бюджетирования». arXiv:1709.05839 [cs.GT ].
  7. ^ Файн, Брэндон; Гоэль, Ашиш; Мунагала, Камеш (2016). Цай, Ян; Ветта, Адриан (ред.). «Суть проблемы совместного бюджетирования». Интернет и Интернет-экономика. Конспект лекций по информатике. Springer Berlin Heidelberg. 10123: 384–399. arXiv:1610.03474. Дои:10.1007/978-3-662-54110-4_27. ISBN  9783662541104. S2CID  13443635.
  8. ^ а б Флориан Брандл, Феликс Брандт, Доминик Петерс, Кристиан Стрикер, Варут Суксомпонг (2019). «Координация доноров: коллективное распределение индивидуальных пожертвований» (PDF). Рабочий документ.CS1 maint: несколько имен: список авторов (ссылка на сайт)