What’s a good algorithm for a random, uneven distribution of a fixed amount of a resource

algorithmsrandom

Problem

I have X, a positive integer, of some resource, R.

There are N potential targets.

I want to distribute all of R to the N targets in some "interesting" way.

"Interesting" means:

  • Some targets may not get any R.
  • It should rarely be near even (with a majority of target getting near X/N of the resource).
  • There should be at least a small chance of one target getting all of R.

Bad solutions

The naive approach would be to pick a random target and give one R to it and repeat X times. This would result in too even of an approach.

The next idea is to pick a random number between 1 and X and give it to a random target. This results in too large of a number (at least X/2 on average) being given to one target.

Question

This algorithm will be used frequently and I want the distribution to be interesting and uneven so that the surprise doesn't wear off for users.

Is there a good algorithm for something in between these two approaches, that fits the definition of interesting above?

Best Answer

Combine the two approaches. Hand out a random amount of the resource to a random user, then repeat. At each step, pick a portion of the remaining resource (1/x, with x a floating point number between 2 and 10), and hand it to any of the players (including a player who has already received some of the resource). When the remaining resource left to hand out gets low enough (say, under 1/2N left) just hand it out without further subdividing.

This allows for the chance of almost all of the resource going to the same player (1/2 handed out twice to one player), it being evenly divided, and a fractal-like distribution in between. Most of the time there will be significant imbalances in the resource available to each user. You can play with the cutoff point and the range of subdivision (2..10, 1..20, 3..5) to see how it varies the distribution of resources until you find a result that pleases you.

Further, the subdivision parameters could themselves be flexible... from A..B, and A and B are randomly chosen. If both are low (1.2 to 2.5) then a very small number of users will get most of the resources. If both are high (8.1 to 11.0) then the distribution will be quite even. This also allows for tuning the granularity of resource distribution as a setup option.

Related Topic