# Fair Task Allocation When Cost of Task Is Multidimensional
## 3 Problem Solution
### Analysis of Algorithm
Then,  
\[C_{i}(P_{i})-C_{i}(P_{i^{\prime}})=\sum_{k=1}^{K}C_{i}(T_{i}(k))-\sum_{k=1}^ {K-1}C_{i}(T_{i^{\prime}}(k)) \tag{12}\]  
According to Equation (12), we can get that  
\[C_{i}(P_{i})-C_{i}(P_{i^{\prime}})=\sum_{k=1}^{K-1}\left(C_{i}(T_{i}(k))-C_{i }(T_{i^{\prime}}(k))\right)+C_{i}(T_{i}(K))\]  
As \(C_{i}(T_{i}(K))\leq C_{i,max}\), therefore \(C_{i}(P_{i})-C_{i}(P_{i^{\prime}})<\frac{m\cdot\alpha_{i}+n}{n}\cdot C_{i,max}\). Case 4: \(i>i^{\prime}\) and UAV \(i^{\prime}\) have selected the task in the last round but UAV \(i\) has not. In this case, UAV \(i\) will pick a task after UAV \(i^{\prime}\) in each round, but according to algorithm rules UAV \(i\) has one less task than UAV \(i^{\prime}\). Then,  
\[C_{i}(P_{i})-C_{i}(P_{i^{\prime}})=\sum_{k=1}^{K-1}C_{i}(T_{i}(k))-\sum_{k=1}^ {K}C_{i}(T_{i^{\prime}}(k)) \tag{13}\]  
According to Equation (13), we can get that  
\[C_{i}(P_{i})-C_{i}(P_{i^{\prime}})=\sum_{k=1}^{K-1}(C_{i}(T_{i}(k))-C_{i}(T_{ i^{\prime}}(k+1)))-C_{i}(T_{i^{\prime}}(1))\]  
Due to the UAV \(i\) pick task in \(k\) round before UAV \(i^{\prime}\) in \(k+1\) round, so \(C_{i}(T_{i}(k))-C_{i}(T_{i^{\prime}}(k+1))<\alpha_{i}\cdot C_{i,max}\). Therefore \(C_{i}(P_{i})-C_{i}(P_{i^{\prime}})<\frac{m\cdot\alpha_{i}}{n}\cdot C_{i,max}\). Case 5: \(i>i^{\prime}\) and both UAV \(i\) and UAV \(i^{\prime}\) have selected the task in the last round. In this case, UAV \(i\) will pick task after UAV \(i^{\prime}\) in each round, then  
\[C_{i}(P_{i})-C_{i}(P_{i^{\prime}})=\sum_{k=1}^{K}C_{i}(T_{i}(k))-\sum_{k=1}^{K }C_{i}(T_{i^{\prime}}(k)) \tag{14}\]The Equation (14) can be can be expressed as \(C_{i}(P_{i})-C_{i}(P_{i^{\prime}})=\sum_{k=1}^{K-1}(C_{i}(T_{i}(k))-C_{i}(T_{i^{ \prime}}(k+1)))+C_{i}(T_{i}(K))-C_{i}(T_{i^{\prime}}(1))\), due to the UAV \(i\) pick task in \(k\) round before UAV \(i^{\prime}\) in \(k+1\) round, so \(C_{i}(T_{i}(k))-C_{i}(T_{i^{\prime}}(k+1))<\alpha_{i}\cdot C_{i,max}\). Moreover, \(C_{i}(T_{i}(K))-C_{i}(T_{i^{\prime}}(1))\leq C_{i,max}\), therefore \(C_{i}(P_{i})-C_{i}(P_{i^{\prime}})<\frac{m\cdot\alpha_{i}+n}{n}\cdot C_{i,max}\). In summary, we can know that \(C_{i}(P_{i})\leq C_{i}(P_{i^{\prime}})+(\frac{m\cdot\alpha_{i}}{n}+1)\cdot C_{ i,max}\). **Lemma 3**. : _Let \(P=(P_{1},P_{2},...,P_{n})\) be the allocation obtained by the Improved Round-Robin Algorithm for \(M\). Then, we have_  
\[C_{i}(P_{i})\leq\frac{C_{i}(M)}{n}+(1-\frac{1}{n})\cdot C_{i,max}+(1-\frac{1}{ n})\cdot\frac{m}{n}\cdot\alpha_{i}\cdot C_{i,max}\]  
Proof. : According to lemma 2, \(C_{i}(P_{i})\leq C_{i}(P_{i^{\prime}})+(\frac{m\cdot\alpha_{i}}{n}+1)\cdot C_ {i,max}\) for \(i^{\prime}\
eq i\), so  
\[ \begin{split} n\cdot C_{i}(P_{i})\leq C_{i}(P_{i})& +\sum_{i^{\prime}\in N\setminus i}C_{i}(P_{i^{\prime}})+(n-1)\cdot C _{i,max}\\ &+(n-1)\cdot\frac{m}{n}\cdot\alpha_{i}\cdot C_{i,max}\end{split}  \tag{15}\]  
Because \(C_{i}(P_{i})+\sum_{i^{\prime}\in N\setminus i}C_{i}(P_{i^{\prime}})=C_{i}(M)\), the Equation (15) divided by \(n\) can yields the result. **Theorem 1**. : _The Improved Round-Robin Algorithm gives an allocation \(P=(P_{1},P_{2},...,P_{n})\), then we have for all \(i\in N\)_  
\[C_{i}(P_{i})\leq 2+\frac{m\cdot\alpha_{i}\cdot(1+n)-n}{n^{2}}\cdot MMS_{U_{i}} (M)\]  
Proof. : According to Definition 2, if partition \(P\) divides task set \(M\) into \(n\) bundles such that biggest cost of a bundle is minimized for UAV \(i\), then the cost of UAV \(i\) is expressed as \(MMS_{U_{i}}^{n}(M)\). Therefore, by definition of the Min-Max share guarantee and the additivity of \(C_{i}\), we obtain that  
\[\frac{1}{n}\cdot C_{i}(M)\leq MMS_{U_{i}}^{n}(M) \tag{16}\]  
and  
\[C_{i,max}\leq MMS_{U_{i}}^{n}(M) \tag{17}\]  
According to the Lemma 3, we can get that \(C_{i}(P_{i})\leq\frac{C_{i}(M)}{n}+(1-\frac{1}{n})\cdot C_{i,max}+(1-\frac{1} {n})\cdot\frac{m}{n}\cdot\alpha_{i}\cdot C_{i,max}\leq 2+\frac{m\cdot\alpha_{i} \cdot(1+n)-n}{n^{2}}\cdot MMS_{U_{i}}(M)\), for each agent \(i\in N\), which proves the Theorem 1. **Theorem 2**.