Optimal strategy found for five expert prediction game in finite time
The finite-horizon five-expert prediction problem
Computer Science and Game TheoryMachine Learning
Summary
This paper solves a puzzle in decision making where you have five experts giving advice over a limited time. The authors found the best way for an opponent to act to make predictions hardest to get right. They used advanced math tools and computer checks to prove their solution. This work links two complex problems and provides exact formulas to guide decisions.
What this means in practice
- •For financial modelers: Use exact optimal adversarial strategies to benchmark prediction algorithms under finite time constraints in investment decisions.
- •For risk management teams: Incorporate rigorously proven bounds on prediction errors from multiple expert advice in short-term risk assessments.
A theory result. No direct application yet.
Authors
Jeff Calder, Nadejda Drenska
Abstract
We give an explicit solution to the five expert prediction with expert advice partial differential equation (PDE) in the finite-time horizon setting. The solution formula establishes that the adversary's rank strategy $(1,0,1,0,0)$ is globally optimal, and the COMB strategy $(1,0,1,0,1)$ is optimal exactly on the set where $x_1=x_2$ and $x_3=x_4$. The formula is derived from the solution of the geometric-stopping problem given in our companion paper through the transform principle of Bayraktar, Ekren and Zhang, which links the two problems by a Laplace transform. Inverting the transform term by term expresses the solution through a series of Gaussian and complementary error function kernels. The optimality of $(1,0,1,0,0)$ is reduced to the signs of $41$ one-variable Gaussian series, which are certified with computer assistance by Poisson summation, first-mode domination and interval arithmetic on $1616$ rational cells. The proofs of our main theorems, certificates included, are also formalized in the Lean proof assistant.