В экономике и теории общественного выбора , зависть свободного соответствия (EFM) является соответствие между людьми с «вещами», который является зависть свободной в том смысле , что ни один человек не хотел бы, чтобы переключить его «вещь» с другого лица. Этот термин использовался в нескольких разных контекстах.
На рынках с деньгами
Рассмотрим рынок, на котором есть несколько покупателей и несколько товаров, и каждый товар может иметь цену. Учитывая вектор цен, у каждого покупателя есть набор спроса - набор пакетов, которые максимизируют полезность покупателя по всем пакетам (этот набор может включать пустой пакет, если покупатель считает все пакеты слишком дорогими).
Зависть свободного соответствия (учитывая цену вектор) паросочетание , в котором каждый агент получает пакет от его спроса-набора. Это означает, что ни один агент не хотел бы получать пакет другого агента с такими же ценами. [1] Примером этой настройки является проблема согласования аренды - сопоставление арендаторов (агентов) комнатам (предметам) при установке цены для каждой комнаты.
Зависть свободной цены является цена-вектор , для которого зависть свободного соответствия существует. Это ослабление вальрасовского равновесия : вальрасовское равновесие состоит из EF-цены и EF-согласования, и, кроме того, каждый товар должен быть согласован или иметь нулевую цену. Известно, что в вальрасовском равновесии согласование максимизирует сумму значений, т. Е. Согласование максимального веса . Однако доход продавца может быть низким. Это мотивирует ослабление ценообразования EF, при котором продавец может использовать резервные цены для увеличения дохода.
В двудольных графах
В невзвешенном двудольном графе G = ( X + Y , E ), зависть свободного соответствие является соответствием , в которой нет равных вершин в X не находится рядом с согласованной вершиной в Y . [2] Предположим, что вершины X представляют людей, вершины Y представляют дома, а ребро между человеком x и домом y представляет тот факт, что x желает жить в y . Тогда EFM - это частичное распределение домов между людьми, так что каждый бездомный не завидует никому, у кого есть дом, поскольку ему в любом случае не нравится какой-либо выделенный дом.
Каждое совпадение, насыщающее X, не вызывает зависти, и каждое пустое совпадение не вызывает зависти.
Более того, если | N G ( X ) | ≥ | X | ≥ 1 (где N G ( X ) - множество соседей X в Y ), то G допускает непустую EFM.
Это ослабление брачного состояния Холла , в котором говорится, что если | N G ( X ') | ≥ | X '| для каждого подмножества X 'из X существует X- насыщающее соответствие.
В нарезке торта
Термин сопоставление без зависти также использовался в другом контексте: алгоритм для повышения эффективности резки торта без зависти . [3]
На рынках без денег
Термин сопоставление без зависти часто используется для обозначения более слабого условия - сопоставления без оправдания зависти .
Смотрите также
Рекомендации
- ^ Alaei Саид; Джайн, Камаль; Малекян, Азарахш (24 июня 2010 г.). «Конкурентное равновесие на двусторонних согласованных рынках с непередаваемыми коммунальными услугами». arXiv : 1006.4696 [ cs.GT ].
- ^ Сегал-Халеви, Эрель; Айгнер-Хорев, Элад (28 января 2019 г.). «Соответствия без зависти в двудольных графах и их приложения к справедливому делению». arXiv : 1901.09527 [ cs.DS ].
- ^ Сен, Сандип; Нучия, Стивен В. (1 августа 2001 г.). Повышение оптимальности n агентских подразделений без зависти . Интеллектуальные агенты VIII . Конспект лекций по информатике. 2333 . Шпрингер, Берлин, Гейдельберг. С. 277–289 . DOI : 10.1007 / 3-540-45448-9_20 . ISBN 978-3-540-43858-8.