Музей фактов

В экономике для решения задачи о марьяже, то есть нахождения стабильных сочетаний пар, известен алгоритм Гэйла — Шепли, изначально описанный этими учёными на примере формирования брачных союзов. Если взять одинаковое число мужчин и женщин и попросить их составить список предпочтений противоположного пола по убыванию, то алгоритм всегда составит такое распределение пар, чтобы в разных парах не нашлось двух человек, предпочитающих друг друга их назначенным партнёрам, то есть все браки в конечном итоге стабильны. Применение алгоритму нашлось в самых разных областях, например, для назначения новых докторов в больницы или нахождения оптимальных приёмных родителей для сирот. А экономист Элвин Рот использовал его в США для изменения системы распределения донорских почек, что на порядок увеличило количество спасённых реципиентов. Проблема была в том, что люди часто готовы пожертвовать почку только для близких, но не могут из-за несовместимости по группе крови или другим факторам, и алгоритм Гэйла — Шепли помог через сложные цепочки обмена сводить такие пары друг с другом.

Источник: Tproger / Алгоритмы спасают людей: как алгоритм подбора пар сохраняет жизни

алгоритмы донорство математика медицина почки семья США трансплантация экономика