Over the last two decades we have developed good understanding how to quantify the impact of strategic user behaviour on outcomes in many games (including traffic routing and online auctions) and showed that the resulting bounds extend to repeated games assuming players use a form of no-regret learning to adapt to the environment. We will review how this area evolved since its early days, and also discuss some of the new frontiers, including when repeated interactions have carry-over effects between rounds: when outcomes in one round effect the game in the future, as is the case in many applications. In this talk, we study this phenomenon in the context of a game modelling queuing systems: routers compete for servers, where packets that do not get served need to be resent, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. In joint work with Jason Gaitonde, we analyse the resulting highly dependent random process, and show bounds on the excess server capacity needed to guarantee that all packets get served despite the selfish (myopic) behaviour of the queues.
This video was produced by the Hausdorff Center for Mathematics, and was part of the conference Panorama of Mathematics II.
