In congestion games, selfish users behave myopically to crowd to the shortest paths, and the social planner designs mechanisms to regulate such selfish routing through information or payment incentives. However, such mechanism design requires the knowledge of time-varying traffic conditions and it is the users themselves to learn and report past road experiences to the social planner (e.g., Waze or Google Maps). When congestion games meet mobile crowdsourcing, it is critical to incentivize selfish users to explore non-shortest paths in the best exploitation-exploration trade-off. First, we consider a simple but fundamental parallel routing network with one deterministic path and multiple stochastic paths for users with an average arrival probability $\lambda$. We prove that the current myopic routing policy (widely used in Waze and Google Maps) misses both exploration (when strong hazard belief) and exploitation (when weak hazard belief) as compared to the social optimum. Due to the myopic policy's under-exploration, we prove that the caused price of anarchy (PoA) is larger than $\frac{1}{1-\rho^{\frac{1}{\lambda}}}$, which can be arbitrarily large as discount factor $\rho\rightarrow1$. To mitigate such huge efficiency loss, we propose a novel selective information disclosure (SID) mechanism: we only reveal the latest traffic information to users when they intend to over-explore stochastic paths upon arrival, while hiding such information when they want to under-explore. We prove that our mechanism successfully reduces PoA to be less than~$2$. Besides the parallel routing network, we further extend our mechanism and PoA results to any linear path graphs with multiple intermediate nodes.

本研究解决了拥堵游戏中，用户自私行为导致的路由效率低下问题，提出了一种选择性信息披露机制，以优化用户的路径选择和探索。研究发现，在非最短路径的激励机制下，可以显著降低效率损失，提高社会整体福利。该机制的有效性在简单并行路由网络及其扩展模型中均得到了验证。

分析和调节拥堵游戏中的人机交互学习