Guy Avni: Decision making using graph games

I will survey two projects that study the theoretical properties of graph games and their applications. The first part of the talk focuses on the controller-design problem. Since in order to deploy a controller in practice, it is critical to guarantee both performance and correctness, the solution uses a combination of formal methods and machine-learning techniques. Specifically, we combine deep reinforcement learning with formal methods for graph games, towards a design of controllers that achieve high-quality performance and are provably correct. The second part of the talk focuses on infinite-duration “bidding” games, which combine graph games with auctions and can model stateful and ongoing auctions. I will describe the intriguing mathematical properties of bidding games with first-price auctions, i.e., in each turn both players simultaneously submit bids and the higher bidder makes the next move. Specifically, I will show their equivalence with a stochastic process called “random-turn games”, and how changes to the auction mechanism leads to different equivalences. I will conclude by mapping directions for future work and survey the preliminary results we obtained in these directions.