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