Yet another coupon collector's problem blog post

04 Jul 2016

The coupon collector’s problem is a very common game mechanic. For example, the entire genre of collectible card games is based on the coupon collector’s problem. (It is also a very common blog topic.)

The player can do something (such as explore the world, or purchase a packet of cards), which gains them a random coupon. The random coupon may be novel to the player, or it may be a duplicate of a coupon that the player already has.

There are two facets to the strength of this game mechanic.

On the one hand, the mechanism is extremely simple and concrete. In the real world, the publisher merely prints many coupons and shuffles them fairly. In a game, the mechanism is something like:

give_coupon(math.random(1, 100))

On the other hand, the cognitive effect of the gradually spacing out, erratic pulses of novelty, is a pretty sophisticated schedule of reinforcement. In operant conditioning terms, it is similar to a “Variable Ratio” schedule of reinforcement, where the “ratio” gradually drifts downward.

That is, early in their collecting process, if the player has 20 distinct coupons out of 100, then they will probably get a new distinct coupon when they get another coupon. Specifically, they have a 0.8 probability. Later on, however, if they have 60 distinct coupons, the odds have shifted, and they will probably not get a new distinct coupon.

We can model this phenomenon using Joris Dormans’s Machinations (a tool for modeling game mechanics based on Petri nets). We have a “source”, which when you click it, creates a token, which flows to a “gate”, which randomly sends the token to a “pool”, either the uniques or the dups pool. That is, when the player collects a coupon, either it is a new unique coupon, or it is a duplicate of some previously collected coupon. The probabilities of the two choices start at 100% and 0%, but they change. Each new unique decreases the probability of subsequent uniques, and increases the probability of dups.

Building a simple randomized model, whether using a graphical tool like this, or in a spreadsheet or a little command-line program, can help answer questions like “If I set the exchange rate of trading at 5 dups for 1 unique, how long will it take to get this 100% achievement?”. It looks to me (using the “Run/Multiple Runs button”) like it might be around 525 clicks to get to 100 uniques without trading, and around 225 clicks to get to 100 uniques with trading.

Collecting the last few coupons is difficult and boring, and so players collecting physical coupons often turn to trading away their dups; even single player games often add a way to “trade away” dups. For example, if you were collecting a particular set of black assassin armor, you might accumulate a lot of “trash”, and the game might provide you a way to exchange the trash for gold, and the gold for arbitrary specific pieces of black assassin armor - slightly complicated, but basically the same mechanic.