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

Скорректированный победитель (AW) — это алгоритм распределения предметов без зависти . Учитывая две стороны и некоторые отдельные товары, он возвращает распределение товаров между двумя сторонами, которое:

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

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

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

Алгоритм

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

Если совокупная стоимость товаров одной стороны больше, чем у другой, алгоритм упорядочивает товары стороны с более высокой стоимостью в возрастающем порядке на основе соотношения ${\frac {{\textrm {value}}{\phantom {n}}{\textrm {for}}{\phantom {n}}{\textrm {higher-combined-value}}{\phantom {n}}{\textrm {party}}}{{\textrm {value}}{\phantom {n}}{\textrm {for}}{\phantom {n}}{\textrm {lower-combined-value}}{\phantom {n}}{\textrm {party}}}}$ , и начинает передавать их от стороны с более высокой совокупной стоимостью к стороне с более низкой совокупной стоимостью до тех пор, пока их оценки не станут почти равными (перемещение большего количества товаров приведет к тому, что сторона с более низкой совокупной стоимостью теперь будет иметь более высокую совокупную стоимость, чем другая) . Следующий товар затем делится между сторонами так, что их ценности становятся одинаковыми.

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

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

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

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

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

Симуляторы

Случаев использования «Скорректированного победителя» для разрешения реальных споров не зарегистрировано. Однако в некоторых исследованиях моделировалось, к чему привели бы определенные споры, если бы был использован алгоритм, в том числе

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

Ограничения

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

^ Перейти обратно: ^а ^б Азиз, Харис.; Брынзей, Симина; Филос-Рацикас, Арис; Сорен Кристоффер Стил, Сорен (2015). «Процедура скорректированного победителя: характеристики и равновесие» . Материалы двадцать четвертой Международной совместной конференции по искусственному интеллекту . стр. 454–460. arXiv : 1503.06665 . Бибкод : 2015arXiv150306665A .
^ Перейти обратно: ^а ^б ^с ^д Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. ISBN 0-521-55644-9 .
^ Стивен Дж. Брамс и Алан Д. Тейлр (2000). Беспроигрышное решение: гарантия справедливого распределения акций для всех . Нортон. ISBN 978-0393320817 .
^ Патент США № 5,983,205 , Компьютерный метод справедливого разделения собственности на товары .
^ Брамс, Стивен Дж.; Тогман, Джеффри М. (1996). «Кемп-Дэвид: было ли соглашение справедливым?». Управление конфликтами и наука о мире . 15 (1): 99–112. дои : 10.1177/073889429601500105 . ISSN 0738-8942 . S2CID 154854128 .
^ Масуд, Танса Джордж (01 июня 2000 г.). «Справедливое разделение, скорректированная процедура победителя (AW) и израильско-палестинский конфликт». Журнал разрешения конфликтов . 44 (3): 333–358. дои : 10.1177/0022002700044003003 . ISSN 0022-0027 . S2CID 154593488 .
^ Денун, DBH; Брамс, SJ (1 февраля 1997 г.). «Справедливое разделение: новый подход к спору об островах Спратли». Международные переговоры . 2 (2): 303–329. дои : 10.1163/15718069720847997 . ISSN 1571-8069 .
^ Уилсон, Стивен Дж. (1995). «Справедливое разделение с использованием линейного программирования» (PDF) . Университет штата Айова (неопубликованная рукопись) .
^ Сэмюэл Висмут; Иван Близнец; Эрел Сегал-Халеви. «Справедливое разделение с ограниченным долевым участием: бинарные и невырожденные оценки». arXiv : 1912.00459 .
^ Сандомирский, Федор; Сегал-Халеви, Эрель (01 мая 2022 г.). «Эффективное справедливое разделение с минимальным долевым участием» . Исследование операций . 70 (3): 1762–1782. arXiv : 1908.01669 . дои : 10.1287/opre.2022.2279 . ISSN 0030-364X . S2CID 247922344 .
^ Азиз, Харис; Караяннис, Иоаннис; Игараси, Аюми; Уолш, Тоби (01 августа 2019 г.). «Справедливое распределение неделимых благ и работ». Материалы двадцать восьмой Международной совместной конференции по искусственному интеллекту . Калифорния: Международные совместные конференции по организации искусственного интеллекта. стр. 53–59. дои : 10.24963/ijcai.2019/8 . ISBN 978-0-9992411-4-1 . S2CID 197468732 .

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

Веб-сайт, объясняющий скорректированный победитель

[Aziz-1] Перейти обратно: ^а ^б Азиз, Харис.; Брынзей, Симина; Филос-Рацикас, Арис; Сорен Кристоффер Стил, Сорен (2015). «Процедура скорректированного победителя: характеристики и равновесие» . Материалы двадцать четвертой Международной совместной конференции по искусственному интеллекту . стр. 454–460. arXiv : 1503.06665 . Бибкод : 2015arXiv150306665A .

[:0-2] Перейти обратно: ^а ^б ^с ^д Брамс, Стивен Дж.; Тейлор, Алан Д. (1996). Справедливое разделение: от разрезания торта до разрешения споров . Издательство Кембриджского университета. ISBN 0-521-55644-9 .

[3] Стивен Дж. Брамс и Алан Д. Тейлр (2000). Беспроигрышное решение: гарантия справедливого распределения акций для всех . Нортон. ISBN 978-0393320817 .

[patent-4] Патент США № 5,983,205 , Компьютерный метод справедливого разделения собственности на товары .

[5] Брамс, Стивен Дж.; Тогман, Джеффри М. (1996). «Кемп-Дэвид: было ли соглашение справедливым?». Управление конфликтами и наука о мире . 15 (1): 99–112. дои : 10.1177/073889429601500105 . ISSN 0738-8942 . S2CID 154854128 .

[6] Масуд, Танса Джордж (01 июня 2000 г.). «Справедливое разделение, скорректированная процедура победителя (AW) и израильско-палестинский конфликт». Журнал разрешения конфликтов . 44 (3): 333–358. дои : 10.1177/0022002700044003003 . ISSN 0022-0027 . S2CID 154593488 .

[7] Денун, DBH; Брамс, SJ (1 февраля 1997 г.). «Справедливое разделение: новый подход к спору об островах Спратли». Международные переговоры . 2 (2): 303–329. дои : 10.1163/15718069720847997 . ISSN 1571-8069 .

[8] Уилсон, Стивен Дж. (1995). «Справедливое разделение с использованием линейного программирования» (PDF) . Университет штата Айова (неопубликованная рукопись) .

[9] Сэмюэл Висмут; Иван Близнец; Эрел Сегал-Халеви. «Справедливое разделение с ограниченным долевым участием: бинарные и невырожденные оценки». arXiv : 1912.00459 .

[10] Сандомирский, Федор; Сегал-Халеви, Эрель (01 мая 2022 г.). «Эффективное справедливое разделение с минимальным долевым участием» . Исследование операций . 70 (3): 1762–1782. arXiv : 1908.01669 . дои : 10.1287/opre.2022.2279 . ISSN 0030-364X . S2CID 247922344 .

[11] Азиз, Харис; Караяннис, Иоаннис; Игараси, Аюми; Уолш, Тоби (01 августа 2019 г.). «Справедливое распределение неделимых благ и работ». Материалы двадцать восьмой Международной совместной конференции по искусственному интеллекту . Калифорния: Международные совместные конференции по организации искусственного интеллекта. стр. 53–59. дои : 10.24963/ijcai.2019/8 . ISBN 978-0-9992411-4-1 . S2CID 197468732 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]