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

В исследовании операций и социальном выборе правило пропорционально -справедливости (PF) — это правило, согласно которому среди всех возможных альтернатив следует выбрать альтернативу, которую невозможно улучшить, при этом «улучшение» измеряется суммой относительных улучшений, возможных для каждого отдельного агента. Его цель – обеспечить компромисс между утилитарным правилом , которое подчеркивает общую эффективность системы, и эгалитарным правилом , которое подчеркивает индивидуальную справедливость.

Правило было впервые представлено в контексте управления скоростью в сетях связи. ^[1] Однако это общее правило социального выбора, которое также может использоваться, например, при распределении ресурсов. ^[2]

Определение

Позволять $X$ быть набором возможных «состояний мира» или «альтернатив». Общество желает выбрать одно государство из $X$ . Например, на выборах с одним победителем $X$ может представлять группу кандидатов; в настройках распределения ресурсов , $X$ может представлять все возможные распределения ресурса.

Позволять $I$ быть конечным множеством, представляющим совокупность индивидов. Для каждого $i\in I$ , позволять $u_{i}:X\longrightarrow \mathbb {R}$ — функция полезности , описывающая количество счастья, которое индивидуум i получает от каждого возможного состояния.

Правило социального выбора – это механизм, использующий данные $(u_{i})_{i\in I}$ выбрать какой-либо элемент(ы) из $X$ которые являются «лучшими» для общества. Вопрос о том, что означает «лучшее», является основным вопросом теории социального выбора . Правило пропорционально-справедливости выбирает элемент $x\in X$ такое, что для любого другого состояния $y\in X$ :

0\geq \sum _{i\in I}{\frac {u_{i}(y)-u_{i}(x)}{u_{i}(x)}}.

Обратите внимание, что член внутри суммы, ${\frac {u_{i}(y)-u_{i}(x)}{u_{i}(x)}}$ , представляет собой относительную выгоду агента i при переключении с x на y . Правило PF предпочитает состояние x состоянию y тогда и только тогда, когда сумма относительных выигрышей при переключении с x на y не положительна.

Сравнение с другими правилами

Утилитарное правило выбирает элемент $x\in X$ которая максимизирует сумму индивидуальных полезностей, то есть для любого другого состояния $y\in X$ :

0\geq \sum _{i\in I}\left(u_{i}(y)-u_{i}(x)\right).

Это правило игнорирует текущую полезность индивидов. В частности, он мог бы выбрать состояние, в котором полезности некоторых индивидов равны нулю, если полезности некоторых других индивидов достаточно велики.Эгалитарное правило выбирает элемент $x\in X$ который максимизирует наименьшие индивидуальные полезности, то есть для каждого другого состояния. $y\in X$ :

0\geq \min _{i\in I}u_{i}(y)-\min _{i\in I}u_{i}(x).

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

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

Характеристики

Когда множества полезностей выпуклые, всегда существует пропорционально-справедливое решение. Более того, он максимизирует продукт полезностей (также известный как благосостояние Нэша ). ^[3]

Когда наборы полезностей не выпуклые, существование пропорционально-справедливого решения не гарантируется. Однако, когда он существует, он все равно максимизирует продукт полезностей. ^[2]

Правило ПФ в определенных настройках

Пропорциональная справедливость изучалась в различных условиях.

Сетевое планирование; см. пропорционально-справедливое планирование . ^[4]
Задача о сумме справедливого подмножества . ^[2]
Очередь. ^[5]

Ссылки

^ Келли, ФП; Мауллоо, АК; Тан, ДКХ (1 марта 1998 г.). «Регулирование тарифов на сети связи: теневые цены, пропорциональная справедливость и стабильность» . Журнал Общества операционных исследований . 49 (3): 237–252. дои : 10.1057/palgrave.jors.2600523 . ISSN 0160-5682 . S2CID 2876114 .
^ Jump up to: ^а ^б ^с Никосия, Гайя; Пасифичи, Андреа; Пферши, Ульрих (16 марта 2017 г.). «Цена справедливости за распределение ограниченного ресурса» . Европейский журнал операционных исследований . 257 (3): 933–943. arXiv : 1508.05253 . дои : 10.1016/j.ejor.2016.08.013 . ISSN 0377-2217 . S2CID 14229329 .
^ Берцимас, Димитрис; Фариас, Вивек Ф.; Тричакис, Николаос (01 февраля 2011 г.). «Цена справедливости» . Исследование операций . 59 (1): 17–31. дои : 10.1287/опре.1100.0865 . hdl : 1721.1/69093 . ISSN 0030-364X .
^ Кушнер, HJ; Уайтинг, Пенсильвания (июль 2004 г.), «Сходимость алгоритмов пропорционального справедливого распределения в общих условиях», IEEE Transactions on Wireless Communications , 3 (4): 1250–1259, CiteSeerX 10.1.1.8.6408 , doi : 10.1109/TWC.2004.830826 , S2CID 6780351 .
^ Бональд, Т.; Массули, Л.; Прутьер, А.; Виртамо, Дж. (1 июня 2006 г.). «Анализ очередей максимальной и минимальной справедливости, пропорциональной справедливости и сбалансированной справедливости» . Системы массового обслуживания . 53 (1): 65–84. дои : 10.1007/s11134-006-7587-7 . ISSN 1572-9443 . S2CID 1207054 .

[1] Келли, ФП; Мауллоо, АК; Тан, ДКХ (1 марта 1998 г.). «Регулирование тарифов на сети связи: теневые цены, пропорциональная справедливость и стабильность» . Журнал Общества операционных исследований . 49 (3): 237–252. дои : 10.1057/palgrave.jors.2600523 . ISSN 0160-5682 . S2CID 2876114 .

[:2-2] Jump up to: ^а ^б ^с Никосия, Гайя; Пасифичи, Андреа; Пферши, Ульрих (16 марта 2017 г.). «Цена справедливости за распределение ограниченного ресурса» . Европейский журнал операционных исследований . 257 (3): 933–943. arXiv : 1508.05253 . дои : 10.1016/j.ejor.2016.08.013 . ISSN 0377-2217 . S2CID 14229329 .

[3] Берцимас, Димитрис; Фариас, Вивек Ф.; Тричакис, Николаос (01 февраля 2011 г.). «Цена справедливости» . Исследование операций . 59 (1): 17–31. дои : 10.1287/опре.1100.0865 . hdl : 1721.1/69093 . ISSN 0030-364X .

[Kushner-4] Кушнер, HJ; Уайтинг, Пенсильвания (июль 2004 г.), «Сходимость алгоритмов пропорционального справедливого распределения в общих условиях», IEEE Transactions on Wireless Communications , 3 (4): 1250–1259, CiteSeerX 10.1.1.8.6408 , doi : 10.1109/TWC.2004.830826 , S2CID 6780351 .

[5] Бональд, Т.; Массули, Л.; Прутьер, А.; Виртамо, Дж. (1 июня 2006 г.). «Анализ очередей максимальной и минимальной справедливости, пропорциональной справедливости и сбалансированной справедливости» . Системы массового обслуживания . 53 (1): 65–84. дои : 10.1007/s11134-006-7587-7 . ISSN 1572-9443 . S2CID 1207054 .

[1]

[2]

[3]

[4]

[5]