Соответствие без зависти - Envy-free matching

В экономика и теория социального выбора, соответствие без зависти (EFM) это соответствие между людьми и "вещами", то есть без зависти в том смысле, что ни один человек не хотел бы менять свою «вещь» на чужую. Этот термин использовался в нескольких разных контекстах.

На рынках с деньгами

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

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

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

На рынках без денег

Рассмотрим проблему подбора врачей для ординатуры в больницах. У каждого врача есть отношение предпочтений по больницам (ранжирование больниц от лучших к худшим), и каждая больница имеет отношение предпочтений к врачам (ранжирование врачей от лучших к худшим). Каждый врач может работать не более чем в одной больнице, и в каждой больнице может работать не более фиксированного числа врачей (называемых вместимость больницы). Мы хотим сопоставить врачей с больницами. Денежные переводы не допускаются. Такое соответствие может быть "плохим" двумя способами:

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

An соответствие без зависти соответствие без оправданной зависти. Это расслабление стабильное соответствие: а стабильное соответствие - это соответствие, которое не вызывает зависти и не имеет потерь.

Структура решетки

В задаче сопоставления "многие к одному" существуют устойчивые сопоставления, которые можно найти с помощью Алгоритм Гейла – Шепли. Следовательно, соответствия EF тоже существуют. В общем, может быть много разных соответствий EF. Набор всех сопоставлений EF - это решетка. Набор стабильных сопоставлений (которые являются подмножеством сопоставлений EF) - это фиксированная точка из Тарский оператор на этой решетке.[8]

И верхняя, и нижняя квоты

Часто в больницах есть не только верхние квоты (мощности), но и более низкие квоты - в каждой больнице должно быть закреплено хотя бы минимальное количество врачей.[9] В таких задачах стабильные сопоставления могут не существовать (хотя легко проверить, существует ли стабильное сопоставление, поскольку теорема о сельских больницах, во всех стабильных сопоставлениях количество врачей, закрепленных за каждой больницей, идентично). В таких случаях естественно проверить, существует ли соответствие EF. Необходимым условием является то, что сумма всех нижних квот не превышает числа врачей (в противном случае вообще не существует допустимого соответствия). В этом случае, если все пары врач-больница приемлемы (каждый врач предпочитает любую больницу безработице, а любая больница предпочитает любого врача вакантной должности), то соответствие EF всегда существует.[9]

Если не все пары приемлемы, то соответствие EF может не существовать. Решить о существовании EFM можно следующим образом. Создайте новый экземпляр проблемы, в котором верхние квоты являются нижними квотами исходной проблемы, а нижние квоты равны 0. В новой задаче всегда существует стабильное соответствие, и его можно эффективно найти. Исходная проблема имеет EF-сопоставление, если и только если при стабильном сопоставлении новой задачи каждая больница заполнена.[10]

Алгоритм можно улучшить, чтобы найти максимальное соответствие EF.[11]

Сведение к минимуму зависти

Как определено выше, сопоставление без зависти устраняет только оправданная зависть, где врач d завидует другому врачу, которого приставили в больницу час который предпочитает d. Однако даже в EFM может быть врач. d и больница час такой, что d предпочитает час над его нынешним работодателем, но час не предпочитает d над любым из его нынешних сотрудников. Это можно назвать «неоправданной завистью». Совпадение без всякой зависти существует только в редких случаях, когда каждый врач может быть сопоставлен с его первым выбором. Когда такого «сопоставления без зависти» не существует, все же разумно найти сопоставления, которые минимизируют «количество зависти». Существует несколько способов измерения количества зависти, например: общее количество экземпляров зависти по всем докторам или максимальное количество экземпляров зависти на одного врача.[12]

В двудольных графах

В невзвешенном двудольный граф G = (Икс+Y, E), соответствие без зависти это соответствие в котором нет несовпадающих вершин в Икс смежна с согласованной вершиной в Y.[13] Предположим, что вершины Икс представляют людей, вершины Y представляют собой дома, а грань между человеком Икс и дом у представляет собой тот факт, что Икс готов жить в у. Тогда EFM - это частичное распределение домов между людьми, так что каждый бездомный человек не завидует никому, у кого есть дом, поскольку ему все равно не нравится какой-либо выделенный дом.

Каждое совпадение, которое насыщает Икс не вызывает зависти, и каждое пустое совпадение не вызывает зависти.

Более того, если |Nг(Икс) | ≥ | X | ≥ 1 (где Nг(Икс) - множество соседей Икс в Y), тогда г допускает непустой EFM.

Это расслабление Состояние брака Холла, что говорит о том, что если |Nг(Икс') | ≥ | X '| для каждое подмножество X'из Икс, затем Икс-насыщающее соответствие существует.

В резке торта

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

Смотрите также

использованная литература

  1. ^ Алаеи, Саид; Джайн, Камаль; Малекян, Азарахш (24 июня 2010 г.). «Конкурентное равновесие на двусторонних согласованных рынках с непередаваемыми коммунальными услугами». arXiv:1006.4696 [cs.GT ].
  2. ^ Гурусвами, Венкатесан; Хартлайн, Джейсон Д .; Карлин, Анна Р .; Кемпе, Дэвид; Кеньон, Клэр; Макшерри, Фрэнк (2005). О ценообразовании без зависти. Материалы шестнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. SODA '05. Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики. С. 1164–1173. ISBN  9780898715859.
  3. ^ Брайст, Патрик (2008). «Единые бюджеты и проблема ценообразования без зависти». В Ачето, Лука; Дамгард, Иван; Голдберг, Лесли Энн; Halldórsson, Magnús M .; Ингольфсдоттир, Анна; Валукевич, Игорь (ред.). Автоматы, языки и программирование. Конспект лекций по информатике. 5125. Springer Berlin Heidelberg. С. 808–819. CiteSeerX  10.1.1.205.433. Дои:10.1007/978-3-540-70575-8_66. ISBN  9783540705758. Отсутствует или пусто | название = (Помогите)
  4. ^ Чен, Нин; Гош, Арпита; Васильвицкий, Сергей (2011). "SIAM (Общество промышленной и прикладной математики)". SIAM Журнал по вычислениям. 40 (3): 623–645. CiteSeerX  10.1.1.193.6235. Дои:10.1137/080740970.
  5. ^ Ван, Яцзюнь; Лу, Пиньян; Им, Сонджин (13 декабря 2010 г.). Ценообразование без зависти с общими ограничениями предложения. Интернет и сетевая экономика. Конспект лекций по информатике. 6484. Шпрингер, Берлин, Гейдельберг. стр.483–491. Дои:10.1007/978-3-642-17572-5_41. ISBN  978-3-642-17571-8.
  6. ^ Фельдман, Михал; Фиат, Амос; Леонарди, Стефано; Санковский, Петр (2012). Увеличение дохода: аукционы с несколькими объектами без зависти с бюджетом. Материалы 13-й конференции ACM по электронной коммерции. EC '12. Нью-Йорк, Нью-Йорк, США: ACM. С. 532–549. Дои:10.1145/2229012.2229052. ISBN  9781450314152. S2CID  15639601.
  7. ^ Чен, Нин; Дэн Сяотэ (1 февраля 2014 г.). «Ценообразование без зависти на многопозиционных рынках». ACM-транзакции на алгоритмах. 10 (2): 7:1–7:15. CiteSeerX  10.1.1.297.784. Дои:10.1145/2567923. ISSN  1549-6325. S2CID  15309106.
  8. ^ У, Цинъюнь; Рот, Элвин Э. (1 мая 2018 г.). «Решетка совпадений без зависти». Игры и экономическое поведение. 109: 201–211. Дои:10.1016 / j.geb.2017.12.016. ISSN  0899-8256.
  9. ^ а б Фрагиадакис, Даниэль; Ивасаки, Ацуши; Троян, Петр; Уэда, Сугуру; Йоку, Макото (1 января 2016 г.). «Стратегически устойчивое соответствие с минимальными квотами». Сделки ACM по экономике и вычислениям. 4 (1): 6:1–6:40. Дои:10.1145/2841226. ISSN  2167-8375. S2CID  1287011.
  10. ^ Ёкои, Ю (17 апреля 2017 г.). «Соответствие без зависти с более низкими квотами». arXiv:1704.04888 [cs.GT ].
  11. ^ "Насколько хороши популярные соответствия?" (PDF). www.cse.iitm.ac.in. Архивировано из оригинал (PDF) 17 января 2019 г.. Получено 16 января 2019.
  12. ^ Таденума, Коичи (2011), «Партнерство, солидарность и минимальная зависть в проблемах сопоставления», во Флербэе, Марк; Саллес, Морис; Веймарк, Джон А. (ред.), Социальная этика и нормативная экономика, Исследования в области выбора и благосостояния, Springer Berlin Heidelberg, стр. 155–167, Дои:10.1007/978-3-642-17807-8_6, ISBN  9783642178078
  13. ^ Сегал-Халеви, Эрель; Айгнер-Хорев, Элад (28 января 2019 г.). «Соответствия без зависти в двудольных графах и их приложения к справедливому делению». arXiv:1901.09527 [cs.DS ].
  14. ^ Сен, Сандип; Нукия, Стивен В. (1 августа 2001 г.). Повышение оптимальности n агентских подразделений без зависти. Интеллектуальные агенты VIII. Конспект лекций по информатике. 2333. Шпрингер, Берлин, Гейдельберг. стр.277–289. Дои:10.1007/3-540-45448-9_20. ISBN  978-3-540-43858-8.