I've come across a practical problem in discrete mathematics, and I suspect that some clever mind knows a better solution than brute force.
Imagine that we are hosting a competition in which each of the $n$ contestants enters a piece of work. However, the contest has no judges, so the contestants agree on a procedure where each of them "draws" $k$ contest works to judge. Therefore, each work is judged by $k$ raters. How the judging is done and handled is not important right now. What we want to do is to divide the works among the raters (instead of a simple random draw) so that the following applies:
- No rater evaluates their own work.
- There is no duplicity in the set of works a rater receives for evaluation.
- If we take any two evaluators, then there will be overlap in the $k$-tuples of works they are given to evaluate in the smallest possible number of elements (i.e., ideally one or none). A specific example: if rater A rates works X, Y, and Z, and rater B also rates work X, then (preferably) rater B does not rate either Y or Z.
- The resulting network of raters and their works is maximally interconnected. What I mean is this: divide the evaluators into two groups, and denote by $m$ the number of such raters in the first group who evaluate at least one work by someone in the second group. We want to find a solution such that there is no such division into two groups where the number $m$ is zero. Ideally we want this number to be as far away from zero as possible, no matter how the two groups are chosen. (This condition is probably written a bit clumsily, but what I mean is that if $m$ could reach 0, it implies that the whole problem can break down into two completely independent systems. And we don't want that. We want as much interconnection as possible.)
A few practical notes:
- Suppose $n$ is several times larger than $k$. For example, $n=100$ and $k=5$.
- So far I've been solving the problem by setting some minimization criterion and running a genetic algorithm on it. But I believe there is a procedure that finds a suitable arrangement instantly.
My question is: do you know an algorithm that finds a solution that is as close as possible to my requirements?