misg_03.jpg (17206 bytes)

Back to Project List

 

   LAND OPERATIONS DIVISION

 

DSTO Home

Analysis of Hierarchical Games

 - The Tennis Problem

 - Desired Outcomes

 - Related Problems

 

 

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

 Back to top

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.

Back to top

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.

Back to top

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.

Back to top

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, Page(s): 3204 -3209 vol.4.

Back to top