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

В процедура подреза это процедура для справедливое распределение позиций между двумя людьми. Это доказуемо находит полный распределение предметов без зависти всякий раз, когда такое назначение существует. Его представили Брамс, Килгур и Кламлер.^[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 такой, что Джордж предпочитает ${ Displaystyle X setminus x}$ к ${ Displaystyle Y чашка х}$. Георгий сообщает ${ Displaystyle X setminus x}$; мы говорим, что Джордж поднутрения X. Поскольку (X, Y) является почти равным разрезом для Алисы, Алиса предпочитает ${ 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]

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

Рекомендации

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