37
Using Queues to Model a
Merchant’s Inventory
John Manslow

37.1 Introduction
37.2 M/M/1 Queues
37.3 Modeling a Merchant’s
Inventory

37.4 Conclusion
References

37.1 Introduction
Queues frequently appear in game worlds. Sometimes they are obvious—like the queues
formed by cars in a traffic jam or patients waiting to see a doctor. At other times, they are
more difficult to identify—like the queues formed by items in the inventory of a merchant.
M/M/1 queues arise when objects are added to, and removed from, a collection at random
time intervals and can be used to model such processes even when the order of the objects
is not important.
This chapter will describe how to use the statistical properties of M/M/1 queues toefficiently simulate how they change over time. To provide a practical example, the chapter will show how to represent the inventory of a merchant as a set of M/M/1 queues anddemonstrate how to efficiently generate realistic and mutually consistent random realizations of the inventory that take account of the levels of supply and demand. The book’s
website (http://www.gameaipro.com) includes a full implementation of everything that is
described in the article.

463

37.2 M/M/1 Queues
An M/M/1 queue is a process in which objects are added to, and removed from, a collection at random intervals. The name M/M/1 is actually a form of Kendall’s notation[Zabinsky 13], which is used to classify queues and indicates that additions and removals
are memoryless (the time of one addition or removal does not affect the time of another)and that the queue consists of only a single collection. The random timings of the additions and removals mean that the number of objects in the collection—the length of thequeue—changes randomly with time. Although this makes it impossible to predict thelength of the queue with any certainty, it is possible to model it using two probability distributions, the stationary distribution and the transient distribution.
The stationary distribution models the length of queue that one would expect to see
if the queuing process had been running for a very long time before it was observed. It istherefore useful for describing the length of a queue when it is encountered by the player
for the first time. If objects are added to a queue at an average rate of add_rate per unit timeand removed from it at an average rate of remove_rate per unit time, then its stationary
distribution isp(n) = (1 − rate _ ratio ) ⋅ rate _ ratio n(37.1)

whererate _ ratio =add _ rate
remove _ rate

(37.2)and p(n) is the probability of the length of the queue being n items.
Note that, for a queue to be of finite length, it is necessary for rate_ratio to be strictly
less than one. In other words, if the merchant’s inventory isn’t going to grow withoutbound, things need to be leaving the store faster than they are coming in. In general, theaverage length of an M/M/1 queue is 1/(1 − rate_ratio), and the probability of observing
an empty queue is 1 − rate_ratio.
Players naturally expect to encounter queues of specific lengths and not strange quantum queues in weird superpositions of states. It is therefore necessary to create a specificrealization of a queue when the player first observes it by sampling from its stationary
distribution. A simple way to do that is to generate a random number x that is greater thanor equal to zero and less than one and, starting at n = 0, add the values of p(n) until theirsum exceeds x and then take n to be the length of the queue. This approach is implemented
in MM1Queue::GetSample.
The transient distribution describes the length of a queue that has already been observed
and is therefore useful when a player encounters a queue for anything other than the firsttime. If, t units of time ago, the player observed a queue to be of length m, its transient
distribution is [Baccelli 89]
p (n | t ,m ) = e −(add _ rate +remove _ rate )⋅t ⋅ [ p1 + p2 + p3 ]464

(37.3)
Character Behavior

wheren −mp1 = rate _ ratio 2 ⋅ I n −m (at )p2 = rate _ ration −m −12

p3 = (1 − rate _ ratio ) ⋅ rate _ ratio⋅ I n +m +1 (at )∞n(37.4)∑(37.5)−

jrate _ ratio 2 ⋅ I n +m +1 (at )(37.6)

j =n + m + 2

anda = 2 × remove _ rate rate _ ratio ,(37.7)I n (⋅) is the modified Bessel function of the first kind, which is computed by
MathUtilities::Iax, and p(n | t ,m) is the probability that the length of the queue is n,which is computed by MM1Queue::GetStateProbability. Once again, it is necessary to create a specific realization of the queue, and that can be done using the procedure that has already been described, but substituting p(n | t ,m) for p(n). This approachis implemented in the overload of MM1Queue::GetSample that takes time and countparameters.
Because both the stationary and transient distributions are derived from a statisticalmodel of the queuing process, samples that are drawn from them naturally satisfy all common sense expectations as to how queues change over time. In particular,
Queues with high rates of addition and low rates of removal will usually be long
Queues with low rates of addition and high rates of removal will usually be short
The effects of player interactions will disappear with time—slowly for queues withlow rates of addition and removal and quickly for queues with high rates of addition and removal•• Queues will change little if the time between observations is short, especially forqueues with low rates of addition and removal•• Queues will change a lot if the time between observations is long, especially forqueues with high rates of addition and removal
••
••
••

The first row of Table 37.1 gives the stationary distribution for a queue with add_rate = 0.5(one addition every other unit of time on average) and remove_rate = 1.0 (one removal perunit of time on average). Assuming that the player observes the queue to be of length two
at time zero and adds four objects to it, the following rows show the transient distribution
0.01, 0.1, 1, 10, and 100 units of time later. It is important to note that these rows show how
the transient distribution would evolve if the queue remained unobserved and hence noconcrete realizations were produced. For example, 10 units of time after the player had
observed the queue, there would be a 0.103 probability of the queue being 3 objects long.
Using Queues to Model a Merchant’s Inventory465

Table 37.1 An Example of an Equilibrium Distribution and Transient Distributions
Queue Length, nTime, t

0

1

2

3

4

5

6

7

8

0.00
0.01
0.10
1.00
10.00
100.00

0.500
0.000
0.000
0.000
0.315
0.500

0.250
0.000
0.000
0.002
0.186
0.250

0.125
0.000
0.000
0.010
0.131
0.125

0.063
0.000
0.000
0.042
0.103
0.063

0.031
0.000
0.004
0.131
0.082
0.031

0.016
0.010
0.087
0.284
0.063
0.016

0.008
0.985
0.865
0.349
0.046
0.008

0.004
0.005
0.043
0.142
0.031
0.004

0.002
0.000
0.001
0.033
0.020
0.002

The transient distribution makes it possible to model how the length of a queue changes
after it has been observed but provides no way of determining how many of the individual
objects that were originally in the queue are still there when it is observed again. Thatkind of information is useful when the objects are uniquely identifiable. For example, cars
parked on a street will have different colors and be different makes and models, and people
waiting in a hospital will have different clothing and facial features.
If the objects are processed on a strictly first-come, first-served basis, then the numberthat remain in the queue from the previous observation can roughly be estimated by taking the original length of the queue and subtracting a sample from a Poisson distributionthat represents the number of objects processed since the queue was last observed.
If the objects are processed in a random order, the number that remain can be approximated by taking a sample from the same Poisson distribution and then using it in conjunction with a binomial distribution to estimate the number of objects in the originalqueue that were processed. Technically, this is equivalent to assuming that the length of
the queue remained the same between the two observations, but it produces realisticlooking estimates even when that is not actually the case. Implementations of both techniques can be found in the Inventory::GenerateRealization overload that takes
the time parameter.
Before finishing the discussion of M/M/1 queues, it is important to highlight the factthat the expressions for the stationary and transient distributions assume that the average rates at which objects are added to, and removed from, the queue are constant. This
assumption holds for many natural processes but breaks down when additions or removals occur in bursts. Such bursts will occur in relation to the numbers of cars waiting at anintersection, for example, due to the presence of a neighboring intersection or the effectsof traffic signals. In such cases, the theoretical deficiencies of M/M/1 queues will often not
be apparent to the player and can be ignored, but, in some cases, it will be necessary to usean alternative model [Zabinsky 13].
This section has described the basic properties of M/M/1 queues, given expressions
for the stationary and transient distributions of queue length, and shown how to sample
from those distributions to generate consistent realizations when queues are encounteredby the player. The following section will describe how M/M/1 queues can be used to model
the inventory of a merchant to produce random inventories that are consistent with eachother, with the levels of supply and demand of each type of item in the inventory and withthe player’s observations and interactions with the merchant.
466

Character Behavior

37.3 Modeling a Merchant’s Inventory
In a large, open world game with dozens of merchants, hundreds of NPCs, and tens of
thousands of individual inventory items, it is impractical to explicitly model economic
activity in real time in enough detail to track the inventory of each merchant. Fortunately,
to make the world believable, it is sufficient to generate random inventories each time amerchant is encountered provided that they are consistent with players’ common sense
expectations as to how they should change with time.
In terms of the numbers of each type of item in an inventory, those expectations are
essentially the same as those for the lengths of queues that were given earlier. This strongly
suggests that a merchant’s inventory can be modeled in the following way:
1. Create one M/M/1 queue for each type of item the merchant can have in his or her
inventory.
2. Set the average rate at which each type of item is added to its queue to be equal tothe average rate at which the merchant will buy it.
3. Set the average rate at which each type of item is removed from its queue to beequal to the average rate at which the merchant will sell it when he or she has it.
4. When the player first encounters the merchant, create his or her inventory bysampling from the stationary distribution for each type of item.
5. On all subsequent encounters, create his or her inventory by sampling from thetransient distribution for each type of item.
Even though real merchants do not buy and sell at random, steps 2 and 3 ensure that themerchant’s inventory is generally consistent with the levels of supply and demand for eachtype of item, and step 5 ensures that players see an inventory that is consistent from one
visit to the next.
Table 37.2 gives an example of how the numbers of three inventory items—truffles,
arrows, and swords—vary with time, which, in this example, is measured in game world
hours. Truffles are assumed to have limited supply (only one is added to the inventory
every 1000 h on average) but high demand (one is sold every hour on average), arrows are
assumed to have high supply (one is added every hour on average) and high demand (oneis sold every 0.98 h on average), and swords are assumed to have low supply (one is added
every 200 h on average) and low demand (one is sold every 100 h on average).

Table 37.2 An Example of How a Simple Three-Item Inventory Changes with Time
Item
Time (h)00 after player interaction
1
48
100
200

TrufflesArrowsSwords

0
5
3
0
0
0

83
33
33
37
26
47

1
1
1
1
0
0

Using Queues to Model a Merchant’s Inventory

467

The numbers of truffles, arrows, and swords at time zero—when the player encounters the merchant for the first time—are obtained by sampling from each type of item’s
stationary distribution. The player sells the merchant five truffles and buys 50 arrows andthen explores the environment for 1 h. He or she then returns to the merchant, and a newinventory is generated by sampling from each type of item’s transient distribution. Thisreveals that the merchant still has three truffles left and the number of arrows and swords
hasn’t changed. Returning to the merchant after 48 h reveals that all truffles have been soldand the merchant has 37 arrows. The code that was used to generate the numbers in thisexample is included on the book’s website.
The basic inventory model that has been described so far can easily be enhanced tosimulate more complex behavior. For example, a merchant might buy 50 arrows every
Monday but only if he has fewer than 50 arrows in stock. This kind of behavior can beclosely approximated by sampling from the distribution for the number of arrows in
the merchant’s inventory from the previous Monday and adding 50 if the sample is lessthan 50. The resulting number can then be used as a “virtual observation” when samplingfrom the current transient distribution to obtain the current number of arrows—the game
simply behaves as though the player had been present the previous Monday and seen how
many arrows the merchant had.
Similar logic can be used if the merchant always buys enough arrows to bring his or her
stock up to 50, if the arrow vendor comes randomly rather than every Monday, or if the supply of arrows is not entirely dependable. The merchant buying additional stock is only one
type of special event that affects the numbers of items in his inventory. Another might be thedeath of a nobleman, causing the merchant to suddenly acquire a large number of luxury
items at the resulting estate sale or the commander of a local garrison buying up all of thearmor. Such events can be modeled in a similar way to the merchant’s buying behavior; avirtual observation of the affected inventory item can be created for the time of the eventand used in the transient distribution when the player encounters the merchant.
Other events might cause permanent changes in the levels of supply and demand, andthey can be simulated by changing add_rate and remove_rate. For example, a new minemight open up, leading to an increase in the supply of iron. This effect can be simulated
by making a virtual observation of the amount of iron that the merchant had in stock
when the mine opened by sampling from a distribution with the old values of add_rate
and remove_rate. That observation would then be used in the transient distribution with
the new values of add_rate and remove_rate when the player encountered the merchant.
If the levels of supply and demand change multiple times between encounters, the effectsof the changes can be simulated by multiple virtual observations that are obtained using
the previous observation, the previous values of add_rate and remove_rate, and the sampling from the transient distribution. The game would thus behave as though the player
had observed the level of stock of the affected type of item each time its supply anddemand changed.
In some cases, it is desirable to ensure that a merchant always has a certain minimum
number of items of a particular type in stock. If a game directs the player to travel a long
way to buy special items, for example, it would be very frustrating to arrive at the destination only to discover that the items were not available. This problem can easily besolved by adding a constant to the number of items generated by the stationary distribution on the player’s first encounter. If the merchant should generally maintain a certain
468

Character Behavior

minimum stock level, then adding a constant is unsatisfactory because it does not adequately model the dynamics of how stock changes in response to interactions with theplayer—if the player buys all the stock, for example, the amount of stock needs to recoverin a convincing way.
The simplest solution to this problem is to model the merchant regularly buying new
stock, as was described earlier. Alternately, it is possible to create a reserve of items thatcan only be purchased by the player and model how it recovers over time if the player
makes a purchase that depletes it. This is done by estimating the number of items that
could have been added to the reserve since it was depleted if the merchant repopulated itby buying items at a rate of add_rate and selling nothing. If the reserve could only havebeen partially repopulated, the reserve is the full extent of the inventory, and no sample
from the transient distribution is required. If the reserve could have been fully repopulated, however, the time when the process of repopulation would’ve been completed is calculated, and the number of nonreserve items is obtained by sampling from the transient
distribution using a virtual observation of zero nonreserve items backdated to when thereserve would’ve reached full strength. This technique is implemented in the overload of
Inventory::GenerateRealization that takes the time parameter.
Finally, some types of items, such as arrows, are naturally traded in batches, and it
is unlikely that a merchant would buy or sell only a single instance of such types. Thiseffect can be approximated by using stationary and transient distributions to represent
the numbers of batches held by the merchant rather than the numbers of individual
items. When the number of batches changes from the player’s last observation, the number of items can be generated randomly by assuming that a particular number of batches
would correspond to a particular range of numbers of items. For example, if each batchof arrows is of size 25, then one batch would correspond to between 1 and 25 arrows,
two batches, 26 and 50 arrows, etc. If a sample from the distribution specified a stocklevel of two batches, the actual number of items would be chosen randomly from therange 26 to 50.
In general, the properties of M/M/1 queues that were described earlier make it possible
to guess values for parameters like add_rate and remove_rate to simulate specific behaviors. It is, however, important to validate those behaviors using a simple test application
like the one included on the book’s website that allows the behaviors to be quickly andefficiently evaluated over a wide range of timescales.
37.3.1 Computational Considerations
A game might contain many thousands of different types of items that could potentially
be found in an inventory, so the question naturally arises as to whether it’s computationally practical to sample from such a large number of queues. Fortunately, for types whererate_ratio is small (i.e., for types that are unlikely to appear in the inventory or to only bepresent in small numbers—such as truffles and swords), samples can be obtained at a rateof hundreds of thousands per second per core on a typical desktop PC. Where rate_ratio
is close to one—as was the case with the arrows—samples can only be obtained at a rate ofthousands per second, so the approach described in this chapter might not be suitable forinventories where hundreds of different types of items are likely to be present in hundreds
or thousands. Such inventories are likely to be the exception, however, and it is importantto remember that samples are only required when a player encounters a merchant—there’sUsing Queues to Model a Merchant’s Inventory469

no ongoing computation—and that samples for each type of item are independent, andhence the process of sampling can, if necessary, easily be distributed across multiple coresand multiple frames.

37.4 Conclusion
This article has described M/M/1 queues and showed how they can be simulated in a consistent and computationally efficient way by sampling from their stationary and transient
distributions. It has shown how they can be used to represent the inventory of a merchantin such a way that it remains consistent with each item’s supply and demand, the player’s
observations of the inventory, and the player’s interactions with the merchant. This provides a simple and efficient way to simulate how the inventory of a merchant changes
with time.

References[Baccelli 89] Baccelli, F., Massey, W. A. 1989. A sample path analysis of the M/M/1
queue. Journal of Applied Probability, 26(2): 418–422. https://www.princeton.
edu/~wmassey/20th%20Century/sample%20path%20MM1.pdf (accessed July 20,2014).
[Zabinsky 13] Zabinsky, Z. 2013. Stochastic models and decision analysis, University ofWashington, Seattle, WA. http://courses.washington.edu/inde411/QueueingTheory.
pdf (accessed July 20, 2014).

470

Character Behavior