Learning Optimal Tax Design in Nonatomic Congestion Games

Authors: qiwen  cui
maryam  fazel
simon s du
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 08:35:39

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.

Main paper: 
 introduction: 
 In modern society, large-scale systems often consist of many self-interested players with shared resources, such as 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 more roads to a network can make the network more congested [Braess, 1968] . Price of anarchy is 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 to improve performance even when the players are still behaving selfishly.Tax mechanisms are a 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 is a 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 a network, and each player chooses a 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 as the toll collected by the road owner or 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 a partial information feedback 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 or 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 feedback?Below we highlight our contributions.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(F 2 β/ϵ) sample complexity for learning an ϵ-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 O(poly(V, E, ϵ)) 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 C and Appendix E.2. Piece-wise linear function approximation. We only assume the cost functions are 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 to 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.[m] = {1, 2, • • • , m}. For a set of real numbers K and a real number x : min{K} ≤ x ≤ max{K}, we define [x] + K := min y∈K:y≥x y and [x] - K := max y∈K:y≤x y. The clip operation clip(a, l, r) := min{max{a, l}, r} clips a into the interval [l, r]. We use O(•) to hide absolute constants and O(•) to hide polylog terms as well. A function f :X → R is α-strongly convex if f (y) ≥ f (x) + ∇f (x) ⊤ (y -x) + α 2 ∥y -x∥ 2 2 , ∀x, y ∈ X . f is β-smooth if ∥∇f (x) -∇f (y)∥ 2 ≤ β ∥x -y∥ 2 , ∀x, y ∈ X .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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 Learning in congestion games. We refer the readers to the textbook [Nisan et al., 2007] for a general introduction to congestion games, the price of anarchy and tax mechanisms. Nonatomic congestion games were first studied in [Pigou, 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 to 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 , Jiang et al., 2022 , Panageas et al., 2023 , Dong et al., 2023 , Dadi et al., 2024] . These algorithms are derived from the perspective of the players in the system, while our algorithm is essentially different in that it is utilized by the system designer to induce better equilibrium.Optimal tax design in congestion games. For nonatomic congestion games, optimal tax design has a closed-form solution known as the marginal cost mechanism [Nisan et al., 2007] . For atomic congestion games, the marginal cost mechanism can no longer improve the efficiency [Paccagnan et al., 2021] . Instead, other mechanisms are proposed for optimal local/global and congestion dependent/independent tax in atomic congestion games [Caragiannis et al., 2010 , Bilò and Vinci, 2019 , Paccagnan et al., 2021 , Paccagnan and Gairing, 2021 , Harks et al., 2015] . Notably, all of these mechanisms assume full knowledge of the game while we consider learning with partial information feedback.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 is 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 on 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 as mathematical programs with equilibrium constraints (MPEC). MPEC is a bilevel optimization problem and is NP-hard in general [Luo et al., 1996] . Existing approaches use specific inner loop algorithms to approach the equilibrium so that the gradient can be propagated to the outer loop [Li et al., 2020 , Liu et al., 2022 , Li et al., 2022 , Maheshwari et al., 2023 , Li et al., 2023 , Grontas et al., 2024] , relying on a 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.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 a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminaries: 
 Nonatomic congestion games. A weighted nonatomic congestion game (congestion game) is described by the tuple (F, A [m] , w [m] , c F ), where F is the set of facilities with cardinality F , m is the number of commodities, A i is the action set for commodityi ∈ [m], w i ∈ [0, 1] is the weight for commodity i ∈ [m] such that i∈[m] w i = 1, and c f : [0, 1] → [0, 1]is the cost function for facility f ∈ F. Each commodity consists of infinite number of infinitesimal players with a total load to be w i . Each individual player is self-interested and has a negligible effect on the game.In congestion games, action a ∈ A i , i ∈ [m] is a subset of F, i.e. a ⊆ F, which denotes the facilities utilized by action a. For commodity i ∈ [m], we use strategy x i = (x i,a ) a∈Ai ∈ [0, w i ] |Ai| with constraint a∈Ai x i,a = w i to denote how the load is distributed over all the actions. The joint strategy for the game is represented byx = (x 1 , x 2 , • • • , x m ) ∈ [0, 1] A , where A = i∈[m] |A i |.We use X to denote the set of all feasible strategies.A decentralized perspective of strategy x i for commodity i is that each self-interested infinitesimal player follows a randomized strategy that chooses a ∈ A i with probability proportional to x i,a . With the law of large number, the load on action a would be x i,a .Cost function. For a strategy x, the cost of a facility is c f (l f (x)), where l f (x) = i∈[m] a∈Ai:f ∈a x i,a is the load on facility f . The cost of an action a is the sum of the facility cost that a utilizes:c a (x) := f ∈a c f (l f (x)).We make the following assumption on the cost function. Monotonicity is a standard congestion game assumption, which is also observed in 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: c f (•) is non-decreasing for all f ∈ F, 2. Smoothness: c f (•) is β-smooth for all f ∈ F.Nash equilibrium. Nash equilibrium in nonatomic congestion games, also known as the Wardrop equilibrium [Wardrop, 1952] , is the strategy that no player has the incentive to deviate from its strategy as formalized in Definition 1. In other words, Nash equilibrium is a 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 ′ ∈ A i , we havec a (x) ≤ c a ′ (x), if x i,a > 0.Similarly, an ϵ-approximate Nash equilibrium x satisfies that∀i ∈ [m], a, a ′ ∈ A i , c a (x) ≤ c a ′ (x) + ϵ, if x i,a > 0.For a strategy x and commodity i, actions a ∈ A i such that x i,a > 0 are named as 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. It 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) := f l f (x) 0 c f (u)du.If Assumption 1 is satisfied, then Φ(x) is a convex function and Nash equilibrium is equivalent to the minimizer of the potential function [Beckmann et al., 1956] .Network congestion games. Network congestion games are congestion games with multicommodity network structure, which are also known as the selfish routing games [Roughgarden, 2005] . A multicommodity network is described by a directed graph (V, E) where V is the vertex set and E is the edge (facility) set. In addition, each commodity i ∈ [m] corresponds to a pair of source and target vertex (s i , t i ), and actions are all feasible paths connecting s i and t i . Each edge is associated with a nondecreasing cost (latency) function.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Answer: [No] Justification:Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 some notions to simplify the problem.For a strategy x i ∈ R |Ai| , the dimension |A i | can be as large as 2 F . Instead, it would be convenient to consider the facility load y i ∈ R F such that y i,f = a∈Ai:f ∈a x i,a . In addition, we define y = i∈[m] y i ∈ R F to be the total facility load. We use ϕ (i) (•) to denote the reparameterization mapping:ϕ(x) = y, ϕ i (x i ) = y i , ∀i ∈ [m],and we set Y = {y ∈ R F : ∃x ∈ X , y = ϕ(x)} to be the set of all feasible loads. Note that ϕ is not necessarily a bijection, i.e., there could exist multiple strategies sharing the same load. We use ϕ -1 (y) := {x ∈ 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 (y) := f y f 0 c f (u)du = Φ(x), ∀x ∈ Φ -1 (y).Importantly, Φ repa (y) does not depend on the choice of strategy x ∈ ϕ -1 (y). For the reparameterized potential function, we have the following lemma showing that it is almost equivalent to the original potential function. When it is clear from the context, we will simplify Φ repa as Φ.Lemma 1. Φ repa is convex under Assumption 1. If y * = argmin y Φ repa (y), then for any x ∈ ϕ -1 (y * ), x is a Nash equilibrium.For any Nash equilibrium strategy x, we call y = ϕ(x) the Nash equilibrium load (Nash load).Nash equilibrium is a stable state for a 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:Ψ(y) := f y f c f (y f ).Price of anarchy is a 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 = max y is a Nash equilibrium load Ψ(y) min y∈Y Ψ(y)For example, in nonatomic congestion games with polynomial cost functions, the price of anarchy grows as Θ(d/ ln d) where d is the degree of the polynomials [Nisan et al., 2007] .To reduce the price of anarchy, one standard approach is to enforce a tax on each facility to change the behavior of the self-interested players. Formally, a taxed congestion game is described by(F, A [m] , w [m] , c F , τ F ) with an additional tax function τ f : [0, 1] → R on facility f ∈ F.The cost of facility f with load u under tax becomes c f (u) + τ f (u). Correspondingly, we define the potential function with tax τ asΦ(y; τ ) := f y f 0 [c f (u) + τ f (u)] du,and the Nash load would satisfy y * ∈ argmin y Φ(y; τ ).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.Initialize: Facility set F. for t = 1, 2, . . . , T do Designer chooses tax τ t . Designer observes Nash load y t = argmin y∈Y Φ(y; τ ) and Nash cost c t = [c f (y t f )] f ∈F for f ∈ F. end for Definition 2. A tax τ is an optimal tax if all Nash equilibria under tax τ can minimize the social cost:argmin y∈Y Φ(y; τ ) ⊆ argmin y∈Y Ψ(y).In addition, a tax τ is an ϵ-optimal tax if we haveΨ(y) ≤ min y ′ ∈Y Ψ(y ′ ) + ϵ, ∀y ∈ argmin y ′′ ∈Y Φ(y ′′ ; τ ).The marginal cost tax is defined asτ * : τ * f (u) = uc ′ f (u), ∀f ∈ F. As Φ(y; τ * ) = Ψ(y), the Nash equilibrium under tax τ * will minimize the social cost and τ * is an optimal tax [Nisan et al., 2007] . We will make the following assumption so that the cost combined with tax c + τ * is still non-decreasing. In many real world problems, c ′ f (u) is non-decreasing due to the law of diminishing marginal utility, which guarantees Assumption 2.Assumption 2. Marginal cost tax τ * f (u) = uc ′ f (u) is non-decreasing for all f ∈ F.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 can 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 1. At round t, the designer can choose a tax τ t and observe the corresponding Nash equilibrium load y t ∈ R F and Nash equilibrium cost c t ∈ R F . The sample complexity of a tax design algorithm is the number of rounds for designing an ϵ-optimal tax.A naive approach is the designer first enumerates all of the ϵ-approximations of τ * and chooses the tax with minimal social cost. However, such an approach would require O((1/ϵ) F β/ϵ ) samples as the complexity of using piece-wise linear function to approximate τ * f (a β-smooth function) with ϵ error is O((1/ϵ) β/ϵ ), resulting in exponential dependence on the parameters β, 1/ϵ and F .Another approach is applying algorithms for mathematical programming under equilibrium constraints. Specifically, we can formulate tax design as solvingmin τ Ψ(y(τ )), s.t. y(τ ) = argmin y∈Y Φ(y; τ ).However, y(τ ) can be non-differentiable or even discontinuous w.r.t. τ , and Ψ(y(τ )) can be nonconvex 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 et al., 2022] . 
learning optimal tax in nonatomic congestion games: 
 In this section, we describe our algorithm that can learn an ϵ-optimal tax with O(F 2 β/ϵ) samples. First, we introduce piece-wise linear functions as a nonparametric way to approximate the marginal cost tax τ * [Takezawa, 2005] .Definition 3. (Piece-wise Linear Function) We use a dictionary * d = {(x 1 , y 1 ), • • • , (x n , y n )} for x i ̸ = x j , ∀i ̸ = j (w.l.o.g. we let x 1 < x 2 < • • • < x n ) to represent a piece-wise linear function d(•) on [x 1 , x n ] such that d(x) = x -x i+1 x i -x i+1 y i + x i -x x i -x i+1 y i+1 , ∀x ∈ [x i , x i+1 ].In addition, we use to represent the update method for dictionary. I.e., d (x, y) 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(x) to y.We will maintain the piece-wise function on a gridL = {0, ∆, 2∆, • • • , K∆ = 1} with K = 2β ϵ and ∆ = 1/K. The time complexity for computing d(x) is O(log K) for any x ∈ [0, 1].Algorithm 1 Tax Design for Congestion Game1: Initialize: Facility set F, number of rounds T , tolerance ϵ, smoothness β, perturbation δ = ϵ∆ 2 /8. 2: Set initial tax τ 1 : τ 1 f = {(0, 0), (1, β + ϵ)} for all f ∈ F. Set K 1 f to be {0} for all f ∈ F. 3: for t = 1, 2, . . . , T do 4:Observe Nash load y t ∈ R F and Nash cost c t ∈ R F under tax τ t .Set F to be the unknown facility set (Definition 4).Setl f = τ t f ([y t f ] - K t f ) + ϵ(y t f -[y t f ] - K t f ) and r f = τ t f ([y t f ] + K t f {1} ) + ϵ(y t f -[y t f ] + K t f {1} ) for each f ∈ F. 7: Run Algorithm 2 with input y t , c t , τ t = [τ t f (y t f )] f , F and [l f , r f ] f ∈ F . 8:if Algorithm 2 return False then 9:return τ t 10:else 11: Algorithm 2 return τ ∈ R F , f ∈ F, sign ∈ {-1, 1}.12:Apply taxτ t : τ t f = τ t f (y t f , τ t f ) + sign • δ and τ t f = τ t f (y t f , τ t f ) for f ̸ = f . 13:Observe ẏt , ċt ∈ R F as the Nash load and the Nash cost of each facility.14:Update τ t+1 and K t+1 according to (1).15:end if 16: end for In this section, we introduce our main algorithm. At each round t, we will maintain a known index set K t f ⊆ L where the marginal cost tax can be accurately estimated (Lemma 7), and use a 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τ t f = {(x t i , y t i )} i and the known index set K t f satisfies {x t i } i = K t f {1} and K t f ⊆ L.Here 1 is a special case as it is not in the known index set initially but it is needed as the boundary for the piece-wise linear function τ t f . Initially, the tax is set to beτ 1 f (u) = {(0, 0), (1, β + ϵ)} and the auxiliary tax is τ 1 f = {(0, 0), (1, β)} for f ∈ F (Line 2).Here we set τ 1 f (1) = β as β is always an upper bound on τ * f (1). The auxiliary tax τ t f is a non-decreasing piece-wice linear approximation of τ * f and we always set tax τ t f (u) = τ t f (u) + ϵu to ensure that the subgradient of the tax enforced is lower bounded by ϵ.At round t, after observing Nash equilibrium load y t ∈ R F and Nash equilibrium cost c t ∈ R F , the facilities are split into two sets: known facilities and unknown facilities. Definition 4. For each round t, facility f is known if the Nash loady t f ∈ [0, 1] satisfies [y t f ] - L ∈ K t f and [y t f ] + L ∈ K t f .Otherwise, facility 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 a result, the tax estimate for the Nash load τ t f (y t f ) will be close to the true optimal tax τ * f (y t f ) with error 2ϵ (Lemma 8). We will apply Algorithm 2 to find the exploratory tax to gather information about unknown facilities (Line 7). Proposition 1. If Algorithm 2 return False at round t, then tax τ t is an 6ϵF -optimal tax. If Algorithm 2 output τ t , f t , sign t at round t, then we have0 < y t f t -ẏt f t ≤ ∆.If Algorithm 2 output τ t , f t , sign t at round t, we update the tax and the known index set by the following rule. Foru ∈ {[y t f t ] + L , [y t f t ] - L }\K t f t (this set is not empty as f t is an unknown facility), we setEQUATIONK t+1 f t =K t f t {u}.(2)and τ t+1 f = τ t f , K t+1 f = K t f for f ̸ = f t . Then we set τ t+1 f (u) = τ t+1 f (u) + ϵu for all f ∈ F and u ∈ [0, 1].In words, we clip the two-point estimate u• c t f t -ċt f t y t f t -ẏt f ton the left and right known index of τ t f t (u) so that τ t+1 f t (u) is still a non-decreasing piece-wise linear approximation of the marginal cost tax τ * f . τ t+1 f is added with an extra linear term to guarantee a strongly convex potential function (Lemma 2).As 0 < y t f -ẏt f ≤ ∆, the two point estimate of the gradientc t f -ċt f y t f -ẏt f is accurate enough for c ′ f (u) such that τ t+1 f t (u) -τ f (u) ≤ ϵ (Lemma 6). As |K t f t |increases by 1 at round t and there are F such sets with size bounded by O(β/ϵ), Algorithm 2 will output False within at most O(F β/ϵ) rounds, which implies τ t is an ϵF -optimal tax (Proposition 1). With proper rescaling, the sample complexity for learning ϵ-optimal tax is O(F 2 β/ϵ). Theorem 1. Under Assumption 1 and Assumption 2, Algorithm 1 will output a 6ϵF tax within T ≤ 2F β/ϵ rounds. In addition, each round has at most two tax realizations. Remark 1. To uniformly approximate a β-smooth function, we have to know its value at O(β/ϵ) points [Takezawa, 2005] . For an ϵ-optimal tax, we need to estimate τ * f with ϵ/F accuracy as the error accumulates with all the facilities. As a result, we conjecture that O(F 2 β/ϵ) sample complexity is tight 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 a non-equilibrium feedback, she can still update the optimal tax estimate if the feedback provides new information. It is possible for our algorithm to find the optimal tax even if no equilibrium feedback is provided. In addition, as long as the equilibrium can be reached after applying a tax, the algorithm can always find the optimal tax.In this section, we describe Algorithm 2, which can find an exploratory tax that satisfies Proposition 1. The idea is we can observe another similar but different Nash equilibrium load by perturbing the tax. However, there are 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, we always apply taxes that have (sub)gradient lower bounded by ϵ > 0. The feasible range [l f , r f ] for updating tax τ t f with (y t f , •) guarantees that the updated tax still maintains the subgradient lower bound. By Lemma 2, the potential function is always ϵ-strongly convex. As a result, the Nash load for any feasible tax is unique and Lipschitz w.r.t. tax perturbation. To resolve Algorithm 2 Test Tax Design1: Initialize: Nash flow y ∈ R F , tax τ ∈ R F , cost c ∈ R F , unknown facility set F, unknown facility range [l f , r f ] for f ∈ F . 2: Set strategy x ∈ ϕ -1 (y). Compute commodity load y i = ϕ i (x i ) ∈ R F for i ∈ [m]. 3: Set I = False. 4: if Exists f ∈ F and i ∈ [m] such that 0 < y i (f ) < w i then 5: return τ, f, 1. 6: end if 7: for Commodity i ∈ [m] do 8: Let Fi = {f ∈ F : a:f ∈a x i,a = w i } and F′ i = {f ∈ F : a:f ∈a x i,a = 0}. 9: Set τ : τ Fi = r Fi , τ F ′ i = l F ′ i , τF\( Fi F ′ i ) = τ F \( Fi F ′ i ) .10:if Gap i (x, c + τ ) < 0 then 11:Set I = True. Set τ ′ = τ 19: for f ∈ Fi do 20: Set τ u : τ u f = u, τ u F \{f } = τ ′ F \{f } .21:Set u = argmax{u : Gap j (x, c + τ u ) ≥ 0, ∀j}.if u ≤ r f then 23:return τ u , f, 1.end ifSet τ ′ = τ r f . 26: end for 27: for f ∈ F′ i do 28:Setτ u : τ u f = u, τ u F \{f } = τ ′ F \{f } .29:Set u = argmin{u : Gap j (x, c + τ u ) ≥ 0, ∀j}.if u ≥ l f then 31:return τ u , f, -1.end ifSet τ ′ = τ l f . 34: end for the second issue, we find the tax that makes the current Nash equilibrium on the "boundary". I.e., an additional perturbation will make the Nash equilibrium change. Intuitively, this is similar to removing the slackness in a constrained optimization problem. By Lemma 3, we can observe a different Nash load on f if we make the additional perturbation. Lemma 2. If the subgradient of the cost function c f is lower bounded by ϵ > 0 for all f ∈ F, then the potential function Φ repa (y) is ϵ-strongly convex. However, Φ(x) is not necessarily strongly convex.Lemma 3. If two taxes τ and τ only differ in facility f and the Nash loads y and ẏ are different, then y f ̸ = ẏf . Definition 5. The gap for a strategy x ∈ X with cost c ∈ R F is defined asEQUATIONIn the algorithm, we use Gap i (x, c) to measure the cost gap between in-support actions and offsupport actions for commodity i and strategy x. If x is a Nash equilibrium and c is the Nash cost, then all of the in-support actions have the same minimal cost and Gap i (x, c) ≥ 0 holds. Informally, "boundary" tax τ means that Gap i (x, c + τ ) = 0 for a Nash equilibrium x and perturbing τ results in Gap i (x, c + τ ) < 0, so the Nash equilibrium under the perturbed tax will be different from x.Now we discuss how Algorithm 2 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 [l f , r f ] for each unknown facility f ∈ 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 F instead of functions. [l f , r f ] is the feasible range for the perturbed tax value at facility f . By the definition of l f and r f , current tax τ t f updated with (y t f , u), u ∈ [l f , r f ] is still a tax with subgradient lower bounded by ϵ. For the first step, the algorithm will compute strategy x ∈ ϕ -1 (y) as the Nash equilibrium strategy (Line 2). If there exists an unknown facility f and commodity i such that not all load of commodity i is using f or not using f (Line 4), then perturbing the tax at facility f will make x not longer a Nash equilibrium as in-support actions have different costs.Otherwise, for each unknown facility f 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 x not a Nash equilibrium. However, there does not exist a 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 r f and the taxes for facilities used by none of the Nash load would be the lower bound l f , thus maximizing the cost for in-support actions and minimizing the cost for off-support 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 16). As τ * is approximately within the range, y t approximately minimizes the social cost (Lemma 10).Otherwise, the algorithm finds commodity i such that x is not the Nash equilibrium under the worstcase tax (Line 11). For the last step, we gradually transform the initial tax to this worst-case tax and stop when x is not the Nash equilibrium for some commodity. Specifically, the algorithm iteratively changes the tax in the unknown facility set F = Fi F′ i (Line 19 and Line 27) to the worst-case tax. For facility f ∈ Fi , the algorithm finds the boundary tax for facility f that satisfies u = argmaxu {u : Gap j (x, c + τ u ) ≥ 0, ∀j ∈ [m]}.If u ≤ r f , we will output τ u , f, 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 is still the Nash equilibrium, and we continue for the next facility. After enumerating all the facilities in Fi , we enumerate F′ i in the same way. Eventually, the tax is transformed into the worst-case tax with negative gap for commodity i, so this process will end and output τ u , f, sign such that τ u is the tax that makes the Nash equilibrium on the boundary, f is the facility to perturb and sign is the direction to perturb the tax at f . 
conclusion: 
 We proposed the first algorithm with polynomial sample complexity for learning optimal tax in nonatomic congestion games. The algorithm leverages several novel designs to 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. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Our experiment is a direct implementation of our algorithm on a 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 to a 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, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 or 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification:Guidelines:• The answer NA means that the authors have not 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., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We did not use public dataset.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: Lemma 4. If strategy x is an ϵ-NE in a congestion game, then x is an ϵ-minimizer of the corresponding potential function Φ(•).Proof. Let x * = argmin x∈X Φ(x) and y = ϕ(x). First, we show that∇ i,a Φ(x) =∇ i,a f y f 0 c f (u)du =∇ i,a f ∈a y f 0 c f (u)du = f ∈a c f (y f )∇ i,a y f = f ∈a c f (y f )∇ i,a i ′ ,a ′ :f ∈a ′ x i ′ ,a ′ = f ∈a c f (y f ).Then we haveΦ(x) -Φ(x * ) ≤ ⟨x -x * , ∇Φ(x)⟩ (Convexity) ≤ i∈[m] ⟨x i -x * i , ∇ i Φ(x)⟩ ≤ i∈[m]   a∈Ai x i,a f ∈a c f (y f ) -min a∈Ai w i f ∈a c f (y f )   ≤ i∈[m] a∈Ai x i,a ϵ = i∈[m] w i ϵ = ϵ.Lemma 1. Φ repa is convex under Assumption 1. If y * = argmin y Φ repa (y), then for any x ∈ ϕ -1 (y * ), x is a Nash equilibrium.Proof. For y 1 , y 2 ∈ Y, we haveΦ repa (y 1 ) + Φ repa (y 2 ) -2Φ repa ( y 1 + y 2 2 ) = f   y 1 f 0 c f (u)du + y 2 f 0 c f (u)du -2 y 1 f +y 2 f 2 0 c f (u)du   .y 1 f 0 c f (u)du + y 2 f 0 c f (u)du -2 y 1 f +y 2 f 2 0 c f (u)du is nonnegative for all f ∈ F.W.l.o.g., we assume y 1 f ≤ y 2 f and we havey 1 f 0 c f (u)du + y 2 f 0 c f (u)du -2 y 1 f +y 2 f 2 0 c f (u)du = y 2 f y 1 f +y 2 f 2 c f (u)du - y 1 f +y 2 f 2 y 1 f c f (u)du = y 1 f +y 2 f 2 y 1 f c f (u + y 2 f -y 1 f 2 ) -c f (u) du ≥0,where the last step is from Assumption 1 (monotonicity). As a result, Φ repa is convex.Let y * = argmin y Φ repa (y) and x ∈ ϕ -1 (y * ). If there exists x ′ ∈ X such that Φ(x ′ ) < Φ(x), then we have Φ repa (ϕ(x ′ )) < Φ repa (y * ), which contradicts the definition of y * . As a result, x is the minimizer of Φ(•), which means x is a Nash equilibrium.Lemma 5. The Nash load under tax τ : y(τ ) = argmin y∈Y Φ(y; τ ) is not continuous w.r.t. τ . In addition, the social welfare Ψ(y(τ )) is not convex w.r.t. τ .Proof. For the first part, we construct a congestion game with two facilities f 1 , f 2 , one commodity with action set {f 1 , f 2 }, and constant cost c 1 = 1, c 2 = 1 -ϵ with ϵ > 0. Then for tax τ = 0, we have y(τ ) = [0, 1]. For constant tax τ 1 = 0, τ 2 = 2ϵ, we have y(τ ) = [1, 0]. As ϵ can be arbitrarily small, y(τ ) is not continuous w.r.t. τ .For the second part, we construct a congestion game with two facilities f 1 , f 2 , one commodity with action set {f 1 , f 2 }, and cost functionc 1 = 1, c 2 (u) = √ u for u ∈ [0, 1]. We apply constant tax τ : τ 1 = t, τ 2 = 0 for t ∈ [-1, 0]. The Nash equilibrium under tax τ is y(τ ) = [1 -(1 + t) 2 , (1 + t) 2 ]. Then the social cost is Ψ(y(τ )) = 1 -t(1 + t) 2 , which is not convex on [-1, 0].Lemma 2. If the subgradient of the cost function c f is lower bounded by ϵ > 0 for all f ∈ F, then the potential function Φ repa (y) is ϵ-strongly convex. However, Φ(x) is not necessarily strongly convex.Proof. First, by the definition of the potential function Φ, it is easy to show that ∇Φ(y) = [c f (y f )] f ∈F . For y 1 , y 2 ∈ Y, we have(∇Φ(y 1 )-∇Φ(y 2 )) ⊤ (y 1 -y 2 ) = f ∈F (c f (y 1 f )-c f (y 2 f ))(y 1 f -y 2 f ) ≥ f ∈F ϵ(y 1 f -y 2 f ) 2 = ϵ y 1 -y 2 2 2 ,which implies Φ(•) is a ϵ-strongly convex function.For the second argument, we only need to construct a congestion game such that there exists two strategy x 1 , x 2 ∈ X such that for ϕ(tx 1 + (1 -t)x 2 ) is a constant for t ∈ [0, 1], which implies the potential function Φ(tx 1 + (1 -t)x 2 ) = Φ repa (ϕ(tx 1 + (1 -t)x 2 )) is a 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 a congestion game with three facilities f 1 , f 2 , f 3 , three actions a 1 = {f 1 }, a 2 = {f 2 }, a 3 = {f 3 } and three commodities with action set {a 1 , a 2 }, {a 2 , a 3 }, {a 3 , a 1 }. Strategy x 1 :x 1 1 = [1, 0, 0], x 1 2 = [0, 1, 0], x 1 3 = [0, 0, 1] and x 2 : x 2 1 = [0, 1, 0], x 2 2 = [0, 0, 1], x 2 3 = [1, 0, 0]. Then tx 1 + (1 -t)x 2 is a feasible strategy and we have ϕ(tx 1 + (1 -t)x 2 ) = [1, 1, 1] for all t ∈ [0, 1].Lemma 3. If two taxes τ and τ only differ in facility f and the Nash loads y and ẏ are different, theny f ̸ = ẏf .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 ḟ . The potential functions areΦ(Y ) = f Y f 0 c f (u)du, Φ(Y ) = f Y f 0 ċf (u)du.By Lemma 2, Φ and Φ are strongly convex and thus the Nash equilibrium load y and ẏ are unique. Suppose y ḟ = ẏ ḟ . Consider any Y ∈ Y such that Y ḟ = y ḟ , we haveΦ(Y ) -Φ(y) = f Y f y f ċf (u)du = f ̸ = ḟ Y f y f ċf (u)du + Y ḟ y ḟ ċ ḟ (u)du = f ̸ = ḟ Y f y f c f (u)du = Φ(Y ) -Φ(y) ≥ 0.As a result, we have Φ(y) ≤ Φ( ẏ). By the optimality of ẏ, we have y = ẏ. By contradiction, if y ̸ = ẏ, we havey ḟ = ẏ ḟ . Lemma 6. If |u 1 -u 2 | ≤ ∆, then for any |u 3 -u 1 | ≤ ∆, we have c f (u 1 ) -c f (u 2 ) u 1 -u 2 -c ′ f (u 3 ) ≤ ϵ.Proof. This is a direct corollary of the β-smoothness. By mean value theorem, we havec f (u1)-c f (u2) u1-u2 = c ′ f (u) for some u ∈ [u 1 , u 2 ]. As |u -u 3 | ≤ |u -u 1 | + |u 1 -u 3 | ≤ 2∆ ≤ ϵ 2β , we have c f (u 1 ) -c f (u 2 ) u 1 -u 2 -c ′ f (u 3 ) ≤ ϵ.Lemma 7. For round t and facility f , if u ∈ K t f , then we haveτ t f (u) -τ * f (u) ≤ 2ϵ.Proof. By the algorithm design, for each u ∈ K t f , τ t f (u) will not change after u is added to K f . We will use induction on t to proveτ t f (u) -τ f (u) ≤ ϵ for u ∈ K t f . At round t = 1, K 1 f = {0} and τ 1 f (0) = τ * f (0) = 0 holds. Suppose at round t, we have K t+1 f t = K t f t {u} with u ∈ {[y t f t ] + L , [y t f t ] - L }\K t f t , and K t+1 f = K t f for f ̸ = f t .By the induction hypothesis, we only need to proveτ t+1 f t (u) -τ * f t (u) ≤ 2ϵ. Recall that τ t+1 f t (u) = clip u • c t f t -ċt f t y t f t -ẏt f t , τ t f t ([y t f t ] - K t f t ), τ t f t ([y t f t ] + K t f t {1} ) .Then we have the following three cases. For simplicity we replace f t with f .(1)τ t+1 f (u) = u • c t f -ċt f y t f -ẏt f. By Lemma 11 and Lemma 6, we haveτ t+1 f (u) -τ * f (u) = u c t f -ċt f y t f -ẏt f -uc ′ f (u) ≤ ϵ. (2) τ t+1 f (u) = τ t f ([y t f ] - K t f ) and u • c t f -ċt f y t f -ẏt f ≤ τ t f ([y t f ] - K t f). Then we haveτ t+1 f (u) = τ t f ([y t f ] - K t f ) ≤ τ * f ([y t f ] - K t f ) + ϵ ≤ τ * f (u) + ϵ,where the first inequality is from the induction hypothesis as[y t f ] - K t f ∈ K t fand the second inequality is from Assumption 2. In addition, we haveτ t+1 f (u) ≥ u • c t f -ċt f y t f -ẏt f ≥ uc ′ f (u) -ϵ = τ * f (u) -ϵ. (3) τ t+1 f (u) = τ t f ([y t f ] + K t f {1} ) and u • c t f -ċt f y t f -ẏt f ≥ τ t f ([y t f ] + K t f {1}). Then we haveτ t+1 f (u) ≤ u c t f -ċt f y t f -ẏt f ≤ uc ′ f (u) + ϵ ≤ τ * f (u) + ϵ. If [y t f ] + K t f {1} ∈ K t f , then we have τ t f (u) = τ t f ([y t f ] + K t f {1} ) ≥ τ * f ([y t f ] + K t f {1} ) -ϵ ≥ τ * f (u) -ϵ. If [y t f ] + K t f {1} = 1 and 1 / ∈ K t f , we still have τ t f (u) = β ≥ uc ′ f (u) = τ * f (u).For each of these three cases, the induction holds.As τ t f (u) = τ t f (u) + ϵu for all f ∈ F and u ∈ [0, 1], we have τ t f (u) -τ * f (u) ≤ 2ϵ.Lemma 8. For round t, if facility f is known, then we haveτ t f (y t f ) -τ * f (y t f ) ≤ 3ϵ.Proof. If y t f ∈ K t f , we can directly apply Lemma 7. Otherwise, we setu 1 = [y t f ] - L and u 2 = [y t f ] + L . Then we have u 1 < y t f < u 2 and u 1 , u 2 ∈ K t f . There exists λ 1 ∈ [0, 1], λ 1 + λ 2 = 1 such that y t f = λ 1 u 1 + λ 2 u 2 . By Lemma 6, we have τ t f (u i ) -τ * f (u i ) ≤ 2ϵ for i ∈ {1, 2}. Then we have τ t f (y t f ) -τ f (y t f ) = λ 1 τ t f (u 1 ) + λ 2 τ t f (u 2 ) -(λ 1 u 1 + λ 2 u 2 )c ′ f (u) ≤ λ 1 τ t f (u 1 ) -λ 1 u 1 c ′ f (u) + λ 2 τ t f (u 2 ) -λ 2 u 2 c ′ f (u) ≤λ 1 τ t f (u 1 ) -τ * f (u 1 ) + λ 1 u 1 c ′ f (u 1 ) -c ′ f (u) + λ 2 τ t f (u 2 ) -τ * f (u 2 ) + λ 2 u 2 c ′ f (u 2 ) -c ′ f (u) ≤2λ 1 ϵ + λ 1 ϵ + 2λ 2 ϵ + λ 2 ϵ (Lemma 6, β-smoothness and |u -u i | ≤ ϵ/β.) ≤3ϵ. Lemma 9. If Algorithm 2 return False at round t, then for any τ ∈ R F such that τ f = τ t f (y f ) for f ∈ F\ Ft and τ f ∈ [l t f , r t f ] for f ∈ Ft , we have Gap i (x t , c t + τ ) ≥ 0 for all i ∈ [m].In addition, x t is a Nash equilibrium for tax τ .Proof. For simplicity, we will omit t when there is no confusion. Algorithm 2 return False if and only if for all i ∈ [m] and tax τi :τ Fi = r Fi , τ F ′ i = l F ′ i , τF \( Fi F ′ i ) = τ F \( Fi F ′ i ) , we have Gap i (x, c + τ ) = min a:xi,a=0 f :f ∈a (c f + τf ) -max a:xi,a̸ =0 f :f ∈a (c f + τf ) ≥ 0.By the definition of Fi , for any f ∈ Fi and a : x i,a ̸ = 0, we have f ∈ a. Similarly, for any f ∈ F ′ i and a : x i,a ̸ = 0, we have f / ∈ a. Thus for any a : x i,a ̸ = 0, we havef :f ∈a (c f + τf ) - f :f ∈a (c f + τ f ) = f ∈ Fi (r f -τ f ) ≥ 0.For any a : x i,a = 0, we havef :f ∈a (c f + τf ) - f :f ∈a (c f + τ f ) = f ∈ F ′ i a (l f -τ f ) ≤ 0.As a result, we haveGap i (x t , c t + τ ) = min a:xi,a=0 f :f ∈a (c f + τ f ) -max a:xi,a̸ =0 f :f ∈a (c f + τ f ) ≥ min a:xi,a=0 f :f ∈a (c f + τf ) -max a:xi,a̸ =0 f :f ∈a (c f + τf ) ≥ 0.To prove that x t is Nash equilibrium for tax τ , we only need to show that for in-support actions a : x t i,a ̸ = 0, the action costs f :f ∈a (c t f + τ f ) are the same. This can be derived byf :f ∈a (c t f + τ t f ) - f :f ∈a (c t f + τ f ) = f ∈ Fi (τ t f -τ f ), ∀a : x t i,a ̸ = 0,which is independent of a. As x t is Nash equilibrium for tax τ t , f :f ∈a (c t f + τ t f ) is also independent of a.Lemma 10. If Algorithm 2 return False at round t, then tax τ t is an 6F ϵ-optimal tax. Proof. For known facility f , by Lemma 8, we have τ * f (y t f ) -τ t f (y t f ) ≤ 3ϵ. By Lemma 7, for any u ∈ K t f , we have τ * f (u) -τ t f (u) ≤ 2ϵ. Thus for unknown facility f , we havel t f = τ t f ([y t f ] - K t f ) + ϵ • (y t f -[y t f ] - K t f ) ≤ τ * f ([y t f ] - K t f ) + 2ϵ + ϵ = τ * f ([y t f ] - K t f ) + 3ϵ, r t f = τ t f ([y t f ] + K t f {1} ) + ϵ • (y t f -[y t f ] + K t f {1} ) ≥ τ * f ([y t f ] + K t f {1} ) -2ϵ -ϵ = τ * f ([y t f ] + K t f {1} ) -3ϵ, As τ *f is nondecreasing (Assumption 2), we havel t f -3ϵ ≤ τ * f ([y t f ] - K t f ) ≤ τ * f (y t f ) ≤ τ * f ([y t f ] + K t f {1} ) ≤ r t f + 3ϵ.Thus there exists tax τ t such that τ t f (y t f ) satisfies the condition of Lemma 9 and τ * f (y t f ) -τ t f (y t f ) ≤ 3ϵ for all f ∈ F. x t is the Nash equilibrium for tax τ t , we have∀i ∈ [m], a, a ′ ∈ A i , f ∈a c f (y t f ) + τ t f (y t f ) ≤ f ∈a ′ c f (y t f ) + τ t f (y t f ), if x t i,a > 0.Thus we have∀i ∈ [m], a, a ′ ∈ A i , f ∈a c f (y t f ) + τ * f (y t f ) ≤ f ∈a ′ c f (y t f ) + τ * f (y t f ) + 6F ϵ, if x t i,a > 0.By Lemma 4, Ψ(y t f ) -min y∈Y Ψ(y) ≤ 6F ϵ.Lemma 11. If Algorithm 2 output τ t , f t , sign t at round t, then we have0 < y t f t -ẏt f t ≤ ∆.Proof. First, we prove y t f t -ẏt f t > 0. We consider the following two cases.(1) Algorithm 2 return at Line 5. As we have 0 < y i ( f t ) < w i , there exists a, a ′ ∈ A i such that x i,a > 0, x i,a ′ > 0 and f t ∈ a, f t / ∈ a ′ . Suppose y t f t = ẏt f t . Then by Lemma 3, we have y t = ẏt as τ t and τ t only differ in facility f t . As a result, x t is Nash equilibrium for tax τ t . However, x t is the Nash equilibrium for tax τ t f impliesf ∈a c f (y t f ) + τ t f (y t f ) = f ∈a ′ c f (y t f ) + τ t f (y t f ).As τ t and τ t only differ in facility f t and f t ∈ a, f t / ∈ a ′ , we havef ∈a c f (y t f ) + τ t f (y t f ) ̸ = f ∈a ′ c f (y t f ) + τ t f (y t f ),which means x t is not the Nash equilibrium for tax τ . By contradiction, we havey t f t = ẏt f t .(2) Algorithm 2 return τ u , f , sign at Line 23 or Line 31. As there exists j ∈ [m] such that Gap j (x, c+ τ u+sign•ϵ ) < 0, x is not a Nash equilibrium under tax τ t . Let τ t : τ t f = τ t f (y t f , τ u f ) for f ∈ F. Then τ t and τ t only differs in f and x is the Nash equilibrium under tax τ t . By applying Lemma 3 with τ t and τ u , we have y t f t = ẏt f t .Second, we provey t f t -ẏt f t ≤ ∆.(1) Algorithm 2 return at Line 5. Suppose we have y t f -ẏt f > ∆. By the tax design, the (sub)gradient of the tax (τ t f ) ′ (u) ≥ ϵ for u ∈ [0, 1]. As a result, Φ(y, c + τ t ) is ϵ-strongly convex by Lemma 2. As y t = argmin y∈Y Φ(y; c + τ t ), we haveΦ( ẏt ; c + τ t ) -Φ(y t ; c + τ t ) > ϵ∆ 2 /2.However, we have |Φ(y; c + τ t ) -Φ(y; c + τ t )| ≤ δ for all y ∈ Y. Thus we haveΦ( ẏt ; c + τ t ) -δ ≤ Φ(y t ; c + τ t ) -δ/2 ≤ Φ(y t ; c + τ t ) ≤ Φ( ẏt ; c + τ t ) ≤ Φ( ẏt ; c + τ t ) + δ.Comparing to the inequality above, we have 2δ > ϵ∆ 2 /2, which is incorrect by the definition of δ.By contradiction, we have y t f -ẏt f ≤ ∆.(2) Algorithm 2 return τ u , f , sign at Line 23 or Line 31. Letτ t : τ t f = τ t f (y t f , τ u f ) for f ∈ F. Then x is the Nash equilibrium under tax τ t . Let τ : τ t f = τ t f (y t f , τ f ) for all f ∈ F.By the definition of τ t and the feasible range τ f ∈ [l f , r f ], the subgradient of τ t f is lower bounded by ϵ. As a result, Φ(•; c + τ t ) is ϵ-strongly convex on [0, 1]. We can prove y t f -ẏt f ≤ ∆ by following the analysis for case (1) and replacing τ t with τ t .Proposition 1. If Algorithm 2 return False at round t, then tax τ t is an 6ϵF -optimal tax. If Algorithm 2 output τ t , f t , sign t at round t, then we have0 < y t f t -ẏt f t ≤ ∆.Proof. This is directly from Lemma 10 and Lemma 11.Lemma 12. Algorithm 1 return False in at most KF rounds.Proof. By Lemma 11 and the update rule (1), if Algorithm 2 return τ t , f, sign at round t, then we will have one more known point, i.e.,f ∈F K t+1 f = f ∈F K t f + 1. As K t f ⊆ L for all f ∈ F and |L| = K + 1, we proved the lemma.Theorem 1. Under Assumption 1 and Assumption 2, Algorithm 1 will output a 6ϵF tax within T ≤ 2F β/ϵ rounds. In addition, each round has at most two tax realizations.Proof. The proof is directly from Proposition 1 and Lemma 12.In this section, we discuss the computation complexity of Algorithm 1 and Algorithm 2. We will show that these two algorithms can be implemented with O(poly(A, F, m)) complexity for each round. For network congestion games, the computation complexity can be sharpened to O(poly(V, E, m)), avoiding the dependence on A that can be exponential in V and E.For Algorithm 1, we compute/update the value of the cost/tax function for each facility. As we use the dictionary data structure, computing value and updating value only have O(log K) = O(log β/ϵ) complexity. As a result, the complexity of one round in Algorithm 1 is O(F ).For Algorithm 2, x ∈ ϕ -1 (y) is a Caratheodory decomposition problem and can be formulated as a linear program with A variables, F +m equation constraints and A inequality constraints (Proposition 2), which can be solved in polynomial time [Cohen et al., 2021] .u = argmax u {u : Gap j (x, c + τ u ) ≥ 0, ∀j ∈ [m]} for τ u : τ u f = u, τ u F \{f } = τ ′ F \{f } , f ∈ Fi .For simplicity, we use the notation: c u = c + τ u as the cost with tax τ u . By Definition 5 and the definition of action cost, we haveEQUATIONFor action cost c u a , if f ∈ a, it is a linear function w.r.t. u in the form of u + C for some constant C. Otherwise, it is a constant w.r.t. u. As a result, we can determine the function c u a with O(F ) computation as we only need to compute c τ ′ f a to decide the constant. Then we can compute Gap j (x, c+ τ u ) in closed form and compute u j = argmax u {u : Gap j (x, c + τ u ) ≥ 0} with O(AF ) complexity. Finally, u = min j∈[m] u j can be computed with O(mAF ) complexity. Similarly, u = argmin u {u :Gap j (x, c + τ u ) ≥ 0, ∀j ∈ [m]} has O(mAF ) computation complexity.For network congestion games, Algorithm 2 can be implemented by applying shortest path algorithms on a modified network, thus avoiding the dependence on A. We will apply Dijkstra's algorithm with O(V + E) complexity while other shortest path algorithms can be used as well.First, the Caratheodory decomposition x ∈ ϕ -1 (y) can be done efficiently with O(V E + E 2 ) steps similar to the decomposition algorithm in [Panageas et al., 2023] . 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 u = argmax u {u : Gap j (x, c + τ u ) ≥ 0, ∀j ∈ [m]}, the computation complexity can be boosted to O(m(E + V )). To achieve this, we consider how (4) changes as u increases from τ ′ f to r f . By Algorithm 2, we have Gap j (x, c + τ u ) ≥ 0 when u = τ ′ f 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 j (x, c + τ u ) ≥ 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 u + C and C can be determined by applying shortest path algorithm with edge weight c + τ τ ′ f . For off-support action cost, we observe that where the second equation is from that the action cost does not depend on u and x j,a = 0 if f / ∈ a. The first term in (5) grows linearly w.r.t. u as f ∈ 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 as the shortest path in the network after removing edge f . As a result, u j = argmax u {u : Gap j (x, c + τ u ) ≥ 0} can be computed with O(E + V ) complexity. Then the complexity for computing u = min j∈[m] u j is O(m(E + V )).Similarly, u j = argmin u {u : Gap j (x, c + τ u ) ≥ 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 τ f to l f . Initially, the gap is nonnegative. If f has all of the Nash load, then the in-support action cost is a linear function u + C and it decreases at least as fast as the first term. As a result, the gap is always nonnegative. Otherwise, f has none of the Nash load and in-support action costs remain constant.We notice the following equation: where the second equation is from that f ∈ a implies a is off-support (x j,a = 0) and f / ∈ a implies c u a is independent of u. The second term in ( 6) is a constant and is always greater than the in-support action cost. The first term in ( 6) is a linear function u and it can be determined by computing the shortest path that always uses f and with edge weights c + τ τ f . 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 f and the target node. As a result, the complexity for u = max j∈[m] u j is O(m(E + V )) as well. Thus the computation complexity for Algorithm 2 in network congestion games is O(V E + E 2 + mV + mE).Proposition 2. Finding x ∈ ϕ -1 (y) can be formulated as the following linear program.min x∈R A 1 s.t. y = i∈[m] ai∈Ai x i,ai a i w i = ai∈Ai x i,ai , ∀i ∈ [m] x i,ai ≥ 0, ∀i ∈ [m], a i ∈ A iProof. The second and third constraints guarantees x is a feasible strategy. The first constraint indicates y = ϕ(x). As a result, any feasible point of the program is a solution of ϕ -1 (y).Algorithm 3 Efficient Computation of Flow Decomposition (Modified from [Panageas et al., 2023] ) 1: Input: A load y ∈ Y. 2: x i,a = 0 for all i ∈ [m] and a ∈ A i . 3: while ∃f : y f > 0 do 4:Let A = {f : y f > 0}.Let f min = argmin f ∈A y f and y min = min f ∈A y f .Let a be a (s i , t i ) path of network G(V, A) with f min ∈ p. Proof. During the algorithm, load y will always be nonnegative: y f ≥ 0, ∀f ∈ F. For each round, we will have y fmin reduced to 0. As a result, the algorithm will end within at most E rounds.We only need to prove that path a always exists in Line (6) for each round. First, y always remains a multi-commodity flow as Line (7) will not affect the law of conservation in the network. By flow decomposition theorem, there exists simple paths a 1 , a 2 , • • • , a p such thaty = i∈[p] w i a i ,where w i > 0 are positive flow weights. As y fmin > 0, there exists a i such that f min ∈ a i . Then for any f ∈ a i , y f ≥ w i > 0. As a result, path a exists for Line (6).We implemented our algorithm and conducted experiments on a classic example known as the nonlinear variant of Pigou's example [Nisan et al., 2007] . Concretely, nonlinear variant of Pigou's example is a routing game with one source node s and one target node t. There are two edges connecting s and t. One edge has constant cost c 0 (x) = c, ∀x ∈ [0, 1] for some c ∈ [0, 1], and the other edge has polynomial cost c 1 (x) = x p . One important property of such games is the price of anarchy grows without bound as p → ∞, which urges proper tax to induce socially optimal behavior. We apply our algorithm to learn the optimal tax with different c 0 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. NeurIPS Paper Checklist38th Conference on Neural Information Processing Systems (NeurIPS 2024).* In this dictionary, key is xi and value is yi. For readers unfamiliar with the dictionary data structure, it can be regarded as a set with a special update operation. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
This 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.
strength_weakness: strength_weakness: 1. While the approach is novel, it heavily relies on theoretical constructs without introducing substantial new empirical methodologies or experimental techniques.
2. 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.
3. The paper's focus on theoretical development without sufficient empirical support may reduce its immediate relevance and usefulness to practitioners in the field.
questions: questions: 1. Can you provide empirical validation or simulation results to support the theoretical claims?
2. Can you justify the assumptions made about the smoothness and other properties of cost functions in more detail?
3. Can you compare your approach with existing tax design methods in terms of performance and applicability?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

Besides 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. 

Finally, 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.
questions: questions: See above.
limitations: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The review of the literature can be more solid. 

1.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.

[1] Harks, Tobias, et al. "Computing network tolls with support constraints." Networks 65.3 (2015): 262-285.


1.2. I encourage the authors to add a paragraph in Section 2 to discuss "Learning in Stackelberg games with bandit feedback."

1.3. There are some other recent works on congestion pricing, which is related tot the present study. 

[1] Li, Jiayang, et al. "Achieving hierarchy-free approximation for bilevel programs with equilibrium constraints." International Conference on Machine Learning. PMLR, 2023.

[2] Grontas, Panagiotis D., et al. "BIG Hype: Best intervention in games via distributed hypergradient descent." IEEE Transactions on Automatic Control (2024).

[3] Maheshwari, Chinmay, et al. "Convergent first-order methods for bi-level optimization and stackelberg games." arXiv preprint arXiv:2302.01421 (2023).


2. There are many editorial mistakes in the paper. For example, please check the title of Section 5.  

For other weaknesses, please refer to my questions.
questions: questions: My rating of the paper could be further increased if the following two questions can be appropriately answered. 

1. 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. 

2. 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: limitations: The limitations are appropriately discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

Minor comments:
- 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.
- The limitations of the proposed approach should be summarized at the end of article.
questions: 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: limitations: The limitations of the proposed approach should be summarized at the end of article.
paper_summary: paper_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.
strength_weakness: strength_weakness: - There are some typos in the paper, for instance:
  - In definition of $\epsilon$-optimal tax, it should be $\Psi(y)\leq \min \Psi(y')$ instead of $\arg\min$
  - Line 163: Marginal cost tax
- The experiment is weak: The network has only two nodes and two edges.
questions: questions: - What's $c'_f$ in the definition of marginal cost tax? Is it the derivative of the cost function?
- Need the algorithm to know the smoothness $\beta$ in advance?
limitations: limitations: Yes. The author addressed the assumptions required by the paper.

Comments: comment: Thank you for detailed reply. The applicability for variants of network congestion games seems reasonable and interesting. Since I think this work is both theoretically and empirically important for tax design, I will keep my score.
I thank the authors for the response. I have no further questions.
Thank you for your response and I will keep my rating.