Non-cooperative queueing games on a Jackson network

Research output: Book/ReportReportOther research output

14 Downloads (Pure)

Abstract

In this paper we introduce non-cooperative games on a Jackson network. A player has a set of routes available and has to decide which routes to use for its customers. Each player's goal is to minimize the expected sojourn time of its customers. We consider two cases. First, each player is allowed to divide his customers over multiple routes. This results in a game for which it can be shown that a unique pure-strategy Nash equilibrium exists. This Nash equilibrium can be found by using a best-response algorithm.
Second, each player may only select a single route for its customers. This results in a game with finite strategy spaces. In general, such games need not have a pure-strategy Nash equilibrium, as shown by an example. We show the existence of pure-strategy Nash equilibria for four subclasses of games on a Jackson network: (i) N-player games with equal arrival rates for the players, (ii) 2-player games with identical service rates for all nodes, (iii) 2-player games on a 2 x 2-grid, and (iv) 2-player games on an A x B-grid with small differences in the service rates.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages16
Volume2066
Publication statusPublished - Jan 2019

Publication series

NameMemorandum of the Department of Applied Mathematics
ISSN (Print)1874-4850

Fingerprint

Jackson Networks
Queueing
Game
Nash Equilibrium
Customers
Grid
Non-cooperative Game
Sojourn Time
Divides
Minimise
Strategy

Keywords

  • Non-cooperative games
  • Routing
  • Pure-strategy Nash equilibria
  • Jackson networks

Cite this

Laan, C. M., Timmer, J., & Boucherie, R. J. (2019). Non-cooperative queueing games on a Jackson network. (Memorandum of the Department of Applied Mathematics). Enschede: University of Twente.
Laan, Corine M. ; Timmer, Judith ; Boucherie, Richard J. / Non-cooperative queueing games on a Jackson network. Enschede : University of Twente, 2019. 16 p. (Memorandum of the Department of Applied Mathematics).
@book{95ec9569ff7349fa92cc7e8e612c9efb,
title = "Non-cooperative queueing games on a Jackson network",
abstract = "In this paper we introduce non-cooperative games on a Jackson network. A player has a set of routes available and has to decide which routes to use for its customers. Each player's goal is to minimize the expected sojourn time of its customers. We consider two cases. First, each player is allowed to divide his customers over multiple routes. This results in a game for which it can be shown that a unique pure-strategy Nash equilibrium exists. This Nash equilibrium can be found by using a best-response algorithm.Second, each player may only select a single route for its customers. This results in a game with finite strategy spaces. In general, such games need not have a pure-strategy Nash equilibrium, as shown by an example. We show the existence of pure-strategy Nash equilibria for four subclasses of games on a Jackson network: (i) N-player games with equal arrival rates for the players, (ii) 2-player games with identical service rates for all nodes, (iii) 2-player games on a 2 x 2-grid, and (iv) 2-player games on an A x B-grid with small differences in the service rates.",
keywords = "Non-cooperative games, Routing, Pure-strategy Nash equilibria, Jackson networks",
author = "Laan, {Corine M.} and Judith Timmer and Boucherie, {Richard J.}",
year = "2019",
month = "1",
language = "English",
volume = "2066",
series = "Memorandum of the Department of Applied Mathematics",
publisher = "University of Twente",
address = "Netherlands",

}

Laan, CM, Timmer, J & Boucherie, RJ 2019, Non-cooperative queueing games on a Jackson network. Memorandum of the Department of Applied Mathematics, vol. 2066, University of Twente, Enschede.

Non-cooperative queueing games on a Jackson network. / Laan, Corine M.; Timmer, Judith; Boucherie, Richard J.

Enschede : University of Twente, 2019. 16 p. (Memorandum of the Department of Applied Mathematics).

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - Non-cooperative queueing games on a Jackson network

AU - Laan, Corine M.

AU - Timmer, Judith

AU - Boucherie, Richard J.

PY - 2019/1

Y1 - 2019/1

N2 - In this paper we introduce non-cooperative games on a Jackson network. A player has a set of routes available and has to decide which routes to use for its customers. Each player's goal is to minimize the expected sojourn time of its customers. We consider two cases. First, each player is allowed to divide his customers over multiple routes. This results in a game for which it can be shown that a unique pure-strategy Nash equilibrium exists. This Nash equilibrium can be found by using a best-response algorithm.Second, each player may only select a single route for its customers. This results in a game with finite strategy spaces. In general, such games need not have a pure-strategy Nash equilibrium, as shown by an example. We show the existence of pure-strategy Nash equilibria for four subclasses of games on a Jackson network: (i) N-player games with equal arrival rates for the players, (ii) 2-player games with identical service rates for all nodes, (iii) 2-player games on a 2 x 2-grid, and (iv) 2-player games on an A x B-grid with small differences in the service rates.

AB - In this paper we introduce non-cooperative games on a Jackson network. A player has a set of routes available and has to decide which routes to use for its customers. Each player's goal is to minimize the expected sojourn time of its customers. We consider two cases. First, each player is allowed to divide his customers over multiple routes. This results in a game for which it can be shown that a unique pure-strategy Nash equilibrium exists. This Nash equilibrium can be found by using a best-response algorithm.Second, each player may only select a single route for its customers. This results in a game with finite strategy spaces. In general, such games need not have a pure-strategy Nash equilibrium, as shown by an example. We show the existence of pure-strategy Nash equilibria for four subclasses of games on a Jackson network: (i) N-player games with equal arrival rates for the players, (ii) 2-player games with identical service rates for all nodes, (iii) 2-player games on a 2 x 2-grid, and (iv) 2-player games on an A x B-grid with small differences in the service rates.

KW - Non-cooperative games

KW - Routing

KW - Pure-strategy Nash equilibria

KW - Jackson networks

M3 - Report

VL - 2066

T3 - Memorandum of the Department of Applied Mathematics

BT - Non-cooperative queueing games on a Jackson network

PB - University of Twente

CY - Enschede

ER -

Laan CM, Timmer J, Boucherie RJ. Non-cooperative queueing games on a Jackson network. Enschede: University of Twente, 2019. 16 p. (Memorandum of the Department of Applied Mathematics).