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

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

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

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

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

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

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

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

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

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

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

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

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