Weighted EF1 and PO Allocations with Few Types of Agents or Chores

Jugal Garg, Aniket Murhekar, John Qin

Abstract

Dividing indivisible chores fairly and efficiently is a fundamental problem in algorithmic fair division, particularly when agents have different entitlements or "weights." This paper investigates the existence and computation of allocations that satisfy weighted envy-freeness up to one item (wEF1) and fractional Pareto-optimality (fPO). The authors demonstrate that such allocations always exist and can be found in polynomial time for two significant cases: when there are at most three types of agents or at most two types of chores. These findings provide a substantial advancement toward solving the general existence problem for fair and efficient chore allocation.

Introduction

In the field of fair division, "chores" represent items with negative utility, such as unpleasant tasks or responsibilities. Unlike "goods," which everyone desires, chores must be distributed such that no agent feels unfairly burdened. The challenge intensifies when agents have different weights, reflecting unequal responsibilities or status (e.g., a senior staff member vs. an intern).

The two primary desiderata are:

  1. Fairness (wEF1): An allocation is weighted envy-free up to one item if, after removing at most one chore from an agent's bundle, no other agent envies them, accounting for their respective weights.
  2. Efficiency (PO/fPO): An allocation is Pareto-optimal (PO) if no agent can be made better off without making another worse off. Fractional Pareto-optimality (fPO) is a stronger condition, implying efficiency even if chores could be shared fractionally.

While EF1 and PO allocations are known to exist for goods, their existence for chores in the general case remains one of the most prominent open problems in the field. This research tackles the weighted version of this problem by focusing on structured instances.

Methodology

The authors combine two distinct algorithmic frameworks to achieve their results:

  • Weighted Picking Sequences (WPS): This is a decentralized mechanism where agents pick chores in a specific order determined by their weights. The authors establish new mathematical properties of WPS, showing it can be a robust tool for maintaining fairness in weighted settings.
  • Competitive Equilibrium (CE): Borrowing from market theory, chores are assigned "payments." Agents are motivated to perform chores to reach a specific earning target. By ensuring agents only perform chores that offer the "minimum pain-per-buck," the resulting allocations naturally satisfy fPO.

For the three-agent-type case, the algorithm groups agents by their preference profiles. It uses a sophisticated process of chore transfers and payment adjustments to resolve envy between these groups while maintaining the market equilibrium. For the two-chore-type case, a "pivot" agent strategy is employed to redistribute chores until weighted fairness is achieved across the entire system.

Key Insights

A central insight of this work is that the difficulty of fair division often scales with the variety of preferences (agent types) rather than the total number of agents. By limiting the problem to three types of agents—where all agents of a single type share the same utility function—the problem becomes computationally tractable even for a large population.

Furthermore, the authors highlight the "Weighting Trap": a common intuition is to handle weights by "cloning" agents (e.g., treating an agent with weight 2 as two agents with weight 1). However, they provide a counter-example demonstrating that this naive approach fails to guarantee wEF1, necessitating the more complex equilibrium-based methods developed in the paper.

Results

The paper's primary contributions are summarized in the following table, which compares the new results against the existing state-of-the-art.

Comparison of existence and complexity results for EF1 and wEF1 chore allocations. The blue cells highlight the new contributions of this paper.

The main breakthroughs include:

  • Theorem 1: For any number of agents belonging to at most three preference types, a wEF1 and fPO allocation exists and can be computed in polynomial time. This significantly generalizes previous results that were limited to three individual agents.
  • Theorem 2: For instances with only two types of chores, a wEF1 and fPO allocation exists and is polynomially computable, regardless of the number of agents or their weight distribution.

In both scenarios, the algorithms achieve the strong efficiency guarantee of fPO, which is more restrictive and desirable than standard PO.

Conclusion and Future Work

This research provides a significant step forward in the study of fair chore allocation. By successfully addressing the weighted setting for few agent or chore types, the authors have narrowed the gap toward solving the general additive case. Future research may look to extend these potential function arguments to $k$ types of agents or explore the relationship between wEF1 and other fairness notions like Maximin Share (MMS) in the weighted chore context. The "General Additive" case remains the ultimate challenge in this domain.

Summary updated

BibTeX
@inproceedings{garg2024weighted,
  author = {Jugal Garg and Aniket Murhekar and John Qin},
  title = {{Weighted EF1 and PO Allocations with Few Types of Agents or Chores}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=zVCYBMKT1q},
}
Figure