## 2 Related Works  
The literature contains some work related to the allocation of goods structured as graphs. In fair division of graphs, the objective is to divide a graph of items between several agents, with additive utilities attached to nodes [5; 6]. These works provide interesting properties to find envy-free or Pareto-optimal, allocations in an efficient manner in some specific graph structures, e.g., paths, trees, stars. However, in our problem, (i) agents do not compete for the very same set of items, (ii) the graph is directed to compose paths from a start time to an end time, and (iii) even by mapping our problem to a graph division problem and by regrouping conflicting items into composite items, it is highly improbable that the resulting graph is acyclic. Here, graphs are used to express preferences and not the goods to allocate. In short, our work does not fall into the existing graph fair division frameworks, and cannot benefit from theoretical results on path-shaped or star-shaped graphs. Another related method is path auctions [7; 8; 9], where agents bid for paths in a graph where each edge is owned by an agent. The goal is to assign paths to agents by the means of auctions, and optionally to keep some privacy for the edge owners. In the case of a utilitarian objective function for the winner determination problem, without price privacy, this falls into the Vickrey-Clarke-Groves framework, and thus guarantees some efficient and _strategy-proof_ mechanisms. However, here again, agents bid on the very same set of nodes and edges. In the transportation domain, investigations on very similar structures, that is flow networks, provide techniques for fair maximum flow in multi-source and multi-sink networks [10]. While the techniques used are very similar to ours (linear programming), the maximum flow objective is very different from path utility maximization with a single path per agent. Furthermore, [11] worked on multiple shortest path problems based on deconficting techniques. While the problem displays similar characteristics, once again the agents evolve on the very same graphs, and the objective is focused on minimizing path length and minimizing conflicting paths, without fairness desiderata. In congestion games, agents are allocated paths so that the delays incurred by crossing paths are minimized. The more agents are allocated the same nodes, the more delay is attached to their paths [12; 13]. In our work, we do not consider delay but incompatibilities. Even if they could be modeled as nonlinear \(\{0,\infty\}\) functions, in our problem some path allocations are unfeasible, contrarily to congestion games. Furthermore, using congestion game solution methods, as in [13], may result in unfair Nash equilibria, because of numerous unfeasible paths1. More generally, another classical approach to the fair allocation of indivisible goods is _round-robin_, which is almost envy-free [14]. This is notably one favored technique to allocate virtual network functions in network function virtualization infrastructures [15], or to schedule tasks. We will use it as a competitor for our techniques. In [16], we proposed constraint-programming approaches for fair sharing of orbit slots in the case of Earth observation satellites. We considered several types of requests, such as periodic and global requests. The latter type of requests cannot be modeled within the graph-based framework proposed in this paper. Therefore, we had to enumerate all the ways to (partially) satisfy requests. This enumeration is not required within the framework we propose here, because of the compact graph representation. Moreover, the approaches of [16] were evaluated on small horizons, due to the computational intensiveness of the proposed solution methods. The horizons considered in this paper are much longer. In this paper, we investigate several mathematical programming-based (utilitarian, leximin, approximate leximin) and ad hoc algorithms (greedy, round-robin) to allocate paths in conflicting graphs.