# Improving Computational Efficiency in Crowded Task Allocation Games with Coupled Constraints
## 2 Preliminaries
### Game-Theoretic Models  
Multiple game-theoretic models for task allocation have been introduced [1; 2; 5; 6; 22] and our previous work introduced a game-theoretic model for task allocation problems with spatial coupled constraints [16]. Consider a set of agents \(\mathcal{N}=\{1,\cdots,n\}\) and a set of tasks \(\mathcal{M}=\{k_{1},\cdots,k_{m}\}\). The action set of agent \(i\), \(\mathcal{A}_{i}\), is then an ordered combination of all compatible tasks available inclusive of the null action \(\mathbf{0}\), and the action profile \(a_{i}\in\mathcal{A}_{i}\) is the (ordered) path that agent \(i\) will take. The reward of each task, \(u^{k_{j}}\), for a generic game-theoretic task allocation model is then defined as  
\[u^{k_{j}}(a)=\begin{cases}v_{k_{j}}(a)&\text{if }t^{c}_{k_{j}}(a)\leq t^{d}_{k_{j}}, \\ 0&\text{otherwise},\end{cases} \tag{2}\]  
where \(v_{k_{j}}(a)\) is the reward of the task, \(t^{c}_{k_{j}}(a)\) is the completion time, and \(t^{d}_{k_{j}}\) is the deadline. The amount of reward provided and the time which the task will be completed are both dependent on the collective action of all agents. To consider the spatial relationships between the tasks, the reward structure in Equation (2) can be adapted [16] to give  
\[u^{k_{j}}(a)=\begin{cases}-C_{k_{j}}(a)&\text{if spatial constraints are violated,}\\ v_{k_{j}}(a)&\text{else if }t^{c}_{k_{j}}(a)\leq t^{d}_{k_{j}},\\ 0&\text{otherwise},\end{cases} \tag{3}\]  
where \(C_{k_{j}}(a)\) is a function dependent on the collective action of all agents that returns a real non-zero positive value. With either reward structure, the marginal utility of each agent for each task is then  
\[\mu^{k_{j}}_{i}(a_{i},a_{-i})=u^{k_{j}}(a_{i},a_{-i})-u^{k_{j}}(0,a_{-i}), \tag{4}\]  
and the local utility of any agent is given as the sum of its marginal utilities,  
\[u_{i}(a_{i},a_{-i})=\sum_{k_{j}\in\mathcal{M}}\mu^{k_{j}}_{i}(a_{i},a_{-i}). \tag{5}\]The agents in the model act in a greedy manner at each iteration, selecting an action profile \(a_{i}^{*}\) that maximizes their local utility,  
\[a_{i}^{*}=\arg\max_{a_{i}\in A_{i}}u_{i}(a_{i},a_{-i}^{*}), \tag{6}\]  
and the global utility is the sum of all task utilities,  
\[u_{g}(a)=\sum_{k_{j}^{\prime}\in\mathcal{M}}u^{k_{j}}(a). \tag{7}\]  
For a spatial coupled-constraint task allocation problem, the above game is an exact potential game which always converge to a feasible solution when function \(C_{k_{j}}(a)\) is well-designed. The proofs for the game model can be found in [23].  
Recall the definition of an agent's action set in the model above. The size of an agent's action set is approximately \(\mathcal{O}(\vec{m}!)\), where \(\vec{m}\) is the number of tasks that the agent can service (i.e., tasks that are compatible with the agent), since the action profile is an ordered sequence of task to service (i.e., an ordered path). This essentially means that the size of the action set blows up when the number of compatible tasks is large, making the model highly impractical in crowded problems which require quick decision-making due to the large number of action combinations that needs to be evaluated. In fact, this is a common problem that plagues most game-theoretic task allocation models as the computational load in equilibrium selection is generally highly dependent on the size of the task set. [PERSON] [2] attempted to overcome this issue by approximating a single large game as a series of smaller static potential games within a limited time interval where the agent's action is a vector of tasks to attend to during the interval \([t,t+w]\), given as \(a_{i}=\{k^{\prime},k^{+1},\cdots,k^{k+w}\}\). While this approach may help to alleviate the issue in most scenarios, it alone cannot guarantee improvements in extreme situations when many tasks are present in any of the time intervals.