Allocating Goods on a Graph to Eliminate Envy

Yann Chevaleyre, Ulle Endriss, Nicolas MaudetAAAI 2007 · OpenReview

Abstract

We introduce a distributed negotiation framework for multi-agent resource allocation where interactions between agents are limited by a graph defining a negotiation topology. A group of agents may only contract a deal if that group is fully connected according to the negotiation topology. An important criterion for assessing the quality of an allocation of resources, in terms of fairness, is envy-freeness: an agent is said to envy another agent if it would prefer to swap places with that other agent. We analyse under what circumstances a sequence of deals respecting the negotiation topology may be expected to converge to a state where no agent envies any of the agents it is directly connected to. We also analyse the computational complexity of a related decision problem, namely the problem of checking whether a given negotiation state admits any deal that would both be beneficial to every agent involved and reduce envy in the agent society.

Introduction

In multi-agent systems, the fair distribution of resources—such as tasks, bandwidth, or physical goods—is a fundamental challenge. A standard benchmark for fairness is envy-freeness, a state where no agent prefers the bundle of goods held by another agent over their own. While traditional economic models often assume a centralized authority or a fully connected network where any two agents can trade, real-world scenarios are frequently constrained by physical or social networks.

This paper investigates resource allocation within a negotiation topology: an undirected graph where edges represent the ability of agents to interact and trade. In such a system, the authors explore whether local, self-interested negotiations can lead to a globally fair outcome and the computational costs associated with finding such trades.

The Framework: Localized Fairness and Trading

The authors introduce the concept of Graph Envy-Freeness (GEF). In a restricted network, requiring an agent to be satisfied with every other agent's bundle is often unrealistic, especially if they cannot observe or interact with distant agents. GEF relaxes this requirement: an agent is satisfied if they do not envy any of their immediate neighbors in the graph.

To reach this state, agents engage in clique-deals—negotiations that occur within a fully connected subgroup (a clique) of the negotiation topology. However, purely rational trading (where agents only move if they gain personal utility) is often insufficient to eliminate envy if the initial distribution is highly skewed. To address this, the authors propose a specific monetary mechanism:

  1. Initial Equitability Payments: A one-time redistribution of wealth at the start of the process to compensate for unfair initial holdings.
  2. Globally Uniform Payment Function (GUPF): A side-payment scheme that acts as a "tax and dividend" system. When a trade generates a surplus, the GUPF redistributes that surplus across the entire society, ensuring that the benefits of local trades are felt globally.

Convergence to Fairness

A central contribution of the paper is determining the conditions under which local trades will eventually result in a state of Graph Envy-Freeness. The authors prove that convergence is guaranteed if agents possess supermodular valuations. In this context, supermodularity means that agents view goods as complements—the value of a bundle is greater than the sum of the values of individual items.

Theorem 1 (Convergence): Given supermodular valuations and the GUPF payment scheme (following initial equitability payments), any sequence of rational clique-deals will eventually result in a state where no neighbor envies another. This demonstrates that local interactions can indeed achieve a specific form of social equilibrium, provided the underlying preferences and tax structures are aligned.

The Complexity of Envy Reduction

While the authors prove that a fair state is reachable, they also uncover a significant algorithmic hurdle. They analyze the "Welfare Improvement with Envy Reduction" problem: the task of identifying a trade that is both individually rational (beneficial to the participants) and reduces the overall "degree of envy" in the system.

Theorem 2 (Complexity): Deciding whether such a trade exists is NP-complete. This suggests a "complexity paradox": while a sequence of trades is guaranteed to converge to a fair state eventually, finding the specific trades that move the system toward that goal at any given step is computationally difficult as the number of agents and goods increases.

Conclusion and Future Work

This research highlights the delicate balance between local autonomy and global fairness. By relativizing efficiency and envy to a graph, the authors provide a more realistic model for distributed resource allocation. However, the reliance on supermodular valuations and the necessity of an initial wealth redistribution may limit applicability in purely free-market environments where agents are resistant to "initial taxes."

Future research directions include exploring the reachability of high-welfare states—which the authors suspect may be PSPACE-complete—and developing heuristic or approximation algorithms to bypass the NP-completeness of identifying envy-reducing deals in practice.

Summary updated

Abstract

We introduce a distributed negotiation framework for multi-agent resource allocation where interactions between agents are limited by a graph defining a negotiation topology. A group of agents may only contract a deal if that group is fully connected according to the negotiation topology. An important criterion for assessing the quality of an allocation of resources, in terms of fairness, is envy-freeness: an agent is said to envy another agent if it would prefer to swap places with that other agent. We analyse under what circumstances a sequence of deals respecting the negotiation topology may be expected to converge to a state where no agent envies any of the agents it is directly connected to. We also analyse the computational complexity of a related decision problem, namely the problem of checking whether a given negotiation state admits any deal that would both be beneficial to every agent involved and reduce envy in the agent society.
BibTeX
@inproceedings{chevaleyre2007allocating,
  author = {Yann Chevaleyre and Ulle Endriss and Nicolas Maudet},
  title = {{Allocating Goods on a Graph to Eliminate Envy}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=rybJjalubB},
}
Figure