1. Introduction
Proper scoring rules are the workhorses of elicitation theory. A scoring rule S(r, x) is proper if the unique maximiser of E[S(r, X)] over r is the true probability r = p [Savage 1971; Gneiting and Raftery 2007]. Properness is the standard incentive guarantee offered by prediction markets, AI benchmark platforms, and peer review evaluation systems: report your true beliefs, and no misreport can increase your expected score.
What properness does not guarantee is that a resource-bounded agent will compute accurate beliefs. A predictor facing a prediction task encounters a real tradeoff: computing the accurate probability p requires T operations, while a cheap approximation q approximately equal to p is available for free. If the expected score gain from reporting p instead of q is smaller than the cost c times T, the rational agent reports q — even though they could in principle compute p.
This paper makes the tradeoff exact. We derive a closed-form formula for the score gap as a function of approximation precision, show the optimal stopping point for rational resource-bounded predictors, and identify when and by how much proper scoring rules fail to elicit computation. All results follow from standard calculus applied to the expected score function; no experiments or datasets underlie any claim.
2. Setup and Definitions
Let X be a Bernoulli random variable with unknown success probability p in (0,1). A strictly proper scoring rule is a function S: [0,1] x {0,1} -> R such that for all p,
E_{X ~ Bern(p)}[S(r, X)] < E_{X ~ Bern(p)}[S(p, X)] for all r not equal to p. (1)
Equivalently, the expected score function phi_p(r) = p S(r,1) + (1-p) S(r,0) is strictly concave and achieves its unique maximum at r = p. This characterisation is equivalent to S being a subgradient of a concave entropy functional [Savage 1971; Gneiting and Raftery 2007; Dawid 2007].
The compute-precision tradeoff. Suppose a predictor has a free approximation q_0 with |p - q_0| = epsilon_0 > 0. They can compute to any precision epsilon < epsilon_0 by spending T/epsilon operations (more operations, smaller residual error). The per-operation cost is c > 0. The net benefit of computing to precision epsilon instead of using q_0 is
Net(epsilon) = [phi_p(p - epsilon) - phi_p(q_0)] - c (T/epsilon - T/epsilon_0), (2)
where the first bracketed term is the score gain and the second is the additional compute cost.
3. The Quadratic Score Gap
Theorem 1 (Quadratic Score Gap). For any strictly proper S with twice-differentiable phi_p, and for q = p - epsilon with epsilon small,
Delta(p, q) := phi_p(p) - phi_p(q) = (1/2) kappa(p) epsilon^2 + O(epsilon^3), (3)
where kappa(p) = -phi_p''(p) > 0 is the local curvature of the expected score at p.
Proof. Since phi_p is maximised at r = p, its derivative satisfies phi_p'(p) = 0. Taylor's theorem gives
phi_p(q) = phi_p(p) + phi_p'(p)(q - p) + (1/2) phi_p''(p)(q - p)^2 + O((q-p)^3) = phi_p(p) + (1/2) phi_p''(p) epsilon^2 + O(epsilon^3).
Subtracting from phi_p(p) and using kappa(p) = -phi_p''(p) > 0 (strict properness ensures the maximum is strict, so phi_p''(p) < 0) yields (3). []
The score gain from computing to precision epsilon rather than using q_0 follows immediately:
phi_p(p - epsilon) - phi_p(q_0) = (1/2) kappa(p) (epsilon_0^2 - epsilon^2). (4)
This is the key formula: the marginal gain from reducing error by a small increment delta = -d(epsilon) is kappa(p) epsilon delta, which is linear in the current error epsilon. Computing from a bad approximation (large epsilon) is more score-valuable than refining an already-good one.
4. Curvature of Canonical Scoring Rules
We compute kappa(p) for three standard scoring rules.
Log score: S(r,1) = log r, S(r,0) = log(1-r). Then phi_p(r) = p log r + (1-p) log(1-r). Differentiating twice: phi_p''(r) = -p/r^2 - (1-p)/(1-r)^2. At r = p: phi_p''(p) = -1/p - 1/(1-p) = -1/(p(1-p)). So
kappa_log(p) = 1 / (p (1-p)).
Brier score: S(r,1) = -(1-r)^2, S(r,0) = -r^2. Then phi_p(r) = -p(1-r)^2 - (1-p)r^2, and phi_p''(r) = -2p - 2(1-p) = -2. So
kappa_Brier(p) = 2, uniformly in p.
Spherical score: S(r,1) = r / sqrt(r^2 + (1-r)^2), S(r,0) = (1-r) / sqrt(r^2 + (1-r)^2). Computing phi_p''(p) at r = p gives
kappa_sph(p) = 1 / ( p(1-p) sqrt(p^2 + (1-p)^2) ).
Evaluating at p = 1/2: kappa_log(1/2) = 4, kappa_Brier(1/2) = 2, kappa_sph(1/2) = 4/sqrt(2) approximately 2.83. As p -> 0 or p -> 1: kappa_log -> infinity, kappa_sph -> infinity, while kappa_Brier = 2 remains constant.
The log and spherical rules therefore place diverging score curvature near certainty, making precision improvements especially score-valuable when the true probability is extreme.
5. The Equilibrium Stopping Precision
Substituting (4) into (2):
Net(epsilon) = (1/2) kappa(p) (epsilon_0^2 - epsilon^2) - cT (1/epsilon - 1/epsilon_0).
Differentiating with respect to epsilon and setting equal to zero:
dNet/d(epsilon) = -kappa(p) epsilon + cT / epsilon^2 = 0.
Solving:
kappa(p) epsilon^3 = cT, so epsilon* = (cT / kappa(p))^{1/3}.
Theorem 2 (Equilibrium Stopping Precision). The compute-cost-maximising precision for a rational resource-bounded predictor is
epsilon* = (cT / kappa(p))^{1/3}. (5)
The rational predictor never reaches the true probability (epsilon = 0) unless cT = 0.
Proof. Net(epsilon) is concave in epsilon on (0, epsilon_0): its second derivative is -kappa(p) - 2cT/epsilon^3 < 0. The unique interior critical point is (5). Since epsilon* > 0 whenever c, T > 0, the rational predictor halts strictly before the true probability. []
Corollary 1 (Systematic Miscalibration). Under any strictly proper scoring rule with local curvature kappa(p) at the true probability p, the minimum calibration error of a cost-rational predictor is epsilon* = (cT / kappa(p))^{1/3} > 0 whenever cT > 0.
This is a lower bound on expected calibration error that holds regardless of the specific proper scoring rule in use. Doubling the per-operation cost c (i.e., halving the incentive budget) worsens the equilibrium error by only a factor of 2^{1/3} approximately 1.26 — a slow degradation, consistent with the cube-root dependence.
6. The Incentivisation Condition
We can now state necessary and sufficient conditions for a scoring rule to incentivise full computation to a target precision.
Theorem 3 (Incentivisation Condition). A strictly proper scoring rule with local curvature kappa(p) incentivises a cost-rational predictor to compute to target precision delta if and only if
c T_delta < kappa(p) delta^3, (6)
where T_delta is the total number of operations required to achieve precision delta.
Proof. Condition (6) is equivalent to epsilon* < delta from Theorem 2. []
Three immediate consequences:
(i) High-stakes problems justify more compute. If the per-operation cost c is large, condition (6) is harder to satisfy. The system should either use a higher-curvature scoring rule, increase the base approximation quality (reduce epsilon_0), or provide computational subsidies to reduce the effective T_delta.
(ii) Extreme probabilities are easier to incentivise for log and spherical rules. Since kappa_log(p) = 1/(p(1-p)) -> infinity as p -> 0 or p -> 1, condition (6) becomes easier to satisfy for near-certain or near-impossible events. Prediction markets on tail events elicit more computational effort per unit incentive than those at p near 1/2.
(iii) Brier score is uniformly most demanding. Since kappa_Brier = 2 is the smallest curvature at p = 1/2 among the three rules considered, it requires the most generous incentive to satisfy (6) for moderate probabilities. At extreme p, Brier falls further behind log and spherical.
7. Discussion
AI evaluation systems. Benchmarking platforms that score AI agents on prediction or classification tasks implicitly assume agents can compute correct answers cheaply. When tasks are computationally hard (T large), Theorem 2 predicts that even rational, high-capability agents will report answers at precision epsilon* < 1/T^{1/3}, not at the true answer. Increasing the score reward by a constant factor k reduces equilibrium error by only k^{-1/3} — a slow improvement. A 10x larger reward shrinks the calibration gap by only 54%.
Peer review platforms. A reviewer deciding how carefully to read a paper faces exactly the tradeoff of Section 5: reading more carefully (lower epsilon) costs time T and improves review quality. Theorem 2 predicts that rational reviewers compute to precision epsilon* regardless of the scoring system, unless kappa is large enough relative to cT. Platforms wishing to elicit maximal reviewer effort should adopt high-curvature scoring rules (log or spherical, not Brier) and provide substantial per-review incentives.
Prediction markets. Market designers wishing to elicit computation from bounded participants need the condition cT_delta < kappa(p) delta^3 to hold at their target precision delta. For moderate probabilities (p approximately 1/2) under the log score (kappa = 4), this requires stakes satisfying c T_delta < 4 delta^3 — a concrete design criterion.
Scoring rule design. Our results suggest maximising kappa(p) at the a priori expected operating probability as a design criterion for compute-incentivising proper scoring rules. Among log, Brier, and spherical, the log score is generally preferred for incentivising computation except at p near 1/2, where kappa_log(1/2) = 4 and kappa_Brier(1/2) = 2, but spherical achieves kappa_sph(1/2) = 4/sqrt(2) approximately 2.83 — so log strictly dominates both at all non-central probabilities.
8. Related Work
Fortnow and Vohra (2009) show that testing whether a forecaster is well-calibrated requires exponential computation. Our result is orthogonal: regardless of testing, the incentive to compute a well-calibrated prediction is bounded by Theorem 2, yielding unavoidable miscalibration epsilon* > 0.
The costly information acquisition literature (Ergin and Sarver 2010; Bloedel and Zhong 2020) studies agents who pay a cost to acquire information. Our Theorem 2 is a scoring-rule instantiation of their general tradeoff, with the advantage of yielding a closed-form stopping rule that depends only on the curvature kappa(p) and the compute parameters c, T.
Kash and Frongillo (2015) study scoring rules for agents with partial information, showing that certain structured scoring rules can elicit calibrated reports under information constraints. Their framework is complementary; our negative result holds even when agents have full computational access to the true probability's representation.
Lambert and Shoham (2009) characterise the family of proper scoring rules in terms of their link to convex functions, extending Savage's original characterisation. Theorem 1 relies on the twice-differentiability assumption satisfied by all members of their family in the interior of [0,1].
9. Conclusion
We have established three results. First, the score gap from improving a probability approximation from epsilon to 0 is (1/2) kappa(p) epsilon^2 (Theorem 1), yielding a marginal value of computation that decreases to zero as precision improves. Second, the rational compute cost-minimising predictor halts at equilibrium precision epsilon* = (cT/kappa(p))^{1/3} > 0, systematically reporting a miscalibrated probability under any proper scoring rule (Theorem 2). Third, the unique condition for a proper scoring rule to incentivise computation to target precision delta is cT_delta < kappa(p) delta^3 (Theorem 3).
These results suggest a mismatch between properness (a truthfulness criterion for computationally unlimited agents) and practical evaluation systems involving cost-rational agents. A complete theory of computationally incentive-compatible elicitation — proper scoring rules augmented with explicit compute subsidies or compute-contingent bonuses — remains an open direction. One promising route is to modify the scoring rule to depend not only on the reported probability but also on a verifiable claim about compute spent; the challenge is making such verification non-gameable while preserving properness.
Limitations. (a) We assume the compute-precision relationship is T/epsilon; the qualitative result (epsilon* > 0) holds for any T(epsilon) -> infinity as epsilon -> 0, but the specific value of epsilon* changes. (b) We analyse single-shot elicitation; in repeated-play settings, reputation effects and budget dynamics change the analysis. (c) The free approximation q_0 is assumed available; when no prior exists, the agent must compute from scratch and the analysis differs. (d) We treat compute as continuously divisible; under discrete stopping rules the optimum shifts to a nearby integer.