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:
-
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.
-
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:
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:
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