Скорректированная процедура определения победителя

Method of fairly dividing property

Логотип

Adjusted Winner (AW) — это алгоритм для распределения товаров без зависти . При наличии двух сторон и некоторых дискретных товаров он возвращает разделение товаров между двумя сторонами, которое равно:

1. Отсутствие зависти : каждая сторона считает, что ее доля благ такая же или лучше, чем у противника;
2. Справедливо : «Относительные уровни счастья» обеих сторон, исходя из их долей, равны;
3. Парето-оптимальное : никакое другое распределение не является лучшим для одной стороны и по крайней мере таким же хорошим для другой стороны; и
4. Подразумевает раздел не более одного товара между сторонами.

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

Процедура была разработана Стивеном Брамсом и Аланом Д. Тейлором и опубликована в их книге о справедливом разделении ^{[2] : 65–94,} а затем в отдельной книге. ^{[3] : 69–88} Adjusted Winning ранее был запатентован в Соединенных Штатах, но срок его действия истек в 2016 году. ^[4]

Алгоритм

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

Если совокупная стоимость товаров одной стороны больше, чем у другой, алгоритм затем упорядочивает товары стороны с более высокой стоимостью в порядке возрастания на основе соотношения и начинает передавать их от стороны с более высокой совокупной стоимостью к стороне с более низкой совокупной стоимостью до тех пор, пока их оценки не станут почти равными (перемещение любого большего количества товаров приведет к тому, что сторона с более низкой совокупной стоимостью теперь будет иметь более высокую совокупную стоимость, чем другая). Следующий товар затем делится между сторонами таким образом, что их стоимости становятся одинаковыми. ^{[3] : 71–74} $${\displaystyle {\frac {\text{value for higher-combined-value party}}{\text{value for lower-combined-value party}}},}$$

Например, если две стороны имеют следующие оценки по четырем товарам:

• Алиса: 86, 75, 30, 9
• Боб: 19, 81, 60, 40

Товары сначала будут разделены таким образом, что Алиса получит товар 1, а Боб получит товары 2, 3 и 4. На этом этапе общая оценка товаров Алисы составляет 86, а Боба — 81 + 60 + 40 = 181; таким образом, товары Боба затем упорядочиваются на основе соотношения , что дает ${\displaystyle {\frac {\text{Bob's valuations}}{\text{Alice's valuations}}}}$

• [Хорошо 2 = ], [Хорошо 3 = ], [Хорошо 4 = ]. ${\displaystyle {\frac {81}{75}}}$ ${\displaystyle {\frac {60}{30}}}$ ${\displaystyle {\frac {40}{9}}}$

Перемещение Товара 2 от Боба к Алисе приведет к тому, что оценка Алисы будет выше, чем у Боба (161 против 100), поэтому товары не передаются. Вместо этого Товар 2 делится между Алисой и Бобом: Алиса получает th товара (примерно 60,9%), а Боб получает th (примерно 39,1%). Теперь их оценки становятся и соответственно, которые равны. ${\displaystyle {\frac {95}{156}}}$ ${\displaystyle {\frac {61}{156}}}$ ${\displaystyle 86+{\frac {95}{156}}(75)=131.673...}$ ${\displaystyle 60+40+{\frac {61}{156}}(81)=131.673...}$

Моделирование

Нет ни одного случая использования Adjusted Winner для разрешения реальных споров. Однако некоторые исследования смоделировали, как бы закончились определенные споры, если бы использовался алгоритм, включая

• Кэмп -Дэвидские соглашения , чьи оценочные функции были смоделированы на основе относительной важности каждого вопроса для Израиля и Египта, и чьи теоретические результаты были аналогичны фактическому соглашению; ^[5]
• Для израильско-палестинского конфликта ; ^[6]
• Для спора вокруг островов Спратли ; ^[7]
• Договоры о Панамском канале ; и
• Дело о разводе Джолис против Джолиса в 1980 году . ^{[2] : 95–114.}

Ограничения

AW не является правдивым механизмом : сторона может выиграть, шпионя за своим оппонентом и изменяя его отчеты, чтобы получить большую долю. ^[2] Однако Adjusted Winner всегда имеет приблизительное равновесие Нэша , а при информированном разрешении ничьей также чистое равновесие Нэша. ^[1]

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

Алгоритм также разработан только для двух сторон; когда есть три или более сторон, не может быть распределения, которое одновременно является свободным от зависти, справедливым и Парето-оптимальным. Это можно показать на следующем примере, построенном JHReijnierse, ^{[2] : 82–83} с участием трех сторон и их оценок:

• Алиса: 40, 50, 10
• Боб: 30, 40, 30
• Карл: 30, 30, 40

Единственным Парето-оптимальным и справедливым распределением было бы такое, при котором благо 1 досталось бы Алисе, благо 2 — Бобу и благо 3 — Карлу; однако такое распределение не было бы свободным от зависти, поскольку Алиса завидовала бы Бобу.

Любые два из этих трех свойств могут быть удовлетворены одновременно:

• Можно найти справедливое и свободное от зависти распределение, предоставив каждой стороне равное количество каждого товара.
• Свободное от зависти и оптимальное по Парето распределение можно найти с помощью эффективного по Парето свободного от зависти деления или теоремы Веллера .
• Справедливое и оптимальное по Парето распределение может быть найдено с помощью линейного программирования . ^{[8] [9]}

Более того, можно найти распределение, которое, будучи Парето-оптимальным/свободным от зависти или Парето-оптимальным/справедливым, минимизировало бы количество объектов, которые должны быть разделены между двумя или более сторонами. Это обычно считалось обобщением процедуры Adjusted Winner на три или более сторон. ^[10]

Adjusted Winner предназначен для агентов с положительными оценками по пунктам. Однако его можно обобщить для сторон со смешанными (положительными и отрицательными) оценками. ^[11]

Сопутствующие процедуры

Процедура Брэмса–Тейлора была разработана теми же авторами, но вместо этого она представляет собой процедуру разрезания торта без зависти : она обрабатывает неоднородные ресурсы («торт»), которые сложнее разделить, чем однородные товары Adjusted Winning. ^{[ как? ]} Соответственно, BT гарантирует только отсутствие зависти, а не какие-либо другие атрибуты.

В статье « Эксперименты по справедливому делению» описываются некоторые лабораторные эксперименты, сравнивающие AW с родственными процедурами.

Ссылки

1. Aziz, Haris.; Brânzei, Simina; Filos-Ratsikas, Aris; Søren Kristoffer Stiil, Søren (2015). «Скорректированная процедура победителя: характеристики и равновесия». Труды Двадцать четвертой Международной совместной конференции по искусственному интеллекту . С. 454–460. arXiv : 1503.06665 . Bibcode :2015arXiv150306665A.
2. Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Cambridge University Press. ISBN 0-521-55644-9.
3. Стивен Дж. Брамс и Алан Д. Тайлр (2000). Беспроигрышное решение: гарантия справедливой доли для всех . Нортон. ISBN 978-0393320817.
4. Патент США 5,983,205 , Компьютерный метод справедливого разделения права собственности на товары .
5. Brams, Steven J.; Togman, Jeffrey M. (1996). «Кэмп-Дэвид: было ли соглашение справедливым?». Conflict Management and Peace Science . 15 (1): 99–112. doi :10.1177/073889429601500105. ISSN  0738-8942. S2CID  154854128.
6. Массуд, Танса Джордж (01.06.2000). «Справедливое разделение, скорректированная процедура определения победителя (AW) и израильско-палестинский конфликт». Журнал разрешения конфликтов . 44 (3): 333–358. doi :10.1177/0022002700044003003. ISSN  0022-0027. S2CID  154593488.
7. Денун, DBH; Брамс, SJ (1997-02-01). «Справедливое разделение: новый подход к спору об островах Спратли». Международные переговоры . 2 (2): 303–329. doi :10.1163/15718069720847997. ISSN  1571-8069.
8. Уилсон, Стивен Дж. (1995). "Справедливое деление с использованием линейного программирования" (PDF) . Университет штата Айова (неопубликованная рукопись) .
9. Сэмюэл Бисмут; Иван Близнец; Эрель Сегал-Халеви. «Справедливое деление с ограниченным распределением: бинарные и невырожденные оценки». arXiv : 1912.00459 .
10. Сандомирский, Федор; Сегал-Халеви, Эрель (2022-05-01). «Эффективное справедливое разделение с минимальным разделением». Исследование операций . 70 (3): 1762–1782. arXiv : 1908.01669 . doi : 10.1287/opre.2022.2279. ISSN  0030-364X. S2CID  247922344.
11. Азиз, Харис; Карагианнис, Иоаннис; Игараси, Аюми; Уолш, Тоби (2019-08-01). «Справедливое распределение неделимых благ и дел». Труды Двадцать восьмой Международной совместной конференции по искусственному интеллекту . Калифорния: Международная организация совместных конференций по искусственному интеллекту. стр. 53–59. doi : 10.24963/ijcai.2019/8 . ISBN 978-0-9992411-4-1. S2CID  197468732.

Внешние ссылки

• Сайт с объяснением Adjusted Winner