Learning Optimal Tax Design in Nonatomic Congestion Games
Qiwen Cui Maryam Fazel Simon S. Du
We study how to learn the optimal tax design to maximize the efficiency in
nonatomic congestion games. It is known that self-interested behavior among the
players can damage the system's efficiency. Tax mechanisms is a common method
to alleviate this issue and induce socially optimal behavior. In this work, we
take the initial step for learning the optimal tax that can minimize the social
cost with \emph{equilibrium feedback}, i.e., the tax designer can only observe
the equilibrium state under the enforced tax. 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,
our algorithm leverages several novel components: (1) piece-wise linear tax to
approximate the optimal tax; (2) an extra linear term to guarantee a strongly
convex potential function; (3) efficient subroutine to find the ``boundary''
tax. 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.