LAND OPERATIONS DIVISION
Analysis of Hierarchical Games
| Project Title |
| "Analysis of Hierarchical Games." |
| Industry Contact |
| George Galanis |
| email: george.galanis@dsto.defence.gov.au |
| Tim Ferris |
| email: timothy.ferris@unisa.edu.au |
| Moderators |
| Vladimir Ejov |
| School of Mathematics and Statistics |
| University of South Australia |
| Mawson Lakes, SA 5095 |
| Tel: 08 8302 3035 |
| Fax: 08 8302 5785 |
| email:vladimir.ejov@unisa.edu.au |
| Elliot Tonkes |
| Department of Mathematics |
| The University of Queensland |
| St Lucia, Queensland 4072 |
| Tel: 07 336 53260 |
| Fax: 07 336 51477 |
| email: ejt@maths.uq.edu.au |
Analysis of Hierarchical Games
A
critical issue in the operation of an organisation, such as an army, is
the training of individuals and the
subsequent training of groups of variable size that must work together to
achieve the large and complex goals of the organisation.
One of the attributes of such organisations is the hierarchical
structure of both the organisation and the tasks, where the goals of the
organisation are divided into many subtasks.
The subtasks, in many situations, permit diverse solution methods,
or tactical approaches.
Achievement of the larger goal may be dependent on the performance
of the sub tasks, and the dependence may not be a simple aggregation of
sub-tasks, i.e. you might win the battle, but subsequently lose the war.
The training need involves the requirement that trainees learn both
individual skills and team skills that enable them to work effectively and
efficiently for the achievement of the larger goals of the organization.
Sometimes achievement of the larger goals involves the
counter-intuitive performance of some activities in a manner that is, at
the sub-task level, apparently sub-optimal.
What is needed is a quantitative theory that informs us of the
optimum individual and collective training requirements that will provide
optimal performance of the larger group in the target environment.
Given the difficulty of theorising about the army, with the risk of
developing a theory that cannot be tested, we are looking for analogs
where the analog is simpler and the outcomes are clearer and with a
testable theory. The
hope is that this will provide insights that can ultimately be transferred
to the complexity of the army or the military in general.
The
Tennis Problem
One
such analog appears to be the sport of tennis.
The hierarchical scoring structure of tennis (game, set, match)
results in not all points having equal value to each side, and thus
seeming to call for different strategies in order to try to proceed
through each point expending the effort that the player specific value of
the point justifies. There
are papers that have investigated some of the issues in tennis (e.g. [1],
[2]). It can be shown
numerically that there is some advantage in selectively reducing effort
expended to win some points in the greater goal of seeking to win the
match. Attached is a paper
draft [3] that investigates some of the surprising effects on
strategy/tactics arising from the hierarchical scoring structure and its
effects mentioned above. The
numerical method has been implemented in Excel using a simple probability
based, energy attrition model. The
assumption is that one of the players is playing to maximal effort at all
times and the other can vary effort in response to the situation.
The problem then reduces to one of optimisation for the player who
can control their effort. The
numerical model suggests a strategic advantage effected through the
strategic/tactical process of establishing criteria to put certain levels
of effort into the play for a particular point.
The
more general problem, and one that would be more useful to solve, relates
to the situation where each player can choose to vary point-wise strategy
in response to the match situation. A
solution to this problem would seem to be useful in developing an
understanding of the sensitivity of outcomes in military situations to
choice of strategic options during the various hierarchical levels of a
conflict.
For
example, commanders in planning a course of action are often faced with
the dilemma of sending in a reserve force behind a leading force.
The dilemma is that an adversary expecting a reserve may either
reinforce their defence or leave the battlefield altogether, either way
the effect of surprise may be nullified and resources wasted.
This situation is conceptually identical to the dilemma faced by a
tennis player who must win a difficult point, but is on a second serve.
Should the player serve safely, the opponent may be waiting and
take advantage of an easy shot, but if the server serves with maximum
force the opponent may be put in a difficult position, but there is a
greater risk of a double fault. Such
situations arise in many other conflict situations, for example in
economics and trade negotiations. The
issue here is take into account the effect of the hierarchical nature of
the problem.
An interesting solution would enable evaluation of the effect of variation of the rules of the game, such as variation of the number of hierarchical levels in the game, or the scoring rules. This would be beneficial because it would develop means to enable investigation of the sensitivity of the target situation to the wide range of variations of situation that may be encountered.
Desired
Outcomes
| Our
interest is to obtain insights in relation to the following issues: |
|
| a. | The non-equivalence of value of the points depending on the current score
in the game, set and match. |
| b. | The effect on the probability of winning the match arising from depleting
available capability through the effort to win the point. |
| c. | The ability to generalise from tennis to a more complex game structure
(i.e. where there is not the convenience of discrete play events between
just the two equivalent players or teams that are present in tennis.) |
| d. | The definition of a model of match outcome into which the effect of
morale or other psychological effects can be incorporated. |
References
[1]
M. Walker & J. Wooders, Equilibrium play in matches: Binary Markov
games, 7 July 2000, www.u.arizona.edu/~mwalker/BMG.pdf
[2]
M. Walker & J. Wooders, Minimax play at Wimbledon, 7 November 1998,
American Economic Review, www.u.arizona.edu/~mwalker/
WimbldnScan990910.pdf
[3]
Ferris, submitted, Emergence:
An Illustration of the Concept for Education of Young Students, INCOSE
2003, Washington, July.
Related
Problems of Interest to DSTO
Another
situation that is of interest to DSTO is the recognition of the analogue of
the fortress position in chess.
In chess a fortress position is one of a wide range of positions in
which neither player is able to force a win because the combination of
pieces on the board and their current positions prevent such an outcome.
Human players of reasonable ability are able to recognise such
situations as they arise, but the experience of the Deep Blue v. Kasparov
tournament shows that it is not yet possible for computers to recognise
fortress positions except on a case-by-case basis using a database of known
fortress positions. A
generic fortress recognition method has not yet been achieved.
The
military analog of the fortress position would be the situation where a
particular position and forces combine to produce a situation that neither
side has a reasonable chance of winning.
The player on the friendly force must design a tactic that uses
optimal movement to suppress and eliminate opponent forces.
The references in [4,5,6] give some examples using Intelligent Agent
(IA) systems.
Our
interest is to obtain insights in relation to the optimum solution for the
game whether it is a chess board game or a wargame exercise.
We are also interested in the possibility that we may be able to
generalise to a more complex game structure where there is not the
convenience of discrete play events between just the two players or teams.
Also of interest are the generation and application of models where
the effect of morale or other psychological effects can be incorporated.
Additional
References
[4]
Pamela McCauley-Bell and Rhonda Freeman, “Uncertainty Management in
Information Warfare”, 1997 IEEE
International Conference, pp1942 –1947, vol.2.
[5] Applegate,
C.; Elsaesser, C.; Sanborn, J., “An architecture for adversarial planning
Systems”, Man and Cybernetics, IEEE Transactions on , Volume: 20 Issue:1
Jan.-Feb. 1990, Page(s): 186 –194.
[6] Fiebig,
C.; Hayes, C.; Schlabach, J., "Human-computer interaction issues in a
battlefield reasoning system”, Systems, Man, and Cybernetics, 1997.
Computational Cybernetics and Simulation., 1997 IEEE International
Conference on , Volume: 4 , 1997,