# Improving Computational Efficiency in Crowded Task Allocation Games with Coupled Constraints
## 5 Results and Discussion
### Feasibility of Game Model  
Several agents and disaster sites at random locations of the grid world were considered. The summary of the disaster relief operations and agent parameters are provided in Table 5 with 20 different relief operations, each simulated as a game to be played 20 times each. The reward for the successful completion of each task was given as a time-decaying function  
\[v_{k_{j}}(a)=v_{k_{j}}\exp(-\lambda_{k_{j}}f_{k_{j}}^{c}(a)) \tag{20}\]  
where \(v_{k_{j}}\) is the intrinsic value of the task, and \(\lambda_{k_{j}}\) is the discount factor for task \(k_{j}\), to reflect the urgency of the tasks and motivate the agents to work in an efficient manner.  
The feasibility of the game model using DSA with sampling can be inferred from the satisfaction of all coupled constraints in all the solutions obtained and the stochasticity of DSA is evident from the variation in global score values and computational times across the games for every operation scenario. For a centralized approach, the computational time for each game is below 1 min and when considering a synchronous decentralized approach, the estimated computational time falls to generally below 10 s. In a decentralized approach, each agent will run the scheduling algorithm, based on other agents' previous actions, independently. After evaluating the possible schedules, the agent will decide on its choice of action and communicate its decision to all other agents. Without explicitly considering the means of communication but assuming synchronous, the simulation times of a decentralized approach is estimated based on the slowest agent for each iteration and the overheads accumulated  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Fire** & **Casaulity** & **Wreckage** \\ \hline
**Fire** & 0 & 4 & 3 \\
**Casaulty** & 0 & 0 & 0 \\
**Wreckage** & 0 & 3 & 0 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Mission Temporal matrix.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Agents** & **6** & **Tasks** & **27** & **Parameters** \\ \hline Engineer & 2 & Fire & 3 & Path length & 4 \\ Rescue & 2 & Casaulty & 3 & Sample size & 20 \\ Firefighter & 2 & Wreckage & 3 & Confirmations & 100 \\  & & Casaulty \(\stackrel{{\text{dep}}}{{\longrightarrow}}\) Fire & 3 & Hold period & 4 \\  & & Casaulty \(\stackrel{{\text{dep}}}{{\longrightarrow}}\) Wreckage & 3 & \\  & & Wreckage \(\stackrel{{\text{dep}}}{{\longrightarrow}}\) Fire & 3 & \\ \hline \hline \end{tabular}
\end{table}
Table 5: Disaster relief operation details and simulation parameters.  
The schedule in Figure 3 represents but one of many possible solutions to the simulated scenario. For a complex multi-agent multi-task allocation problem coupled with a flexible hold period, multiple Nash equilibria are likely to exist and the stochasticity of the agents' actions due to random sampling leads to variation in the route of progression for each game, and thereby terminating at various different solutions. Regardless of the progression, the feasibility of the scheduling algorithm to satisfy the temporal constraints are evident from the complementary behaviors portrayed in the solution (e.g., A _rescue_-type agent (_A4_) waits at a _casualty_-type task (_13_) for a short period so that the temporal constraint which require the _rescue_ (_13_) to occur during _firefighting_ (_12_) can be satisfied, _rescue_-type agent (_A4_) attempts a _casualty_ rescue (_21_) task after the _wreckage_ (_20_) have been cleared by an _engineer_-type agent (_A1_), etc.)  
Moving beyond providing a feasible solution, the game should converge within a reasonably short time period to ensure the practically of a game-theoretic implementation in real-world operations and hence, further studies on the number of confirmations \(t_{\text{on}}\) and sample size \(s\), which are the main parameters influencing the rate of convergence, are presented in the subsequent sections.