Algorithms and Complexity for Congested Assignments

Jiehua Chen, Jiong Guo, Yinghui WenarXiv 2023 · DOI · arXiv

Introduction

In traditional matching theory, agents typically have preferences over discrete resources or "posts." However, many real-world allocation problems involve congestion: the utility an agent derives from a post depends not only on the post itself but also on the number of other agents assigned to it. This "congested assignment problem" is central to scenarios ranging from school choice to resource allocation in distributed systems. While the existence of stable assignments in such settings has been studied, their computational complexity remained an open question until now.

Stability in Congested Environments

This research focuses on three primary stability concepts for assignments where preferences are strictly decreasing with respect to congestion (i.e., agents always prefer fewer people at any given post):

  1. Nash Stability (NS): No agent wants to move to another post, accounting for the fact that their arrival increases that post's congestion.
  2. Envy-Freeness (EF): No agent prefers the specific assignment (post and congestion level) of another agent over their own.
  3. Competitiveness (CP): An assignment that is both envy-free and "market-clearing," meaning no agent would prefer to move to an empty post.

While previous work by Bogomolnaia and Moulin (2023) introduced these concepts, this paper establishes the computational boundaries for finding such assignments.

The Complexity Gap: Envy-Freeness vs. Competitiveness

The paper's most striking finding is the divergence in computational complexity between Envy-Freeness and Competitiveness. Counter-intuitively, the additional "market-clearing" constraint in CP actually makes the problem computationally easier to solve.

Envy-Freeness is NP-Complete

The authors prove that determining whether an envy-free assignment exists is NP-complete. This is demonstrated through a reduction from EXACT COVER BY 3 SETS (X3C). The proof involves constructing complex gadgets where agent preferences are meticulously defined to ensure that a stable, envy-free configuration corresponds exactly to a solution of the underlying combinatorial problem.

Figure 1: A gadget construction used in the reduction from X3C to prove the NP-completeness of finding an envy-free assignment.

The difficulty arises primarily when empty posts are permitted. In these cases, the search space for envy-free assignments becomes combinatorial and lacks the structural properties needed for efficient optimization. This phenomenon is referred to as the "Empty Post Paradox."

Competitiveness is Tractable

In contrast, the authors provide a polynomial-time algorithm for finding a competitive assignment (CP). The algorithm runs in $O(m^2 \cdot (n+m)^2)$ time, where $n$ is the number of agents and $m$ is the number of posts.

The tractability of CP stems from the requirement that no agent wants to move to an empty post. This constraint allows the problem to be framed using flow-based techniques. The authors develop an Iterative Flow Network algorithm that identifies "obstructions"—subsets of posts that cannot accommodate assigned agents—and systematically updates congestion requirements until a stable assignment is found or non-existence is proven.

Key Insights and Future Work

A critical observation of this work is that Envy-Freeness and Competitiveness are equivalent if and only if no post is empty. This bridge allows the use of flow networks for CP while explaining why EF remains hard in the general case.

While this paper completes the complexity landscape for decreasing preferences, future research may explore settings where agents actually prefer crowds (e.g., social venues) or investigate whether these mechanisms are strategy-proof, ensuring agents have no incentive to misrepresent their preferences.

Summary updated

Abstract

We study the congested assignment problem as introduced by Bogomolnaia and Moulin (2023). We show that deciding whether a competitive assignment exists can be done in polynomial time, while deciding whether an envy-free assignment exists is NP-complete.
BibTeX
@misc{chen2023algorithms,
  author = {Jiehua Chen and Jiong Guo and Yinghui Wen},
  title = {{Algorithms and Complexity for Congested Assignments}},
  year = {2023},
  eprint = {2312.07431},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.07431},
}
Figure