Nearly 20 years after publishing his paper “The element of surprise in timed games,” UC Santa Cruz Professor of Computer Science and Engineering Luca de Alfaro received a surprise himself: he won the 2022 CONCUR test of time award.
This award, presented at the annual International Conference on Concurrency Theory, recognizes important achievements in concurrency theory, which has to do with the timing of programs, algorithms, or problems.
The paper studies the effect of time and delay between moves in a two-person game. Prior to this work, game theory focused on the effect moves have on a game, independently from precisely when they are played. De Alfaro and his co-authors Marco Faella, Thomas Henzinger, Rupak Majumdar, and Mariëlle Stoelinga found that if players can choose not only which move to play, but also precisely when to play it, they can take each other by surprise. This “surprise” effect can be used to win games that could not be won if moves are played at predetermined times.
“One of the beautiful results of this paper is that it determines that the element of surprise is important,” de Alfaro said. “Time really adds a new dimension to the types of strategies you can use to play a game.”
The paper presents a model of timed games, laying out a complex method for computing their solutions and thus instructing on how to win. This model is constrained by what can be considered a physically meaningful strategy, as the amount of time a player takes to move must be physically achievable.
While the paper describes a generalized game theory approach, the results are applicable to many real-world situations such as commerce systems, driving, and more. Significantly, these results are influential for the subfield of computer science that deals with understanding system behavior and how pieces of systems interact.
“Timed games are important because they represent many control problems,” de Alfaro said. “This is important for control theory, the design of embedded software that controls systems, and has indications for understanding the interactions between systems that can often be modeled as a game.”
De Alfaro’s foundational work has been cited in nearly 200 papers on system interaction, modeling of time systems, and the design of controls. De Alfaro called this project a “particularly beautiful collaboration” between the co-authors, who are from several countries around the world and two of which were visiting him in Santa Cruz at the time of the research. He noted that all of the co-authors have gone on to very successful careers in academia.
