Learning Optimal Tax Design in Nonatomic Congestion Games
Authors: Qiwen Cui
Maryam Fazel
Simon Shaolei Du
Venue: NeurIPS 2024 poster (2024)
Keywords: game theory; congestion games; mechanism design; equilibrium feedback
Primary area: algorithmic_game_theory
TL;DR: We propose the first algorithm for learning optimal tax in nonatomic congestion games with equilibrium feedback.

Abstract: In multiplayer games, self-interested behavior among the players can harm the social welfare. Tax mechanisms are a common method to alleviate this issue and induce socially optimal behavior. In this work, we take the initial step of learning the optimal tax that can maximize social welfare with limited feedback in congestion games. We propose a new type of feedback named \emph{equilibrium feedback}, where the tax designer can only observe the Nash equilibrium after deploying a tax plan. Existing algorithms are not applicable due to the exponentially large tax function space, nonexistence of the gradient, and nonconvexity of the objective. To tackle these challenges, we design a computationally efficient algorithm that leverages several novel components: (1) a piece-wise linear tax to approximate the optimal tax; (2) extra linear terms to guarantee a strongly convex potential function; (3) an efficient subroutine to find the exploratory tax that can provide critical information about the game. The algorithm can find an $\epsilon$-optimal tax with $O(\beta F^2/\epsilon)$ sample complexity, where $\beta$ is the smoothness of the cost function and $F$ is the number of facilities.

Learning Optimal Tax Design in Nonatomic Congestion Games
Qiwen Cui
Maryam Fazel Department of Electrical Computer Engineering University of Washington Seattle, WA 98195
Paul G. Allen School of Computer Science
Engineering University of Washington Seattle, WA 98195 qucui@cs. wastinwwsshinnnoonomm edu
mf mfaeel @uw edu
Simon S. Du
Paul G. Allen School of Computer Science Engineering University Washington
Seattle, WA 98195
ssdu@cs. www.::ssswwaainntoococo edu
Abstract
In multiplayer games, self-interested behavior among the players can harm the social welfare. Tax mechanisms are a common method to alleviate this issue and induce socially optimal behavior. learning the optimal tax that can maximize social welfare with limited feedback in congestion games. We propose a new type of feedback named equilibrium feedback, where the tax designer can only observe the Nash equilibrium after deploying tax plan. Existing algorithms are not applicable due to the exponentially large tax function space, nonexistence of the gradient, and nonconvexity of the objective. To tackle these challenges, we design a computationally efficient algorithm that leverages several novel components: (1) a piece-wise linear tax to approximate the optimal tax; (2) extra linear terms to guarantee strongly convex potential function; (3) efficient subroutine find the exploratory
this work, we take the initial step of
that provide critical information about the game. The algorithm can find an 6-optimal tax with FBF22e /e) sample complexity, where 3 the smoothness of the cost function and F' is the number of facilities.
Introduction
In modern society, large-scale systems often consist of many self-interested players with shared resources, such transportation and communication networks. Importantly, the objectives of individual players are not always aligned with the system efficiency, and the system designer should take this into consideration. A widely known example is Braess's paradox, where adding to network can make the network more congested [Braess] 1968). Price anarchy a notion that measures the inefficiency caused by selfish behavior compared with optimal centralized behavior Koutsoupias and Papadimitriou 1999]. Characterizing such inefficiency has been an active research area with applications in resource allocation [Marden and Roughgarden 2014], traffic congestion (Roughgarden and Tardos 2004), and others. The inefficiency motivates research on how to design mechanisms improve performance even when the players are still behaving selfishly.
roads
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Tax mechanisms are standard approach to resolving the inefficiency issue, which are widely studied in economics, operations research, and game theory. The goal of tax mechanisms is to incentivize self-interested players to follow socially optimal behavior by applying tax/subsidy. Congestion game widely studied class of game theory models characterizing the interactions between players sharing facilities, where the cost of each facility depends on the "congestion" level [Wardrop] 1952 Rosenthal, 1973). As a motivating example, in traffic routing games, each facility corresponds to an edge in network, and each player chooses path that connects her source node and target node. The cost of each facility corresponds to the latency of each edge, which depends on the number of players using that edge. Then, the tax can be interpreted the toll collected by the road owner the government to improve overall traffic efficiency [Bergendorff et al. 1997].
Most existing works on congestion game tax design focus on the computation complexity of the optimal tax (Nisan et al. 2007 Caragiannis et al. 2010). They assume the tax designer has full knowledge of the underlying game, which is unrealistic in many applications. As Nash equilibrium is the only stable state of the system, we study partial information feedhack setting named "equilibrium feedback", where the tax designer can only observe information about the Nash equilibrium. The limited feedback information brings new challenges to the tax designer, and strategic exploration is necessary to learn design the optimal tax. In this work, we aim to take the first step in learning optimal tax design for congestion games, and we study the following problem:
How can we learn the optimal tax design in congestion games with equilibrium
Below we highlight our contributions.
1.1 Main Contributions and Technical Novelties
1. The first algorithm for learning optimal tax design in congestion games. To the best of our knowledge, this is the first result for learning optimal tax in congestion games with partial information feedback. Our algorithm enjoys O 3/c) sample complexity for learning an e-optimal tax, where F is the number of facilities and / is the smoothness coefficient of the cost function. The sample complexity has no dependence on the number of actions, which could be exponential in F. In addition, we provide an efficient implementation for network congestion games with (poly(VV. E, c)) computational complexity, where V and E are the numbers of the vertexes and edges in the network. Due to space limitation, we defer the computation analysis and experiments to Appendix [[add Appendix [
2. Piece-wise línear function approximation. We only assume the cost functions smooth and make no parameterization assumptions as they are too strong to be satisfied in real-world applications. To tackle this challenge, we use piece-wise linear functions approximate the optimal tax function. While only the values of the cost functions can be observed, we show that a carefully designed piece-wise linear function can approximate the unobservable optimal tax function well.
3. Strongly convex potential function. One challenge in tax design is controlling the sensitivity of Nash equilibrium w.r.t. tax perturbation. We always enforce tax functions with subgradient lower bounded by some positive value, which leads to a strongly convex potential function. As a result, the Nash equilibrium will be unique and Lipschitz with respect to tax perturbation. As the potential function for optimal tax is not necessarily strongly convex, we carefully choose the strong-convexity coefficient to balance the induced bias.
4. Exploratory tax design. Given the equilibrium feedback, the tax designer can only indirectly query the cost function by applying tax. Consequently, exploration in tax design becomes much more difficult than that in standard bandit problems where the player can directly query the value of an action [Lattimore and Szepesvári 2020). We design an exploratory tax that pushes the equilibrium to the "boundary", where an additional tax perturbation will change the equilibrium and reveal information about at least one unknown facility.
In this work, we focus on the well-known nonatomic congestion games. We hope our algorithm and analysis provide new insight on the intriguing structure of nonatomic congestion games. In addition, the tax design algorithm might find applications in real-world problems such as toll design in traffic networks. Due to space limitation, most proofs are deferred to the appendix.

---

Notations. [m] = {1.2, ... m.]. For set of real numbers K. and real number : min(X) - S max we define [ == min and [τ] := maxyeK.ys
The clip operation clip(a, (,)) == [inx ( |) r} clips a into the interval [4,r]. We use O(+) to hide absolute constants and Ō()) to hide polylog terms as well. A function f X + R is a-strongly convex f(v) 2 f(z) + Vx())" (y- x) + 1 Vx, y E X. f 8-smooth if [ VV (t)lll S
|| vlla Va,y X.
2 Related Work
Learning in congestion games. We refer the readers to the textbook [Nisan et al. 2007 for general introduction to congestion games, the price of anarchy and tax mechanisms. Nonatomic congestion games were first studied in [Pggou 1912] and formalized by [Wardrop 1952]. Atomic congestion games were introduced by Rosenthal 1973 and the connection with potential games is developed by [Monderer and Shapley 1996]. In contrast general-sum games without structures, (approximate) Nash equilibrium can be computed efficiently in congestion games due to the existence of the potential function. Recently, various algorithms are developed to learn the Nash equilibrium in congestion games with different feedback oracles [Krichene et al. 2015 Chen and Lu 2016 Cui
et al. 2022 Tiang et al., [022 Panageas al. [2023] Dong et al.] 2023] Dadi et al., [024]. T These algorithms are derived from the perspective of the players in the system, while our algorithm is
essentially different in that is utilized by the system designer to induce better equilibrium.
Optimal tax design in congestion games. For nonatomic congestion games, optimal tax design has closed-form solution known the marginal cost mechanism [Nisan et al. 2007]] For atomic congestion games, the marginal cost mechanism can no longer improve the efficiency [Paccagnan
al. 202T]. Instead, other mechanisms are proposed for optimal local/global and congestion
dependent/independent tax in atomic congestion games [Caragiannis et al., 2010 [ilō and Vinci 2019 Paccagnan et al. 2021]] Paccagnan and Gairing | et al.) [015] Notably, all of these mechanisms assume full knowledge of the game while we consider learning with partial information feedback.
Stackelberg games. Stackelberg game (Von Stackelberg. 2010 models the interactions between leaders and followers such that leaders take actions first and the followers make decisions after observing leaders' actions. Tax design can be formulated as a Stackelberg game where the designer the leader and the game players are the followers. Equipped with a best response oracle to predict followers' actions, Letchford et al. (2009), Blum et al. [2014), Peng et al. [2019] propose algorithms for learning Stackelberg equilibrium. Recently, Bai et al. [2021). Zhong et al. [2021] Zhao et al. 2023) generalize these results to learning Skackelberg equilibrium with bandit feedback, under finite actions or linear function approximation assumptions. For tax design, the search space is an exponentially large function space with complicated dependence the objective. Consequently, existing results for Stackelberg games become vacuous when specialized to our problem.
Mathematical programming under equilibrium constraint. Tax design can be formulated as minimizing social cost with respect to tax under the constraint that players are following the
equilibrium. This is known mathematical programs with equilibrium constraints (MPEC). MPEC a bilevel optimization problem and is NP-hard in general [Luo et al.) 1996). Existing approaches use specific inner loop algorithms approach the equilibrium
that the gradient can be propagated to the outer loop [Li et al. 2020 Liu et al. 2022 Li et al., 2022 Maheshwari et 2003 Li ct al. 2023 Grontas al. 2024] relying on unique and differentiable equilibrium [Colson et al. 2007] However, such an approach requires many strong assumptions, such as the tax designer can control the algorithm of the agents, convex objective function and parameterized tax function. In contrast,
our results make none of these assumptions.
3 Preliminaries
Nonatomic congestion games. A weighted nonatomic congestion game (congestion game) is deseribed by the tuple (Fm) CF), where F is the set of facilities with cardinality F, m is the number of commodities, A, is the action set for commodity E [m]. w, [0, 1] is the weight for
3

---

commodity i E [m] such that Exem) w; 1, and cy :0,,
[0,1]
[0, is the cost function for facility
I E F. Each commodity consists of infinite number of infinitesimal players with total load to be wi Each individual player self-interested and has a negligible effect on the game.
In congestion games, action E A,, i E [ma] is a subset of F, i.e. C F.F which denotes the facilities utilized by action a. For commodity i E [mm], we use strategy T = (ar,a)aEA E [0, wgJl-A.l with constraint EaeA, Fi,a wy to denote how the load distributed over all the actions. The joint strategy for the game is represented by = (I1. 22, 11 Fm) E [0, 1]A, where = -iE((m] |A:]-
We use X' to denote the set of all feasible strategies.
A decentralized perspective of strategy 2; for commodity i is that each self-interested infinitesimal player follows a randomized strategy that chooses a E A, with probability proportional to Ti With the law of large number, the load on action would be Ti,e-
Cost function. For a strategy x, the cost of a facility ()((x())), where 1y(x) Eielm]] EeEAnfea Via is the load on facility J. The cost of an action is the sum of the facility cost that a utilizes: (x) Eyea ()(1)(x)).
We make the following assumption on the cost function. Monotonicity is a standard congestion game assumption, which also observed many real-world applications as more players sharing one facility, each player will have less gain or more cost [Nisan et al. 2007]. Smoothness is a standard technical assumption for analysis.
Assumption 1. We assume the cost function satisfies:
1. Monotonicity: cf(-) is non-decreasing for all f E F,
2. Smoothness: cf(-) is B-smooth for all E F.
Nash equilibrium. Nash equilibrium in nonatomic congestion games, also known as the Wardrop cquilibrium [Wardrop 1952]. is the strategy that no player has the incentive to deviate from its strategy as formalized Definition] I In other words, Nash equilibrium is stable state for a system with selfish players.
Definition 1. A Nash equilibrium strategy x is a joint strategy such that each player is choosing the best action: for any commodity i [m]] and actions a, a' Ai, we have
ca(x) car(2)) if Tiaa > 0.
Similarly, an e-approximate Nash equilibrium a satisfies that
Vi [m], a. E Ar, cx()) S ca (x) + e, vtaa > O.
For strategy x and commodity i, actions E A, such that Fi,a > 0 are named the "in-support" actions and the others are "off-support" actions. For a Nash equilibrium, in-support actions must all have the same cost and off-support actions are no better than in-support actions. is well known that Nash equilibrium always exists in congestion games [Beckmann et al. 1956).
Potential Function.
An important concept in congestion games is the potential function:
(x) = Σ (a)
of (u)du.
If Assumption I is satisfied, then (2x) a convex function and Nash equilibrium equivalent the minimizer of the potential function [Beckmann et al. 1956].
Network congestion games. Network congestion games are congestion games with multicommod- ity network structure, which are also known as the selfish routing games (Roughgarden) [005]. A multicommodity network described by a directed graph (V,E) where V is the vertex set and the edge (facility) set. In addition, each commodity E [m]] corresponds to pair of source and target vertex (8; 42), and actions are all feasible paths connecting 8; and 1,, Fach edge associated with a nondecreasing cost (latency) function.

---

Tax Design for Congestion Games
In this section, we introduce tax design in congestion games. Before we get into the details, we will first introduce notions to simplify the problem.
4.1 Polytope Description for Congestion Games
For strategy 2; RlA: the dimension |A; can be as large 2F. Instead, it would be convenient to consider the facility load yi E IR such that Vi,f - -aeAA:Ea Vi,e- In addition, we define y - [e]m Ur E IR to be the total facility load. We (+))() to denote the reparameterization mapping:
<(z) v. yc, vi [m].
and we set y { E R 3x E x } to be the set of all feasible loads. Note that ø not necessarily a bijection, i.e., there could exist multiple strategies sharing the same load. We use 6 (y) == {ir E X' : ((x) y to denote the set of strategies that are mapped to load y. The potential function can be defined after the repameterization as well:
(repa = _[ ys
cy(u)du = VE
Importantly, drep"(y) (y) does not depend on the choice of strategy x E (z). For the reparameterized potential function, we have the following lemma showing that it is almost equivalent the original potential function. When it is clear from the context, we will simplify Treps as T.
Lemma 1. dreps is convex under Assumption
If y" argmin, Trepa then for any x
x- (y"), is Nash equilibrium.
For any Nash equilibrium strategy we call (xx) the Nash equilibrium load (Nash load).
4.2 Optimal Tax for Congestion Games
Nash equilibrium is stable state for system with self-interested players, as no player has the incentive to deviate unilaterally. However, Nash equilibrium does not efficiently utilize the facilities, which is measured by the social cost:
(V)) Σ yree(yr))
Price of anarchy is concept that measures the efficiency of selfish agents in a system, defined as the ratio between the worst-case social cost for equilibria and the optimal social cost:
PoA maXy is Nash equilihrium load (v)
min V (Vy
For example, in nonatomic congestion games with polynomial cost functions, the price of anarchy grows as ((d/ dn) where is the degree the polynomials [Nisan et al. 2007].
To reduce the price of anarchy, one standard approach is to enforce tax each facility to change the behavior of the self-interested players. Formally, a taxed congestion game is described by
(F, Amm) [I[m] Cr, TF) with an additional tax function Ty [0, 1] - R on facility f E F. The cost of facility ff with load u under tax becomes (u) + (u). Correspondingly, we define the potential function with 7 as
ক ( ((:;))== == l
_| (cr(u) (u)) du,
and the Nash load would satisfy y" argminn p(y: T).
The optimal tax is defined as the tax that can induce optimal social behavior for self-interested players. We want to note that tax is not included in social cost following the convention in tax design.
5

---

Protocol Online Tax Design for Congestion Games
Initialize: Facility set F. for t= 1,2, do Designer chooses tax T². Designer observes Nash load y' argmin (y:: and Nash cost cf [cy(1)))se for f F. end for
Definition lax an optimal tax if all Nash equilibria under tax T can minimize the social cost:
argmin (g: S argmin (y).
yEY
NEY
In addition, a tax T is an e-optimal tax if we have
V (v)
min (b') e, Vy E argmin :T)":T). y'Ey
y"Ey
The marginal cost is defined
+" :4)
As (yy; r*) (y), the Nash equilibrium under tax will minimize the social cost and r* an optimal tax [Nisan et al. 2007). We will make the following assumption so that the cost combined with tax e + 7" is still non-decreasing. In many real world problems, (() is non-decreasing due to the law of diminishing marginal utility, which guarantees Assumption 2
Assumption 2. Marginal cost tax 7 (u) = uc'y (u) is non-decreasing for all f e F.
4.3 Tax Design for Congestion Games
In this paper, we consider the case where the system designer (e.g. government) wants to enforce an (approximate) optimal tax to induce optimal social behavior and maximize social welfare. However, the cost function is unknown so the optimal tax function cannot be computed directly via the marginal cost mechanism. On the other hand, the designer enforce several taxes and observe the feedback. As Nash equilibrium is the stable state of the system, we assume the designer can observe the equilibrium feedback.
Formally, tax design is formulated as an online learning problem as shown in Protocol I At round t, the designer can choose tax 7¹ and observe the corresponding Nash equilibrium load y R and Nash equilibrium cost c' RF. The sample complexity of a tax design algorithm is the number of rounds for designing e-optimal tax.
naive approach is the designer first enumerates all of the c-approximations of and chooses the with minimal social cost. However, such an approach would require ((1/e))F samples as the complexity of using piece-wise linear function to approximate T (a B-smooth function) with error ((1)e)//)) resulting exponential dependence on the parameters 1/c and F.
Another approach is applying algorithms for mathematical programming under equilibrium con- straints. Specifically, we can formulate tax design solving
min (y(()), s.t. y()) = argmin (y;
yEy
However, v()) can be non-differentiable or even discontinuous w.r.t. т, and (y((T) can non- convex w.r.t. (Lemma 5). As a result, previous results do not apply to our problem as they apply gradient-based methods and make convexity assumptions [Li et al. 2020 Liu al. 2022].
Learning Optimal Tax in Nonatomic Congestion Games
In this section, we describe our algorithm that can learn e-optimal tax with O(F²3/e) samples. First, we introduce piece-wise linear functions as a nonparametric way to approximate the marginal cost tax r* Takezawa 2005).

---

Definition 3. (Piece-wise Linear Function) We use dictionar d = (1). (I Vo) for I; o 2z. Vi + j (w.lo.g. we let 2 on [n) such that
<
22 znd represent piece-wise linear function d(-)
2i+1
24 Vi+1, VI T++1l.
d(x)
+
34
1++1
I2 2i+1
In addition, we U to represent the update method for dictionary. Lee, d Uar, u) is the piece-wise linear function interpolating one more point (x, y) if (x. d(x)) is not already in d, otherwise it will update d(z) to y.
We will maintain the piece-wise function on a grid L = A,,,, ..... and A = 1/K. The time complexity for computing d(x) is O(log K) for any a E [0,1].
KA = 1 with K = 28
5.1
Main Algorithm
Algorithm Tax Design for Congestion Game
1: Initialize: Facility set F, number of rounds T, tolerance 6, smoothness 3, perturbation á <A//8.
2: Set initial tax -² T] = (1,33 for all f E F. Set k} to be {0} for all f E F.
3: for = 1, 2,,..... do
4: Observe Nash load y E I2 and Nash cost cf R under tax T'.
5: F to be the unknown facility set (Definition 4
6:
Set = + c(y wyjke) ) and ry () ( + <uy
( for
each f F.
7:
Run Algorithm with input y', c', 7' [r)(0)))s, F and [1,r,)
8:
if Algorithm
2
return False then
9:
return
10:
else
Algorithm return 7 RF, f sign E 1-1.1).
12:
Apply tax +" : + U(6 sign and tj tj ()) for f f F
13:
Observe ji',²' e E IR as the Nash load and the Nash cost of each facility.
14:
Update Te+1 and K2+1 according to [
15:
end if
end for
In this section, we introduce our main algorithm. At each round t, we will maintain a known index set K2 S L where the marginal cost tax can be accurately estimated (Lemma 7. and use piece-wise linear function to approximate the tax function by interpolating the values at the known indexes. The piece-wise linear function takes the form of ((x), v/)); ): and the known index set KG satisfies { K Uf1} and K2 C C. Here 1 is special case it is not in the known index set initially but is needed as the boundary for the piece-wise linear function Tÿ. Initially, the tax set to be TJ (w) = ((0,0), 0), (1, +
}}} and the auxiliary tax is f {0, 0), (1, for f E F (Line Z Here set (1) f as 3 is always an upper bound on r7 (1). The auxiliary tax f/. is non non-decreasing
piece-wice linear approximation of r and we always set tax (f) (u) eu ensure that the subgradient of the tax enforeed is lower bounded by
At round f, after observing Nash equilibrium load y² E F and Nash equilibrium cost cl R.F. the facilities are split into two sets: known facilities and unknown facilities.
Definition 4. For each round t, facility f known if the Nash load y E [0. 1] satisfies W/l KG and W E KtJ. Otherwise,
f is unknown for round t.
For a known facility f. the Nash load is either in the known index set or sandwiched by two consecutive known indexes. As result, the tax estimate for the Nash load 7f (w/)) will be close to the
"In this dictionary, key is æ; and value is ys. For readers unfamiliar with the dictionary data structure, it can be regarded as set with special update operation.
7

---

true optimal tax 77f))) with enror 2e (Lemma 8b. We will apply Algorithm 2 to find the exploratory tax to gather information about unknown facilities (Line
Proposition 1. If Algorithmm return False at round t, then tax is an ooF-mptimal tax. If Algorithm
2 output 7.J" sign' at round t, then we have
0 < U/. SA SA.
If Algorithm 2 output F*, sign' at round 6, we update the and the known index set by the following rule. For u E (1/.le. byylekk Ky (this set not empty as I² is an unknown facility), we set
sj -
ct. 7. bt
3 - cl,pp
- (...ll...... ) 7. un)))).
(1)
3 = U(u..
and p++1 E [0.
Fy. x = K'' for f # pr. Then we set Tf (u) = (u) + eu for all f E and
In words, clip the two-point estimate o the left and right known index of 7j. (u) so 07. 8/
that
7 Fft1 (u) is still non-decreasing piece-wise linear approximation of the marginal cost tax 7
++1 added with extra linear term to guarantee a strongly convex potential function (Lemma 2
Tf
As < 53 i/ < A, the two point estimate of the gradient is accurate enough for ey (1)
such that 7 (u) Ty (w) < (Lemma
As IC ft will output False within at most O(F3/e) rounds, which implies 7' is an e Fooptimal tax (Proposition
increases by 1 at round t and there are F such sets with size bounded by O(3/e), Algorithm 2
D. With proper rescaling, the sample complexity for learning e-optimal tax is ((F33/e).
Theorem 1. Under Assumption | and Assumption 2 Algorithum 7 will output GeF tax within < 2/B/E rounds. In addition, each round has at most two tax realizations.
Remark 1. uniformly approximate a B-smooth function, we have to know its value at O(Bee) points Takezawa 2005|. For an e-optimal tax, we need to estimate T with F accuracy as the error accumulates with all the facilities. As result, we conjecture that ((F2B/e) sample complexity is light and we leave the lower bound to future work.
Remark 2. Our algorithm can be easily adapted to the case where we have feedback other than only the equilibrium feedback. Specifically, when the tax designer obtain con-equilibrium feedback, she can still update the optimal tax estimate if the feedback provides new information. is possible for our algorithm to find the optimal tax even if no equilibrium feedback is provided. In addition, long as the equälibrium can be reached after applying a tax, the algorithm can always find the optimal tax.
5.2 Subroutine for Finding Exploratory Tax
In this section, we describe Algorithm 2 which can find exploratory tax that satisfies Proposition I The idea is we can observe another similar but different Nash equilibrium load by perturbing the tax. However, there two challenges:
1. Perturbing the tax might change the Nash equilibrium load drastically.
2. Perturbing the tax might not change the Nash equilibrium load at all.
To resolve the first issue, always apply taxes that have (sub)gradient lower bounded by >> 0. The feasible range [4,, for updating tax 7/ with (v) guarantees that the updated tax still maintains the subgradient lower bound. By Lemma 2 the potential function always e-strongly convex. result, the Nash load for any feasible tax is unique and Lipschitz w.r.t. tax perturbation. To resolve
8

---

Algorithm 2 Test Tax Design
1: Initialize: Nash flow y E IRF, facility range [y for f F.
RR, cost RRF, unknown facility set F, unknown
2: Set strategy E & (v). Compute commodity load = ox(x;) E Rf for [m]]
3: Set - False.
4: if Exists / E F and i E [m]] such that 0 < yi(s) < wy then
5: return 1.
6: end if
7: for Commodity E [m] do
8: Let F; = {f E F: Ea:feo Ria wi} and Fi (f EEEsfa Fi,a 0}.
9: S F3, = =TA, T.: (pp TA(FUFD = -FNBUUF
10: if Gap, (z, c c F) then
Set = True. 12: break
11:
13: end
14: end for
15: if False then
return False. 17: end if
18: Set s'tr'=9
19: for
E do
Set 7M 7 = u, Fun Tim
21:
Set u = argmax :u Gap,(r,c+77) 2 20]
22:
if u ry then
23:
return 111. 24: end if
25:
Set
end for
27:
for
f F do
28:
Set 7M 7 u, Fun T
29:
Set u = argmin u (x, 2,
30:
if u I then
31:
return 7". 1
32:
end if
33:
S'
end for
the second issue, we find the tax that makes the current Nash equilibrium on the "boundary". I.c.. an additional perturbation will make the Nash equilibrium change. Intuitively, this is similar to removing the slackness in a constrained optimization problem. By Lemma we can observe different Nash load on f if we make the additional perturbation.
Lemma 2. If the subgradient of the cost function oj is lower bounded by > 0 for all f E F, then the potential function drepa (y) e-strongly convex. However, (xx) is not necessarily strongly convex.
Lemma 3. If two taxes 7 and è only differ in facility f and the Nash loads and ÿ are different, then Vf + Uy- Definition 5. The gap for strategy x E X' with
RF is defined as
Gap,(
min
Σeg fifEa
max
Σ Cg.
ai
fifea
In the algorithm, we use Gap,(r, c) to measure the cost gap between in-support actions and off- support actions for commodity and strategy æ. ar a Nash equilibrium and is the Nash cost, then all of the in-support actions have the same minimal cost and (2, 2 0 holds. Informally, "boundary" tax T means that Gap, ( = for Nash equilibrium and perturbing T results in (a, 7) 0, so the Nash equilibrium under the perturbed tax will be different from ar

---

Now we discuss how Algorithm22) S finds the "boundary" tax in detail. The input to the algorithm is the Nash flow y, the Nash cost c, the Nash tax т, the unknown facility set F and the feasible tax range [1, Vyl for each unknown facility f E F. We emphasize that here the Nash cost/tax are the values of the cost/tax function on the Nash load and they are vectors in R instead of functions. [1,, ryl is the feasible range for the perturbed tax value facility f. By the definition of l and ry, current tax rj updated with (0/y u), E [4g.ry ry is still a tax with subgradient lower bounded by e.
For the first step, the algorithm will compute strategy x E (b) as the Nash equilibrium strategy (Line 2). If there exists an unknown facility J and commodity such that not all load of commodity i is using / or not using I (Line D then perturbing the tax at facility I will make x not longer a Nash equilibrium in-support actions have different costs.
Otherwise, for each unknown facility ff and commodity i, either all of the load is using f or all of the load is not using f. As a result, in-support actions always have the same cost after perturbing the tax. For the next step, we verify if there exists a tax within the feasible ranges for unknown facilities that makes not a Nash equilibrium. However, there does not exist universal worst-case tax that can verify if x is always a Nash equilibrium or not.
Fortunately, the worst-case tax has a closed form for each commodity separately: the taxes for facilities used by all of the Nash load would be the upper bound ry and the taxes for facilities used by none of the Nash load would be the lower bound 1,. thus maximizing the cost for in-support actions and minimizing the cost for sup-rt actions (Line 9). For each commodity i, we apply the corresponding worst-case tax and check if the in-support actions are still the optimal actions (Line 10.. If for all commodities, the in-support actions are optimal under the worst-case tax, then for any tax within the feasible range, y is the Nash load and the algorithm will output False (Line As r is approximately within the range, yf approximately minimizes the social cost (Lemma 10).
Otherwise, the algorithm finds commodity i such that x is not the Nash equilibrium under the worst- case tax (Line IT). For the last step, we gradually transform the initial tax to this worst-case tax and stop when æ is not the Nash equilibrium for some commodity. Specifically, the algorithm iteratively changes the tax in the unknown facility set f = F, F (Line 19 and Line 27 to the worst-case tax.
For facility f E Fr the algorithm finds the boundary tax for facility f that satisfies argmax(u u: G2, F") 2 0, Vj [m]].
u S ry. we will output 1. 1. By the definition of u. if we further increase u, one of the gaps will become negative and x is no longer the Nash equilibrium. Otherwise, all feasible taxes for f have a nonnegative gap for all commodities, which means x still the Nash equilibrium, and we continue for the next facility. After enumerating all the facilities in F, we enumerate Fi in the same way. Eventually, the tax transformed into the worst-case tax with negative gap for commodity i, so this process will end and output J sign such that 7" is the tax that makes the Nash equilibrium on the boundary, f the facility to perturb and sign the direction to perturb the tax at f.
6 Conclusion
We proposed the first algorithm with polynomial sample complexity for learning optimal tax in nonatomic congestion games. The algorithm leverages several novel designs exploit the special structure of congestion games, which can also be implemented efficiently. Below we list a few potential future research directions:
1. Relaxing the Nash equilibrium assumption to players following no-regret dynamics or quantal response equilibrium.
2. Design algorithms that do not require prior knowledge of the smoothess coefficient.
3. Generalize the algorithm to atomic congestion games.
7 Acknowledgement
SSD acknowledges the support of NSF IIS 2110170. NSF DMS 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF CCF 2019844, and NSF IIS 2229881. MF acknowledges the support of NSF awards CCF 2007036, TRIPODS II DMS 2023166, CCF 2212261, and CCF-AF 2312775.
10

---

References
Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong. Sample-cfficient learning of stackelberg equilibria in general-sum games. Advances in Neural Information Processing Systems, 34:25799-25811 2021.
Martin Beckmann, Charles B McGuire, and Christopher B Winsten. Studies the economics of transportation. Technical report, 1956.
Pia Bergendorff, Donald W Hearn, and Motakuri V Ramana. Congestion toll pricing of traffic networks. Springer, 1997.
Vittorio Bild and Cosimo Vinci. Dynamic taxes for polynomial congestion games. ACM Transactions on Economics and Computation (TEAC), 7(3):1-36, 2019.
Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Learning optimal commitment to overcome insecurity. Advances in Neural Information Processing Systems, 27, 2014.
Dietrich Braess. Über ein paradoxon aus der verkehrsplanung. Unternehhmensforschwnn, 12:258-266 1968.
Ioannis Caragiannis, Christos Kaklamanis, and Panagiotis Kanellopoulos, Taxes for linear atomic congestion games, ACM Transactions on Algorithms (TALG). 7(1):1-31, 2010.
Po-An Chen and Chi-Jen Lu. Generalized mirror descents in congestion games. Artificial Intelligence, 241:217-243, 2016.
Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. Journal of the ACM (JACM), 68(1):1-39, 2021.
Benoit Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153:235-256, 2007.
Qiwen Cui, Zhihan Xiong, Maryam Fazel, and Simon S Du Learning in congestion games with bandit feedback. Advances in Neural Information Processing Systems, 35: 1009-11002.., 2022.
Leello Dadi, Ioannis Panageas, Stratis Skoulakis, Luca Viano, and Volkan Cevher. Polynomial convergence of bandit no-regret dynamics in congestion games. arXiv preprint arXiv:2401.09623 2024.
Jing Dong, Jingyu Wu, Siwei Wang, Baoxiang Wang, and Wei Chen. Taming the exponential action set: Sublinear regret and fast convergence to nash equilibrium in online congestion games. arXiv preprint arXiv:2306.13677 13673, 2023.
Panagiotis D Grontas, Giuseppe Belgioioso, Carlo Cenedese, Marta Fochesato, John Lygeros, and Florian Dörfler. Big hype: Best intervention in games via distributed hypergradient descent. IEEE Transactions on Automatic Control, 2024.
Tobias Harks, Ingo Kleinert, Max Klimm, and Rolf H Möhring. Computing network tolls with support constraints. Networks, 65(3):262-285 2015.
Haozhe Jiang, Qiwen Cui, Zhihan Xiong, Maryam Fazel, and Simon S Du. Offline congestion games: How feedback type affects data coverage requirement. arXiv preprint arXiv:2210.1339, 2022.
Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. Annual symposium on theoretical aspects of computer science, pages 404 413. Springer, 1999.
Walid Krichene, Benjamin Drighès, and Alexandre M Bayen. Online learning of nash equilibria in congestion games. SIAM Journal on Control and Optimization, 135)0100 2015.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009, Proceedings 2, pages 250-262. Springer, 2009.
11

---

Jiayang Li, Jing Yu, Yu Nie, and Zhaoran Wang. End-to-end learning and intervention in games.
Advances in Neural Information Processing Systems. 33: 33:16653-16665, 2020.
Jiayang Li, Jing Yu, Qianni Wang, Boyi Liu, Zhaoran Wang, and Yu Marco Nie. Differentiable
bilevel programming for stackelberg congestion games. arXiv preprint arXiv:2209.076 2022.
Jiayang Li, Jing Yu, Boyi Liu, Yu Nie, and Zhaoran Wang. Achieving hierarchy- free approximation for bilevel programs with equilibrium constraints. In International Conference on Machine Learning, pages 20312-20335. PMLR, 2023.
Boyi Liu, Jiayang Li, Zhuoran Yang, Hoi-To Wai, Mingyi Hong, Yu Nic, and Zhaoran Wang. Inducing equilibria via incentives: Simultaneous design-and-play ensures global convergence. Advances in Neural Information Processing Systems, 35:29001-29013, 2022.
Zhi-Quan Luo, Jong-Shi Pang. and Daniel Ralph. Mathematical progrums with equilibrium con- straints. Cambridge University Press, 1996.
Chinmay Maheshwari, Shankar Sasty, Lillian Ratliff, and Eric Mazumdar. Convergent first-order methods for bi-level optimization and stackelberg games, arXiv preprint arXiv:2302.01421, 2023.
Jason R Marden and Tim Roughgarden. Generalized efficiency bounds in distributed resource allocation. IEEE Transactions on Automatic Control, 59(3):571 1-584, 2014.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124-143, 1996.
Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007.
Dario Paccagnan and Martin Gairing. In congestion games, taxes achieve optimal approximation. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 743-744, 2021.
Dario Paccagnan, Rahul Chandan, Bryce L Ferguson, and Jason R Marden. Optimal taxes in atomic congestion games. ACM Transactions on Economics and Computation (TEAC), 9(3):1-33, 2021.
Ioannis Panageas, Stratis Skoulakis, Luca Viano, Xiao Wang, and Volkan Cevher. Semi bandit dynamics in congestion games: Convergence to nash equilibrium and no-regret guarantees. In International Conference on Machine Learning, pages 26904 26930. PMLR, 2023.
Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning optimal strategies commit to. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 2149-2156, 2019.
Arthur Cecil Pigou. Wealth and welfare. Macmillan and Company, limited, 1912.
Robert W Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65-67, 1973.
Tim Roughgarden. Selfish routing and the price of anarchy. MIT press, 2005.
Tim Roughgarden and Éva Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and economic behavior, 47(2)3389 403, 2004.
Kunio Takezawa. Introduction to nonparametric regression. John Wiley Sons, 2005.
Heinrich Von Stackelberg, Market structure and equilibrium. Springer Science & Business Media, 2010.
John Glen Wardrop. Road paper. some theoretical aspects of road traffic research. Proceedings of the institution of civil engineers, 1(3):325-622, 1952.
Geng Zhao, Banghua Zhu, Jiantao Jiao, and Michael Jordan. Online learning stackelberg games with an omniscient follower. In International Conference on Machine Learning, pages 42304- 42316. PMLR. 2023.
Han Zhong, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Can reinforcement learning find stackelberg-nant equilibria in general-sum markov games with myopic followers? arXiv preprint 13X1v:2112.13521, 2021.
12

---

A Basics about Congestion Games
Lemma strategy a is an e-NE a congestion game, then x an e-minimizer of the corresponding potential function (-))
Proof. Let argmin ((x) and y x(x).
First, we show that
V 1.0 Σ L cg(u)du
L.a P(x)
-V, Σ cj(u)du
SEa
Σ cy(Uy)Vi,.J) Vi.Vos FEa
Eerly)
Σ
1,a
Sea
Maa':EEa'
Ees Ee((ys).
fEa
Then we have
((x) (xx)) S (z x¹, (2(x))
(Convexity)
<
(m. 2 V,b(z))
3m/m]
Σ
Σ
Tiaa Σ
Ce((ys)
min wi SEa
Ec((r)
aeA:
iE/m]
aeA:
fEa
1E/m] aEAA
Σ
W/e
sE|m]
6.
L
Lemma 1. Tepa is convex under Assumption (y"),, x is Nash equilibrium.
yf = argmin, (y), then for any x e
Proof. For y.y... 2² E V, we have
| cy(()du 1/" cy(u)du -2 2/ fo
(y + (132) 20prepa 1¹ +22
)
Σ
4t
(u(udu
2
* ug
Now show that 1 ej (u)du + fod cy(u)du W.l.o.g,, we assume y I v and we have
2
ej (u)du is nonnegative for all f E F.
S/dd (u(uddu + L-d cy(u)du - 2 2/ +
cy(u)du= = 1 cy(u)du-
cy(u)du
Juz
1/103
17 1
cr(u+
cg(u)) du
2 0,
13

---

where the last step is from Assumption |
monooonnicit).. As a result, @ropa is convex.
Let y² argminy (repa and (v") have pprepa (x())) < Trepa (y"), which contradicts the definition of y". As result, x: is the minimizer of (.). which means x is a Nash equilibrium.
:. If there exists x' X such that ((x') ((x), then
Lemma 5.
The Nash load under tax T: y(T) argmin wey (yy: 7) is not continuous w.r.t T. In addition, the social welfare ((((T) is not convex w.r.f. т.
Proof. For the first part, we construct a congestion game with two facilities f2. one commodity with action set [fi.fal and constant cost 0 1. c2 = 11-6 with e > Then for tax T 0, we have ((T [0, 1]. For constant tax T1 = 0, T2 = 2e, we have u(T) = [1, 0j. As e can be arbitrarily small, ((T) ) is not continuous w.r.t. T.
For the second part, we construct a congestion game with two facilities fi, f2. one commodity with action set {fi f2), and cost function c 1, c2(u) = Vu for E [0, 1]. We apply constant tax T: = t, T2 = 0 for & E [-1,0] The Nash equilibrium under tax r is y(T) = =I [1- [1-(1+t)² (1+
Then the social cost is (V(()) = 1 t(1 1)2, which is not convex on [-1,
B Missing Proofs in Section
Lemma 2. If the subgradient of the cost function oj is lower bounded by c > 0 for all f E F, then the potential function Tropa (y) is c-strongly convex. However, (xx) is not necessarily strongly convex.
Proof.
First, by the definition of the potential function +, it is easy show that V (CF()))se For y² .2² E V, we have
(VD())) (y² -²) = [((r()))-o(()))00
2 Σ -()) = <lly² y211 JEF
JEF
which implics (-) is e-strongly convex function.
For the second argument, only need to construct congestion game such that there exists two strategy æ! x² E X' such that for p(xx + (1-t)x²) ) is a constant for E [0, 1]. which implies the potential function ((xx' + (1 t)x²) ) propp (o(x= + (1 - t)x²)) is constant w.r.t. t. However, a strongly convex function cannot be a constant on a line, which implies & is not strongly convex.
We construct congestion game with three facilities /2, Sa. three actions ai {[i}, 02
{/2]. 03- = {fa} and three commodities with action set (ai, )2); {a2, aa); {ag, a1). SStrttgyy xt at = (1.0,0) an [0, 1, 0]. = [0, 0, 1] and x² .ी = [0, 1, 1,0],
[0. O, 1].23 = [1. 0, 0j.
Then tx + (1 t)x² is a feasible strategy and we have of txx + +11 t)2²) = [1,1, for
e [0.
Lemma 3. If two taxes 7 and i only differ in facility f and the Nash loads and ij are different, then yy f Dj-
Proof. For simplicity, we consider the equivalent tax-free case that we have two costs c, è with subgradient lower bounded by and they only differ in facility f. The potential functions are
(Y) = E/ cf(u)du, +(V) =E Yr cz(u)du.
LT""
By Lemma 2 ①b and & are strongly convex and thus the Nash equilibrium load y and ý are unique. Suppose y Dj. Consider any Y E y such that Y₁ = Vf. we have
( -v)) [|
L/ ()()) = / cg(u)du + S.d Cf(u)du
=E
349 9r
Σ 1
cj(u)du x(V) +b()) 2 0.
141
14

---

As result, we have (vv) - Φ(V)). By the optimality of 3, we have = y. By contradiction, if y + y, we have f Vj.
Lemma 6. /f/u1 u2l S A then for any |ug -uil S A, have
cy(u1) cz(12) cy(us) Sc.
u1 u2
Proof. This is a direct corollary of the B-smoothness. cr(wa)-os(ma) (u) for some E [ui, u2]. As |u u3l S I uil + +|u1
By mean value theorem, we have
ual S 22 I D3 we
have
cy(uz) ((00))(((()) cg(u2) cly (u(s Se.
U1 U2
Lemma 7. For round t and facility J. if u. E K'y, then we have rÿ(1)= -7((u) s 2r.
Proof. By the algorithm design, for each E K', (u) will not change after u is added to Ky, We will use induction on to prove ()(()) Ty(1) S e for u e KG. At round L. K3} {0} and () = (0) holds.
Suppose at round I, we have K = Ky, Ufu} with a E (wfzl2. Vof.ee and k2t1 = Ky for f + 8.. By the induction hypothesis, we only need to prove | (u) T7. (u) that
- 2e. Recall
g. - c 07
f (t) clip u
(1
). (1u (1 un)))
Then we have the following three cases. For simplicity we replace f with f.
-t By Lemma 11 and Lemma 6 we have
(1) (u) = u
-
ctt - ct ud,(w)) Se.
(w) r7(w]
y/ 03;
(2) 77 (u) = ()((())))))) ) and u $ S (1o) ). Then we have
( S 7j (1oiTT))) +
where the first inequality is from the induction hypothesis luβlū; E Ky and the second inequality is from Assumption
In addition, we have
oj - ct 2 uue((u) cc cc= Tz(1)= c.
7 (u)
03 -0
(3) (3) 7) (u) 7/ I K U(1)
and u
- w
2 2l0 k un))) Then we have
c it
(w)
< u
S udd (u) + S (1)) +e.
51 if
If My E Kj. then we have
Ff(u)
15

---

If Pbikkyu =1 and & Kj, we still have
()) - B ué = rj(
For each of these three cases, the induction holds.
As (T(()= ()( + eu for all E F and u E [0, 1]. we have 74(1)) - -r] 2e.
Lemma 8. For round facility is known, then we have (2(()) - -3((8) S 3e.
Proof. If uf E KG,, we can directly apply Lemma 7 Otherwise, we set un = [uf]ž and w22 = (
Then we have u1 < s'y < U2 and u1, U2 E K'.. There exists A1 E [0, 1].1 + X = such that
,/ = Am d222. By Lemma
6 we have (Tf(us) r3()s) S 2e for i {1,2). Then we have
T/(ott) - Ty (u9)]
AITI(U1) + X275(12) - (Aru + (2)2)<f(u))
< AATT (u1) (w)dd(()) + (detÿ(u2) (w))
SA1 1 (w1) - [](11)] Xu (d)(un) - -G(()) + 2 (T((22) - (7 + X2 (c((w2) - cf(w)l
22he + dic 222e + Aze
(Lemma B-smoothness and - us S e/B.)
<3c.
Lemma 9. If Algorithm 2 return False at round t, then for any 7 RR such that 7f = (Us) ( E F and `, E 1y for J E F², we have Gap,(a', et + 2 0 for all i E [m]] In addition, x² is a Nash equilibrium for tax F.
Proof. For simplicity, we will omit t when there is no confusion. Algorithm 2 False if and only if for all i [m) and tax 7 FF. TF;
TP: 1p, TMMFFUU FO) = TF((F UP) we have
(z,
min
Σ (c) + +F)
max amt
Σ + ())
f:fea
f:fEa
By the definition of F., for any f E F; and a: Tia + 0, we have f E a. Similarly, for any f E F/
and a Iiaa X O, we have f $ a. Thus for any a Via + O, we have
Σ (c/ tイ) Σ (ef + + Σ (r, - -,7200 2. FifEa
fifER
fER
For any a : Tiaa = O, we have
Σ (cf (5)+
Σ (o)+
Σ (4
fifeo
f:fEa
fEP
As result, we have
Gap, c +7) = min
amri 70 Σ (c/ +7)+
Σ (cf +7/)
max
a: =0
f:fEa
f:fEa
min
(g)+
max
Σ (c) + +f)) 2 0.
f-fEa
f:fEa
To prove that xt is Nash equilibrium for tax 7, we only need to show that for in-support actions ahoo # 0, the action costs Exsea(chy -y) are the same. This be derived by
E +/)
Σ 1(+ = Σ (r) -y), Va 2 + O,
F.fe
fifEa
FEF
which is independent of a. As x' is Nash equilibrium for tax r., E Ex.rea (cy + +T/) is also independent of a.
16

---

Lemma 10. If Algorithm 2 return False at round t, then tax 7² is an 6F 6Fe-optimal tax.
Proof. For known facility f. by Lemma 8 we have - - 3e. By Lemmal for any
u E y we have 77(x) - (w) s 2c. Thus for unknown facility f, we have
14 = - + (0} luflkyy) - + 2e (1b]kk;)))) 3c,
r = 7 un)) + (0f luf uay) 2 (1 un1)) -c 73 (lvf r1u 3c,
As rj is nondecreasing (Assumption
2 we have
r - 3e S (Ti(w))))))) S S s S + 3e.
Thus there exists tax 7 such that (v)) satisfies the condition of Lemma 9 and - 3e for all f E F. x' is the Nash equilibrium for tax 7L, we have
vi [m], d' Ai, Ee + (ottt = (r((ft) if if 0.
fEa
fEa
Thus have
e am), E A,,
Eerlih + +J(08t v Σ ce(lt) + + + 6Fe, if 2 > 0.
fEa
feal
By Lemma 4 1 (((t))
min (v) S 6Fe.
Lemma 11. If Algorithm 2 output 7t, Fr, sign' at round t, then we have
13 5 S.
0
Proof. First, prove 1// 3
0. We consider the following two cases.
(I) Algorithm return at Line 5 As we have 0 < (f((tt) < Wi, there exists a, a' E A, such that
Lita > 0, Fi.0 > 0 and f E a, f & a'. Suppose 3/z- ify. Then by Lemma we have y = jf as
7¹ and 7 only differ in facility fr. As result, x² is Nash equilibrium for tax However, x' is the Nash equilibrium for tax Ty implies
Eerluf) +((T))
JEa
SEal
As r' and 3 only differ in facility jr and j E Ea, J" $ a', we have
Ec +( # Eerlsh + -
+(((1)
JEa
Sea'
which means x' is not the Nash equilibrium for tax f. By contradiction, we have vz. fz..
(2) Algorithm return 7 f, sign at Line 23 or Line 31 As there exists j E [m]] such that Gap, c+ tu+signe)) < 0, not Nash equilibrium under tax **. Let # #J = rÿ U(v}, 77) for f F.
Then 3 and #t only differs in I and is the Nash equilibrium under tax #t_ By applying Lemma with j² and fu, we have y²z = Uy--
Second, we prove 1z - S A. (1) Algorithm return at Line 5 Suppose we have |0} 0/3 > A. By the tax design, the (sub)gradient the tax (r,)(() 2 for a E [o, 1]. As a result, (yy, C+T')
17.
is c-strongly convex by Lemma 2 As y argmin yey $(y; ( 7"), we have
((j 46y +()':c+ 223
17

---

However, we have Py -g) for all y E y. Thus we have +() - 8
" c - c s + +*) + 6.
Comparing to the inequality above, we have 25 > / which incorrect by the definition d. By contradiction, we have y 3/ S..
Ty) (2) Algorithm @gorithm@retumn 7" f" sign at Line 23 or Line 31 #t : = : for f E F. Then is the Nash equilibrium under tax #*. Let F Fj T Ulv Ty) for all f f F. By the definition of Ff and the feasible range Fy [y] the subgradient of jj lower bounded by e. As a result,
@ ((:cc +*) is c-strongly convex on [0, 1]. We can prove 0/ if - A by following the analysis for case (1) and replacing r² with gt.
Proposition 1. If Algorithm 2 return Falsc round then tax 5 is an 66 Gc.-optimal tax. If Algorithm 2 output 7,, f sign' round then we have
7
Proof. This directly from Lemma 10 and Lemma
Lemma 12. Algorithm 7 return False in at most K.F rounds.
Proof. By Lemma and the update rule ① if Algorithm return 7", f. sign at round t, then we will have one more known point, i.c., E kettl
Ey As Kł C C for all f F and
[ K + 1, we proved the lemma.
Theorem 1. Under Assumption 7 and Assumption 2 Algorithm 7 will output 6cF tax within < 2/Bec rounds. In addition, each round has at most two tax realizations.
Proof. The proof is directly from Proposition | and Lemma 12
C Computation Complexity
this section, we discuss the computation complexity of Algorithm T and Algorithm 2 will show that these two algorithms can be implemented with (A, F, m)) complexity for each round. For network congestion games, the computation complexity can be sharpened to (ppoly E, E)), avoiding the dependence on that can be exponential in and E.
C.1 General Congestion Games
For Algorithm T we compute/update the value of the cost/tax function for each facility. As the dictionary data structure, computing value and updating value only have Ollog K) = Olog B/e) complexity. As result, the complexity of one round in Algorithm is Ô(F).
For Algorithm 2 x E (y) is Caratheodory decomposition problem and can be formulated m 2). which can be solved in polynomial time [Cohen al. 2021
linear program with A variables, F+ m equation constraints and A inequality constraints (Proposition
The bottleneck is in computing u = argmax,, {u (x, > 0, Vj [m]] for 7M 77
u, F\() = T f E F.. For simplicity, we use the notation: 2h + F as the cost with tax
7r.. By Definition 5 and the definition of action cost, we have
(+)
min 2
max T 200
(4)
18

---

For action cost C. if f E a, it is linear function w.r.t u in the form of u + C' for some constant C. Otherwise, a constant w.r.t. u. As a result, we can determine the function 22 with O(F)
computation as we only need compute 2 to decide the constant. Then we can compute Gapy( (r, c+ 7)) in closed form and compute " = argmax, {w: Gap, (2, ++7") 2 03 with O(AF) complexity. Finally, u minjer je ml U can be computed with (m)AF) complexity. Similarly, u = argmin, {u Gap, + 7*) 0, Vjj E [m]} has Om.FF) computation complexity.
C.2 Network Congestion Games
For network congestion games, Algorithm can be implemented by applying shortest path algorithms on a modified network, thus avoiding the dependence on A. We will apply Dijkstra's 's algorithm with Ö(V + E') complexity while other shortest path algorithms can be used as well.
First, the Caratheodory decomposition (v) can be done efficiently with O(VE + E²) steps similar to the decomposition algorithm in [Panageas et al.) [023]. While their algorithm is for the flow polytopes with one commodity, it can be directly generalized to the multi-commodity case. We defer the algorithm and analysis to Appendix D
For argmaxx, {u: Gap, c+ ( F*) 2 V, E [m]], the computation complexity can be boosted to Õmm E + V)). To achieve this, we consider how (4) changes as u increases from 7/ to ry. By Algorithm 2 we have (z, c F") 2 O when
r as otherwise the algorithm ends at the previous iteration. In addition, facility/ f either has none of the Nash load or has all of the Nash load for facility j according to the algorithm design. For the first case, the in-support action costs will not change as u increases. Gap,(I,e 7")) 2 0 always holds as the off-support action costs are nondecreasing w.r.t. u.
For the second case (all in-support actions use f), the in-support action costs take the form of - C' and C' can be determined by applying shortest path algorithm with edge weight c 77), For off-support action cost, we observe that
min 2h min 1
min a0.
2% min
3 = min
min C min 25 a. E,E
affea J (5)
EEa a. fge
where the second equation is from that the action cost does not depend on u and 2j,a = if f & a. The first term in (5) grows linearly w.r.t u as f E a, so it is always larger than the in-support action cost. The second term in (5) is the shortest path length for commodity j that does not use facility f. which can be computed the shortest path in the network after removing edge f. As result, My = argmax,, {u: Gap,( (1, c + 7") 2 0} can be computed with O(E + V) complexity. Then the complexity for computing u minje[m] Uy is Ö(m(E + V)).
Similarly, U,- = argmin, {u Gap, (z, c +*) 2 0} can be reduced to solving the shortest path that must use edge f in the network. We consider how (4) changes as u decreases from Ty to l.. Initially, the gap is nonnegative. If f has all of the Nash load, then the in-support action cost is linear function u + C' and it decreases at least as fast as the first term. As a result, the gap is always nonnegative. Otherwise, has none of the Nash load and in-support action costs remain constant.
We notice the following equation:
min ट. = min min 2u min a: =
] minf min Ca min affEa a
2 },
(6)
a:z5.a fea a=.
where the second equation is from that f E a implies a is off-support (Iy,a 0) and f & a implies 24 independent of u. The second term in (6) a constant and always greater than the in-support action cost. The first term in (6) is linear function u and it can be determined by computing the shortest path that always uses f and with edge weights + FT, This subproblem can be solved by applying the shortest path algorithm twice: the first one is to connect the source node and the starting node of f. and the second one is to connect the end node of ff and the target node. As a result, the complexity for = maxje(m] Uj is Ö(m(E E + V)) as well. Thus the computation complexity for Algorithm 2 in network congestion games is O(VE + E + mV mL).
19

---

D Missing Proofs in Section C
Proposition 2. Finding x E Φ (v) can be formulated as the following linear program.
min 1 ZERA
Σ
Σ
s.1.
F4,0;
iE(m) a.EA,
W/ = Σ
Di,azs Vi E [m]]
a.EAi
Tia;; 2 0, V. E.,
Proof. The second and third constraints guarantees z is a feasible strategy. The first constraint indicates ((x). As result, any feasible point of the program is solution (y).
Algorithm 3 Efficient Computation of Flow Decomposition (Modified from Panageas al. 2023
Input: load y V.
2: Ti,a = 0) for all i E [m] and a E As.
3: while 3f yf > do
4:
Let A = {f uy > 0}.
5: Let fmin argmin Vy and Ymin minnee Vs-
6:
Let be a (st, 1:) path of network G(V, A) with Smin p.
7: Let Ti.a = Umins Vf yf Ynii if f E
8: end while
Proposition Algorithm 3 Can output Caratheodory decomposition of within E steps.
Proof. During the algorithm, load will always nonnegative: y, 2 0f E F. For each round, will have fmen reduced to O. As result, the algorithm will end within most E rounds.
We only need to prove that path always exists in Line (6) for each round. First, y always remains multi-commodity flow as Line 7 will not affect the law of conservation in the network. By flow decomposition theorem, there exists simple paths a1 a2. such that
Σ KE(P)
y
where > are positive flow weights. As Vmmmn > 0, there exists as such that fuin E Then for any f E a. yy wi > As result, path a exists for Line (6).
E Experiments
We implemented our algorithm and conducted experiments on a classic example known as the nonlinear variant of Pigou's 's example [Nisan et al. 2007 Concretely, nonlinear variant of Pigou's 's example routing game with one source node s and one target node t. There are two edges connecting and f. One edge has constant cost (z) c, Vr [0, for some [0, 1], and the other edge has polynomial cost eı (x)) = x². One important property of such games is the price of anarchy grows without bound p oo, which urges proper tax to induce socially optimal behavior.
apply our algorithm to learn the optimal tax with different co and p. As we can see, the social welfare quickly converges to the optimal one. Another important observation is the learned tax function does not uniformly converge to the marginal cost tax, which is reasonable as accurate estimate is only necessary around the Nash equilibrium induced by the tax.
20

---

Social Wellere Curve of the Algorithm C=0.2, gi22
Socia Welfeere Curve the Algerithm c= pad
Alganthim social wolfore Opemall socal waFarre
Alguiili soc wellare
Opamall socia wallrre
0.155
0.00
0.80
52044 eer
0:25
0.70
0.54
0.165
Number
Number
(a) c=0.2. p=2
(b) c=0.2, p=4
of Algoritti cm0.6, pm2
Social Welfare Curve the Algor Agorfthim c-0 -0, pmd
0.50
Agonthin sonal wallee
Aigenihin wettere
oppmal pocaa welfrre
optimal socal welfre
0.18
0.0-
3000 wolare
0A7
0.45
0.48
0.55
10
Namberr Aeretiono
Nurbic of kicell om
(c) c=0.6, p=2
(d) c=0.6, p=4
Welfare
Aigoithin
Zigorther
podal walfore
0.
0.70
0.0
50CJ wefer
068
Socral
086
10
0
10
20
22
30
acrelion
Number iicral
(e) c=1, p=2
(f) c=, p=4
Figure 1: Social Welfare Curves of the Algorithm for various values of and We can observe that the social welfare converges to the optimal one quickly.
21

---

Estimated lax Function at the Last Itertion for c=:.2, pin
Estimated Tex Punction al the Last Iteration for c=D22 p-
50
Margral cost
Estimated
Estimated
Marginal caat
1.5
1.
Edon land
Edoe
(a) c=0.2. p=2
(b) c=0.2, p=4
Runction the beration for c-0.6, p-2
Estimated Tax Fanction Last Ieration C-0.6, p-t
3.
Marginal 002t
Marginal cest t3x
Extemated
7.5
2.0
0.5
0.0
6.4
0.6
1.0
012
0/b
Edge load
Edge locd
(c) c=0.6, p=2
(d) c=0.6, p=4
Estimated
Estimated Function
Marginal t3x
Morginal 0922
2.5
10
2.0
0.
00
04
0.6
1.
90
04
0.4
0.6
19
Edpe
(e) c=1, p=2
(f) c11,p=4
Figure 2: Estimated Tax Functions at the Last Iteration for various values of e and p. The estimation is not uniformly accurate but they are accurate at the induced Nash equilibrium.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction accurately reflect the paper's contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitations of our assumptions and algorithms.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
We provide the proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibiliyy
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our experiment a direct implementation of our algorithm on well-known task and can be reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [No]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/dde/eeee Cooeeeoodeesssseeeeee 7/nips.com htc/://bbb///gdddee///eeeeeeisss ssiniiiiccyp for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Our experiment a direct implementation of our algorithm on well-known task and can be reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification:
Our experiments are deterministic.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
25

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Our experiment require minimal computation resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://aaarrs....pppl/////aaaaaa
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
Our research can be potentially applied to real-world tax design.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We did not use public dataset.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
27

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "BjAwNkPhGx", "reviewer": "Reviewer_nncK", "summary": "The paper focuses on the challenge of designing tax mechanisms to maximize social welfare in congestion games, where players' self-interested behaviors can lead to suboptimal outcomes for the overall system. The study introduces an innovative algorithm to learn the optimal tax with limited feedback, termed \"equilibrium feedback,\" where the tax designer can only observe the Nash equilibrium resulting from a deployed tax plan.\nThis paper introduces a novel approach to learning optimal tax design in nonatomic congestion games, addressing critical challenges with innovative solutions. The proposed algorithm not only advances the theoretical understanding of congestion game tax design but also has potential real-world applications in improving system efficiency in scenarios with shared resources.", "questions": "1. Can you provide empirical validation or simulation results to support the theoretical claims?\n2. Can you justify the assumptions made about the smoothness and other properties of cost functions in more detail?\n3. Can you compare your approach with existing tax design methods in terms of performance and applicability?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a novel algorithm for learning optimal tax design in nonatomic congestion games with equilibrium feedback, an approach that has not been previously explored. The use of piece-wise linear functions to approximate optimal tax functions is a good solution to handle the complexity of the tax function space.\n2. The theoretical foundation of the paper is strong, with rigorous proofs and a well-defined algorithm that addresses key challenges in tax design.\n3. The paper is well-organized and clearly written, making it easy to follow the logical progression of ideas and the development of the algorithm.", "weaknesses": "1. While the approach is novel, it heavily relies on theoretical constructs without introducing substantial new empirical methodologies or experimental techniques.\n2. The absence of empirical validation or simulation results weakens the overall quality of the paper, as it is difficult to assess the practical effectiveness and efficiency of the proposed algorithm.\n3. The paper's focus on theoretical development without sufficient empirical support may reduce its immediate relevance and usefulness to practitioners in the field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your thoughtful review. We acknowledge the importance of empirical validation and **have provided it in Appendix F**. In the final version, we will ensure this is better highlighted.\n\n- **Assumptions:** Monotonicity is a standard assumption in the nonatomic congestion game literature [Nisan et al., 2007]. Smoothness is a widely accepted technical assumption in the literature. Non-decreasing marginal cost function is a reasonable assumption in real-world problems that enjoy the law of diminishing return. We want to emphasize that our assumptions are much weaker than all prior works, which assumes at least one of the following conditions: full information about the game, (linearly) parameterized cost function, control over all the agent, and convex objective function. \n- **Comparision with existing methods:** One line of research focused on the computational complexity of tax design in congestion game, which requires full knowledge of the game and is not applicable to the equilibrium feedback setting. Tax design with equilibrium feedback can also be formalized as Stackelberg games or mathematical programming under equilibrium constraint. However, existing approaches for these two problems require assumptions such as parameterized function space, convexity and control over the agents [Bai et al., 2021, Zhong et al., 2021, Li et al., 2020, Liu et al., 2022]. To best of our knowledge, none of the existing approaches has favorable theoretical guarantees. We believe our work serve as an initial step in this area.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "udLPRqfipI", "reviewer": "Reviewer_Q6MU", "summary": "The paper considers the problem where a system designer endeavors to guide players to welfare-maximizing behavior via imposing a tax function. One key challenge is that the designer can only observe equilibrium feedback from a Nash equilibrium, a stable state of the system, after imposing the tax. The main contribution of the paper is an algorithm that solves this problem with a polynomial sample complexity.", "questions": "See above.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main problem introduced in the paper is interesting, well-motivated and, to my knowledge, new. Imposing taxes so as to mitigate the price of anarchy has been a popular approach in the literature on algorithmic game theory, but prior work makes assumptions that are too strong for some applications, such as precise knowledge of the underlying game. Instead, this paper puts forward a more realistic feedback model, which I believe is well-motivated. Further, the proposed algorithm and analysis contains a number of interesting technical ideas, as this problem has a number of distinct features compared to prior work. These ideas are nicely presented in the introduction. Another compelling aspect of the proposed method is that it is also computationally efficient, even in network congestion games where the number of actions is exponential. The paper also accurately places its contributions in the context of related lines of work.", "weaknesses": "One important question, which I feel is not addressed adequately in the paper, is whether it is realistic to assume that players will immediately reach a Nash equilibrium after the imposition of the tax. This is an important modeling assumption which requires further justification in my opinion. If I understand correctly, a Nash equilibrium can be at least computed efficiently even after the tax is imposed; can the authors discuss about specific dynamics that will end up in an equilibrium in polynomial time? Otherwise, why is it reasonable to assume that a Nash equilibrium will be reached in the first place? Also, have the authors considered relaxing that assumption by only assuming that players have no-regret? For example, this assumption is made in the paper by Zhang et al. (titled \"Steering No-Regret Learners to a Desired Equilibrium\"), which could be discussed in the paper. \n\nBesides the point above, it can be argued that most of the technical components used in the paper are fairly standard, although the way they are combined appears to be novel and non-trivial. \n\nFinally, I believe the writing is a bit sloppy at times. The abstract talks about \"boundary tax,\" which is not at all clear in the context of the abstract, although it is clarified later. Can the authors try to rephrase that in the abstract? I would also suggest pointing out in the abstract that the proposed algorithm is also computationally efficient, as it is an important feature. Moreover, the section of the conclusions is underwhelming, and I would strongly recommend expanding it with directions for future work. The authors should also remove the instructions block from the NeurIPS paper checklist so as to adhere to the formatting instructions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your appreciation! We address your questions below.\n\n- **Nash equilibrium assumption:** Under Assumption 1 (standard assumption used in nonatomic congestion game [Nisan et al., 2007]), the potential function of the game is convex and computing the Nash equlibrium is equivalent to solving a convex optimization problem. In addition, as we always apply a tax with positive subgradient lower bound, the potential function in the game with tax is always strongly convex (Lemma 2). As a result, computing the Nash equilibrium is equivalent to minimizing a strongly convex function. E.g., one kind of no-regret dynamics is shown to converge to Nash equilibrium [Chen and Lu, 2016]. Only assuming each player apply an no-regret algorithm would be an interesting future direction. We will add the discussion on [Zhang et al., 2023] in the final version. \n- **Writing:** Thanks for your suggestions! We will add the computation efficiency part to the abstract and replace boundary tax with \"exploratory tax that can provide critical information about the game\". We will also add a future work section with following potential directions.\n1. Relaxing the Nash equilibrium assumption to players following no-regret dynamics or quantal response equilibrium.\n2. Design algorithms that do not require prior knowledge of the smoothess coefficient.\n3. Generalize the algorithm to atomic congestion games.\n\n> Chen, Po-An, and Chi-Jen Lu. \"Generalized mirror descents in congestion games.\" Artificial Intelligence 241 (2016): 217-243.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SuE4JKI52d", "reviewer": "Reviewer_vts3", "summary": "The paper studied the classic congestion pricing problem, which can be framed as a Stackelberg game in which a leader (a tax designer) imposes congestion tolls in a congested network used by many self-interested travelers (followers), with the goal of minimizing the total social cost.  The proposed algorithm can be applied to scenarios where the tex designer can observe nothing but the equilibrium reached by the travelers.", "questions": "My rating of the paper could be further increased if the following two questions can be appropriately answered. \n\n1. In this paper, travelers' behavior is assumed to be a Nash equilibrium,  which implicitly assumes travelers are perfectly rational. A more realistic assumption is that they are boundedly rational, which may correspond to a so-called quantal response equilibrium. Please discuss how your work can be extended with this assumption. \n\n2. In reality, equilibrium-reaching may be time-consuming, maybe taking several weeks. That is to say, it is not easy for a tax designer to actually observe the equilibrium outcome. How would you address this challenge?", "limitations": "The limitations are appropriately discussed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In the literature, most algorithms for congestion pricing are dedicated to scenarios where the tax designer can accurately predict how travelers would behave in response to the congestion taxes. However, for this to be possible, a basic requirement is that the tax designer should know how travelers would balance between time and money (like \"$5\" and \"10 min\", which one is more important), which is usually not practical. Hence, exploring congestion pricing under the bandit setting is a great endeavor.\n\nMeanwhile, I believe there is no easy path to this setting, as it is fundamentally different from standard bandit problems: in this case, the \"feedback\" is an equilibrium state. Hence, I personally believe the paper's contribution is valid.", "weaknesses": "1. The review of the literature can be more solid. \n\n1.1. In Appendix A, it is stated that \"MPEC is a bilevel optimization problem, which is usually intractable.\" This is not sufficient. Instead, the authors are encouraged to cite some works that have proved MPECs to be strongly NP-hard (you may find many). Particularly, you may cite some works discussing the complexity of congestion pricing problems; the following paper is an example.\n\n[1] Harks, Tobias, et al. \"Computing network tolls with support constraints.\" Networks 65.3 (2015): 262-285.\n\n\n1.2. I encourage the authors to add a paragraph in Section 2 to discuss \"Learning in Stackelberg games with bandit feedback.\"\n\n1.3. There are some other recent works on congestion pricing, which is related tot the present study. \n\n[1] Li, Jiayang, et al. \"Achieving hierarchy-free approximation for bilevel programs with equilibrium constraints.\" International Conference on Machine Learning. PMLR, 2023.\n\n[2] Grontas, Panagiotis D., et al. \"BIG Hype: Best intervention in games via distributed hypergradient descent.\" IEEE Transactions on Automatic Control (2024).\n\n[3] Maheshwari, Chinmay, et al. \"Convergent first-order methods for bi-level optimization and stackelberg games.\" arXiv preprint arXiv:2302.01421 (2023).\n\n\n2. There are many editorial mistakes in the paper. For example, please check the title of Section 5.  \n\nFor other weaknesses, please refer to my questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your appreciation! We address your questions below.\n\n- **Literature review:** Thanks for pointing out references! We will include MPEC hardness and the complexity of the pricing problems in the final version. We will also move the discussion on Stackelberg games in the Appendix to the main paper.\n- **Quantal response equilibrium:** We consider Nash equilibrium as we believe this would be a reasonable first step in this direction. Relaxing this assumption, e.g. cosidering quantal response equilibrium, would be an interesting future direction. The main challenge in adapting our algorithm would be in finding the \"boundary\" tax that can provide critical information about the game. Designing such tax would require a more sophisticated analysis that is specialized to quantal response equilibrium.\n- **Time constraint in practice:** Our algorithm can be easily adapted to the case where we have feedbacks other than only the equilibrium feedback, which correspond to the observations when the system is evolving towards the Nash equilibrium. Specifically, when the tax designer obtain a non-equilibrium feedback, she can still update the optimal tax estimate (if the feedback provides new information) and apply the new tax. It is possible for our algorithm to find the optimal tax even if no equilibrium feedback is used. In addition, as long as the equilibrium can be reached after applying a tax for some time, the algorithm can always find the optimal tax. In short, our algorithm is not restricted to only using the equilibrium feedback, but all possible feedback.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x1YBh6cLUL", "reviewer": "Reviewer_udJm", "summary": "This manuscript proposes an algorithm for obtaining optimal tax design on nonatomic congestion games that decreases the social welfare of equilibrium state. Although the optimal tax design for nonatomic congestion games has a closed form of cost function, the cost function is generally unknown for tax designers. Thus, this manuscript proposes a non-parametric way to obtain an $\\epsilon$-optimal tax design under that the tax designer can only access the information of equilibrium state. The algorithms for network congestion games where each strategy is a path in the network is also given, which enjoy polynomial complexity with respect to the number of vertices and edges.", "questions": "I'm interested in a variant of network congestion games, where user's strategy forms a specific type of subgraph (other than path) of a network. If the type has a polynomial time algorithm for optimizing the weight (e.g., Kruskal algorithm for spanning trees), can you incorporate this algorithm to the proposed approach? This may widen the applicability of the proposed algorithm with exponentially many strategies.", "limitations": "The limitations of the proposed approach should be summarized at the end of article.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The proposed approach consists of novel and non-trivial ingredients: parameter-free approach with piecewise-linear tax function and tax design leading to strongly convex potential. Although there are some works for mathematical programming under equilibrium constraint (MPEC) that is a more generalized problem, they cannot reach a global optimal for tax design due to the non-convexity.\n\nThe support for network congestion games is also impressive, since it have exponentially many choices (paths) for users.", "weaknesses": "- The applicability of the proposed algorithm for network congestion games is not empirically confirmed. Since the proposed algorithm for network congestion games enjoy polynomial complexity, empirical evaluation with network congestion game instances will enhance the manuscript since it is directly connected to toll design on road networks.\n\nMinor comments:\n- Although I agree that it may be the first work to design tax under \"equilibrium feedback\", the notion of such a partial feedback setting may go back to previous literatures, e.g., [Liu et al., NeurIPS 2022] that is cited by the manuscript. Thus, it is questionable that the \"equilibrium feedback\" setting is the proposal of this manuscript.\n- The limitations of the proposed approach should be summarized at the end of article.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your appreciation! We address your questions below.\n\n- **Equilibrium feedback:** Thanks for pointing out the usage of similar concepts as equilibrium feedback in prior works. We will comment on this and make clear that we are the first studying it in the tax design setting in the final version.\n- **Limitation:** We will add a limitation section at the end of the paper in the final version to summarize the limitations we mentioned in the main paper.\n- **Variant of network congestion games:** This is an very interesting direction! In our analysis, we only require that there are polynomial algorithms to optimize the weight in two specific networks, i.e., removing one given edge from the original network or having to use one given edge in the original network. For the minimum spanning tree case you mentioned, we can apply any minimum spanning tree with the weight of that given edge modified to be negative infinity or positive infinity (or just $-\\sum_{e}w_e$ and $\\sum_{e}w_e$).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DWrkfu7xOW", "reviewer": "Reviewer_18G8", "summary": "This paper investigated how to design the optimal tax in congestion games to minimize the social cost, with partial information. Specifically, the tax designer cannot observe the cost function directly. Instead, whenever a tax assignment is announced, the designer will observe the Nash equilibrium and cost.", "questions": "- What's $c'_f$ in the definition of marginal cost tax? Is it the derivative of the cost function?\n- Need the algorithm to know the smoothness $\\beta$ in advance?", "limitations": "Yes. The author addressed the assumptions required by the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- This paper learns the optimal tax with partial information feedback, which is more realistic in real-world applications.\n- The assumption is mild: This paper only assumes monotonicity and smoothness of the cost function, as well as a non-decreasing marginal cost tax\n- The sample complexity is independent of the action set size", "weaknesses": "- There are some typos in the paper, for instance:\n  - In definition of $\\epsilon$-optimal tax, it should be $\\Psi(y)\\leq \\min \\Psi(y')$ instead of $\\arg\\min$\n  - Line 163: Marginal cost tax\n- The experiment is weak: The network has only two nodes and two edges.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your appreciation! We address your questions below.\n\n- **Typos:** Thanks for pointing out the typos! We will correct them in the final version.\n- **Definition of the marginal cost function $c'_f$:** Yes it is the derivative of the cost function.\n- **Knowledge of $\\beta$:** The algorithm requires knowing the value (or an upper bound) of the smoothness $\\beta$ in advance. It would be an interesting future direction to remove this requirement.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Based on the general consensus that this paper provides an important theoretical contribution, I recommend acceptance of the paper as a poster. Some major points of criticism were the lack / small scale of experiments and the practicability of the assumption that players converge towards an actual Nash equilibrium. However, the former is fine for a theoretical paper and the latter is indeed a limitation that should be clearly stated, but the results still remain interesting with this assumption.
Decision: Accept (poster)