Learning Competitive Equilibria in Exchange Economies with Bandit Feedback

Wenshuo Guo, Kirthevasan Kandasamy, Joseph Gonzalez, Michael I. Jordan, Ion Stoica

Abstract: The sharing of scarce resources among multiple rational agents is one of the classical problems in economics. In exchange economies, which are used to model such situations, agents begin with an initial endowment of resources and exchange them in a way that is mutually beneficial until they reach a competitive equilibrium (CE). The allocations at a CE are Pareto efficient and fair. Consequently, they are used widely in designing mechanisms for fair division. However, computing CEs requires the knowledge of agent preferences which are unknown in several applications of interest. In this work, we explore a new online learning mechanism, which, on each round, allocates resources to the agents and collects stochastic feedback on their experience in using that allocation. Its goal is to learn the agent utilities via this feedback and imitate the allocations at a CE in the long run. We quantify CE behavior via two losses and propose a randomized algorithm which achieves sublinear loss under a parametric class of utilities. Empirically, we demonstrate the effectiveness of this mechanism through numerical simulations.

Introduction

In an "Exchange Economy," agents start with initial endowments of resources and engage in trades until they reach a Competitive Equilibrium (CE). A CE is considered the "gold standard" for resource allocation because it satisfies two critical properties: Pareto efficiency (no agent can be made better off without making another worse off) and fairness (the allocation respects the agents' initial contributions).

Traditionally, finding a CE requires a central planner to have full knowledge of every agent's utility function—a mathematical representation of their preferences over different resource combinations. In many modern applications, such as cloud resource scheduling, users cannot provide these complex algebraic formulas. Instead, they can only provide noisy, point-wise feedback on how a specific allocation performed for them. This paper addresses the challenge of reaching a CE using only this limited "bandit feedback."

The Bandit Learning Framework

The authors frame the problem as an online learning task. In each round, the mechanism proposes an allocation and receives a noisy report of the agent's utility. The goal is to minimize the cumulative loss relative to the true equilibrium over time.

Key Components of the Mechanism

  1. Parametric Utility Modeling: The framework focuses on broad families of utilities, such as Constant Elasticity of Substitution (CES) utilities and Amdahl’s law utilities (common in data center modeling).
  2. Randomized Sampling: Unlike standard "optimistic" bandit algorithms (like UCB), which can fail in fixed-point problems like CE, this approach uses a Thompson-style randomized sampling. It samples utility parameters from a distribution centered at the current Maximum Quasi-Likelihood estimate, ensuring the resulting utility functions maintain the structural properties necessary for an equilibrium to exist.
  3. Proportional Response Dynamics (PRD): Once utility parameters are sampled, the algorithm employs PRD as a subroutine to efficiently compute the corresponding CE for that round.

Empirical Results

The algorithm's performance was evaluated through numerical simulations where the ground-truth utilities were known. The primary metric is the CE loss, which measures how far the system's state is from a formal equilibrium definition.

Cumulative CE loss over time for CES-type utility agents with varying elasticity parameters (ρ).

As shown in the figures above, the cumulative CE loss grows sublinearly across different elasticity parameters ($\rho = 0.5, 0.75, 1$). This sublinear growth is a critical result, as it implies that the average error per round vanishes as $T$ increases, confirming that the mechanism successfully learns to imitate the true competitive equilibrium despite starting with no knowledge of agent preferences.

Discussion and Future Directions

This work provides a robust theoretical and empirical foundation for learning fair allocations in unknown environments. A key insight is the superiority of randomized sampling over optimistic methods for equilibrium problems.

However, several avenues for future research remain:

  • Truthfulness: The current model assumes agents report their performance honestly. In competitive settings, agents might manipulate feedback to secure more resources, necessitating the integration of incentive compatibility.
  • Non-Parametric Models: Moving beyond fixed parametric classes would increase the flexibility of the mechanism for more complex, real-world utility functions.
  • Dynamic Preferences: Extending the framework to handle non-stationary or contextual preferences (where needs change over time) would be a valuable next step for practical deployment in dynamic systems like cloud clusters.

Summary updated

Abstract

The sharing of scarce resources among multiple rational agents is one of the classical problems in economics. In exchange economies, which are used to model such situations, agents begin with an initial endowment of resources and exchange them in a way that is mutually beneficial until they reach a competitive equilibrium (CE). The allocations at a CE are Pareto efficient and fair. Consequently, they are used widely in designing mechanisms for fair division. However, computing CEs requires the knowledge of agent preferences which are unknown in several applications of interest. In this work, we explore a new online learning mechanism, which, on each round, allocates resources to the agents and collects stochastic feedback on their experience in using that allocation. Its goal is to learn the agent utilities via this feedback and imitate the allocations at a CE in the long run. We quantify CE behavior via two losses and propose a randomized algorithm which achieves sublinear loss under a parametric class of utilities. Empirically, we demonstrate the effectiveness of this mechanism through numerical simulations.
BibTeX
@inproceedings{guo2022learning,
  author = {Wenshuo Guo and Kirthevasan Kandasamy and Joseph Gonzalez and Michael I. Jordan and Ion Stoica},
  title = {{Learning Competitive Equilibria in Exchange Economies with Bandit Feedback}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=2TE1SSj9v_},
}
Figure