2009 Poster Sessions : On the Seeding Problem in Knockout Tournaments

Student Name : Thuc Vu
Advisor : Yoav Shoham
Research Areas: Artificial Intelligence
Tournaments constitute a very common social institution. Their best known use is in sporting events, which attract millions of viewers and billions of dollars annually. The question of how to seed players in an n-player knockout tournament, one of the most popular tournament formats, turns out to be surprisingly subtle. It depends, among other things, on (a) the model of the players, (b) the quantity being optimized, and (c) whether one considers only ordinal solutions or also cardinal ones. Past results have been limited to tournaments of size 4 and 8, under the assumption that the only information available to the tournament is ordinal (the relative ranking of the players), and for a particular objective function: maximizing predictive power.

We dramatically extend these results by considering tournaments of size up to 128, different player models, ordinal as well as cardinal solutions, and two additional objective functions. Some of our results are theoretical and some experimental. The latter rely on an innovative, provably correct upper bound which experiments show to be fairly tight.

Thuc Vu is currently a graduate student at Stanford University, working towards his Ph.D. degree in Computer Science. He received his B.S. degree with Honors in Computer Science with a minor in Mathematical Science from Carnegie Mellon University in 2004. He is a member of the Phi Beta Kappa Society, and has received several national and international honors including Computing Research Association Outstanding Undergraduate Awards. His research interests include Game Theory, Multi-agent Systems, and Machine Learning.