Десять подразделений получили стажёров после большой ярмарки вакансий: учли пожелания и команд, и новичков, а первыми ушли те, о ком заботились больше всего. Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский рисует компромиссный подбор и алгоритм стабильных пар в трёх нотациях.

Рис. 1. Алгоритм Гейла – Шепли: предложения по списку, временное согласие и освобождение
Однажды провели крупную ярмарку вакансий и набрали выпускников-стажёров для десяти подразделений. Старались учесть пожелания и команд, и новичков.
К сожалению, первыми ушли те, о ком заботились больше. Нужно было думать прежде всего о бизнесе, а не только о людях. Компромисс, удобный на бумаге, оставлял пары, которым выгоднее тихо договориться в обход.
Короткий ответ: подбор устойчив, когда нет человека и команды, которые предпочли бы друг друга нынешним партнёрам. Такое распределение всегда находит алгоритм Гейла – Шепли: одна сторона делает предложения по списку, другая держит лучшее из полученных.
Объяснять распределение руководителю удобнее всего диаграммой последовательности: по раундам видно, кто кому предложил, кто кого отпустил и почему в итоге ни стажёру, ни команде нет смысла искать замену в обход правил.
Что такое стабильные пары?
Стабильное паросочетание – способ разбить две стороны на пары так, чтобы никакие человек и команда вне распределения не хотели уйти друг к другу. Если такая пара есть, её называют блокирующей: рано или поздно она договорится в обход правил.
Задачу поставили Дэвид Гейл и Ллойд Шепли в 1962 году. В 2012 году Шепли и Элвин Рот получили Нобелевскую премию по экономике за теорию стабильных распределений и практику: подбор врачей в ординатуру, школьников в школы, доноров почек.
Как устроен алгоритм Гейла – Шепли?
Алгоритм Гейла – Шепли – способ найти стабильные пары, в котором одна сторона делает предложения, а другая отвечает «пока да» или «нет». Свободный стажёр предлагает себя следующей команде из списка. Свободная команда соглашается, занятая сравнивает новичка с прежним и оставляет лучшего.
Согласие временное: команда передумает, если придёт кандидат сильнее. Стажёр же движется по списку только вниз и не обращается к одной команде дважды. Поэтому предложений не больше, чем клеток в таблице пожеланий, и алгоритм всегда заканчивается.
По ГОСТ 19.701 это цикл с тремя ромбами. Петля возврата одна: после каждого ответа – снова к вопросу, остался ли свободный стажёр. Справа на схеме – два способа получить место в команде, слева внизу – вежливый отказ.
Чем плох компромисс?
Сервисная компания «Кедр» берёт четырёх стажёров в четыре команды: «Монтаж», «Сервис», «Проекты», «Склад». Стажёры расставили команды по местам, а команды – стажёров.

Рис. 2. Сумма мест 17, но Жанна и «Сервис» уйдут друг к другу
Отдел кадров ищет компромисс: назначение с наименьшей суммой мест у обеих сторон, как в предыдущей статье сборника. Сумма – 17, двое стажёров попадают куда хотели. Но Жанна хочет в «Сервис» больше, чем в «Монтаж», а «Сервис» предпочитает Жанну Дине.
Пара «Жанна – Сервис» блокирующая. Дина, которой отдали команду мечты, стоит там последней в списке и уйдёт первой: команда при первой возможности возьмёт Жанну. Забота о сумме мест не равна заботе об устойчивости.
Как идут раунды предложений?
Диаграмма последовательности – способ показать обмен сообщениями между участниками во времени. Сверху – участники, стрелки – предложения, пунктир – ответы команд, серые линии отделяют этапы переговоров.
В первом раунде Дина идёт в «Сервис», Егор и Жанна – в «Проекты», Илья – в «Монтаж». «Проекты» оставляют Егора, Жанне отказывают. Во втором раунде Жанна предлагает себя «Сервису», и тот меняет Дину на Жанну.

Рис. 3. Четыре круга и семь предложений до стабильных пар
Дина идёт в «Монтаж», тот отпускает Илью, и Илья уходит на «Склад». Блокирующих пар нет, хотя сумма мест – 18, на одно место больше, чем у компромисса.
Как выглядит подбор глазами стажёра?
Диаграмма состояний – способ показать, через какие положения проходит участник и почему. У стажёра их пять: свободен, ждёт ответа, временно в команде, закреплён, без пары.

Рис. 4. Пять положений стажёра и переходы между ними
Положение «Без пары» возникает, только если мест меньше, чем стажёров. В реальном наборе у подразделения квота: оно держит нескольких лучших кандидатов и отпускает слабейшего, когда приходит сильнее. Алгоритм от этого не меняется.
Почему пары распадаются?
Была коллега Лариса – крайне скромная и колоссально педантичная. Клиент приват-банкинга описал персонального менеджера мечты, и показалось, что это Лариса.
Он назвал лишь то, чего хотел, и забыл упомянуть параметры отрицательного отбора. Через время пришлось произвести «развод»: обоим было лучше взаимодействовать с другими.
Алгоритм надёжен ровно настолько, насколько полны списки. Если сторона перечислила только желаемое и умолчала о неприемлемом, расчёт выдаст формально стабильную пару, которая распадётся. Списки пожеланий стоит дополнять вопросом «с кем точно не сработаетесь?».
Кто должен делать предложения?
Предлагающая сторона получает лучшее из всех стабильных распределений, а отвечающая – худшее. Если в «Кедре» предлагают команды, пары другие: Дина – «Проекты», Егор – «Сервис», Жанна – «Монтаж», Илья – «Склад».

Рис. 5. Обе раскладки стабильны, но выигрывает тот, кто предлагает
Сумма мест у команд падает с 11 до 6, у стажёров растёт с 7 до 12. Американская система подбора ординаторов в 1997 году, наоборот, перешла на предложения кандидатов: прежняя схема систематически играла на руку больницам.
Через год ярмарку повторили, и была дана негласная команда игнорировать пожелания кандидатов, отдавая предпочтение требованиям команд, которым нужны стажёры. Почти все продолжили работу, хотя «хотелки» не учитывались, особенно при формальном отборе.
На языке алгоритма предложения стали делать команды. Новичок ещё не знает, где ему будет хорошо, а команда знает, кто ей нужен. Перекос в пользу команд обошёлся дешевле.
Откуда брать списки пожеланий?
Бухгалтерия приучила большую организацию не тратить деньги зря: летишь в Питер – заскочи в Калининград, будешь в Новосибирске – заедь в Барнаул. Менеджеры получали дополнительные точки в нагрузку из-за территориальной близости.
Когда применил алгоритм, оказалось, что это одна из самых страшных ошибок. Гораздо важнее учитывать силу бренда, конкурентную среду и соответствие менталитета сотрудника клиентской базе города. Списки пожеланий строят по тому, что приносит результат, а не по карте.
Сколько стоит расчёт?
Каждый стажёр делает не больше одного предложения каждой команде: для четырёх на четыре – не больше 16 предложений, в «Кедре» хватило семи. Для ста стажёров и ста команд – не больше 10’000 предложений, доли секунды на ноутбуке. Перебор всех распределений бессмыслен: для ста стажёров число вариантов записывается 158 цифрами.
Когда уместен алгоритм стабильных пар?
Там, где у обеих сторон есть пожелания и каждая может уйти: стажёры и подразделения, менеджеры и клиенты, наставники и новички, сотрудники и города. Если мнение одной стороны не важно, хватит венгерского алгоритма.
Метод не учитывает, что приоритеты меняются со временем. Раз в полгода списки пересобирают и проверяют пары на блокирующие.
В следующей статье сборника – топологическая сортировка: как выстроить работы так, чтобы ни одна не началась раньше нужной.
Какими нотациями рисовать подбор пар?
ГОСТ 19.701 точно передаёт цикл и три проверки, но не показывает, кто кого вытеснил. Его ценят авторы регламентов набора: каждый ромб – правило комиссии.
Диаграмма последовательности делит ход переговоров на раунды. Её любят руководители и аналитики: видно, почему Дина оказалась в «Монтаже», а не в «Сервисе».
Диаграмма состояний описывает путь одного участника. Ею пользуются разработчики систем подбора: каждое положение – статус кандидата в базе.
Какая нотация лучше?
Лучшая нотация для подбора пар – диаграмма последовательности: 18 баллов против 17 у диаграммы состояний и 16 у ГОСТ. Руководитель видит не только итог, но и цепочку вытеснений. Вес вопроса о руководителе удвоен: сборник написан для него.

Рис. 6. Оценка трёх нотаций: 16, 18 и 17 баллов
Диаграмма состояний отстала на балл: она компактнее и удобнее разработчику. ГОСТ остаётся для регламента набора.
Что сделать руководителю?
Хватит четырёх шагов:
- Соберите списки пожеланий обеих сторон и добавьте вопрос «с кем не сработаетесь?».
- Проверьте нынешние пары на блокирующие: кто и куда ушёл бы при первой возможности.
- Решите, какая сторона делает предложения: ей достанется лучшее.
- Пересобирайте списки и пары раз в полгода.
Что запомнить?
- компромисс по сумме мест может оставить пары, которым выгодно уйти
- в стабильном распределении нет блокирующих пар
- алгоритм Гейла – Шепли всегда находит такое распределение
- предлагающая сторона получает лучшее из стабильных распределений
- подбор пар лучше всего рисовать диаграммой последовательности.