Approximate Nash Equilibrium Learning for n-Player Markov Games in Dynamic Pricing
This work addresses the challenge of finding equilibria in multi-agent dynamic pricing for oligopolistic markets, representing an incremental advancement in applying model-free learning to complex game-theoretic environments.
The paper tackles the problem of learning approximate Nash equilibria in competitive Markov games, specifically in dynamic pricing, where exact equilibria are intractable due to high dimensionality, and demonstrates that their method can learn such equilibria effectively.
We investigate Nash equilibrium learning in a competitive Markov Game (MG) environment, where multiple agents compete, and multiple Nash equilibria can exist. In particular, for an oligopolistic dynamic pricing environment, exact Nash equilibria are difficult to obtain due to the curse-of-dimensionality. We develop a new model-free method to find approximate Nash equilibria. Gradient-free black box optimization is then applied to estimate $ε$, the maximum reward advantage of an agent unilaterally deviating from any joint policy, and to also estimate the $ε$-minimizing policy for any given state. The policy-$ε$ correspondence and the state to $ε$-minimizing policy are represented by neural networks, the latter being the Nash Policy Net. During batch update, we perform Nash Q learning on the system, by adjusting the action probabilities using the Nash Policy Net. We demonstrate that an approximate Nash equilibrium can be learned, particularly in the dynamic pricing domain where exact solutions are often intractable.