Часто в конце спортивных чемпионатов мы наблюдаем матчи, от которых ничего не зависит. Марко Фаэлла и Луиджи Сауро из Неаполитанского университета имени Фридриха II доказали, что это не случайно. Оказывается, в любом круговом турнире с как минимум пятью участниками найдется ни на что не влияющий матч. Результат своих исследований Фаэлла и Сауро обнародовали на 17-й Международной конференции по автономным агентам и многоагентным системам и опубликовали в итоговых материалах конференции.
В последнем туре розыгрыша Единой баскетбольной лиги ВТБ сезона 2017/2018 годов состоялся матч «Нижний Новгород» — «Локомотив-Кубань» (92:86). Результат этого матча ни на что не повлиял: если бы он завершился с любым другим счетом, то «Нижний Новгород» все равно остался бы на седьмом месте, а «Локомотив-Кубань» — на третьем. «Локомотив-Кубань» в случае победы не смог бы обойти впереди стоящие команды. Чтобы убедиться в этом, достаточно посмотреть на итоговую турнирную таблицу Лиги без учета этой единственной игры:
| Место | Команда | Число побед |
|---|---|---|
| 1 | ЦСКА | 22 |
| 2 | Уникс | 22 |
| 3 | Локомотив-Кубань | 17 |
| 4 | Зенит | 16 |
| 5 | Автодор | 14 |
| 6 | Химки | 13 |
| 7 | Нижний Новгород | 9 |
| 8 | ВЭФ | 8 |
| 9 | Цмоки-Минск | 8 |
| 10 | Астана | 7 |
| 11 | Парма | 7 |
| 12 | Калев | 6 |
| 13 | Енисей | 6 |
Такие матчи, как «Нижний Новгород» — «Локомотив-Кубань», Фаэлла и Сауро называют бессмысленными. Очевидно, что организаторы турнира хотели бы избежать бессмысленных матчей. Но возможно ли это сделать?
Ученые ограничиваются рассмотрением видов спорта, в которых каждый матч заканчивается победой одной из команд (например, к таким видам относятся баскетбол и волейбол). Рассматриваются соревнования по круговой системе, то есть каждая команда играет с каждой по одному разу. Ранжирование команд происходит по числу побед. Что касается стимулов команд, то будем считать, что каждая команда хотела бы занять как можно более высокое место.
В соревновании важную роль играет календарь, определяющий последовательность игр. Обычно на практике календарь фиксируется перед началом соревнования. Предположим, что все игры происходят последовательно (это предположение часто выполняется: телевидение заинтересовано в том, чтобы никакие игры не пересекались).
Турниром называется дерево, в котором каждая вершина соответствует матчу, каждое исходящее ребро соответствует одному из двух возможных результатов соответствующего матча, а каждый путь от корневой вершины до терминальной вершины определяет последовательность матчей и соответствует одному из вариантов полного заполнения турнирной таблицы. Рассмотрим произвольный матч М между командами a и b. Формально матч М называется значимым для команды a, если существует хотя бы один вариант развития следующих за М матчей, при котором команда a в случае победы и в случае поражения в матче М окажется на разных местах по итогам чемпионата. Если матч не является значимым ни для одной из играющих команд, то он называется бессмысленным. Турнир называется значимым в строгом (соответственно, слабом) смысле, если все матчи турнира значимы для обеих участвующих команд (соответственно, хотя бы для одной команды).
Если М — последняя игра чемпионата, то мы получаем ситуацию из матча «Нижний Новгород» — «Локомотив-Кубань», описанную выше. Если М — матч в середине турнира, то существует много вариантов развития событий в оставшихся матчах. Для бессмысленности матча М необходимо, чтобы при любом возможном раскладе в оставшихся матчах матч М уже не мог бы изменить место играющих в матче М команд.
Фаэлла и Сауро доказывают три основных результата. Во-первых, авторы работы демонстрируют, что для любого числа участников турнира N ≥ 5 при фиксированном расписании турнир будет содержать бессмысленные матчи. Идея построения такого матча проста. Рассмотрим развитие событий, при котором в последнем матче турнира встречаются команды a и b, причем команда a выиграла, а команда b проиграла все предыдущие матчи. Кроме того, предположим, что все остальные команды обыгрывали друг друга по кругу так, что все они выиграли примерно половину матчей. Тогда команда a независимо от исхода последнего матча займет первое место, а команда b — последнее. Таким образом, матч между a и b будет бессмысленным. А вот если N ≤ 4, то турнир будет значимым в строгом смысле.
При этом оказывается, и это второй важный результат работы, что возможность динамически обновляемого в зависимости от результатов игр расписания позволяет добиться того, что турнир будет значимым в слабом смысле (то есть каждая игра будет значимой по крайней мере для одной из команд). Авторы строят подходящее расписание турнира рекурсивным способом. Недостаток построенного расписания состоит в том, что матчи команды могут быть распределены неравномерно вдоль турнирной дистанции, поэтому воплотить это расписание в жизнь будет проблематично.
Существует ли динамически обновляемое расписание, которое позволяет получить значимый турнир в строгом смысле для произвольного достаточно большого числа команд? Этот вопрос остается открытым. Однако Фаэлла и Сауро доказывают, что если такое расписание и существует, то при N ≥ 6 оно точно не будет сбалансированным, то есть оно не будет разбиваться на туры, в которых каждая команда проводит по одному матчу.
Дмитрий Дагаев,
Лаборатория исследований спорта НИУ ВШЭ