  We initiate the study of fair distribution of delivery tasks among a set of
agents wherein delivery jobs are placed along the vertices of a graph. Our goal
is to fairly distribute delivery costs (modeled as a submodular function) among
a fixed set of agents while satisfying some desirable notions of economic
efficiency. We adopt well-established fairness concepts -- such as
envy-freeness up to one item (EF1) and minimax share (MMS) -- to our setting
and show that fairness is often incompatible with the efficiency notion of
social optimality. We then characterize instances that admit fair and socially
optimal solutions by exploiting graph structures. We further show that
achieving fairness along with Pareto optimality is computationally intractable.
We complement this by designing an XP algorithm (parameterized by the number of
agents) for finding MMS and Pareto optimal solutions on every tree instance,
and show that the same algorithm can be modified to find efficient solutions
along with EF1, when such solutions exist. The latter crucially relies on an
intriguing result that in our setting EF1 and Pareto optimality jointly imply
MMS. We conclude by theoretically and experimentally analyzing the price of
fairness.
