When playing speci c classes of no-regret algorithms (especially, multiplicative updates) in atomic congestion games, some previous convergence analyses were done with a standard Rosenthal potential function in terms of mixed strategy pro les (probability distributions on atomic ows), which may not be convex. In several other works, the convergence analysis was done with a convex potential function in terms of nonatomic ows as an approximation of the Rosenthal one in terms of distributions. It can be seen that though with different techniques, the properties from convexity help there, especially for convergence time. However, it would be always a valid question to ask if convergence can still be guaranteed directly with the Rosenthal potential function, playing mirror descents individually in atomic congestion games. We answer this affirmatively by showing the convergence, individually playing discrete mirror descents with the help of the smoothness property similarly adopted in many previous works for congestion games and Fisher (and some more general) markets and individually playing continuous mirror descents with the separability of regularization functions.
Playing learning algorithms in repeated games has been extensively studied within this
decade, especially with generic no-regret algorithms [
For speci c classes of no-regret algorithms (especially, multiplicative updates), the
analysis in [
However, it would be always a valid question to ask if convergence can still be
guaranteed directly with the Rosenthal potential function, playing mirror descents
individually in atomic congestion games. In this paper, we answer this affirmatively by
showing the convergence using discrete generalized mirror descents with the help of the
smoothness property similarly adopted in [
We need to formally de ne the game and potential function before we proceed. We consider the following atomic congestion game, described by (N; E; (Si)i2N ; (ce)e2E ) is the set of players, E is the set of m edges (resources), Si 2E is the collection of allowed paths (subsets of resources) for player i, and ce is the cost function of edge e, which is a nondecreasing function of the amount of ow on it. Let us assume that there are n players, each player has at most d allowed paths, each path has length at most m, each allowed path of a player intersects at most k allowed paths (including that path itself) of that player, and each player has a ow of amount 1=n to route.
The mixed strategy of each player i is to send her entire ow on a single path, chosen randomly according to some distribution over her allowed paths, which can be represented by a jSij-dimensional vector pi = (pi ) 2Si , where pi 2 [0; 1] is the probability of choosing path . It turns out to be more convenient for us to represent each player's strategy pi by an equivalent form xi = (1=n)pi, where 1=n is the amount of ow each player has. That is, for every i 2 N and 2 Si, we have that xi = (1=n)pi 2 [0; 1=n] and ∑2Si xi = 1=n. Let Ki denote the feasible set of all such xi 2 [0; 1=n]jSij for player i, and let K = K1 ::: Kn, which is the feasible set of all such joint strategy pro les (x1; :::; xn) of the n players.
i is a random subset of resources, and i is a vector ( i)i2N except i. We
consider the following Rosenthal potential function in terms of mixed strategy pro le
p ([
(p) = E i [ i(
i)] + E( i; i)[ci( i)] E i [∑
Ki(e)
∑ ce(j)] + E( i; i)[ci( i)];
e2E j=1
(1)
(2)
where Ki(e) is a random variable de ned as Ke( i) jfj : j ̸= i; e 2 j gj. Let i
have value , which is a strategy for i, with probability pi , and E( i; i)[ci( i)] is
1 There is a tradeoff of an error from the nonlinearity of cost functions if the implication of
reaching approximate equilibria is needed besides the convergence guarantee ([
We consider the following discrete update rule for player i.
pt+1 = arg min f i⟨(cit ) ; zi⟩ + BRi (zi; pit)g i zi2Ki = arg min BRi (zi; pit i∇i (pt))
zi2Ki where the expected individual cost for player i choosing over the randomness from the other players is ci = E i [ci( ; i)] = ∑e2 E i [ce(1 + Ki(e))].
We have the following properties.
E( i; i)[ci( i)] = ∑ pi ci ; = ci ; = ∑ e2 \ ′ The equality in (5) holds because (cit ) = ∇i (pt). Here, i > 0 is some learning rate, Ri : Ki ! R is some regularization function, and BRi ( ; ) is the Bregman divergence with respect to Ri de ned as
BRi (ui; vi) = Ri(ui)
Ri(vi) ⟨∇Ri(vi); ui vi⟩ for ui; vi 2 Ki.
We can ask about the actual convergence of the value of to some minimum and
thus an approximate equilibrium and/or aim for convergence of the mixed strategy
pro le pt. The difficulty to deal with such is that it is not convex. There may be
no way to bound the convergence time, and there can be multiple minima to converge
to. Nevertheless, with the \smoothness" as de ned in [
De nition 1 (Smoothness). We say that is -smooth with respect to (R1; :::; Rn) if for any two inputs p = (p1; :::; pn), p′ = (p′1; :::; p′n) 2 K, (p′) = (p) + ⟨∇ (p); p′ p⟩ + n ∑ BRi (p′i; pi): i=1 Note that
has to be properly set in different games.
The convergence follows from the assumption that for each i, i
1= i, and the implication from the -smoothness condition (7).
Theorem 1. For any t 0, (pt+1) (pt).
1= and thus (3) (4) (5) (6) Continuous Generalized Mirror Descents We consider the case where Ri is a separable function, i.e., it is of the form ∑2Si Ri(ui ). The continuous update rule with respect to BRi ( ; ) is de ned as follows. Let 1 pi(ϵ) = arg min f i⟨(cit ) ; zi⟩ + ϵ BRi (zi; pit)g:
zi2Ki
dpit = lim pi(ϵ)
dt ϵ!0 ϵ
pit :
(7)
(8)
The following claim and the convexity of Ri give the convergence result.
Claim ( lemma 4.2 of [
0, d (pt) dt 0. 4
More challengingly, we can also consider partial-information models with such trickier
potential function . Does the bandit algorithm in [
Another direction is application to the analysis of the average-case price of anarchy
as the application of \pointwise" convergence for the average-case price of anarchy in
[