Право (справедливое разделение)

Ценность, которую сторона в идеале хотела бы получить

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

Деление денег

Даже когда нужно разделить только деньги и для каждого получателя указана фиксированная сумма, проблема может быть сложной. Указанные суммы могут быть больше или меньше суммы денег, и тогда прибыль или убыток нужно будет разделить. В настоящее время в законодательстве обычно используется пропорциональное правило , и оно является предположением по умолчанию в теории банкротства . Однако можно использовать и другие правила. Например:

• Число Шепли является одним из распространенных методов определения переговорной силы , как это можно увидеть на примере проблемы аэропорта .
• С другой стороны, экономика благосостояния пытается определить распределение в зависимости от функции общественного благосостояния .
• Люди также могут договориться о своих относительных правах посредством процесса консенсуса. Например, они могут сказать, что, по их мнению, все остальные имеют право, и если оценки совпадают, то они имеют согласованное беспристрастное консенсусное разделение. ^[1]
• Правила приоритета — это еще один вид механизма распределения с различными правами. ^[2]

В Талмуде

В Талмуде есть ряд примеров, когда права не определяются на пропорциональной основе.

• Проблема спорного предмета одежды. Если один человек претендует на весь кусок ткани, а другой — на половину, то он делится на 3/4 и 1/4. ^[3]
• Проблема раздела имущества. Три жены имеют права на 100, 200 и 300 zuz . Рассматриваются три случая: если имущество составляет 100 zuz, то они получают по 33 и треть каждая, если 200, то 50, 75, 75, а если 300, то 50, 100 и 150. ^[4]
• Прибыль от совместного фонда. Если два человека вкладывают 200 и 100 в фонд и покупают быка для пахоты и используют его для этой цели, они должны разделить прибыль поровну между собой. Но если они вместо этого режут быка, они делят прибыль пропорционально. Это обсуждается в Вавилонском Талмуде (сразу после проблемы раздела имущества). ^[4]
• Задача Ибн Эзры. Это более поздняя задача о разделе имущества, которая была решена другим способом. Человек с имуществом в 120 умирает, завещав 120, 60, 40 и 30 своим четырем сыновьям. Рекомендация состояла в том, чтобы присудить (120–60)/1+(60–40)/2+(40–30)/3+(30–0)/4 первому и суммы с удаленными ведущими членами для остальных, заканчивающиеся на 30/4 для последнего. Это распределение отличается от предыдущего раздела имущества. ^[4]

Все эти решения могут быть смоделированы с помощью кооперативных игр . Проблема раздела имущества имеет большую литературу и впервые получила теоретическую основу в теории игр Робертом Дж. Ауманном и Майклом Машлером в 1985 году. ^[5] См. правило о спорной одежде .

Разделение непрерывных ресурсов

Справедливое разделение пирога — это проблема деления неоднородного непрерывного ресурса. Всегда существует пропорциональное разделение пирога, учитывающее различные права. Два основных вопроса исследования: (a) сколько разрезов требуется для справедливого разделения? (b) сколько запросов требуется для вычисления разделения? Смотрите:

• Пропорциональное разрезание торта с различными правами .
• Разрезание торта без зависти с разными правами .

Облачные вычислительные среды требуют разделения нескольких однородных разделяемых ресурсов (например, памяти или ЦП) между пользователями, где каждому пользователю требуется разная комбинация ресурсов. ^[6] Условия, в которых агенты могут иметь разные права, были изучены ^[7] и. ^[8]

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

Одинаковые неделимые предметы - разделение мест в парламентах

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

Распределение мест по численности населения может оставить небольшие избирательные округа вообще без голоса. Самое простое решение — иметь избирательные округа одинакового размера. Иногда, однако, это может оказаться невозможным — например, в Европейском Союзе или Соединенных Штатах . Обеспечение пропорциональности «права голоса» размеру избирательных округов — это проблема права.

Существует ряд методов, которые вычисляют силу голоса для избирательных округов разного размера или веса. Основными из них являются индекс силы Шепли-Шубика , индекс силы Банцхафа . Эти индексы силы предполагают, что избирательные округа могут объединяться любым случайным образом и приближаются к квадратному корню веса, как дано методом Пенроуза . Это предположение не соответствует реальной практике, и можно утверждать, что более крупные избирательные округа подвергаются ими несправедливому обращению.

Разнородные неделимые элементы

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

Азиз, Гасперс, Маккензи и Уолш ^{[9] : раздел 7.2} определяет пропорциональность и отсутствие зависти для агентов с различными правами, когда агенты раскрывают только порядковый рейтинг элементов, а не их полные функции полезности. Они представляют полиномиальный алгоритм для проверки того, существует ли распределение, которое возможно пропорционально (пропорционально в соответствии по крайней мере с одним профилем полезности, соответствующим рейтингам агентов), или обязательно пропорционально (пропорционально в соответствии со всеми профилями полезности, соответствующими рейтингам).

Фархади, Годси, Хаджиагайи, Лахайе, Пеннок, Седдигин, Седдигин и Ями ^[10] определили взвешенную максиминную долю (WMMS) как обобщение максиминной доли для агентов с различными правами. Они показали, что наилучшая достижимая мультипликативная гарантия для WMMS составляет 1/ n в общем случае и 1/2 в особом случае, когда ценность каждого товара для каждого агента не превышает WMMS агента. Азиз, Чан и Ли ^[11] адаптировали понятие WMMS к домашним делам (элементам с отрицательной полезностью). Они показали, что даже для двух агентов невозможно гарантировать более 4/3 WMMS (обратите внимание, что в случае домашних дел коэффициенты аппроксимации больше 1, и чем меньше, тем лучше). Они представляют алгоритм аппроксимации 3/2-WMMS для двух агентов и алгоритм WMMS для n агентов с бинарными оценками. Они также определяют OWMMS, которая является оптимальным приближением WMMS, достижимым в данном случае. Они представляют полиномиальный алгоритм, который достигает 4-факторного приближения OWMMS.

WMMS является кардинальным понятием в том смысле, что если кардинальные полезности агента изменяются, то набор наборов, которые удовлетворяют WMMS для агента, может измениться. Бабаиофф, Нисан и Талгам-Коэн ^[12] представили другую адаптацию MMS для агентов с различными правами, которая основана только на порядковом ранжировании агентом наборов. Они показывают, что это понятие справедливости достигается путем конкурентного равновесия с различными бюджетами, где бюджеты пропорциональны правам. Это понятие справедливости называется порядковой максиминной долей (OMMS) Чакраборти, Сегал-Халеви и Суксомпонг. ^[13] Связь между различными порядковыми приближениями MMS дополнительно изучается Сегалом-Халеви. ^{[14] [15]}

Бабаиофф, Эзра и Фейдж ^[16] представляют другое порядковое понятие, более сильное, чем OMMS, которое они называют AnyPrice Share (APS) . Они показывают алгоритм полиномиального времени, который достигает 3/5-доли APS.

Азиз, Мулен и Сандомирский ^[17] представляют сильно полиномиальный алгоритм времени, который всегда находит оптимальное по Парето и WPROP(0,1) распределение для агентов с различными правами и произвольными (положительными или отрицательными) оценками.

Релаксации WEF были изучены, до сих пор, только для товаров. Чакраборти, Игараши и Суксомпонг ^[18] представили алгоритм взвешенного кругового перебора для WEF(1,0). В последующей работе Чакраборти, Шмидт-Крепелин и Суксомпонг обобщили алгоритм взвешенного кругового перебора на общие последовательности выбора и изучили различные свойства монотонности этих последовательностей.

Вещи и деньги

В задаче справедливого распределения вещей и денег денежные переводы могут использоваться для достижения точной справедливости неделимых благ.

Корради и Корради ^[19] определяют распределение как справедливое , если полезность каждого агента i (определяемая как стоимость предметов плюс деньги, предоставленные i ) равна r t _i u _i (AllItems), где r одинаково для всех агентов.

Они представляют алгоритм, который находит справедливое распределение при r >= 1, что означает, что распределение также является пропорциональным .

Торг

Кооперативный торг — это абстрактная проблема выбора допустимого вектора полезности как функции набора допустимых векторов полезности (справедливый раздел — это частный случай торга).

Три классических решения по торгам имеют варианты для агентов с различными правами. В частности:

• Калай ^[20] расширил решение Нэша по торгам , введя максимально взвешенное правило благосостояния Нэша;
• Томсон ^[21] расширил решение по переговорам Калаи-Смородинского ;
• Дризен ^[22] расширил правило лексимина , введя асимметричное правило лексимина.

Ссылки

1. Жоффруа де Клиппель; ЭрвеМулен; Николаус Тайдман (март 2008 г.), «Беспристрастное деление доллара», Journal of Economic Theory , 139 (1): 176–191, CiteSeerX  10.1.1.397.1420 , doi :10.1016/j.jet.2007.06.005
2. Мулен, Эрве (май 2000 г.). «Правила приоритета и другие методы асимметричного нормирования». Econometrica . 68 (3): 643–684. doi :10.1111/1468-0262.00126. ISSN  0012-9682.
3. Бава Меция 2а. Спорная одежда
4. Ketubot 93a. Проблема раздела имущества
5. Игровой теоретико-аналитический анализ проблемы банкротства из Талмуда Роберта Дж. Ауманна и Майкла Машлера. Журнал экономической теории 36, 195-213 (1985)
6. «Доминирующая справедливость ресурсов: справедливое распределение нескольких типов ресурсов». 2011.
7. Долев, Дэнни; ​​Фейтельсон, Дрор Г.; Хэлперн, Джозеф И.; Купферман, Раз; Линиал, Натан (2012-01-08). «Нет обоснованных жалоб». Труды 3-й конференции по инновациям в теоретической информатике . ITCS '12. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 68–75. doi :10.1145/2090236.2090243. ISBN 978-1-4503-1115-1. S2CID  9105218.
8. Гутман, Авиталь; Нисан, Ноам (19.04.2012). «Справедливое распределение без торговли». arXiv : 1204.4286 [cs.GT].
9. Азиз, Харис; Гасперс, Серж; Маккензи, Саймон; Уолш, Тоби (2015-10-01). «Справедливое назначение неделимых объектов при порядковых предпочтениях». Искусственный интеллект . 227 : 71–92. arXiv : 1312.6546 . doi : 10.1016/j.artint.2015.06.002 . ISSN  0004-3702. S2CID  1408197.
10. Фархади, Алиреза; Годси, Мохаммед; Хаджиагайи, Мохаммад Таги; Лаэ, Себастьен; Пеннок, Дэвид; Седдигин, Масуд; Седдигин, Саид; Ями, Хади (07 января 2019 г.). «Справедливое распределение неделимых товаров между асимметричными агентами». Журнал исследований искусственного интеллекта . 64 : 1–20. arXiv : 1703.01649 . дои : 10.1613/jair.1.11291 . ISSN  1076-9757. S2CID  15326855.
11. Азиз, Харис; Чан, Хау; Ли, Бо (18.06.2019). «Взвешенное распределение неделимых домашних дел по справедливой максминовой схеме». arXiv : 1906.07602 [cs.GT].
12. Бабаиофф, Моше; Нисан, Ноам; Талгам-Коэн, Инбал (2021-02-01). «Конкурентное равновесие с неделимыми товарами и общими бюджетами». Математика исследования операций . 46 (1): 382–403. arXiv : 1703.08150 . doi : 10.1287/moor.2020.1062. ISSN  0364-765X. S2CID  8514018.
13. Чакраборти, Митхун; Сегал-Халеви, Эрел; Суксомпонг, Варут (2024). «Повторный взгляд на понятия взвешенной справедливости для неделимых предметов». arXiv : 2112.04166 . doi :10.1145/3665799. {{cite book}}: |journal=игнорируется ( помощь ) ; Отсутствует или пусто |title=( помощь )
14. Сегал-Халеви, Эрель (2020-02-20). «Конкурентное равновесие почти для всех доходов: существование и справедливость». Автономные агенты и многоагентные системы . 34 (1): 26. arXiv : 1705.04212 . doi : 10.1007/s10458-020-09444-z. ISSN  1573-7454. S2CID  210911501.
15. Сегал-Халеви, Эрель (18 декабря 2019 г.). «Максиминные отношения доминирования». arXiv : 1912.08763 [math.CO].
16. Бабаиофф, Моше; Эзра, Томер; Файге, Уриэль (15.11.2021). «Справедливое распределение для агентов с произвольными правами». arXiv : 2103.04304 [cs.GT].
17. Азиз, Харис; Мулен, Эрве; Сандомирский, Федор (2020-09-01). «Алгоритм полиномиального времени для вычисления оптимального по Парето и почти пропорционального распределения». Operations Research Letters . 48 (5): 573–578. arXiv : 1909.00740 . doi : 10.1016/j.orl.2020.07.005. ISSN  0167-6377. S2CID  202541717.
18. Чакраборти, Митхун; Игараси, Аюми; Суксомпонг, Варут; Зик, Яир (16.08.2021). «Взвешенная свобода от зависти при распределении неделимых предметов». Труды ACM по экономике и вычислениям . 9 (3): 18:1–39. arXiv : 1909.10502 . doi : 10.1145/3457166. ISSN  2167-8375. S2CID  202719373.
19. Корради, Марко Клаудио; Корради, Валентина (21.04.2001). «Скорректированная процедура Кнастера при неравных правах». SSRN  2427304.
20. Калай, Э. (1977-09-01). «Несимметричные решения Нэша и репликации переговоров двух лиц». Международный журнал теории игр . 6 (3): 129–133. doi :10.1007/BF01774658. ISSN  1432-1270. S2CID  122236229.
21. Томсон, Уильям (1994), «Кооперативные модели переговоров», Справочник по теории игр с экономическими приложениями , 2 , Elsevier: 1237–1284, doi :10.1016/S1574-0005(05)80067-0 , получено 29.03.2022
22. Driesen, Bram W. (2012). Асимметричное решение Leximin (Отчет). doi :10.11588/heidok.00013124.