The Query Complexity of Scoring Rules

Proper scoring rules are crucial tools to elicit truthful information from experts. A scoring rule maps X, an expert-provided distribution over the set of all possible states of the world, and ω, a realized state of the world, to a real number representing the expert’s reward for his provided information. To compute this reward, a scoring rule queries the distribution X at various states. The number of these queries is thus a natural measure of the complexity of the scoring rule. We prove that any bounded and strictly proper scoring rule that is deterministic must make a number of queries to its input distribution that is a quarter of the number of states of the world. When the state space is very large, this makes the computation of such scoring rules impractical. We also show a new stochastic scoring rule that is bounded, strictly proper, and which only makes two queries to its input distribution. Thus, using randomness allows us to have significant savings when computing scoring rules.