The Complexity of Fairness Through Equilibrium

Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein

Abstract

While economists have proven that "approximately fair" allocations of indivisible goods always exist, this research demonstrates that finding them is computationally intractable. By applying the tools of computational complexity theory to the problem of Approximate Competitive Equilibrium with Equal Incomes (A-CEEI), the authors prove that finding the guaranteed approximate equilibrium is PPAD-complete, while finding a better-than-guaranteed approximation is NP-hard. These results establish a formal boundary between economic existence and algorithmic feasibility.

Introduction

In resource allocation, the challenge of distributing indivisible goods—such as university course seats or medical residency slots—fairly and efficiently is a perennial problem. Economists frequently advocate for the Competitive Equilibrium with Equal Incomes (CEEI) model. In this framework, participants are given equal budgets of a fictional currency to bid on items. In a divisible market (like commodities), a price equilibrium exists where every participant receives their most preferred affordable bundle and the market clears perfectly.

However, most real-world resources are indivisible; one cannot take a fraction of a specific seminar. For these goods, a perfect CEEI often does not exist. In 2011, Eric Budish proposed a solution: the Approximate CEEI (A-CEEI). He proved that an allocation always exists that is nearly fair, nearly efficient, and nearly clears the market. While this mechanism has been adopted by institutions like the Wharton School, Budish’s proof was non-constructive. It established that a solution exists but did not provide an efficient algorithm to find it. This paper addresses that gap by analyzing the computational complexity of finding A-CEEI allocations.

Methodology: Economic Gadgets and Reductions

The authors utilize Computational Complexity Theory to categorize the difficulty of the A-CEEI problem. Their approach relies on two primary reductions:

1. PPAD-Completeness and GCIRCUIT

To prove the problem lies within the class PPAD (Polynomial Parity Arguments on Directed graphs)—the same class containing the problem of finding a Nash Equilibrium—the authors reduce it from GCIRCUIT. They construct "economic gadgets," which are specific configurations of students, courses, and capacities that simulate logic gates (e.g., NOT, AND, OR). In this simulated market, the equilibrium prices of specific courses represent signal values in a circuit. This construction demonstrates that finding an equilibrium is equivalent to finding a fixed point in a complex directed graph.

2. NP-Hardness and 3SAT-5

To explore the limits of approximation, the authors perform a reduction from 3SAT-5 (a restricted version of the Boolean satisfiability problem). This allows them to show that while an approximate solution is guaranteed to exist, finding a solution that is significantly "better" or "tighter" than the standard theoretical bound is computationally equivalent to solving an NP-hard problem.

Key Insights

The Fixed-Point Connection

The existence of A-CEEI is mathematically rooted in Kakutani’s fixed-point theorem. The authors show that problems whose existence is guaranteed by such theorems are inherently tied to the PPAD complexity class. This suggests that the difficulty of finding fair allocations is not a flaw of specific algorithms, but a fundamental property of the equilibrium itself.

Prices as Logic Gates

A central contribution of the paper is the creative use of market mechanics to mimic computation. For instance, the authors designed a "NOT gadget" where the market is structured such that, in equilibrium, the price of an "output course" must be $1 - P$, where $P$ is the price of the "input course." By chaining these gadgets, they prove that a market can, in effect, perform arbitrary computations.

The Limits of Approximation

The paper clarifies that the approximation bound discovered by Budish ($\alpha = \sqrt{kM/2}$) represents a "computational frontier." Attempting to find an allocation with a clearing error significantly smaller than this bound is not just difficult, but NP-hard, meaning no efficient algorithm is likely to exist for the general case.

Results and Implications

  • Theorem 2 (PPAD-Completeness): Finding the A-CEEI guaranteed by Budish’s existence theorem is PPAD-complete. This implies that no polynomial-time algorithm exists unless $P = PPAD$, a condition widely considered unlikely in computer science.
  • Theorem 3 (NP-Hardness): It is NP-hard to distinguish between instances where an exact CEEI exists and instances where no A-CEEI exists that improves upon the standard theoretical guarantee.

Conclusion

This research highlights a significant "Practical Paradox." While the paper proves that finding A-CEEI is intractable in the worst case, heuristic algorithms used in practice (such as those at Wharton) often find high-quality solutions relatively quickly. This suggests that real-world student preferences may possess specific structural properties that avoid the "hard" instances constructed in these proofs. Future work is needed to identify these properties and bridge the gap between theoretical complexity and empirical success.

Summary updated

BibTeX
@article{othman2014complexity,
  author = {Abraham Othman and Christos H. Papadimitriou and Aviad Rubinstein},
  title = {{The Complexity of Fairness Through Equilibrium}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2014},
  doi = {10.1145/2600057.2602855},
}
Figure