## 3 Directed Path Allocation Problems
In this example, we consider two agents \(\mathsf{A}\) and \(\mathsf{B}\) that each have one observation request, request \(\mathsf{a}\) for agent \(\mathsf{A}\) and request \(\mathsf{b}\) for agent \(\mathsf{B}\)._  
_Within the DPAP modeling framework, we consider a graph for each request: graph \(g_{\mathsf{a}}\) for request \(\mathsf{a}\) and graph \(g_{\mathsf{b}}\) for request \(\mathsf{b}\). The nodes of these graphs are the orbit slot candidates for each request (slots \(\mathsf{a}_{1}\), \(\mathsf{a}_{2}\), and \(\mathsf{a}_{3}\) for request \(\mathsf{a}\), and slots \(\mathsf{b}_{1}\), \(\mathsf{b}_{2}\), \(\mathsf{b}_{3}\), and \(\mathsf{b}_{4}\) for request \(\mathsf{b}\)). A path in a graph represents a way to satisfy the corresponding request. For instance, for satisfying request \(\mathsf{a}\), starting from \(\mathsf{a}_{\mathsf{a}}\), one can either select first slot \(\mathsf{a}_{1}\) and then slot \(\mathsf{a}_{2}\), or select first slot \(\mathsf{a}_{3}\) and then slot \(\mathsf{a}_{2}\). Each edge has a utility that represents the reward for selecting slots in a given order. For instance, edges \(\mathsf{a}_{\mathsf{a}}\to\mathsf{a}_{1}\) and \(\mathsf{a}_{\mathsf{a}}\to\mathsf{a}_{3}\) have utilities equal to \(0.2\) and \(0.5\), respectively. This represents the fact that agent \(\mathsf{A}\) prefers selecting slot \(\mathsf{a}_{3}\) rather than selecting slot \(\mathsf{a}_{1}\). Such a difference can be due to a satellite viewing angle that is better for \(\mathsf{a}_{3}\) than for \(\mathsf{a}_{1}\). Note that for a node, its incoming edges do not necessarily have the same utility value. For instance, the utility of edge \(\mathsf{b}_{1}\to\mathsf{b}_{4}\) is equal to \(0.1\), whereas the utility of edge \(\mathsf{b}_{3}\to\mathsf{b}_{4}\) is equal to \(0.3\)._  
_The graph associated with request \(\mathsf{a}\) contains three possible paths while the graph associated with request \(\mathsf{b}\) contains five possible paths. We assume here that only \(10\) combinations of paths are allowed by the path compatibility function \(\phi\) among the \(15\) possible ones. For instance, paths \(\pi_{\mathsf{a},1}\) and \(\pi_{\mathsf{b},2}\) are compatible (\(\phi(\pi_{\mathsf{a},1},\pi_{\mathsf{b},2})=1\)) but paths \(\pi_{\mathsf{a},1}\) and \(\pi_{\mathsf{b},3}\) are not (\(\phi(\pi_{\mathsf{a},1},\pi_{\mathsf{b},3})=0\))._  
**Definition 3**. : _For a DPAP \(\langle\mathcal{A},\mathcal{G},\mu,\phi\rangle\), an allocation is a function \(\pi\) that associates, with each graph \(g\in\mathcal{G}\), one path \(\pi(g)\) from \(s_{g}\) to \(t_{g}\) in \(g\). If \(\mathcal{G}=\{g_{1},\ldots,g_{m}\}\), such an allocation is valid if and only if \(\phi(\pi(g_{1}),\ldots,\pi(g_{m}))=1\) holds. Formally, \(\pi(g)\) can be represented as a set of nodes in \(V_{g}\). Indeed, as DAGs are manipulated, it is easy to reconstruct the edges successively traversed by the path from this set._  
Figure 1: Sample users’ bundle valuations (or preferences) represented as a DPAP. **Definition 4**. : _For a DPAP \(\langle\mathcal{A},\mathcal{G},\mu,\phi\rangle\), the global utility \(u(\pi)\) associated with an allocation \(\pi\) is the sum of the utilities obtained in each graph, that is \(u(\pi)=\sum_{g\in\mathcal{G}}u_{g}(\pi(g))\). The utility obtained for agent \(a\) is \(u_{a}(\pi)=\sum_{g\in\mathcal{G}_{a}}u_{g}(\pi(g))\)._  
**Definition 5**.