Свойства турниров на выбывание.
Турниры на выбывание, или турниры по олимпийской системе, — это один из самых популярных форматов проведения турниров. Устроен он очень просто. Представим набор участников, команд. В каждом матче победитель проходит в следующий раунд турнира, а проигравший покидает турнир. Таким образом, после каждого раунда количество участников уменьшается в два раза, и мы достаточно быстро можем определить победителя из большого количества участников. Поэтому такой формат проведения турниров очень популярен при проведении различных кубков, в которых принимает участие большое количество команд. Например, футбольный кубок России проходит как раз по олимпийской системе. Практически все теннисные турниры также используют формат турнира на выбывание.
Несмотря на кажущуюся простоту такого формата проведения турниров, на самом деле организаторы могут сталкиваться с достаточно серьезными академическими задачами — в первую очередь с задачами, которые лежат в области дизайна правил проведения турниров. Сегодня я как раз хотел бы рассказать об одной из таких задач — о задаче оптимального посева команд турнира.
Что такое посев? Перед началом турнира команды можно проранжировать по силе. Например, во многих видах спорта ведется рейтинг команд. И давайте представим, что мы можем сравнить все команды друг с другом по силе. У нас есть сильнейшая команда (будем называть ее Первой), вторая по силе команда (будем называть ее Второй) и так далее. Перед началом турнира команды распределяются по турнирной сетке. Вообще говоря, распределить команды по турнирной сетке можно большим числом способов. Какой из них оптимален для организаторов?
Здесь все зависит от того, какой смысл мы вкладываем в понятие «оптимален». Если организаторы хотят максимизировать вероятность победы самого сильного участника турнира, то есть первого номера посева, то, например, в турнире из четырех участников лучше всего поступить следующим образом. Пусть самая сильная команда в полуфинале сыграет с четвертой по силе, а вторая по силе команда сыграет с третьей. Победители этих матчей в финале сыграют друг с другом. При таком наборе полуфиналов вероятность победы самой сильной команды в турнире максимальна. Тем не менее уже при восьми участниках это не так. Бывают оптимальными и другие посевы.
У организаторов может быть и другая целевая функция. Давайте представим, что организаторы заботятся о том, чтобы собрать максимальное количество денег на билеты со всех матчей турнира. Тогда они должны задаться вопросом: а от чего зависит спрос на просмотр того или иного матча? Существует достаточно большое количество эмпирических исследований, выделяющих целый ряд факторов, от которых зависит спрос на просмотр футбольных матчей на стадионе или по телевизору и, соответственно, готовность платить за просмотр этих матчей. В первую очередь важны следующие два параметра. Болельщикам очень важно, чтобы играли друг с другом сильные команды. При прочих равных они с большей готовностью пойдут смотреть на матч, в котором сумма сил соперников больше. Второй важный параметр — это непредсказуемость результата матча, конкурентность матча. Чем меньше разница сил участников матча, тем выше готовность болельщиков платить за просмотр такого матча. Таким образом, организаторы турнира могут поставить перед собой задачу максимизации прибыли по какому-то параметру.
Предположим, что у организаторов есть возможность выбирать, как распределить участников турнира по турнирной сетке. Уже сейчас во многих турнирах используется система посева, когда сильные команды разводятся по разным частям турнирной сетки. Например, на Уимблдонском теннисном турнире из 128 участников 32 оказываются посеянными, то есть занимают специальные выделенные позиции в турнирной сетке. Самый сильный теннисист оказывается посеянным под первым номером на самой верхней строчке; второй по силе — на самой нижней строчке турнирной сетки. И таким образом, раньше финала они друг с другом точно не встретятся.
Возникает вопрос: а такая система посевов, когда сильные участники сначала играют против более слабых участников, будет ли оптимальной для организаторов турнира? И оказывается, что на самом деле, если мы рассматриваем задачу максимизации зрительского спроса на все матчи турнира в сумме, все зависит от следующего параметра: насколько финальные матчи важны организаторам по сравнению с матчами предварительных этапов. Так, если мы предположим, что более сильная команда с достаточно большой вероятностью обыгрывает более слабую команду, если зрительский интерес линейно или почти линейно зависит от качества матча и его конкурентности, то в случае, когда организаторам важно провести интересные финальные матчи в значительно большей степени, чем интересные матчи на предварительных раундах турнира, именно традиционная система посевов (которая используется во многих турнирах), когда в каждом раунде более сильный участник, то есть участник из первой половины по силе, играет против одного из участников из нижней половины по силе, будет оптимальной.
Если представим, что организаторы установили одинаковые цены на билеты на матчи как первых раундов турнира, так и финальных стадий турнира, тогда они не делают различий между первым раундом и финалом. И при такой задаче будет оптимальным другой посев. Оказывается, что в этом случае организаторам было бы более выгодно, если бы сильнейший участник в каждом раунде играл против второго по силе участника, третий участник играл против четвертого по силе и так далее. Таким образом, есть своеобразный trade off между тем, чтобы провести большое количество конкурентных матчей на первых стадиях турниров.
В этом случае большое количество сильных команд покинет турнир уже на первых стадиях, но тем не менее они проведут интересные для болельщиков матчи. При этом финал будет достаточно неконкурентным. В него выйдут команды, которые достаточно сильно различаются по силе. Это первая альтернатива. А вторая альтернатива — сделать так, чтобы в самом начале сильные команды играли против слабых, тогда будет достаточно большое количество разбалансированных матчей на ранних стадиях турнира, но зато в финал выйдут самые сильные команды. И если организаторам важно, чтобы именно в финале на стадион пришло максимальное число болельщиков (например, если организаторы установили большую цену на билеты на финал), тогда именно такая система посевов, которая иногда называется близкой, когда всегда команды, которые близки по силе, играют друг с другом в каждом раунде, будет оптимальной.
Удивительно, что никакие промежуточные посевы оптимальными не бывают. И это интересный теоретический результат, который и является в первом приближении ответом на задачу об оптимальном посеве. Дальше можно двигаться по нескольким разным направлениям. Во многих видах спорта более слабые команды играют достаточно успешно против более сильных. Например, в покере вероятность победы во многом зависит в том числе от удачи, поэтому что будет, если мы проводим турнир, в котором аутсайдеры могут играть довольно успешно? Ответ на этот вопрос пока неизвестен. Это открытая задача. Что будет, если целевая функция организаторов турнира устроена по-другому и зависит от качества матча вовсе не линейно? Ответ на вопрос об оптимальном посеве в таком случае тоже является открытой задачей.
Наши каналы:
@matem - лучший канал для развития логики и интеллектуальных способностей. Ежедневно мы публикуем 2-3 головоломки.
@joyfromx - Удовольствие от Х. Математика, которую не преподавали в школе. Рассказываем о сложной науке увлекательно, доступно и с юмором.
@ticketsfootball - канал, посвящённый Чемпионату мира по футболу, который пройдёт в России в 2018 году. У нас вы сможете узнать последние футбольные новости, прочитать интересные факты об истории мировых первенств и главное - приобрести билеты на любой матч российского мундиаля.
Наша фирма, проработав в данной сфере более 20 лет, имеет за плечами огромный опыт и гарантирует качество, удобство и оперативность оказания всех услуг.🏆