Cost Design in Atomic Routing Games Yue Yu Shenghui Chen David Fridovich-Keil and Ufuk Topcu Abstract An atomic routing game is a multiplayer game on

2025-04-27 4 0 321.34KB 6 页 10玖币

侵权投诉

Cost Design in Atomic Routing Games

Yue Yu, Shenghui Chen, David Fridovich-Keil, and Ufuk Topcu

Abstract— 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 connect 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 mini-

mize a given smooth performance function. This method ﬁrst

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.

I. INTRODUCTION

A routing game is a multiplayer game on a directed graph

that contains a collection of nodes and links. Each player in

the game chooses a sequence of links, which together form

apath, that connect its origin node to its destination node—

with the lowest cost, where the cost of each link is a function

of all players’ choices of paths. The Nash equilibrium of this

game is a collective path choice where no player can obtain

a lower cost by unilaterally switching to an alternative path.

Routing games are the fundamental mathematical models

for predicting the collective behavior of selﬁsh players in

communication and transportation networks [1], [2], [3], [4],

[5], [6].

Cost design—also known as network design—is the prob-

lem of designing the link cost function of a routing game so

that the Nash equilibrium satisﬁes certain desired properties,

e.g., matching a desired equilibrium pattern or minimizing

the total cost of all players. Cost design is the key to mod-

ifying unwanted trafﬁc patterns in congested transportation

networks [7], [8], [9], [10], [11], [12].

Existing results on cost design are limited to nonatomic

routing games, where the number of players is assumed to be

inﬁnite and each player is a negligible fraction of the entire

player population [5]. Although reasonable for applications

with a large number of players—e.g., predicting the trafﬁc

patterns of thousands of vehicles [6]—such an assumption

is not valid for applications in multi-agent systems with a

medium number of agents, where each player is no longer

negligible compared with the entire player population.

This research is supported in part by NSF 2211548, NSF 1652113, NASA

80NSSC21M0071, and AFRL FA9550-19-1-0169. Y. Yu, S. Chen, and

U. Topcu are with the Oden Institute for Computational Engineering and

Sciences, The University of Texas at Austin, TX, 78712, USA (emails:

yueyu@utexas.edu, shenghui.chen@utexas.edu, utopcu@utexas.edu). D.

Fridovich-Keil is with the Department of Aerospace Engineering and

Engineering Mechanics, The University of Texas at Austin, TX, 78712,

USA (email: dfk@utexas.edu).

We develop a numerical method for cost design in atomic

routing games, where the number of players is ﬁnite and

each player searches for the shortest path in a directed

connected graph. We ﬁrst show that the Nash equilibrium

conditions in atomic routing games are equivalent to a set

of nonsmooth piecewise linear equations. Next, we develop

an approximate projected gradient method to design the link

cost function such that the Nash equilibrium of the game

minimizes a given smooth performance function. In each

iteration, this method ﬁrst approximates the nonsmooth Nash

equilibrium conditions with a set of smooth nonlinear equa-

tions, then updates the link cost function via an approximate

projected gradient method based on implicit differentiation.

We demonstrate the application of this method to atomic

routing games that model noncooperative agents navigating

in grid worlds.

Our results extend a previous cost design method for

matrix games [13] to atomic routing games while remaining

scalable. In particular, the results in [13] require enumerating

all the options of each player. In an atomic routing game, the

number of these options equals the number of all possible

paths for all players, which scales exponentially with the

number of nodes and links of the underlying graph. In

contrast, the proposed method does not require such enu-

meration, and the number of equations needed scales linearly

with the number of nodes and links of the underlying graph.

Notation: We let R,R≥0,R>0, and Ndenote the set of

real, nonnegative real, positive real, and natural numbers, re-

spectively. Given m, n ∈N, we let Rnand Rm×ndenote the

set of n-dimensional real vectors and m×nreal matrices; we

let 1nand Indenote the n-dimensional vector of all 1’s and

the n×nidentity matrix, respectively. Given positive integer

n∈N, we let [n]:={1,2, . . . , n}denote the set of positive

integers less or equal to n. Given x∈Rnand k∈[n], we let

[x]kdenote the k-th element of vector x, and kxkdenote the

`2-norm of x. Given a square real matrix A∈Rn×n, we let

A>,A−1, and A−> denote the transpose, the inverse, and

the transpose of the inverse of matrix A, respectively; we say

A0and A0if Ais symmetric positive semideﬁnite

and symmetric positive deﬁnite, respectively; we let kAkF

denote the Frobenius norm of matrix A. Given continuously

differentiable functions f:Rn→Rand G:Rn→Rm,

we let ∇xf(x)∈Rndenote the gradient of fevaluated at

x∈Rn; the k-th element of ∇xf(x)is ∂f(x)

∂[x]k. Furthermore,

we let ∂xG(x)∈Rm×ndenote the Jacobian of function G

evaluated at x∈Rn; the ij-th element of matrix ∂xG(x)is

∂[G(x)]i

∂[x]j.

arXiv:2210.01221v2 [cs.GT] 18 May 2023

II. ATOMIC ROUTING GAMES AND ITS APPROXIMATION

VIA ENTROPY REGULARIZATION

We ﬁrst introduce the mathematical model for atomic

routing games on a directed graph, followed by a smooth

approximation of the Nash equilibria in atomic routing

games. These results provide the foundation of the cost

design results in the next section.

A. Directed graphs

A directed graph Gcontains a set of nodes [n], a set of

directed links [m]. Each link is an ordered pair of distinct

nodes, where the ﬁrst and second node are the “tail” and

“head” of the link, respectively. We characterize the con-

nection among different nodes in graph Gvia the incidence

matrix, denoted by E∈Rn×m. The entry [E]ij in matrix E

is associated with node iand link jas follows:

[E]ij =









1,if node iis the tail of link j,

−1,if node iis the head of link j,

0,otherwise.

(1)

B. Atomic routing games

Given the incidence matrix E∈Rn×mof a directed graph

G, we consider a game with p∈Nplayers. Player i∈[p]

has an origin node oi∈[n]and a destination node di∈[n]

in graph G. We deﬁne the key components of this game as

follows.

1) Players’ path choices: Each player i∈[p]chooses a

path with the lowest cost that connects its origin node oiand

destination node di. We represent the path chosen by player

ivia a ﬂow vector xi∈Rm, where [xi]k∈[0,1] denotes the

probability for player ito use link kon the path it chooses.

If vector xidenotes a path that connects node oiand di,

then it belongs to certain feasible ﬂow set, which we deﬁne

as follows. Let ri∈Rndenote the origin-destination vector

of player isuch that [ri]j= 1 if j=oi;[ri]j=−1if

j=di; and [ri]j= 0 if j6=oiand j6=di. Furthermore, let

si∈Rn−1denote the reduced origin-destination vector as

si= Γ(ri, di),(2)

where Γ(ri, di)∈Rn−1is vector obtained from vector riby

deleting the di-th element in ri. We also use the notion of

reduced incidence matrix for player i, deﬁned as follows:

Ei:= Γ(E, di),(3)

where Γ(E, di)∈R(n−1)×mis the matrix obtained from

matrix Eby deleting its di-th row.

Equipped with the above notations, we deﬁne the feasible

ﬂow set for player i, denoted by Pi⊂Rm, as

Pi={y∈Rm|Eiy=si, y ≥0}(4)

for all i∈[p]. Notice that if xi∈Piand we let e>

ibe the

di-th row of matrix E, then (1) and (3) together imply that

ixi=1>

nExi−1>

n−1Eixi= 0 −1>

n−1si=−1,(5)

where the second step is due to the fact that 1>

nE= 0m.

Therefore, xi∈Piis and only if Exi=ri. In other words,

xi∈Piif and only if xidenotes a unit ﬂow that originates at

node oi, disappear at node di, and is preserved at any other

node.

2) The Nash equilibrium conditions: We assume the cost

of each link is a quadratic function of all players’ ﬂow

vectors, and each player chooses a path that minimizes this

quadratic function. In other words, each player ichooses its

ﬂow vector xias follows:

xi∈argmin

y∈Pibi+1

2Ciiy+Pj6=iCij xj>y, (6)

where vector bi∈Rmdeﬁnes the nominal link cost, which is

independent of the players’ strategies; matrices Cij ∈Rm×m

for all i, j ∈[p]are matrices such that vector Cij xj∈Rm

denotes the link cost for player idue to its interaction with

player j. Here we assume that the link cost is a linear

function—rather than general polynomials—of the players’

ﬂow vectors to simplify our further computation.

We introduce the notion of Nash equilibrium in an atomic

routing game as follows

Deﬁnition 1. A joint ﬂow x:=x>

1. . . x>

p>is a Nash

equilibrium if (6) holds for all i∈[p].

C. Computing Nash equilibria via nonlinear programming

We now discuss how to compute the Nash equilibrium in

Deﬁnition 1. To this end, we denote the joint ﬂow of all

players as

x:=x>

1x>

2· · · x>

p>.(7)

We also use the following notation:

C:=



C11 C12 ... C1p

C21 C22 ... C2p

.....

Cp1Cp2... Cpp



, b :=





, s :=





,

E[1,p]:= blkdiag(E1, E2, . . . , Ep),

(8)

where E[1,p]= blkdiag(E1, E2, . . . , En)is the block diag-

onal matrix obtained by aligning matrices E1, E2, . . . , Ep

along the diagonal of matrix E[1,p].

The following lemma shows how to compute the Nash

equilibrium in Deﬁnition 1 by solving a set of piecewise

linear equations.

Lemma 1. Suppose that set Piis nonempty and Cii =C>

ii 

0for all i∈[p]. Then (6) holds for all i∈[p]if and only if

one of the two following set of conditions holds.

1) There exists v∈Rp(n−1) and u∈Rpm such that

s=E[1,p]x, (9a)

u=b+Cx −E>

[1,p]v, u>x= 0, x, u ≥0pm.(9b)

2) There exists v∈Rp(n−1) such that

s=E[1,p]x, (10a)

0pm = min{x, b +Cx −E>

[1,p]v}.(10b)

Proof. We start with the conditions in (9). Since Cii =

ii 0, and set Piis nonempty and described by linear

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

CostDesigninAtomicRoutingGamesYueYu,ShenghuiChen,DavidFridovich-Keil,andUfukTopcuAbstractAnatomicroutinggameisamultiplayergameonadirectedgraph.Eachplayerinthegamechoosesapathasequenceoflinksthatconnectitsoriginnodetoitsdestinationnodewiththelowestcost,wherethecostofeachlinkisafunctionofallplayers...

展开>> 收起<<

Cost Design in Atomic Routing Games Yue Yu Shenghui Chen David Fridovich-Keil and Ufuk Topcu Abstract An atomic routing game is a multiplayer game on.pdf

共6页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Cost Design in Atomic Routing Games Yue Yu Shenghui Chen David Fridovich-Keil and Ufuk Topcu Abstract An atomic routing game is a multiplayer game on

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: