Stability and Learning in Strategic Queuing Systems
Autor: | Éva Tardos, Jason Gaitonde |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2020 |
Předmět: |
FOS: Computer and information sciences
Computer Science - Machine Learning Computer science Stability (learning theory) Context (language use) 0102 computer and information sciences 01 natural sciences Machine Learning (cs.LG) Computer Science - Computer Science and Game Theory Server Price of anarchy FOS: Mathematics 0101 mathematics Queue management system business.industry Network packet 010102 general mathematics Probability (math.PR) ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS 010201 computation theory & mathematics Repeated game Algorithmic game theory business Mathematics - Probability Computer network Computer Science and Game Theory (cs.GT) |
Zdroj: | EC |
Popis: | Bounding the price of anarchy, which quantifies the damage to social welfare due to selfish behavior of the participants, has been an important area of research. In this paper, we 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. We model this as an (infinitely) repeated game, where the system holds a state (number of packets held by each queue) that arises from the results of the previous round. We assume that routers satisfy the no-regret condition, e.g. they use learning strategies to identify the server where their packets get the best service. Classical work on repeated games makes the strong assumption that the subsequent rounds of the repeated games are independent (beyond the influence on learning from past history). The carryover effect caused by packets remaining in this system makes learning in our context result in a highly dependent random process. We analyze this 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, and queues use no-regret learning algorithms, then the expected number of packets in the queues will remain bounded throughout time, assuming older packets have priority. This paper is the first to study the effect of selfish learning in a queuing system, where the learners compete for resources, but rounds are not all independent: the number of packets to be routed at each round depends on the success of the routers in the previous rounds. 29 pages, 1 figure |
Databáze: | OpenAIRE |
Externí odkaz: |