Game-Theoretic Question Selection for Tests

Yuqian Li, Vincent Conitzer

TL;DR

This paper tackles the challenge of designing effective tests when question leaks are inevitable. They model this as a game between a tester who strategically selects questions and a test-taker who can memorize some answers. The authors develop game-theoretic approaches to find optimal question selection strategies that maximize the tester's ability to assess true knowledge, even with imperfect confidentiality.

What Problem Does This Paper Address?

The traditional assumption in test design is that questions are kept secret until the test. However, for large-scale, asynchronous tests like TOEFL or MOOC exams, this is often impossible. When questions become known, test-takers can memorize answers, potentially masking their true understanding. This paper addresses how to design tests that remain informative and fair even when this confidentiality is compromised. The core problem is to find a question selection strategy that balances the tester's goal of accurately assessing ability with the test-taker's goal of maximizing their score by memorizing answers.

Methods

The authors frame the problem as a Bayesian Stackelberg game. The tester is the leader, committing to a mixed strategy (a probability distribution over question sets), and the test-taker is the follower, best-responding by choosing which questions to memorize. A key contribution is transforming this into a Bayesian zero-sum game, which simplifies computation. They then leverage linear programming (LP) to find optimal strategies.

For scored tests (where questions have point values), they develop a polynomial-time algorithm using a separation oracle for an LP. For binary tests (pass/fail), the problem is generally harder. They provide an exponential-size LP formulation and prove NP-hardness results for general cases. However, they offer efficient algorithms for specific scenarios:

  • Single-question tests: Solved in polynomial time using LP or network flow.
  • Constant memory size: The problem is in NP.
  • Constant test size: The problem is coNP-hard.

Datasets

Not discussed in the paper. The authors generate synthetic test game instances for their experiments.

Key Insights and Ideas

  • Confidentiality is not everything: Even with leaked questions, strategic question selection can still yield informative tests. The key is to randomize intelligently.
  • Game theory as a solution: Modeling the interaction between tester and test-taker as a game provides a powerful framework for finding optimal strategies.
  • Stackelberg vs. Nash: While a Stackelberg model (tester commits first) is natural, they show its equivalence to Nash equilibrium and zero-sum game solutions under certain conditions, simplifying computation.
  • Binary tests are hard: The pass/fail nature of binary tests, combined with memorization, leads to significant computational complexity (NP-hardness).
  • Structure matters: The performance of optimal strategies over random ones is significantly higher when question difficulty has structure (e.g., questions are sorted by difficulty), suggesting real-world test design could benefit greatly from considering such correlations.

Key Results

  • Scored tests: Optimal strategies can be computed in polynomial time.
  • Binary tests: Generally NP-hard, but efficient algorithms exist for single-question tests.
  • Experimental findings: Optimal strategies significantly outperform uniform random selection, especially when question difficulty is structured. The performance increase can be substantial, indicating the practical value of game-theoretic approaches.
  • Scalability: While general LPs can be slow, specialized algorithms and network flow approaches show promise for specific cases.

Limitations and Future Work

  • Computational complexity: General binary test problems remain NP-hard, limiting scalability for large, complex scenarios.
  • Data acquisition: The current approach assumes statistical data on test-taker types is available. Future work could focus on developing methods to obtain this information, potentially through online learning as test-takers interact with the system.
  • Structured test cases: The paper explores some structured cases (e.g., sorted difficulty), but real-world tests often have more complex correlations in question difficulty that could be further investigated.
  • Online learning: The authors suggest a more integrated online-learning approach where the testing strategy adapts dynamically as more test-takers are evaluated.

Summary updated

Abstract

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, 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, as offered for example by Coursera, Udacity, and edX). Specifically, the test result may not reflect the true ability of a test taker if questions are leaked beforehand. 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 to let appear on the test. We model this as a Stackelberg game, where the tester commits to a mixed strategy and the follower responds. Informally, the goal of the tester is to best reveal the true ability of a test taker, while the test taker tries to maximize the test result (pass probability or score). We provide an exponential-size linear program formulation that computes the optimal test strategy, prove several NP-hardness results on computing optimal test strategies in general, and give efficient algorithms for special cases (scored tests and single-question tests). Experiments are also provided for those proposed algorithms to show their scalability and the increase of the tester's utility relative to that of the uniform-at-random strategy. The increase is quite significant when questions have some correlation---for example, when a test taker who can solve a harder question can always solve easier questions.
BibTeX
@article{li2017game,
  author = {Yuqian Li and Vincent Conitzer},
  title = {{Game-Theoretic Question Selection for Tests}},
  journal = {J. Artif. Intell. Res.},
  year = {2017},
  url = {https://openreview.net/forum?id=7W5kkkOLsj},
}
Figure