Последовательность комплектации - Picking sequence

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

В качестве примера предположим, что между Алисой и Бобом нужно разделить 4 элемента. Некоторые возможные последовательности комплектации:

  • AABB - Алиса выбирает два предмета, затем Боб выбирает два оставшихся предмета.
  • ABAB - Алиса выбирает один элемент, затем Боб выбирает один элемент, затем снова Алиса, затем снова Боб. Это более "справедливо", чем AABB, поскольку дает Бобу больше шансов получить лучший предмет.
  • АББА - Алиса выбирает один предмет, затем Боб выбирает два предмета, затем Алиса получает оставшийся предмет. Это интуитивно даже более «справедливо», чем ABAB, поскольку в ABAB Боб всегда отстает от Алисы, а ABBA более сбалансирован.[1]

Преимущества

Последовательность выбора имеет несколько достоинств как протокол справедливого деления:[2]:307

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

Максимизация благосостояния

Как выбрать последовательность комплектации? Бувере и Ланг[3] изучите этот вопрос при следующих предположениях:

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

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

Калиновский и др.[4] показать, что когда есть два агента с Борда функция подсчета очков, и каждое ранжирование является равновероятным, последовательность «циклического перебора» (ABABAB ...) достигает максимальной ожидаемой суммы полезностей.[2]:308

Справедливость с разными правами

Брамс и Каплан[5] изучить проблему распределения министерств между партиями. Есть коалиция партий; каждая партия имеет разное количество мест в парламенте; для более крупных партий следует выделить больше министерств или более престижных министерств. Это частный случай справедливое распределение позиций с разными правами. Возможное решение этой проблемы - определить последовательность выбора на основе различных прав и позволить каждой партии выбрать министерство по очереди. Такое решение используется в Северной Ирландии, Дании и Европейском парламенте.[6]

Брамс предполагает, что у каждого агента есть строгий порядок доставки товаров и отзывчивые предпочтения по пачкам товаров. Это означает, что в каждой точке последовательности выбора остается единственный предмет, который является «лучшим предметом» для агента. Агент называется искренний (правдивый), если в каждом пункте он выбирает свой лучший предмет. Если агенты имеют полную информацию о предпочтениях друг друга (что является обычным явлением для сторон), для них может быть нерационально делать правдивый выбор; им может быть лучше сделать сложный (стратегический) выбор. Таким образом, последовательность выбора порождает последовательная игра и интересно проанализировать его идеальное равновесие по подиграм. Доказано несколько результатов:

  • С двумя агентами правдивый и стратегический выбор приводит к Парето эффективный распределения. Более того, игра монотонный в следующем смысле: агент всегда лучше, если одна или несколько его позиций в последовательности улучшены (например, Алиса лучше в последовательности ABBA, чем в BABA). Оба свойства остаются верными для трех или более агентов, если они делают правильный выбор.
  • При наличии трех или более агентов, которые делают стратегический выбор, последовательность выбора может привести к неэффективному распределению (т. Е. Совершенное по подиграм равновесие может не быть эффективным по Парето).
  • С тремя или более агентами, которые делают стратегический выбор, игра может быть немонотонный, то есть агент может сделать еще хуже, если сделает выбор раньше в последовательности.[5]:210–212
  • Для двух агентов существует простая модификация последовательности выбора, которая представляет собой правдивый механизм - правдивый подбор предметов - доминирующая стратегия. Следовательно, существует идеальное по подиграм равновесие, оптимальное по Парето, и игра монотонна.

Определение последовательности комплектации

Какая последовательность выбора была бы справедливой, учитывая разные права агентов?[5]:202–206 предлагает использовать методы делителей, аналогичные тем, которые используются для распределение мест в конгрессе между штатами. Два наиболее часто используемых метода предложены Дэниел Вебстер и Томас Джеферсон. Оба метода запускаются одинаково:

  • Рассчитайте делитель - сумма прав, деленная на количество элементов (например, если сумма всех прав составляет 201, и есть 15 элементов для совместного использования, то делитель равен 201/15).
  • Рассчитайте квота - дробное количество предметов, на которые имеет право каждый агент. Это право, разделенное на делитель (например, для агента с правом 10 из 201 квота составляет 10 * 15/201 ~ 0,75 единиц).

Конкурентное равновесие

Последовательности PIcking можно использовать для поиска распределений, которые удовлетворяют строгому условию справедливости и эффективности, называемому конкурентное равновесие.[7]

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

В циклическое распределение элементов протокол - это частный случай последовательности выбора, в которой последовательность циклическая: 1, 2, ..., п, 1, 2, ..., п, ...

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

  1. ^ Стивен Брамс и Алан Д. Тейлор (1999–2000). Беспроигрышное решение: гарантия справедливой доли участия для всех. Нью-Йорк: У. В. Нортон.
  2. ^ а б Сильвен Бувере, Ян Шевалейр и Николя Моде, «Справедливое распределение неделимых благ». Глава 12 в: Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору. Издательство Кембриджского университета. ISBN  9781107060432. (бесплатная онлайн-версия )
  3. ^ Общий протокол без извлечения для распределения неделимых товаров. Дои:10.5591 / 978-1-57735-516-8 / ijcai11-024.
  4. ^ Оптимальная процедура последовательного распределения социального обеспечения. AAAI-13. 2013.
  5. ^ а б c Глава 9 в Стивен Дж. Брамс (2008). Математика и демократия: разработка более эффективных процедур голосования и справедливого разделения. Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN  9780691133218.. Адаптирован из Брамс, Стивен Дж .; Каплан, Тодд Р. (2004). «Разделение неделимого». Журнал теоретической политики. 16 (2): 143. Дои:10.1177/0951629804041118.
  6. ^ О'Лири, Брендан; Грофман, Бернард; Элклит, Йорген (2005). «Методы разделения для последовательного распределения портфеля в многопартийных исполнительных органах: опыт Северной Ирландии и Дании». Американский журнал политологии. 49: 198–211. Дои:10.1111 / j.0092-5853.2005.00118.x.
  7. ^ Сегал-Халеви, Эрель (20.02.2020). «Конкурентное равновесие почти для всех доходов: существование и справедливость». Автономные агенты и мультиагентные системы. 34 (1): 26. Дои:10.1007 / s10458-020-09444-z. ISSN  1573-7454.