stringtranslate.com

Проблема стабильного брака

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

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

Другими словами, сопоставление является устойчивым, когда не существует пары ( A , B ), каждая из которых предпочитает другого своему текущему партнеру в сопоставлении.

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

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

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

Приложения

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

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

Алгоритм Гейла-Шепли для стабильного соответствия используется для назначения раввинов, окончивших Еврейский унионный колледж, в еврейские общины. [4]

Различные стабильные соответствия

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

А: YXZ Б: ZYX В: XZY  
X: BAC Y: CBA Z: ACB

Существует три устойчивых решения этой схемы соответствия:

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

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

Алгоритмическое решение

Анимация, демонстрирующая пример алгоритма Гейла-Шепли

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

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

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

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

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

Теорема о сельских больницах

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

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

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

Связанные проблемы

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

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

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

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

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

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

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

Ссылки

  1. ^ Стабильные алгоритмы сопоставления
  2. ^ "Премия по экономическим наукам 2012 года". Nobelprize.org . Получено 2013-09-09 .
  3. ^ ab Брюс Мэггс и Рамеш Ситараман (2015). «Алгоритмические крупицы в доставке контента» (PDF) . Обзор компьютерной связи ACM SIGCOMM . 45 (3).
  4. ^ Бодин, Лоуренс; Панкен, Аарон (июнь 2003 г.). «Высокие технологии для высшей власти: размещение выпускников раввинов из Еврейского унионного колледжа — Еврейского института религии». Интерфейсы . 33 (3): 1–11. doi :10.1287/inte.33.3.1.16013. ISSN  0092-2102.
  5. ^ Гасфилд, Дэн (1987). «Три быстрых алгоритма для четырех проблем в стабильном браке». SIAM Journal on Computing . 16 (1): 111–128. doi :10.1137/0216010. MR  0873255.
  6. ^ Питтель, Борис (1989). «Среднее число устойчивых паросочетаний». Журнал SIAM по дискретной математике . 2 (4): 530–549. doi :10.1137/0402048. MR  1018538.
  7. ^ Карлин, Анна Р .; Гаран, Шаян Овейс; Вебер, Робби (2018). «Простая экспоненциальная верхняя граница максимального числа устойчивых паросочетаний». В Диакониколас, Илиас; Кемпе, Дэвид; Хензингер, Моника (ред.). Труды 50-го симпозиума по теории вычислений (STOC 2018) . Ассоциация вычислительной техники. стр. 920–925. arXiv : 1711.01032 . doi : 10.1145/3188745.3188848. MR  3826305.
  8. ^ Ирвинг, Роберт В.; Лезер, Пол (1986). «Сложность подсчета стабильных браков». SIAM Journal on Computing . 15 (3): 655–667. doi :10.1137/0215048. MR  0850415.
  9. ^ ab Gale, D.; Shapley, LS (1962). «Поступление в колледж и стабильность брака». American Mathematical Monthly . 69 (1): 9–14. doi :10.2307/2312726. JSTOR  2312726. Архивировано из оригинала 25 сентября 2017 г.
  10. ↑ Гарри Мейрсон : «Проблема стабильного брака», The Brandeis Review 12, 1992 (онлайн).
  11. ^ Ивама, Казуо ; Миядзаки, Шуичи (2008). «Обзор проблемы стабильного брака и ее вариантов». Международная конференция по образованию и исследованиям в области информатики для общества с циркулирующими знаниями (ICKS 2008) . IEEE. стр. 131–136. doi :10.1109/ICKS.2008.7. hdl : 2433/226940 . ISBN 978-0-7695-3128-1.
  12. ^ Эриксон, Джефф (июнь 2019 г.). "4.5 Стабильное соответствие" (PDF) . Алгоритмы . Иллинойсский университет. стр. 170–176 . Получено 19 декабря 2023 г.
  13. ^ Дубинс, Л. Э .; Фридман, Д. А. (1981). «Макиавелли и алгоритм Гейла–Шепли». American Mathematical Monthly . 88 (7): 485–494. doi :10.2307/2321753. JSTOR  2321753. MR  0628016.
  14. ^ Хуан, Чиен-Чунг (2006). «Обман мужчин в алгоритме стабильного соответствия Гейла-Шепли». В Азар, Йосси; Эрлебах, Томас (ред.). Алгоритмы — ESA 2006, 14-й ежегодный европейский симпозиум, Цюрих, Швейцария, 11–13 сентября 2006 г., Труды . Заметки лекций по информатике. Том 4168. Springer. стр. 418–431. doi :10.1007/11841036_39. MR  2347162.
  15. ^ Робинсон, Сара (апрель 2003 г.). «Встречают ли студенты-медики свою (наилучшую возможную) пару?» (PDF) . SIAM News (3): 36. Получено 2 января 2018 г.
  16. ^ Гасфилд, Д.; Ирвинг, Р. В. (1989). Проблема стабильного брака: структура и алгоритмы . MIT Press. стр. 54. ISBN 0-262-07118-5.
  17. ^ Хэтфилд, Джон Уильям; Милгром, Пол (2005). «Соответствие контрактам». American Economic Review . 95 (4): 913–935. doi :10.1257/0002828054825466. JSTOR  4132699.
  18. ^ Кроуфорд, Винсент; Кноэр, Элси Мари (1981). «Подбор рабочих мест для гетерогенных фирм и работников». Econometrica . 49 (2): 437–450. doi :10.2307/1913320. JSTOR  1913320.

Дальнейшее чтение

Внешние ссылки