6.4. ОЛИМПИЙСКИЙ ТУРНИР (С ВЫБЫВАНИЕМ) И ДРУГИЕ ТУРНИРЫ

Аналогия между сбалансированными экспериментами парных сравнений и круговыми турнирами наводит на мысль, что другие типы турниров тоже могут заслуживать более внимательного изучения. Особенностью таких турниров является то, что от уравновешивания отказываются либо для ускорения, либо для увеличения числа встреч между наиболее удачными игроками, или с обеими целями. Отсутствие баланса затрудняет изучение свойств этих турниров, но они интуитивно привлекательны как метод проведения эксперимента в том случае, когда наша главная цель — выбор наилучшего объекта. Хорошо известен олимпийский турнир (или игра на кубок), с которого мы начнем.

Олимпийский турнир

Будем предполагать, что число игроков было уменьшено в предварительных состязаниях или другим способом так, что оно стало равно некоторой степени 2, скажем, Победитель может быть

объявлен в этом случае после туров и игр, а в круговом турнире потребуется туров и игр, без переигровок.

Если некий игрок побеждает любого соперника с вероятностью то он выигрывает турнир с выбыванием с вероятностью . В более сложном случае вероятность выигрыша игрока очевидно, зависит от первоначального хода турнира, который, как мы предположим с самого начала, будет совершенно случайным. Пусть означает вероятность того, что доходит до тура турнира и выигрывает свою встречу в этом туре, тогда вероятность его победы в турнире. Пусть вероятность того, что встречается с в -том туре и вероятность их встречи в ходе турнира. Ясно, что

Предположим теперь, что

Тогда вероятность выигрыша в турнире

Если известно, как проходил турнир, то следовательно, можно вычислить. Вместо этого мы можем получить выражения для значений до проведения жеребьевки. Эти априорные вероятности до сих пор связывались с (6.4.2). Мы имеем

Если и встречаются во втором туре, в котором будут участвовать игроков, они оба должны выиграть в первом туре, так что

Продолжая рассуждения, находим

и, следовательно, из (6.4.1)

Интересно заметить, что зависит от лишь как функция их произведения Мы видим также, что вероятность того, что встретятся в финале, равна Если на время мы вообразим,

что были фаворитами, которых поместили в противоположные половины жеребьевки, эта вероятность будет

Для того чтобы рассмотреть общий случай с вероятностями предпочтения возьмем и предположим (без потери общности), что выстроились по жребию в этом порядке. Так, мы имеем, например:

Соответствующие вероятности до жеребьевки можно получить усреднением по всем возможным исходам жеребьевок. Пусть означает совместную вероятность того, что победит в первом туре и выиграет у победителя встречи во втором; тогда — это выражение (6.4.3). Также мы можем (для написать из (6.4.4) более подробно в виде . Отсюда следует, что

Для число членов в правой части может стать огромным. Так, есть среднее из

Сравнение эффективности турниров

Для сравнения олимпийского турнира с круговым мы можем использовать как критерий вероятность того, что лучший игрок (т. е. игрок с наибольшей ожидаемой суммой очков) выиграет турнир. Конечно, такое сравнение несправедливо по отношению к олимпийскому турниру, который требует значительно меньше игр (однако не всегда, см. упражнение 6.3). Поэтому при сравнении можно рассмотреть олимпийский турнир с повторениями (в несколько кругов).

Например, если два повторения требуют 6 игр, то же число, что и для кругового турнира с 4 игроками. Возможные исходы

описываются размещениями первые три из которых отвечают единоличной победе одного из трех игроков. Трудность состоит в том, что для обоих типов турниров возможен дележ первого места. Простейший выход из этого положения, причем совсем неплохой, если вероятность дележа мала, — это бросание жребия для определения победителя. В практике проведения турниров устраивается повторная игра (переигрывание); если это возможно, то число игр становится случайной величиной, не меньшей 6. Возникает также вопрос: как повторять игры в олимпийском турнире? Можно использовать две различные случайные жеребьевки (назовем их но, вероятно, лучше просто поместить двух финалистов первого турнира в разные половины жеребьевки второго турнира, а их соперников из первого круга поменять местами Гленн [55] исследовал этот и смежные вопросы, в основном в серии численных примеров, для различных наборов вероятностей предпочтения, а также при строгой стохастической транзитивности (§ 1.3). Дележ первого места устранялся кратчайшим возможным переигрыванием: дележ между двумя игроками требует в точности одной дополнительной игры, но тройной дележ требует уже по крайней мере трех дополнительных игр и может привести к бесконечному числу повторений (с вероятностью нуль). Гленн рассматривает также другой тип турнира с выбыванием введенный Морис [104], в котором предполагается лучший выход — скорее тремя играми, чем одной, определять победителя каждой встречи, что требует всего от шести до десяти игр. В конце концов, хотя и нельзя исчерпать все разумные возможности, он работает с турниром с вторичным исключением В этом турнире игрок не исключается до проигрыша двух игр. Первый круг такой же, как для обычного олимпийского турнира, но во втором круге в дополнение к встрече двух победителей проводится встреча двух проигравших. В конце этого круга один игрок выбывает из игры, а остаются один двукратный победитель и два игрока, у которых по одному выигрышу и по одному проигрышу Мы обозначим трех уцелевших соответственно. Последние два встречаются в пятой игре и победитель встречи и встречается с в шестой игре. Если выиграет эту игру, он победитель турнира, если он проиграет, два других игрока встречаются в седьмой, решающей игре.

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

Эти выводы верны для всех значений (сравните упражнение 6.4). Для принятия решения о выборе или необходимо определить какую-нибудь подходящую в данной ситуации функцию цены, в которой «цена» от выбора худшего игрока должна сравниваться с

ценой проведения игры. Конечно, турниры с сильно отличающимися размерами также могут сравниваться с помощью функции цены, однако это целесообразно, только если есть веские основания для выбора какой-либо функции цены.

Другие проблемы турниров

Много лет тому назад Льюис Кэррол (см., например, издание 1947 г.) выразил неудовлетворение использованием в теннисе турниров с выбыванием из-за очевидной ненадежности при определении игрока, занявшего второе место. Кэррол полагал, что соревнующиеся должны быть точно расположены в порядке их силы и что игрок будет всегда побеждать более слабого соперника. Случайным элементом в турнире будет лишь жеребьевка. При этих предположениях ясно, что лучший игрок должен победить наверняка. Средство против возможной несправедливости по отношению к игроку на втором месте Кэррол дает в виде подробного предписания, существенной чертой которого является то, что игрок исключается из турнира лишь тогда, когда вполне ясно, что два других игрока превосходят его. Это может быть прямой победой над ним этих игроков (как в турнире с вторичным исключением) или непрямой, когда игрок терпит первое поражение от соперника, который однажды проиграл. Скорее, хотя это и будет менее спортивным, стоит организовать турнир с выбыванием между игроками, проигравшими чемпиону. Для того чтобы показать, сколько матчей требуется для этой процедуры, рассмотрим обычный турнир с выбыванием с игроками, где, вообще говоря,

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

Следовательно, чемпион может побеждать столько же, сколько его соперников в дальнейших матчах, где определяется игрок, занявший второе место, участвуя всего в

где квадратные скобки означают целую часть числа, как и далее, до конца этого раздела. Этот результат дан Штейнгаузом [130], который также рассматривал задачу обеспечения полного ранжирования за минимальное число матчей (единичных парных сравнений). Он предполагает, что множество игроков уже было ранжировано и что мы хотим найти место для нового игрока А. Сначала выделим медианного игрока т. е. такого, что в ранжировке одинаковое число игроков имеют ранг меньше и больше, чем у него; если же число игроков четное, то

двух игроков в середине ранжировки мы называем медианными. Затем мы устроим матч Если мы проведем матч с медианным среди игроков, превосходящих если проведем матч А с медианным игроком нижней половины и т. д., пока не будет определено место А в ранжировке. Так, для ранжирования 3 игроков надо 3 матча (и два матча могут это обеспечить, но не так хорошо), четыре игрока можно проранжировать за 5 матчей, пять — за 8 матчей и т. д. Размещение игрока в ранжировке требует матчей. Следовательно, общая формула для числа матчей при ранжировании игроков

Мы запишем в виде

так что

Тогда

Это не самый короткий из возможных путей, что было показано Фордом и Джонсоном [49]. Их оригинальная улучшенная процедура, оптимальность которой до сих пор открытый вопрос, состоит в следующем.

Предположим, или Тогда

а) разделим на пары игроков и пусть пары играют в первом круге, оставляя одного игрока, если нечетное;

б) распространение данного метода на игроков дает полное ранжирование этих победителей первого круга;

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

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

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

Теперь мы начнем с введения точки 1 в цепь После того как это будет сделано, главная цепь под точкой 2 будет состоять из возможно, точки 1; это введение можно выполнить за два сравнения.

Теперь мы обратимся к цепи длиной и заметим, что точка 3 расположена так высоко, как только возможно, главная цепь под 3 состоит из и 2 и т. д.

Рис. 6.2. Из работы [49], с разрешения авторов и редактора «American Mathematical Monthly»

Это образует методику ранжирования, требующую сравнений, где дается следующими рекуррентными соотношениями:

при число сравнений, требующееся для введения игроков в цепь длиной и

где

Таблица 6.1 (см. скан) (из [49], с разрешения автора и издателя)

В табл. 6.1 приведены значения для 13. Последняя строка дает нижнюю границу, которую Форд и Джонсон получили из теории информации. Каждое соединение в пару не может дать сведений более чем о разделении оставшихся возможностей на два взаимно дополняющих множества; в результате сравнения выделяется то или иное из этих множеств. Очевидные исходные возможностей делятся пополам; это лучшее, что можно сделать на каждом шаге, поэтому мы приходим к формуле

Упражнения

(см. скан)

(см. скан)