Паросочетание без зависти

Паросочетание без зависти (англ. envy-free matching, EFM) — это паросочетание между людьми и «объектами», в котором нет зависти в том смысле, что никто из людей не имеет желания переключиться на «объект», который принадлежит другому лицу. Этот термин используется в нескольких различных контекстах. Ниже сокращение ОЗ означает Отсутствие Зависти, а ПбЗ означает Паросочетание без зависти.

На рынке с деньгами

Рассмотрим рынок, в котором имеется несколько покупателей и несколько объектов и каждый объект может иметь цену. Если дан вектор цен, каждый покупатель имеет набор запросов — множество наборов, которые максимизируют полезность покупателя над остальными наборами (это множество может включать пустой набор, если покупатель считает, что все наборы слишком дорогие).

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

Цены без зависти — это вектор цен, для которых паросочетание без зависти существует. Это ослабление равновесия Вальрасиана — равновесие Вальрасиана состоит из ОЗ цены и ОЗ паросочетания, и, кроме того, каждый объект должен либо входить в паросочетание, либо иметь нулевую цену. Известно, что в равновесии Вальрасиана паросочетание максимизирует сумму значений, то есть это паросочетание максимального веса. Однако доход продавца может быть низким. Это побуждает ослабление на ОЗ цены, в котором продавец может использовать минимально приемлемые цены для увеличения дохода.

На рынке без денег

Рассмотрим задачу сочетания докторов для работы в клиниках. Каждый доктор имеет предпочтения на клиники (у него есть сравнительное мнение о клиниках от плохого до хорошего), а каждая клиника имеет предпочтения на докторов (упорядочивая докторов от лучших до худших). Каждый доктор должен работать не более чем в одной клинике, а каждая клиника может нанять фиксированное число докторов (называемое ёмкостью клиники). Нам нужно расставить докторов по клиникам. Денежные обмены не позволяются. Имеется два случая, в которых такая расстановка может оказаться «плохой»:

1. Паросочетание имеет обоснованную зависть, если есть доктор d и клиника h, такие, что d предпочитает h текущему месту работы, а клиника h предпочитает доктора d вместо одного из текущих работников.
2. Паросочетание имеет пустоту, если есть доктор d и клиника h, такие, что d предпочитает клинику h текущему месту работы, а клиника h имеет некоторые вакантные позиции и h предпочитает нанять d, чем оставлять место пустым.

Паросочетание без зависти — это паросочетание без обоснованной зависти. Такое паросочетание является ослаблением условия стабильности паросочетания — стабильное паросочетание одновременно и свободно от зависти, и не имеет пустот.

Решёточная структура

В задаче нахождения сочетания много-к-одному, стабильные паросочетания существуют и могут быть найдены при помощи алгоритма Гейла-Шепли. Поэтому ОЗ тоже существует. В общем случае может иметься много различных ОЗ паросочетаний. Множество всех ОЗ паросочетаний является решёткой. Множество стабильных паросочетаний (которое является подмножеством ОЗ паросочетаний) является неподвижной точкой оператора Тарского на этой решётке.

Верхние и нижние квоты

Часто клиники имеют не только верхние квоты (ёмкости), но и нижние квоты – каждая клиника должна нанять какое-то минимальное число докторов. В таких задачах стабильные паросочетания могут не существовать (хотя легко проверить, существует ли стабильное паросочетание по теореме о сельских клиниках, по которой во всех стабильных паросочетаниях число докторов, назначенных каждой клинике, одинаково). В таких условиях естественно проверить, существует ли ОЗ паросочетание. Необходимым условием является то, что сумма всех нижних квот не должна быть больше числа докторов (в противном случае никакого допустимого решения не существует вообще). В этом случае, если все пары доктор-клиника приемлемы (каждый доктор предпочитает где-то работать и не быть безработным, а каждая клиника предпочитает нанять какого-либо доктора, чтобы не было недостатка в кадрах), то ОЗ паросочетание существует всегда.

Если не все пары приемлемы, то ОЗ паросочетание может и не существовать. Можно узнать о существовании ПбЗ следующим образом. Создадим новую задачу, в которой верхние квоты равны нижним квотам исходной задачи, а нижние квоты равны 0. В этой новой задаче стабильное паросочетание всегда существует и может быть найдено эффективно. Исходная задача имеет ОЗ паросочетание тогда и только тогда, когда в новой задаче любая клиника заполнена.

Алгоритм может быть улучшен для поиска максимального ОЗ паросочетания.

Минимизация зависти

Как было определено выше, паросочетание без зависти исключает только обоснованную зависть, когда доктор d завидует другому доктору, который был назначен в клинику h, которую предпочитает d. Однако даже в ПбЗ может иметься доктор d и клиника h, такие, что d предпочитает h, хотя ей назначен другой доктор, но h не видит доктора d как замену какого-то своего имеющегося сотрудника. Это может быть названо «необоснованной завистью». Паросочетание без зависти вообще существует лишь в редких случаях, когда каждый доктор может быть назначен на место, которое он предпочитает больше всего. Когда такое «паросочетание полностью без зависти» не существует, целесообразно найти паросочетания, которые минимизируют «величину зависти». Имеется несколько способов измерения величины зависти, например, как сумму завистей всех докторов или максимальную зависть.

В двудольных графах

В невзвешенном двудольном графе $G=(X+Y,E)$ паросочетанием без зависти является паросочетание, в котором никакая из не входящих в паросочетание вершина из X не смежна входящей в паросочетание вершине из Y. Представим, что вершины X представляют людей, а вершины Y представляют дома, а ребро между персоной x и домом y представляет факт, что x хотел бы жить в y. Тогда ПбЗ является частичным распределением домов для людей, таким, что каждое бездомное лицо не завидует лицу с домом, поскольку не хочет жить ни в одном предложенном доме.

Любое паросочетание, которое насыщает X, не имеет зависти и любое пустое паросочетание зависти не имеет.

Более того, если $|N_{G}(X)|\geqslant |X|\geqslant 1$ (где $N_{G}(X)$ является множеством соседей X в Y), то G допускает непустое ПбЗ.

Это является ослаблением условия Холла, которое гласит, что если $|N_{G}(X')|\geqslant |X'|$ для любого подмножества X' множества X, то существует полное разбиение X на пары.

В разрезании торта

Термин паросочетание без зависти использовалось также в другом контексте — в алгоритме для улучшения эффективности завистливого разрезания торта.

См. также

• Отсутствие зависти (справедливый делёж)
• Завистливое разрезание торта
• Завистливое распределение предметов