Алгоритм стабильного брака в государственном дейтинге Сингапура

Когда государство решает найти вам пару

Представьте: вы государственный чиновник в Сингапуре, вам от 21 до 35 лет, и однажды утром вам предлагают воспользоваться официальным правительственным приложением для знакомств — не Tinder, не Bumble, а сервисом, созданным агентством GovTech прямо на государственном хакатоне. И в его основе лежит алгоритм, удостоенный Нобелевской премии по экономике.

Это не антиутопия и не шутка. Сингапур запустил FirstDate — государственную платформу для знакомств, использующую модель стабильного сопоставления Гейла–Шепли. Проект вызвал волну обсуждений по всему миру: одни называют его «дистопией», другие — смелым и практичным решением демографического кризиса. Давайте разберёмся, как это работает, почему алгоритм стабильного брака оказался именно здесь — и что это говорит о будущем технологий знакомств.

Демографический контекст: зачем Сингапуру государственный Tinder

Сингапур — один из мировых лидеров по уровню жизни, но одновременно один из аутсайдеров по рождаемости. Страна давно ведёт активную пронаталистскую политику.

Ещё в 1984 году страна создала Агентство социального развития (Social Development Unit), чтобы стимулировать заключение браков среди выпускников университетов. Это был первый государственный «свах». Спустя четыре десятилетия государство снова берёт дело в свои руки, но теперь вооружено куда более мощным инструментом — математикой.

Сингапур запустил государственный сервис знакомств для работников государственного сектора на фоне рекордно низкого уровня рождаемости и стареющего населения. Пилотная программа FirstDate ориентирована на государственных служащих в возрасте от 21 до 35 лет и использует алгоритм Гейла–Шепли для подбора партнёров.

Агентство GovTech Сингапура создало FirstDate в ходе ежегодного хакатона. Проект начался с простого вопроса: делает ли большее количество потенциальных совпадений поиск партнёра проще?

Алгоритм Гейла–Шепли: математика любви

Чтобы понять, как работает FirstDate, нужно познакомиться с алгоритмом в его основе.

Алгоритм Гейла–Шепли, также известный как алгоритм стабильного брака, был разработан для создания стабильных совпадений между двумя группами на основе индивидуальных предпочтений. Его создали математик Ллойд Шепли и экономист Дэвид Гейл.

Несмотря на первоначальное отсутствие теоретической основы, алгоритм стабильного брака Гейла–Шепли применялся в Национальной программе распределения ординаторов (National Resident Matching Program) с 1952 года и был опубликован в «The American Mathematical Monthly» в 1962 году.

«Цель — найти стабильные совпадения между двумя группами людей с разными предпочтениями. Ключевой принцип: совпадения должны быть стабильными — не должно существовать двух людей, которые предпочли бы друг друга своим текущим партнёрам.»

Как работает алгоритм — пошагово

Алгоритм разбивает участников на две группы равного размера: «предлагающих» и «принимающих». Каждый непарный участник из группы предлагающих выбирает своего лучшего кандидата, и это совпадение остаётся в силе, пока принимающий не выберет более предпочтительного партнёра. Отвергнутые переходят к следующему выбору в следующем раунде — до тех пор, пока все не получат пару.

sequenceDiagram
    participant P as Предлагающий (А)
    participant R as Принимающий (Б)
    participant A as Алгоритм

    A->>P: Составь список предпочтений
    A->>R: Составь список предпочтений
    P->>R: Предложение №1 (лучший кандидат)
    R-->>P: Принято (временно)
    Note over P,R: Появляется новый претендент
    P->>R: Новое предложение (лучший, чем текущий)
    R-->>P: Принято (текущий отвергнут)
    P->>A: Отвергнутый ищет следующий вариант
    A-->>P: Все участники получили пару — алгоритм завершён

Что делает совпадение стабильным: после завершения процесса ни одна пара не предпочтёт друг друга своим текущим партнёрам. Ключевое новшество алгоритма состоит в том, что он доказал: такое стабильное совпадение всегда существует, когда есть равное количество участников каждого типа.

Реализация на Python (упрощённая)

def gale_shapley(proposers_prefs: dict, receivers_prefs: dict) -> dict:
    """
    Алгоритм Гейла–Шепли (deferred acceptance).
    proposers_prefs: {proposer: [ranked list of receivers]}
    receivers_prefs: {receiver: [ranked list of proposers]}
    Возвращает: {proposer: receiver}
    """
    free_proposers = list(proposers_prefs.keys())
    next_proposal = {p: 0 for p in proposers_prefs}      # индекс следующего предложения
    current_match = {}                                     # receiver -> proposer

    while free_proposers:
        p = free_proposers.pop(0)
        r = proposers_prefs[p][next_proposal[p]]           # лучший доступный кандидат
        next_proposal[p] += 1

        if r not in current_match:
            current_match[r] = p                           # принимающий свободен — принимаем
        else:
            current_p = current_match[r]
            # Принимающий выбирает лучшего из двух претендентов
            r_rank = receivers_prefs[r]
            if r_rank.index(p) < r_rank.index(current_p):
                current_match[r] = p                       # новый претендент лучше
                free_proposers.append(current_p)           # старый снова свободен
            else:
                free_proposers.append(p)                   # новый отвергнут

    return {p: r for r, p in current_match.items()}

Как FirstDate применяет алгоритм на практике

Абстрактная математика — это хорошо, но как она превращается в реальные свидания?

Шаг 1: Анкета

Чтобы найти потенциальных партнёров, заявители должны заполнить анкету, охватывающую интересы, привычки, ценности и предпочтения пользователя. Затем анкета применяет нобелевскую математическую модель — алгоритм стабильного брака Гейла–Шепли. Движок «оценивает ключевые предпочтения совместимости» для расчёта пар внутри защищённой сети.

Участникам задают 60 вопросов, затрагивающих всё — от планов на будущее до «красных флагов».

Шаг 2: Одно совпадение за раз

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

FirstDate предлагает активности для свидания и собирает обратную связь после него.

Шаг 3: Верификация личности

FirstDate использует государственную систему цифровой идентификации Сингапура для аутентификации. Это помогает верифицировать личности и предотвращает вступление в сервис людей, состоящих в браке.

Где ещё применяется алгоритм Гейла–Шепли

Focusing на романтике, легко упустить масштаб реального применения этого алгоритма.

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

Алгоритм стабильного брака Гейла–Шепли является предпочтительным методом, используемым принадлежащим Match Group приложением Hinge — которое, к слову, является самым популярным приложением для знакомств в Сингапуре.

Критика и ограничения: всё ли так гладко?

Ни одна технология не идеальна, и FirstDate — не исключение.

Реакция общества

Запуск вызвал неоднозначную реакцию в Сингапуре: часть пользователей социальных сетей назвала инициативу «дистопической», тогда как другие выразили желание попробовать сервис.

Математические ограничения алгоритма

Совпадение, генерируемое алгоритмом Гейла–Шепли, оптимально для предлагающей стороны — каждый предлагающий получает наилучшего возможного партнёра — и наименее выгодно для принимающей стороны, которая получает наименее предпочтительного из возможных партнёров. Это математически встроенная асимметрия.

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

Вопрос конфиденциальности

Государственный сервис знакомств неизбежно поднимает вопросы приватности. Пользователи отвечают на 60 личных вопросов, а их данные проходят верификацию через государственный ID. Где хранятся ответы? Кто имеет к ним доступ? Эти вопросы пока остаются открытыми.

Выводы: математика как язык любви

FirsDate — это гораздо больше, чем просто ещё одно приложение для знакомств. Это смелый эксперимент на стыке демографической политики, технологий и поведенческой экономики.

Алгоритм Гейла–Шепли доказал свою состоятельность за 60+ лет применения в медицине и образовании. Его перенос в сферу романтических отношений — логичный, хотя и дерзкий шаг. Центральная концепция состоит в том, что совпадения должны быть стабильными: не должно существовать двух людей, которые предпочли бы друг друга своим реальным партнёрам. Это ровно то, чего большинство людей хочет от долгосрочных отношений.

Главный вопрос не в том, работает ли алгоритм математически — он работает. Вопрос в том, согласны ли люди доверить выбор спутника жизни государственному уравнению. Сингапур решил попробовать. Остальной мир смотрит.

Романтика — это не враг математики. Возможно, лучшие отношения начинаются не со свайпа, а с правильно заданного вопроса.