# Fair Task Allocation When Cost of Task Is Multidimensional
## 2 Problem Definition
### Fair Allocation Problem  
For the fair allocation problem, \(N\) is a set of \(n\) agents and \(M\) is a set of \(m\) indivisible tasks. For any \(i\in N\) and \(j\in M\), \(C_{i,j}\) represents the cost of task \(j\) to agent \(i\). Next, we will illustrate the definition of preference. Definition 1: Preference  
Imagine that agent \(i\in N\) and \(j,k\in M\), then for \(i,j\preceq k\) if and only if \(C_{i,j}\leq C_{i,k}\). **Example 1**. : _Assuming there are \(2\) agents and \(2\) tasks, the cost of agents by tasks can be seen in Table 1, then for agent \(1\), task \(1\preceq\) task \(2\), and for agent \(2\), task \(2\preceq\) task \(1\)._  
Different agents may have different preferences for these tasks and these preferences are generally captured by cost functions \(C_{i}:2^{M}\rightarrow\mathbb{R}\). As the goal of the problem is to fairly allocate all the tasks to these agents, the MMS fairness is defined in the following. Definition 2: MMS fairness:  
Imagine that agent \(i\) gets the opportunity to partition all the tasks into \(n\) bundles, but she is the last to choose a bundle. Then, her best strategy is to partition the tasks such that the biggest cost of a bundle is minimized. Let \(\Pi(M)\) denote the set of all possible \(n\)-partitionings of \(M\). Then, the Minmax share (MMS) of agent \(i\) is defined as  
\[MMS_{i}=\min_{\langle X_{1},\ldots,X_{n}\rangle\in\Pi(M)}\max_{j\in M}C_{i}(X_{ j}) \tag{1}\]  
where \(X_{j}\) is the task bundle that agent \(i\) partitions, and \(C_{i}\) represents that the cost of agent \(i\). **Example 2**. : _(Continues from Example 1)_  
_Assuming that agent \(1\) gets the opportunity to partition all tasks into \(2\) bundles and she is the last to choose, her best strategy is to partition the tasks into \(\{\text{task }1\}\) and \(\{\text{task }2\}\), then the Minmax share of agent \(1\) is \(3\). Similarly, the Minmax share of agent \(2\) is \(4\)._  
Next, we will introduce the formal definition of MMS allocation. Definition 3: MMS allocation:  
Let \(x=(x_{i})_{i\in N}\) be an allocation, where \((x_{i,j})_{j\in M}\) and \(x_{i,j}\in\{0,1\}\) indicates if agent \(i\) gets task \(j\) under allocation \(x\). Then, \(x\) is a MMS allocation if and only if for all \(i\in N\)  
\[\sum_{j=1}^{m}C_{i,j}\cdot x_{i,j}\leq MMS_{i} \tag{2}\]  
**Example 3**. : _(Continues from Example 2) Assuming that the task \(1\) is allocated to agent \(1\) and task \(2\) is allocated to agent \(2\), then the coat of agent \(1\) is \(2\) and the coat of agent \(2\) is \(1\). All agents' costs do not exceed their value of MMS, so this allocation is a MMS allocation._  
The authors of [7] have shown that a MMS allocation does not necessarily exist, and to make it more accurate to measure the fairness of allocation, the definition of approximated MMS allocation has been proposed. Definition 4: \(r-\)approximated MMS allocation: \begin{table}
\begin{tabular}{l c c} \hline \hline  & **Task 1** & **Task 2** \\ \hline Agent 1 & 2 & 3 \\ \hline Agent 2 & 4 & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Cost of Agents by Tasks. _Let \(x=(x_{i})_{i\in N}\) be an allocation, where \((x_{i,j})_{j\in M}\) and \(x_{i,j}\in\{0,1\}\) indicates if agent \(i\) gets task \(j\) under allocation \(x\). Then, \(x\) is a \(r-\)approximated MMS allocation if and only if for all \(i\in N\)_  
\[\sum_{j=1}^{m}C_{i,j}\cdot x_{i,j}\leq r\cdot MMS_{i} \tag{3}\]  
In Equation (3), \(r>1\), because when \(r\leq 1\) an allocation will be called MMS-fairness, which has been shown in Definition 3. Note that a feasible allocation guarantees \(\sum_{i\in N}x_{i,j}=1\) because a task can be assigned to only one agent when tasks are indivisible. It is assumed that all agents have underlying cardinal additive utilities over the tasks. Next, we will present the definition of the preference model that will be used in this paper.