Порядковая эффективность Парето
Порядковая эффективность по Парето относится к нескольким адаптациям концепции эффективности по Парето к условиям, в которых агенты выражают порядковые полезности только для предметов, но не для наборов. То есть агенты ранжируют элементы от лучшего к худшему, но не ранжируют подмножества элементов. В частности, они не указывают числовое значение для каждого элемента. Это может вызвать неоднозначность относительно того, являются ли определенные распределения эффективными по Парето или нет. В качестве примера рассмотрим экономику с тремя элементами и двумя агентами со следующими рейтингами:
- Алиса: х > у > z.
- Джордж: x > z > y.
Рассмотрим распределение [Алиса: x, Джордж: y,z]. Является ли это распределение эффективным по Парето или нет, зависит от числовых оценок агентов. Например:
- Возможно, что Алиса предпочитает {y,z} {x}, а Джордж предпочитает {x} {y,z} (например: оценки Алисы для x,y,z равны 8,7,6, а оценки Джорджа равны 7 ,1,2, поэтому профиль полезности равен 8,3). Тогда распределение не будет эффективным по Парето, поскольку и Алиса, и Джордж выиграют, если обменяются своими наборами (профиль полезности будет равен 13,7).
- Напротив, возможно, что Алиса предпочитает {x} {y,z}, а Джордж предпочитает {y,z} {x} (например: оценки Алисы равны 12,4,2, а оценки Джорджа — 6,3, 4). Тогда распределение будет эффективным по Парето: при любом другом распределении, если Алиса по-прежнему получает x, то полезность Джорджа будет ниже; если Алиса не получает x, то полезность Алисы ниже. Более того, распределение является Парето-эффективным, даже если предметы делятся (т. е. оно дробно эффективно по Парето ): если Алиса отдает Джорджу какое-либо количество r от x, то Джорджу придется отдать ей как минимум 3 r от y или 6 r от z, чтобы сохранить ее полезность на том же уровне. Но тогда полезность Джорджа изменится на 6r - 9r или 6r - 24r , что отрицательно.
Поскольку эффективность распределения по Парето зависит от ранжирования пакетов, априори неясно, как определить эффективность распределения, когда заданы только ранги элементов.
Определения
[ редактировать ]Распределение X = (X 1 ,...,X n ) доминирует по Парето над другим распределением Y = (Y 1 ,...,Y n ), если каждый агент i слабо предпочитает пакет X i пакету Y i , и по крайней мере один агент j строго предпочитает X j Y j . Распределение X является эффективным по Парето, если никакое другое распределение не доминирует над ним по Парето. Иногда проводится различие между дискретной эффективностью по Парето , что означает, что в распределении не доминирует дискретное распределение, и более сильной концепцией дробной эффективности по Парето , которая означает, что в распределении не доминирует даже дробное распределение.
Приведенные выше определения зависят от ранжирования агентами пакетов (наборов элементов). В наших условиях агенты сообщают только о своем рейтинге элементов . Ранжирование пакетов называется согласованным с ранжированием элементов, если оно ранжирует одиночные пакеты в том же порядке, что и элементы, которые они содержат. Например, если рейтинг Алисы равен w < x < y < z , то любой последовательный рейтинг пакета должен иметь {w} < {x} < {y} < {z]. Часто делаются дополнительные предположения о множестве разрешенных рангов пакетов, что накладывает дополнительные ограничения на согласованность. Примеры предположений:
- Монотонность: добавление предмета в комплект всегда улучшает комплект. Это соответствует предположению, что все предметы хороши . Таким образом, рейтинг пакета Алисы должен иметь, например, {y} < {y,x}.
- Оперативность : замена предмета на более качественный всегда улучшает комплект. Таким образом, рейтинг пакета Алисы должен иметь, например, {w,x} < {w,y} < {x,y} < {x,z}. Это сильнее, чем последовательность.
- Аддитивность : агент присваивает ценность каждому элементу и оценивает каждый пакет по сумме его содержимого. Это предположение сильнее, чем отзывчивость. Например, если Алиса имеет ранг {x,y}<{z}, то она должна иметь ранг {w,x,y}<{w,z}.
- Лексикографический : агент всегда ставит набор, содержащий некоторый элемент x, выше любого пакета, который содержит только элементы с рейтингом ниже x. В приведенном выше примере Алиса должна иметь ранг {w,x,y} < {z}.
Необходимая Парето-эффективность
[ редактировать ]Брамс, Эдельман и Фишберн [1] : 9 называют распределение обеспечивающим по Парето, если оно эффективно по Парето для всех рейтингов пакетов, которые согласуются с рейтингами элементов агентов (они допускают все монотонные и отзывчивые ранжирования пакетов). Например:
- Если оценки агентов предполагаются положительными, то каждое распределение, отдающее все предметы одному агенту, является гарантирующим по Парето.
- Если рейтинг Алисы равен x>y, а рейтинг Джорджа равен y>x, то распределение [Алиса:x, Джордж:y] является гарантирующим по Парето.
- Если рейтинг Алисы равен x>y>z, а рейтинг Джорджа равен x>z>y и распределения должны быть дискретными, то распределение [Алиса: x,y; Джордж: z] обеспечивает Парето. [1] : 5 [ нужны разъяснения ]
- При приведенном выше рейтинге распределение [Алиса: x, Джордж: y,z] не является Парето-гарантирующим. Как объяснялось во введении, это не эффективно по Парето, например, когда оценки Алисы для x, y, z равны 8,7,6, а оценки Джорджа равны 7,1,2. Обратите внимание, что обе эти оценки согласуются с рейтингами агентов.
Бувере, Эндрисс и Ланг. [2] : 3 используйте эквивалентное определение. Они говорят, что распределение X, возможно, доминирует по Парето над распределением Y, если существует некоторый рейтинг пакетов, соответствующий рейтингу элементов агентов, для которого X доминирует по Парето над Y. Распределение называется обязательно-парето-эффективным (NecPE), если нет другого распределение, возможно, доминирует над ним по Парето.
Оба определения логически эквивалентны:
- «X является Парето-гарантирующим» эквивалентно «Для каждого последовательного ранжирования пакета, для любого другого распределения Y, Y не доминирует по Парето X».
- «X есть NecPE» эквивалентно «Для любого другого распределения Y, для каждого последовательного ранжирования пакета Y не доминирует по Парето X». Изменение порядка кванторов «для всех» не меняет логического смысла.
Условие NecPE остается неизменным независимо от того, разрешаем ли мы все рейтинги аддитивных пакетов или разрешаем только рейтинги, основанные на аддитивных оценках с уменьшающимися различиями. [3] : Раздел 8
Существование
[ редактировать ]NecPE — это очень строгое требование, которое зачастую невозможно удовлетворить. Например, предположим, что два агента имеют одинаковый рейтинг элементов. Один из них, скажем, Алиса, обязательно получает предмет с самым низким рейтингом. Существуют последовательные аддитивные рейтинги пакетов, в которых Алиса оценивает этот элемент в 0, а Джордж оценивает его в 1. Следовательно, передача его Алисе неэффективна по Парето.
Если мы требуем, чтобы все предметы имели строго положительное значение, то отдавать все предметы одному агенту — это тривиально NecPE, но это очень несправедливо. Если разрешено дробное распределение, то не может быть распределения NecPE, которое дает обоим агентам положительное значение. Например, предположим, что Алиса и Джордж имеют рейтинг x>y. Если оба получают положительное значение, то либо Алиса получит некоторое количество x, а Джордж получит некоторое количество y, или наоборот. В первом случае возможно, что оценки Алисы равны, например, 4,2, а оценки Джорджа равны 8,1, поэтому Алиса может обменять небольшую сумму r от x на небольшую сумму 3 r от y. Алиса получает 6 r -4 r , а Джордж получает 8 r -3 r , поэтому оба выигрыша положительны. В последнем случае имеет место аналогичный аргумент.
Возможная Парето-эффективность
[ редактировать ]Брамс, Эдельман и Фишберн [1] : 9 Назовите распределение возможным по Парето, если оно эффективно по Парето для некоторых рейтингов пакетов, которые согласуются с рейтингами элементов агентов. Очевидно, что любое распределение, обеспечивающее Парето, является Парето-возможным. Кроме того:
- Если рейтинг Алисы равен x>y>z, а рейтинг Джорджа равен x>z>y, то распределение [Алиса: x, Джордж: y,z] возможно по Парето. Как объяснялось во введении, это эффективно по Парето, например, когда оценки Алисы для x, y, z равны 12,4,2, а оценки Джорджа равны 6,3,4. Обратите внимание, что обе эти оценки согласуются с рейтингами агентов.
- Если рейтинг Алисы равен x>y, а рейтинг Джорджа равен y>x, то распределение [Алиса:y, Джордж:x] не является возможным по Парето, поскольку в нем всегда доминирует по Парето распределение [Алиса:x, Джордж: й].
Бувере, Эндрисс и Ланг. [2] : 3 используйте другое определение. Они говорят, что распределение X обязательно доминирует по Парето над распределением Y, если для всех рангов пакетов, соответствующих ранжированию элементов агентов, X доминирует по Парето над Y. Распределение называется возможно-эффективным по Парето (PosPE), если никакое другое распределение не обязательно Парето-доминирует над ним.
Эти два определения логически не эквивалентны:
- «X возможно по Парето» эквивалентно «Существует непротиворечивое ранжирование пакета, для которого при любом другом распределении Y Y не доминирует над X». Это должен быть тот же рейтинг пакета для всех остальных распределений Y.
- «X есть PosPE» эквивалентно «Для любого другого распределения Y существует согласованный рейтинг пакета, для которого Y не доминирует над X». может быть разный рейтинг пакетов. Для каждого другого распределения Y
Если X возможно по Парето, то это PosPE, но другой вывод (логически) неверен. [ нужны разъяснения ]
Условие Парето-возможности остается тем же, независимо от того, разрешаем ли мы все аддитивные групповые ранжирования или разрешаем только ранжирования, основанные на аддитивных оценках с уменьшающимися различиями . [3] : Раздел 8
Стохастическое доминирование Парето-эффективности
[ редактировать ]Богомольная и Мельница [4] : 302–303 представить понятие эффективности для настройки справедливого случайного назначения (где рейтинги пакетов аддитивны , распределения являются дробными , а сумма дробей, присвоенных каждому агенту, должна быть не более 1 ). Он основан на понятии стохастического доминирования .
Для каждого агента i пакет X i слабо-стохастически доминирует (wsd) над пакетом Y i , если для каждого элемента z общая доля элементов лучше, чем z в X i, по крайней мере так же велика, как и в Y i (если распределения дискретны, то X i sd Y i означает, что для каждого элемента z количество элементов лучше, чем z в X i, по меньшей мере так же велико, как и в Y i ). Отношение sd имеет несколько эквивалентных определений; см. расширение адаптивного набора . В частности, X i sd Y i тогда и только тогда, когда для каждого ранга пакета, соответствующего рангу элемента, X i по крайней мере так же хорош, как Y i . [5] Расслоение X i строго стохастически доминирует (ssd) над расслоением Y i, если X i wsd Y i и X i ≠ Y i . Эквивалентно, по крайней мере, для одного элемента z значение «по крайней мере такое же большое, как в Y i » становится «строго большим, чем в Y i ». В [1] отношение ssd записывается как «X i >> Y i ».
Распределение X = (X 1 ,...,X n ) стохастически доминирует над другим распределением Y = (Y 1 ,...,Y n ), если для каждого агента i : X i wsd Y i и Y≠X ( эквивалентно: хотя бы для одного агента i X i ssd Y i ). В [1] стохастическое отношение доминирования между распределениями также записывается как «X >> Y». Это эквивалентно необходимому доминированию по Парето.
Распределение называется SD-эффективным. [6] (также называемый: порядково эффективным или O-эффективным ) [4] если нет распределения, которое стохастически доминирует над ним. Это похоже на PosPE, но подчеркивает, что ранжирование пакетов должно основываться на аддитивных функциях полезности, а распределения могут быть дробными .
Эквиваленты
[ редактировать ]Как отмечалось выше, возможное по Парето подразумевает PosPE, но другое направление логически неверно. МакЛеннан [7] доказывает, что они эквивалентны в задаче справедливого случайного назначения (со строгим или слабым ранжированием элементов). В частности, он доказывает, что следующие утверждения эквивалентны:
- (a) X является sd-эффективным (т. е. X является PosPE);
- (b) существуют аддитивные групповые рейтинги, соответствующие рейтингам элементов агентов, для которых X является дробно-эффективным по Парето (т. е. X является возможным по Парето);
- (c) существуют аддитивные рейтинги пакетов, соответствующие рейтингам элементов агентов, для которых X максимизирует сумму полезностей агентов.
Импликации (c) → (b) → (a) просты; самая сложная часть — доказать, что (a) → (c). МакЛеннан доказывает это, используя теорему о многогранниках, разделяющих гиперплоскости . [7]
Богомольная и Мельница [4] : Лем.3 докажите еще одну полезную характеристику sd-эффективности для той же справедливой настройки случайного назначения, но со строгим ранжированием элементов. Определите граф обмена данного дробного распределения как ориентированный граф , в котором узлами являются элементы и существует дуга x → y тогда и только тогда, когда существует агент i , который предпочитает x и получает положительную долю y. Определите распределение как ациклическое , если его граф обмена не имеет направленных циклов. Тогда распределение будет sd-эффективным тогда и только тогда, когда оно ациклично.
Фишберн доказал следующую эквивалентность отношений доминирования дискретных пакетов с адаптивным ранжированием пакетов: [8] [1] : Лем.2.1
- Если X i >> Y i (то есть: X i ≠ Y i , и для каждого элемента z у X i есть по крайней мере столько же элементов, которые по крайней мере так же хороши, как z), то для каждого адаптивного рейтинга пакета, соответствующего рейтинг элемента X i >Y i .
- Если не X i >> Y i , то существует по крайней мере один адаптивный рейтинг пакета, соответствующий рейтингу элемента, для которого X i <Y i .
Следовательно, для отношений доминирования дискретных распределений справедливо следующее: X >> Y тогда и только тогда, когда X обязательно доминирует по Парето Y . [1] : 8
Характеристики
[ редактировать ]Если X i wsd Y i , то |X i | ≥ |Y я | , то есть общее количество объектов (дискретных или дробных) в X i должно быть не меньше, чем в Y i . Это происходит потому, что если |X i | < |Y я | , то для оценки, которая присваивает почти одинаковое значение всем предметам, v( X i ) < v( Y i ).
Это означает, что если X wsd Y и X и Y являются полными распределениями (все объекты распределены), то обязательно |X i | = |Y я | для всех агентов i . [1] : Лем.2.2 Другими словами, в полном распределении X может обязательно доминировать только распределение Y, которое присваивает каждому агенту ту же сумму, что и X.
Это означает, что, в частности, если X является sd-эффективным в множестве всех распределений, которые дают ровно 1 единицу каждому агенту, то X в целом является sd-эффективным.
Лексикографическое доминирование, Парето-эффективность
[ редактировать ]Чо представляет два других понятия эффективности для установления справедливого случайного назначения , основанных на лексикографическом доминировании .
Распределение X = (X 1 ,...,X n ) нисходящим лексикографически (dl) доминирует над другим распределением Y = (Y 1 ,...,Y n ), если для каждого агента i, X i слабо-dl- доминирует Y i , и по крайней мере для одного агента j X j строго dl-доминирует Y j . Распределение называется dl-эффективным, если не существует другого распределения, которое dl-доминировало бы над ним.
Аналогично, основываясь на понятии восходящего лексикографического (ul) доминирования , распределение называется ul-эффективным, если нет другого распределения, которое бы ul-доминировало над ним.
В общем, сд-доминирование подразумевает дл-доминирование и ул-доминирование. Следовательно, dl-эффективность и ul-эффективность подразумевают sd-эффективность.
Эквиваленты
[ редактировать ]Рассмотрим настройку справедливого случайного назначения (ранги пакетов аддитивны , распределения могут быть дробными , а общая доля, отдаваемая каждому агенту, должна быть равна 1) со строгим ранжированием элементов, где элементов может быть больше, чем агентов (поэтому некоторые элементы могут остаются нераспределенными). Чо и Доган [6] докажите, что в данном конкретном случае dl-эффективность и ul-эффективность эквивалентны sd-эффективности. В частности, они доказывают, что если распределение X эффективно по sd/ld/ul, то:
- Граф обмена X ацикличен, и -
- X не расточителен («расточительно» означает, что некоторый агент i , который получает положительную долю предмета x , предпочитает другой предмет y , который не распределен полностью).
Эквивалентность не выполняется, если существуют ограничения распределения: существуют распределения, которые являются эффективными с точки зрения SD, но не эффективными с точки зрения dl. [9] : Пример 4
Дальнейшее чтение
[ редактировать ]- Азиз, Гасперс, Маккензи и Уолш [10] изучать вычислительные вопросы, связанные с понятиями порядковой справедливости. В разделе 7 они кратко изучают sd-эффективность по Парето.
- Доган, Доган и Йылдыз [11] изучите другое отношение доминирования между распределениями: распределение X доминирует над распределением Y, если оно эффективно по Парето для большего набора рангов пакетов, соответствующих рейтингам элементов.
- Абдулкадироглу и Сёнмез [12] исследовать связь между sd-эффективностью и эффективностью Парето ex-post (в контексте случайного назначения). Они вводят новое понятие доминирования для наборов заданий и показывают, что лотерея является sd-эффективной тогда и только тогда, когда каждое подмножество поддержки лотереи не доминируется.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д и ж г час Брамс, Стивен Дж.; Эдельман, Пол Х.; Фишберн, Питер К. (1 сентября 2003 г.). «Справедливый раздел неделимых вещей» . Теория и решение . 55 (2): 147–180. дои : 10.1023/B:THEO.0000024421.85722.0a . ISSN 1573-7187 . S2CID 153943630 .
- ^ Перейти обратно: а б Бувере, Сильвен; Эндрисс, Улле; Ланг, Жером (4 августа 2010 г.). «Справедливое разделение при порядковых предпочтениях: расчет распределения неделимых товаров без зависти» . Материалы конференции ECAI 2010 г. 2010: 19-я Европейская конференция по искусственному интеллекту . НЛД: IOS Press: 387–392. ISBN 978-1-60750-605-8 .
- ^ Перейти обратно: а б Сегал-Халеви, Эрель; хасидим, Авинатан; Азиз, Харис (10 марта 2020 г.). «Справедливое распределение с уменьшением различий» . Журнал исследований искусственного интеллекта . 67 : 471–507–471–507. arXiv : 1705.07993 . дои : 10.1613/jair.1.11994 . ISSN 1076-9757 . S2CID 108290839 .
- ^ Перейти обратно: а б с Богомольная, Анна; Мулен, Эрве (01 октября 2001 г.). «Новое решение проблемы случайного назначения» . Журнал экономической теории . 100 (2): 295–328. дои : 10.1006/jeth.2000.2710 . ISSN 0022-0531 .
- ^ Катта, Акшай-Кумар; Сетураман, Джей (2006). «Решение проблемы случайного назначения в области полных предпочтений». Журнал экономической теории . 131 (1): 231. doi : 10.1016/j.jet.2005.05.001 .
- ^ Перейти обратно: а б Чо, Вонки Джо; Доган, Баттал (1 сентября 2016 г.). «Эквивалентность понятий эффективности для порядковых задач назначения» . Письма по экономике . 146 : 8–12. дои : 10.1016/j.econlet.2016.07.007 . ISSN 0165-1765 .
- ^ Перейти обратно: а б МакЛеннан, Эндрю (1 августа 2002 г.). «Порядковая эффективность и теорема о многогранной разделяющей гиперплоскости» . Журнал экономической теории . 105 (2): 435–449. дои : 10.1006/jeth.2001.2864 . ISSN 0022-0531 .
- ^ Фишберн, Питер К. (1 марта 1996 г.). «Конечная линейная качественная вероятность» . Журнал математической психологии . 40 (1): 64–77. дои : 10.1006/jmps.1996.0004 . ISSN 0022-2496 .
- ^ Азиз, Харис; Брандл, Флориан (01 сентября 2022 г.). «Правило бдительного питания: общий подход к вероятностному экономическому проектированию с ограничениями» . Игры и экономическое поведение . 135 : 168–187. arXiv : 2008.08991 . дои : 10.1016/j.geb.2022.06.002 . ISSN 0899-8256 . S2CID 221186811 .
- ^ Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (01 октября 2015 г.). «Справедливое распределение неделимых объектов по порядковым предпочтениям» . Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . дои : 10.1016/j.artint.2015.06.002 . ISSN 0004-3702 . S2CID 1408197 .
- ^ Доган, Баттал; Доган, Серхат; Йылдыз, Кемаль (01 мая 2018 г.). «Новый критерий ожидаемой эффективности и последствия для вероятностного последовательного механизма» . Журнал экономической теории . 175 : 178–200. дои : 10.1016/j.jet.2018.01.011 . hdl : 11693/48988 . ISSN 0022-0531 .
- ^ Абдулкадироглу, Атила; Сёнмез, Тайфун (1 сентября 2003 г.). «Порядковая эффективность и доминируемые наборы заданий» . Журнал экономической теории . 112 (1): 157–172. дои : 10.1016/S0022-0531(03)00091-7 . HDL : 10161/1940 . ISSN 0022-0531 .