## 6 V-DPAP Solution Methods
### Leximin Allocation (lex)  
Beyond utilitarianism, one way to implement fair allocation and Pareto-optimality is to consider the _leximin_ rule, that selects, among all possible allocations, an allocation leading to the best utility profiles with respect to the leximin order [22]. More precisely, let \(z=[z_{1},\ldots,z_{n}]\) be the utility vector, where each component \(z_{a}\in[0,Z_{a}]\) represents the utility for agent \(a\in\mathcal{A}\). \(Z_{a}\) denotes here the best utility value for user \(a\) considered alone, i.e., for the mono-agent problem, where the best path can be chosen for each graph \(g\in\mathcal{G}_{a}\). In leximin optimization, the objective is to lexicographically maximize vector \(\Lambda=[\Lambda_{1},\ldots,\Lambda_{n}]\) obtained after ordering \([z_{1},\ldots,z_{n}]\) following an increasing order. Such a leximin rule can be implemented through a sequence of ILP [23]. We adapt here such a procedure to the specific case of V-DPAP. Suppose we have already optimized over the first \(K-1\) components \([\Lambda_{1},\ldots,\Lambda_{K-1}]\) of \(\Lambda\), for \(K\in[1..n]\). Then, one can use the MILP presented thereafter to optimize the \(K^{\text{th}}\) component \(\Lambda_{K}\) of the leximin profile. In this MILP model, variable \(\lambda\) represents the utility optimized at level \(K\) in \(\Lambda\), with \(\lambda\in[\Lambda_{K-1},\max_{a\in\mathcal{A}}Z_{a}]\), using convention \(\Lambda_{0}=0\). Variable \(y_{ak}\) is a binary variable that takes value \(1\) if agent \(a\in\mathcal{A}\) plays the role of the agent associated with level \(k\in[1..K-1]\) in \([\Lambda_{1},\ldots,\Lambda_{K-1}]\), and \(0\) otherwise. Constraint (10) computes the utility associated with each agent. Constraints (11) and (12) ensure that a unique agent is associated with each level \(k\in[1..K-1]\) already dealt with. Constraint (13) ensures that the utility obtained for the agent associated with level \(k\in[1..K-1]\) must not be less than \(\Lambda_{k}\). Last, together with the objective function, Constraint (14) ensures that \(\lambda\) will be equal to the minimum utility value obtained for the agents that are not associated with levels \([1..K-1]\) in \(\Lambda\). In this constraint, \(M=\max_{a\in\mathcal{A}}Z_{a}\) is used to ignore the agents associated with levels strictly lower than \(K\) when optimizing \(\lambda\) (big-M formulation). In the end, the optimization of \(\Lambda_{K}\) can be performed using program \(P_{\text{lex}}(\langle\mathcal{A},\mathcal{G},\mu,\mathcal{C}\rangle,K,[ \Lambda_{1},\ldots,\Lambda_{K-1}])\) that is composed of constraints (1)-(7) and the additional constraints and objective function given below:  
\[\text{\bf maximize}\ \ \ \ \lambda \tag{9}\] \[z_{a}=\sum_{g\in\mathcal{G}_{a}}\sum_{e\in E_{g}}u_{g}(e)\cdot x _{e},\ \ \ \forall a\in\mathcal{A}\] (10) \[\sum_{a\in\mathcal{A}}y_{ak}=1,\ \ \ \forall k\in[1..K-1]\] (11) \[\sum_{k\in[1..K-1]}y_{ak}\leq 1,\ \ \ \forall a\in\mathcal{A}\] (12) \[z_{a}\geq\sum_{k\in[1..K-1]}\Lambda_{k}\cdot y_{ak},\ \ \ \forall a\in\mathcal{A}\] (13) \[\lambda\leq z_{a}+M\sum_{k\in[1..K-1]}y_{ak},\ \ \ \forall a\in \mathcal{A} \tag{14}\]\[z_{a}\in[0,Z_{a}],\,\forall a\in\mathcal{A} \tag{15}\] \[y_{ak}\in\{0,1\},\,\forall a\in\mathcal{A},\forall k\in[1..K-1]\] (16) \[\lambda\in[\Lambda_{K-1},\max_{a\in\mathcal{A}}Z_{a}] \tag{17}\]  
To implement the leximin rule, it then suffices to solve a sequence of \(P_{\text{lex}}\) problems for \(K\in\mathcal{A}\) to optimize the value of each component of the utility profile, as presented in Algorithm 1. ```
Data: A V-DPAP \(\langle\mathcal{A},\mathcal{G},\mu,\mathcal{C}\rangle\) Result: A leximin-optimal path allocation \(\pi\)
1 for\(K=1\)to\(|\mathcal{A}|\)do
2\((\lambda^{*},\text{sol})\leftarrow\) solve \(P_{\text{lex}}(\langle\mathcal{A},\mathcal{G},\mu,\mathcal{C}\rangle,K,[ \Lambda_{1},\ldots,\Lambda_{K-1}])\)
3\(\Lambda_{K}\leftarrow\lambda^{*}\)for\(g\in\mathcal{G}\)do\(\pi(g)\leftarrow\{v\in V_{g}\mid\text{sol}(g_{v})=1\}\) return\(\pi\)
```  
**Algorithm 1**Leximin algorithm.