Введение: когда математика приходит на помощь личной жизни

Представьте, что вы пятничным вечером сидите в баре, листаете популярное дейтинг-приложение и ловите себя на мысли: почему алгоритм в сотый раз подсовывает вам совсем не тех людей (ведь продакшен-баги и то реже повторяются)? За этим «невезеньем» скрывается холодный расчет продуктовых метрик. Но что происходит, когда за разработку платформы для знакомств берется не стартап с венчурным финансированием, а целое государство, у которого на кону стоит демография?

В условиях демографических вызовов правительство Сингапура неоднократно экспериментировало с IT-инициативами для содействия знакомствам среди граждан. В основе академических и прикладных дискуссий о цифровом сватовстве лежат строгие математические принципы. Одним из самых элегантных решений является алгоритм Гейла — Шепли (Gale-Shapley algorithm), известный как алгоритм стабильного брака.

В этой статье мы разберем математическую базу алгоритма, ограничения коммерческих рекомендательных систем и напишем рабочий пример реализации логики стабильного распределения на Python.

Анатомия проблемы: почему Tinder не решает системных задач

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

  • Дисбаланс внимания: небольшой процент популярных пользователей получает максимум отклика, пока алгоритм игнорирует остальных.
  • Конфликт бизнес-модели: цель платформы — удержать пользователя в системе (как легаси-код на поддержке), а не помочь ему удалить приложение после успешного мэтча.
  • Отсутствие глобальной оптимизации: локальные рекомендации не гарантируют эффективного распределения ресурсов всей базы пользователей.

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

Теоретическая база: алгоритм Гейла — Шепли

Разработанный в 1962 году Дэвидом Гейлом и Ллойдом Шепли алгоритм решает задачу поиска стабильного паросочетания (Stable Matching Problem) для двух равных по численности множеств с упорядоченными списками предпочтений.

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

Как работает логика инициативы:

  1. Все мужчины (или инициаторы) делают предложение своим самым желанным женщинам из списка.
  2. Женщины временно принимают лучшее из поступивших предложений, а остальные отвергают.
  3. На следующем шаге отвергнутые мужчины делают предложения следующим кандидаткам из своего списка предпочтений.
  4. Процесс повторяется, пока каждый не найдет свою пару.

Реализация алгоритма на Python

Пора перенести сухую теорию в плоскость компилятора. Представим задачу в виде словарей предпочтений и напишем базовую реализацию алгоритма Гейла — Шепли на Python:

def gale_shapley(men_prefs, women_prefs):
    # Инициализация свободных мужчин
    free_men = list(men_prefs.keys())
    engaged = {}
    
    # Создаем обратный рейтинг для женщин для быстрого поиска (O(1))
    women_ranking = {
        w: {m: i for i, m in enumerate(prefs)}
        for w, prefs in women_prefs.items()
    }
    
    # Указатель на следующий выбор мужчины
    next_proposal = {m: 0 for m in men_prefs}
    
    while free_men:
        m = free_men.pop(0)
        m_prefs = men_prefs[m]
        w = m_prefs[next_proposal[m]]