# Improving Computational Efficiency in Crowded Task Allocation Games with Coupled Constraints
## 3 Game Design
### Scheduling Algorithm  
Before describing the scheduling algorithm, some terminologies that will be used in the discussions are first defined along with the assumptions that are made. **Definition 4**. : _(Allocation) A task is allocated if the task is in the path of any agent (i.e., \(k_{j}\) is allocated if \(k_{j}\in a\))._  
**Definition 5**. : _(Assignment) A task is assigned if there exists a task completion time determined by the scheduling algorithm._The definitions essentially differentiate allocation and assignment such that  
\[\mathcal{M}_{\text{assigned}}\subseteq\mathcal{M}_{\text{allocated}}\subseteq \mathcal{M}. \tag{15}\]  
In other words, not all allocated tasks must be assigned. Allocated tasks that are incompatible with the temporal constraints will not be assigned. In this way, the scheduling algorithm can be thought of as an oracle which advises the agents on the suitability of their actions. All constraint violations are then determined based on assignments rather than allocations. **Assumption 1**. _(Complete information game) Every agent has complete information with regards to the environment. They know the locations and details concerning all agents and tasks. This assumption, though demanding, is not overly restrictive. Firstly, in multi-agent systems, it is not unusual for an agent to understand the basic capabilities of other agents within the system, especially in cases where the agents are expected to cooperate. Secondly, the main research objective of this paper covers that of task allocation rather than path planning or mapping. Therefore, it is fair to assume that there is sufficient knowledge regarding the environment when assigning agents to tasks._  
**Assumption 2**. _(Optimistic agents) If an agent arrive at a task that it cannot complete due to insufficient information on the schedule resulting in the inability to determine a feasible service time window, then the agent will hold at this task for a user-specified time period before leaving. If sufficient information can be gathered during this hold period, then the agent will attempt to complete the task (i.e., determine a task completion time). In other words, agents are optimistic. In our application, this hold period is trivially considered in the form of number of iterations rather than true time units._  
The scheduling algorithm (Algorithm 1) is designed using a greedy approach--assignment is based on the earliest-first principle. Additionally, cooperation between agents to complete a single task is permitted. The duration of service for each task, and thus completion time, is then determined based on some function \(f_{s}\) that is dependent on the number of agents and starting times. To begin, the availability of each agent, which can be computed from the expected time of arrival at the targeted task in its path \(a_{i}\), needs to be determined. (i.e., The initial availability of an agent is first determined based on the expected time of arrival at the first task in its path \(a_{i}\), which is also the initial target. After leaving the first task, the agent targets the next task in the path and determine its availability based on the targeted task. Target transition and availability computation continue in such a manner until the agent reaches the final task in its path whereby having no target after leaving the final task, the availability is set to be infinity.) At each iteration, the agent with the earliest availability is selected (line 4) and the serviceability of the allocated task is determined by the temporal constraints that are enforced on the task. For example, if task \(A\) is to end before task \(B\) begins, then task \(A\) will only be serviceable if an expected start time for task \(B\) exists. In fact, it is for this particular reason that the second assumption is necessary since most tasks can be unserviceable in complicated scenarios if the agents are pessimistic.