2025/03/11 by Vincent Liu, Chris Manzie, Liu, Vincent +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #49L25 #49N70 #93B03 #93C05 #FOS: Mathematics #Game Theory and Voting Systems #Optimization and Control (math.OC) #Optimization and Variational Analysis #Simulation Techniques and Applications
paper · pdf · doi:10.48550/arxiv.2503.08310
openalex publication_date 2025/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper develops an algorithm for upper- and lower-bounding the value function for a class of linear time-varying games subject to convex control sets. In particular, a two-player zero-sum differential game is considered where the respective players aim to minimise and maximise a convex terminal state cost. A collection of solutions of a single-player dynamical system subject to a trimmed control set is used to characterise a viscosity supersolution of a Hamilton-Jacobi (HJ) equation, which in turn yields an upper bound for the value function. Analogously, a collection of hyperplanes is used to characterise a viscosity subsolution of the HJ equation, which yields a lower bound. The computational complexity and memory requirement of the proposed algorithm scales with the number of solutions and hyperplanes that characterise the bounds, which is not explicitly tied to the number of system states. Thus, the algorithm is tractable for systems of moderately high dimension whilst preserving rigorous guarantees for optimal control and differential game applications.