Co-author Mariëlle Stoelinga worked with de Alfaro during her postdoctoral research at UCSC.
Nearly 20 years after publishing his paper “The Factor of Surprise in the Time Game,” UC Santa Cruz Professor of Engineering and Computer Science Luca de Alfaro received a surprise: he won Okay 2022 CONCUR time prize test.
This award, presented at the Annual International Conference on Concurrency Theory, recognizes significant achievements in the theory of concurrency, related to the timing of programs, algorithms or problems.
Paper study the effect of time and lag between moves in a two-player game. Prior to this work, game theory focused on movement effects present in a game, independent of exactly when they were played. De Alfaro and his co-authors Marco Faella, Thomas Henzinger, Rupak Majumdar and Mariëlle Stoelinga found that if a player could not only choose which motion to play, but also when To play it, they can take each other to surprise. This “surprise” effect can be used to win unwinnable games if moves are played at predetermined times.
“One of the great results of this paper is that it establishes that the element of surprise is important,” says de Alfaro. “Time really adds a new dimension to the kinds of strategies you can use to play a game.”
The paper presents a timed game model, which sets out a complex method for calculating their solutions and thus instructs how to win. This model is limited by what could be considered a physically meaningful strategy, given the amount of time a player has to physically make a move.
While the paper describes a general game theory approach, the results are applicable to many real-world situations such as trading systems, driving, etc. Notably, these results have an impact influence to the field of computer science concerned with understanding the behavior of systems and how parts of the system interact.
“Timed games are important because they represent a lot of control problems,” said De Alfaro. “This is very important for control theory, the design of embedded software that controls systems and has instructions for understanding 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, temporal system modeling, and design of controls. De Alfaro called the project a “particularly nice collaboration” between co-authors from several countries around the world, two of whom were visiting him in Santa Cruz at the time of the study. He notes that all of the co-authors have had very successful careers in the academic field.
