Thu 20 Mar 14:30: A Covering Pursuit Game
In the `Covering’ game on a graph, a robber and a set of cops play alternately, with the cops each moving to a vertex at distance at most 1 from their current vertex and the robber moving to a vertex at distance at most 2 from his current vertex. The cops win if, after every one of their moves, there is always a cop at the same vertex as the robber. How few cops are needed? We investigate this problem for the two-dimensional grid. There are applications to the game of `Catching a Fast Robber’, and our work answers questions of Bollobas and Leader and of Balister, Bollobas, Narayanan and Shaw.
- Speaker: Ben Gillott (Cambridge)
- Thursday 20 March 2025, 14:30-15:30
- Venue: MR12.
- Series: Combinatorics Seminar; organiser: ibl10.
Thu 20 Mar 14:30: A Covering Pursuit Game
In the `Covering’ game on a graph, a robber and a set of cops play alternately, with the cops each moving to a vertex at distance at most 1 from their current vertex and the robber moving to a vertex at distance at most 2 from his current vertex. The cops win if, after every one of their moves, there is always a cop at the same vertex as the robber. How few cops are needed? We investigate this problem for the two-dimensional grid. There are applications to the game of `Catching a Fast Robber’, and our work answers questions of Bollobas and Leader and of Balister, Bollobas, Narayanan and Shaw.
- Speaker: Ben Gillott (Cambridge)
- Thursday 20 March 2025, 14:30-15:30
- Venue: MR12.
- Series: Combinatorics Seminar; organiser: ibl10.
Thu 20 Mar 14:30: A Covering Pursuit Game
In the `Covering’ game on a graph, a robber and a set of cops play alternately, with the cops each moving to a vertex at distance at most 1 from their current vertex and the robber moving to a vertex at distance at most 2 from his current vertex. The cops win if, after every one of their moves, there is always a cop at the same vertex as the robber. How few cops are needed? We investigate this problem for the two-dimensional grid. There are applications to the game of `Catching a Fast Robber’, and our work answers questions of Bollobas and Leader and of Balister, Bollobas, Narayanan and Shaw.
- Speaker: Ben Gillott (Cambridge)
- Thursday 20 March 2025, 14:30-15:30
- Venue: MR12.
- Series: Combinatorics Seminar; organiser: ibl10.
Fri 21 Mar 15:30: A Graphical Approach to State Variable Selection in Off-policy Learning
Preprint available at: https://arxiv.org/abs/2501.00854
Sequential decision problems are widely studied across many areas of science. A key challenge when learning policies from historical data – a practice commonly referred to as off-policy learning – is how to ``identify’’ the impact of a policy of interest when the observed data are not randomized. Off-policy learning has mainly been studied in two settings: dynamic treatment regimes (DTRs), where the focus is on controlling confounding in medical problems with short decision horizons, and offline reinforcement learning (RL), where the focus is on dimension reduction in closed systems such as games. The gap between these two well studied settings has limited the wider application of off-policy learning to many real-world problems. Using the theory for causal inference based on acyclic directed mixed graph (ADMGs), we provide a set of graphical identification criteria in general decision processes that encompass both DTRs and MDPs. We discuss how our results relate to the often implicit causal assumptions made in the DTR and RL literatures and further clarify several common misconceptions. Finally, we present a realistic simulation study for the dynamic pricing problem encountered in container logistics, and demonstrate how violations of our graphical criteria can lead to suboptimal policies.
- Speaker: Joakim Blach Andersen (Statistical Laboratory)
- Friday 21 March 2025, 15:30-17:00
- Venue: MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
- Series: Causal Inference Reading Group; organiser: Martina Scauda.
Fri 21 Mar 14:00: Participation of Energy Storage in Electricity Markets: Strategic Withholding Behaviors and Equilibrium
Energy storage is rapidly reshaping electricity markets worldwide, with deployments accelerating in regions like California and Texas. While these resources offer flexibility that can reduce system costs and emissions, recent market data reveals that storage operators often engage in significant strategic withholding behaviors. Such behaviors—driven by complex and sometimes opaque cost structures (including degradation, opportunity, and risk premiums)—can lead to inefficient outcomes, elevated prices, and underutilization of storage during critical peak demand periods.
In this seminar, I will discuss the theoretical and practical implications of storage participation in two-stage electricity markets (day-ahead and real-time). I will present evidence from real-world market data (such as CAISO and ERCOT ) showing that current bidding practices can deviate substantially from the socially optimal outcomes. Informed by equilibrium models and agent-based simulations, we will quantify the resulting price impacts, system costs, and emission trade-offs, highlighting the “price of anarchy” that arises when storage owners operate independently.
Finally, I will introduce potential market design improvements and regulatory measures to mitigate inefficiencies, including state-of-charge-based cost curves and dynamic bid caps. These proposals aim to align private incentives with overall market efficiency—ensuring that storage fully delivers on its promise to bolster renewable integration, reduce emissions, and enhance power system reliability.
The seminar will be held in JDB Seminar Room , Department of Engineering, and online (zoom): https://newnham.zoom.us/j/92544958528?pwd=YS9PcGRnbXBOcStBdStNb3E0SHN1UT09
- Speaker: Bolun Xu, Columbia University
- Friday 21 March 2025, 14:00-15:00
- Venue: JDB Seminar Room, Department of Engineering and online (Zoom).
- Series: CUED Control Group Seminars; organiser: Fulvio Forni.
Thu 20 Mar 14:00: Stochastic Algorithms for Nonconvex Optimization
Nowadays it is quite common to solve optimization problems in 10^9 or more variables. At these levels, it is not practical to use the “true” gradient of the objective function. Instead, a variety of methods are based on using approximate gradients, which are also random; in other words, they are stochastic gradients. Often, only some components of the argument are updated at each iteration, to reduce storage calls. As a result, nowadays optimization algorithms produce stochastic processes, as opposed to sequences of vectors in some Euclidean space. Another issue is that the objective function is not convex.
The seminar will be held in LR3A , Department of Engineering, and online (zoom): https://newnham.zoom.us/j/92544958528?pwd=YS9PcGRnbXBOcStBdStNb3E0SHN1UT09
- Speaker: Mathukumalli Vidyasagar, IIT Hyderabad
- Thursday 20 March 2025, 14:00-15:00
- Venue: LR3A, Department of Engineering and online (Zoom).
- Series: CUED Control Group Seminars; organiser: Fulvio Forni.
Fri 09 May 14:00: A topological proof of the H-colouring dichotomy
A colouring of a graph with $k$ colours is an assignment of colours to vertices so that no edge is monochromatic. As it is well-known colouring with 2 colours is in P while colouring with $k > 2$ colours is NP-complete. This dichotomy was extended to the graph homomorphism problem, also called $H$-colouring, by Hell and Nešetřil [J. Comb. Theory B, 48(1):92-110, 1990]. More precisely, they proved that deciding whether there is a graph homomorphism from a given graph to a fixed graph $H$ is in P if $H$ is bipartite (or contains a self-loop), and is NP-complete otherwise. This dichotomy served as an important test-case for the Feder–Vardi dichotomy conjecture, and Bulatov–Zhuk dichotomy of complexity of finite-template CSPs.
In the talk, I will present a new proof of this theorem using tools from topological combinatorics based on ideas of Lovász [J. Comb. Theory, Ser. A, 25(3):319-324, 1978] and Brower’s fixed-point theorem. This is joint work with Sebastian Meyer (TU Dresden).
- Speaker: Jakub Oprsal (University of Birmingham)
- Friday 09 May 2025, 14:00-15:00
- Venue: SS03, Computer Laboratory.
- Series: Logic and Semantics Seminar (Computer Laboratory); organiser: Anuj Dawar.