Once again, the world is facing a terrible pandemic.
Time to rise to the occasion and eradicate this scourge!
The good news? We’re talking about Pandemic, the board game.
The bad news? I’m going to dissect some aspects of it using some mathematical analysis.
This might get ugly 🙂
Joking aside, it is the second time I’m tackling a board game using graph analysis, the first time in Graph analysis of the Cthulhu Wars maps, and now, Pandemic… I may have a weak spot for apocalyptic scenarios!
The reason I wanted to look at the Pandemic is simple: It is an ideal match for graph analysis. The game’s theme and mechanics scream GRAPHS…
…And they even already represented the board as one:
So let’s see what graphs theory can reveal about this game, and helps us in the fight against fictional diseases!
Pandemic: the game in 3 sentences
You are trying to contain outbreaks of four deadly diseases, travelling around the world and collaborating with other players as a team of specialists.
Each turn, you take actions like treating infections, building research stations, or sharing knowledge, all while fighting the spread of disease that can trigger devastating epidemics.
You will win by discovering cures for all four diseases, but if the outbreaks become unmanageable or time runs out, you’ll have failed.
The whole thing is very fun, so if you haven’t played, you should give it a try!
In the meantime, you can read the following, a discussion of graph and board games that don’t require actually having played.
So let’s dive into it!
What is this article about
This article is about introducing simple concepts from graph theory that can offer insight into the Pandemic map.
Here’s what we will be doing:
- Building a graph from the Pandemic map.
- Discuss graph metrics like degree, diameter, closeness centrality, eccentricity and see their influence on gameplay.
- Figuring out the best spots to position players for maximum map coverage.
- Finding prime locations for research stations to reduce the graph size and facilitate movement.
Let’s play smarter, and hopefully get new ways to look at game maps in general!
The world as a Graph
When looking at a map, everyone have some sense on the best ways to move around.
But as you may have personally experienced, not everyone agrees on the shortest path between two points. Some people are very opinionated about their ‘shortcuts’ !
To simplify the world, a nifty trick is to consider the map as a graph separating the world in locations and travel paths between them.
Here, each city will become a node, and each travel path between cities an edge.
That’s it! We now have the world as a graph.
The Pandemic game makes that visually very explicit.
A few additional specifications:
- Each connection between cities is considered of the same length, in our case taking a single action to traverse it.
- All connections can be traversed in one direction or the other.
(This is what graph theorists would call an Unweighted, Undirected Graph.)
Other maps, same concept
A lot of other games, like Risk, can be abstracted in the same way. Each location being a node, each travel path being an edge.
In games like Risk (or Cthulhu wars), edge representation are closer to their real life counterpart, being represented more or less as linear land frontiers.
This can obscure the graph nature of a map quite a bit, but in the end, those games do not consider the size of the countries, only their connections. So you end up with exactly the same abstract representation when playing. Visually it does not feel the same, but those are in facts very similar graphs!
The Pandemic Map Graph
If we break down the Pandemic map by it’s graph elements, we have the following:
48 cities, linked by 93 connections.
From an epidemic point of view, the first thing to consider is how connected to each other are the cities in the world.
The more connected cities are among the most dangerous.
If the pandemic reach those, they risk infecting all connected cities soon after, so well connected cities make disease spread faster.
We can check each city individually and count it’s neighbours, but since we are looking at the map, colour-coding the graph is much more efficient (and fun). This allows to understand the connection density much more quickly.
The following map represent this, with the most connected cities in Red, and the least in blue:
If we were to compare different maps, we could consider the average connection-count of the locations on the maps. What is some time called the degree of nodes. This would inform you a bit about the speed a disease can spread.
This is easy to calculate: You take twice number of edge (to account that a edge connect 2 cities) and divide it by the number of cities.
93 * 2 / 48 = 3.875
Unfortunately for us, since we only have one map to consider, we will not go far with that.
Another way to visualize this information is simply counting how many cities have similar connection numbers.
The following histogram represent exactly this:
Looking at both this and the map, we can see they represent the same information. Hong Kong and Istanbul are the only two 6-connections cities, and Santiago being the only 1-connection city. Most cities are 4-connected, with an almost equivalent cohort of 3 and 5-connected cities as well.
Reaching beyond
One very important piece of information about the connections-count is that it tells us the number of locations that can be reached from a city using only one move. I know, it seems self-evident, but this is the starting point for what is to follow…
The number of cities we can travel to with one move is self-evident. But what about the number of cities you can travel to with 2 moves? It’s also a measure of how connected cities are, but one that is more difficult to grasp with a quick glance!
Here is the map showing how many cities can be reached in 2 moves from each location.
If we compare the most extreme cases, in red, we can see a few changes. Cairo becomes more dangerous than Istanbul… It is less immediately connected, but it reaches other hubs faster.
And we do not have to stop here.
Following is the same map colour coded with how many cities can be reached in 3 moves.
The difference are even more marked! Cities that sit on the edge of clusters, such as Madrid, are suddenly becoming the hot points on the map!
So depending on the timelines we consider, the centrality of cities will change.
This is something that true Pandemic experts must be aware of. Sometimes cities that look less critical can end up becoming your undoing if you are too late to understand their role in the graph!
A true measure of a city centrality
To generalize on this idea of how central a node is in a graph, nothing beats the real thing.
In Graph analysis, this measure is called: Closeness centrality.
You can take an individual city-node and:
- Select another city on the map
- Find the shortest path to it through the graph
- Measure the length of that path, and save it.
- .. Redo this for all other cities on the map.
The sum of all shortest paths, divided by the number of city gives the average distance a city is from all other cities on the map.
We call that measure the centrality of that node.
Now… If you do that for all cities, you have a new way at looking at the graph. Each node have a closeness centrality measure telling you it’s relation to the rest of the graph.
The lower the number, the closer you are to everything. (The higher, the farther away you are!)
Have a look at the map with each city measured and color coded. (Here Red is for smaller number, closer to everything on average, blue farther)
Looking for the worst case.
If you are more of a pessimistic nature, another measure we could consider is the worst case distance to reach a node on the map. Or if you prefer: assuming you always take the shortest route, what is the longest route you would have to rush through to stop an epidemic on the other side of the world.
In graph speak, that measure (Longest route in the graph) is called the eccentricity of a node.
If we measure this for each node and represent it on the map, here what it looks like:
While it shows similarity to the average distance map, it is clearly not the same.
As an example, Chennai suddenly is a more interesting position to hold if your goal is to minimize the worst case.
This contrast with locations like Algiers which ends up having a worse worse case travel than could have been foreseen by only looking at it’s average distance to other cities!
Where to position yourself to cover the world
Waiting for an epidemic outburst must be nerve wracking. It could arise anywhere, and always need a quick intervention to keep it contained… The best thing you can do is to position yourself as to be able to reach anywhere as quickly as possible!
One strategy could be to use the eccentricity map and position yourself at the node with the best worst case scenario. This minimize the maximum number of moves you could need to reach any point on the map.
Montreal, Chennai, Bogota, Los Angeles and Mexico city would be great spots for that!
However, if you want a statistically safer option, you could position yourself to minimize the average distance to all the cities on the map. You could find yourself in a worse case scenario, but on average, you will still be able to reach outbreak faster.
Let’s explore this strategy a bit mode in-depth.
Covering the world as a team
If you are alone, and want to position yourself to have the shortest distance to go on average to reach any outbreaks, we already covered that with the map of average distances:
Looking at the top 5 cities to station yourself for quick reach, we get the following:
| City | Average distance |
|---|---|
| Chicago | 3.44 |
| Los Angeles | 3.54 |
| Mexico City | 3.58 |
| Madrid | 3.60 |
| Bogotá | 3.62 |
This is a great starting point!
(Just to be clear, here the lowest distance is 3.44 instead of the 3.51 because I calculated the avg distance to all nodes, including the one you are standing on. So it’s simply a matter of dividing by 48 instead of 47, but the optimal position and color coding stays the same).
To make this a bit more real, here is the map colour coded by distance to a player positioned in Chicago
Divide and cover
With more players, this get slightly more trickier…
For 2 players, you have to compare all possible starting pair of player positions for the following:
- For each node, what is the shortest distance to the closest player position.
- Calculate the average
So instead of doing the individual average distance for each on the 48 nodes of the map once… You do it for each possible pair of starting position, of which there are 48 * 47 different pairs, so 2256 times!
Good thing we can delegate this to a computer. So here are the best pair of cities to position 2 players, in order to cover the graph the most effectively (on average).
| City pair | Average distance |
|---|---|
| Madrid, Hong Kong | 2.08 |
| San Francisco, Cairo | 2.15 |
| San Francisco, Istanbul | 2.17 |
| Chicago, Cairo | 2.17 |
| Cairo, Los Angeles | 2.17 |
Here is the map showing the distance to any of the player, when positioned in best locations (Madrid and Hong Kong):
3 Players best coverage
Repeating the same for 3 players, we get to consider all the possible case for 48*47*46 or 103776 triplets.
Here are the best 5 options to position 3 players on the map:
| City triplet | Average distance |
|---|---|
| Cairo, Hong Kong, Mexico City | 1.625 |
| Istanbul, Hong Kong, Bogotá | 1.6458 |
| Istanbul, Hong Kong, Mexico City | 1.6458 |
| Cairo, Hong Kong, Bogotá | 1.6458 |
| Cairo, Hong Kong, Miami | 1.6458 |
In this case, it seems there are more than one option with very similar average distance values.
This peaked my curiosity, so I decided to take a small detour and generated a histogram of all possible triplet and average distance:
And for the curious, the worse positions you can take is: Beijing,Seoul,Osaka with a whooping average distance of 4.6042 !
This interestingly gives you an idea about the average distances you will find yourself to cities during the course of a normal play where you are bumbling around, fighting epidemics. Here you can have an idea of the worse and best cases you could find yourself into depending on if you take care of staying spread out throughout the map!
Don’t read too much into the gap or peaks of the histogram, this is simply an artifact caused by the bin size chosen for the histogram, and maybe some idiosyncrasy of the way the distance average on our particular map.
As before, here is the map with 3 players starting in the best locations:
4 Players best coverage
Finally with 4 players, here are the top 5 locations to starts from.
- Average distance: 1.44 from New York, Cairo, Hong Kong, Bogotá
- Average distance: 1.44 from New York, Cairo, Hong Kong, Mexico City
- Average distance: 1.44 from Madrid, Cairo, Hong Kong, Mexico City
- Average distance: 1.44 from Madrid, Baghdad, Hong Kong, Mexico City
- Average distance: 1.44 from London, Cairo, Hong Kong, Bogotá
This time the full average histogram looks like this:
Once again, we can ignore the peak and look more to the average shape and values.
And the map covered with four players look like this:
Checking the histogram for 1 and 2 players
For the sake of completeness, I offer you the same histogram for one and two players.
How the graph cover improve with the player count
Let’s see how the best cover positions improve the average distance when adding more players.
- Going from 1 Player to 2 players – Best Avg Dist goes from 3.44 to 2.08 A difference of 1.36
- Going from 2 players to 3 players – Best Avg Dist goes from 2.08 to 1.62 A difference of 0.46
- Going from 3 Players to 4 players – Best Avg Dist goes from 1.62 to 1.44 A difference of 0.18
| Player Count | Best avg. dist | Mean avg. dist | Worst avg dist | Median avg dist |
| 1 | 3.44 | 4.054 | 5.2083 | 3.948 |
| 2 | 2.08 | 2.985 | 4.7083 | 2.917 |
| 3 | 1.62 | 2.431 | 4.6042 | 2.354 |
| 4 | 1.44 | 2.080 | 4.1875 | 2.021 |
Adding more and more players makes a smaller and smaller difference on the best average distance…
But the best case progression only shows part of the picture. The Mean, Median, and Worst values make a case for the idea that it’s not as bad as it seems!
It is kind of expected that adding player ends up offering diminishing returns when covering the graph. And if you take into account the fact that when playing, diseases spreading occurs between each individual player turn, having more people kind of ends up not helping that much.
This is to be expected from a game, after all, the game designer certainly put a lot of thoughts into balancing the difficulty with the number of players.
But it’s always worth it to optimize the player positions!
Shrinking the graph
If we think about the graph size in term of travel distance, adding players to the map is akin to shrinking the graph. But there is a more literal way of ‘shrinking the graph’ than adding players.
In fact, Pandemic provides us with an explicit mechanism to do so: Adding new connections between cities!
The role of research Stations
An action a player can take during the game is to build a Research Stations. Those research stations are where a player can develop cures for the diseases.
But aside from that essential role, Research stations have the side benefits of adding fast travel routes between any city containing such a station. They are de facto connecting cities you choose.
Well, it is not exactly the same since it only allow players to travel on those connections. Diseases can’t spread through research stations in the game… which is a good thing!
As you can imagine, a single research station won’t affect the graph. But as soon as 2 or more are built, new connections appear, allowing player to travel and, for possibly, cutting short the previously longest routes on the map!
The first research Station
In the game rules, the game start with a Research Station already built in Atlanta, since it is the home of the real life Center for Disease Control (CDC).
While it gives you a research station right form the start, we will see that it is not necessarily the best possible location to put a Research station.
Some people may decide to play by slightly different rules, and try starting with a research station in a different city.
And, as I’m far from perfect, I forgot to add this restriction when calculating the best way to reduce the graph size at first. So I had to re-do the calculations with Atlanta as the first station!
Deciding not to let a good mistake go to waste, I will present both ways of optimizing the positions, with the first station in Atlanta, but also with the optimal position if no such constraint was to exist.
This will have the added benefit of giving us some perspective on the impact of optimal positions on graph reduction!
Optimally positioning research stations
Where you build research stations is of paramount importance. Proof by the absurd: 2 research stations built on adjacent cities won’t change anything to the graph: There are already connection in place for those.
The question is then: Where to build stations to maximize your mobility in the graph ?
And the answer is not necessarily where you would think!
Our first instinct could be to minimize the worse case scenario by building the on the 2 cities the farthest apart on the map.
As our worst eccentricity example, we could connect Johannesburg and Beijing.
If we do so the Eccentricity on the game change like this, lowering the maximum eccentricity on the map from 9 to 8.
But this is not be the best way to proceed. There are far more effective ways of adding connections to reduce the graph!
Consider the following two option:
- Optimizing for the worst cases -> Find the locations that would minimize the average eccentricity on the map
- Optimizing for the average case -> Find the locations that would minimize the average distance between all cities
Those two approaches are different, but I think both valid, so I will present you the top 5 of each for different group of cities.
Research Stations reducing the average eccentricity on the map
Initial Average Eccentricity: 7.3542
This can be reduced quite a bit, I ran a computer program considering all possible pair of cities to built research stations, keeping only the lowest 5 average eccentricity on the map:
First, when forcing the first research station to be in Atlanta:
| 2 Research Stations locations | New Average Eccentricity | Improvement |
|---|---|---|
| Atlanta, Cairo | 6.6667 | 9.35% |
| Atlanta, Khartoum | 6.9167 | 5.95% |
| San Francisco, Istanbul | 6.9375 | 5.67% |
| Atlanta, Baghdad | 6.9583 | 5.38% |
| Atlanta, Kinshasa | 6.9792 | 5.10% |
Then, allowing any pair of city for the same thing:
| 2 Research Stations locations | New Average Eccentricity | Improvement |
|---|---|---|
| Hong Kong, São Paulo | 6.0208 | 18.13% |
| Kolkata, São Paulo | 6.0833 | 17.28% |
| San Francisco, Cairo | 6.1042 | 17.00% |
| Bangkok, São Paulo | 6.1458 | 16.43% |
| San Francisco, Istanbul | 6.1667 | 16.15% |
As you can see, removing the Atlanta constraint double the gains made on the average eccentricity! This is not a small difference, and kind of show the power of finding optimal graph position (when we are allowed!)
To give you some visual information, here is a map showing each city eccentricity when building a research station in Hong Kong and Sao Paulo, the best pair to be found.
Note here that the best eccentricity found of the map is now 4 instead of 6 !
Best Average distance on the map
If we do a similar exercise but minimizing average distance between cities instead of the average map eccentricity, we get different pairs. This time remember, we are addressing the average case instead of the worse case!
The initial average distance between any 2 cities is: 4.1401
Given total free reign, the following pairs of Research Stations locations would give the best improvement for average travel:
| 2 Research Stations locations | New Average Distance between cities | Improvement |
|---|---|---|
| ‘Algiers’, ‘Hong Kong’ | 3.6941 | 10.77% |
| ‘Madrid’, ‘Hong Kong’ | 3.6950 | 10.75% |
| ‘Cairo’, ‘Hong Kong’ | 3.6986 | 10.66% |
| ‘Hong Kong’, ‘São Paulo’ | 3.7039 | 10.54% |
| ‘Istanbul’, ‘Hong Kong’ | 3.7110 | 10.36% |
But if we are to limit ourselves to the official rules (with Atlanta), then the optimal locations are the following:
| 2 Research Stations locations | New Average Distance between cities | Improvement |
|---|---|---|
| ‘Atlanta’, ‘Cairo’ | 3.9131 | 5.48% |
| ‘Atlanta‘, ‘Istanbul’ | 3.9246 | 5.20% |
| ‘Atlanta‘, ‘Baghdad’ | 3.9264 | 5.16% |
| ‘Atlanta‘, ‘Karachi’ | 3.9459 | 4.69% |
| ‘Atlanta‘, ‘Delhi’ | 3.9486 | 4.63% |
Once again, by constraining the first research station to Atlanta, the effective improvement on the average distance on the graph is almost cut in half! Almost shocking!
The only silver lining here is that this time the best Average distance locations for research station ends-up being close to the best location minimizing the average eccentricity on the map! This at least has the benefit of making the trade-off decision quite easy between optimizing for the average or worse case scenario!
Let’s see what happens if we add more research stations…
Best Average Distance With 3 Research Stations
Adding research station has a deeper impact than adding players. Because all Research Station being connected, if you add a third Station, you do not add ONE link to the graph, but TWO. On to each station already built on the map… Which is not negligeable at all!
So it almost double the improvement from 2 Research Station when unconstrained. But it almost TRIPLE the improvement from the Atlanta constrained one !!!
The reason for this is quite interesting. Similarly to the player count, you cannot avoid the diminishing return of adding connections. If you were to add all the possible connections, the end result would only be an average of 1.0… However, by carefully choosing where to put Research Station, you maximize the possible with relatively few locations.
The Atlanta penalty does not disappear, but quickly fade when you can put new connections to compensate the poor first placement choice.
| 3 Research Stations locations | New Average Distance between cities | Improvement |
|---|---|---|
| ‘Atlanta’, ‘Cairo’, ‘Hong Kong’ | 3.4610 | 16.40% |
| ‘Atlanta’, ‘Istanbul’, ‘Hong Kong’ | 3.4752 | 16.06% |
| ‘Atlanta’, ‘Cairo’, ‘Shanghai’ | 3.5089 | 15.25% |
| ‘Atlanta’, ‘Algiers’, ‘Hong Kong’ | 3.5186 | 15.01% |
| ‘Atlanta’, ‘Baghdad’, ‘Hong Kong’ | 3.5204 | 14.97% |
| 3 Research Stations locations | New Average Distance between cities | Improvement |
|---|---|---|
| ‘Istanbul’, ‘Hong Kong’, ‘Bogotá’ | 3.3617 | 18.80% |
| ‘Cairo’, ‘Hong Kong’, ‘Mexico City’ | 3.3617 | 18.80% |
| ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 3.3635 | 18.76% |
| ‘Istanbul’, ‘Hong Kong’, ‘Mexico City’ | 3.3759 | 18.46% |
| ‘Cairo’, ‘Hong Kong’, ‘Miami’ | 3.3848 | 18.24% |
Best Average Eccentricity with 3 research station
If we go back to our worse case scenario, choosing the location that will minimize the average eccentricity on the map, having 3 Research station will have the following effect:
First with a station in Atlanta:
| 3 Research Stations locations | Average Eccentricity | Improvement |
|---|---|---|
| ‘Atlanta’, ‘Cairo’, ‘Hong Kong’ | 5.8333 | 20.68% |
| ‘Atlanta’, ‘Baghdad’, ‘Hong Kong’ | 5.8542 | 20.40% |
| ‘Atlanta’, ‘Istanbul’, ‘Hong Kong’ | 5.8958 | 19.83% |
| ‘Atlanta’, ‘Cairo’, ‘Shanghai’ | 5.9167 | 19.55% |
| ‘Atlanta’, ‘Cairo’, ‘Taipei’ | 5.9375 | 19.26% |
And here without constraint:
| 3 Research Station locations | Average Eccentricity | Improvement |
|---|---|---|
| ‘Cairo’, ‘Hong Kong’, ‘Mexico City’ | 5.1875 | 29.46% |
| ‘Istanbul’, ‘Hong Kong’, ‘Mexico City’ | 5.2292 | 28.90% |
| ‘Baghdad’, ‘Hong Kong’, ‘São Paulo’ | 5.2708 | 28.33% |
| ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 5.2917 | 28.05% |
| ‘Tehran’, ‘Hong Kong’, ‘São Paulo’ | 5.2917 | 28.05% |
Interestingly, the best eccentricity result trio is once again the best average distance trio when we are given no choice about the first Research Station in Atlanta. The ratio of the improvement is now 2/3 instead of half, which is improving, but given the choice, you would be better off with a center in Mexico City than in Atlanta!
However, this time the unconstrained choice still has a way better effect on the worse case than on the average case… This is interesting! It means that eccentricity is a trickier metric to optimize for…
If we look at it on the map, we still get some interesting information:
With the best result on a map with an average eccentricity of 5.18, and the extreme keep dropping with a new highest eccentricity of 6, and lowest eccentricity of 3 !
Best Average Distance with 4 Research Stations (One in Atlanta)
| 4 Research Stations locations | Average Distance between cities | Improvement |
|---|---|---|
| ‘Atlanta’, ‘Istanbul’, ‘Hong Kong’, ‘São Paulo’ | 3.2571 | 21.33% |
| ‘Atlanta’, ‘Istanbul’, ‘Hong Kong’, ‘Bogotá’ | 3.2589 | 21.28% |
| ‘Atlanta’, ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 3.2589 | 21.28% |
| ‘Atlanta’, ‘Cairo’, ‘Hong Kong’, ‘Lima’ | 3.2651 | 21.13% |
| ‘Atlanta’, ‘Baghdad’, ‘Hong Kong’, ‘São Paulo’ | 3.2748 | 20.90% |
| 4 Research Stations locations | Average Distance between cities | Improvement |
|---|---|---|
| ‘Cairo’, ‘Chennai’, ‘Shanghai’, ‘Mexico City’ | 3.1888 | 22.98% |
| ‘London’, ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 3.1897 | 22.96% |
| ‘Essen’, ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 3.1897 | 22.96% |
| ‘Essen’, ‘Cairo’, ‘Hong Kong’, ‘Mexico City’ | 3.1897 | 22.96% |
| ‘New York’, ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 3.1941 | 22.85% |
As predicted from the 3 Research station case, the average distance gain is getting quite smaller, and the difference between the Atlanta Constrained case and the unconstrained is even smaller!
This is not to say that you can build anywhere with the same efficiency. But careful choose location tend to make the result converge!
Best Average Eccentricity with 4 research station
Top 5 groups of 4 cities to minimize average eccentricity, with Atlanta:
| 4 Research Stations locations | Average Eccentricity | Improvement |
|---|---|---|
| ‘Atlanta’, ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 5.0625 | 31.16% |
| ‘Atlanta’, ‘Cairo’, ‘Hong Kong’, ‘Lima’ | 5.0833 | 30.88% |
| ‘Atlanta’, ‘Istanbul’, ‘Hong Kong’, ‘Bogotá’ | 5.1042 | 30.59% |
| ‘Atlanta’, ‘Cairo’, ‘Hong Kong’, ‘Mexico City’ | 5.1042 | 30.59% |
| ‘Atlanta’, ‘Istanbul’, ‘Hong Kong’, ‘Lima’ | 5.1458 | 30.03% |
Without forcing Atlanta:
| 4 Research Station locations | Average Eccentricity | |
|---|---|---|
| ‘New York’, ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 4.7083 | 35.98% |
| ‘New York’, ‘Cairo’, ‘Hong Kong’, ‘Mexico City’ | 4.7292 | 35.69% |
| ‘New York’, ‘Cairo’, ‘Hong Kong’, ‘Lima’ | 4.7500 | 35.41% |
| ‘Madrid’, ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 4.7500 | 35.41% |
| ‘Madrid’, ‘Cairo’, ‘Hong Kong’, ‘Mexico City’ | 4.7500 | 35.41% |
Once again, the worse case scenario keep improving with more station, and the gap with Atlanta constrained map is shrinking, but is still not negligible.
Here is the best case, still represented on the map:
Best Average distance with 5 research stations
Finally, here are the results for the best location for 5 Research Stations that will minimize the Average distance between cities.
The improvement is still slightly better when we don’t have to built in Atlanta. And we still have a 4-5% improvement of the overall average distance compared to the results with 4 Research stations. This is less than the 9-10% gain we had at the beginning, but this is still making the world measurably smaller.
| 5 Research Stations locations | Average Distance between cities | Improvement |
|---|---|---|
| ‘Atlanta’, ‘Istanbul’, ‘Chennai’, ‘Shanghai’, ‘São Paulo’ | 3.0842 | 25.50% |
| ‘Atlanta’, ‘Essen’, ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 3.0851 | 25.48% |
| ‘Atlanta’, ‘Istanbul’, ‘Hong Kong’, ‘Kinshasa’, ‘Bogotá’ | 3.0869 | 25.44% |
| ‘Atlanta’, ‘Istanbul’, ‘Chennai’, ‘Shanghai’, ‘Bogotá’ | 3.0878 | 25.42% |
| ‘Atlanta’, ‘Cairo’, ‘Chennai’, ‘Shanghai’, ‘Bogotá’ | 3.0878 | 25.42% |
When no restraints on location:
| 5 Research Stations locations | Average Distance between cities | Improvement |
|---|---|---|
| ‘Paris’, ‘Karachi’, ‘Hong Kong’, ‘Khartoum’, ‘Mexico City’ | 2.9876 | 27.84% |
| ‘Paris’, ‘Karachi’, ‘Hong Kong’, ‘Khartoum’, ‘Bogotá’ | 2.9956 | 27.64% |
| ‘Essen’, ‘Karachi’, ‘Hong Kong’, ‘Khartoum’, ‘Mexico City’ | 3.0009 | 27.52% |
| ‘Paris’, ‘Delhi’, ‘Shanghai’, ‘Khartoum’, ‘Mexico City’ | 3.0018 | 27.49% |
| ‘Paris’, ‘Karachi’, ‘Hong Kong’, ‘Kinshasa’, ‘Mexico City’ | 3.0027 | 27.47% |
Top 5 groups of 5 cities to minimize average eccentricity:
Similarly the improvement on the average eccentricity front keeps rolling with 5-6% improvement.
With a nice touch that the worse eccentricity can now be reduced to 5, instead of the initial 9.
The Best locations for optimizing the worse case (eccentricity) with one Station in Atlanta
| 5 Research Stations locations | Average Eccentricity | Improvement |
|---|---|---|
| ‘Atlanta’, ‘New York’, ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 4.6667 | 36.54% |
| ‘Atlanta’, ‘Essen’, ‘Cairo’, ‘Hong Kong’, ‘Bogotá’ | 4.6667 | 36.54% |
| ‘Atlanta’, ‘New York’, ‘Cairo’, ‘Hong Kong’, ‘Lima’ | 4.6875 | 36.26% |
| ‘Atlanta’, ‘New York’, ‘Cairo’, ‘Hong Kong’, ‘Mexico City’ | 4.6875 | 36.26% |
| ‘Atlanta’, ‘Madrid’, ‘Cairo’, ‘Hong Kong’, ‘Lima’ | 4.6875 | 36.26% |
The best location overall for 5 research station to reduce the average Eccentricity.
| 5 Research Station locations | Average Eccentricity | Improvement |
|---|---|---|
| ‘Paris’, ‘Karachi’, ‘Hong Kong’, ‘Khartoum’, ‘Mexico City’ | 4.2703 | 41.93% |
| ‘New York’, ‘Cairo’, ‘Delhi’, ‘Shanghai’, ‘Mexico City’ | 4.2917 | 41.64% |
| ‘New York’, ‘Cairo’, ‘Delhi’, ‘Hong Kong’, ‘Bogotá’ | 4.2917 | 41.64% |
| ‘New York’, ‘Cairo’, ‘Delhi’, ‘Hong Kong’, ‘Mexico City’ | 4.2917 | 41.64% |
| ‘New York’, ‘Cairo’, ‘Chennai’, ‘Shanghai’, ‘Bogotá’ | 4.2917 | 41.64% |
That’s it!
I suppose we could consider other measures, maybe taking into account how many player are close by, or a compound metric taking into account both Average distance, and eccentricity.
But I think that will do for now…
Conclusion
Even if games are always more messier in real life than it theory, I think that looking at the best case and worst case offer some insight on where players can position themselves and build research stations.
Otherwise I hope you did gain some insights on how players and research station positioning interact with the graph, beyond the simple idea of simply visually spreading out over the map!
A more involve analysis that we could take is to to apply the optimization algorithm as the game progress and some player become more tied to certain regions. Or maybe try to solve real time research station situation based on where people are and where they need to go. (As opposed as to solve to optimize overall graph metric, not taking into account the pandemic situation on the map.).
In all case, thanks to all who have read until the end!
If I missed something, or you have other suggestions of map and important question to address, let me know in the comments!