# Fair Task Allocation When Cost of Task Is Multidimensional
## 5 Related Work  
There are already some studies on the problems related to the use of UAVs in agricultural plant protection. The researchers in [10] proposed a path planning algorithm with the goal of minimizing the total energy consumption of the work, realizing the full coverage path planning of the field and the optimization of the return point location. The researchers in [11] proposed a path planning method based on Grid-GSA algorithm, which can plan a reasonable return point for the field with irregular boundaries, which makes the non-plant protection operation time the shortest. The researchers in [6] fully consider the influence of the additional flight distance caused by the change of flight height, and studied a path planning method for plant protection UAVs that can be used for three-dimensional terrain. However, these works did not take into account the differences between plant protection tasks. In this work, we will study the problem of fair allocation when there are differences in the cost of plant protection tasks. The fair allocation of indivisible items is a central problem in multi-agent systems [3,12]. Fair allocation has been extensively studied for allocation of divisible goods, commonly known as cake cutting [13]. In order to identify fair allocations, one needs to formalize what fairness means. Multiple solution concepts, such as envy-freeness, proportionality, and equitability, have been proposed to formally capture fairness [14,15]. The authors of [16] proposed the idea of envy-freeness up to one good (EF1); it has been further popularized in [17], the researchers have shown that a natural modification of the Nash welfare maximizing rule satisfies EF1 and Pareto-optimal (PO), in addition they proposed envy freeness up to the least valued good (EFX), which is a stronger fairness concept. MMS fairness was proposed in [2] as a fairness concept for allocation of indivisible items. The concept coincides with the standard proportionality fairness concept if the items to be allocated are divisible [3,4]. An agent's MMS is the \"most preferred bundle he could guarantee himself as a divider in divide-and-choose against adversarial opponents\" [2]. The authors of [2] studied the conditions under which MMS allocations would exist. Although MMS is a highly attractive fairness concept, the authors of [3,7] have shown that an MMS allocation of items does not exist in general. This fact initiated research on approximate MMS allocations of goods in which each agents gets some fraction of her MMS guarantee [18]. There have been several works on algorithms that find an approximate MMS allocation [19, 20, 21, 22, 23]. [7] showed that although an MMS allocation of goods may not always exist, but there exists a polynomial-time algorithm that returns a \(\frac{2}{3}\)-approximate MMS allocation. [21] developing a simple and efficient  
Figure 6: Improved Round-Robin vs. SequPick. algorithm that achieves the same approximation guarantee. [23] proved that MMS allocations do not always exist but can be 2-approximated by a simple algorithm and also presented a PTAS for relaxation of MMS called optimal MMS. Fair allocation of indivisible items problem can be divided into good allocation and task allocation (i.e., in some works, it is expressed as more allocation). If all agents have positive utilities for the items, we view the items as goods. On the other hand, if all agents have negative utilities for the items, we can view the items as tasks [18]. The authors of [17] have shown that a natural modification of the Nash welfare maximizing rule satisfies EF1 and Pareto-optimal (PO) for the case of goods. Algorithms for computing approximate MMS allocations of goods are being used in practice for fair division in real-world problems [24]. The authors of [19; 20; 21] proposed an algorithm that can guarantee an approximate MMS allocation. The work mentioned above only focused on the case of goods. There are many settings in which agents may have negative utilities such as when tasks are allocated.