# Improving Computational Efficiency in Crowded Task Allocation Games with Coupled Constraints
## 4 DSA with Sampling  
For equilibrium selection, the DSA algorithm was considered to be the basis for improvement. The DSA is preferred over other algorithms such as log-linear learning for its relatively low overhead, good solutions [2; 24] and ease of decentralization. In theory, DSA uses a best-reply dynamic given a complete action set and therefore, when considering a very large action set, DSA requires significant computational power and time to determine the best reply, making implementation impractical. Hence, by somehow placing a limit on the number of evaluations required, it is possible to implement DSA in a game with significant number of tasks.  
One obvious way to do so will be to constrain the action set of every agent to reduce the computational load, where at each iteration, the action set is randomly sampled with a pre-defined sample size \(s\) (Algorithm 4, Line 4). It is necessary to further ensure that the null action, which is always feasible, is included in the constrained action set so that agents will always have a feasible action to consider. An agent will then choose to either maintain its action, or select an action in the constrained set using the best-reply dynamics. [PERSON] [26] took a similar approach in his payoff-based implementation of log-linear learning albeit for different reasons, and consider only one randomly chosen action at every iteration, without the restriction of having a null action. In our implementation, the rate of convergence is expected to improve due to the reduction in number of evaluations required at every iteration. Recall that the motivation for using a parallel degree of execution in DSA is to introduce stochasticity into the model in hopes of escaping from a local optimum. This also means that the search path taken to select the Nash equilibrium is stochastic and in a problem with multiple Nash equilibria, the game can terminate at either equilibrium when played multiple times despite having similar levels of parallel degree of execution. Instead of using parallel executions, stochasticity is introduced into the equilibrium selection through having constrained action sets. Intuitively, DSA with sampling will still arrive at a Nash equilibrium as \(t\rightarrow\infty\). A basic implementation of the game-theoretic coupled-constraint task allocation is shown in Algorithm 4.  
```
1:Input:\(\mathcal{N},\mathcal{A},s,t_{\text{con}},t=1,T=1,a_{T=0}=\mathbf{0}\)
2:while\(t\leq t_{\text{con}}\)do
3:for\(i\in\mathcal{N}\)do
4:\(\mathcal{A}_{i,T}=datasample(\mathcal{A}_{i},s)\)
5:\(\text{assignment}_{i,T-1}=schedule(a_{i,T-1},a_{-i,T-1})\)
6:\(u_{i,T-1}=utility(\text{assignment}_{i,T-1})\)
7:\(m\mu=0,\text{bestAction}_{i,T}=a_{i,T-1}\)
8:for\(a_{i,T}\in\mathcal{A}_{i,T}\)do
9:\(\text{assignment}_{i,T}=schedule(a_{i,T},a_{-i,T-1})\)
10:\(u_{i,T}=utility(\text{assignment}_{i,T})\)
11:if\(u_{i,T}-u_{i,T-1}>m\mu\)then
12:\(m\mu=u_{i,T}-u_{i,T-1}\)
13:\(\text{bestAction}_{i,T}=a_{i,T}\)
14:endif
15:endfor
16:\(a_{i,T}=\text{bestAction}_{i,T}\)
17:endfor
18:if\(a_{i,T}=a_{i,T-1}\quad\forall i\in\mathcal{N}\)then
19:\(t=t+1\)
20:else
21:\(t=0\)
22:endif
23:\(T=T+1\)
24:endwhile
```  
**Algorithm 4** Game-Theoretic ImplementationThe proposed equilibrium selection algorithm should have a lower dependency on the number of tasks and the rate of convergence is affect by two main parameters--the number of confirmations \(t_{\text{con}}\) (Algorithm 4, Line 2) and the sample size \(s\) (Algorithm 4, Line 4). Therefore, by carefully varying the number of confirmations and sample size, the equilibrium selection will be capable of satisfying the time requirements of the game.