# Fair Task Allocation When Cost of Task Is Multidimensional
###### Abstract  
We consider the problem of fairly allocating indivisible tasks, focusing on a recently introduced notion of fairness called Minmax share guarantee. Minmax share (MMS) is a term of fairness guarantees that is defined to be the minimum cost that an agent can ensure for herself, if she were to partition the tasks into \(n\) bundles, and then receive the maximum cost bundle of tasks. However, the cost of tasks considered in previous work is single dimensional, and multidimensional situations have not been researched. In this work, we proposed an allocation algorithm that allocates tasks with multidimensional cost to agents under ordinal model. We prove the approximation ratio of MMS of the algorithm proposed can be guaranteed under \(2+\frac{m\cdot a_{i}(1+n)-n}{n^{2}}\), in addition the time complexity of the algorithm is \(O(m\log m)\). This proposed method is implemented and tested on datasets generated based on  
from the World Health Organization (WHO) in recent years, more than 3 million cases of pesticide poisoning occur every year around the world [5]. With advancement in technologies, UAV can be useful in agricultural plant protection for crops to execute multiple tasks. To allocate tasks to UAVs in an agricultural plant protection environment, various situations need to be considered, such as reducing energy cost while minimizing overall task completion time. In order to find a method that can accomplishes fairness in allocation tasks to UAVs in the agricultural plant protection environment, evaluation of the cost of UAVs from multiple dimensions is needed. According to the authors of [6] and combined with the actual situation, the cost of UAVs by tasks usually comes from three dimensions: time cost, energy cost, and UAV service life cost. Time cost mainly includes working time and flight time of UAVs arriving at tasks. Energy cost is UAV cost of electricity and fuel during flight and working. Because of the limited life of UAVs and their assembled lithium battery, the UAV service life cost includes the life loss of UAVs and lithium battery. When allocating tasks, the cost of all dimensions needs to be considered comprehensively, not just a single dimension. The Round-Robin algorithm is a classic task allocation algorithm, its process is that the agent chooses a task according to its own preferences every round until all tasks are allocated. Although there are some variations of this algorithm, such as Greedy Round-Robin or Double Round-Robin, none of the existing algorithms can solve the task allocation problem when the cost of task is multidimensional. In this work, we take the agricultural plant protection environment as an example to study the task allocation problem when the cost of task is multidimensional. The fairness concept we use in this work is the intensively studied and well-established MMS fairness and all tasks are set as indivisible. It needs to be emphasized that this work only uses the agricultural plant protection environment as an example to conduct research, and the conclusions obtained can be applied to all task allocation issues. The main contributions of this paper are as follows. 1. Designing of a task allocation model for UAV applications in the agricultural plant protection environment. 2. Defining the Minmax share when the cost of tasks is multidimensional. 3. Improving the traditional Round-Robin algorithm to solve the task allocation problem when the cost of task is multidimensional. 4. Prove in the form of a theorem that the Minmax share approximation can be guaranteed. 5. Test and evaluate the performance of the proposed method using datasets generated based on real agricultural plant protection environment at the lab. The remainder of the paper is structured as follows. Section 2 explains the problem and detailed model of the task allocation system in agricultural plant protection environment. Section 3 describes the key elements involved in the implementation of the algorithm we proposed and we analyze the properties of the algorithm in detail.