Given once, 2025
How Many Matches Does It Take to Find a Champion?
How many races does it take to find the fastest horses, and who even counts as a champion?
An intermediate seminar, for graduate students and up.
Abstract
As published by IIT Delhi, April 2025Suppose there are n horses and we have a track with k lanes. If we pick k horses to run a race, a linear ordering is established among the chosen horses, based only on the finishing order (race time is not considered). How many races do we need to organize to determine the best two horses? How many races are necessary to reveal the full ranking?
To address this question, we might assume that there is an overall linear ordering among all horses and that the outcomes of the races are always consistent with this global linear order. However, this may not be true in real-world tournaments: actual outcomes may deviate from our estimate of the global order. In this talk, we will discuss some developments around questions of determining the “top k” elements in the general setting of tournaments and the special situation when we are promised that comparisons are consistent with an underlying linear order.
The results presented are drawn from the following papers:
Variations on the Tournament Problem
Fabrizio Luccio, Linda Pagli, Nicola Santoro
FUN 2024
Query Complexity of Tournament Solutions
Arnab Maiti, Palash Dey
TCS 2024
Source: homecse.iitd.ac.in.