# Improving Computational Efficiency in Crowded Task Allocation Games with Coupled Constraints
## 3 Game Design
### Scheduling Algorithm
Additionally, it should be noted that for a task to enforce some temporal constraints, it has to be allocated (e.g., If task \(C\) must begin after task \(D\), but task \(D\) is not allocated, then task \(C\) can be considered to be having no temporal constraints). Temporal constraints do not actively enforce allocations, but rather, consider that if dependent tasks are allocated, then their assignments must be constrained. If the allocated task is unserviceable, then the agent is placed on hold and the next available agent is considered. Otherwise, a service time window can be computed, and the agent determines the expected completion time for the task and updates its availability based on the next task in its path. At any iteration, if any agent has been placed on hold at a task for longer than the specified hold period, then it leaves the current task and transits to the next task in its path (line 11 to 16) and will most probably never return to the skipped task. If an agent completes all its allocated task, then it will no longer be considered even if it has the earliest availability. The algorithm converges when all agentscan no longer proceed for any reason (e.g., all allocations have been assigned, all agents' allocated tasks are temporally constrained, etc.). ```
1:Input:\(a\leftarrow(a_{i},a_{-i})\)
2:Initialize:\(\mathbf{L}=\mathbf{1}^{n},\mathbf{t}^{\mathbf{s}}=-\mathbf{1}^{n},\mathbf{t}^{ \mathbf{c}}=-\mathbf{1}^{n},\text{hold}=\mathbf{0}^{n},Con(i,\mathbf{L},a, \mathbf{t}^{\mathbf{c}},\mathbf{t}^{\mathbf{s}})=\{0,1\}\)
3:Sort:
4:\(i\leftarrow\operatorname*{arg\,min}_{i\in\mathcal{N}}(\text{availability})\)
5:Constraint:
6:if\(Con(i,\mathbf{L},a,\mathbf{t}^{\mathbf{s}},\mathbf{t}^{\mathbf{c}})=1\)then
7:if\(\text{hold}_{i}<\max\text{Hold}\)then
8:\(\text{hold}_{i}=\text{hold}_{i}+1\)
9:\(i\leftarrow\operatorname*{arg\,min}_{i\in\mathcal{N}\setminus\{i\}}(\text{ availability})\)
10:gotoConstraint
11:else
12:\(\text{hold}_{i}=0\)
13:\(\mathbf{L}_{i}=\mathbf{L}_{i}+1\)
14:\(update(\text{availability})\)
15:gotoSort
16:endif
17:Schedule:
18:elseif\(Con(i,\mathbf{L},a,\mathbf{t}^{\mathbf{s}},\mathbf{t}^{\mathbf{c}})=0\)then
19:\(\mathbf{L},\mathbf{t}^{\mathbf{s}},\mathbf{t}^{\mathbf{c}}\gets compute\_ schedule(i,\mathbf{L},a,\mathbf{t}^{\mathbf{s}},\mathbf{t}^{\mathbf{s}},f_{ \mathbf{s}})\)
20:\(\mathbf{L}_{i}=\mathbf{L}_{i}+1\)
21:if not firstthen
22:\(\mathbf{L}_{0}=\mathbf{L}\)
23:\(\mathbf{L},\mathbf{t}^{\mathbf{s}},\mathbf{t}^{\mathbf{c}},\text{hold}, \text{availability}\gets align(\mathbf{L},a,\mathbf{t}^{\mathbf{s}},\mathbf{t} ^{\mathbf{c}})\)
24:if\(\mathbf{L}\
eq\mathbf{L}_{0}\)then
25:\(\mathbf{L},\mathbf{t}^{\mathbf{s}},\mathbf{t}^{\mathbf{c}},\text{hold}, \text{availability}\leftarrow constraint(\mathbf{L},a,\mathbf{t}^{\mathbf{s}}, \mathbf{t}^{\mathbf{c}})\)
26:if\(ismember(\mathbf{L},\mathbf{L}_{\text{hist}})\)then
27:return
28:else
29:\(append(\mathbf{L},\mathbf{L}_{\text{hist}})\)
30:endif
31:endif
32:endif
33:gotoSort
34:endif
```  
**Algorithm 1** Scheduling Algorithm: _schedule_  
In the event that multiple agents have been allocated to the same task, then agents will only participate if the task has yet to be completed at their time of arrival. If an agent were to participate in servicing a task, then it will update the expected completion time of the task, its own availability and also the availability of all other (previous and current) participating agents to reflect the change based on \(f_{\mathbf{s}}\). Immediately after updating the schedule, the algorithm will invoke an alignment procedure (Algorithm 2) and possibly a temporal constraint check procedure (Algorithm 3) before moving on to the next iteration.