2024/02/12 by Qiwen Cui, Maryam Fazel, Cui, Qiwen +3 · 1 citation
Business, Management and Accounting · Economics, Econometrics and Finance · #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #Corporate Taxation and Avoidance #FOS: Computer and information sciences #Fiscal Policy and Economic Growth #Machine Learning (cs.LG) #Multiagent Systems (cs.MA) #Taxation and Compliance Studies
paper · pdf · doi:10.48550/arxiv.2402.07437
openalex publication_date 2024/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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(βF2/ε) sample complexity, where β is the smoothness of the cost function and F is the number of facilities.