Skip to main content

Game-theoretic question selection for tests

Publication ,  Conference
Li, Y; Conitzer, V
Published in: Journal of Artificial Intelligence Research
May 1, 2017

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.

Duke Scholars

Published In

Journal of Artificial Intelligence Research

DOI

EISSN

1076-9757

Publication Date

May 1, 2017

Volume

59

Start / End Page

437 / 462

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 4611 Machine learning
  • 4603 Computer vision and multimedia computation
  • 4602 Artificial intelligence
  • 1702 Cognitive Sciences
  • 0801 Artificial Intelligence and Image Processing
  • 0102 Applied Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Li, Y., & Conitzer, V. (2017). Game-theoretic question selection for tests. In Journal of Artificial Intelligence Research (Vol. 59, pp. 437–462). https://doi.org/10.1613/jair.5413
Li, Y., and V. Conitzer. “Game-theoretic question selection for tests.” In Journal of Artificial Intelligence Research, 59:437–62, 2017. https://doi.org/10.1613/jair.5413.
Li Y, Conitzer V. Game-theoretic question selection for tests. In: Journal of Artificial Intelligence Research. 2017. p. 437–62.
Li, Y., and V. Conitzer. “Game-theoretic question selection for tests.” Journal of Artificial Intelligence Research, vol. 59, 2017, pp. 437–62. Scopus, doi:10.1613/jair.5413.
Li Y, Conitzer V. Game-theoretic question selection for tests. Journal of Artificial Intelligence Research. 2017. p. 437–462.

Published In

Journal of Artificial Intelligence Research

DOI

EISSN

1076-9757

Publication Date

May 1, 2017

Volume

59

Start / End Page

437 / 462

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 4611 Machine learning
  • 4603 Computer vision and multimedia computation
  • 4602 Artificial intelligence
  • 1702 Cognitive Sciences
  • 0801 Artificial Intelligence and Image Processing
  • 0102 Applied Mathematics