Jump to content

Сопоставление без зависти

В теории экономики и социального выбора соответствие без зависти (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 ]

См. также

[ редактировать ]
  1. ^ Jump up to: а б Сегал-Халеви, Эрель; Айгнер-Хорев, Элад (2022). «Сопоставления без зависти в двудольных графах и их приложения к справедливому дележу». Информационные науки . 587 : 164–187. arXiv : 1901.09527 . дои : 10.1016/j.ins.2021.11.059 . S2CID   170079201 .
  2. ^ Алаи, Саид; Джайн, Камаль; Малекян, Азарахш (24 июня 2010 г.). «Конкурентное равновесие на двусторонних рынках с непередаваемыми полезностями». arXiv : 1006.4696 [ cs.GT ].
  3. ^ Сен, Сандип; Нучия, Стивен В. (1 августа 2001 г.). «Повышение оптимальности n агентских подразделений без зависти» . Интеллектуальные агенты VIII . Конспекты лекций по информатике. Том. 2333. Шпрингер, Берлин, Гейдельберг. стр. 277–289 . дои : 10.1007/3-540-45448-9_20 . ISBN  978-3-540-43858-8 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: c255ea6978c315fdffd56009bae9ebcf__1711013400
URL1:https://arc.ask3.ru/arc/aa/c2/cf/c255ea6978c315fdffd56009bae9ebcf.html
Заголовок, (Title) документа по адресу, URL1:
Envy-free matching - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)