## 2 Mechanism Overview  
This study's problem context is similar to that of our prior study [21]. As depicted in Figure 1, the major objective is to encourage vehicles to reroute collaboratively during their trips in order to improve system performance (specifically, reducing total travel time in this study). When assigning vehicles, the system performance evaluation is based on vehicles' estimated travel times. Given the difficulty of precisely estimating long-term travel times in the real world, the method will be executed repeatedly throughout the whole horizon of interest. In each iteration, vehicles reroute based on precisely predicted travel times inside the local range (shown by the gray line in Figure 1) and approximations of travel times outside the local range. The decentralized incentive system in [21] follows a hierarchical architecture. Vehicles with the same local origin-destination (OD) pairs are grouped together (the temporary destinations within the defined local range in [21]). First, a route flow assignment model finds the optimal route flows for all vehicle groups in each iteration (with the same local OD pairs). Then, using these optimal flows and the value of time for each vehicle as inputs, a vehicle assignment model assigns vehicles to various routes within each vehicle group. Then, an envy-free procedure produces incentives for every vehicle in the group to ensure participation willingness and behavioral honesty. Notably, in [21], the participation willingness did not account for the potential disadvantages associated with individuals' privacy concerns about sharing sensitive data during the process. Similarly, whereas behavioral honesty implies that users' utilities are maximized when they reveal their real value of time, the utility functions did not account for the negative consequences of disclosing the value of time. Figure 1: Nudging re-routing behavior with incentives for a local system-optimal assignment (the solid lines and circles denote the road links and nodes within the local range; the dashed lines are the remaining routes from the local destinations to the destination; and dollar signs represent the incentives on the four local routes in the figure). For instance, there are four local routes for the group of vehicles in Figure 1. At the end of the current iteration, the vehicles will be provided with four option bundles (incentives calculated by the mechanism are bonded to the corresponding routes). Choosing a certain route determines the bonded amount of incentives. The incentives are designed such that all vehicles picking the bundles that optimize their individual utilities generate a local system-optimal assignment [21]. However, these benefits come with a price in terms of privacy. The vehicle route assignment and incentive calculation depend on vehicles sharing their values of time. And there seems to be no way to prevent incentive scams in which a vehicle claims to choose the option with the highest incentive but later travels on the route with the shortest travel time. Figure 2 depicts the conceptual structure of the privacy-preserving incentive mechanism for collaborative routing, which consists of a secure collaborative routing scheme at the origin (or local origin), and a route validation scheme at the checkpoints along the selected route. Both schemes employ on-chain and off-chain operations (depending on whether they need logging information on the blockchain for the record), ensuring that just the bare minimum amount of data are safely stored on the blockchain (against pattern-analysis attacks). The collaborative routing scheme leverages MPC to securely execute the protocols defined by the vehicle route assignment model and incentive model (steps 2 and 3 in the hierarchical framework) in [21]. Users will not receive the incentives corresponding to the routes they choose at the origin. Instead, the incentives will be temporarily frozen, which means they will be sent to a series of multi-signature wallets/accounts from the traffic operator's account.