Learning Optimal Tax Design in Nonatomic Congestion Games
This work addresses inefficiencies in multiplayer games for applications like traffic management, though it is incremental as it builds on existing tax design concepts with new feedback and algorithmic components.
The paper tackles the problem of designing optimal tax mechanisms to maximize social welfare in congestion games with limited feedback, proposing a computationally efficient algorithm that achieves an ε-optimal tax with sample complexity O(βF²/ε).
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 $ε$-optimal tax with $O(βF^2/ε)$ sample complexity, where $β$ is the smoothness of the cost function and $F$ is the number of facilities.