How Many Judges Does it Take to Screw in a Light Bulb?

An optimized solution to the problem of judging the best papers in a contest

Elizabeth Herman

May 2004

In this thesis we study an optimal solution to the problem of scoring P papers with the help of J judges to find W of the best 2W papers as quickly as possible. We will model the problem using graph theory where the vertices of the graph represent the papers, and the edges of the graph represent the relationship between two papers. We determine the direction of the edge to mean that if vertex v_i has an edge directed toward vertex v_j, then the paper represented by v_i is better than paper represented by v_j. We then use an algorithm to find W of the best 2W papers using this graph. With the use of a sorting algorithm, we can use the vertices and edges of the graph to determine when W of the best 2W papers have been found. Implementing this algorithm in a program, we show how the judges will determine the winners of a randomly selected ordering of papers.