AL-процедура (AL-hjkey;rjg)

AL-процедура — это процедура справедливого распределения объектов между двумя лицами. Процедура находит распределение подмножества объектов, при котором будет отсутствовать зависть. Более того, получающееся распределение эффективно по Парето в следующем смысле: нет другого распределения, в котором отсутствует зависть и которое лучше для одного лица и не хуже для любого другого.

AL-процедуру первыми опубликовали Брамс и Кламлер^[1]. Позднее её обобщил Азиз для случая, когда агенты не смогут различить по значимости некоторые предметы^[2].

Предположения

AL-процедура выполнения следующих условий:

Каждое лицо может расположить предметы от лучших до худших (то есть каждое лицо может предоставить строгое^[3] отношение предпочтения на предметах).
Каждое лицо имеет отношения предпочтения на наборах предметов, которое совместимо с адаптивным расширением^[англ.] упорядочения предметов.

Требования

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

Поэтому процедура должна давать распределение, в котором нет зависти, для любого отношения предпочтения, которое согласуется с упорядочением предметов и слабой аддитивностью. Другими словами, процедура должна возвращать распределение, в котором обязательно не будет зависти (обязательно без зависти, ОБЗ-распределение, англ. necessarily envy-free, NEF)^[4].

Пусть двумя лицами будут Алиса и Джордж. Распределение является ОБЗ-распределением для Алисы, если инъекция f из предметов Джорджа в предметы Алисы, такая, что для каждого предмета x, полученного Джорджем, Алиса предпочитает предмет f(x) предмету x. Распределение является ОБЗ-распределением для Джорджа, если выполняется симметричное свойство. Распределение предметов является ОБЗ-распределением, если оно ОБЗ-распределение для обоих партнёров. Заметим, что в ОБЗ-распределении Алиса и Джордж получают одинаковое число предметов.

Пустое распределение, очевидно, является ОБЗ-распределением, но оно очень неэффективно. Поэтому мы ищем «лучшее» распределение среди всех ОБЗ-распределений. ОБЗ-распределение называется эффективным по Парето, если нет другого ОБЗ-распределения, которое лучше для одного предмета и хуже для другого.

BT-процедура

В качестве введения введём следующую простую процедуру дележа:

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

Эта процедура возвращает ОБЗ-распределение. Процедура очень проста, но не очень-то эффективна, поскольку большое число предметов будет отброшено в «Спорную Кучу». AL-процедура немного более сложна, но гарантирует, что «Спорная куча» никогда не больше кучи, получающейся в ВТ-процедуре, но может оказаться меньше.

AL-процедура

AL-процедура работает аналогично BT-процедуре, но перед отправкой в «Спорную Кучу» процедура пытается отдать предмет одному участнику, в качестве компенсации отдать другому участнику другой предмет. Только когда такая компенсация не удаётся, предмет отправляется в «Спорную Кучу».

Например, пусть имеется четыре предмета (1, 2, 3, 4) и предпочтения участников следующие:

Алиса: 1 > 2 > 3 > 4
Джордж: 2 > 3 > 4 > 1

BT-процедура отдаёт предмет 1 Алисе и предмет 2 Джорджу, поскольку они наиболее желаемы и они различны. Теперь и Алиса, и Джордж выбирают предмет 3, так что он отбрасывается. Теперь оба выбирают предмет 4 и он тоже отбрасывается. Конечное распределение: Алиса $\leftarrow \{1\},$ Джордж $\leftarrow \{2\}.$ . Распределение является ОБЗ-распределением, но не эффективно по Парето.

AL-процедура также начинает с передачи предмета 1 Алисе и предмета 2 Джорджу. Теперь, вместо отбрасывания предмета 3, процедура передаёт его Алисе, а Джорджу для компенсации передаётся предмет 4. Конечное распределение: Алиса $\leftarrow \{1,3\},$ Джордж $\leftarrow \{2,4\}.$ Распределение является ОБЗ-распределением и эффективно по Парето.

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

AL-процедура с неотличимостью предметов

Оригинальная AL-процедура принципиально опирается на предположение, что упорядочение предметов строгое (нет неразличимых). Азиз^[5] обобщил эту процедуру до упорядочений общего вида с возможностью иметь неразличимые предметы.

Примечания

↑ Brams, Kilgour, Klamler, 2014, с. 130.
↑ Aziz, 2015, с. 307–324.
↑ Здесь строгое означает, что для участника не может быть двух предметов, которые он не различает по значимости.
↑ Brandt, Conitzer и др., 2016, с. 303.
↑ Aziz, 2015, с. 307-324.

Литература

Steven J. Brams, D. Marc Kilgour, Christian Klamler. Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm // Notices of the American Mathematical Society. — 2014. — Февраль (т. 61, вып. 2). — doi:10.1090/noti1075.
Haris Aziz. A generalization of the AL method for fair allocation of indivisible objects // Economic Theory Bulletin. — 2015. — Т. 4, вып. 2. — doi:10.1007/s40505-015-0089-1. — arXiv:1409.6765.
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Handbook of Computational Social Choice. — Cambridge University Press, 2016. — ISBN 9781107060432. (online версия)

[_7c67265e39803f62-1] Brams, Kilgour, Klamler, 2014, с. 130.

[_0079adb234ba06a9-2] Aziz, 2015, с. 307–324.

[3] Здесь строгое означает, что для участника не может быть двух предметов, которые он не различает по значимости.

[_0b20e2215e57f57a-4] Brandt, Conitzer и др., 2016, с. 303.

[_a1699e784872bf15-5] Aziz, 2015, с. 307-324.

[1]

[2]

[3]

[4]

[5]