So a Puzzle Walks into a Bar...
These contests have two features that make them interesting from this blog's perspective. First, there's apparently a company that sends its quizmasters all over town, and presumably supplies them with fun questions. So let's assume that the questions are drawn from some fixed distribution D, unknown in advance.
Second, these are team games. So now--let's say you've got n trivia-loving friends, and you're trying to form a team of k < n of them to maximize your chances of winning. k might grow with n.
To help you choose, you can take your friends out for drinks and watch the contests for a few weeks or months before deciding on your team. You can record who out of your friends answered which questions correctly as they watched. (For simplicity, let's say that if someone answers correctly, they know they're right, and if they don't know the answer they keep their mouths shut.) But you can only afford poly(n) of these expensive outings before you decide your team and start trying to rake in gift certificates or stuffed bears or whatever.
So--what are your prospects in general for determining the best team?
(i.e., we're looking for algorithms that, for any group of friends and any D, perform well with high probability.)
If one has only been exposed to computational problems in which all the necessary information is presented as a single input, a problem like this can be disconcerting. There appears to be both a computational and a statistical puzzle to solve, simultaneously. (If the computational aspect doesn't seem challenging, keep in mind: your friends' various knowledge-bases may be similar, disjoint, or anywhere crazily in between...)
My challenge to readers is to think about how this problem fits into algorithms/complexity theory. Not necessarily to solve it--I've found it touches on published research, and I will give references in a future post--but to relate it to what you've seen before. I'm hoping this might be a good warm-up to thinking about ideas from computational learning theory which I also have been wanting to exposit.
I should note that even slight tweaks on this problem could lead to questions I haven't thought about, but which I encourage others to (e.g., what if player ability is affected by drinking?).