Computational Information Games

We show how the discovery/design of scalable numerical solvers can be addressed/automated as a Uncertainty Quantification/Decision Theory problem by reformulating the process of computing with partial information and limited resources as that of playing underlying hierarchies of adversarial information games. As an illustration we show how the application of the proposed approach to the resolution of elliptic PDEs with rough ($L^\infty$) coefficients leads to a near-linear complexity multigrid/multiresolution method with rigorous a-priori accuracy and performance estimates. In this application, the numerical solver is discovered by identifying optimal strategies for gambling on the value of the solution of the PDE based on hierarchies of nested measurements of its solution or source term.