Learning Optimal Tax Design in Nonatomic Congestion Games

Thanks for your appreciation! We address your questions below.

• Typos: Thanks for pointing out the typos! We will correct them in the final version.
• Definition of the marginal cost function $c'_f$: Yes it is the derivative of the cost function.
• 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.

Thanks for your appreciation! We address your questions below.

• 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.
• 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.
• 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$).

Thanks for your appreciation! We address your questions below.

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

Thanks for your appreciation! We address your questions below.

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

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.

Chen, Po-An, and Chi-Jen Lu. "Generalized mirror descents in congestion games." Artificial Intelligence 241 (2016): 217-243.

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.

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