Welfare Maximization in Competitive Equilibrium: Reinforcement Learning for Markov Exchange Economy

Zhihan Liu, Miao Lu, Zhaoran Wang, Michael I. Jordan, Zhuoran YangICML 2022 · OpenReview

Introduction

Many real-world systems, ranging from tax policy design to cloud resource allocation, operate on a "bilevel" structure. In these systems, a central planner (such as a government or system administrator) aims to steer the environment toward a broad social goal, while individual agents (like citizens or developers) act strictly in their own self-interest.

Traditionally, these dynamics are studied as Exchange Economies (EE), where agents trade resources to reach a Competitive Equilibrium (CE). However, standard EE models are often static and assume that everyone's utility functions—how much they value a given resource—are perfectly known. In reality, these systems are dynamic: actions taken today affect the state of the world tomorrow, and the underlying values and transition rules are often unknown.

This paper introduces the Markov Exchange Economy (MEE), a novel framework that bridges classic exchange economics with dynamic Markov Decision Processes. The central challenge it addresses is designing learning algorithms capable of finding the optimal policy for both the planner and the agents simultaneously, even when the environment's rules and agent preferences are unknown.

The Markov Exchange Economy (MEE) Framework

The MEE framework adds a crucial temporal dimension to the traditional exchange economy. In this model, the central planner’s actions influence how resources (endowments) and contextual states evolve over time. To solve the MEE, the authors develop the first provably efficient multi-agent reinforcement learning (MARL) algorithms that simultaneously achieve competitive equilibrium for agents and social welfare maximization for the planner.

1. Online Learning: MOLM

For settings where the learner can actively interact with the environment, the authors propose MOLM (Model-based Optimistic online Learning for MEE). MOLM relies on the Optimism in Face of Uncertainty (OFU) principle. It constructs "confidence sets" of possible utility functions and transition models, selecting the most optimistic ones to encourage exploration. At each step, it utilizes a "CE Oracle" to solve the agents' subgame.

MOLM Algorithm Pseudocode

2. Offline Learning: MPLM

For learning from a fixed historical dataset without active exploration, the authors introduce MPLM (Model-based Pessimistic offline Learning for MEE). This algorithm employs the Pessimism principle to avoid overestimating the value of actions that are not well-represented in the data. This effectively mitigates the "distribution shift" between the historical dataset and the optimal policy.

Crucially, both MOLM and MPLM support General Function Approximation (such as neural networks or kernels), enabling them to scale to the massive, continuous state spaces typical of real economic systems.

Key Theoretical Insights

  • Joint Suboptimality Metric: The authors derive a novel mathematical metric that characterizes joint optimality as a fixed-point problem. They prove that if this single metric reaches zero, the system has successfully achieved both Competitive Equilibrium for the agents and Social Welfare Maximization (SWM) for the planner.
  • Fairness as a Byproduct: A significant theoretical contribution is the proof that by solving for CE and SWM, the algorithms inherently achieve Fair Division. This guarantees that agents have an incentive to participate (Sharing Incentive) and that the resulting allocation is Pareto Efficient—meaning it cannot be improved for one person without making someone else worse off.
  • Bridging RL and Economics: The research successfully imports advanced RL concepts, such as the Eluder Dimension (a measure of function class complexity), into the domain of general equilibrium theory.

Experimental Setup and Results

While the paper is heavily focused on theoretical guarantees, the authors validate their findings using a synthetic MEE environment consisting of 10 contextual states, 5 planner actions, 3 types of goods, and 3 agents with randomly generated linear utility functions.

The paper provides rigorous "regret bounds" that quantify the learning efficiency of the algorithms:

  • Online Performance: MOLM achieves a sublinear regret of $\tilde{O}(\sqrt{dH^4N^2K})$. In practical terms, as the number of episodes ($K$) increases, the average error the algorithm makes steadily drops toward zero. In simulations, MOLM's regret flattens out sublinearly, significantly outperforming a random baseline whose regret grows linearly.
  • Offline Performance: MPLM finds a policy where the suboptimality decays at a rate of $1/\sqrt{K}$, provided the historical dataset maintains "partial coverage" of the optimal paths.

Limitations and Future Directions

  • Discrete Planner Actions: The current framework assumes the central planner chooses from a discrete set of actions. Extending this to continuous action spaces (e.g., fine-grained tax rates) is a natural next step.
  • Transition Dependencies: The model assumes state transitions depend on the planner's actions but not directly on the agents' specific trades, even though agent actions do affect the planner's rewards.
  • Computational Overhead: The algorithms rely on a "CE Oracle" to solve the agents' subgame at every timestep. While theoretically sound, developing highly efficient implementations of this oracle for high-dimensional, real-world settings remains an ongoing engineering challenge.

Summary updated

Abstract

We study a bilevel economic system, which we refer to as a <em>Markov exchange economy</em> (MEE), from the point of view of multi-agent reinforcement learning (MARL). An MEE involves a central pla...
BibTeX
@inproceedings{liu2022welfare,
  author = {Zhihan Liu and Miao Lu and Zhaoran Wang and Michael I. Jordan and Zhuoran Yang},
  title = {{Welfare Maximization in Competitive Equilibrium: Reinforcement Learning for Markov Exchange Economy}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=QbhWWszMTw3},
}
Figure