Из Википедии, свободной энциклопедии
  (Перенаправлен из стабильного брака )
Перейти к навигации Перейти к поиску

В математике , экономике и информатике , то проблема стабильного брака (также стабильная проблема соответствия или SMP ) является задачей нахождения соответствия между стабильным двумя одинаковыми по размеру наборов элементов данных упорядочивания предпочтений для каждого элемента. Соответствия является биекция из элементов одного набора к элементам другого набора. Соответствующий является не стабильным , если:

  1. Существует элемент A первого согласованного набора, который предпочитает некоторый данный элемент B второго согласованного набора элементу, с которым A уже согласован, и
  2. B также предпочитает A элементу, которому уже соответствует B.

Другими словами, соответствие является стабильным, когда не существует ни одного совпадения ( A , B ), которое оба предпочитают друг друга своему текущему партнеру при сопоставлении.

Проблема стабильного брака сформулирована следующим образом:

Учитывая n мужчин и n женщин, где каждый оценил всех представителей противоположного пола в порядке предпочтения, женитесь на мужчинах и женщинах вместе так, чтобы не было двух людей противоположного пола, которые оба предпочли бы иметь друг друга, а не своих нынешних партнеров. . Когда таких пар людей нет, совокупность браков считается стабильной.

Существование двух классов, которые необходимо объединить в пары (в данном примере гетеросексуальные мужчины и женщины), отличает эту проблему от проблемы соседей по квартире .

Приложения [ править ]

Алгоритмы поиска решений проблемы стабильного брака находят применение во множестве реальных ситуаций, пожалуй, самая известная из них связана с назначением выпускников-медиков на их первые визиты в больницу. [1] В 2012 году Нобелевская мемориальная премия по экономическим наукам была присуждена Ллойду С. Шепли и Элвину Э. Роту «за теорию стабильного распределения и практику рыночного дизайна». [2]

Важное и крупномасштабное применение стабильного брака заключается в назначении пользователей на серверы в большом распределенном Интернет-сервисе. [3] Миллиарды пользователей получают доступ к веб-страницам, видео и другим сервисам в Интернете, требуя, чтобы каждый пользователь был сопоставлен с одним из (потенциально) сотен тысяч серверов по всему миру, которые предлагают эту услугу. Пользователь предпочитает серверы, которые находятся достаточно близко друг к другу, чтобы обеспечить более быстрое время отклика для запрашиваемой услуги, что приводит к (частичному) предпочтительному упорядочиванию серверов для каждого пользователя. Каждый сервер предпочитает обслуживать пользователей, насколько это возможно, с меньшими затратами, что приводит к (частичному) предпочтительному упорядочиванию пользователей для каждого сервера. Сети доставки контентакоторые распространяют большую часть мирового контента и услуг, решают эту большую и сложную проблему стабильного брака между пользователями и серверами каждые десятки секунд, чтобы позволить миллиардам пользователей быть сопоставленными с их соответствующими серверами, которые могут предоставлять запрошенные веб-страницы, видео или другие Сервисы. [3]

Различные стабильные совпадения [ править ]

Основная статья: Решетка стабильных соответствий

В общем, может быть много разных стабильных соответствий. Например, предположим, что есть три мужчины (A, B, C) и три женщины (X, Y, Z), которые имеют следующие предпочтения:

А: YXZ B: ZYX C: XZY  
X: BAC Y: CBA Z: ACB

Есть три стабильных решения для этого согласования:

  • мужчины получают свой первый выбор, женщины - третий - (AY, BZ, CX);
  • всем участникам предоставляется второй выбор - (AX, BY, CZ);
  • женщины получают свой первый выбор, а мужчины - третий - (AZ, BX, CY).

Все три стабильны, потому что нестабильность требует, чтобы оба участника были более довольны альтернативным матчем. Предоставление одной группе права первого выбора гарантирует, что матчи будут стабильными, потому что они будут недовольны любым другим предложенным матчем. Предоставление каждому возможности второго выбора гарантирует, что любой другой матч не понравится одной из сторон. В общем, семейство решений любого экземпляра проблемы стабильного брака может иметь структуру конечной распределительной решетки , и эта структура приводит к эффективным алгоритмам для нескольких проблем стабильных браков. [4]

В равномерно-случайном примере проблемы стабильного брака с n мужчинами и n женщинами среднее количество стабильных совпадений асимптотически . [5] В случае стабильного брака, выбранного для максимального увеличения числа различных стабильных совпадений, это число является экспоненциальной функцией от n . [6] Подсчет количества стабильных совпадений в данном экземпляре - # P-полный . [7]

Алгоритмическое решение [ править ]

Основная статья: алгоритм Гейла – Шепли
Анимация, показывающая пример алгоритма Гейла – Шепли

В 1962 году Дэвид Гейл и Ллойд Шепли доказали, что для любого равного числа мужчин и женщин всегда возможно решить SMP и сделать все браки стабильными. Они представили алгоритм для этого. [8] [9]

Алгоритм Гейла-Шепли (также известный как отложенный алгоритм приема) включает в себя ряд «раундов» (или « итераций »):

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

Этот алгоритм гарантированно произведет стабильный брак для всех участников во времени, где есть количество мужчин или женщин. [10]

Среди всех возможных различных стабильных совпадений он всегда дает лучший для всех мужчин среди всех стабильных совпадений и худший для всех женщин. Это правдивый механизм с точки зрения мужчин (предлагающей стороны). То есть ни один мужчина не может добиться лучшего соответствия для себя, искажая свои предпочтения. Более того, алгоритм GS является доказательством даже групповой стратегии для мужчин, т. Е. Никакая коалиция мужчин не может координировать искажение своих предпочтений так, чтобы все мужчины в коалиции были строго в лучшем положении. [11] Тем не менее, некоторая коалиция может искажать свои предпочтения так, что одни мужчины живут лучше, а другие сохраняют того же партнера. [12]Алгоритм GS не соответствует действительности для женщин (проверяющая сторона): каждая женщина может исказить свои предпочтения и получить лучшее соответствие.

Теорема о сельских больницах [ править ]

Основная статья: Теорема о сельских больницах

В сельской местности больницы теорема относится более общий вариант задача стабильного согласование, как и применение в задаче сопоставления врачей позиции в больницах, отличающемся следующие способах от основного п -До- п формы задачи стабильной брак:

  • Каждый участник может пожелать быть сопоставленным только с подмножеством участников на другой стороне сопоставления.
  • Участники на одной стороне сопоставления (больницы) могут иметь числовой потенциал, указывая количество врачей, которых они готовы нанять.
  • Общее количество участников на одной стороне может не равняться общей вместимости, которой они должны соответствовать на другой стороне.
  • Полученное соответствие может не совпадать со всеми участниками.

В этом случае условием стабильности является то, что ни одна несовпадающая пара не предпочитает друг друга своей ситуации в сопоставлении (независимо от того, является ли эта ситуация другим партнером или несовпадающей). При этом условии стабильное сопоставление все еще будет существовать, и его все еще можно будет найти с помощью алгоритма Гейла – Шепли.

Для такого рода задач стабильного согласования теорема о сельских больницах утверждает, что:

  • Набор назначенных врачей и количество занятых должностей в каждой больнице одинаковы во всех стабильных матчах.
  • Любая больница, у которой есть несколько свободных позиций в некотором стабильном сопоставлении, получает точно такой же набор врачей во всех стабильных сопоставлениях.

Связанные проблемы [ править ]

При стабильном сопоставлении с безразличием некоторые мужчины могут безразлично относиться к двум или более женщинам и наоборот.

Проблема стабильных соседей по комнате похожа на проблему стабильного брака, но отличается тем, что все участники принадлежат к одному пулу (вместо того, чтобы быть разделенными на равное количество «мужчин» и «женщин»).

Проблема больниц / резидентов - также известная как проблема поступления в колледж - отличается от проблемы стабильного брака тем, что в больницу могут принимать несколько резидентов, а в колледж - входящий класс из нескольких студентов. Алгоритмы решения проблемы больниц / резидентов могут быть ориентированы на больницу (как NRMP была до 1995 года) [13] или ориентирована на жителей . Эта проблема была решена с помощью алгоритма в той же оригинальной статье Гейла и Шепли, в которой решалась проблема стабильного брака. [8]

Проблема больниц / резидентов с парами позволяет включать в набор резидентов пары, которые должны быть распределены вместе либо в одну и ту же больницу, либо в конкретную пару больниц, выбранных парой (например, супружеская пара хочет гарантировать, что они останутся вместе и не застревать в программах, которые находятся далеко друг от друга). Добавление пар к проблеме больниц / резидентов делает проблему NP-полной . [14]

Задача присваивания стремится найти соответствие во взвешенном двудольном графе, которое имеет максимальный вес. Максимально взвешенное сопоставление не обязательно должно быть стабильным, но в некоторых приложениях максимальное взвешенное сопоставление лучше, чем стабильное.

Проблема согласования с контрактами является обобщением проблемы согласования, в которой участники могут быть согласованы с различными условиями контрактов. [15] Важным частным случаем контрактов является согласование с гибкой заработной платой. [16]

См. Также [ править ]

  • Matching (теория графов) - соответствие между разными вершинами графа; обычно не имеет отношения к упорядочиванию предпочтений.
  • Сопоставление без зависти - ослабление стабильного сопоставления для задач сопоставления многие к одному
  • Сопоставление радуги для графов с краями
  • Устойчивый согласующий многогранник

Ссылки [ править ]

  1. ^ Стабильные алгоритмы сопоставления
  2. ^ "Премия в области экономических наук 2012" . Nobelprize.org . Проверено 9 сентября 2013 .
  3. ^ a b Брюс Мэггс и Рамеш Ситараман (2015). «Алгоритмические самородки в доставке контента» (PDF) . Обзор компьютерных коммуникаций ACM SIGCOMM . 45 (3).
  4. ^ Gusfield, Dan (1987). «Три быстрых алгоритма для четырех проблем в стабильном браке». SIAM Journal on Computing . 16 (1): 111–128. DOI : 10.1137 / 0216010 . Руководство по ремонту 0873255 . 
  5. ^ Питтель, Борис (1989). «Среднее количество стабильных совпадений». Журнал СИАМ по дискретной математике . 2 (4): 530–549. DOI : 10.1137 / 0402048 . Руководство по ремонту 1018538 . 
  6. ^ Карлин, Анна Р .; Гаран, Шаян Овейс; Вебер, Робби (2018). «Просто экспоненциальная верхняя граница максимального числа стабильных сопоставлений». В Диакониколасе, Илиас; Кемпе, Дэвид; Хенцингер, Моника (ред.). Труды 50-го симпозиума по теории вычислений (STOC 2018) . Ассоциация вычислительной техники. С. 920–925. arXiv : 1711.01032 . DOI : 10.1145 / 3188745.3188848 . Руководство по ремонту 3826305 . 
  7. ^ Ирвинг, Роберт В .; Кожа, Пол (1986). «Сложность подсчета стабильных браков». SIAM Journal on Computing . 15 (3): 655–667. DOI : 10.1137 / 0215048 . Руководство по ремонту 0850415 . 
  8. ^ a b Gale, D .; Шепли, LS (1962). «Прием в колледж и стабильность брака» . Американский математический ежемесячник . 69 (1): 9–14. DOI : 10.2307 / 2312726 . JSTOR 2312726 . 
  9. ^ Харри Мэрсон : «Стабильный Брак проблема», Брандес Обзор 12, 1992 ( онлайн ).
  10. ^ Ивама, Кадзуо ; Миядзаки, Шуичи (2008). «Обзор проблемы стабильного брака и его вариантов». Международная конференция по образованию и исследованиям в области информатики для общества, распространяющего знания (ICKS 2008) . IEEE. С. 131–136. DOI : 10,1109 / ICKS.2008.7 . ЛВП : 2433/226940 . ISBN 978-0-7695-3128-1.
  11. ^ Дубинс, LE ; Фридман, Д.А. (1981). «Макиавелли и алгоритм Гейла – Шепли». Американский математический ежемесячник . 88 (7): 485–494. DOI : 10.2307 / 2321753 . JSTOR 2321753 . Руководство по ремонту 0628016 .  
  12. ^ Хуан, Chien-Chung (2006). «Обман со стороны мужчин в стабильном алгоритме сопоставления Гейла-Шепли». В Азаре Йоси; Эрлебах, Томас (ред.). Алгоритмы - ESA 2006, 14-й ежегодный европейский симпозиум, Цюрих, Швейцария, 11-13 сентября 2006 г., Материалы . Конспект лекций по информатике. 4168 . Springer. С. 418–431. DOI : 10.1007 / 11841036_39 . Руководство по ремонту 2347162 . 
  13. ↑ Робинсон, Сара (апрель 2003 г.). «Встречаются ли студенты-медики со своим (наилучшим) совпадением?» (PDF) . Новости СИАМ (3): 36 . Проверено 2 января 2018 .
  14. ^ Gusfield, D .; Ирвинг, Р.В. (1989). Проблема стабильного брака: структура и алгоритмы . MIT Press. п. 54. ISBN 0-262-07118-5.
  15. ^ Хэтфилд, Джон Уильям; Милгром, Пол (2005). «Согласование с контрактами». Американский экономический обзор . 95 (4): 913–935. DOI : 10.1257 / 0002828054825466 . JSTOR 4132699 . 
  16. ^ Кроуфорд, Винсент; Ноер, Элси Мари (1981). «Подбор работы с разнородными фирмами и рабочими». Econometrica . 49 (2): 437–450. DOI : 10.2307 / 1913320 . JSTOR 1913320 . 

Дальнейшее чтение [ править ]

  • Клейнберг, Дж., И Тардос, Э. (2005) Разработка алгоритмов , Глава 1, стр. 1–12. См. Текст [1] на сопутствующем веб-сайте .
  • Knuth, DE (1996). Стабильный брак и его связь с другими комбинаторными проблемами: введение в математический анализ алгоритмов . CRM Proceedings and Lecture Notes. Английский перевод. Американское математическое общество.
  • Питтель, Б. (1992). «О возможных решениях проблемы стабильного брака» . Анналы прикладной теории вероятностей . 2 (2): 358–401. DOI : 10.1214 / aoap / 1177005708 . JSTOR  2959755 .
  • Рот, AE (1984). «Эволюция рынка труда для медицинских интернов и ординаторов: тематическое исследование в теории игр» (PDF) . Журнал политической экономии . 92 (6): 991–1016. DOI : 10.1086 / 261272 .
  • Рот, AE; Сотомайор, МАО (1990). Двустороннее сопоставление: исследование в области теоретико-игрового моделирования и анализа . Издательство Кембриджского университета .
  • Шохам, Йоав; Лейтон-Браун, Кевин (2009). Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы . Нью-Йорк: Издательство Кембриджского университета . ISBN 978-0-521-89943-7.См. Раздел 10.6.4; скачать бесплатно онлайн .
  • Schummer, J .; Вохра, Р.В. (2007). «Конструирование механизмов без денег» (PDF) . В нисане - Ноам; Roughgarden, Тим; Тардос, Ева; Вазирани, Виджай (ред.). Алгоритмическая теория игр . С. 255–262. ISBN 978-0521872829.

Внешние ссылки [ править ]

  • Интерактивная демонстрация SMP в формате Flash
  • https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
  • http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
  • Заметки к лекциям SMP