Бальный зал гудит. Гости подходят когда придётся — это самый настоящий случайный поток. Распорядитель должен найти каждому пару для танца. Можно свести двоих сразу — но вдруг через минуту явится кто-то гораздо более подходящий? А если медлить, копится нетерпение: стоять без пары скучно и обидно. Такая задачка — головоломка для программ, управляющих доставкой или облачными вычислениями, где решения надо принимать, не зная будущего.

Ключ к успеху — в том, как считать недовольство ожидающих. Если штраф растёт с числом одиноких гостей (каждый лишний добавляет забот), то число возможных комбинаций пар взрывается: оно растёт как 2 в степени n, где n — число гостей.

Идею такого состязания с идеальным соперником ввёл Джон фон Нейман для анализа стратегических игр. Для масштабного штрафа любой заранее заданный, не подстраивающийся под обстановку план проигрывает идеалу экспоненциально.

Но стоит переключить режим нетерпения — и задача вдруг становится простой. Представьте, что недовольство у каждого гостя растёт с ускорением: первая минута ожидания терпима, а пятая уже выводит из себя. Добавьте к этому крошечный, но обязательный штраф уже за сам факт задержки — и поведение распорядителя резко меняется, словно система переключила режим. Такую формулу недовольства описывают как f(t) = $t^k$/k + t, где t — время. В нуле штрафа нет, но в первое же мгновение появляется слагаемое t, а потом рост ускоряется. Достаточно простого правила: если кто-то ждёт дольше порога 4δ, немедленно соединить его с ближайшей парой. Этот «нетерпеливый» алгоритм глядит лишь на часы — и всё равно работает почти идеально, проигрывая всезнающему сопернику не более чем в константу.

Так бал завершается без драм: немножко терпения, но не чрезмерного. Этот простой урок теперь вшит в логистические и облачные сервисы, чтобы пары — будь то заказы или задачи — встречались вовремя.