# Fair Task Allocation When Cost of Task Is Multidimensional
## 3 Problem Solution
### Analysis of Algorithm  
In Section 3.1, we have proposed an improved Round-Robin algorithm to allocate tasks to UAVs in agricultural plant protection system to achieve Approximate Maximin Fair Allocation. In this section, we will analyze the algorithm's property. **Lemma 1**. : _Let \(T_{i}\) be the task picked by UAV \(i\) and \(T_{i^{\prime}}\) be the task picked by UAV \(i^{\prime}\). If UAV \(i\) picks \(T_{i}\) before UAV \(i^{\prime}\) picks \(T_{i}^{\prime}\) in the Improved Round-Robin Algorithm, then we have \(C_{i}(T_{i})-C_{i}(T_{i^{\prime}})<\alpha_{i}\cdot C_{i,max}\). Here, \(\beta_{i}=max\{\beta_{i}(t),\beta_{i}(e),\beta_{i}(l)\},\alpha_{i}=1-\beta_{i}\), \(C_{i}(T_{i})\) is cost of UAV \(i\) for task \(T_{i}\) and \(C_{i,max}\) is the maximum cost of UAV \(i\) in all tasks._  
Proof. : According to Equation (5), \(C_{i}(T_{i})-C_{i}(T_{i^{\prime}})=w_{i}(t)\cdot(c_{i,T_{i}}(t)-c_{i,T_{i^{ \prime}}}(t))+w_{i}(e)\cdot(c_{i,T_{i}}(e)-c_{i,T_{i^{\prime}}}(e))+w_{i}(l) \cdot(c_{i,T_{i}}(l)-c_{i,T_{i^{\prime}}}(l))\). In the following, we assume that \(\beta_{i}(t)=max\{\beta_{i}(t),\beta_{i}(e),\beta_{i}(l)\}\) (same as other situations), UAV \(i\) will pick tasks in order to minimize time cost, due to UAV \(i\) pick before UAV \(i^{\prime}\), so \(c_{i,T_{i}}(t)<c_{i,T_{i^{\prime}}}(t)\), therefore \(C_{i}(T_{i})-C_{i}(T_{i^{\prime}})<w_{i}(e)\cdot(c_{i,T_{i}}(e)-c_{i,T_{i^{ \prime}}}(e))+w_{i}(l)\cdot(c_{i,T_{i}}(l)-c_{i,T_{i^{\prime}}}(l))\). Because \(K_{t,e}\cdot c_{ij}(t)\geq c_{i,j}(e)\) and \(K_{t,l}\cdot c_{i,j}(t)\geq c_{i,j}(l)\), so time cost accounts for at least \(\beta_{i}\) of total cost. Moreover, \(C_{i}(T_{i})-C_{i}(T_{i^{\prime}})<C_{i,max}\) for any \(i,i^{\prime}\), therefore \(C_{i}(T_{i})-C_{i}(T_{i^{\prime}})<\alpha_{i}\cdot C_{i,max}\). **Lemma 2**. : _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 C_{i}(P_{i^{\prime}})+(\frac{m\cdot\alpha_{i}}{n}+1)\cdot C_{ i,max}\)._Proof. : The Improved Round-Robin Algorithm has exactly \(K=\lceil\frac{m}{n}\rceil\) rounds of allocation. The task picked by UAV \(i\) (\(i^{\prime}\) resp.) in round \(k\) is denoted by \(T_{i}(k)\in M\) (\(T_{i^{\prime}}(k)\in M\) resp.). Next, we will prove this lemma in five cases. Case 1: \(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 before 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))\]  
and for round \(k\), according to Lemma 1, \(C_{i}(T_{i}(k))-C_{i}(T_{i^{\prime}}(k))<\alpha_{i}\cdot C_{i,max}\). Therefore, \(C_{i}(P_{i})-C_{i}(P_{i^{\prime}})<\lceil\frac{m}{n}\rceil\cdot\alpha_{i}\cdot C _{i,max}\). Due to that \(\lceil\frac{m}{n}\rceil<\frac{m}{n}+1\), \(C_{i}(P_{i})-C_{i}(P_{i^{\prime}})<(\frac{m\cdot\alpha_{i}}{n}+\alpha_{i}) \cdot C_{i,max}\). Case 2: \(i<i^{\prime}\) and non of UAV \(i\) and UAV \(i^{\prime}\) have selected the task in the last round. Similar to case 1, UAV \(i\) will pick task before UAV \(i^{\prime}\) in each round, then  
\[C_{i}(P_{i})-C_{i}(P_{i^{\prime}})=\sum_{k=1}^{K-1}C_{i}(T_{i}(k))-\sum_{k=1}^ {K-1}C_{i}(T_{i^{\prime}}(k))\]  
therefore \(C_{i}(P_{i})-C_{i}(P_{i^{\prime}})<(\lceil\frac{m}{n}\rceil-1)\cdot\alpha_{i }\cdot C_{i,max}<\frac{m\cdot\alpha_{i}}{n}\cdot C_{i,max}\). Case 3: \(i<i^{\prime}\) and UAV \(i\) have selected the task in the last round but UAV \(i^{\prime}\) not. In this case, UAV \(i\) will pick task before UAV \(i^{\prime}\) in each round but according to algorithm rules UAV \(i\) has one more task than UAV \(i^{\prime}\).