Learning Outcomes in Queueing Systems

          @misc{ scivideos_16701,
            doi = {},
            url = {https://simons.berkeley.edu/talks/learning-outcomes-queueing-systems},
            author = {},
            keywords = {},
            language = {en},
            title = {Learning Outcomes in Queueing Systems},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {oct},
            note = {16701 see, \url{https://scivideos.org/index.php/Simons-Institute/16701}}
          }
          

Abstract

Over the last two decades we have developed good understanding how to quantify the impact of strategic user behavior on overall performance in many games (including traffic routing as well as online auctions), and showed that the resulting bounds extend to repeated games assuming players use a form of no-regret learning that helps them adapt to the environment. In this talk we will study this phenomenon in the context of a game modeling queuing systems: routers compete for servers, where packets that do not get service will be resent at future rounds, 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 analyze the resulting highly dependent random process and find that if the capacity of the servers is high enough to allow a centralized and knowledgeable scheduler to get all packets served even with double the packet arrival rate, then learning can help the queues in coordinating their behavior, the expected number of packets in the queues will remain bounded throughout time, assuming older packets have priority.