Computing fair chore markets is as hard as difficult math problems

The Complexity of Computing a Competitive Equilibrium in Fisher Markets with Chores

Computer Science and Game Theory

Summary

This paper studies how hard it is to find fair prices and payments when people have chores to do instead of things they want. The authors show that exactly calculating these fair solutions is very challenging, as it requires solving complex mathematical problems. They also find some special cases where it is easier to compute these fair outcomes efficiently. This helps us understand which chore-sharing situations can be solved fairly with a computer and which cannot.

What this means in practice

  • For market designers: Know which chore-sharing markets can have their fair prices computed efficiently and which require complex approximations.
  • For optimization software developers: Understand computational limits when building tools to calculate competitive equilibria in markets involving chores and constraints.

A theory result. No direct application yet.

Authors

Christian Kroer, Ruta Mehta, Tianlong Nan

Abstract

We study the complexity of computing competitive equilibria in Fisher markets with divisible chores and positive rational disutility coefficients and earning requirements. For linear disutilities, we prove that exact equilibrium computation is CLS-complete. In particular, the problem remains CLS-hard even when the earning requirements are binary in $1$ and $2^k$, where $k$ is an integer. We prove hardness by encoding the first-order conditions of a box-constrained quadratic program in equilibrium prices and earning flows, using a compact minimum-cost flow construction. For convex constant-elasticity-of-substitution (CES) disutilities, exact equilibrium prices may be irrational. We formulate the problem of finite-precision equilibrium price computation, in which we seek rational prices with a certified market clearing error at most a given rational tolerance encoded in binary. We prove that this problem is CLS-complete for every fixed rational exponent $ρ>1$. To prove this hardness, we encode a quartic polynomial through the fourth-order expansion of the CES price potential function corresponding to the Eisenberg-Gale (EG) dual program, and show that every sufficiently accurate approximate equilibrium of the constructed market lies near uniform prices. Additionally, we also identify a tractable special case of chores Fisher markets. In particular, we provide a strongly polynomial algorithm for exact equilibrium computation in linear markets whose disutility matrix has rank at most two and earning requirements are arbitrary positive rationals. For $n$ agents and $m$ chores, the algorithm uses $O(nm(n+m))$ rational arithmetic operations and comparisons, with polynomial intermediate encoding length.