## 3 Directed Path Allocation Problems
: _For a DPAP \(\langle\mathcal{A},\mathcal{G},\mu,\phi\rangle\) involving \(n\) agents, the leximin utility vector associated with an allocation \(\pi\) is the vector \(\text{lex}(\pi)=(\Lambda_{1},\ldots,\Lambda_{n})\) that corresponds to vector \((u_{1}(\pi),\ldots,u_{n}(\pi))\) sorted following an increasing order (\(\Lambda_{i}\leq\Lambda_{j}\) holds for \(i<j\))._  
If \(\pi\) and \(\pi^{\prime}\) denote two allocations for a given DPAP, and \(\text{lex}(\pi)=(\Lambda_{1},\ldots,\Lambda_{n})\) and \(\text{lex}(\pi^{\prime})=(\Lambda^{\prime}_{1},\ldots,\Lambda^{\prime}_{n})\) are their associated leximin utility vectors, \(\pi\) is strictly better than \(\pi^{\prime}\) with respect to the leximin criterion if there exists \(k\) in \([1..n]\) such that \(\Lambda_{k}>\Lambda^{\prime}_{k}\) and for all \(i<k\), \(\Lambda_{i}=\Lambda^{\prime}_{i}\). Note that leximin-based fair allocations allow the favoring of agents that are less satisfied. The problems we consider in this paper are: (i) how to compute an optimal (utilitarian) valid allocation \(\pi\) that maximizes \(u(\pi)\), and (ii) how to compute an optimal fair valid allocation \(\pi\) that maximizes \(\text{lex}(\pi)\). **Example 2**. : _In the graphs described in Example 1 and illustrated in Figure 1, the individual best paths for agents \(\mathsf{A}\) and \(\mathsf{B}\) are \(\{\mathsf{s}_{\mathsf{a}},\mathsf{a}_{3},\mathsf{a}_{2},\mathsf{f}_{\mathsf{a}}\}\) and \(\{\mathsf{s}_{\mathsf{b}},\mathsf{b}_{1},\mathsf{b}_{2},\mathsf{f}_{\mathsf{b}}\}\), respectively. They both have a utility equal to \(1\). However, these paths are not compatible according to the list of forbidden paths and cannot both belong to a valid allocation._  
_Figure 2a gives an example of a valid allocation \(\pi_{\text{ex}}=\{g_{\mathsf{a}}\mapsto\{\mathsf{s}_{\mathsf{a}},\mathsf{a}_ {1},\mathsf{a}_{2},\mathsf{f}_{\mathsf{a}}\},\mathsf{g}_{\mathsf{b}}\mapsto \{\mathsf{s}_{\mathsf{b}},\mathsf{b}_{1},\mathsf{b}_{4},\mathsf{f}_{\mathsf{b }}\}\}\) for the DPAP introduced before. The global utility of \(\pi_{\text{ex}}\) is \(u(\pi_{\text{ex}})=u(\pi_{\text{ex}}(\mathsf{A}))+u(\pi_{\text{ex}}(\mathsf{B }))=0.7+0.6=1.3\). The leximin vector associated with \(\pi_{\text{ex}}\) is \(\text{lex}(\pi_{\text{ex}})=(0.6,0.7)\): agent \(\mathsf{B}\) has the lowest utility (\(0.6\)), and agent \(\mathsf{A}\)'s utility is equal to \(0.7\)._  
_Figure 2b illustrates allocation \(\pi_{\text{util}}=\{g_{\mathsf{a}}\mapsto\{\mathsf{s}_{\mathsf{a}},\mathsf{a} _{3},\mathsf{a}_{2},\mathsf{f}_{\mathsf{a}}\},g_{\mathsf{b}}\mapsto\{\mathsf{ s}_{\mathsf{b}},\mathsf{b}_{1},\mathsf{b}_{4},\mathsf{f}_{\mathsf{b}}\}\}\) that maximizes the global utility: \(u(\pi_{\text{util}})=1.0+0.6=1.6\). The leximin vector is \(\text{lex}(\pi_{\text{util}})=(0.6,1.0)\)._  
_Figure 2c illustrates allocation \(\pi_{\text{lex}}=\{g_{\mathsf{a}}\mapsto\{\mathsf{s}_{\mathsf{a}},\mathsf{a} _{1},\mathsf{a}_{2},\mathsf{f}_{\mathsf{a}}\},g_{\mathsf{b}}\mapsto\{\mathsf{ s}_{\mathsf{b}},\mathsf{b}_{3},\mathsf{b}_{4},\mathsf{f}_{\mathsf{b}}\}\}\) that maximizes the leximin vector: \(\text{lex}(\pi_{\text{lex}})=(0.7,0.7)\). The global utility associated with \(\pi_{\text{lex}}\) is lower: \(u(\pi_{\text{util}})=1.4\)._  
Figure 2: Examples of valid allocations for the DPAP described in Figure 1. (**a**) Illustration of allocation \(\pi_{\text{ex}}\) with the paths selected in graphs \(g_{a}\) and \(g_{\mathsf{b}}\). (**b**) Allocation \(\pi_{\text{util}}\) that maximizes the global utility: \(u(\pi_{\text{util}})=1.6\). (**c**) Allocation \(\pi_{\text{lex}}\) that maximizes the leximin vector: \(\text{lex}(\pi_{\text{lex}})=(0.7,0.7)\).