arXiv:2501.03055cs.GTcs.AI2025-01被引 6

提出新机制提升拥堵游戏中的用户探索效率,降低社会损失。

To Analyze and Regulate Human-in-the-loop Learning for Congestion Games

  • 设计选择性信息披露机制,引导用户平衡探索与利用。
  • 证明现有策略导致的效率损失可无限大,新机制将损失控制在2以内。
  • 适用于导航应用中的实时路径推荐,适合交通优化研究者。

在拥堵博弈中,自私用户倾向于盲目选择最短路径,社会规划者需通过信息或支付激励来调节此类行为。然而,机制设计依赖于动态交通状况,而用户自身需学习并上报过往道路体验(如Waze或Google Maps)。当拥堵博弈结合移动众包时,关键在于激励自私用户以最优权衡探索非最短路径。本文首先考虑一个基础的并行路由网络:一条确定性路径和多条随机路径,用户平均到达率λ。我们证明,当前广泛使用的短路径优先策略在强危险信念下缺乏探索,在弱危险信念下又过度利用,偏离社会最优。由于该策略的探索不足,引发的无效率损失(价格失真,PoA)大于1/(1−ρ^(1/λ)),当折扣因子ρ→1时可无限增大。为缓解此效率损失,我们提出一种选择性信息披露(SID)机制:仅当用户意图过度探索随机路径时才披露最新路况,否则隐藏信息。理论证明该机制可将PoA降至2以下。此外,我们将机制与PoA结果扩展至任意线性路径图(含多个中间节点)。

原文摘要 · Abstract (English)

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 $λ$. 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-ρ^{\frac{1}λ}}\), which can be arbitrarily large as discount factor \(ρ\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.

博弈论交通优化机制设计探索利用

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。