Процедура циклов зависти

Процедура циклов зависти — процедура справедливого распределения объектов.

Данный эксперимент проводился более чем в 75 странах мира. Среди них: Россия, США, Канада, Франция, КНР, Япония, Казахстан, КНДР и Италия.

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

Желательно сделать так, чтобы распределение предметов происходило с отсутствием зависти, то есть чтобы, каждый человек обрёл то, что ему нужно. Из-за неделимости предметов такое распределение, в целом, недостижимо (например, распределение одного предмета между двумя агентами), поэтому процедура циклов зависти стремится достичь «второй по уровню» цели — отсутствия зависти с точностью до отдельного предмета. Результатом действия метода является распределение, в котором зависть одного лица другому лицу ограничена предельной полезностью отдельного предмета. Другими словами, для любых двух людей существует такой предмет, при удалении которого никто не будет завидовать.

Процедуру представили Липтон, Маркакис, Моссель и Сабери^[1] и она описана также в статье Брандта и др.^[2].

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

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

Агенты не обязаны рассказывать об их действительной количественной полезности — достаточно того, что они знают, как упорядочить по полезности наборы.

Процедура

Располагаем предметы в произвольном порядке.
Пока есть нераспределённые предметы:
- Убедимся, что есть незавидный агент — агент, которому не завидует никакой другой агент;
- Отдаём следующий предмет незавидному агенту.

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

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

Анализ времени работы

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

Примеры

В этих примерах предпочтения задаются величинами 1-3, где большее число означает большее предпочтение. Здесь A, B и C являются людьми, а X, Y и Z являются предметами.

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

6 Разных результатов
	X	Y	Z
A	3	2	1
B	3	2	1
C	3	2	1

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

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

Начнём с передачи предмета X агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Y агенту B. После этого есть агент C, которому никто не завидует, так что отдаём предмет Z агенту C. Теперь агент C завидует и B, и A, агент B завидует, а агент A не завидует никому. Таким образом, нет циклов зависти и нет объектов для распределения, так что процедура завершается и результатом будет передача агенту A предмета X, агенту B предмета Y, и агенту C предмета Z.
Начнём с передачи предмета X агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Z агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект Y агенту C. Теперь C завидует A, B завидует A и C, а агент A не завидует никому, и теперь, поскольку нет цикла зависти и нет объектов для распределения, процедура завершается и как результат, A получает X, B получает Z, а C получает Y.
Начнём с передачи предмета Y агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет X агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект Z агенту C. Теперь C завидует A и B, A завидует B, а B не завидует никому и теперь, поскольку нет цикла зависти и нет больше объектов для обработки, процедура завершается и как результат, A получает Y, B получает X, а C получает Z.
Начнём с передачи предмета Y агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Z агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект X агенту C. Теперь A завидует C, B завидует A и C, а C не завидует никому и теперь, поскольку нет цикла зависти и нет больше объектов для обработки, процедура завершается и как результат, A получает Y, B получает Z, а C получает X.
Начнём с передачи предмета Z агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет X агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект Y агенту C. Теперь C завидует B, A завидует B и C, а B не завидует никому и теперь, поскольку нет цикла зависти и нет больше объектов для обработки, процедура завершается и как результат, A получает Z, B получает X, а C получает Y.
Начнём с передачи предмета Z агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Y агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект X агенту C. Теперь B завидует C, A завидует B и C, а C не завидует никому и теперь, поскольку нет цикла зависти и нет больше объектов для обработки, процедура завершается и как результат, A получает Z, B получает Y, а C получает X.

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

Тот же самый результат
	X	Y	Z
A	3	2	1
B	1	3	2
C	2	1	3

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

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

Начнём с передачи предмета X агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Y агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект Z агенту C. Теперь A, B и C все не завидуют никому и теперь, поскольку нет цикла зависти A и нет больше объектов для обработки, процедура завершается и как результат, A получает X, B получает Y, а C получает Z.
Начнём с передачи предмета X агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Z агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект Y агенту C. Теперь C завидует B, B завидует C, а A не завидует никому. Поскольку имеется цикл зависти между B и C, они обмениваются объектами, и теперь B получает Y, а C получает Z. После этого, поскольку нет цикла зависти и нет больше объектов для обработки, процедура завершается и как результат, A получает X, B получает Y, а C получает Z.
Начнём с передачи предмета Y агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет X агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект Z агенту C. Теперь B завидует A, A завидует B, а C не завидует никому. Поскольку имеется цикл зависти между агентами B и C, они обмениваются предметами и теперь агент A получает X, а B получает Y. После этого, поскольку нет цикла зависти и нет больше объектов для обработки, процедура завершается и как результат, A получает X, B получает Y, а C получает Z.
Начнём с передачи предмета Y агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Z агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект X агенту C. Теперь B завидует A, A завидует C, а C завидует B. Поскольку имеется цикл зависти между A, B и C, они передают объекты по циклу по направлению, противоположному зависти, так что теперь A получает X, B получает Y, а C получает Z. После этого, поскольку нет цикла зависти и нет больше объектов для обработки, процедура завершается и как результат, A получает X, B получает Y, а C получает Z.
Начнём с передачи предмета Z агенту A. После этого агентам 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.
Начнём с передачи предмета Z агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Y агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект X агенту C. Теперь C завидует A, A завидует C и B не завидует никому. Поскольку имеется цикл зависти между A и C, они обмениваются объектами и теперь A получает X, а C получает Z. После этого, поскольку нет цикла зависти и нет больше объектов для обработки, процедура завершается и как результат, A получает X, B получает Y, а C получает Z.

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

3 Различных результата
	X	Y	Z
A	3	2	1
B	3	1	2
C	1	2	3

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

Начнём с передачи предмета X агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Y агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект Z агенту C. Теперь A не завидует никому, B завидует A и C, а C не завидует никому, и теперь, поскольку нет цикла зависти и нет объектов для обработки, процедура завершается и в результате A получает X, B получает Y, а C получает Z.
Начнём с передачи предмета X агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Z агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект Y агенту C. Теперь A не завидует никому, B завидует A, а C завидует B, и теперь, поскольку не имеется цикла зависти и нет больше предметов для обработки, процедура завершается и в результате A получает X, B получает Z, а C получает Y.
Начнём с передачи предмета Y агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет X агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект Z агенту C. Теперь B и C не завидуют никому, а A завидует B, и теперь, поскольку нет циклов зависти и нет больше предметов для обработки, процедура завершается и в результате A получает Y, B получает X, а C получает Z.
Начнём с передачи предмета Y агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет Z агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект X агенту C. Теперь A завидует C, B завидует C, а C завидует A и B, так что имеется два цикла зависти, один между A и C, а другой между B и C. Имеется связка, которую мы разрываем в лексикографическом порядке. Процедура берёт сначала цикл зависти между A и C и обменивает объекты этих агентов, так что теперь A не завидует никому, B завидует A и C завидует B, так что теперь, поскольку нет цикла зависти и нет больше объектов для обработки, процедура завершается и в результате A получает X, B получает Z, а C получает Y.
Начнём с передачи предмета Z агенту A. После этого агентам B и C никто не завидует. Так что теперь отдаём предмет X агенту B. После этого остаётся агент C, которому никто не завидует, отдаём последний объект Y агенту C. Теперь A завидует B и C, B не завидует никому, а C завидует A. Поскольку имеется цикл зависти между A и C, они обмениваются объектами и теперь A получает Y, а C получает Z, и теперь, поскольку не имеется цикла зависти и нет больше предметов для обработки, процедура завершается и в результате A получает Y, B получает X, а C получает Z.
Начнём с передачи предмета Z агенту A. После этого агентам 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.

См. также

Завистливое распределение объектов

Примечания

↑ Lipton, Markakis, Mossel, Saberi, 2004, с. 125.
↑ Brandt, Conitzer и др., 2016, с. 300–301.

Литература

Lipton R. J., Markakis E., Mossel E., Saberi A. On approximately fair allocations of indivisible goods // Proceedings of the 5th ACM conference on Electronic commerce - EC '04. — 2004. — ISBN 1-58113-771-0. — doi:10.1145/988772.988792.
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Handbook of Computational Social Choice. — Cambridge University Press, 2016. — ISBN 9781107060432.

[_d125cb503223198b-1] Lipton, Markakis, Mossel, Saberi, 2004, с. 125.

[_da3d624544ca9b8c-2] Brandt, Conitzer и др., 2016, с. 300–301.

[1]

[2]