An atomic routing game is a multiplayer game on a directed graph. Each player in the game chooses a path -- a sequence of links that connects its origin node to its destination node -- with the lowest cost, where the cost of each link is a function of all players' choices. We develop a novel numerical method to design the link cost function in atomic routing games such that the players' choices at the Nash equilibrium minimize a given smooth performance function. This method first approximates the nonsmooth Nash equilibrium conditions with smooth ones, then iteratively improves the link cost function via implicit differentiation. We demonstrate the application of this method to atomic routing games that model noncooperative agents navigating in grid worlds.
翻译:原子路由游戏是定向图形上的多玩游戏。 游戏中的每个玩家选择一条路径 -- -- 一条连接其起源节点与目的地节点的链接序列 -- -- 费用最低, 每个链接的成本是所有玩家选择的函数。 我们开发了一种新的数字方法来设计原子路由游戏中的链接成本函数, 使玩家在纳什平衡上的选择能够将给定的平稳性能功能最小化。 这个方法首先将非摩特的纳什平衡条件与平滑的功能相近, 然后通过隐含的区分来迭接地改进连接成本函数。 我们演示了这种方法在原子路由游戏中的应用, 以模拟不合作的代理人在网格世界中航行。