## 4 Privacy-Preserving Incentive Mechanism
### Collaborative Routing Scheme
\(\mathcal{L}^{R}\) reports \(n_{s}\) to the RSU nearby, which will update the flows related to this OD pair iteratively together with other RSUs in a distributed manner following the route flow assignment model in [21]. 5. At the same time, \(\mathcal{L}^{R}\) and \((n_{s}-1)\)\(\mathcal{T}^{R}\) start establishing the communication network for the MPC protocol. \(\mathcal{L}^{R}\) produces a participation confirmation message,\(\{<ID_{1},ID_{2},\ldots,ID_{n_{s}}>,<sig_{ID_{1}},sig_{ID_{2}},\ldots,sig_{ID_{n_{ s}}}>\}\), which generates an order for all participants. 6. After \(\mathcal{F}^{R}\) receive the confirmation message, they start creating secret shares of their value of time. \(\lambda_{ID_{i}}\) is denoted as the value of time of the \(i\)th vehicle (\(i\in[1,\ 2,\ \ldots,\ n_{s}]\) in the confirmation message. The vehicle creates secret shares \(s_{ij},\ j\in[1,\ 2,\ \ldots,\ n_{s}]\) for the \(j\)th vehicle and sends it. 7. After the RSU receives optimal route flows, it broadcasts the information as public inputs of the MPC protocol. Note that step 6 takes the most time out of the entire process as there are \(n_{s}(n_{s}-1)\) messages sent. However, this happens while RSUs are solving for the optimal flows, which is also the most time-consuming step in the hierarchical framework in [21], which mitigates the influence of step \(6\)'s relatively long computation time. With all required private and public inputs, the vehicles can execute the MPC protocol to produce the private outputs, which consists of their updated routes and corresponding incentives. However, MPC protocols are pre-compiled, which means that they have a fixed number of inputs, while the number of vehicles participating in the collaborative routing scheme varies in the real world. Hence, the vehicle assignment model and incentive mechanism proposed in [21] are modified as follows. Assume that the MPC protocol requires \(N\) vehicles to collaboratively update their routes (\(N\) is the maximum number of participants allowed in the scheme, determined by step 6 in practice). According to _Lemma 3_ in [21], the vehicle assignment is to sort vehicles' value of time. We can create \((N-n_{s})\) fake vehicles with zero value of time to complement the number of inputs required by the MPC protocol. In this way, the updated routes of the participants are the same as the ones they are supposed to obtain in the vehicle route assignment model. When determining the incentives, the protocol assumes that fake vehicles take a fake route with the same travel time as the longest travel time of all real routes. According to _Lemma 4_ in [21], the adjustment incentives of the fake vehicles are zero and the real vehicles' adjustment incentives are the same as those they are supposed to obtain from the incentive mechanism in [21]. The details of the MPC protocol for route/incentive assignment (Algorithm 1) are described as follows. ```
Private input: individual value of time \(\lambda_{i},i=1,\ 2,\ldots,\ n_{s}\). Public input: travel times and optimal route flows for each route \(T_{k},\ f_{k},\ k\in K,\ K\) is the route id set (\(\sum f_{k}=n_{s}\)). Public output: incentives \(p_{k}\) for each route \(k\in K\). Sort \(\lambda_{i}\) (denote smallest as \(\lambda_{\min}\) and \(T_{k}\) add \(N-n_{s}\) vehicles with \(\lambda_{i}=0\), and add \(N-n_{s}\) flow to route with largest travel time. Duplicate \(T_{k}\) for \(f_{k}\) times such that there are \(N\) travel times in total. Assign the vehicle with the \(r\)th largest value of time, \(\lambda^{(r)}\), to the route with \(r\)th shortest travel time \(T^{(t)}\) (denoted as \(\eta^{(t)}\)). Compute \(p^{(1)}=\frac{1}{n_{s}}\sum_{j=2}^{N}\sum_{m=2}^{j}\lambda^{(m)}\left(T^{(m) }-T^{(m-1)}\right)\), \(p^{(r)}=\frac{1}{n_{s}}\sum_{j=2}^{N}\sum_{m=2}^{j}\lambda^{(m)}\left(T^{(m) }-T^{(m-1)}\right)-\sum_{m=2}^{r}\lambda^{(m)}\left(T^{(m)}-T^{(m-1)}\right)\) as if there were \(N\) vehicles. Return\(\eta^{(r)}\) and \(p^{(r)}\) to the vehicle with \(\lambda^{(r)}\).