To start off, I’d like to clarify what I mean by “economy” here – just the underlying simulation that moves around commodities and is responsible for matching up supply and demand across the Sector. This does not include things like trade disruptions, which are events that cause price changes. These are certainly part of a more expansive and player-centric definition of “economy”, but for this post, I’d like to focus purely on the commodity distribution algorithm.

Overview
So, what does the algorithm need to do? We’ve got markets and commodities, and each market has a supply (i.e. production) and a demand (i.e. consumption) for each. What we need to do is figure out where commodities will end up, given the supply/demand situation. For example, if one market is producing food, its output should be distributed among food-consuming markets according to their demand.

There are some further complications, but the above is the gist of it – fairly straightforward supply and demand stuff, though getting it to actually work out is anything but.

Taking a step back for a moment, “does there need to be a detailed economy simulation?” is a good question to ask. Certainly, nothing in the game right now justifies that – it could all be handled using a healthy dose of smoke and mirrors instead. (Though at some point the amount of smoke and mirrors required exceeds the effort to do something “properly”, but I digress.)

For this blog post, though, let’s work with the assumption that there are solid mechanical reasons for having an economy simulation, and it’s not just a pointless “but this would be realistic”-style complication.

(As an aside: an astute reader might notice that the stated problem bears some resemblance to the assignment problem. Prices changing as demand is met throws a huge spanner in the works, but reading up on existing approaches to solving it was nonetheless quite useful.)

Current Algorithm
There’s already code in place to do this – but, without going into the details of how it works – it takes too long for prices to reach a stable point. The algorithm is iterative, and we can only run it a certain number of times in, say, a game-month, given all the other things that game needs to do. Given how often it can be run, it takes too many iterations to reach an equilibrium, something on the order of an in-game year or more.

If we’re going to have player-run industry, the economy will have to be able to adjust to changes introduced by the player more quickly than that, so this is a problem.

New Algorithm
Instead of going into detail and describing how the entire algorithm works (which, truth be told, I tried – but it came out drier than Arrakis), let me hit the high points instead – the parts that were interesting and sometimes unexpected. Here we go then: take two.

The new approach is also iterative, meaning we’re going to be running it in steps, which for performance reasons are spread out over many frames, with a limit on how long the work in each frame can take.  The ultimate goal is to produce a “stockpile” value for each commodity at each market – how much of it ends up there. This value may fluctuate a bit, but should be fairly stable once an equilibrium is reached.

Bids and Contracts
The heart of the algorithm is a system of “contracts” and “bids”. Markets put out contracts for a commodity, other markets make bids to fill the contracts, and the best bids at each stage are accepted.

Accepted bids remain accepted for a number of steps. This accomplishes two things: 1) “where does each market get its supply of X from” becomes less volatile (don’t want a market getting changing its mind about where it’s getting 90% of its food 10 times a month), and 2) the algorithm runs faster since it doesn’t have to find as many contract-bid pairs at every step.

If a contract isn’t filled at a given step, the size of that contract is halved. This lets smaller suppliers fill large contracts eventually, though it does mean that larger suppliers get “first dibs” on filling large contracts. This wasn’t one of the goals for the simulation, but isn’t a bad property to have, as it also produces results that make more sense to a human looking at them.

If a contract filled for two steps in a row, the contract size is doubled, up to the initial contract value, which is the local demand for a commodity. If this sounds familiar, it’s because this is very similar to the AIMD algorithm, notably used in the TCP protocol for congestion avoidance.

The AIMD algorithm uses a linear increase, which helps zero in on the best rate, but we don’t care about that here – there aren’t enough steps for this to matter. What we want to avoid is a situation where one market fills the demand of another, while a less-profitable option has its contracts progressively halved until they’re at the minimum level – at which point, filling its demand will take lots of steps. In this case, we want to ramp the contract size, and an exponential works well for that.

Supply and Stockpiles
A natural way to handle supply is to add it to local stockpiles at the start of a step, and then distribute these stockpiles according to the “contracts and bids” algorithm. However, this doesn’t work! We’re moving commodities around in large chunks (see: contract size), and if these are taken from/added to stockpiles, the stockpile values become very, very volatile from step to step.

The result is that the simulation never stabilizes. If we could move commodities around in very small quantities – say, one unit per bid – then it would work, because we wouldn’t keep overshooting the equilibrium point in one direction or another. Unfortunately, that’s not computationally feasible.

Instead, during every step, the algorithm keeps track of “for sale” quantities separately from stockpiles, and only adjusts the actual stockpiles at the end of a step, once it’s figured out the commodity flow for that step. The “for sale” quantities are based on local supply, and only include a quantity based on the local stockpile if it exceeds local supply and demand.

In effect, instead of moving around stockpiles, we’re moving around projected supply. Since supply values tend to stay the same, this gives us a much more stable starting state at each step than using the actual stockpiles, and produces an equilibrium state in the simulation much more quickly.

Finally, supply is dynamically scaled back when local stockpiles get too high. This prevents runaway over-production, and should be of particular use in making modded economies more likely to reach a balance.

Other Details
All pairs of markets have a “connection weight” that denotes how expensive it is to ship from one to the other, initially based on distance. For markets owned by hostile factions, this weight is increased further, representing the difficulties in smuggling the commodities across. This results in commodities naturally flowing through neutral third parties, where this is profitable to said third party.

There is no “backflow” – i.e. if market A sold commodity B to market C, market C will not sell commodity B back to market A during the same step. The reasons to disallow this are: 1) it produces confusing player-facing results, and 2) it can lead to the simulation taking longer to stabilize due to the extra sales it generates.

Performance
The new simulation runs 10 times per month, compared to the current one running once a month. The performance so far is good – on my dev computer, it uses about 10% of the 1 millisecond-per-frame budget, with 3 game days allotted for a full iteration.

This gives some room for growth, which is needed both to account for mods and the base game getting bigger, especially as the performance is non-linear in terms of the number of markets and commodities. For example, there are 40 or so markets now. If that number went up to 400, it would more than use up the budget.

UI Changes
The above is all backend stuff, and it’s not much good without the player being able to see it. Some of this will come with industry and outposts, but even without that, we can do some things to make what’s going on visible to the player.

There’s a screenshot of the “market info” screen at the beginning of this post; let’s take a look at another one.

The goal for this screen is to convey what this market’s economy is all about. Here, for example, we can see that Organics are a major factor in Jangala’s economy – and we can see that local stockpiles are high, meaning the price is good if we want to buy some.

Drilling down deeper, let’s look at the details for Organics:

Here we can see that most of the exports are going to Chicomoztoc, with a smattering going to other places. This would also be a good place for a breakdown of local consumption, when that becomes relevant.

We’ve also got a graph showing long-term trends for every commodity, and revealing other information that was previously completely hidden from the player. For example, looking at Recreational Drugs in Sindria, you can see a relationship between stability and demand for drugs – less stability, more demand. These graphs could also be a good way to check on how your actions are impacting a particular market, though just what those actions are is still up in the air.

The overall number of commodities is much-reduced compared to the current version. Instead of using a power-of-ten based on market size, it uses a power-of-two. The disparity between large and small markets is still significant, but the lower numbers make it easier to display various commodity icons next to each other while making comparative scale clear. So, what does it look like for the biggest market in the Sector, Chicomoztoc?

Yikes. Borderline manageable, but not quite there. Options include cutting down the number of icons – the goal of the main market info screen is to provide relative data, after all – or just waiting to see if the final number of commodities turn out to be smaller. Either way, it’s not far off from being usable, and will be tweaked accordingly at some point.

In conclusion: a more robust economy backend was needed before the economy could be something that the player can get directly involved in. The work outlined above was done while keeping in mind what that involvement will look like – but perhaps I’ve said too much already.

 

Comment thread here.

 

 

Tags: contracts, demand, economy, market, performance, supply, the spice must flow, UI