## Two proofs about the Diplomacy rulesAs said earlier, the interpretation of the official rulebook is encoded in the equations, while any follow up is a matter of mathematics. In this chapter we will prove two properties of the rules. But first, I have to introduce the notion of a “dependency graph”. If we look again at figure 9:
Figure 9 repeated.Then we can make a directed graph between the dependencies of the orders: Figure 11.The arrows no longer represent Some people might like to draw dependency arrows in the opposite direction: however, this way the dependency arrows have the same direction as the movement, and in the case of the simple recursive algorithm, recursion is entered in the direction of the arrow. In the dependency graphs we only look at the real In case of the convoy paradox of figure 7:
Figure 7 repeated.The dependencies are as follows: Figure 12.Although the army in Tunis plays a major role in this convoy paradox, the resolution of the Tunis order is not part of the cyclic dependency. In resolving the support order of Fleet Greece it is important to know whether the fleet in the Ionian Sea will start the convoying operation or not, but the success or failure of the Tunis order is irrelevant. This example shows that there is a subtle difference between a dependency on the
This subtle difference occurs also in much simpler situations. Consider the bounce situation of figure 6:
Figure 6 repeated.If we remove the move orders for Berlin and Warsaw from the order set, then the army
in Bohemia could advance. So the resolution of the Bohemia order depends on the
existence of the Berlin and Warsaw orders. However, if we look at the equations,
then we see that the resolutions of the Berlin and Warsaw orders are of no importance
to the resolution of the Bohemia order. To adjudicate the Bohemia order we need to
calculate the Figure 13.The dependency graph indicates (correctly) that after resolving Munich, any of the orders Berlin, Bohemia or Warsaw can be adjudicated. Having established the concept of a dependency graph, we now want to prove the following: THEOREM I
No order can be part of two different cycles of dependencies. This means that an order set with the following dependency graph cannot exist: Figure 14.Both To prove this theorem, we have to distinguish between 6 types of orders, which are listed in the following table:
The dependencies in the last column list the type of orders on which the resolution of the order can depend directly or indirectly. The set of support orders is split between orders of type D and orders of type E. The purpose for this split is to distinguish between orders that are subject to the dislodgement rule (a support is cut when it is dislodged), and those that are not. Formally, the dislodge rule would still apply for orders of type E: however, the rule is not relevant for that type, since the support is already cut by the simple fact that the unit is being attacked by the unit that may dislodge. Again, remember the difference between a dependency on the existence of an order
and the resolution of an order. Support orders of type E can be cut due to the
The detailed proof of each of the dependencies can be derived from the equations and is left as an exercise for the reader. When we have a situation on the board, we mark every dependency and every order that is in a cycle. We cannot remove the unmarked orders from the scene, because those orders can play a role in the adjudication of the marked orders in various ways. If we observe the dependencies, then the marked orders (connected by marked dependencies) form pockets (islands) that consist entirely of orders of type A, or a mixture of B, E and F. Still, a single pocket may contain an order that is part of multiple cycles. For a pocket that consists only of orders of type A, it is rather clear that these orders form one circular movement, with all orders in one cycle. The same counts for a pocket with orders of type B, E and F, because a movement of type B can only disrupt one convoy, a support of type E can only support one unit, and a convoy of type F can only convoy one unit. Although the above reasoning may look obvious, it gave me a headache to get the right arguments. The tricky part is that the orders that can influence the order of the row are written down in the third column of the table. Thus, an order of type B, E, or F can only be influenced by the resolution of an order of type B, E or F. However, to prove that a pocket of B, E and F orders cannot have orders that are part of multiple cycles, we look at the dependencies in the opposite direction (the influence of the order). Thus, the overall proof consists first of limiting the scope to pockets of certain types of orders, and second of proving that those pockets constitute a single cycle. For the convoy paradoxes, in the second step we look at the dependencies in the opposite direction. This ends the proof of Theorem I. Theorem I implies that if we have a cycle, then any order on which the cycle depends, can be resolved first. Consider the dependency graph based on figure 9 drawn in figure 11: Figure 11 repeated.We maybe could extend the situation and make the success of the Skagerrak order
dependent on other orders. However, we could never make the resolution of the
Skaggerak order dependent, directly or indirectly, on North Sea, Norway, or
Norwegian Sea. If so, the North Sea order would be in the cycle This is true in general, meaning that in case of a cycle, all orders on which the cycle depends can be resolved first. This counts even when the orders on which the cycle depends contain an independent cycle. Consider the following dependency relationship: Figure 15.In such a situation, the Given the fact that any order on which a cycle depends can be resolved first, we want to prove: THEOREM II
In case of the following conditions: - There is a cycle;
- All other orders on which the resolution of one or more orders in the cycle depends, and which are not part of the cycle itself, are resolved;
- The cycle has a unique resolution.
Then there is at least one order in the cycle that can be resolved based only on partial information. We prove this by contradiction. That is, we assume: - There is a cycle;
- All other orders on which the resolution of one or more orders in the cycle depends, and which are not part of the cycle itself, are resolved.
- The cycle has a unique resolution;
- None of the orders can be resolved based only on partial information.
Back to the dependency graph of figure 11: Figure 11 repeated.If the resolution of the order to Fleet Skagerrak makes the order to Fleet Norway irrelevant for purposes of resolving the order to Fleet North Sea (which is the case when this graph is based on the situation of figure 9), then the order of the North Sea can be adjudicated based on partial information. This means that if we respect the assumption that none of the orders in the cycle can be resolved with only partial information, the cycle may depend on other orders, but that those other orders may not make the dependencies on the orders within the cycle irrelevant. This restricts the dependency relations within the cycle. Suppose we have a
direct From the initial assumption we know that there is one exclusive resolution. From the restricted dependency relations, it follows that the opposite of the resolution must also be a resolution respecting the equations. But this contradicts the assumption that there is a single resolution. And this proves Theorem II. Theorems I and II together prove that an algorithm that can make decisions based on partial information will find the unique resolution for a cyclic dependency.
If you wish to e-mail feedback on this article to the author, and clicking
on the envelope above does not work for you, feel free to use the "
Dear
DP..." mail interface. |