Optimizing Mechanism Parameters for Markov Games under Policy-Space Equilibrium Constraints

Mechanism parameter optimization seeks to align the strategic behavior of players with global system objectives. While this problem is tractable in games with closed-form equilibrium solutions, extending it to Markov games remains challenging. The presence of stochastic transitions and high-dimensional state spaces precludes closed-form equilibrium characterization, necessitating computationally intensive multi-agent reinforcement learning (MARL) methods for equilibrium computation. Embedding such methods within an outer black-box optimization loop over mechanism parameters incurs substantial computational cost. We propose a gradient-based framework for optimizing mechanism parameters in two-player Markov games under quantal response equilibrium constraints. Our approach addresses the lack of differentiability in MARL-based equilibrium computation through two key components. First, we iteratively construct and evolve a manageable set of representative policies as mechanism parameters vary, mitigating the intractability of the full policy space. Second, we apply implicit differentiation to the equilibrium conditions over these representative policies, yielding gradient signals that enable efficient parameter optimization. We theoretically show that the surrogate gradient computed from the representative policy set approximates the full-space gradient, and analyze the convergence of gradient descent driven by this surrogate gradient. We evaluate our framework on two mechanism optimization settings: transition dynamics modification and reward function revision. Specifically, we consider minimizing unfairness in Kuhn Poker and balancing productivity and equality in the AI Economist environment. Experiments show that our framework outperforms the baselines in solution quality and search efficiency.