Game-Theoretic Question Selection for Tests / 254
Yuqian Li, Vincent Conitzer

Conventionally, the questions on a test are assumed to be kept secret from test takers until the test.  However, for tests that are taken on a large scale, particularly asynchronously, this is very hard to achieve. For example, example TOEFL iBT and driver's license test questions are easily found online.  This also appears likely to become an issue for Massive Open Online Courses (MOOCs). In this paper, we take the loss of confidentiality as a fact.  Even so, not all hope is lost as the test taker can memorize only a limited set of questions' answers, and the tester can randomize which questions appear on the test.  We model this as a Stackelberg game, where the tester commits to a mixed strategy and the follower responds.  We provide an exponential-size linear program formulation, prove several NP-hardness results, and give efficient algorithms for special cases.