Процедура зависти-графа - Envy-graph procedure

В процедура envy-graph (также называемый процедура цикла зависти) - процедура для справедливое распределение предметов. Его могут использовать несколько человек, которые хотят разделить между собой несколько отдельных предметов, таких как реликвии, сладости или места в классе.

В идеале мы бы хотели, чтобы распределение было без зависти (EF). то есть дать каждому агенту набор, который он / она предпочитает связкам всех других агентов. Однако элементы являются дискретными и не могут быть разрезаны, поэтому задание без зависти может оказаться невозможным (например, рассмотрим один элемент и двух агентов). Процедура envy-graph направлена ​​на достижение «следующего лучшего» варианта - свобода от зависти до одного хорошего (EF1): он находит распределение, в котором зависть каждого человека к каждому другому ограничена максимальной предельной полезностью, которую он извлекает из отдельного элемента. Другими словами, на каждых двух человек я и j, существует такой элемент, что, если этот элемент удален, я не завидует j.

Процедуру представили Липтон и Маркакис, а также Моссель и Сабери.^[1] и это также описано в.^{[2]:300–301}

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

Процедура зависти-графа предполагает, что у каждого человека есть кардинальная полезность функция на связках предметов. Эта функция полезности должна быть монотонный (полезность набора не меньше полезности его подмножеств). Однако это так нет должны быть аддитивными. То есть предметы нет предполагается, что это независимые товары.

Агентам не обязательно сообщать о своей кардинальной полезности: достаточно, чтобы они знали, как ранжировать пакеты.

Процедура

1. Заказывайте товары произвольно.
2. Пока есть неназначенные предметы:
   • Убедитесь, что есть незавидный агент - агент, которому не позавидует ни один другой агент.
   • Отдайте следующий предмет незавидному агенту.

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

Результирующее распределение не обязательно является EF, но оно не вызывает зависти, за исключением одного элемента. Это верно не только для окончательного распределения, но также и для каждого промежуточного распределения: поскольку элемент всегда передается незавидному агенту, зависть всех остальных агентов после этого распределения составляет не более одного элемента.

Анализ во время выполнения

Предположим, есть м Предметы. Каждое распределение элемента добавляет к зависти-графу не более п-1 ребро. Следовательно, не более ${\displaystyle (n-1)m}$ края добавляются в целом. Каждый цикл удаления удаляет как минимум две кромки. Следовательно, нам нужно выполнить этап удаления цикла не более ${\displaystyle (n-1)m/2}$ раз. Найти цикл можно вовремя ${\displaystyle O(n^{2})}$ используя, например, поиск в глубину. В общем, время выполнения ${\displaystyle O(n^{3}m)}$.

Примеры

В этих примерах предпочтения идут от 1 до 3, где чем выше число, тем выше предпочтение. Также a, b и c - это люди, а X, Y и Z - объекты.

1) С 3 людьми и 3 объектами все возможные распределения будут разными результатами. Этот случай случается, когда у всех троих одинаковые предпочтения. Есть шесть различных способов размещения объектов:

6 различных результатов

	Икс	Y	Z
а	3	2	1
б	3	2	1
c	3	2	1

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

1. Начнем с передачи объекта X в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Y объекту b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Z в c. Теперь c завидует b и a, b завидует a, а a не завидует никому, и теперь, поскольку нет цикла зависти и больше нет предметов для раздачи, процедура заканчивается, и конечный результат a получает X, b получает Y, а c получает Z.
2. Начнем с передачи объекта X в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Z в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Y в c. Теперь c завидует a, b завидует a и c, а a не завидует никому, и теперь, поскольку нет цикла зависти и больше нет предметов для раздачи, процедура заканчивается, и конечный результат a получает X, b получает Z, а c получает Y.
3. Начнем с передачи объекта Y объекту. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект X в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Z в c. Теперь c завидует a и b, a завидует b, а b не завидует никому, и теперь, поскольку нет цикла зависти и больше нет предметов для раздачи, процедура заканчивается, и конечный результат a получает Y, b получает X, а c получает Z.
4. Начнем с передачи объекта Y объекту. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Z в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект X в c. Теперь a завидует c, b завидует a, а c и c не завидует никому, и теперь, поскольку нет цикла зависти и больше нет предметов для раздачи, процедура завершается, и конечный результат a получает Y, b получает Z, а c получает X.
5. Начнем с передачи объекта Z в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект X в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Y в c. Теперь c завидует b, a завидует b, а c и b никому не завидует, и теперь, поскольку нет цикла зависти и больше нет предметов для раздачи, процедура завершается, и конечный результат a получает Z, b получает X, а c получает Y.
6. Начнем с передачи объекта Z в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Y объекту b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект X в c. Теперь b завидует c, a завидует b и c, а c не завидует никому, и теперь, поскольку нет цикла зависти и больше нет предметов для раздачи, процедура завершается, и конечный результат a получает Z, b получает Y, а c получает X.

2) С 3 людьми и 3 объектами все возможные распределения будут одинаковыми. Этот случай случается, когда у каждого из трех людей совершенно разные предпочтения, потому что у каждого человека есть что-то еще, что он предпочитает, независимо от того, что он получит то, что хочет.

Тот же результат

	Икс	Y	Z
а	3	2	1
б	1	3	2
c	2	1	3

Есть шесть различных способов размещения объектов:

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

1. Начнем с передачи объекта X в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Y объекту b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Z в c. Теперь a, b и c никому не завидуют, и теперь, поскольку нет цикла зависти и больше нет предметов для раздачи, процедура завершается, и конечный результат - a получает X, b получает Y, а c получает Z.
2. Начнем с передачи объекта X в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Z в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Y в c. Теперь c завидует b, b завидует c, а a никому не завидует. Поскольку существует цикл зависти между b и c, они будут переключать объекты, и теперь b получает Y, а c получает Z. И теперь, поскольку нет цикла зависти и больше нет объектов для раздачи, процедура завершается, и конечный результат получает X, b получает Y, а c получает Z.
3. Начнем с передачи объекта Y объекту. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект X в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Z в c. Теперь b завидует a, a завидует b, а c никому не завидует. Поскольку существует цикл зависти между b и c, они будут переключать объекты, и теперь a получает X, а b получает Y. И теперь, поскольку нет цикла зависти и больше нет объектов для раздачи, процедура завершается, и конечным результатом является получает X, b получает Y, а c получает Z.
4. Начнем с передачи объекта Y объекту. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Z в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект X в c. Теперь b завидует a, a завидует c, а c завидует b. Поскольку между a, b и c существует цикл зависти, они будут вращать объекты против направления ревности, и теперь a получает X, b получает Y, а c получает Z. А теперь, поскольку цикла зависти нет и больше нет предметов в руке out, тогда процедура заканчивается, и конечный результат: a получает X, b получает Y, а c получает Z.
5. Начнем с передачи объекта Z в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект X в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Y в c. Теперь b завидует a и c, a завидует b и c, а c завидует b и a. Поскольку между a, b и c существует цикл зависти, они будут вращать объекты против направления ревности, и теперь a получает X, а b получает Y, а c получает Z. А теперь, поскольку цикла зависти нет и больше нет предметов для раздачи затем процедура завершается, и конечный результат: a получает X, b получает Y и c получает Z.
6. Начнем с передачи объекта Z в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Y объекту b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект X в c. Теперь c завидует a, a завидует c, а b никому не завидует. Поскольку существует цикл зависти между a и c, они будут переключать объекты, и теперь a получает X, а c получает Z. И теперь, поскольку нет цикла зависти и больше нет объектов для раздачи, процедура завершается, и конечный результат получает X, b получает Y, а c получает Z.

3) С 3 людьми и 3 объектами любая другая ситуация, кроме первого и второго примеров, даст от 1 до 6 результатов. Поэтому для этого вам просто нужно, чтобы как минимум два человека имели одинаковые предпочтения в отношении одного объекта или максимум два человека имели разные предпочтения в отношении одного и того же объекта.

3 разных результата

	Икс	Y	Z
а	3	2	1
б	3	1	2
c	1	2	3

Есть шесть различных способов размещения объектов:

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

1. Начнем с передачи объекта X в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Y объекту b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Z в c. Теперь a не завидует никому, b завидует a, а c и c не завидует никому, теперь, поскольку нет цикла зависти и больше нет предметов для раздачи, процедура завершается, и конечный результат - a получает X, b получает Y, а c получает Z.
2. Начнем с передачи объекта X в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Z в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Y в c. Теперь a не завидует никому, b завидует a, а c завидует b, теперь, поскольку нет цикла зависти и больше нет предметов для раздачи, процедура завершается, и конечный результат - a получает X, b получает Z и c получает Y.
3. Начнем с передачи объекта Y объекту. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект X в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Z в c. Теперь b и c никому не завидуют, а a завидует b, теперь, поскольку нет цикла зависти и больше нет предметов для раздачи, процедура заканчивается, и конечный результат: a получает Y, b получает X и c получает Z .
4. Начнем с передачи объекта Y объекту. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Z в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект X в c. Теперь a завидует c, b завидует c, а c завидует a и b, поэтому существует два цикла зависти: один между a и c, а другой между b и c. Поскольку разделитель разрешен в лексикографическом порядке, процедура сначала выполняет цикл зависти a и c, затем a и c будут переключаться, затем a никому не завидует, b завидует a, а c завидует b, и теперь, поскольку нет цикл зависти и больше не нужно раздавать предметы, тогда процедура заканчивается, и конечный результат: a получает X, b получает Z и c получает Y.
5. Начнем с передачи объекта Z в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект X в b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект Y в c. Теперь a завидует b и c, b никому не завидует, а c завидует a. Поскольку существует цикл зависти между a и c, они будут переключать объекты, и теперь a получает Y, а c получает Z, теперь, поскольку нет цикла зависти и больше нет объектов для раздачи, процедура завершается, и конечный результат - получает Y , b получает X, а c получает Z.
6. Начнем с передачи объекта Z в. После этого и b, и c, и незавидные агенты. Итак, теперь давайте передадим объект Y объекту b. После этого c - незавидный агент. Итак, теперь давайте передадим последний объект X в c. Теперь b завидует a и c, a завидует b и c, а c завидует b и a. Поскольку существует цикл зависти между a, b и c, они будут вращать объекты против направления ревности. Однако, поскольку существует 2 цикла зависти между a, b и c, может быть два варианта. Поскольку разделитель разрешается в лексикографическом порядке, a получает X от c, b получает Z от a, а c получает Y от b, поэтому результатом будет a, получив X, b получит Z, а c получит Y. И теперь, поскольку нет никакой зависти цикл и больше не нужно раздавать предметы, тогда процедура завершается, и конечный результат: a получает X, b получает Z и c получает Y.

Расширения

Алгоритм envy-graph гарантирует EF1, когда элементы товары (- предельная стоимость каждой позиции положительна для всех агентов). Однако, когда есть и товары, и работа по дому, это не гарантирует EF1. Адаптация под названием обобщенный зависть-граф гарантирует EF1 даже при смешивании товаров и работы по дому. Он работает, когда оценки дважды монотонный, то есть: каждый агент может разделить предметы на два подмножества: одно подмножество содержит товары (- предметы, предельная полезность которых всегда положительна), а другое - домашние дела (- предметы, предельная полезность которых всегда отрицательна).^[3]

Когда агенты имеют ограничения количества элементов (т. Е. Для каждой категории элементов существует верхняя граница количества элементов, которые каждый агент получает из этой категории), алгоритм графа зависти может дать сбой. Однако в сочетании с круговой протокол дает алгоритм, который находит распределения, которые одновременно являются EF1 и удовлетворяют ограничениям мощности.^[4]

Смотрите также

• Распределение предметов без зависти
• Жадное разбиение чисел - можно рассматривать как частный случай алгоритма envy-graph для случая, когда все агенты имеют одинаковые оценки.

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

1. Lipton, R.J .; Markakis, E .; Mossel, E .; Сабери, А. (2004). «О примерно справедливых размещениях неделимых товаров». Материалы 5-й конференции ACM по электронной коммерции - EC '04. п. 125. CiteSeerX  10.1.1.400.1762. Дои:10.1145/988772.988792. ISBN  1-58113-771-0.
2. Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (2016). Справочник по вычислительному социальному выбору. Издательство Кембриджского университета. ISBN  9781107060432. (бесплатная онлайн-версия )
3. Харис Азиз, Иоаннис Карагианнис, Аюми Игараши, Тоби Уолш (2019). «Справедливое распределение неделимых товаров и дел» (PDF). Конференция IJCAI 2019.
4. Бисвас, Арпита; Бармен, Сиддхарт (13.07.2018). «Справедливое деление при ограничениях мощности». Материалы 27-й Международной совместной конференции по искусственному интеллекту. IJCAI'18. Стокгольм, Швеция: AAAI Press: 91–97. arXiv:1804.09521. ISBN  978-0-9992411-2-7.