## 3 Directed Path Allocation Problems  
In this section, we define the so-called directed path allocation problem (DPAP), where agents' valuations of item bundles are represented as edge-weighted DAGs, as illustrated in Figure 1, and where the goal is to select one path in each DAG while satisfying set compatibility constraints over the selected paths. We first introduce some notation related to graphs and then formalize the generic problem we consider. **Definition 1**. : _A single-source single-sink edge-weighted DAG \(g\) is a triple \(\langle V_{g},E_{g},u_{g}\rangle\) such that:_  
* \(V_{g}\) _is a set of nodes; in our case, each node corresponds to an item that can be allocated to an agent, except for two specific nodes referred to as the source_ \(s_{g}\) _and the sink_ \(t_{g}\)_;_
* \(E_{g}\subset V_{g}\times V_{g}\) _is the set of arcs of the acyclic graph, with the assumption that_ \(s_{g}\) _and_ \(t_{g}\) _are, respectively, the unique source and sink of the graph; an arc_ \(v_{1}\to v_{2}\) _indicates that items_ \(v_{1}\) _and_ \(v_{2}\) _can be selected sequentially;_
* \(u_{g}:E_{g}\rightarrow\mathbb{R}^{+}\) _is a utility function that associates a weight to each arc of the graph to represent a preference over the combinations of item selections; we assume that_ \(E_{g}\) _contains an arc from_ \(s_{g}\) _to_ \(t_{g}\) _labeled by utility_ \(0\)_, to deal with cases where no bundle of items can be selected in_ \(g\)_._ _In the following, the set of paths from_ \(s_{g}\) _to_ \(t_{g}\) _is denoted by_ \(\Pi_{g}\)_._  
For each graph \(g\) and each set of edges \(X\subseteq E_{g}\), the utility of \(X\) for \(g\) is defined by \(u_{g}(X)=\sum_{e\in X}u_{g}(e)\), which means that edge valuations are additive. As a result, each path from \(s_{g}\) to \(t_{g}\) in a graph \(g\) is evaluated by summing the utilities of the traversed edges, and each DAG represents, in a compact manner, a set of valuations for bundles of items, as in combinatorial auctions. **Definition 2**. : _A Directed Path Allocation Problem (DPAP) is a tuple \(\langle\mathcal{A},\mathcal{G},\mu,\phi\rangle\), where \(\bullet\quad\mathcal{A}=\{1,\ldots,n\}\) is a set of agents;_* \(\mathcal{G}=\{g_{1},\ldots,g_{m}\}\) _is a set of single-source single-sink edge-weighted DAGs, as introduced in Definition_ 1_;_
* \(\mu:\mathcal{G}\to\mathcal{A}\) _maps each graph_ \(g\) _in_ \(\mathcal{G}\) _to its owner_ _a in_ \(\mathcal{A}\)_; we also denote by_ \(\mathcal{G}_{a}=\mu^{-1}(a)\) _the set of graphs owned by agent_ \(a\)_;_
* \(\phi:\Pi_{g_{1}}\times\ldots\times\Pi_{g_{m}}\to\{0,1\}\) _is a path compatibility function that indicates whether a combination of paths_ \((p_{1},\ldots,p_{m})\) _(one path per graph) is feasible (value_ \(1\)_) or not (value_ \(0\)_)._  
In a DPAP, the definition of the path compatibility function \(\phi\) is related to the presence of items that cannot be shared by the agents. More precisely, a conflict between two paths represents the fact that assigning these paths to clients is infeasible (e.g., because some orbit slots overlap) or strongly undesirable for the constellation manager. A naive definition of the compatibility function is the list of combinations of paths that are compatible with each other. However, the number of paths in a DAG is exponential, which makes this definition impractical in the general case. Therefore, in the next sections, we propose and discuss different ways to define the compatibility function in a compact way. **Example 1**. : _Figure 1 illustrates a DPAP representing an orbit slot allocation problem. In such a problem, satellite orbit slots must be allocated to agents so that the latter can make several observations of a POI on Earth.