# Improving Computational Efficiency in Crowded Task Allocation Games with Coupled Constraints
## 5 Results and Discussion
### Size of Samples  
To investigate the impact of variation in sample size, a dense allocation setting given in Table 10 is considered. The world remains as a 10-by-10 grid but the number of agents and tasks increased significantly and the sample sizes were varied to be 20, 40, 60, 80, and 100. The simulation results for the dense task allocation game are displayed in Figure 7, Tables 11-13.  
Predictably, the mean global score values increase with increasing size of sample. The sample sizes of 20, 40, 60, 80, and 100 provided each agent with exposure to approximately 0.3%, 0.6%, 0.9%, 1.2% and 1.4% of its entire action set, respectively. Such low levels of understanding of the action set usually means that the agreements are suboptimal since the probability of making improvements to the existing agreement is rather high. Despite the suboptimality of the solutions, it should be noted that a 5-fold increase in sample size from 20 to 100 led to improvements in score by a mere 5% as seen in Figure 8. The logarithmic increment trend for the global scores further supports our belief that agents can make reasonably good scheduling decisions despite having an incomplete, and possibly small, understanding of their action set in a dense task allocation setting.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Agents** & **15** & **Tasks** & **90** & **Parameters** & \\ \hline Engineer & 5 & Fire & 10 & Path length & 4 \\ Rescue & 5 & Casualty & 10 & Confirmations & 100 \\ Firefighter & 5 & Wreckage & 10 & Hold period & 4 \\  & \multicolumn{2}{c}{Casualty \(\xrightarrow{\text{dep}}\) Fire} & 10 & & \\  & \multicolumn{2}{c}{Casualty \(\xrightarrow{\text{dep}}\) Wreckage} & 10 & & \\  & \multicolumn{2}{c}{Wreckage \(\xrightarrow{\text{dep}}\) Fire} & 10 & & \\ \hline \hline \end{tabular}
\end{table}
Table 10: Crowded disaster relief operation details and simulation parameters.  
Figure 6: Mean computation times for various number of confirmations.  
More importantly, from Figure 9, the computation times were observed to increase exponentially with the sample size. Without the use of sampling in the equilibrium selection, a game-theoretic approach for task allocation in a dense emergency operation will simply be impractical. Using random sampling, the computation times were suppressed to provide reasonably good solutions, enabling game-theoretic implementations in emergency operations which tend to be crowded, complex, and time-sensitive. In the game simulated, the mean computation times for both the centralized and decentralized approach were kept well below 60 min and 10 min, respectively, when the sample sizes are kept smaller than 60. Feasibly good solutions were also obtained quickly when considering a sample size of only 20 in the simulations.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Sample Size** & **Mean** & **Standard Deviation** \\ \hline
20 & 795.294 & 21.166 \\
40 & 823.923 & 16.742 \\
60 & 825.086 & 21.365 \\
80 & 831.913 & 17.918 \\
100 & 839.281 & 18.486 \\ \hline \hline \end{tabular}
\end{table}
Table 11: Mean and standard deviation for global scores.  
Figure 7: Variations in global scores and computation times due to size of sample.  
_Appl. Sci._**2019**, 9, 2117  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Sample Size** & **Mean** & **Standard Deviation** \\ \hline
20 & 30.295 & 12.386 \\
40 & 80.517 & 35.030 \\
60 & 205.754 & 116.449 \\
80 & 542.142 & 376.058 \\
100 & 928.077 & 944.542 \\ \hline \hline \end{tabular}
\end{table}
Table 13: Mean and standard deviation for estimated decentralized computation times.  
Figure 8: Mean global score values for various sample sizes.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Sample Size** & **Mean** & **Standard Deviation** \\ \hline
20 & 404.854 & 165.431 \\
40 & 1093.975 & 476.654 \\
60 & 2804.496 & 1593.538 \\
80 & 7360.438 & 5086.329 \\
100 & 12,632.142 & 12,861.328 \\ \hline \hline \end{tabular}
\end{table}
Table 12: Mean and standard deviation for centralized computation times.