В социальном выбор и исследовании операций , то эгалитарное правило (также называется правило макс-мин или Ролз правило ) является правилом о том , что среди всех возможных альтернатив, общество должно выбрать альтернативу , которая максимизирует минимальную полезность всех людей в обществе. Это формальное математическое представление эгалитарной философии. Это также соответствует принципу Джона Ролза о максимальном благосостоянии наиболее обездоленного человека. [1]
Определение
Позволять быть набором возможных "состояний мира" или "альтернатив". Общество желает выбрать единое государство из. Например, в выборах одного победителя ,может представлять набор кандидатов; в настройке распределения ресурсов , может представлять все возможные распределения.
Позволять - конечное множество, представляющее совокупность индивидов. Для каждого, позволять быть функцией полезности , описывающее количество счастья индивидуума я производные от каждого возможного состояния.
Правило социального выбора является механизмом , который использует данные выбрать некоторые элементы из которые являются «лучшими» для общества. Вопрос о том, что означает «лучшее», является основным вопросом теории социального выбора . Уравнительное правило выбирает элементкоторый максимизирует минимальную полезность , то есть решает следующую задачу оптимизации:
Правило Лексимина
Часто бывает много разных состояний с одинаковой минимальной полезностью. Например, состояние с профилем полезности (0,100,100) имеет то же минимальное значение, что и состояние с профилем полезности (0,0,0). В этом случае эгалитарное правило часто использует лексиминовый порядок , то есть: при условии максимизации наименьшей полезности, оно нацелено на максимизацию следующей наименьшей полезности; в зависимости от этого максимизировать полезность, следующую по величине, и так далее.
Например, предположим, что есть два человека - Алиса и Джордж и три возможных состояния: состояние x дает полезность 2 для Алисы и 4 для Джорджа; состояние y дает полезность 9 для Алисы и 1 для Джорджа; и состояние z дает полезность 1 для Алисы и 8 для Джорджа. Тогда состояние x является лексимин-оптимальным, поскольку его профиль полезности равен (2,4), что лексимин-больше, чем у (9,1) и z (1,8).
Эгалитарное правило, усиленное порядком лексиминов, часто называют правилом лексиминов , чтобы отличить его от более простого правила максимума- минимума .
Правило лексимина для социального выбора было введено Амартией Сеном в 1970 году [1] и подробно обсуждалось во многих более поздних книгах. [2] [3] [4] [5] : подпункт 2.5 [6]
Характеристики
Парето эффективность
Макс-мин правило , не обязательно может привести к Парето эффективному результату. Например, он может выбрать состояние, которое ведет к профилю полезности (3,3,3), в то время как есть другое состояние, ведущее к профилю полезности (3,4,5), которое является улучшением по Парето.
Напротив, правило лексимина всегда выбирает результат, эффективный по Парето. Это связано с тем, что любое улучшение по Парето приводит к вектору полезности с лучшим лексимином: если состояние y по Парето доминирует над состоянием x , то y также лучше по лексимину, чем x .
Пигу-Дальтон недвижимость
Правило лексимина удовлетворяет принципу Пигу-Далтона , а именно: если полезность «перемещается» от агента с меньшей полезностью к агенту с большей полезностью, и в результате разница в полезности между ними становится меньше, тогда результирующая альтернатива предпочтительнее.
Более того, правило лексимина - единственное правило упорядочивания общественного благосостояния, которое одновременно удовлетворяет следующим трем свойствам: [5] : 266
- Эффективность Парето;
- Принцип Пигу-Дальтона;
- Независимость общего темпа полезности - если все полезности преобразованы с помощью общей монотонно возрастающей функции, то порядок альтернатив остается прежним.
Распределение эгалитарных предметов
Эгалитарное правило особенно полезно как правило для справедливого разделения . В этой настройке набор представляет все возможные распределения, и цель состоит в том, чтобы найти распределение, которое максимизирует минимальную полезность или вектор лексимина.
Простое применение этого правила - разделение единого однородного ресурса . Это также рассматривалось в контексте проблемы справедливой суммы подмножества . [7]
Вычисление
Когда элементы неоднородны, можно использовать различные алгоритмы для поиска максимального и минимального распределения элементов . [8] Особый случай этой проблемы - когда каждый элемент j стоит для каждого агента либо 0, либо некоторая константа v j ; этот вариант получил название «проблема Санта-Клауса». [9]
Процедура уменьшения спроса реализует максимальное-минимальное распределение элементов на основе порядкового ранжирования пакетов.
Характеристики
Правило leximin имеет несколько свойств, связанных с распределением элементов без зависти :
- Когда все агенты имеют одинаковые оценки с ненулевыми предельными полезностями, любое (относительное) лексимин-оптимальное распределение - это PO и EFX . Улучшение лексимина под названием leximin ++ гарантирует EFX (но не PO) с общими идентичными оценками. [10]
- Когда все агенты имеют оценки, которые являются функциями ранга матроидов (т. Е. Субмодульными с бинарными маргиналами), набор лексимин-оптимальных распределений эквивалентен набору распределений максимального произведения; все такие распределения - это максимальная сумма и EF1. [11]
- В общем, лексимин-оптимальное распределение может быть даже не EF1, даже с аддитивными оценками . Например, предположим, что есть четыре товара и два агента, которые оценивают их в {0,1,1,1} и {3,3,3,3}. Уникальное (абсолютное) лексимин-оптимальное распределение дает {1,1,1} первому агенту и {3} второму агенту, но тогда второй агент завидует. [11] : 28
В условиях неделимого распределения хозяйственных работ (объектов с отрицательной полезностью):
- С 3 или 4 агентами с аддитивными оценками любое лексимин-оптимальное распределение будет PROP1 и PO; с n агентами с одинаковыми общими оценками любое лексимин-оптимальное распределение будет EFX. [12]
Реальное приложение
Правило лексимина использовалось для справедливого распределения неиспользуемых классных комнат в государственных школах по чартерным школам. [13]
Эгалитарная резка торта
Существование
Лексимин-оптимальные распределения существуют всякий раз, когда множество распределений является компактным пространством . Это всегда имеет место при распределении дискретных объектов и легко доказать при распределении конечного числа непрерывных однородных ресурсов. Дубинс и Спаниер доказали, что при непрерывном гетерогенном ресурсе (« торте ») множество распределений компактно. [14] Следовательно, лексимин-оптимальное распределение тортов существует всегда. По этой причине правило торт распределения leximin иногда называют правилом Dubins-Spanier . [15]
Характеристики
Когда оценки агентов не нормализованы (т. Е. Разные агенты могут присвоить разное значение всему пирогу), существует разница между профилем абсолютной полезности распределения (где элемент i - это просто полезность агента i ) и его относительный профиль полезности (где элемент i - полезность агента i, деленная на общую ценность агента i ). Абсолютное правило leximin выбирает распределение , в котором абсолютная полезности профиль является leximin-максимальным, а относительное правило leximin выбирает распределение , в котором относительная полезности профиль является leximin-максимальным. Хотя оба правила являются PO, они отличаются другими свойствами. В контексте торт резки , абсолютное правило leximin является монотонной ресурс и монотонное населения , но не пропорционально , в то время как правило относительного leximin пропорционально и населения монотонного , но не ресурсы монотонны. [16]
Вычисление
Далл'аглио [15] представляет алгоритм для вычисления лексимин-оптимального распределения ресурсов.
Смотрите также
- Утилитарное правило - другое правило, которое подчеркивает сумму полезностей, а не наименьшую полезность.
- Правило пропорционально-справедливости - правило, которое пытается уравновесить эффективность утилитарного правления и справедливость эгалитарного правления.
- Max-min fair scheduling - max-min справедливое планирование процесса.
Рекомендации
- ^ a b Сен, Амартия (20 февраля 2017 г.). Коллективный выбор и социальное обеспечение . Издательство Гарвардского университета. DOI : 10.4159 / 9780674974616 / html . ISBN 978-0-674-97461-6.
- ^ Д'Аспремон, Клод; Геверс, Луи (1977). «Справедливость и информационная основа коллективного выбора» . Обзор экономических исследований . 44 (2): 199–209. DOI : 10.2307 / 2297061 . ISSN 0034-6527 .
- ^ Кольм, Серж-Кристоф (2002). Справедливость и равноправие . MIT Press. ISBN 978-0-262-61179-4.
- ^ Мулен, Эрве (1991-07-26). Аксиомы совместного принятия решений . Издательство Кембриджского университета. ISBN 978-0-521-42458-5.
- ^ а б Эрве Мулен (2004). Справедливое разделение и коллективное благосостояние . Кембридж, Массачусетс: MIT Press. ISBN 9780262134231.
- ^ Бувере, Сильвен; Лемэтр, Мишель (01.02.2009). «Вычисление лексимин-оптимальных решений в сетях с ограничениями» . Искусственный интеллект . 173 (2): 343–364. DOI : 10.1016 / j.artint.2008.10.010 . ISSN 0004-3702 .
- ^ «Цена справедливости для распределения ограниченного ресурса» . Европейский журнал операционных исследований . 257 (3): 933–943. 2017-03-16. arXiv : 1508.05253 . DOI : 10.1016 / j.ejor.2016.08.013 . ISSN 0377-2217 .
- ^ Безакова, Ивона; Дани, Варша (2005). «Размещение неделимых товаров». Биржи ACM SIGecom . 5 (3): 11. CiteSeerX 10.1.1.436.18 . DOI : 10.1145 / 1120680.1120683 .
- ^ Бансал, Нихил; Свириденко, Максим (2006). «Проблема Деда Мороза». Материалы тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 . п. 31. DOI : 10,1145 / 1132516,1132522 . ISBN 1595931341.
- ^ Плаут, Бенджамин; Рафгарден, Тим (01.01.2020). «Почти свобода от зависти с общими оценками» . Журнал СИАМ по дискретной математике . 34 (2): 1039–1068. arXiv : 1707.04769 . DOI : 10.1137 / 19M124397X . ISSN 0895-4801 .
- ^ а б Бенаббоу, Наваль; Чакраборти, Митхун; Игараси, Аюми; Зик, Яир (2020). Поиск справедливого и эффективного распределения, когда оценки не складываются . Конспект лекций по информатике. 12283 . С. 32–46. arXiv : 2003.07060 . DOI : 10.1007 / 978-3-030-57980-7_3 . ISBN 978-3-030-57979-1. S2CID 208328700 .
- ^ Чен, Синюй; Лю, Цзыцзе (11.05.2020). «Справедливость Leximin в распределении неделимых обязанностей». arXiv : 2005.04864 [ cs.GT ].
- ^ Курокава, Дэвид; Procaccia, Ariel D .; Шах, Нисарг (15.06.2015). «Распределение лексимина в реальном мире» . Труды Шестнадцатой конференции ACM по экономике и вычислениям . EC '15. Портленд, Орегон, США: Ассоциация вычислительной техники: 345–362. DOI : 10.1145 / 2764468.2764490 . ISBN 978-1-4503-3410-5. S2CID 1060279 .
- ^ Дубинс, Лестер Эли ; Спаниер, Эдвин Генри (1961). «Как правильно разрезать торт». Американский математический ежемесячник . 68 (1): 1–17. DOI : 10.2307 / 2311357 . JSTOR 2311357 .
- ^ а б Далл'Аглио, Марко (01.05.2001). "Задача оптимизации Дубинса – Спаниера в теории справедливого деления" . Журнал вычислительной и прикладной математики . 130 (1-2): 17-40. Bibcode : 2001JCoAM.130 ... 17D . DOI : 10.1016 / S0377-0427 (99) 00393-3 . ISSN 0377-0427 .
- ^ Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01.09.2019). «Монотонность и конкурентное равновесие в нарезке торта» . Экономическая теория . 68 (2): 363–401. arXiv : 1510.05229 . DOI : 10.1007 / s00199-018-1128-6 . ISSN 1432-0479 . S2CID 179618 .