Сопоставление без оправданной зависти
В экономике и теории социального выбора сопоставление без оправданной зависти — это сопоставление на двустороннем рынке , на котором ни один агент не предпочитает назначение другого агента и одновременно получает предпочтение от этого назначения.
Рассмотрим, например, задачу подбора врачей для ординатуры в больницах. Каждый врач имеет свои предпочтения в отношении больниц, ранжируя больницы от лучших к худшим. Каждая больница имеет отношение к врачам, ранжируя их от лучших к худшим. Каждый врач может работать не более чем в одной больнице, и в каждой больнице может работать не более фиксированного количества врачей (называемого пропускной способностью больницы). Цель состоит в том, чтобы подобрать врачей в больницы без денежных переводов.
Завистью называется ситуация, когда некий врач работающий , в какой-то больнице , h1 предпочитает какую-то другую больницу , h2 в которой работает какой-то другой врач d2 d1 (мы говорим, что завидует d1 d2 ) . Зависть оправдана при h2 d1 предпочитает этом если перед d2 . , , что если d1 к оправдал зависть , h2 то оправдал Заметим зависть ( d1 h2 завидует h1 ) к h2 . В этом случае мы также говорим, что d 1 и h 2 являются блокирующей парой . Сопоставление без блокирующих пар называется сопоставлением без оправданной зависти (NJE) или сопоставлением, исключающим обоснованную зависть . [ 1 ] [ 2 ]
Связанные термины
[ редактировать ]Соответствие без оправданной зависти — это смягчение двух разных условий:
- Партия без зависти — это парочка, в которой вообще нет зависти, оправданной или нет.
- Стабильный матчинг – это матчинг, при котором нет оправданной зависти, а кроме того, нет растрат . Сопоставление имеет потери, если есть врач d и больница h , так что d предпочитает h своему нынешнему работодателю, h имеет несколько вакантных должностей и h предпочитает d вакантной должности.
Решетчатая структура
[ редактировать ]В задаче сопоставления «многие к одному» существуют устойчивые сопоставления, которые можно найти с помощью алгоритма Гейла – Шепли . Следовательно, соответствия NJE тоже существуют. В общем, может быть много разных совпадений NJE. Множество всех NJE-паросочетаний представляет собой решетку . Множество устойчивых паросочетаний (которые являются подмножеством паросочетаний NJE) является неподвижной точкой оператора Тарского на этой решетке. [ 3 ]
Как верхняя, так и нижняя квоты
[ редактировать ]Часто в больницах существуют не только верхние квоты (мощности), но и нижние – в каждой больнице должно быть закреплено хотя бы какое-то минимальное количество врачей. [ 4 ] В таких задачах устойчивых паросочетаний может не быть (хотя легко проверить, существует ли устойчивое паросочетание, поскольку по теореме о сельских больницах во всех устойчивых паросочетаниях количество врачей, приписанных к каждой больнице, одинаково). В таких случаях естественно проверить, существует ли соответствие NJE. Необходимым условием является то, чтобы сумма всех нижних квот не превышала числа врачей (в противном случае никакого возможного сопоставления вообще не существует). В этом случае, если все пары врач-больница приемлемы (каждый врач предпочитает любую больницу безработице, а любая больница предпочитает любого врача вакантной должности), то соответствие NJE всегда существует. [ 4 ]
Если не все пары приемлемы, совпадение NJE может не существовать. О существовании ЭФМ можно судить следующим образом. Создайте новый экземпляр задачи, в котором верхние квоты являются нижними квотами исходной задачи, а нижние квоты равны 0. В новой задаче всегда существует устойчивое сопоставление, и его можно эффективно найти. Исходная задача имеет соответствие NJE тогда и только тогда, когда при устойчивом сопоставлении новой задачи каждая больница заполнена. [ 5 ]
Алгоритм можно улучшить, чтобы найти максимальное соответствие NJE. [ 6 ]
Минимизация неоправданной зависти
[ редактировать ]По определению, при сопоставлении NJE могут существовать врач d и больница h, так что d предпочитает h своему нынешнему работодателю, но h не предпочитает d ни одному из своих нынешних сотрудников. Это можно назвать «неоправданной завистью». Сопоставление без зависти существует только в том редком случае, когда каждый врач может быть сопоставлен с первым выбором. Когда такого «совпадения, полностью исключающего зависть», не существует, все же разумно найти совпадения, которые минимизируют «сумму зависти». Существует несколько способов измерения количества зависти, например: общее количество случаев зависти ко всем врачам или максимальное количество случаев зависти на одного врача. [ 7 ]
См. также
[ редактировать ]- Свобода от зависти
- Ценообразование без зависти — другая концепция, связанная с отсутствием зависти и соответствием.
Ссылки
[ редактировать ]- ^ Абдулкадироглу, Атила; Сёнмез, Тайфун (1 июня 2003 г.). «Выбор школы: подход к разработке механизма» . Американский экономический обзор . 93 (3): 729–747. дои : 10.1257/000282803322157061 . HDL : 10161/2090 . ISSN 0002-8282 .
- ^ Абдулкадироглу, Атила; Че, Ён Ку; Патхак, Параг А.; Рот, Элвин Э.; Терсье, Оливье (27 марта 2017 г.). «Минимизация оправданной зависти при выборе школы: дизайн OneApp в Новом Орлеане» . Серия рабочих документов. дои : 10.3386/w23265 . S2CID 9497845 .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ У, Цинъюнь; Рот, Элвин Э. (1 мая 2018 г.). «Решетка совпадений без зависти» . Игры и экономическое поведение . 109 : 201–211. дои : 10.1016/j.geb.2017.12.016 . ISSN 0899-8256 .
- ^ Перейти обратно: а б Фрагиадакис, Дэниел; Ивасаки, Ацуши; Троян, Питер; Уэда, Сугуру; Ёко, Макото (1 января 2016 г.). «Стратегическое сопоставление с минимальными квотами». Транзакции ACM по экономике и вычислениям . 4 (1): 6:1–6:40. дои : 10.1145/2841226 . ISSN 2167-8375 . S2CID 1287011 .
- ^ Ёкои, Ю (17 апреля 2017 г.). «Соответствие без зависти с более низкими квотами». arXiv : 1704.04888 [ cs.GT ].
- ^ «Насколько хороши популярные совпадения?» (PDF) . www.cse.iitm.ac.in. Архивировано из оригинала (PDF) 17 января 2019 года . Проверено 16 января 2019 г.
- ^ Таденума, Коичи (2011), «Партнерство, солидарность и минимальная зависть в задачах сопоставления», в Флербе, Марке; Саллес, Морис; Веймарк, Джон А. (ред.), Социальная этика и нормативная экономика , Исследования выбора и благосостояния, Springer Berlin Heidelberg, стр. 155–167, doi : 10.1007/978-3-642-17807-8_6 , ISBN 9783642178078