Human-in-the-loop Learning for Dynamic Congestion Games
Hongbo Li Lingjie Duan







IEEE Transactions on Mobile Computing
Shell et al.: A Sample Article Using IEEEtran.cls for IEEE Journals

0000–0000/00$00.00  2021 IEEE



Human-in-the-loop Learning for Dynamic Congestion Games
    Hongbo Li, Student Member, IEEE and Lingjie Duan, Senior Member, IEEE
        
This work was supported in part by the Ministry of Education, Singapore, under its Academic Research Fund Tier 2 Grant with Award no. MOE-T2EP20121-0001; in part by SUTD Kickstarter Initiative (SKI) Grant with no. SKI 2021_04_07; and in part by the Joint SMU-SUTD Grant with no. 22-LKCSB-SMU-053. Part of this work was published in IEEE ISIT 2024 Conference <cit.>.

Hongbo Li and Lingjie Duan are with the Pillar of Engineering Systems and Design, Singapore University of Technology and Design, Singapore 487372 (e-mail: hongbo_li@mymail.sutd.edu.sg; lingjie_duan@sutd.edu.sg).


    April 29, 2024
=======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




Today mobile users learn and share their traffic observations via crowdsourcing platforms (e.g., Google Maps and Waze). Yet such platforms simply cater to selfish users' myopic interests to recommend the shortest path, and do not encourage enough users to travel and learn other paths for future others. Prior studies focus on one-shot congestion games without considering users' information learning, while our work studies how users learn and alter traffic conditions on stochastic paths in a human-in-the-loop manner. In a typical parallel routing network with one deterministic path and multiple stochastic paths, our analysis shows that the myopic routing policy (used by Google Maps and Waze) leads to severe under-exploration of stochastic paths. This results in a price of anarchy (PoA) greater than 2, as compared to the socially optimal policy achieved through optimal exploration-exploitation tradeoff in minimizing the long-term social cost. Besides, the myopic policy fails to ensure the correct learning convergence about users' traffic hazard beliefs. To address this, we focus on informational (non-monetary) mechanisms as they are easier to implement than pricing. We first show that existing information-hiding mechanisms and deterministic path-recommendation mechanisms in Bayesian persuasion literature do not work with even PoA=∞. Accordingly, we propose a new combined hiding and probabilistic recommendation (CHAR) mechanism to hide all information from a selected user group and provide state-dependent probabilistic recommendations to the other user group. Our CHAR mechanism successfully ensures PoA less than 5/4, which cannot be further reduced by any other informational (non-monetary) mechanism. Besides the parallel network, we further extend our analysis and CHAR mechanism to more general linear path graphs with multiple intermediate nodes, and we prove that the PoA results remain unchanged. Additionally, we carry out experiments with real-world datasets to further extend our routing graphs and verify the close-to-optimal performance of our CHAR mechanism.



human-in-the-loop learning, dynamic congestion games, price of anarchy, mechanism design




§ INTRODUCTION


In today's traffic networks, a random number of users arrive sequentially to decide their routing paths (e.g., the shortest path) based on real-time traffic conditions <cit.>. To assist new user arrivals in their decision-making process, emerging crowdsourcing applications (e.g., Google Maps and Waze) serve as important platforms to leverage users for information learning and sharing (<cit.>). These platforms aggregate the latest traffic information of stochastic paths from previous users who have recently traveled there and reported their observations, then share this information with new users. However, these platforms always myopically recommend the currently shortest path, and do not encourage enough selfish users to travel and learn other longer paths of varying traffic conditions for future others. 
Prior congestion game literature assumes a static scenario of one-shot routing by a group of users, without considering their long-term information learning in a long-term dynamic scenario (e.g., <cit.>).

To efficiently learn and share the time-varying information, multi-armed bandit (MAB) problems are developed to study the optimal exploration-exploitation among stochastic arms/paths (e.g., <cit.>). For example, <cit.> utilizes MAB techniques to predict congestion in a fast-varying transportation environment. <cit.> applies the MAB exploration-exploitation strategy to balance the recruitment of previously well-behaved users or new uncertain users for completing crowdsourcing tasks. Recently, some studies have extended traditional MAB problems to distributed scenarios with multiple user arrivals at the same time (e.g., <cit.>). For instance, <cit.> study how users make their own optimal decisions at each time slot based on the private arm information that they learned beforehand. <cit.> explores cooperative information exchange among all users to facilitate local model learning.
Subsequently, both <cit.> and <cit.> examine the performance under partially connected communication graphs, where users communicate only with their neighbors to make locally optimal decisions. In general, these MAB solutions assume users' cooperation to align with the social planner, without possible selfish deviations to improve their own benefits.



As selfish users may not listen to the social planner, some recent congestion game works focus on Bayesian persuasion and information design to incentivize users' exploration of different paths <cit.>. For example, <cit.> assumes that the social planner has the complete system information and properly discloses system information to regulate users and control efficiency loss. Without perfect feedback, <cit.> estimates users' expected utilities of traveling each path based on all possible cases to improve the robustness of Bayesian persuasion. Similarly, <cit.> allows the system to learn stochastic travel latency based on users' travel data while only regulating the immediate congestion in the current time slot. In summary, all these works assume that users' routing decisions do not internally alter the long-term traffic congestion condition for future users, and only focus on exogenous information to learn dynamically.  


It is practical to consider endogenous information variation in dynamic congestion games, where more users choosing the same path not only improve learning accuracy there (<cit.>), but also produce more congestion for followers (<cit.>). For this new problem, we need to overcome two technical issues. The first is how to dynamically allocate users to reach the best trade-off between learning accuracy and resultant congestion costs of stochastic paths. To minimize the long-run social travel cost, it is critical to dynamically balance multiple user arrivals' positive information learning effect and negative congestion effect to avoid both under- and over-exploration of stochastic paths. 



Even provided with the socially optimal policy, we still need to ensure selfish users follow it. Thus, the second issue is how to design an informational mechanism to properly regulate users' myopic routing. In practice, informational mechanisms (e.g., Bayesian persuasion <cit.>) are non-monetary and easier to implement compared to pricing or side-payment mechanisms (e.g., <cit.>). There are two commonly used informational mechanisms to optimize long-run information learning in congestion games: information hiding mechanism <cit.> and deterministic path-recommendation <cit.>. For example, <cit.> analyzes how users infer the expected travel cost of each path to decide routing if the system hides all traffic information. <cit.> assumes a publicly known process for varying each path's traffic condition, and selectively provides deterministic path recommendations to regulate users' myopic routing. We will show later that both mechanisms do not work in improving our system performance, inspiring our new mechanism design. 


Our main contributions and the key novelty of this paper are summarized as follows. 

    
  * Human-in-the-loop learning for dynamic congestion games: Prior studies focus on one-shot congestion games without information learning, while we study how users learn and alter traffic conditions on stochastic paths in a human-in-the-loop manner. When such congestion games meet human-in-the-loop learning, more users' routing on stochastic paths generates both positive learning benefits and negative congestion effects there for followers. We use users’ positive learning effect to negate negative congestion, which fundamentally extends traditional one-shot congestion games (e.g., <cit.> and <cit.>).
    
  * Policies comparison via PoA analysis: 
    To minimize the social cost, we formulate the optimization problems for both myopic and socially optimal policies as Markov decision processes (MDP). Our analysis shows that the myopic routing policy (used by Google Maps and Waze) leads to severe under-exploration of stochastic paths. This results in a price of anarchy (PoA) greater than 2, as compared to the socially optimal policy achieved through optimal exploration-exploitation tradeoff in minimizing the long-term social cost. 
    
  * Learning convergence and new mechanism design: We first prove that the socially optimal policy ensures correct convergence of users’ traffic hazard beliefs on stochastic paths, while the myopic policy cannot. Then we show that existing information-hiding and deterministic-recommendation mechanisms in Bayesian persuasion literature make PoA=∞. Accordingly, we propose a combined hiding and probabilistic recommendation (CHAR) mechanism to hide all information from a selected user group and provide state-dependent probabilistic recommendations to the other user group. Our CHAR mechanism successfully ensures PoA less than 5/4, which cannot be further reduced by any other informational mechanism.
    
  * Extensions to linear path graph: Besides the basic parallel transportation network between two nodes, we further extend our analysis and CHAR mechanism to encompass any linear path graph with multiple intermediate nodes. In this extended model, myopic users also consider their future travel costs when making current routing decisions, which adds complexity to their decision analysis. Nonetheless, we successfully prove that the PoA caused by users' myopic routing policy remains greater than 2, and our CHAR mechanism continues to effectively reduce PoA to less than 5/4. Finally, we conduct experiments using real-world datasets to show the close-to-optimal average-case performance of our CHAR mechanism.


The rest of the paper is organized as follows. In Section <ref>, we formulate the dynamic congestion model and the human-in-the-loop learning model for the system. Then we formulate the optimization problems for both myopic policy and socially optimal policy in Section <ref>. After that, in Section <ref> we analytically compare the two policies via PoA analysis. Based on the analysis, we propose our CHAR mechanism in Section <ref>. Subsequently, we extend the system model and analysis to a general linear path graph in Section <ref> and verify the performance of our CHAR mechanism in Section <ref>. Finally, Section <ref> concludes the paper. For ease of reading, we summarize all the key notations in Table <ref>.



§ SYSTEM MODEL





In this section, we first introduce the dynamic congestion model for a typical parallel multi-path network between two nodes O and D as in existing congestion game literature (e.g., <cit.> and <cit.>). Then we introduce the human-in-the-loop learning model for the crowdsourcing platform. Note that we have extended our congestion model and key results to any general linear path graphs later in Section <ref>.
As shown in Fig. <ref>, we consider an infinite discrete time horizon t∈{0,1,⋯} to model the dynamic congestion game. Within each time slot t, a stochastic number N(t)∈ [N_min,N_max] of atomic users, where 𝔼[N(t)]=N, arrive at origin O to decide their paths among M+1 paths to travel to destination D.








 §.§ Dynamic Congestion Model


Following the traditional routing game literature (<cit.>), we model a safe path 0 with a fixed travel latency, which is denoted by ℓ_0. While the other paths are stochastic with time-varying travel latencies, denoted by ℓ_i(t) at time t∈{1,2,⋯}, where i∈ℳ:={1,⋯,M}. 
According to prior research on travel delay estimation (e.g., <cit.>), the next ℓ_i(t+1) at t+1 is correlated with both current ℓ_i(t) and the number of atomic users traveling this path, which is denoted by n_i(t). For example, more users traveling on the same path results in slower driving speeds and longer queueing times at traffic lights, thereby increasing the latency for later users. Define this general correlation function as:

    ℓ_i(t+1)=f(ℓ_i(t),n_i(t),α_i(t)),

where α_i(t) is the correlation coefficient, measuring the leftover flow to be served over time. Note that f(·) is defined as a general increasing function in ℓ_i(t),n_i(t) and α_i(t).

As in existing congestion game literature (<cit.>), we model α_i(t) to follow a memoryless stochastic process (not necessarily a time-invariant Markov chain) to alter as below:

    α_i(t)=α_H,if high hazard (bad) condition on path i at t,
    α_L,if low hazard (good) condition on path i at t,

where α_H∈[1,+∞) and α_L∈[0,1).
Unlike these works assuming that the social planner knows the probability distribution of α_i(t) beforehand, we relax this assumption to keep it unknown in our work. For ease of exposition, we only consider two states here, while our later analysis and mechanism design can be extended to accommodate multiple states of α_i(t).

We denote the expected steady state of correlation coefficient α_i(t) in the long run by

    𝔼[α_i(t)|x]=x·α_H+(1-x)·α_L,

where x is the long-run expected probability of α_i(t)=α_H yet the exact value of x is unknown to users. They can only know x to satisfy a distribution ℙ(x). Here we assume ℙ(x) is not extreme, such that users may consider traveling on any stochastic path i under x∼ℙ(x). To accurately estimate 𝔼[α_i(t)|x], the system expects users to learn the real steady state x by observing real-time traffic conditions.




 §.§ Human-in-the-loop Learning Model

When traveling on stochastic path i, users cannot observe α_i(t) directly but a traffic hazard event (e.g., ‘black ice’ segments or jamming). At the same time, <cit.> shows that each user has a noisy observation of the hazard. Hence, our system uses a majority vote to fuse all their observation reports of stochastic path i into a hazard summary y_i(t)∈{0,1,∅} during time t. Specifically,

    
  * y_i(t) = 1 tells that most of the current n_i(t) users observe a traffic hazard on stochastic path i at time t.
    
  * y_i(t)=0 tells that most of the current n_i(t) users observe no traffic hazard on stochastic path i at time t.
    
  * y_i(t)=∅ tells that there is no user traveling on path i (i.e., n_i(t)=0), without any new observation. 


However, the fused summary y_i(t) by n_i(t) users can still be inaccurate. Given n_i(t), we define the group probabilities under α_i(t)_H and α_i(t)=α_L for observing a hazard below:

    q_H(n_i(t))   =𝐏𝐫(y_i(t)=1|α_i(t)=α_H, n_i(t)),
    
        q_L(n_i(t))   =𝐏𝐫(y_i(t)=1|α_i(t)=α_L, n_i(t)).

According to <cit.>, q_H(n_i(t))∈[0,1] increases with n_i(t), because more users help spot hazard α_i(t)=α_H. Similarly, q_L(n_i(t))∈[0,1] decreases with n_i(t) under α_i(t)=α_L.

We summarize the current routing decisions and observations of all paths as vectors 𝐧(t)={n_i(t)|i∈{0,⋯, M}} and 𝐲(t)={y_i(t)|i∈ℳ}, respectively. To guide trip advisory at time t, the crowdsourcing platform needs to memorize all the historical data of (𝐧(1),⋯,𝐧(t-1)) and (𝐲(1),⋯,𝐲(t-1)), which keep growing over time. Following the memoryless property <cit.>, we use Bayesian inference to equivalently summarize these data into a prior hazard belief x_i(t)∈[0,1] for any stochastic path i:

    x_i(t)=𝐏𝐫(α_i(t)=α_H|x_i(t-1),y_i(t-1),n_i(t-1)),

which indicates the probability of α_i(t)=α_H at time t.

Next, we explain how our human-in-the-loop learning model works in the time horizon.


    
  * At the beginning of time t, the crowdsourcing platform publishes latest latency 𝔼[ℓ_i(t)|x_i(t-1),y_i(t-1)] and prior hazard belief x_i(t) in (<ref>) on any stochastic path i. 
    
  * During time t, N(t) users arrive to decide n_i(t) on each stochastic path i and travel there to return their observation summary y_i(t). Based on y_i(t), the platform next updates prior belief x_i(t) to a posterior belief x_i'(t)=𝐏𝐫(α_i(t)=α_H|x_i(t),y_i(t),n_i(t)). For example, if y_i(t)=1, we have
    
    x_i'(t)   =Pr(α_i(t)=α_H|x_i(t),n_i(t),y_i(t)=1)
       =[0.94]Pr(y_i(t)=1|α_i(t)=α_H)Pr(α_i(t)=α_H)/[0.94]∑_j∈{α_H,α_L}Pr(y_i(t)=1|α_i(t)=j)Pr(α_i(t)=j)
       =x_i(t)q_H(n_i(t))/x_i(t)q_H(n_i(t))+(1-x_i(t))q_L(n_i(t))

    where the second equation is due to Bayes' Theorem and Law of total probability.
    Similarly, if y_i(t)=0, we obtain
    
    x'(t)=[0.95] x(t)(1-q_H(n(t)))/[0.95] x(t)(1-q_H(n(t)))+(1-x(t))(1-q_L(n(t))).

    Note that we keep x'(t)=x(t) if y_i(t)=∅, as there is no observation to update x'(t).
    
  * At the end of time t, the platform updates the expected correlation coefficient given posterior belief x'_i(t):
    
    𝔼[α_i(t)|x_i'(t)]=x_i'(t)α_H+(1-x_i'(t))α_L.

    Combing (<ref>) with (<ref>), we obtain expected travel latency
    
    [0.96]𝔼[ℓ_i(t+1)|x_i'(t)]=𝔼[f(𝔼[ℓ_i(t)|x'_i(t-1)],n_i(t),α_i(t))]

     on stochastic path i for next time slot t+1.

    Finally, the platform updates x_i(t+1)=x_i'(t) and repeats  above process in t + 1.




§ PROBLEM FORMULATIONS FOR MYOPIC AND SOCIALLY OPTIMAL POLICIES


Based on the dynamic congestion and human-in-the-loop learning models in Section <ref>, we next formulate the optimization problems for both myopic and socially optimal policies. The myopic policy is widely used in existing crowdsourcing platforms (e.g., Google Maps and Waze), defined as follows.

Under the myopic policy, the platform recommends a path to each user to minimize their current travel cost.





 §.§ Problem Formulation for the Myopic Policy

In this subsection, we focus on the myopic policy used by Google Maps and Waze, which post all the collected useful information to the public. First, we summarize all stochastic paths' expected latencies and hazard beliefs into vectors

    𝐋(t)   ={𝔼[ℓ_i(t)|x_i'(t-1)]|i∈ℳ},
    𝐱(t)   ={x_i(t)|i∈ℳ},

respectively. Let n_i^(m)(t)∈{0,⋯, N(t)} define the (exploration) number of users traveling on any path i∈{0,⋯,M} allocated by the myopic policy from N(t) users, where the superscript (m) means the myopic policy. We use 𝐧^(m)(t) to summarize all the n_i^(m)(t) under the myopic policy.

Following the typical travel cost model as in congestion game literature <cit.>, for each of the n_0(t) users on safe path 0, his expected travel cost consists of travel latency ℓ_0 and congestion cost n_0(t) caused by other users on this path:

    c_0(n_0(t))=ℓ_0+n_0(t).


For each user on stochastic path i∈ℳ, besides the expected travel latency 𝔼[ℓ_i(t)|x_i'(t-1)] caused by past users and the immediate congestion cost n_i(t) in traditional congestion games without learning (<cit.>), he also faces an extra variance cost V(n_i(t-1)) due to former n_i(t-1) users' imperfect observation summary y_i(t-1) (<cit.>). V(n_i(t-1)) tells how much the gap (between the n_i(t-1) reports fused result and the reality) adds to the total cost by misleading decision making of future users. Then his travel cost on stochastic path i is:

    c_i(n_i(t))=𝔼[ℓ_i(t)|x_i'(t-1)]+n_i(t)+V(n_i(t-1)),

where V(n_i(t-1)) is a general decreasing function of n_i(t-1), as more users improve the learning accuracy on stochastic path i.

Based on each user's individual cost (<ref>) of safe path 0 and (<ref>) of stochastic path i, we next analyze myopic policy n_i^(m)(t). For ease of exposition, we first consider M=1 in a basic two-path network to solve and explain n_1^(m)(t) below. 

Under the myopic policy, given expected travel latency 𝔼[ℓ_1(t)|x_1'(t-1)] and hazard belief x_1(t) of stochastic path 1, the exploration number is:

    n^(m)_1(t)=0,             if c_1(0)≥ c_0(N(t)),
    N(t),         if c_1(N(t))≤ c_0(0),
    N(t)/2+c_0(0)- c_1(0)/2,   otherwise.



The proof of Lemma 1 is given in Appendix A of the supplement material.
If the minimum expected travel cost of stochastic path 1 is larger than the maximum cost of path 0, all the N(t) users will choose path 0 with n_1^(m)(t)=0 in the first case of (<ref>). Otherwise, in the last two cases of (<ref>), there is always a positive n_1^(m)(t)≥ 1 number of users traveling on stochastic path 1 to learn and update x_1(t+1) and 𝔼[ℓ_1(t+1)|x_1'(t)] there. 
When there are M ≥ 2 stochastic paths, N(t) user arrivals myopically decide on the exploration number n_i(t) for each path i, as described in (<ref>), in an attempt to balance the expected cost c_i(n_i^(m)(t))=c_j(n^(m)_j(t)) for any path j ≠ i at the equilibrium. Under the constraint ∑_i=0^Mn_i^(m)(t)=N(t), this system of M+1 linear equations in M+1 unknowns can be solved by Gaussian elimination.


Based on the above analysis, we further examine the long-run social cost of all users since the current time t. For current N(t) user arrivals, their immediate social cost under the myopic policy is 

    c(𝐧^(m)(t))=∑_i=0^Mn_i^(m)(t)c_i(n_i^(m)(t))

with individual cost c_i(·) in (<ref>) or (<ref>).
Define the long-term ρ-discounted social cost function under the myopic policy to be C^(m)(𝐋(t),𝐱(t),N(t)). Based on (<ref>), we leverage the Markov decision process (MDP) to formulate:

    C^(m)(𝐋(t),𝐱(t),N(t))=
       c(𝐧^(m)(t))+ρ𝔼[C^(m)(𝐋(t+1),𝐱(t+1),N(t+1))],

where the update of each travel latency 𝔼[ℓ_i(t+1)|x_i'(t)] and hazard belief x_i(t+1) are given in (<ref>) and (<ref>), depending on current N(t) users' routing decision n_i^(m)(t) and the possible observation summary y_i(t)∈{0,1,∅} on path i. Here the discount factor ρ∈(0,1) is widely used to discount future travel costs to its present cost <cit.>.



 §.§ Problem Formulation for Socially Optimal Policy

Different from the myopic policy, the socially optimal policy minimizes the long-term social travel cost for all users.
Define n_i^*(t)∈{0,1,⋯,N(t)} to be the optimal exploration number, and let vector 𝐧^*(t) summarize all the n_i^*(t). Different from the myopic policy that only minimizes each user's travel cost, the social optimum aims to well control the overall congestion cost and information learning to minimize the long-run expected social cost. 


Define the long-run expected social cost function under the socially optimal policy to be C^*(𝐋(t),𝐱(t),N(t)).
Under the socially optimal policy, the update of 𝐋(t) and 𝐱(t) also depend on the optimal exploration number set 𝐧^*(t). For any stochastic path i,

    
  * If n_i^*(t)=0, i.e., the platform asks no user to choose this stochastic path i, then y_i(t)=∅ and the next hazard belief x_i(t+1)=x_i(t) keeps unchanged. 
    
  * Otherwise, x_i(t+1) is updated based on y_i(t)=1 or 0. 

After that, the expected travel latency 𝔼[ℓ_i(t+1)|x_i'(t)] of each stochastic path i is updated according to (<ref>).

Based on the above analysis, we formulate the long-term objective function under the socially optimal policy as:

    C^*(𝐋(t),𝐱(t),N(t))=
       min_𝐧^*(t) c(𝐧^*(t))+ρ𝔼[C^*(𝐋(t+1),𝐱(t+1),N(t+1))],

where the immediate social cost c(𝐧^*(t)) is similarly defined as in (<ref>).
Note that (<ref>) is non-convex and incurs the curse of dimensionality under the infinite time horizon <cit.>. 

To derive an approximated solution 𝐧^*(t), we combine successive approximation <cit.> and exhaustive search <cit.> to formulate the following iterative algorithm, which iterates over Q steps. In each step q∈{1,⋯,Q}, we update the current solution 𝐧_q(t) by solving the problem C_q(𝐋(t),𝐱(t),N(t)). 

Initially, we define

    C_0(𝐋(t),𝐱(t),N(t))=min_𝐧_0(t) c(𝐧_0(t)),

which is a linear optimization problem and can be solved by the ellipsoid method <cit.>.
Then for any step q≥ 1, let

    C_q(𝐋(t),𝐱(t),N(t))=
       min_𝐧_q(t) c(𝐧_q(t))+ρ𝔼[C_q-1(𝐋(t+1),𝐱(t+1),N(t+1))],

which can be solved by the exhaustive search in the finite discrete action space <cit.>. According to <cit.>, 𝐧_q(t) will finally converge to the actual 𝐧^*(t) as q increases.






§ POLICIES COMPARISON VIA POA ANALYSIS

In this section, we first analyze the monotonicity of the two policies with respect to hazard belief x_i(t) and variance cost V(·). Then, we show that the myopic policy misses both exploration and exploitation over time, as compared to the social optimum, leading to PoA≥ 2. This implies at least doubled total travel cost for all users and motivates our mechanism design in Section <ref>. 


We first analyze the monotonicity of cost functions under both policies in (<ref>) and (<ref>) below.

The long-term cost functions (<ref>) and (<ref>) under both policies increase with expected travel latency 𝔼[ℓ_i(t)|x_i'(t-1)], hazard state x_i(t) and users' variance cost V(·) on stochastic path i. 


The proof of Lemma 2 is given in Appendix B of the supplement material. As hazard belief x_i(t) increases, the expected correlation coefficient 𝔼[α_i(t)|x_i'(t)] will also increase, which incurs a larger travel cost for future users choosing stochastic path i. As variance cost V(·) enlarges, users at any time t face a greater error to estimate the travel latency on path i, which incurs a larger travel cost in (<ref>). 






































Based on the monotonicity of cost functions in Lemma <ref>, we then analyze the monotonicity of their corresponding exploration numbers n_i^(m)(t) and n_i^*(t) in the next lemma.

Both exploration numbers n_i^(m)(t) and n_i^*(t) decrease with x_i(t) and V(·). While the difference n_i^*(t)-n_i^(m)(t) increases with x_i(t) but decreases with V(·).


The proof of Lemma 3 is given in Appendix C of the supplement material. Intuitively, as hazard belief x_i(t) increases, the myopic policy becomes less willing to explore stochastic path i, which has a larger immediate travel cost than safe path 0, than the socially optimal policy. However, as V(·) enlarges, users' explorations will incur extra error costs, making both policies unwilling to explore. 
Lemma <ref> also tells that longer expected latency 𝔼[ℓ_i(t)|x_i'(t-1)], stronger hazard belief x_i(t), and enlarged variance cost V(·) may hinder allocating more users to explore stochastic path i.



 §.§ Exploration and Exploitation Comparison

Thanks to Lemma <ref>, now we are ready to analytically compare n_i^(m)(t) with n_i^*(t). Before that, we first define the myopic routing policy's under/over-exploration of stochastic path i as compared to the social optimum in the following.

The myopic policy under-explores stochastic path i if n_i^(m)(t)< n_i^*(t), and over-explores if n_i^(m)(t)≥ n_i^*(t) at time t.



Based on Definition <ref>, we next prove that the myopic policy misses both proper exploration and exploitation of stochastic path i, as hazard belief x_i(t) dynamically changes over time.

There exists a belief threshold x_th∈(0,1), such that the myopic policy will over-explore stochastic path i (with n_i^(m)(t)≥ n_i^*(t)) if x_i(t)<x_th, and will under-explore stochastic path i (with n_i^(m)(t)<  n_i^*(t)) if x_i(t)≥ x_th, as compared to the socially optimal policy. This belief threshold x_th increases with V(·).


The proof of Proposition 1 is given in Appendix D of the supplement material. If there is a strong hazard belief x_i(t)≥ x_th of α_i(t)=α_H, the myopic policy is not willing to explore stochastic path i due to longer latency. However, the socially optimal policy still allocates some users to learn possible α_L future others to exploit. In contrast, given weak x_i(t)<x_th, myopic users flock to stochastic path i without considering future congestion, while the social optimum may exploit safe path 0 to reduce congestion on path i. According to Lemma <ref>, as error cost V(·) increases, the socially optimal policy also becomes less willing to explore stochastic path i, leading to a belief threshold x_th.



To illustrate this, in Fig. <ref>, we simulate Fig. <ref> using an illustrative basic two-path network with M=1. We plot the myopic exploration number n_1^(m)(t) in (<ref>) and the optimal n_1^*(t) derived by (<ref>) versus hazard belief x_1(t) of stochastic path 1. These two thresholds are very different as shown in Fig. <ref>. Here we set ℓ_0=15,N=5,𝔼[ℓ_1(t-1)]=20, α_H=1.5,α_L=0.05 at current time t. Here q_H(n_1(t)) in (<ref>) follows a normal distribution’s CDF with mean 0.3 and variance 1, and we properly choose error function V(n(t-1))=min{10/n(t-1),20}. Given the belief threshold x_th=0.3 here, if the hazard belief x_1(t)<x_th, we have the myopic exploration threshold n_1^(m)(t) larger than the optimal n_1^*(t) to over-explore stochastic path 1. 
If x_1(t)≥ x_th, the myopic exploration threshold satisfies n_1^(m)(t) smaller than the optimal n_1^*(t) to under-explore. This result is consistent with Proposition <ref>.



 §.§ PoA Analysis

After comparing the two policies, we want to quantify the efficiency gap between their corresponding social costs. Define the price of anarchy (PoA) as the maximum ratio between the social cost in (<ref>) under the myopic policy and the minimum cost in (<ref>) under the socially optimal policy <cit.>:

    PoA^(m)=max_   [0.65]α_H,α_L,𝐱(t),ℓ_0,N(t)
       [0.65]  𝐋(t),q_H,q_L,V(·)C^(m)(𝐋(t),𝐱(t),N(t))/C^*(𝐋(t),𝐱(t),N(t)),

by searching all possible parameters and error function V(·) of the dynamic system. It is obvious that PoA^(m)≥ 1. 

In the next theorem, we prove the lower bound of PoA. 

In the parallel traffic network with M stochastic paths, as compared to the minimum social cost in (<ref>), the myopic policy in (<ref>) results in: 

    PoA^(m)≥2(1-ρ^Ψ)/2-ρ-ρ^Ψ,

where Ψ=1+log_α_H(M(ℓ_0-N_min/M-V(N_min/M))(α_H-1)/α_H N_max+1). The lower bound in (<ref>) is larger than 2 as ρ→ 1, V(N_min/M)≪ℓ_0 and ℓ_0≫α_H N_max/M.


The proof of Theorem <ref> is given in Appendix E of the supplement material. Inspired by Proposition <ref>, the worst case may happen when the myopic policy maximally under-explores stochastic paths with strong hazard belief x_i(t). Initially, we set expected correlation coefficient 𝔼[α_i(0)|x_i(0)]=1 and expected travel costs c_i(0)=c_0(N_max) for any stochastic path i. Then according to (<ref>), myopic users always choose safe path 0 to make n_i^(m)(t)=0. However, the socially optimal policy frequently asks n_i^*(t)>0 of new user arrivals to explore stochastic path i to learn α_L=0, which greatly reduces future travel latency on this path. After that, all users will keep exploiting path i with α_i(t)=α_L, and the expected travel cost on this path may gradually increase to c_i(N_min/M)=c_0(0) again after at least Ψ time slots. As Ψ→∞ (by setting small variance cost V(N_min/M)≪ℓ_0 and large latency ℓ_0≫α_H N_max/M) and ρ→ 1, we have PoA^(m)≥ 2.

We can also show that the PoA^(m) lower bound in (<ref>) decreases with variance cost V(·). This is consistent with Lemma <ref> and Proposition <ref> that n_i^(m)(t) approaches to n_i^*(t) as V(·) enlarges. Besides, if stochastic path number M→∞, Ψ approaches infinity, and the lower bound of PoA in (<ref>) becomes 2, as more stochastic paths can negate the congestion cost caused by users' exploration.
As users' myopic routing can at least double the social cost with PoA^(m)≥ 2, we are well motivated to design an efficient mechanism to regulate.



§ CHAR MECHANISM WITH LEARNING CONVERGENCE

In this section, we aim to design an informational mechanism to regulate users' myopic routing. We first analyze x_i(t)'s learning convergence under both myopic and socially optimal policies. Based on this analysis, we further show that existing information-hiding and deterministic-recommendation mechanisms are far from efficient. Accordingly, we propose our combined hiding and probabilistic recommendation (CHAR) mechanism and prove its close-to-optimal efficiency.



 §.§ Learning Convergence Analysis


In the next lemma, we show that the myopic policy fails to ensure correct long-run convergence of hazard belief x_i(t).


Under the myopic policy with exploration number n^(m)_i(t) on path i, the learned x_i(t) is not guaranteed to converge to its real steady state x in (<ref>) as t→∞.


The proof of Lemma 4 is given in Appendix F of the supplement material. Under the myopic policy, users only care about the immediate travel latency of each path. If the travel latencies of stochastic paths all satisfy 𝔼[ℓ_i(t)|x_i(t)]> ℓ_0 with 𝔼[α_i(t)|x_i(t)]≥ 1, myopic user arrivals will never explore any stochastic path i and fail to update x_i(t). In this case, hazard belief x_i(t) may deviate a lot from its real steady state x. The deviation of x_i(t) also incurs extra costs to mislead future users. Next, we examine the learning convergence of x_i(t) under the socially optimal policy.


Under the socially optimal policy with exploration number n_i^*(t), once V(N_min)<ℓ_0, as t→∞, x_i(t) is guaranteed to converge to its real steady state x in (<ref>).


The proof of Proposition 2 is given in Appendix G of the supplement material. If V(N_min)≥ℓ_0, the huge variance cost discourages the system to explore and converge to the real expected belief x in any way. Note that even with V(N_min)<ℓ_0, the myopic policy is not guaranteed to converge to real expected belief x. While the socially optimal policy is willing to frequently explore stochastic path i to learn a low-hazard state α_L to reduce the expected travel latency for the followers. With long-term frequent exploration, hazard belief x_i(t) can finally converge to its real steady state x. The convergence to x also helps the system best decide routing and reduce social costs.



In Fig. <ref>, we run multiple experiment instances to show the average convergence of x_1(t) under both policies in a finite time horizon {0,⋯,30}. Here we set N(0)=N=7,ℓ_0=100,x_1(0)=0.66,𝔼[ℓ_1(0)|x_1(0)=0.6]=110,n_1(0)=0,ρ=0.99,α_H=1.5,α_L=0.05, and α=0.7 with x=0.45 at initial time t=0. Here q_H(n_1(t)) in (<ref>) follows a normal distribution's CDF with mean 0.3 and variance 1, and we properly choose error function V(n(t-1))=min{10/n(t-1),20}. Under these parameter settings, the myopic policy never explores stochastic path 2, because the expected latency on path 2 keeps increasing under 𝔼[α(t)|x(t-1)]=1.007. Hence, the myopic policy makes x(t)=0.66 deviate from real but unknown x=0.45 in Fig. <ref>. However, the socially optimal policy still recommends some users to learn useful information on path 2, which ensures x(t)'s correct convergence to x=0.45. The simulation results above are consistent with Lemma <ref> and Proposition <ref>.



 §.§ Benchmark Informational Mechanisms Comparison


Before presenting our new mechanism, we first follow the mechanism design literature <cit.> to generally define the informational mechanism below. 

An informational mechanism defines an incomplete information Bayesian game, where the social planner determines the disclosing level of variables based on the system state. 


In practice, informational mechanisms are non-monetary and easier to implement as compared to pricing and side-payment mechanisms (e.g., <cit.>).
Then we analyze the efficiency of two widely used informational mechanisms: information-hiding <cit.> and deterministic-recommendation <cit.>. Note that we also tried prior Bayesian persuasion mechanisms <cit.>, which focus on one-shot games and cannot optimize long-run information learning.

Based on Proposition <ref>, if the platform hides all the information, i.e., 𝐋(t),𝐱(t) and N(t), as <cit.>, users can only estimate that each stochastic path has reached its steady state x∼ℙ(x) in (<ref>) and 𝔼[N(t)]=N for any time t. As in <cit.>, expected exploration number n_i^∅∈{0,1,⋯,N(t)} of stochastic path i under information-hiding becomes constant:

    n_i^∅=min{N(t)/M,N+c_0(0)-𝔼_x∼ℙ(x)[c_i(0)|x]/M+1},

where c_0(·) and c_i(·) are defined in (<ref>) and (<ref>), respectively.
We next prove the infinite PoA caused by the hiding mechanism.

If the platform hides all the information, i.e., 𝐋(t),𝐱(t) and N(t), from users, the constant policy n^∅_i in (<ref>) makes users either under- or over-explore stochastic path i as compared to the social optimum, leading to PoA=∞.


The proof of Lemma 5 is given in Appendix H of the supplement material. If 𝔼_x∼ℙ(x)[c_i(N_max/M)|x]≤ c_0(0), all the N(t) users without information will choose stochastic paths with less expected cost. However, the actual α_i(t) can be α_H and 𝔼[ℓ_i(t)|x_i(t)]≫ℓ_0, then users’ maximum over-exploration makes PoA arbitrarily large. Similarly, if 𝔼_x∼ℙ(x)[c_i(0)|x]> c_0(N_max), all users will choose path 0, leading to the maximum under-exploration.

Next, we consider the existing deterministic recommendation mechanisms (<cit.>), which privately provide state-dependent deterministic recommendations to users while hiding other information, to prove the caused infinite PoA. 

The deterministic-recommendation mechanism makes PoA=∞ in our system.


The proof of Lemma 6 is given in Appendix I of the supplement material. When a user receives recommendation π(t)=i, he only infers n_i(t)≥ 1 on path i. However, if expected user number N≫ 1, this information is insufficient to alter his posterior distribution of x from ℙ(x). Consequently, the caused exploration number still approaches n^∅_i in (<ref>), leading to PoA=∞. 



 §.§ New CHAR Mechanism Design and Analysis


Inspired by Subsection <ref>, the previous two mechanisms do not work in improving our system performance. Thus, we will properly combine them for a new mechanism design. To approach optimal policy n_i^*(t) as much as possible, we dynamically select a number N^∅(t) of users to follow hiding policy n_i^∅ in (<ref>), while providing state-dependent probabilistic recommendations to the remaining N(t)-N^∅(t) users.

Now we are ready to propose our combined hiding and probabilistic recommendation (CHAR) mechanism, which contains two steps per time slot t. Under CHAR, let n^(CHAR)_i(t)∈{0,⋯,N(t)} represent the exploration number of path i at t. Similar to (<ref>), denote C^(CHAR)(𝐋(t),𝐱(t),N(t)) to be the long-term social cost under 𝐧^(CHAR)(t).
 
At any time t, in the first step, the platform randomly divides the N(t) users into the hiding-group with N^∅(t) users and the recommendation-group with N(t)-N^∅(t) users, where the dynamic number N^∅(t) is the optimal solution to 

    min_N^∅(t)∈{0,⋯,N(t)}   C^(CHAR)(𝐋(t),𝐱(t),N(t)),
    s.t.         n_i^(CHAR)(t)=N^∅(t)·n_i^∅/N(t)+
               (N(t)-N^∅(t))𝐏𝐫(π(t)=i|x_i(t)),

where

    𝐏𝐫(π(t)=i|x_i(t))=p_L,  if x_i(t)< x_th,
    p_H, if x_i(t)≥ x_th,

with x_th is in Proposition <ref> and any feasible p_L and p_H to satisfy p_Lℙ(x_th)≥ p_H(1-ℙ(x_th)).

In the second step, the platform performs as follows:

    
  * For the N^∅(t) hiding-group users, the platform hides all the past information from them. 
    
  * For the rest N(t)-N^∅(t) users in the recommendation-only group, the platform randomly recommends a path π(t) to each user arrival by the following distribution:
    
    π(t)=
                i,   with 𝐏𝐫(π(t)=i|x_i(t)) in (<ref>),
    
                0,   with 1-∑_i=1^M𝐏𝐫(π(t)=i|x_i(t)).

    



According to Definition <ref>, the N^∅(t) users in the uniformly selected hiding-group rely on hiding policy n_i^∅ in (<ref>) to make routing decisions. For the recommendation-only group, given the always feasible p_L and p_H to satisfy p_L ℙ(x_th)≥ p_H (1-ℙ(x_th)), if a user receives a recommendation π(t)=i, he infers that the posterior belief of low hazard x_i(t)<x_th on path i is larger than the high harzard x_i(t)≥ x_th. Thus, this user will not deviate from the recommendation for a smaller expected travel cost. Similarly, if recommended π(t)=0, the user can infer that any stochastic path i is more likely to have x_i(t)≥ x_th and accordingly will choose safe path 0. 

Given Bayesian incentive compatibility for all users, according to (<ref>), there are respectively N^∅(t)· n_i^∅/N(t) users in the hiding-group and (N(t)-N^∅(t))·𝐏𝐫(π(t)=i|x_i(t)) users in the recommendation-only group traveling on any path i. 
If stochastic path i has a good condition with x_i(t)<x_th at time t, the recommendation probability in (<ref>) is 𝐏𝐫(π(t)=i|x_i(t))=p_L. Then the exploration number of users on path i under our CHAR mechanism satisfies

    n_i^(CHAR)=N^∅(t)(n_i^∅/N(t)-p_L)+p_LN(t),




which depends on the choice of N^∅(t)∈{0,⋯, N(t)}. While if path i has a bad condition with x_i(t)≥ x_th, n_i^(CHAR) is similarly derived.



To make n_i^(CHAR)(t) approach optimum n_i^*(t) on each path i, the platform optimizes (<ref>) to determine the optimal solution N^∅(t) in each time slot t.

Then we propose the following theorem to prove the close-to-optimal performance of our CHAR mechanism.

Our CHAR mechanism in Definition <ref> ensures Bayesian incentive compatibility for all users and regulates the dynamic routing system to achieve 

    PoA^(CHAR)=1+1/2(M+1)(1+M/N· V(N(2M+1)/2M(M+1))),

which is always less than 5/4 and cannot be further reduced by any informational mechanism.




The proof of Theorem <ref> is given in Appendix J of the supplement material. On one hand, our CHAR mechanism recommends n_i^(CHAR)>n_i^(m)(t) users to explore stochastic path i of high belief x_i(t)≥ x_th. This successfully avoids myopic policy's zero-exploration in Theorem <ref>. On the other hand, our CHAR well controls the number of users on stochastic paths with bad conditions, avoiding benchmark mechanisms' maximum exploration in bad traffic conditions in Lemmas <ref> and <ref>. Therefore, it efficiently reduces PoA^(m)≥ 2 caused by the myopic policy. Under our CHAR, the worst case occurs when users over-explore stochastic paths in good conditions (α_i(t)=α_L).
We consider the scenario where the travel cost on any stochastic path i satisfies c_i(N_max/M)<c_0(0) even if α_i(t)=α_H. Then all users will opt for stochastic paths, and no information incentives can curb their over-exploration. The achieved minimum PoA is derived in (<ref>), which cannot be further reduced by any informational mechanism.

Our CHAR's PoA in (<ref>) increases with the expected user number N and decreases with path number M. As N→∞, PoA^(CHAR) converges to 1+1/2(M+1) with minimum 5/4. While if M→∞, PoA^(CHAR) approaches the optimum 1.





§ EXTENSIONS OF PARALLEL TRANSPORTATION NETWORK TO LINEAR PATH GRAPHS

In this section, we extend our congestion model and analysis from the parallel transportation network between two nodes O and D in Fig. <ref> to more general linear path networks with multiple intermediate nodes and stochastic paths (<cit.>). In this generalized model, we first establish that the PoA lower bound caused by the myopic policy remains unchanged. Next, we prove that our CHAR mechanism continues to effectively reduce the PoA to its minimum possible value.


As depicted in Fig. <ref>, we consider a general linear path graph, which contains an order list of k intermediate nodes, denoted by D_1,⋯, D_k, between origin O and destination D. For ease of exposition, we denote D_0=O and D_k+1=D. At each node D_j for j∈{0,1,⋯,k}, there exist one safe path 0^j and M stochastic paths 1^j,⋯, M^j leading to the next node D_j+1. The safe path 0^j within the j-th subnetwork has a fixed travel latency ℓ_0^j. While for the other M^j stochastic paths, their correlation coefficients still alternate between a high-hazard state α_H and a low-hazard state α_L over time.  

Within each subnetwork j from node D_j to D_j+1 of this generalized path network, users traveling on stochastic path i^j will learn the traffic information there and update its hazard belief x_i^j(t+1) for the platform as follows:

    x_i^j(t+1)=x'_i^j(t)q_HH(t)+(1-x'_i^j(t))q_LH(t).


In this extended system model, a user arriving at node D_j not only needs to consider his current travel cost c_i^j(n_i^j(t)) in the j-th subnetwork, but also cares about his cost-to-go in the future subnetworks {j+1,⋯,k}. This makes the myopic policy different from the one-shot decision in (<ref>) for the parallel network in Fig. <ref>. Nonetheless, we still managed to obtain the PoA caused by the myopic routing policy in the following proposition.


Under the general linear path graph in Fig. <ref>, as compared to the social optimum, the myopic policy achieves 

    PoA^(m)≥2(1-ρ^Ψ)/2-ρ-ρ^Ψ,

where Ψ=1+log_α_H(M(ℓ_0^j-N_min/M-V(N_min/M))(α_H-1)/α_H N_max+1). The lower bound in (<ref>) is larger than 2 as ρ→ 1, V(N_min/M)≪ℓ_0^j and ℓ_0^j≫α_H N_max/M for any j∈{0,⋯,k}.


The proof of Proposition <ref> is given in Appendix K of the supplement material. In the linear path network illustrated in Fig. <ref>, we set an expected correlation coefficient 𝔼[α_i^j(0)|x_i^j(0)]=1 and expected travel costs c_i^j(0)=c_0^j(N_max) for any stochastic path i^j. In the worst-case scenario with ρ=1, the myopic policy still leads all users to choose the safe path 0^j at any node D_j. While the socially optimal policy always recommends n_i^j^*(t)>0 users to explore stochastic path i^j to potentially learn possible α_L=0 there. After that, all users keep exploiting stochastic path i^j with α_i^j(t)=α_L, resulting in PoA>2. It is noteworthy that in this case, both the myopic policy and the socially optimal policy just repeat their decision-making processes, as in (<ref>) and (<ref>), for k+1 times from origin O to destination D. Consequently, the resulting PoA remains the same as that of the parallel path network in Theorem <ref>. 

Motivated by Proposition <ref>, we next examine our CHAR mechanism's performance for this generalized system. In the following, we consider ρ=1 in the worst-case scenario to regulate myopic routing. Let vectors 𝐋^j(t) and 𝐱^j(t) summarize the latencies and beliefs of all the M stochastic paths within the j-th subnetwork. Denote by N^j(t) the arriving user number at node D^j at time t. We first propose the following lemma to check users' decision-making without information sharing.

If the platform hides all the information of the linear path graph in Fig. <ref> from all users at any node D_j, i.e., 𝐋^j(t), 𝐱^j(t) and N^j(t) at any time t, the expected exploration number of stochastic path i^j within the j-th subnetwork equals

    n_i^j^∅=min{N^j(t)/M,N+c_0^j(0)-𝔼_x∼ℙ(x)[c_i^j(0)|x]/M+1}.



The proof of Lemma <ref> is given in Appendix L of the supplement material. Intuitively, without any information, users can only estimate that each stochastic path i^j has reached its steady state x in (<ref>) and 𝔼[N^j(t)]=N for any time t. Under the steady state, for any user at node D_j, his expected cost-to-go for the future subnetworks {j+1,⋯,k} is unaffected by his current path choice. Therefore, he only needs to focus on the current subnetwork j, as (<ref>) in the parallel network, to make his routing decision. This leads to the total exploration number n_i^j^∅ in (<ref>) for path i^j.

Thanks to Lemma <ref>, we only need to focus on a single subnetwork {D_j,D_j+1} to regulate each user arrival at node D_j. As a result, our CHAR mechanism for the parallel network in Definition <ref> still works. Subsequently, we prove its PoA result in the following theorem.


Under the linear path graph in Fig. <ref>, our CHAR mechanism in Definition <ref> regulates the dynamic system to achieve the same PoA as (<ref>), which is always less than 5/4.


The proof of Theorem <ref> is given in Appendix M of the supplement material. Since our CHAR mechanism only needs to regulate users within each subnetwork j, the achieved PoA within each subnetwork is equal to (<ref>), as in the parallel transportation network. When considering all k+1 subnetworks, the PoA remains unchanged.



§ EXPERIMENT VALIDATION USING REAL DATASETS

In addition to the worst-case PoA analysis, in this section, we further conduct experiments to evaluate our CHAR's average performance versus the myopic policy used by Waze and Google Maps and the popular information hiding mechanism used in existing congestion game literature (<cit.>). To further practicalize our dynamic congestion model in (<ref>), we sample peak hours' real-time traffic congestion data in Beijing, China on public holidays using BaiduMap (<cit.>), and further extend our parallel transportation network in Fig. <ref> and linear path graph in Fig. <ref> to a hybrid road network in Fig. <ref>. 



As depicted in Fig. <ref>, we consider a popular hybrid road network from the Palace Museum to the National Stadium on public holidays, as many visitors randomly leave the Palace Museum and travel to the National Stadium. This hybrid network consists of three path choices, each with a series of safe and stochastic roads:

    
  * Path 1: Donghuamen Street, Beiheyuan Street, and Anding Road.
    
  * Path 2: Beichizi Avenue, Dianmen Street, Outer Jiugulou Street and Beichen Road.
    
  * Path 3: Beichizi Avenue, Dianmen Street, Jingzang Expressway, and Jianxiang Bridge.

Here Path 2 and Path 3 overlap on Beichizzi Avenue and Dianmen Street, making it different from the linear path graph in Fig. <ref>.

To train a practical congestion model with travel latency, we mine and analyze many data about the real-time traffic status values of the nine roads from <cit.>, which can dynamically change every 5 minutes in the peak-hour periods. We validate from the dataset that the traffic conditions of Donghuamen Street and Beiheyuan Street on Path 1, Beichizi Avenue on both Path 2 and Path 3, and Jianxiang Bridge on Path 3 can be well approximated as Markov chains with two discretized states (high and low traffic states) as in (2), while the other five roads tend to have deterministic/safe conditions. Similar to <cit.>, we employ the hidden Markov model (HMM) approach to train the transition probability matrices for the four stochastic road segments using 432 statuses with 5 minutes per time slot, which suffice to achieve high accuracy. Based on the transition probability matrices, we further calculate the steady-state belief x's of the four stochastic roads in Fig. <ref>:

    x_Donghuamen   =0.388, x_Beihe   =0.106,
    x_Beichizi   =0.192, x_Jianxiang=0.936.

Then these steady-state beliefs can be used in the congestion model for our experiments.










Besides the above congestion model, based on the travel latency data in <cit.>, we calculate the long-term average correlation coefficients α_H≈ 1.3 and α_L≈ 0.3, by assuming a linear latency function f(·) in (<ref>). Then we use the traffic flow data from Baidu Map to calculate the mean arrival car number is N=121 every 5 minutes at the gateway of the Palace Museum, with a standard deviation of 12.33. Given the mean arrival car number, we set V(n(t-1))=min{100/n(t-1),200}.

Based on the derived system parameters above, we are now ready to conduct our experiments. In the myopic policy, each user estimates the travel cost of any path choice, by aggregating the costs of its road segments, to select the one that minimizes his own travel cost, whereas the socially optimal policy seeks the path choice that minimizes the collective long-term social cost for all users. Our CHAR mechanism optimizes the user number of the hiding-group N^∅(t) in (<ref>) and recommends path π(t) to each user of the recommendation-only group in (<ref>). This is achieved by combining the actual hazard beliefs of all stochastic road segments on each path choice. As users' costs are proportional to their travel delays, we conduct 50 experiments, each with 31 time slots (equivalent to 155 minutes), to calculate their average long-term social costs (in minutes). Here the initial hazard beliefs are approximated to 0.5,0.2,0.3, and 0.8 for Donghuamen Street, Beiheyuan Street, Beichizi Avenue, and Jianxiang Bridge, respectively.




In the first experiment, we fix discount factor ρ=0.98 to compare the average long-term social costs under the myopic policy, information hiding mechanism, the socially optimal policy, and our CHAR mechanism versus time horizon T∈{0,⋯, 30}. Fig. <ref> depicts that our CHAR mechanism has less than 5% efficiency loss from the social optimum for any time horizon T, while the myopic policy and the information hiding mechanism cause around 90% and 125% efficiency losses, respectively.




Next, we define 

    IR^(m)=𝔼[C^(m)(𝐋(t),𝐱(t),N(t))]/𝔼[C^*(𝐋(t),𝐱(t),N(t))]

to be the long-term average inefficiency ratio of the total travel cost C^(m)(𝐋(t),𝐱(t),N(t)) under the myopic policy in (<ref>), as compared to C^*(𝐋(t),𝐱(t),N(t)) under the socially optimal policy in (<ref>). Similarly, define 

    IR^(∅)   =𝔼[C^(∅)(𝐋(t),𝐱(t),N(t))]/𝔼[C^*(𝐋(t),𝐱(t),N(t))],
    IR^(CHAR)   =𝔼[C^(CHAR)(𝐋(t),𝐱(t),N(t))]/𝔼[C^*(𝐋(t),𝐱(t),N(t))]

to be the average inefficiency ratios caused by the information hiding mechanism and our CHAR mechanism, respectively. Then in the second experiment, we fix time horizon T=30 to compare the average inefficiency ratios IR^(m), IR^(∅) and IR^(CHAR) caused by the myopic policy, information hiding mechanism, and our CHAR mechanism versus discount factor ρ∈{0,0.2,0.4,0.6,0.8,1}. 

Fig. <ref> tells that all the inefficiency ratios increase with discount factor ρ, which is aligned with Theorem <ref>. In the worst case with ρ=1, our CHAR mechanism obviously reduces IR^(m)>1.9 and IR^∅>2.2 under the myopic policy and hiding mechanism to the close-to-optimal ratio IR^(CHAR)<1.1, which is consistent with Theorem <ref>. Note that even in the best case with ρ=0, both myopic policy and information hiding mechanism perform poor with IR^(m)>1.2 and IR^∅>1.5, while our CHAR mechanism makes IR^(CHAR)<1.05.



§ CONCLUSION

In this paper, we focus on dynamic congestion games with endogenous time-varying conditions to analyze and regulate human-in-the-loop learning. In a typical parallel routing network, our analysis shows that the myopic routing policy (used by Google Maps and Waze) leads to severe under-exploration of stochastic paths. This results in a price of anarchy (PoA) greater than 2, as compared to the social optimum achieved through optimal exploration-exploitation tradeoff. Besides, the myopic policy fails to ensure the correct learning convergence about users' traffic hazard beliefs. To address this, we first show that existing information-hiding mechanisms and deterministic path-recommendation mechanisms in Bayesian persuasion literature do not work with even PoA=∞. Accordingly, we propose a new combined hiding and probabilistic recommendation (CHAR) mechanism to hide all information from a selected user group and provide state-dependent probabilistic recommendations to the other user group. Our CHAR successfully ensures PoA less than 5/4, which cannot be further reduced by any other informational mechanism. Besides parallel networks, we further extend our analysis and CHAR to more general linear path graphs with multiple intermediate nodes, and we prove that the PoA results remain unchanged. Additionally, we carry out experiments with real-world datasets to validate the close-to-optimal performance of our CHAR mechanism.

In the future, we consider generalizing our human-in-the-loop learning beyond transportation applications, by considering stochastic queueing service systems (e.g., hospitals and restaurants). In queueing systems, many selfish users (e.g., customers for dining) are unwilling to explore new restaurants to learn useful information (e.g., tastes and queue length) for future customers. Thus, we need to design an efficient mechanism to regulate their exploration and exploitation of different servers.



































9

li2024distributed
H. Li and L. Duan, “Distributed Learning for Dynamic Congestion Games,” in Proc. IEEE International Symposium on Information
  Theory (ISIT), 2024.  

zhang2022review
H. Zhang, H. Ge, J. Yang, and Y. Tong, “Review of vehicle routing problems:
  Models, classification and solving algorithms,” Archives of
  Computational Methods in Engineering, vol. 29, no. 1, pp. 195–221, 2022.
  
waze
T. Haselton, “How to use Google Waze,”
  <https://www.cnbc.com/2018/11/13/how-to-use-google-waze-for-directions-and-avoiding-traffic.html>,
  2018.

application
FHWA, “Crowdsourcing for advancing operations,”
  <https://www.fhwa.dot.gov/innovation/everydaycounts/edc_6/crowdsourcing.cfm>,
  2024.

zhu2022information
Y. Zhu and K. Savla, “Information design in non-atomic routing games with
  partial participation: Computation and properties,” IEEE Transactions
  on Control of Network Systems, 2022.

vasserman2015implementing
S. Vasserman, M. Feldman, and A. Hassidim, “Implementing the wisdom of waze,”
  in Twenty-Fourth International Joint Conference on Artificial
  Intelligence, 2015.

liu2012learning
H. Liu, K. Liu, and Q. Zhao, “Learning in a changing world: Restless
  multiarmed bandit with unknown dynamics,” IEEE Transactions on
  Information Theory, vol. 59, no. 3, pp. 1902–1916, 2012.

slivkins2019introduction
A. Slivkins et al., “Introduction to multi-armed bandits,”
  Foundations and Trends® in Machine Learning, vol. 12,
  no. 1-2, pp. 1–286, 2019.

gupta2021multi
S. Gupta, S. Chaudhari, G. Joshi, and O. Yağan, “Multi-armed bandits
  with correlated arms,” IEEE Transactions on Information Theory,
  vol. 67, no. 10, pp. 6711–6732, 2021.

bozorgchenani2021computation
A. Bozorgchenani, S. Maghsudi, D. Tarchi, and E. Hossain, “Computation
  offloading in heterogeneous vehicular edge networks: On-line and off-policy
  bandit solutions,” IEEE Transactions on Mobile Computing, vol. 21, no. 12, pp. 4233-4248, 2021.

wang2022truthful
H. Wang, Y. Yang, E. Wang, W. Liu, Y. Xu, and J. Wu, “Truthful user
  recruitment for cooperative crowdsensing task: A combinatorial multi-armed
  bandit approach,” IEEE Transactions on Mobile Computing, vol. 22, no. 7, pp. 4314-4331, 2022.

li2020multi
F. Li, D. Yu, H. Yang, J. Yu, K. Holger, and X. Cheng, “Multi-armed-bandit-based spectrum scheduling algorithms in wireless networks: A survey,” IEEE Wireless Communications, vol. 27, no. 1, pp. 24-30, 2020.
  
shi2021federated
C. Shi and C. Shen, “Federated multi-armed bandits,” in Proceedings of
  the AAAI Conference on Artificial Intelligence, vol. 35, no. 11, 2021, pp.
  9603–9611.

yang2021cooperative
L. Yang, Y.-Z. J. Chen, S. Pasteris, M. Hajiesmaili, J. Lui, and D. Towsley,
  “Cooperative stochastic bandits with asynchronous agents and constrained
  feedback,” Advances in Neural Information Processing Systems,
  vol. 34, pp. 8885–8897, 2021.

yang2022distributed
L. Yang, Y.-Z. J. Chen, M. H. Hajiemaili, J. C. Lui, and D. Towsley,
  “Distributed bandits with heterogeneous agents,” in IEEE INFOCOM
  2022-IEEE Conference on Computer Communications.1em plus 0.5em minus
  0.4emIEEE, 2022, pp. 200–209.

zhu2023distributed
J. Zhu and J. Liu, “Distributed multi-armed bandits,” IEEE Transactions
  on Automatic Control, 2023.

meng2014routing
C. Meng and A. Markopoulou, “On routing-optimal networks for multiple
  unicasts,” in 2014 IEEE International Symposium on Information
  Theory.1em plus 0.5em minus 0.4emIEEE, 2014, pp. 111–115.  

das2017reducing
S. Das, E. Kamenica, and R. Mirka, “Reducing congestion through information
  design,” in 2017 55th annual allerton conference on communication,
  control, and computing (allerton).1em plus 0.5em minus 0.4emIEEE, 2017, pp. 1279–1284.

kamenica2019bayesian
E. Kamenica, “Bayesian persuasion and information design,” Annual
  Review of Economics, vol. 11, pp. 249–272, 2019.

mansour2022bayesian
Y. Mansour, A. Slivkins, V. Syrgkanis, and Z. S. Wu, “Bayesian exploration:
  Incentivizing exploration in bayesian games,” Operations Research,
  vol. 70, no. 2, pp. 1105–1127, 2022.

babichenko2022regret
Y. Babichenko, I. Talgam-Cohen, H. Xu, and K. Zabarnyi, “Regret-minimizing
  bayesian persuasion,” Games and Economic Behavior, vol. 136, pp.
  226–248, 2022.

gollapudi2023online
S. Gollapudi, K. Kollias, C. Maheshwari, and M. Wu, “Online learning for
  traffic navigation in congested networks,” in International Conference
  on Algorithmic Learning Theory.1em plus 0.5em minus 0.4emPMLR,
  2023, pp. 642–662.

yang2009discretization
Y. Yang and G. I. Webb, “Discretization for naive-bayes learning: managing
  discretization bias and variance,” Machine learning, vol. 74, no. 1,
  pp. 39–74, 2009.

meunier2010equilibrium
F. Meunier and N. Wagner, “Equilibrium results for dynamic congestion games,”
  Transportation Science, vol. 44, no. 4, pp. 524–536, 2010.

carmona2020pure
G. Carmona and K. Podczeck, “Pure strategy nash equilibria of large
  finite-player games and their relationship to non-atomic games,”
  Journal of Economic Theory, vol. 187, p. 105015, 2020.

li2022online
H. Li, and L. Duan, “Online pricing incentive to sample fresh information,” IEEE Transactions on Network Science and Engineering,
  vol. 10, no. 1, pp. 514–526, 2022.
  
Ferguson2022effective
B. L. Ferguson, P. N. Brown, and J. R. Marden, “The effectiveness of subsidies
  and tolls in congestion games,” IEEE Transactions on Automatic
  Control, vol. 67, no. 6, pp. 2729–2742, 2022.

li2024incentivizing
F. Li, Y. Chai, H. Yang, P. Hu, and L. Duan, “The effectiveness of subsidies
  and tolls in congestion games,” IEEE/ACM Transactions on Networking, 2024.

tavafoghi2017informational
H. Tavafoghi and D. Teneketzis, “Informational incentives for congestion
  games,” in 2017 55th Annual Allerton Conference on Communication,
  Control, and Computing (Allerton).1em plus 0.5em minus 0.4emIEEE, 2017, pp. 1285–1292.

wang2020efficient
J. Wang and M. Hu, “Efficient inaccuracy: User-generated information sharing
  in a queue,” Management Science, vol. 66, no. 10, pp. 4648–4666,
  2020.

farhadi2022dynamic
F. Farhadi and D. Teneketzis, “Dynamic information design: a simple problem on
  optimal sequential information disclosure,” Dynamic Games and
  Applications, vol. 12, no. 2, pp. 443–484, 2022.

li2019recommending
Y. Li, C. Courcoubetis, and L. Duan, “Recommending paths: Follow or not
  follow?” in IEEE INFOCOM 2019-IEEE Conference on Computer
  Communications.1em plus 0.5em minus 0.4emIEEE, 2019, pp.
  928–936.

wu2019learning
M. Wu and S. Amin, “Learning an unknown network state in routing games,”
  IFAC-PapersOnLine, vol. 52, no. 20, pp. 345–350, 2019.

li2023congestion
H. Li and L. Duan, “When congestion games meet mobile crowdsourcing: Selective
  information disclosure,” in Proceedings of the AAAI Conference on
  Artificial Intelligence, vol. 37, no. 5, 2023, pp. 5739–5746.

kremer2014implementing
I. Kremer, Y. Mansour, and M. Perry, “Implementing the “wisdom of the
  crowd”,” Journal of Political Economy, vol. 122, no. 5, pp.
  988–1012, 2014.

ban2009delay
X. Ban, R. Herring, P. Hao, and A. M. Bayen, “Delay pattern estimation for
  signalized intersections using sampled travel times,” Transportation
  Research Record, vol. 2130, no. 1, pp. 109–119, 2009.

alam2019prediction
I. Alam, D. M. Farid, and R. J. Rossetti, “The prediction of traffic flow with
  regression analysis,” in Emerging Technologies in Data Mining and
  Information Security.1em plus 0.5em minus 0.4emSpringer, 2019,
  pp. 661–671.

venanzi2013crowdsourcing
M. Venanzi, A. Rogers, and N. R. Jennings, “Crowdsourcing spatial phenomena
  using trust-based heteroskedastic gaussian processes,” in First AAAI
  Conference on Human Computation and Crowdsourcing, 2013.

smith2018bayesian
A. L. Smith and S. S. Villar, “Bayesian adaptive bandit-based designs using
  the gittins index for multi-armed trials with normally distributed
  endpoints,” Journal of Applied Statistics, vol. 45, no. 6, pp.
  1052–1076, 2018.

roughgarden2005selfish
T. Roughgarden, Selfish routing and the price of anarchy.1em plus
  0.5em minus 0.4emMIT press, 2005.

bertsimas1997introduction
D. Bertsimas and J. Tsitsiklis, “Introduction to linear optimization,” 1em plus 0.5em minus
  0.4emAthena Scientific Belmont, MA, 1997





ross2014introduction
S. Ross, “Introduction to stochastic dynamic programming,” Academic press, 2014.

yao1980efficient
F. Yao, “Efficient dynamic programming using quadrangle inequalities,” Proceedings of the twelfth annual ACM symposium on Theory of computing, pp. 429–435, 1980.

fudenberg1991game
D. Fudenberg and J. Tirole, Game theory.1em plus 0.5em minus
  0.4emMIT press, 1991.

Broersma1989pathgraph
H. J. Broersma and C. Hoede, “Path graphs,” Journal of graph theory, vol. 13, no. 4, pp. 427–444, 1989.


Baidumap
B. BaiduMap, “Baidu maps open platform,”
  <https://lbsyun.baidu.com/faq/api?title=webapi/traffic-roadseek>, 2023.

eddy1998profile
S. R. Eddy, “Profile hidden markov models.” Bioinformatics (Oxford,
  England), vol. 14, no. 9, pp. 755–763, 1998.

chen2016predicting
Z. Chen, J. Wen, and Y. Geng, “Predicting future traffic using hidden markov
  models,” in 2016 IEEE 24th international conference on network
  protocols (ICNP).1em plus 0.5em minus 0.4emIEEE, 2016, pp.
  1–6.


















[
    < g r a p h i c s >
]Hongbo Li(S'24)
received the B.S. degree in Electronics and Electric Engineering from Shanghai Jiao Tong University, Shanghai, China, in 2019. He is working toward the Ph.D. degree with the Pillar of Engineering Systems and Design, Singapore University of Technology and Design (SUTD). Currently, he is a Visiting Scholar at The Ohio State University. His research interests include game theory and mechanism design, networked AI, and machine learning theory.





[
    < g r a p h i c s >
]Lingjie Duan(S'09-M'12-SM'17) received the Ph.D. degree from The Chinese University of Hong Kong in 2012. He is an Associate Professor at the Singapore University of Technology and Design (SUTD) and is an Associate Head of Pillar (AHOP) of Engineering Systems and Design. In 2011, he was a Visiting Scholar at University of California at Berkeley, Berkeley, CA, USA. His research interests include network economics and game theory, network security and privacy, energy harvesting wireless communications, and mobile crowdsourcing. He is an Associate Editor of IEEE/ACM Transactions on Networking and IEEE Transactions on Mobile Computing. He was an Editor of IEEE Transactions on Wireless Communications and IEEE Communications Surveys and Tutorials. He also served as a Guest Editor of the IEEE Journal on Selected Areas in Communications Special Issue on Human-in-the-Loop Mobile Networks, as well as IEEE Wireless Communications Magazine. He is a General Chair of WiOpt 2023 Conference and is a regular TPC member of some other top conferences (e.g., INFOCOM, MobiHoc, SECON). He received the SUTD Excellence in Research Award in 2016 and the 10th IEEE ComSoc Asia-Pacific Outstanding Young Researcher Award in 2015.








