Online Learning of Competitive Equilibria in Exchange Economies

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

TL;DR

This paper introduces a novel online learning mechanism for resource allocation in exchange economies where agent preferences (utilities) are initially unknown. The algorithm learns these preferences from bandit feedback and achieves competitive equilibrium (CE) allocations that are both fair and efficient, with theoretical guarantees of sublinear loss. This work is significant because it tackles the practical challenge of computing fair and efficient resource allocations without prior knowledge of user needs, a common issue in systems like data centers.

What Problem Does This Paper Address?

In many real-world scenarios, such as sharing computational resources in a data center, we need to allocate scarce resources among multiple users (agents) in a way that is both efficient (making good use of resources) and fair (satisfying users equitably). Exchange economies provide a theoretical framework for modeling this, where agents trade resources until they reach a "competitive equilibrium" (CE). A CE guarantees Pareto efficiency and fairness. However, a major hurdle in applying this framework is that we often don't know the agents' exact preferences (their utility functions) beforehand. Agents might not be able to precisely quantify how much they value different resource allocations. This paper addresses this gap by proposing a method to learn these unknown agent utilities through online interaction and then use this learned information to compute fair and efficient CE allocations.

Methods

The core of this paper is a randomized online learning algorithm designed to learn agent utilities and compute CE allocations simultaneously. The mechanism operates in rounds:

  1. Allocation: The central mechanism allocates resources to agents.
  2. Feedback: Agents provide stochastic feedback (e.g., performance metrics) about their experience with the allocated resources. This feedback is assumed to be related to their true utility.
  3. Learning: The mechanism uses this feedback to update its estimates of agent utilities.
  4. CE Computation: Based on the learned utilities, the mechanism computes a CE allocation for the next round.

A key innovation is the use of a randomized sampling strategy inspired by Thompson Sampling. This strategy balances exploration (trying different allocations to learn utilities) and exploitation (using current best estimates to achieve good allocations). The algorithm is designed for a specific, yet general, parametric class of utility functions (including CES and Amdahl's utilities) that are common in economics and systems literature. The authors also define two loss functions: one directly measuring deviation from a CE, and another based on fairness and Pareto-efficiency desiderata for fair division.

Datasets

Not discussed in the paper. The experiments are based on simulations using synthetic utility functions.

Key Insights and Ideas

  • Learning CE without knowing utilities is possible: The paper demonstrates that it's feasible to learn and achieve competitive equilibria even when agent preferences are initially unknown, relying solely on bandit feedback.
  • Thompson Sampling for CE: Adapting Thompson Sampling principles to the CE computation problem is a novel approach that effectively balances exploration and exploitation in this complex setting.
  • Two distinct loss metrics: Defining both a CE-centric loss and a fair-division-centric loss highlights that these objectives, while related, are not identical and require different analytical considerations.
  • Parametric utility class is key: The theoretical guarantees are derived for a specific parametric class of utilities, which is broad enough to cover many practical scenarios but also allows for tractable analysis.
  • CE computation as a subroutine: The CE computation itself is treated as a subroutine within the learning framework, leveraging existing efficient algorithms like Proportional Response Dynamics.

Key Results

The paper presents theoretical guarantees for their randomized algorithm. It shows that the algorithm achieves sublinear loss in both the CE loss and the fair division loss, specifically O(√T) (where T is the number of rounds) with high probability and in expectation, under certain conditions. This means the algorithm gets progressively better at learning utilities and achieving fair/efficient allocations as more rounds are completed. Empirical results with CES and Amdahl's utilities demonstrate that the CE loss decreases as the number of rounds increases, validating the theoretical findings.

Limitations and Future Work

  • Parametric Utility Assumption: The theoretical results are derived for a specific parametric class of utility functions. While this class is broad, it doesn't cover all possible utility functions. Relaxing this assumption is a significant avenue for future work.
  • Computational Complexity of FD Loss: Computing the fair division (FD) loss is computationally expensive, requiring approximation of the Pareto front. This limited its evaluation in the experiments, with a focus on the CE loss. Developing more efficient ways to compute or bound the FD loss is an open problem.
  • Static Preferences: The current model assumes agent utilities are static. Future work could explore scenarios where utilities change over time or are influenced by contextual information.
  • Single-Resource vs. Multi-Resource Exchange: The paper highlights that learning in multi-resource exchange economies is significantly more challenging than single-resource settings due to the possibility of trading different resource types. The proposed techniques are tailored for this more complex multi-resource scenario.

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{guo2022online,
  author = {Wenshuo Guo and Kirthevasan Kandasamy and Joseph E. Gonzalez and Michael I. Jordan and Ion Stoica},
  title = {{Online Learning of Competitive Equilibria in Exchange Economies}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2022},
  url = {https://openreview.net/forum?id=2TE1SSj9v_},
}
Figure