Процедура поднутрения

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

Предположения [ править ]

Процедура подрезки требует только следующих слабых предположений о людях:

У каждого человека слабое отношение предпочтений к подмножествам предметов.
Каждое отношение предпочтения является строго монотонным : для каждого множества и элемента , человек строго предпочитает , чтобы . ${\ displaystyle X}$ ${\ displaystyle y \ notin X}$ ${\ Displaystyle X \ чашка y}$ ${\ displaystyle X}$

Это не предполагается , что агенты имеют адаптивные предпочтения .

Основная идея [ править ]

Процедуру подрезания можно рассматривать как обобщение протокола « разделяй и выбирай» с делимого ресурса на неделимый. Протокол «разделяй и выбирай» требует, чтобы один человек разделил ресурс на две равные части. Но если ресурс содержит неделимые части, то сделать точно равное сокращение может быть невозможно. Соответственно, процедура поднутрения работает с почти равными надрезами . Почти равный разрез человека - это разбиение набора элементов на два непересекающихся подмножества (X, Y) таким образом, что:

Человек слабо предпочитает X Y;
Если какой-либо отдельный элемент перемещается из X в Y, то человек строго предпочитает Y вместо X (т. Е. Для всех x в X человек предпочитает это ). ${\ Displaystyle Y \ чашка х}$ ${\ Displaystyle X \ setminus x}$

Процедура [ править ]

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

Случай 1 : отчеты разные, например, есть раздел (X, Y), который является почти равным для Алисы, но не для Джорджа. Затем эта перегородка преподносится Джорджу. Джордж может принять или отклонить его:
- Джордж принимает разделение, если он предпочитает Y вместо X. Затем Алиса получает X, а Джордж получает Y, и полученное распределение не вызывает зависти.
- Джордж отвергает разделение, если он предпочитает X вместо Y. По предположению, (X, Y) не является почти равным разрезом для Джорджа. Таким образом, существует пункт х в X такое , что Джордж предпочитает , чтобы . Джордж сообщает ; мы говорим, что Джордж подрезает X. Поскольку (X, Y) почти равное сечение для Алисы, Алиса предпочитает это . Затем Джордж получает, а Алиса получает, и полученное распределение не вызывает зависти. ${\ Displaystyle X \ setminus x}$ ${\ Displaystyle Y \ чашка х}$ ${\ Displaystyle X \ setminus x}$ ${\ Displaystyle Y \ чашка х}$ ${\ Displaystyle X \ setminus x}$ ${\ Displaystyle X \ setminus x}$ ${\ Displaystyle Y \ чашка х}$
Случай 2 : отчеты идентичны, т.е. Алиса и Джордж имеют одинаковый набор почти одинаковых разрезов. Затем процедура спрашивает их, является ли один из их почти равных разрезов точно равным. Согласно предположению строгой монотонности, (X, Y) является точно равным разрезом, если и только если оба (X, Y) и (Y, X) являются почти равными разрезами. Следовательно, в случае 2 Алиса и Джордж имеют одинаковый набор точно равных разрезов. Есть два подслучая:
- Простой случай: существует точно такой же разрез (X, Y). Тогда один человек (независимо от того, кто) получает X, а другой - Y, и разделение происходит без зависти.
- Трудный случай: не бывает абсолютно равного среза. Затем процедура возвращается и сообщает, что «распределения без зависти не существует».

Чтобы доказать правильность процедуры, достаточно доказать, что в Жестком случае распределения без зависти не существует. В самом деле, предположим, что существует распределение (X, Y) без зависти. Поскольку мы находимся в жестком случае, (X, Y) не является точно равным разрезом. Таким образом, один человек (например, Джордж) строго предпочитает Y вместо X, в то время как другой человек (Алиса) слабо предпочитает X вместо Y. Если (X, Y) не является почти равным для Алисы, то мы перемещаем некоторые элементы из X в Y, пока мы не получим раздел (X ', Y'), который является почти равным разрезом для Алисы. Алиса по-прежнему слабо предпочитает X 'Y'. Исходя из предположения о монотонности, Джордж по-прежнему строго предпочитает Y 'X'. Это означает, что (X ', Y') не является почти равным для Джорджа. Но в жестком случае оба агента имеют одинаковый набор почти равных разрезов - противоречие.

Сложность выполнения [ править ]

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

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

Неравные права [ править ]

Процедура подрезки также может работать, когда агенты имеют неравные права. ^[2] Предположим, что каждый агент имеет право на часть предметов. Затем определение почти равной доли (для агента ) следует изменить следующим образом: ${\ displaystyle i}$ ${\ displaystyle e_ {i}}$ ${\ displaystyle i}$

${\ displaystyle u_ {i} (X) \ geq {c_ {i} \ over c _ {- i}} u_ {i} (Y)}$ , и
Для всех x в X ${\ displaystyle u_ {i} (X \ setminus x) <{c_ {i} \ over c _ {- i}} u_ {i} (Y \ cup x)}$

Фаза генерации [ править ]

В оригинальной публикации ^[1] процедуре поднутрения предшествует следующая фаза генерации :

Пока на столе лежат предметы:
- Каждый сообщает о своем лучшем предмете.
  - Если отчеты разные, то каждый получает свой лучший результат.
  - Если отчеты идентичны, то лучший предмет помещается в оспариваемую стопку .

Выточки Описанная выше процедура затем выполняется только на спорной кучу.

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

	Алиса	Георгий
ш	9	1
Икс	8	4
y	7	3
z	6	2

Однако фаза генерации имеет ряд недостатков: ^[2]

Это может привести к тому, что процедура пропустит возможное распределение без зависти. Например, предположим, что имеется четыре предмета, и их оценки такие же, как в соседней таблице. Распределение, которое дает {w, z} Алисе и {x, y} Джорджу, не вызывает зависти. В самом деле, его можно найти с помощью процедуры с голым вырезом, так как раздел ({w, z}, {x, y}) является почти равным разрезом для Алисы, но не для Джорджа, и Джордж согласился бы с этим разделением. Но на этапе генерации сначала Алиса получает w, а Джордж - x, а остальные элементы {y, z} помещаются в оспариваемую кучу, и нет свободного от зависти распределения оспариваемой кучи, поэтому процедура не выполняется.
Это требует, чтобы люди выбирали свой «лучший предмет», не зная, какие еще предметы они собираются получить. Это основано на предположении, что товары являются независимыми товарами . В качестве альтернативы, он полагается на предположение о быстродействии : если в пакете элемент заменен на лучший элемент, то результирующий набор лучше (это тесно связано со слабо аддитивными предпочтениями).
Не работает, когда у агентов неравные требования.
Он основан на последовательном распределении, которое подвержено стратегическим манипуляциям.

См. Также [ править ]

Снижение процедуры Спроса и процедура зависти-граф - два дополнительных процедур , основанных на порядковом ранжировании пучков.

Ссылки [ править ]

^ ^a ^b Брамс, Стивен Дж .; Килгур, Д. Марк; Кламлер, Кристиан (2011). «Процедура подрезания: алгоритм разделения неделимых элементов без зависти» (PDF) . Социальный выбор и благосостояние . 39 (2-3): 615. DOI : 10.1007 / s00355-011-0599-1 .
^ ^a ^b ^c Азиз, Харис (2015). «Примечание о процедуре подрезки». Социальный выбор и благосостояние . 45 (4): 723–728. arXiv : 1312.6444 . DOI : 10.1007 / s00355-015-0877-4 .

Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору . Издательство Кембриджского университета. С. 306–307. ISBN 9781107060432.( бесплатная онлайн-версия )

[bkk12-1] Брамс, Стивен Дж .; Килгур, Д. Марк; Кламлер, Кристиан (2011). «Процедура подрезания: алгоритм разделения неделимых элементов без зависти» (PDF) . Социальный выбор и благосостояние . 39 (2-3): 615. DOI : 10.1007 / s00355-011-0599-1 .

[a15-2] Азиз, Харис (2015). «Примечание о процедуре подрезки». Социальный выбор и благосостояние . 45 (4): 723–728. arXiv : 1312.6444 . DOI : 10.1007 / s00355-015-0877-4 .

[1]