Нет соответствия оправданной зависти

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

Рассмотрим, например, задачу подбора врачей для резидентуры в больницах. У каждого врача есть отношение предпочтения к больницам, ранжирующее больницы от лучших к худшим. У каждой больницы есть отношение предпочтения к врачам, ранжирующее врачей от лучших к худшим. Каждый врач может работать не более чем в одной больнице, и каждая больница может нанять не более фиксированного количества врачей (называемого вместимостью больницы ). Цель состоит в том, чтобы подобрать врачей для больниц без денежных переводов.

Зависть — это ситуация, в которой некий врач d ₁ , работающий в некоторой больнице h ₁ , предпочитает некоторую другую больницу h ₂ , в которой работает некий другой врач d ₂ (мы говорим, что d ₁ завидует d ₂ ). Зависть оправдана , если в то же время h ₂ предпочитает d _{1 ,} а не d ₂ . Обратите внимание, что если d ₁ имеет обоснованную зависть к h ₂ , то h ₂ имеет обоснованную зависть к d ₁ ( h ₂ завидует h ₁ ). В этом случае мы также говорим, что d ₁ и h ₂ являются блокирующей парой . Соответствие без блокирующих пар называется соответствием без обоснованной зависти (NJE) или соответствием, которое устраняет обоснованную зависть . ^{[1] [2]}

Соответствие без обоснованной зависти — это смягчение двух различных условий:

• Соответствие без зависти — это соответствие, в котором вообще нет зависти, независимо от того, оправдана она или нет.
• Стабильное соответствие — это соответствие, в котором нет оправданной зависти, и, кроме того, нет отходов . Соответствие имеет отходы, если есть врач d и больница h , такие, что d предпочитает h своему текущему работодателю, у h есть некоторые вакантные должности, и h предпочитает d вакантной должности.

В задаче сопоставления многих к одному существуют устойчивые сопоставления, которые можно найти с помощью алгоритма Гейла–Шепли . Следовательно, сопоставления NJE также существуют. В общем случае может быть много различных сопоставлений NJE. Множество всех сопоставлений NJE представляет собой решетку . Множество устойчивых сопоставлений (которые являются подмножеством сопоставлений NJE) представляет собой неподвижную точку оператора Тарского на этой решетке. ^[3]

Часто больницы имеют не только верхние квоты (мощности), но и нижние квоты — каждой больнице должно быть назначено по крайней мере некоторое минимальное количество врачей. ^[4] В таких задачах стабильные соответствия могут не существовать (хотя легко проверить, существует ли стабильное соответствие, поскольку по теореме о сельских больницах во всех стабильных соответствиях количество врачей, назначенных в каждую больницу, одинаково). В таких случаях естественно проверить, существует ли соответствие NJE. Необходимым условием является то, что сумма всех нижних квот не превышает количества врачей (в противном случае никакого возможного соответствия вообще не существует). В этом случае, если все пары врач-больница приемлемы (каждый врач предпочитает любую больницу безработице, а любая больница предпочитает любого врача вакантной должности), то соответствие NJE всегда существует. ^[4]

Если не все пары приемлемы, то соответствие NJE может не существовать. Можно решить о существовании EFM следующим образом. Создайте новый экземпляр задачи, в котором верхние квоты являются нижними квотами исходной задачи, а нижние квоты равны 0. В новой задаче устойчивое соответствие всегда существует и может быть эффективно найдено. Исходная задача имеет соответствие NJE тогда и только тогда, когда в устойчивом соответствии новой задачи все больницы заполнены. ^[5]

Алгоритм можно улучшить, чтобы найти максимальное соответствие NJE. ^[6]

По определению, в сопоставлении NJE может быть врач d и больница h, такие, что d предпочитает h своему текущему работодателю, но h не предпочитает d никому из своих текущих сотрудников. Это можно назвать «неоправданной завистью». Сопоставление без зависти вообще существует только в редком случае, когда каждому врачу можно сопоставить его первый выбор. Когда такого «совершенно свободного от зависти сопоставления» не существует, все равно разумно найти сопоставления, которые минимизируют «количество зависти». Существует несколько способов измерения количества зависти, например: общее количество случаев зависти по всем врачам или максимальное количество случаев зависти на одного врача. ^[7]

• Отсутствие зависти
• Ценообразование без зависти — другая концепция, связанная с отсутствием зависти и соответствием.