Johns Hopkins Magazine -- April 1997
S C I E N C E    A N D    T E C H N O L O G Y

Can You Protect
The Roman Empire?

By Charles ReVelle

The first recorded location problem that I know of was approached by the Emperor Constantine in the 4th century. Constantine's challenge was to deploy the legions of Rome in such a way as to secure and protect his empire from invasion or insurrection.

In the 3rd century, when Rome dominated Europe, it was able to deploy 50 legions throughout the empire, securing even the furthermost areas. By the following century the empire had lost much of its muscle, however, and Rome's forces had diminished to just 25 legions. Emperor Constantine's problem: How to station legions in sufficient strength to protect the most forward positions of the empire without abandoning the core--namely Rome. He devised a new defensive strategy to cope with Rome's reduced power.

The problem is not "solved" in a mathematical sense, but a set of rules exists that defines when a solution is acceptable. Once you understand the rules, you can attempt to see if you can improve on Constantine's choice of deployment.

The Rules
Each set of six legions may be thought of as a "pebble," a unit of forces whose presence is sufficient to secure any one of the regions of the empire. The regions of the empire may be considered to be connected as shown below. Moving along the line between regions represents a "step," and for a region to be securable, a pebble must be able to reach it in just one step--to repel invaders or put down a revolt.

A region, then, may be thought of as either secured or securable. It is considered to be secured if it has one or more pebbles placed in it already. It is considered securable if a pebble can be deployed to that region in a single step. At any shift or movement from a region, two pebbles must initially be present together before one of them can be launched. That is, a pebble can only be deployed if it moves from an adjacent region where there is already another pebble to help launch it. This is analogous to the island hopping strategy pursued by General MacArthur in World War II in the Pacific theater--where movement only followed the chain of islands (secured areas).

Now that you know the rules, the challenge is to place just four pebbles in the eight regions of the empire.

Constantine's strategy
Constantine's placement could not protect the entire empire. He had to leave one region uncovered, that is unable to be reached, according to the rules, in a single step. Constantine placed two pebbles at Rome, a symbolic as well as strategic choice, and two at his new capital, Constantinople. With this deployment, each region of the empire could be reached by a pebble in just one step--except for Britain. To reach Britain required a pebble to move from Rome to Gaul, securing Gaul, and a second pebble to move from Constantinople to Rome, then from Rome to Gaul, and finally from Gaul to Britain, a total of four steps. It is no wonder that Britain was lost.

Here is another alternative, not necessarily better than Constantine's strategy, but it gives you an idea of possibilities. We will place one pebble in Gaul, two in Rome, and one in Constantinople. Britain can now be reached in two steps (a pebble from Rome to Gaul and a pebble from Gaul to Britain), better for Britain than before. However, Asia Minor is now not reachable in one step, but two (from Rome to Constantinople and Constantinople to Asia Minor). All the rest of the empire is reachable in just one step. It is not clear that this is better than Constantine's strategy. Although the number of steps to the worst-off nodes has been reduced to two, the number of regions more than one step away has gone from one to two.

Can you improve on Constantine's solution?
If you would like to try, here's how to evaluate the merit of the alternative. There are, for our purposes, two criteria. The first is the number of regions that cannot be reached in a single step. For Constantine's solution, that number is just one. The second is the number of steps it takes to reach the worst-off node. Again, for Constantine's choice, this number is four steps--to reach Britain.

If you can keep the number of nodes that can't be reached in one step to just one, and can reduce the maximum number of steps to reach that node to a number less than four, then you have done better than Constantine. Of course, you hit the jackpot if you can make all regions either initially secure or reachable in one step, given the rules.

I will tell you that it is possible to do better than Constantine, but I won't tell you how. If you do have success at allocating the pebbles, you should think about the consequences of a second war occurring somewhere in the empire. Of the situations you create, which would be better in the event of a second war at one of the unsecured regions? The answer, which I mailed in early February, is in a sealed envelope in the desk drawer of editor Sue De Pasquale. She has agreed to publish it in the next issue of the Johns Hopkins Magazine.

A final footnote
Although we can examine specific arrangements of a known number of regions, to my knowledge, no universal mathematical procedure has yet been published to solve this problem in the general case. The general case would have any number of regions in any arrangement and a number of pebbles specified in advance. I have recently made progress on the problem with my colleague Ken Rosing, progress we hope will be published soon. I would also like to acknowledge the marvelous paper that introduced me to this problem. It is "Graphing an Optimal Grand Strategy," by John Arquilla and Hal Fredricksen, which appeared in the Fall 1995 Military Operations Research.