Competitive Equilibrium in Labor Economies through the Lens of Goods and Chores Fisher Markets

Bhaskar Ray Chaudhury, Christian Kroer, Ruta Mehta, Tianlong Nan, Zongjun YangarXiv 2026 · arXiv

TL;DR

This paper introduces a unified, two-sided labor market framework that elegantly couples classical Fisher markets for goods (demand side) and chores (supply side). Despite the notorious non-convexity typically introduced by chores, the authors prove that the demand side stabilizes the market, resulting in a convex set of equilibrium prices and enabling polynomial-time algorithms for computing exact competitive equilibria.

What Problem Does This Paper Address?

In traditional economic market design, Fisher markets are usually one-sided: either agents spend a fixed budget to maximize utility from a set of goods, or they accept a set of chores (bads) to meet a specific earning requirement while minimizing disutility. Real-world labor platforms like Upwork, Fiverr, or Amazon Mechanical Turk don't fit neatly into either bucket. They are inherently two-sided: employers (users) have fixed budgets to buy task completions, while gig workers exhibit "income-targeting behavior"—setting daily or weekly earning goals and trying to minimize their labor pain to get there.

Prior work on chores-only markets revealed a highly fractured mathematical landscape: the equilibrium sets can be non-convex or even disconnected, making exact equilibrium computation notoriously difficult (and PPAD-hard in general exchange economies). This paper tackles a fundamental question: When you combine goods and chores into a single market where both demand and supply are endogenous, does the market inherit the chaotic, non-convex difficulties of the chores side?

Methods

The authors model the market with $n$ users, $m$ workers, and $k$ divisible tasks. Each task acts as a "good" for the user and a "chore" for the worker. To solve this market under linear preferences, the authors deploy two distinct, novel algorithmic approaches:

  1. A Combinatorial Walrasian Price-Adjustment Algorithm: Traditional Walrasian tatonnement (raising prices for items with excess demand) often diverges in chores-only markets because raising a chore's price can actually increase its net excess demand under certain conditions. The authors design a clever price-update scheme where the adaptive bids from the goods side mitigate this instability. By tracking a novel quadratic potential function of task surpluses, they prove the algorithm converges to an exact competitive equilibrium in polynomial time.

  2. Linear Programming in Logarithm Space: The authors construct an Eisenberg-Gale (EG) dual program for the labor market. While the primal and dual formulations are initially non-convex, they observe that the objective function lacks a direct price term, exhibiting a unique log-linear homogeneity. By taking the logarithm of the constraints and applying a change of variables ($\tilde{p}_\ell = \log p_\ell$), they transform the non-convex program into a clean Linear Program (LP). Because the LP contains irrational coefficients (due to the $\log$ terms), they introduce a precision-bounding truncation and a post-processing extraction technique to solve it exactly in polynomial time.

Datasets

None used. This is a purely theoretical paper focused on algorithmic game theory, structural proofs, and computational complexity.

Key Insights and Ideas

  • The "Anchoring" Effect of Demand: The most surprising structural insight is that adding the goods-side demand completely tames the pathological non-convex behaviors of the chores-side supply. The demand side disciplines the prices; an excessively inflated task price might clear the supply side, but it fails to attract buyers, preventing market clearance.
  • Convexity Restored: Thanks to this anchoring effect, the set of competitive equilibrium price vectors is proven to be a convex cone.
  • An Elusive LP Formulation: For decades, finding a direct LP formulation that captures competitive equilibria in standard goods-only linear Fisher markets has remained an open problem. Remarkably, by adding chores to the mix, the objective function simplifies in a way that permits an exact LP characterization in log-space.

The contrast between the dual formulations of these different market types highlights this structural shift:

Comparison of EG-Dual formulations across Goods, Chores, and the unified Labor Market.

Key Results

  • Existence & Welfare: The authors prove that a competitive equilibrium always exists under general conditions (concave utilities for users, convex disutilities for workers), and both the First and Second Welfare Theorems hold.
  • Algorithmic Complexity: For linear preferences, the combinatorial algorithm computes an exact equilibrium in polynomial time.
  • Strongly Polynomial Fairness: In the "CEEI-like" case (Competitive Equilibrium with Equal Earnings and Incomes), where all budgets and earning requirements are equal to one, the algorithm runs in strongly polynomial time—meaning its runtime is completely independent of the utility/disutility values.

An example of how prices balance demand and supply in this framework is illustrated below:

Figure 1: An equilibrium (left) and a non-equilibrium (right) for the instance in Example 1, with 2 users (left nodes), 3 tasks (middle nodes), and 2 workers (right nodes). The demand and supply are shown with directed edges, with the corresponding amounts of allocation marked on the edges.

Limitations and Future Work

  • Irrational Coefficients: Although the log-space LP characterization is a major theoretical breakthrough, it introduces irrational inputs ($\log v_{i\ell}$ and $\log c_{j\ell}$). Even though the authors bypass this with a polynomial-time truncation method, it requires a non-trivial post-processing step rather than an off-the-shelf exact LP solution.
  • Indivisible Tasks: This work assumes tasks are perfectly divisible. Extending these strong fairness (envy-freeness, proportionality) and efficiency guarantees to discrete settings (indivisible tasks) remains an open and compelling challenge for fair division research.
  • Alternative Dynamics: While the paper proves convergence for their specific Walrasian scheme, exploring whether other natural market dynamics (like proportional response or pacing) converge in this two-sided setting is left for future work.

Summary updated

Abstract

In this paper, we study a two-sided labor market that couples the classical Fisher market with goods and the Fisher market with bads into a single unified framework. In our model, users demand tasks in order to derive utility, while workers supply labor to perform these tasks in exchange for earnings. Each task thus plays a dual role: it is a good for the user side of the market and a chore for the worker side. Given prices for tasks, users choose utility-maximizing bundles subject to budgets, while workers choose disutility-minimizing task bundles subject to earning requirements; the resulting choices induce demand and supply endogenously for each task, and a CE corresponds to prices at which these coincide. We show that such markets are guaranteed to admit a CE in a very general setting, and the first and second welfare theorems hold for our labor market model. We next study the computation of equilibria under linear preferences. We show that, similar to the chores setting, equilibria correspond to KKT points of an Eisenberg-Gale-like non-convex program. Despite the non-convex characterization, we go on to show a set of surprisingly positive results. First, we show that there exists a polynomial-time combinatorial algorithm for computing CE, which relies on a natural Walrasian scheme for updating prices. In the "CEEI-like" case, this yields a strongly polynomial-time algorithm. We next show that our market admits a natural dual program, and this non-convex labor-market program admits a change of variables that transforms it into a linear program (albeit with irrational coefficients). Finally, leveraging this LP, we give yet another polynomial-time algorithm while deriving an approach for addressing the irrational coefficients in an efficient manner. We note that, even for goods-only linear Fisher markets, obtaining such an LP formulation remains open.
BibTeX
@misc{chaudhury2026competitive,
  author = {Bhaskar Ray Chaudhury and Christian Kroer and Ruta Mehta and Tianlong Nan and Zongjun Yang},
  title = {{Competitive Equilibrium in Labor Economies through the Lens of Goods and Chores Fisher Markets}},
  year = {2026},
  eprint = {2606.15060},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.15060},
}

Loading related content...

Figure