Discrete Event Population Updates: finding game theoretic emergent behaviour in queueing systems with simulation

Strategic behaviour in queueing systems has been studied extensively in the behavioural queueing literature, but almost exclusively for systems that admit closed-form expressions for the cost or utility experienced by a strategic user.

Evolutionary game theory offers a mature framework for analysing populations whose individual payoffs depend on the composition of the population itself, and would in principle apply to a much wider class of queueing systems; its application has, however, been constrained by the same closed-form requirement.

We introduce Discrete Event Population Updates (DEPU), a general algorithmic framework that couples a single long run of a discrete event simulation (DES) directly to an evolutionary population update rule, removing that constraint.

We present two implementations: Discrete Event Replicator Dynamics (DERD), which follows an Euler discretisation of the replicator dynamics equation, and Discrete Event Moran Replacement (DEMR), which maintains a finite population updated via Moran-style copying events.

Both are applied to a multi-server jockeying model for which no closed-form fitness expressions are available.

On the jockeying model considered, DEPU reaches comparable precision tens of times faster than the standard practice of nesting short simulations inside an outer evolutionary loop, and because each operating point then costs only a single simulation run it also makes systematic parameter sweeps tractable.

This brings the toolkit of evolutionary dynamics within reach of any system a modeller can build in a discrete event simulator.