To Optimize Human-in-the-loop Learning in Repeated Routing Games

We consider an infinite discrete time horizon $t\in\{0,1,\cdots\}$. In Figure 1(a), at the beginning of each $t$, there is a unit flow of users arriving at origin O. Then this unit flow of users individually choose paths from all the $N+1$ available paths to travel to their common destination D. We generally consider a deterministic path 0 with a fixed internal travel cost $c_{0}$ other than $N$ stochastic paths as in [17, 18, 28].

Following existing routing game literature (e.g., [30, 31, 24]), for any stochastic path $i\in\mathbb{N}=\{1,\cdots,N\}$, the internal travel cost $c_{i}(t)\in\{c_{L},c_{H}\}$ is random and dynamically alternates between a high-cost state $c_{H}$ and a low-cost state $c_{L}$ over time, according to the commonly used Markov chain in Figure 1(b).¹¹1Besides the references to support, we also validate the suitability of this Markov chain model in Section VI’s experiments. The internal cost may refer to factors like travel time or fuel consumption, which depend on the condition of each path (e.g., poor visibility, ‘black ice’ segments [28, 24]). Upon reaching destination D, users repeat the same process in the subsequent time slot $t+1$. The length of a time slot can represent a day, for instance, when people commute from home to the office each morning within a similar time range. Therefore, we generally assume that users are non-myopic, allowing them to retain their prior traffic observations to guide future routing decisions.

Given the unit flow of user arrivals at current $t$, we denote by $f_{i}(t)\in[0,1]$ the flow of users choosing any stochastic path $i$. Following the existing literature (e.g., [17, 30, 18]), in addition to the internal travel cost $c_{i}(t)$, each user on path $i$ will face another (external) congestion cost $f_{i}(t)$ caused by the other users on the same path. Therefore, the individual cost of each user traveling on stochastic path $i\in\mathbb{N}$ is $c_{i}(t)+f_{i}(t)$. Similarly, each of the other $f_{0}(t)$ flow of users on deterministic path 0 has individual cost $c_{0}+f_{0}(t)$, where

To learn the time-varying internal cost $c_{i}(t)$ of stochastic path $i\in\mathbb{N}$ for future use, the platform (e.g., Waze) expects users to frequently travel on diverse paths and share their observations. Then it observes user flow $f_{i}(t)$ and observation $c_{i}(t)$ via GPS and travel time [35].

The HILL model depends on the implemented mechanism, and we first consider the existing information-sharing mechanism used by Google Maps and Waze to share all useful traffic information with the public. After all users making routing decisions, a flow $f_{i}(t)$ of users travel on stochastic path $i$ to observe the actual state $c_{i}(t)$ there. We define a public hazard belief $x_{i}(t)\in[0,1]$ to be the expected probability for seeing the bad traffic or high-cost condition $c_{i}(t)=c_{H}$ at time $t$. Using the Bayesian inference, we obtain:

where $x_{i}(t-1)$ summarizes prior public hazard beliefs before $t-1$. Then we introduce the information learning process of this public HILL model below.

• •

  At the beginning of time $t$, the platform broadcasts the public hazard belief $x_{i}(t)$ of any stochastic path $i$ in (1) about traffic state $c_{i}(t)$.

• •

  During time slot $t$, users traveling on stochastic path $i$ will observe the actual state $c_{i}(t)$ and report it back to the platform. Then the platform will further update this prior belief to a posterior belief $x_{i}^{\prime}(t)$ below:

  • –

    If the $f_{i}(t)$ flow of users observe $c_{i}(t)=c_{H}$ on path $i$, then the posterior belief is updated to $x^{\prime}_{i}(t)=1$.

  • –

    If these users observe $c_{i}(t)=c_{L}$ on path $i$, then the posterior belief is updated to $x^{\prime}_{i}(t)=0$.

  • –

    If $f_{i}(t)=0$ without user to travel and learn this path $i$, the posterior belief $x^{\prime}_{i}(t)$ remains as $x_{i}(t)$.

• •

  At the end of each time slot, the platform updates public hazard belief from $x_{i}^{\prime}(t)$ to $x_{i}(t+1)$ below, based on the Markov chain in Fig. 1(b):

  $$x_{i}(t+1)=x_{i}^{\prime}(t)q_{HH}+\big{(}1-x_{i}^{\prime}(t)\big{)}q_{LH}.$$

  (2)

The above process will repeat as the new time slot $t+1$ begins. Note that the Markov chain-based HILL process described above is equivalent to the existing restless multi-armed bandit (MAB) problem (e.g., [36, 37]). Our subsequent analysis and key results (e.g, Proposition 1, Proposition 2, and our UPR mechanism) can also be generalized if $c_{i}(t)$ follows a memoryless stochastic process (e.g., Poisson process or exponential distribution), as the worst-case scenario remains unchanged.

If the platform chooses to hide this public information $x_{i}(t)$ from users (e.g., by applying the latest information hiding mechanism [17, 32, 24]), users have to independently update private beliefs based on their own routing choices and observations of any path $i$ in the past. In this subsection, we introduce how users update their differential private beliefs without public information sharing by the platform. To aid users’ routing decisions, we allow them to observe the traffic flow in the last time slot (i.e., $f_{i}(t-1)$ on any path $i$) at the beginning of each $t$, as widely assumed in existing transportation literature (e.g., [38, 39, 40]).

At the initial time $t=0$, the hazard belief $x_{i}(0)$ of any stochastic path $i$ is given to all users. Without knowing public belief $x_{i}(t)$ but only the past flow $f_{i}(t-1)$ since $t=1$, users will experience different information ages since their last observations of this path. Denote by $d_{i}(t)$ the information age of path $i$ for an individual user at time $t\geq 1$, and let $y_{i,d_{i}(t)}(t)$ denote its corresponding private hazard belief. Then, we proceed to introduce the update of $d_{i}(t)$ and $y_{i,d_{i}(t)}(t)$ under differential HILL in the following two cases.

• •

  If this user just explored stochastic path $i$ at $t-1$, its information age of this path is set to the minimum $d_{i}(t)=1$. Therefore, its current private hazard belief is exactly the same as the public belief of the platform:

  $\displaystyle y_{i,1}(t)=x_{i}(t).$

  (3)

• •

  If this user did not explore stochastic path $i$ at time $t-1$, its information age $d_{i}(t)$ should increase by $1$ from $d_{i}(t-1)$. As it is able to observe the last flow $f_{i}(t-1)$ at the beginning of $t$, it will rectify its private belief $y_{i,d_{i}(t-1)}(t-1)$. For example, if this user observes more users traveling on path $i$ with $f_{i}(t-1)\geq f_{i}(t-2)$ in the last time slot, it will believe that this path had a good traffic condition with weak hazard belief $x_{i}(t-1)=q_{LH}$ according to Fig. 1(b). Otherwise, it infers $x_{i}(t-1)=q_{HH}$ with strong hazard belief there. By rectifying the last private belief to the exact public belief $x_{i}(t-1)$ from the prior flow distribution, its information age keeps at $d_{i}(t)=2$ and does not grow over time. Thus, its private belief for time $t$ is updated to:

  	$\displaystyle y_{i,2}(t)$	$\displaystyle=\mathbb{E}[x_{i}(t)|x_{i}(t-1)]$
  		$\displaystyle=x_{i}(t-1)q_{HH}+(1-x_{i}(t-1))q_{LH},$		(4)

  due to (2) and $x_{i}^{\prime}(t-1)=x_{i}(t-1)$ without new observation.

According to the above analysis, we summarize the dynamics of a user’s information age $d_{i}(t)$ of path $i$ below:

with the self-learning update of private hazard belief $y_{i,1}(t)$ in (3) and $y_{i,2}(t)$ in (4), respectively.

In this subsection, we consider the information-sharing mechanism (used by Waze) to cater to users’ selfish interests such that users will not deviate from its recommendations.

We first summarize the dynamics of public hazard belief $x_{i}(t)$ for each stochastic path $i$ at any time $t$ in a vector below:

each of which can be obtained by (2). For the unit user flow at time $t$, the platform first shares the latest public hazard belief set $\mathbf{x}(t)$ with them. Then each non-myopic user will selfishly choose the path that minimizes its own long-run cost.

Let $Q^{(s)}\big{(}\mathbf{x}(t)|f_{i}^{(s)}(\mathbf{x}(t))\big{)}$ denote the minimal long-run expected cost of a single user since time $t$, given the $f_{i}^{(s)}(\mathbf{x}(t))\in[0,1]$ flow of non-myopic users choosing path $i$ under the sharing mechanism with symbol $(s)$ in the superscript. For ease of explanation, we take the special case of $N=1$ stochastic path alongside the deterministic path 0 in a typical two-path network example to solve and intuitively explain $f_{1}^{(s)}(x_{1}(t))$ below. For an arbitrary number $N\geq 2$, we can similarly compute $f_{i}^{(s)}(\mathbf{x}(t))$ by balancing the expected costs of all the $N+1$ paths as in (7).

The proof of Lemma 1 is given in Appendix A of the supplemental material. From the first case of (7), even if the stochastic path 1’s internal travel cost $\mathbb{E}[c_{1}(t)|x_{1}(t)]$ is larger than path 0’s internal cost $c_{0}$ plus the maximum congestion $1$ there, non-myopic users may still choose path 1 with minimum flow $\epsilon$ to learn possible $c_{L}$ state for future use given $Q^{(s)}(x_{1}(t)|\epsilon)\leq Q^{(s)}(x_{1}(t)|0)$. If the internal cost of path 0 is larger than the internal cost of path 1 plus the maximum congestion, all user flow will choose path 1 in the first case of (7). Otherwise, the two paths’ conditions are comparable and the user flow will partition to both paths to balance congestion there.

In the last two cases of (7), as there is always a positive $f_{1}^{(s)}(x_{1}(t))>0$ flow of users traveling on path 1 to learn fresh information $c_{1}(t)$ there, non-myopic users will myopically make routing decisions to minimize their immediate individual costs in the current time slot.

Then we further analyze the long-term social cost under the sharing mechanism (with specific (7) for $N=1$ case). Define $C^{(s)}(\mathbf{x}(t))$ and $c^{(s)}(\mathbf{x}(t))$ to be the long-term and immediate social cost functions. At each time slot $t$, the immediate social cost is obtained as:

which includes the current travel cost of $f_{0}^{(s)}(\mathbf{x}(t))$ flow of users on deterministic path 0 and $f_{i}^{(s)}(\mathbf{x}(t))$ flow of users on any stochastic path $i\in\mathbb{N}$.

After obtaining immediate social cost (8), we further formulate the long-term cost function $C^{(s)}(\mathbf{x}(t))$ as a Markov decision process (MDP), where the update of hazard belief $x_{i}(t+1)$ depends on current users’ routing choices and observations of $c_{i}(t)$ on path $i$’s. Consequently, two cases arise for updating $x_{i}(t+1)$ at each time slot. If $f_{i}^{(s)}(\mathbf{x}(t))=0$ without user traveling on stochastic path $i$, $x_{i}^{\prime}(t)$ remains as $x_{i}(t)$ and will be updated to $x_{i}(t+1)$ according to (2). If $f_{i}^{(s)}(\mathbf{x}(t))>0$ with users traveling on path $i$, then $x_{i}(t+1)$ will be updated to $q_{HH}$ or $q_{LL}$, depending on whether users’ observation there is $c_{i}(t)=c_{H}$ or $c_{i}(t)=c_{L}$ in Fig. 1(b).

Based on the analysis above, we formulate the long-term $\rho$-discounted cost function under information sharing below:

where $c^{(s)}(\mathbf{x}(t))$ is given in (8) and $\rho\in(0,1)$ is the discount factor. Selfish users will not choose any stochastic path $i$ with higher long-run cost, and thus $x_{i}(t)$ of this path may not be updated on time to be useful for the next time slot.

In this subsection, we formulate the long-term cost function under the latest hiding mechanism in the routing game literature (e.g., [17, 32, 24]). Note that their mechanisms cannot be directly applied to our repeated routing as users are non-myopic and no longer hold the same private belief. Thus we need to revise it to fit our differential HILL model as described in Section II-C. Note that the hiding mechanism still caters to users’ selfish interests to hide all information including $\alpha(t)$ and lets users themselves choose routing paths that minimize their own long-run costs under Definition 1.

Recall in (5) that users under the hiding mechanism are different in their private information ages $d_{i}(t)=1$ or $2$ from their own last observations, resulting in differential private belief $y_{i,1}(t)$ in (3) or $y_{i,2}(t)$ in (4) about path $i$, respectively. We summarize the dynamics of users’ private beliefs $y_{i,1}(t)$ and $y_{i,2}(t)$ among $N$ stochastic paths at time $t$ as:

Let $f_{i}^{\emptyset}(\mathbf{y}(t))\in[0,1]$ denote the flow of non-myopic users choosing path $i$ at time $t$ under the hiding mechanism with subscript $\emptyset$, which needs to specify users’ path decisions under different information age $d_{i}(t)$’s. Denote by $f_{i,d_{i}(t)}^{\emptyset}(y_{i,d_{i}(t)}(t))$ the flow of users choosing path $i$ with the same information age $d_{i}(t)$, which satisfies

Given $f_{i}^{\emptyset}(\mathbf{y}(t-1))$ flow of users exploring path $i$ in the last time, the current flow of users with $d_{i}(t)=1$ is thus $f_{i}^{\emptyset}(\mathbf{y}(t-1))$. As they have the latest information on this path with $d_{i}(t)=1$, they will infer other users’ private belief $y_{i,2}(t)$ with $d_{i}(t)=2$ according to (4). Thus, they can estimate the exact flow $f_{i,2}^{\emptyset}(y_{i,2}(t))$ of these users on path $i$, and then decide $f^{\emptyset}_{i,1}(y_{i,1}(t))$ to minimize their own long-run costs.

While for the other $1-f_{i}^{\emptyset}(\mathbf{y}(t-1))$ flow of users with $d_{i}(t)=2$, they only hold delayed or aged belief $y_{i,2}(t)$ to decide $f^{\emptyset}_{i,2}(y_{i,2}(t))$ to minimize their expected long-run costs.

To clearly tell non-myopic users’ decision-making under the differential HILL model, we derive in the next lemma the closed-form expressions for how users decide $f_{1,1}^{\emptyset}(y_{1,1}(t))$ and $f_{1,2}^{\emptyset}(y_{1,2}(t))$ in the basic two-path network at the equilibrium as an example.

The proof of Lemma 2 is given in Appendix B of the supplemental material. As compared to $f_{1}^{(s)}(x_{1}(t))$ under information sharing in (7), users with $d_{i}(t)=2$ under information hiding have to use their private belief $y_{1,2}(t)$ to decide $f_{1,2}^{\emptyset}(y_{1,2}(t))$ in (13). Then users with $d_{i}(t)=1$ decide $f_{1,2}^{\emptyset}(y_{1,2}(t))$ in (12) to make the total flow on path $1$ approach to $f_{1}^{(s)}(y_{1,1}(t))$ under information sharing as much as possible.

Next, we similarly formulate the long-term $\rho$-discounted cost function under the hiding mechanism below:

where the immediate social cost $c^{\emptyset}(\mathbf{y}(t))$ is similarly defined as (8) and the update of $\mathbf{y}(t+1)$ is given in (3) or (4), depending on the system belief sets $\mathbf{x}(t-1)$ and $\mathbf{x}(t)$.

Recall that the sharing and hiding mechanisms that cater to users’ selfish interests for persuading them to follow path recommendations in Lemmas 1 and 2. Differently, the socially optimal policy aims to centrally solve the optimal routing flow $f^{*}_{i}(t)\in[0,\alpha(t)]$ to minimize the long-run expected social cost for all users, by assuming users to be cooperative all the time. Let $C^{*}(\mathbf{x}(t))$ denote the long-term $\rho$-discounted cost function under the socially optimal policy, given as:

where $c^{*}(\mathbf{x}(t))$ is similarly defined as (8). If the platform asks all the unit flow of arriving users to choose path 0, there would be no observation on stochastic path $i$. As a result, the posterior belief $x_{i}^{\prime}(t)$ remains as $x_{i}(t)$. However, if the platform instructs some users to travel on path $i$, $x_{i}^{\prime}(t)$ can be timely updated to $0$ or $1$ and will be further updated to $x_{i}(t+1)$ by (2).

In (15), even if the expected travel cost $\mathbb{E}[c_{i}(t)|x_{i}(t)]$ on path $i$ is much higher than others, the socially optimal policy may still recommend a small flow $\epsilon>0$ of users to learn $x_{i}(t)$ on path $i$. As $\epsilon\rightarrow 0$, this infinitesimal flow of users’ immediate total cost $\epsilon(\mathbb{E}[c_{i}(t)|x_{i}(t)]+\epsilon)$ is negligible. At the same time, their learned information on path $i$ can help reduce future costs for all users. Therefore, the socially optimal policy always decides $f_{i}^{*}(t)\geq\epsilon$ for any stochastic path $i$.

Next, we derive the optimal recommended flow $f_{1}^{*}(x_{1}(t))$ in the typical two-path network example.

The proof of Lemma 3 is given in Appendix C of the supplemental material. By comparing (16) to (7) under the sharing mechanism, we observe that the socially optimal policy always explores stochastic path 1 with $f_{1}^{*}(x_{1}(t))\geq\epsilon$, even if $\mathbb{E}[c_{1}(t)|x_{1}(t)]$ is much larger than $c_{0}$. If $\mathbb{E}[c_{1}(t)|x_{1}(t)]<c_{0}$, $f_{1}^{*}(x_{1}(t))=\frac{1}{2}+\frac{c_{0}-\mathbb{E}[c_{1}(t)|x_{1}(t)]}{4}$ in (16) is smaller than $f_{1}^{(s)}(x_{1}(t))=\frac{1}{2}+\frac{c_{0}-\mathbb{E}[c_{1}(t)|x_{1}(t)]}{2}$ in (7) to reduce the overall congestion on this stochastic path.

By comparing (16) to (12)-(13) under the hiding mechanism, the socially optimal policy adaptively uses actual $x_{1}(t)$ to guide users’ routing in different cases. However, the hiding mechanism uses $y_{1,1}(t)$ and $y_{1,2}(t)$ for partially blind routing decisions, which can be very different from the optimum. Based on (7), (12)-(13) and (16) of the three mechanisms/policies, we are ready to compare their system performances in Section IV to inspire our mechanism design.

We compare $f_{i}^{(s)}(\mathbf{x}(t))$ under the sharing mechanism in Section III-A to the optimal recommended flow $f_{i}^{*}(\mathbf{x}(t))$ under the social optimum in Section III-C to examine the sharing mechanism’s efficiency loss. For example, by comparing $f_{1}^{(s)}(\mathbf{x}(t))$ in (7) and $f_{1}^{*}(\mathbf{x}(t))$ in (16) for the two-path network example, we find that the sharing mechanism misses both exploitation and exploration on stochastic path 1, as compared to the social optimum. Below, we examine their performance gap for an arbitrary number $N$ of stochastic paths.

We use the standard definition of the price of anarchy (PoA) in game theory [41], for measuring the maximum ratio between the long-term social cost under the sharing mechanism in (9) and the minimal social cost in (15):

which is always larger than $1$ by considering all system parameters.

Through involved worst-case analysis, we prove the lower bound of $\text{PoA}^{(s)}$ in (17) caused by the sharing mechanism’s lack of exploration in the following proposition.

The proof of Proposition 1 is given in Appendix E of the supplemental material. In Proposition 1’s proof, we consider the worst case of minimum exploration under the sharing mechanism. Given $\mathbb{E}[c_{i}(0)|x_{i}(0)]$ up to $c_{0}+1$ on path $i$, there will be an $\epsilon$ flow of users traveling on stochastic path $i$ at time $t=0$. Once they find $c_{i}(t)=c_{H}$ there at any $t\geq 1$, no user will explore this path again, as $q_{HH}\rightarrow 1$. However, socially optimal policy (16) always recommends $\epsilon$ flow of users to explore any path $i$ to learn possible $c_{i}(t)=c_{L}$ there. As $\frac{1-q_{LL}}{1-q_{HH}}\rightarrow 0$, it takes them at most $\frac{\lceil\log_{q_{HH}}\delta\rceil}{N}$ time slots to find at least one path with $c_{L}=0$. After that, all users’ long-term costs will be significantly reduced due to $q_{LL}\rightarrow 1$. Then we compare the two long-term costs to derive the PoA lower bound in (18).

In (18), the PoA lower bound decreases with path number $N$, as more stochastic paths help risk pooling and make it easier for users to find $c_{i}(t)=c_{L}$ to approach the optimum. As $N\rightarrow\infty$ with infinite stochastic paths, $\text{PoA}^{(s)}$ in (18) approaches the optimum $1$.

In this subsection, we further analyze the PoA lower bound caused by the hiding mechanism. Let $\text{PoA}^{\emptyset}$ denote the PoA caused by the hiding mechanism, which is similarly defined as (17) to compare the social cost $C^{\emptyset}(\mathbf{y}(t))$ in (14) with $C^{*}(\mathbf{x}(t))$ in (15). In the next proposition, we successfully provide the worst-case analysis to prove $\text{PoA}^{\emptyset}$’s lower bound.

The proof of Proposition 2 is given in Appendix F of the supplemental material. This PoA bound (19) can be similarly proved by considering the minimum exploration case as in Proposition 1. However, different from the sharing mechanism that always knows the latest system information, users with information delay $d_{i}(t)=2$ under the hiding mechanism have a time slot’s latency to decide exploration or exploitation, which makes $\text{PoA}^{\emptyset}$ in (19) different from $\text{PoA}^{(s)}$ in (18)

In (19), the lower bound of $\text{PoA}^{\emptyset}$ also decreases with path number $N$. As $N\rightarrow\infty$ with infinite paths, $\text{PoA}^{\emptyset}$ approaches $1+\rho$, due to users’ late exploitations of stochastic paths to increase the total cost under information delay $d_{i}(t)=2$.

Given neither the sharing mechanism nor the hiding mechanism performs well for non-myopic users with finite $N$ in practice, it is critical to design a new mechanism other than simply sharing or hiding information.