A political simulation cannot do without an economic model that defines the reality in which the game plays out. Political decisions can’t just be limited to ethical issues or power for the sake of power, there has to be a way to actually influence and shape the world. The complication of doing so in a game that aims for a high degree of realism, is that politicians in most developed (and most undeveloped) countries don’t directly control the economy, but instead influence it through policy about issues like taxes, trade, industrial regulations, and so forth. In many strategy games, the game actually relies on the player(s) to make trade deals and so forth, but here the task is basically simulating an entire world’s private and public sectors, and the policies that influence them. Sounds easy right?

An economist is an expert who will know tomorrow why the things he predicted yesterday didn’t happen today.Laurence J. Peter

The economy simulation as a whole consists of two broad phases: the one which simulates the internal economies of territories (the micro phase), and the simulation of interaction between territories (the macro phase). As a reminder, consider that territories are the smallest geograhic, demographic and economic unit in the game world. The number of territories in a game world is planned to be about 1000, at least that’s what I think of as a convincing minimum, so I hope the simulation can manage. The game map generator spits out quite a lot of small islands (I usually see at least a hundred, often more), and every island is its own territory, as that permits naming them individually and so forth. Continental territories are a lot larger than those islands, of course, they will usually have a population of 4 to 8 million, to give you an idea.

In the micro simulation phase, economic actors (industrial sectors, consumers and government) produce and consume goods and services (which I call products) within the scope of one territory. Each territory does this on its own, independent of others, and local markets develop a price based on local prices of other products, wages, government regulations, etc. It is during this phase that local market prices are updated based on the supply and demand information available. Interesting technical note: since these economies are independent, they can be simulated in parallel on a multi-threaded system, without risking making any of the calculations non-deterministic.

In the macro phase, territories can export a surplus of a product to other territories which have a shortage of the same product. Since each territory has its own market price for that product, exporters and importers will have to agree on a price before trade can happen. There are other external factors as well, such as the cost to transport a quantity of product from one place in the world to another (this cost does not exist in the micro phase, because all the actors in the territory represent an aggregation of all relevant corporations or consumers), and possibly import or export tariffs imposed by governments. In principle the importer will pay for all the externality costs, though of course price pressure will eventually shift some of it to the exporter.

The micro phase uses the data flow graph model explained a few months ago in a previous blog post. While working on this part of the project, I encountered some challenges in terms of processing time, which had me doubting the scalability of the model for a while, but I ended up resolving it to my satisfaction. While I don’t consider the model finished yet at all, I’m confident this approach will work out. It is quite distinct from the academic approaches of economic simulation models because those typically rely on solving differential equations, whereas my approach feels more like the rules of board game (a pretty boring one, but it’s a computer playing it) rather than a mathematical system of equations. Since I have no basis in econometry and my calculus is rusty enough to warrant a tetanus vaccine, I feel much more at home in a more game-mechanical model which I debug and build on with relative easy.

After some time I took a break from the micro model to focus on the macro one, because I though it would be much easier. Turns out I was quite wrong!

The macro phase ended up using a distinct approach, with no data flow graph involved. I first investigated a few different algorithms, because the problem itself is not trivial: the algorithm needs to decide which territory trades which quantities of product with which other territories, at which price. There are obviously visible constraints: you can’t export more than you have as surplus, and you can’t import more than your demand. An additional soft constraint is that the process should not be too sensitive to changes in input. Just because the price changes in one place, usually shouldn’t mean trade deals at the other side of the world should shift radically. The algorithm would also need to respect trade embargoes, disallowing trade between some partners.

At first this feels like an optimization problem (e.g. Linear Programming). However, with the problem defined as above, it’s not even trivial to define a sensible optimization goal, since there are two contradictory goals: exporters want to maximize their profit, while importers want to minimize their cost. It’s not immediately obvious to me how to optimize for two opposite goals at the same time. To optimize both you’d need to take some non-linear function of both goals to keep both at a relative optimum (e.g. the square root of both terms), so that rules out Linear Programming as a strategy.

I soon scrapped these generic constraint programming optimization strategies as a feasible approach, because with 1000 territories, that makes for ~500 exporters and ~500 importers, so in total a matrix of 250,000 variables would need to be optimized. My time budget for calculating the trade for a single product is about 15 seconds at most, which turns out to not be attainable on commodity hardware with such a problem size, even for Linear Programming. Other approaches are by definition more complex, so they wouldn’t exactly be faster either.

I started thinking about the processing time and the optimization goals and figured that an additional requirement is that the algorithm needs to be fairly predictable in terms of run-time, so that it doesn’t depend too much on the actual values in the input. This hints at using “classic” algorithmic techniques like sorting and looping in straightforward ways, rather than scanning an unpredictable search space. I did learn from the optimization strategy that it’s helpful to think of the problem as a matrix: each column in an exporter, and each row is an importer, and the value in the matrix is how much they trade (the output of the algorithm). You also need separate matrices for the exporter’s price and the importer’s price (which includes transport and tariff costs). After some measurements, I realized that N=1000 is not at all a problem for classic algorithmic strategies. Matrices of a quarter million elements won’t blow up your computer, and sorting a thousand elements a thousand times is actually trivial.

So I approached the problem in the simplest way possible. First, I needed a way to settle on the price equilibrium. As an abstraction, I consider the trade price to be the average between the buyer’s price and seller’s price, weighed for the global seller/buyer volume advantage. The latter factor is simply the total supply or total demand of the product divided by the total supply plus total demand. That way, if there’s a global surplus of the product, buyers have more bargaining power, so the compromise price is closer to the buyer’s desired price rather than the seller’s, and the other way around. I use that formula to establish a seller’s price matrix for each buyer/seller combination, and a buyer’s price matrix, which is simply the seller’s price plus all the extras the buyer has to pay for (transport and tariffs).

This means every seller/buyer pair has a unique buyer’s price and a unique seller’s price. Now what we have to do is figure out which of these trades actually execute, and what volume is traded. After all, territories can (and should) trade with multiple partners, both domestic and abroad.

For each seller I sort all the buyers (higher seller’s price is better) and for each buyer I sort all the sellers (lower buyer’s price is better). For the programmers among you, this makes the algorithm O(N2*log(N)) which turns out not to be a problem at all. Then, I create a rank score for each seller/buyer pair and store it in a matrix. The rank score is calculated using the order of preference of the buyer and seller, squared. As an example, if territory A has territory B as its 3rd most preferred trade partner, and A is B’s 4th most preferred trade partner, their score equals 32 + 42 = 25. This is reminiscent of the least-sum-of-squares concept, which prefers a lower value for both terms over a very low and very high value. In addition, I also use factors to penalize for nations that don’t get along well, but that is outside the scope of this overview.

This rank score then is used to sort all seller/buyer pairs from low rank score to high rank score, so the deals at the front of the list are more likely to occur than the ones at the back. The algorithm then loops through the deals to execute them one by one, for a limited transaction quantity so that every territory gets some chance to participate in the trade. The allowed trade volume drops as the loop progresses, to emphasize the notion that deals at the front of the loop are more preferred. As the loop runs on, some sellers will run out of supply or some buyers will see their demand satisfied, so they will skip out on the next deal in the list involving them. That way most of the unfavored deals never actually execute. The loop is executed as many times as required, until there is either no more supply or no more demand.

The maximum trade volume for each run of the loop is something I still need to test and fine tune, but as it is directly dependent on the number of territories in the world and the total supply/demand volume, it works in a way that is independent of quantities. So if it makes the trade allocation behave somewhat suboptimally, it should do so in fairly consistent way. I implemented this algorithm, and while there are still some things to tune, it seems to work pretty well, and it manages to execute in the required time frame (well under 10 seconds for N=1000 with random inputs).

Here’s an example render of a setup using geography data from the 25 largest departments of France (I needed it to look pretty), clustered in three fictional nations (red, green and blue). The red semicircle signifies the supply, the blue one the demand, in each territory. If red is larger than blue, there’s a surplus, and vice versa. The purple lines signify trade, and a thicker line means a higher trade volume.

The second picture shows what happens if blue and red declare a trade embargo. You see the purple lines connecting the two disappear, and get replaced by thicker lines elsewhere.

Now that I have made significant progress on the macro model, I’ve resumed work on the micro model.