# Fair Task Allocation When Cost of Task Is Multidimensional
## 4 Experiment
### Result  
In the this section, we provide details of the experimental performance of improved Round-Robin algorithm. As per Definition 4, we will evaluate the approximate ratio of Min-Max share of the algorithm as an indicator. Due to the real-time task allocation needed in reality, the running time of the experiment also need to be evaluated. To better illustrate the superiority of our algorithm, we compare our proposed algorithm with Random Serial Dictatorship (RSD) proposed in [8] and the SequPick algorithm proposed in [1]. First, we compare our algorithm with Random Serial Dictatorship (RSD). This comparison was made because RSD is probably the best known and most-studied mechanism in the random allocation literature. In addition, RSD guarantees the total utilitarian welfare if the utilities are normalized to sum up to one for each agent under ordinal preferences, which is similar to our model. However, the main difference is RSD targets the situation where cost comes from a single dimension, but in this work cost is multidimensional. Next, we will compare our algorithm and RSD in terms of the approximate ratio of Min-Max share and runtime. Figure 1 shows the approximate ratio of Min-Max share when the number of UAV is unchanged and the number of tasks is changed. The number of UAV is 5. From Figure 1, we can get two conclusions. 1. The algorithm proposed in Section 4 performs better than the Random Serial Dictatorship (RSD) method. By Definition 3, the allocation is Min-Max share when the approximate ratio is less than 1, so our proposed algorithm can achieve Min-Max share allocation, but the RSD can not in some cases. 2. Our proposed algorithm has a more stable performance than the RSD, because our algorithm has greater adaptability to perform well when dealing with different types of data. Figure 2 shows the approximate ratio of Min-Max share when the number of task is unchanged and the number of UAV is changed. The number of tasks is 200. From Figure 2, we can see that although  
Figure 1: Improved Round-Robin vs. RSG. the experimental performance varies slightly as the number of UAV changes, the overall performance is still very good. As the number of UAVs increases, the approximate ratio of Min-Max share shows fluctuation; this is because different UAVs have different weights over tasks and the approximate ratio is related to the weights, which has been proved in Theorem 1. However, from Figure 2, we can see that although the experimental performance varies slightly as the number of UAV changes, the overall performance is still very good, while the performance of the RSD is not as good as ours. Next, we will examine the running time of the algorithm. As proved in Theorem 2, the time complexity of the Improved Round-Robin Algorithm is \(O(m\log m)\), which means that algorithm running time grows slowly with the number of task increases. Figure 3 shows the experimental results. From Figure 3, we draw 3 conclusions. 1. The running time of the two algorithms is almost the same. 2. The running time of the improved Round-Robin algorithm can meet the needs of real-time task allocation. 3. As the number of tasks increases, the algorithm runtime increases slowly, which consistent with the analysis in the Theorem 2. Moreover, it means that our proposed algorithm can handle situations with large amounts of data. Figure 3: Improved Round-Robin vs. RSG. Figure 2: Improved Round-Robin vs. RSG. Next, we compare our work with the SequPick algorithm proposed in [1]. The SequPick algorithm requires that agents pick a certain number of tasks that have smallest cost to it in sequence. The reason compared with this method is that it guarantees the approximation ratio of MMS is no more than \(O(\log\frac{m}{n})\) under ordinal preferences [1], which is the lowest approximation ratio in theory so far. In addition, SequPick algorithm has a low time complexity because all tasks only need to be allocated once.