Fair Distribution of Delivery Orders

1 Introduction

With the rise of digital marketplaces and the gig economy, package delivery services have become crucial components of e-commerce platforms like Amazon, AliExpress, and eBay. In addition to these novel platforms, traditional postal and courier services also require swift turnarounds for distributing packages. Prior work has extensively investigated the optimal partitioning of tasks among the delivery agents under the guise of vehicle routing problems (see [Toth and Vigo, 2002] for an overview). However, these solutions are primarily focused on optimizing the efficiency (often measured by delivery time or distance travelled [Kleinberg et al., 1999; Pioro, 2007]), and do not consider fairness towards the delivery agents. This is particularly important in the settings where agents do not receive monetary compensation, e.g., in volunteer-based social programs such as Meals on Wheels [O'Dwyer and Timonen, 2009].

We consider fair distribution of delivery orders that are located on the vertices of a connected graph, containing a warehouse (the hub). Agents are tasked with picking up delivery packages (or items) from the fixed hub, deliver them to the vertices, and return to the hub. In this setting, the cost incurred by an agent i is the total distance traveled, that is, the total number of the edges traversed by i in the graph. Let us illustrate this through an example.

Example 1. Consider seven delivery orders {a, b, . . . , g} and a hub (h) that are located on a graph as depicted in Figure 1. An agent's cost depends on the graph structure and is submodular. For instance, the cost of delivering an order to vertex f is the distance from the hub h to f, which is 41 ; but the cost of delivering to f and g is only 5 since they can both be serviced in the same trip.

Let there be two (delivery) agents. If the objective were to simply minimize the total distance travelled (social optimality), then there are two solutions with the total cost of 7: either one agent delivers all the items or one agent services a while the other services the rest. However, these solutions do not distribute the delivery orders fairly among the agents.

One plausible fair solution may assign {a, b, f} to the first agent and {c, d, e, g} to the other, minimizing the cost discrepancy. However, since both agents benefit from exchanging f for c, this allocation is not efficient or, more precisely, it is not Pareto optimal. After the exchange, the first agent services {a, b, c} and the second agent {d, e, f, g}, which in fact is a Pareto optimal allocation.

The above example captures the challenges in satisfying fairness in conjunction with efficiency, and consequently, motivates the study of fair distribution of delivery orders. The literature on fair division has long been concerned with the fair allocation of goods (or resources) [Lipton et al., 2004;

1 Formally, there is also the cost of returning to h, but since, on trees, each edge must be traversed by an agent twice (once in each direction), we do not count the return cost for simplicity.

Budish, 2011; Barman et al., 2019; Freeman et al., 2019], chores (or tasks) [Chen and Liu, 2020; Ebadian et al., 2022; Huang and Lu, 2021; Hosseini et al., 2022], and mixtures thereof [Bhaskar et al., 2021; Aziz et al., 2022; Caragiannis and Narang, 2023; Hosseini et al., 2023b]. It has resulted in a variety of fairness concepts and their relaxations. Most notably, envy-freeness and its relaxation-envy-freeness up to one item (EF1) [Lipton et al., 2004]-have been widely studied in the context of fair division. Another well-studied fairness notion, minimax share (MMS) [Budish, 2011], requires that agents receive cost no more than what they would have received if they were to create (almost) equal partitions. A key question is how to adopt these fairness concepts to the delivery problems, and whether these fairness concepts are compatible with natural efficiency requirements.

1.1 Contributions

We initiate the study of fair distribution of delivery tasks among a set of agents. The tasks are placed on the vertices of an acyclic or tree graph and have submodular service costs. The primary objective is to find a fair partition of m delivery orders (represented by vertices of a graph), starting from a fixed hub, among n agents. We consider two well-established fairness concepts of EF1 and MMS and explore their existence and computation along with efficiency notions of social optimality (SO) and Pareto optimality (PO).

Table 1 summarizes our results on the coexistence of fairness and efficiency in arbitrary graphs. We first show that an EF1 allocation always exists and can be computed in polynomial time on trees (Proposition 1). In contrast, an MMS allocation is guaranteed to exist, but its computation remains NP-hard (Theorem 1). Of the combinations of fairness and efficiency, only MMS and PO allocations are guaranteed to exist. Finding a fair and efficient allocation remains NP-hard.

We note that our intractability results hold even for the restricted case of unweighted tree graphs. Thus, while our existence and hardness results hold for cyclic and/or weighted graphs (see the full version of the paper [Hosseini et al., 2023a] for details on how our results extend beyond unweighted trees), in order to establish a solid baseline for further work on fair delivery, in this paper we focus on unweighted tree instances.

Indeed, a popular technique to deal with computationally difficult problems on graphs is to provide algorithms with complexity parameterized by some measure of treeresemblance [Cygan et al., 2015]. Trees can be also motivated in practice. Many suburban neighborhoods in the United States, among other countries, are designed with a culde-sac layout, with houses/mailboxes typically located at uniform distances. Then, a group of agents distributing a newspaper or a leaflet to every house in such neighborhood, will face an unweighted tree instance of our problem.

For this setting, we characterize the conditions for the existence of fair (EF1 and MMS) and efficient (PO and SO) allocations in tree instances. In particular, we find a necessary condition for an allocation to be EF1 and PO (Proposition 5), which helps us prove that such an allocation must be leximin optimal. This leads us to an intriguing result that an EF1 and PO allocation always satisfies MMS as well (Theorem 3). We use these observations to circumvent our hardness results by designing an XP algorithm (Algorithm 1), parameterized by the number of agents, that allows us to find an MMS and PO solution and check whether an instance admits an EF1 and PO allocation as well (Theorem 5).

Subsequently, we study the price of fairness in our setting by establishing its worst case bounds and typical values in a theoretical and experimental analysis, respectively.

All missing proofs can be found in the full version of the paper [Hosseini et al., 2023a]. There, we also present additional results on a stronger fairness notion of envy-freeness up to any item (EFX). We note that an EFX allocation always exists in this setting, however EFX combined with some efficiency requirement, for large classes of graphs, becomes as restrictive as envy-freeness. We also discus how our results extend to graphs with weighted edges and/or cycles and provide additional experiments.

1.2 RelatedWork

Fair division of indivisible items has garnered much attention in recent years. Several notions of fairness have been explored in this space, with EF1 [Lipton et al., 2004; Budish, 2011; Barman et al., 2019; Caragiannis and Narang, 2023] and MMS [Ghodsi et al., 2018; Barman and Krishnamurthy, 2020; Hosseini and Searns, 2021] being among the most prominent ones. An important result is from Caragiannis et al. [2019] showing that an EF1 and PO allocation is guaranteed to exist for items with non-negative additive valuations. Some prior work has also looked at fair division on graphs [Bouveret et al., 2017; Truszczynski and Lonc, 2020; Misra et al., 2021; Bilò et al., 2022; Misra and Nayak, 2022], but in the settings that are very different from assigning delivery orders. The majority of these works identified the vertices of a graph with goods and analyzed how to fairly partition the graph into contiguous pieces.

Recent works have explored fairness in delivery settings [Gupta et al., 2022; Nair et al., 2022] or ride-hailing platforms [Esmaeili et al., 2023; Sánchez et al., 2022]. However, these studies are mainly experimental and do not provide any positive theoretical guarantees. While fairness has been studied in routing problems, the aim has been to balance the amount of traffic on each edge [Kleinberg et al., 1999; Pioro, 2007], which does not capture the type of delivery instances that we investigate in this paper. In the full version of the paper [Hosseini et al., 2023a], we provide an extended review of the literature.

2 Our Model

We denote a delivery instance by an ordered triple I = ⟨[n],G, h⟩, where [n] is a set of agents, G = (V,E) is an undirected acyclic graph (or a tree) of delivery orders rooted in h ∈ V . The special vertex, i.e., the root, h is called the hub. The goal is to assign each vertex in graph G, except for the hub, to a unique agent that will service it. Formally, an allocation A = (A1, . . . , An) is an n-partition of vertices in V \ {h}. We are interested in complete allocations such that ∪i∈[n]Ai = V \ {h}, and denote the set of all complete allocations by Πn .

An agent's cost for servicing a vertex v ∈ V , denoted by c(v), is the length of the shortest path from the hub h to v. An agent's cost for servicing a set of vertices S ⊆ V \ {h} is equal to the minimum length of a walk that starts and ends in h and contains all vertices in S divided by two. 2 A walk to serve vertices in S may pass through vertices in some superset of S, i.e., S′ ⊇ S. Thus, the cost function c is submodular and belongs to the class of coverage functions. We use G|S to denote the minimal connected subgraph containing all vertices in S ∪ {h}. Thus, we have c(S) = |E(G|S)|. We say that an agent servicing S, visits all vertices in G|S.

Fairness Concepts. The most plausible fairness notion is envy-freeness (EF), which requires that no agent (strictly) prefers the allocation of another agent. An EF allocation may not exist; consider one delivery order and two agents. A prominent relaxation of EF is envy-freeness up to one order (EF1) [Lipton et al., 2004; Budish, 2011], which requires that every pairwise envy can be eliminated by a removal of a single order served by the envious agent.

Definition 1 (Envy-Freeness up to One Order (EF1)). An allocation A is EF1 if for every pair i, j ∈ [n], either Ai = ∅ or there exists x ∈ Ai such that c(Ai \ {x}) ≤ c(Aj).

Another well-studied notion is minimax share (MMS), which ensures that each agent gets at most as much cost as they would if they were to create an n-partition of the delivery orders but then receive their least preferred bundle. This notion is an adaptation of maximin share fairness-that deals with positive valuations [Budish, 2011]-to the settings that deals with negative valuations and has been recently studied in fair allocation of chores (see e.g., Huang and Lu [2021]).

Definition 2 (Minimax Share (MMS)). An agent's minimax share cost is given by

An allocation A is MMS if c(Ai)≤MMSi(I) for all i∈[n].

Under additive non-negative identical valuations, MMS implies EF1 (for completeness, we give a formal proof in the full version of the paper). However, since in our case the costs are submodular, EF1 and MMS do not imply each other, even though the cost functions are identical (see Example 2).

2 On trees, in each such walk, each edge is traversed by an agent two times (once in both directions). For simplicity, we drop the return cost, hence the division by 2.

Economic Efficiency. Our first notion of efficiency is social optimality that requires that the aggregate cost of the agents is minimum, i.e., equal to the number of edges in the graph. In such a case, each vertex (except for the hub) is visited by only one agent.

Definition 3 (Social Optimality (SO)). An allocation A is socially optimal if ∑ni=1 c(Ai) = |E(G)|. In other words, for every pair of agents i ̸= j ∈ [n], the only vertex they both visit is the hub, i.e., V (G|Ai ) ∩ V (G|Aj ) = {h}.

Here, V (·) takes as an input a subgraph and returns the set of vertices in it. An allocation that assigns all vertices to a single agent is vacuously SO. However, as we discussed in Example 1 it may result in a very unfair distribution of orders. Therefore, we consider a weaker efficiency notion that allows for some overlap in vertices visited by the agents.

Definition 4 (Pareto Optimality (PO)). An allocation A Pareto dominates A′ if c(Ai) ≤ c(A′i ), for every agent i ∈ [n], and there exists some agent j ∈ [n] such that c(Aj) < c(A′j ). An allocation is Pareto optimal if it is not Pareto dominated by any other allocation.

In other words, an allocation is PO if we cannot reduce the cost of one agent without increasing it for some other agent. Let us now follow up on Example 1 and analyze allocations satisfying our notions.

Example 2. Consider the instance with 2 agents and the graph from Figure 1. As previously noted, there are only two SO allocations and neither is EF1 or MMS.

PO allocation ({d, e, f, g}, {a, b, c}) satisfies MMS (vertex g must be serviced by some agent, hence the MMS cost cannot be smaller than 5), but it is not EF1. In fact, there is no EF1 and PO allocation in this instance, as an agent servicing g has to service f, e and d as well (otherwise giving them to this agent would be a Pareto improvement). But then, even when we assign the remaining vertices, a, b, c, to the second agent, the allocation would violate EF1.

Finally, observe that allocation ({a, b, f}, {c, d, e, g}) is EF1, but not MMS.

In order to study the (co-)existence of these fairness and efficiency notions, we use leximin optimality. Let us first set up some notation before defining it. Given an allocation A, we can sort it in non-increasing cost order to obtain allocation B = sort(A) such that c(B1) ≥ c(B2) ≥ · · · ≥ c(Bn) and Bi = Aπ(i) for every agent i ∈ [n] and some permutation of agents π.

Definition 5 (Leximin Optimality). An allocation A leximin dominates an allocation A′ if there is agent i ∈ [n] such that c(Bi) < c(B′i ) and c(Bj) = c(B′j ) for every j ∈ [i - 1], where B = sort(A) and B′ = sort(A′ ). An allocation is leximin optimal if it is not leximin dominated by any other allocation.

In other words, a leximin optimal allocation first minimizes the cost of the worst-off agent, then minimizes the cost of the second worst-off agent, and so on. We note that a leximin optimal allocation is always Pareto optimal as well.

3 Existence of Fair Allocations

In this section, we consider the existence and computation of EF1 and MMS allocations.

Recall that our cost functions are submodular and monotone. Thus, an EF1 allocation can be obtained by adapting an envy-graph algorithm from Lipton et al. [2004]: start with each agent having an empty set, pick an agent who currently has minimum cost (i.e., a sink of the envy-graph) and out of the unassigned vertices give them the one that results in a minimal increase of the cost. Repeat this till all vertices in V \ {h} are allocated. This algorithm always returns an EF1 solution as long as valuations are identical and monotone.

Proposition 1. Given a delivery instance I = ⟨[n], G, h⟩, an EF1 allocation always exists and can be computed in polynomial time.

An MMS allocation in our setting always exists. It follows from the fact that agents have identical cost functions (an allocation that minimizes the maximum cost will satisfy MMS). However, finding such an allocation is NP-hard. To establish this, we first show the hardness of finding the MMS cost.

Proposition 2. Given a delivery instance I = ⟨[n],G, h⟩, finding the MMS cost is NP-hard.

Theorem 1. Given a delivery instance I = ⟨[n],G, h⟩, an MMS allocation always exists, however, finding such an allocation is NP-hard.

Proof. The existence of MMS allocations follows from the cost functions being identical. The same allocation will give the MMS threshold for all agents, hence would satisfy MMS for all. Further, for each instance I and MMS allocation A the cost of the agent that is the worst off, must be equal to MMS cost, i.e., maxi∈[n] c(Ai) = MMSi(I). Hence, if we had a polynomial time algorithm for finding an MMS allocation, we would be able to find MMS cost by looking at the maximal cost of an agent. Since by Proposition 2 the latter is NP-hard, there is no such algorithm unless P = NP .

4 Characterizing Fair and Efficient Solutions

Example 2 established the possible incompatibility of fairness and efficiency in our setting. In this section, we exploit the structure provided by trees to characterize the space of delivery instances for which fair and efficient allocations exist. We first discuss social optimality and then turn our attention to Pareto optimality.

4.1 Social Optimality

In every socially optimal allocation, each edge is traversed by a unique agent, thus the sum of all agents costs is m (the number of edges in a tree with m + 1 vertices). This is a very demanding condition, hence it is not surprising that it may be impossible to satisfy it together with some fairness requirement. We show that checking if there exists a social optimal and fair allocation is computationally hard.

Proposition 3. Given a delivery instance I = ⟨[n],G, h⟩, an SO allocation that satisfies EF1 or MMS need not exist. Moreover, checking whether an instance admits such an allocation is NP-hard.

Despite the computational hardness result, we exploit the tree structure to characterize instances with such allocations.

Theorem 2. Given a delivery instance I = ⟨[n], G, h⟩:

1. An EF1 and SO allocation exists if and only if there is a partition (P1, . . . , Pn) of branches out of h such that ∑B∈Pi |B| - ∑B∈Pj |B| ≤ 1, for every i, j ∈ [n],
2. An MMS and SO allocation exists if and only if there is a partition (P1, . . . , Pn) of branches outgoing from h such that ∑B∈Pi |B| ≤MMSi(I) for every i ∈ [n].

By Proposition 3, checking the condition in point a of the above theorem is NP-hard. However, we develop a polynomial-time verifiable necessary condition for EF1 and SO existence using the notion of the center of the graph (which was studied in computational social choice [Skibski, 2023] and in theoretical computer science in general [Goldman, 1971]).

Definition 6. The center of a tree G = (V,E) is a set of vertices C = arg minv∈V ∑u∈V dist(u, v), where dist(x, y) is the length of a shortest path from x to y.

Proposition 4. Given a delivery instance I = ⟨[n],G, h⟩, there exists an EF1 and SO allocation only if the hub is in the center of the tree.

4.2 Pareto Optimality

Given the challenges in satisfying SO, we now focus on Pareto optimality. Recall that all SO allocations are PO, but not vice versa. We begin by noting that an MMS and PO allocation always exists, but the same is not true for an EF1 and PO allocation.

Proposition 5. Given a delivery instance I = ⟨[n], G, h⟩,

1. an EF1 and PO allocation need not exist,
2. an MMS and PO allocation always exists.

The central result of this section is the proof that every EF1 and PO allocation will satisfy MMS as well. This comes in contrast to typical fair chore division settings, where under additive preferences EF1 and MMS are independent notions even in the presence of efficiency requirements. To this end, we first prove an insightful necessary condition for EF1 and PO allocations: in every such allocation, the pairwise difference in the costs of agents cannot be greater than 1.

Proposition 6. Given a delivery instance I = ⟨[n], G, h⟩ and an EF1 allocation A, if |c(Ai) - c(Aj)| > 1 for some agents i, j ∈ [n], then A is not PO.

Proof. Without loss of generality, assume that A is sorted in non-increasing cost order, i.e., c(A1) ≥ · · · ≥ c(An) (otherwise we can relabel the agents). We will show that if c(An) < c(A1) - 1, then A is not PO, i.e., it is Pareto dominated by some allocation A′ (not necessarily EF1).

For every vertex x ∈ V \ {h}, by p(x) let us denote the parent of x in a tree G rooted in h. Also, for every agent i ∈ [n], let w(i) be the worst vertex in i's bundle, i.e., the vertex which on removal gives the largest decrease in cost (if there is more than one we take an arbitrary one). Formally, w(i) = argmaxx∈Ai c(Ai) - c(Ai \ {x}). Since A is EF1, for every agent i with maximal cost, i.e., such that c(Ai) = c(A1), we have

Observe that this is only possible if the parent of w(i) is not serviced by i, i.e., p(w(i)) ̸∈ Ai. To construct allocation A′ which Pareto dominates A, we look at the agent servicing the parent of the worst vertex of agent 1, call this agent i1 . If i1 incurs maximum cost, we look at the agent servicing the parent of the worst vertex of i1. We continue in this manner and obtain a maximal sequence of pairwise disjoint agents 1 = i0, i1, . . . , ik such that p(w(is-1)) ∈ Ais and c(Ais ) = c(A1) for every s ∈ [k]. The cost incurred by the agent servicing the parent of the worst vertex of ik, which we denote by i∗ (i.e., p(w(ik)) ∈ Ai∗) can create two cases. Either i∗ does not incur maximum cost, i.e., c(Ai∗) < c(A1) (Case 1), or it already appears in the sequence, i.e., i∗ = ij for some j < k (Case 2).

Case 1. Consider allocation A′ obtained from A by exchanging the bundles of agent ik and agent i∗ with the exception of w(ik) (which continues to be serviced by ik). See Figure 2 for an illustration. Formally, A′i∗ = Aik \ {w(ik)}, A′ik =Ai∗ ∪{w(ik)}, and A′t =At, for every t ∈ [n]\{i∗, ik}. Since costs of agents in [n] \ {i∗ , ik} are not affected, it suffices to prove that the cost of either ik or i∗ decreases without increasing the other's cost. To this end, observe that since parent of w(ik) belongs to Ai∗, adding this vertex to Ai∗ increases the cost by 1, i.e.,

Now, let us consider two subcases based on the original difference in costs of agents ik and i∗ .

If it is greater than one, i.e., c(Aik ) > c(Ai∗) + 1, then from Equation (2) we get that c(A′ik ) = c(Ai∗ )+1 < c(Aik ). Hence, the cost of ik decreases. On the other hand, by Equation (1), c(A′i∗) = c(Aik \ {w(ik)}) ≤ c(An) ≤ c(A′i∗), so agent i∗ does not suffer from the exchange.

Otherwise, the difference in costs is exactly one, i.e., c(Aik ) = c(Ai∗) + 1. Now, the cost of ik stays the same by Equation (2). However, since c(An) < c(A1) - 1, it must be that c(An) < c(Ai∗). Thus, from Equation (1) we have c(A′i∗) ≤ c(An) < c(Ai∗), i.e., the cost of i∗ decreases.

Case 2. When i∗ = ij for some j < k, we have a cycle of agents i∗ = ij, ij+1, . . . , ik such that c(Ais ) = c(A1) and p(w(is)) ∈ Ais+1 for every s ∈ {j, . . . , k} (we denote ij as ik+1 as well for notational convenience). Here, we consider two subcases, based on whether it happens somewhere in the cycle that the parent of the worst vertex of one agent is the worst vertex of the next agent, i.e., p(w(is)) = w(is+1) for some s ∈ {j, . . . , k}.

Case 2a. If this is the case, consider A′ obtained from A by giving w(is+1) to agent is. Formally, A′is+1 = Ais+1 \ {w(is+1)}, A′is = Ais ∪ {w(is+1)}, and A′t = At, for every t ∈ [n] \ {is, is+1}. Now, the cost of agent is+1 decreases as it no longer services its worst vertex. Since agent is was servicing a child of w(is+1), it was visiting w(is+1) on the way. Hence, the cost of is stays the same. As the bundles of the remaining agents did not change, A′ Pareto dominates A.

Case 2b. Finally, if in the cycle there is no agent for which the parent of its worst vertex is the worst vertex of the next agent, we swap the worst vertices along the cycle (e.g. in Figure 2). Formally, A′is = Ais \ {w(is)} ∪ {w(is-1)} for every s ∈ {j + 1, . . . , k + 1} and A′i = Ai for every i ∈ [n] \ {ij+1, . . . , ik+1}. As each is is servicing the parent of the worst vertex of the previous agent in the cycle, i.e., p(w(is-1)) ∈ A′is , servicing w(is-1) incurs an additional cost of 1. However, from Equation (1) giving away the worst vertex decreases the cost by more than 1. Hence, the cost of each agent in the cycle decreases. The other agents' costs stay the same, thus A′ Pareto dominates A.

We can now show that EF1 and PO imply MMS.

Theorem 3. Given a delivery instance I = ⟨[n], G, h⟩, every EF1 and PO allocation satisfies MMS.

Proof. We show a stronger result that an EF1 and PO allocation A is necessarily leximin optimal (thus, also MMS). Without loss of generality, let A be s.t. c(A1) ≥ · · · ≥ c(An). By contradiction, suppose that there exists A′ (also sorted) that leximin dominates A, i.e., there exists i ∈ [n] such that c(A′i ) < c(Ai) and c(A′j ) = c(Aj) for every j ∈ [i - 1]. Fix an agent j ∈ [n] such that j > i. From Proposition 6 we know that its cost is either c(Aj) = c(Ai) or c(Aj) = c(Ai) - 1. On the other hand, we assumed that c(A′j ) ≤ c(A′i ) < c(Ai). Hence, c(A′j ) ≤ c(Ai) - 1 ≤ c(Aj). Thus, A′ also Pareto dominates A, which is a contradiction.

From the proof of the above theorem we obtain the following characterization.

Corollary 1. Given a delivery instance I = ⟨[n],G, h⟩, an EF1 and PO allocation exists if and only if for every leximin optimal allocation A, maxi,j∈[n] |c(Ai) - c(Aj)| ≤ 1.

Finally, by modifying the proof of Proposition 2 we show that deciding if there exists a PO allocation that is EF1 is also NP-hard. Also, we note that hardness for MMS and PO is directly implied by Proposition 2.

Proposition 7. Given a delivery instance I = ⟨[n],G, h⟩, checking whether there exists an EF1 and PO or finding an MMS and PO allocation is NP-hard.

Algorithm 1 FindParetoFrontier(n, G,h)

• 1: F ← [(∅, . . . ,∅)]
• 2: for u ∈ children of h do
• 3: Tu ←a subtree rooted in u
• 4: F ′ ←FindParetoFrontier(n, Tu, u)
• 5: for A ∈ F ′ do add u to A1
• 6: F ←maximal set of sorted combinations of allocations from F and F ′ such that none is weakly Pareto dominated by another within the set
• 7: end for
• 8: return F

5 Computing Fair and Efficient Solutions

We have shown that finding a fair and efficient allocation (or deciding if it exists) is computationally hard. In this section, we develop a recursive algorithm for computing each combination of the fairness-efficiency notions that is XP with respect to the number of agents, i.e., when the number of agents is bounded, the running time of our algorithm is polynomial. Let us start by defining a notion of Pareto frontier as a set of Pareto optimal solutions and introduce Algorithm 1 that finds such set for every delivery instance.

Definition 7. Given a delivery instance I = ⟨[n],G, h⟩, its Pareto frontier is a minimal set of allocations F such that for every PO allocation A there exists B ∈ F and permutation of agents π such that c(Ai) = c(Bπ(i)), for every i ∈ [n].

Algorithm. Throughout the algorithm, we keep allocations in the list F, each allocation sorted in non-increasing cost order. First, we initialize it with just one empty allocation. Then, we look at vertices directly connected to the hub. For each, say u, we run our algorithm on a smaller instance where the graph is just the branch outgoing from h that u is on, and u is the hub. In each allocation in the output, F ′ , we add u to the bundle of the first agent. Finally, we combine these allocations, by looking at all possible sorted combinations of allocations in both lists, and keeping only the ones that are not weakly Pareto dominated by any other (where an allocation weakly Pareto dominates another allocation if it Pareto dominates it, or all agents have equal costs in both allocations).

Example 3. We run our algorithm on the instance with 2 agents from Figure 1. First, we run it on two smaller graphs: the vertex a as one and one on the branch containing vertices b, c, d, e, f and g. Vertex a is a leaf, so we get one allocation, i.e., F = {({a},∅)}. When b is the hub, we obtain two allocations: either one agent services g along with all its ancestors and the other agent services c, or one agent services everything. Thus, F ′ = {({b, d, e, f, g}, {c}), ({b, c, d, e, f, g},∅)}. Finally, we combine F with F ′ . We consider all four possible combinations. However, one of them, ({a, b, d, e, f, g}, {c}) is Pareto dominated by another, ({b, c, d, e, f, g}, {a}) (the cost of the first agent is the same, but for the second agent it decreases by 1). In conclusion, we return three allocations: ({b, d, e, f, g}, {a, c}), ({b, c, d, e, f, g}, {a}), and ({a, b, c, d, e, f, g},∅). We note that the first one is in fact MMS and PO allocation.

Now, let us prove the correctness of our algorithm.

Theorem 4. Given a delivery instance I = ⟨[n],G, h⟩, Algorithm 1 computes its Pareto frontier and runs in time O((n + 2)!m3n+2 ), where m = |E(G)|.

Proof (sketch). Here, we note two key observations.

For the first, consider an arbitrary instance ⟨[n],G, h⟩, and a smaller one obtained by taking a subtree rooted in some vertex u ∈ V , i.e., ⟨[n], Tu, u⟩. Then, every PO allocation A in the original instance, must be still PO when we cut it to the smaller instance (i.e., we remove vertices not in Tu). Otherwise, a Pareto improvement on the cut allocation, would also be a Pareto improvement for A. Hence, by looking at all combinations of PO allocations on the branches outgoing from h, we obtain all PO allocations in the original instance.

The second observation is that we do not need to keep two allocations that give the same cost for each agent. The maximum cost of each agent is m. Hence, we will never have more than (m+ 1)n different allocations in the list (in fact, since we keep all allocations sorted in non-increasing cost order, this number will be much smaller). Thus, we can combine two frontiers efficiently.

We can use Algorithm 1 to obtain the desired allocations.

Theorem 5. There exists an XP algorithm parameterized by n, that given a delivery instance I = ⟨[n],G, h⟩, computes an MMS and PO allocation, and decides whether there exist MMS and SO, EF1 and PO, and EF1 and SO allocations.

Proof (sketch). Here, we focus on MMS and PO allocations (see the full version of the paper for the other notions). By Theorem 4, we can obtain a Pareto frontier for every instance. Also, from the proof of Theorem 4, we know that a Pareto frontier contains at most (m+ 1)n allocations. Thus, we can search through them to find the leximin optimal one, which will be MMS and PO as well.

We note that the proof for EF1 and PO here relies on Cor. 1.

6 Price of Fairness

In this section, we study the price of fairness, i.e., the loss to a total cost incurred by requiring EF1 or MMS while delivery tasks located on the vertices of an weighted tree. Specifically, we show tight bounds for the relative amount of such additional cost. The price of fairness has been well studied in the fair division literature and merits exploration in delivery settings as well [Barman et al., 2020; Sun et al., 2023; Bhaskar et al., 2023]. Formally, it is defined as the ratio of the minimum total cost of allocation satisfying given notion to the minimum total cost of any allocation.

Definition 8 (Price of Fairness). Given a fairness concept F and an instance I = ⟨[n], G, h⟩, the price of F is given as:

In the following proposition we identify the tight bounds for the price of EF1 and MMS.

Proposition 8. Given a delivery instance I = ⟨[n],G, h⟩, it holds that PoMMS(I) ≤ n(m-n+1) m and PoEF1(I) ≤ n(2m-n+1) 2m . Both these bounds are tight.

We note that the bound for the price of MMS is lower, which matches our intuition that MMS is more compatible with efficiency in our setting. In the full version of the paper, we also show the hardness of finding cost minimizing allocations satisfying MMS or EF1 and prove that for MMS such allocation has to be PO (which is not the case for EF1). This allows us to use Algorithm 1 to calculate the price of MMS and study it in numerical experiments.

7 Experiments

We now present our experimental results concerning the existence of EF1 and PO allocations and investigate the efficiency loss of fair solutions through their price of fairness. We also check the running time of our algorithm, which we report in the full version of the paper [Hosseini et al., 2023a]. In each experiment, we generated trees, uniformly at random, based on Prüfer sequences [Prüfer, 1918] using NetworkX Python library [Hagberg et al., 2008]. 3 For each experiment and a graph size, we sampled 1,000 trees.

Experiment 1. EF1 and PO existence. First, we checked how often there exists an EF1 and PO allocation. To this end, we generated trees of sizes 10, 20, . . . , 100 and for each tree we run Algorithm 1 for each number of agents from 2 to 6. Based on the output, we checked the number of trees that admit an EF1 and PO allocation. As shown in Figure 3a, the probability of finding an EF1 and PO allocation increases steadily when we increase the size of the graph, but drops sharply when we increase the number of agents. Intuitively, on larger graphs we have more flexibility in how we fairly and efficiently split the vertices. However, when there are more agents, it may still be difficult to satisfy fairness for each of them. We repeat a similar experiment for EF1 and SO as well as MMS and SO allocations in the full version of the paper.

Experiment 2. Price of Fairness. Next, we analyze the price of MMS. To this end, we generated trees of sizes 100, 200, 300, 400 and we run Algorithm 1 for two agents (we also consider larger instances in the full version). Figure 3b illustrates that the median price is around 1.15 for the graphs of size 100 and it steadily decreases for the larger graphs. These results suggest that as the size of the instance grows, the efficiency loss due to MMS becomes negligible in most cases (at least for a small number of agents).

3 The code for our experiments is available at: https://doi.org/10. 5281/zenodo.11149658.

Experiment 3. Pareto Frontiers. In our final experiment, we analyze the trade-off between fairness and the total cost of agents in singular Pareto frontiers. To this end, we focus on a single size of a graph, 400, and two agents. For each one of 1000 trees generated, we look at each allocation in the Pareto frontier and report the total cost of both agents on yaxis and the difference in costs of agents on x-axis. Then, we connect all such points for allocations in one Pareto frontier to form a partially transparent blue line. By superimposition of all 1000 of such blue lines, we obtain a general view on the distribution of Pareto frontiers. With the thick red line we denote the average total cost, for each difference in costs. We see that particular Pareto frontiers can behave very differently, but the general pattern is quite strong: The total cost does not vary much when the difference in costs is between 0 and 250, however it is much steeper for the larger differences. These findings imply that it is usually not effective to focus on partial fairness as the additional total cost that we incur by guarantying complete fairness instead of partial is not that big. We present a similar experiment for different graph sizes and numbers of agents in the full version of the paper.

8 Conclusions and FutureWork

We introduced a novel problem of fair distribution of delivery orders on graphs. We provided a comprehensive characterization of the space of instances that admit fair (EF1 or MMS) and efficient (SO or PO) allocations and-despite proving their hardness-developed an XP algorithm parameterized by the number of agents for each combination of fairness-efficiency notions.

Our work paves the way for future research on developing approximation schemes or perhaps algorithms parameterized by graph characteristics (e.g., maximum degree or diameter) in this domain. Another natural direction is extending our results to cycled and weighted graphs. The model can also be generalized to account for heterogeneous cost functions, capacity constraints of agents, or multiple hubs.

Acknowledgments

Hadi Hosseini acknowledges support from NSF grants #2144413 (CAREER), #2052488, and #2107173. Part of this work was done when Shivika Narang was a visitor at Pennsylvania State University.