# Improving Computational Efficiency in Crowded Task Allocation Games with Coupled Constraints
## 3 Game Design
### Scheduling Algorithm
```
1:for all agents \(i\) participating in task \(k\)do
2: find \(k\) in \(a_{i}\)
3:if\(\text{index}(k\in a_{i})+1\
eq\mathbf{L}_{i}\)then
4:\(\mathbf{t}^{s},\mathbf{t}^{c},\text{hold}_{i}\gets drop(\text{tasks after }k)\)
5:\(\mathbf{L}_{i}=\text{index}(k\in a_{i})+1\)
6:endif
7:endfor
8:\(update(\text{availability})\)
```  
**Algorithm 2** Alignment procedure: _align_  
```
1:if\(Con(i,\mathbf{L},a,\mathbf{t}^{s},\mathbf{t}^{c})=1\)then
2: loop:
3:for\(k\) which violate constraints do
4:for\(i\in\mathcal{N}\)do
5:\(\mathbf{t}^{c},\mathbf{t}^{s},\text{hold}\gets drop(k\) and tasks after)
6: affected tasks \(\leftarrow\) tasks after
7:\(update(\text{availability})\)
8:endfor
9:while\(len(\text{affected tasks})\
eq 0\)do
10:for\(i\in\mathcal{N}\)do
11:\(\mathbf{t}^{c},\mathbf{t}^{c},\text{hold}\gets drop(\text{affected tasks and tasks after})\)
12: affected tasks \(\leftarrow\) tasks after
13:\(update(\text{availability})\)
14:endfor
15:endwhile
16:endfor
17:if\(Con(i,\mathbf{L},a,\mathbf{t}^{s},\mathbf{t}^{c})=1\)then
18: goto loop
19:endif
20:endif
```  
**Algorithm 3** Constraint check procedure: _constraint_  
The alignment procedure (Algorithm 1, Line 23) is crucial in this algorithm when multiple agents' availability are updated simultaneously to ensure that the agents' availability are in-line with their targeted tasks. The importance of this procedure is shown in the following example. **Example 2**. : _Consider an agent \(i\) with ordered path \(a_{i}=\{k_{1},k_{2},k_{3}\}\). Agent \(i\) was previously expected to complete task \(k_{1}\) and \(k_{2}\) at time \(t_{1}\) and \(t_{2}\), respectively and its availability to begin work at \(k_{3}\) is expected to be \(t_{3}\). However, agent \(j\) now decides to participate in task \(k_{1}\) and the expected completion time for task \(k_{1}\) is brought forward to \(t_{1}-w\). Agent \(j\) then updates agent \(i\)'s expected availability to be some time \(t_{2}-w^{\prime}\) as \(j\) expects \(i\) to be at the next step in the path, \(k_{2}\), because it cannot easily predict \(i\)'s availability any further than the next step. This leads to a loss of alignment between path step and expected availability and any further scheduling will only be incorrect._  
Therefore, an alignment invoked at task \(k\) is effectively a procedure to bring agents back to \(k\) such that the agents must reschedule for all tasks in their path after \(k\). When an alignment procedure is invoked, temporal constraint violation checks (Algorithm 1, Line 25) are necessary as a result of dropping some tasks when aligning the agents. If no agents are realigned, then a temporal constraint violation check is not necessary. However, if a temporal constraint violation is found during the checking procedure, then tasks with violations (and all future tasks in the path) will be dropped. Further alignment for all agents (Algorithm 3, Line 9) is required before checking for temporal constraint violations again. One major issue resulting from the alignment and temporal constraint check procedure is that cycling may occur. Cycling refers to the phenomenon when, as a result of removing some conflicting task schedules, the overall schedule reverts to a historic state. Since the scheduling process is deterministic, then the process is stuck in an infinite loop. Maintenance of a history on the scheduling outcome, such as the path step of every agent, \(\mathbf{L}\), whenever a constraint check procedure is invoked will help to identify cycling and if a cyclic state transition is observed (Algorithm 1, line 26 to 27), then the scheduling is considered to have converged as defined previously since it is infeasible to continue with the scheduling process. Please note that the scheduling algorithm is anytime (with respect to temporal constraints) as temporal constraint checks are considered at every iteration when necessary. Therefore, any schedule proposed by the algorithm at the end of an iteration is feasible, even when a cyclic state transition is present.