A fast algorithm for unit level team resource allocation in a game environment

This paper deals with the problem of allocating tasks to members of a non-homogeneous team of entities that is in conflict with another team of non-homogeneous entities. Each team is assumed to have a finite number of tasks that need to be assigned to its members. The task assignment within each team is done in such a way as to optimize an overall team objective function which depends not only on the task assignments in that team, but also on the task assignment in the adversarial team as well. In this sense, the task assignment in each team must take into account the task assignment in the other team. Because of the presence of an adversarial relationship between the two teams, this problem is best formulated and solved within the framework of game theory. The Nash strategy is an important solution concept for this type of problems. Task assignments that are formulated as Nash strategies yield an equilibrium in that no team has an incentive to unilaterally alter the assignments in an attempt to improve its position. An issue that arises when solving for the Nash strategies is the dimensionality of the search space, which quickly becomes overwhelming even with relatively small numbers of entities and tasks. In this paper we discuss an algorithm, called unit level team resource allocation (ULTRA), which overcomes this scalability issue. We also present simulation results to illustrate the performance of this algorithm when compared to an exhaustive search.