Approximating Competitive Equilibrium by Nash Welfare
New theory shows maximizing Nash welfare yields strong approximate competitive equilibrium for complex utility functions.
A new theoretical computer science paper by Jugal Garg, Yixin Tao, and László A. Végh bridges a fundamental gap in algorithmic game theory concerning the allocation of divisible goods. The study connects two central solution concepts: competitive equilibrium (CE), a market-based outcome, and allocations that maximize Nash welfare (the weighted geometric mean of agent utilities). While these coincide for simple, homogeneous utilities, they diverge for more complex, non-homogeneous functions. Crucially, computing an exact CE is PPAD-hard for classes like separable piecewise linear concave (SPLC) utilities, making it computationally intractable, whereas maximizing Nash welfare remains a solvable convex program.
The researchers' key innovation is defining a new class of 'Gale-substitute' utility functions, an analogue of the weak gross substitutes property. They prove that for any utility in this class—which includes all separable concave utilities and Leontief-free utilities—maximizing Nash welfare yields an allocation that is an approximate competitive equilibrium with strong guarantees. Specifically, every agent receives at least half of the maximum utility they could obtain in any true CE, and the allocation is approximately envy-free. This provides a computationally efficient method to find provably fair outcomes for problems where finding an exact CE is infeasible.
Conversely, the paper also establishes a 'price of anarchy' bound for general concave utilities, showing that every competitive equilibrium achieves at least a factor of (1/e)^(1/e) (approximately 0.69) of the maximum possible Nash welfare, and that this bound is tight. The work introduces 'generalized network utilities' as a unifying model that encompasses SPLC and Leontief-free utilities and demonstrates they are all Gale-substitutes, significantly expanding the known frontier of tractable fair division problems.
- Introduced 'Gale-substitute' utility functions, a broad class where Nash welfare maximization yields an approximate competitive equilibrium (CE).
- For Gale-substitutes, the Nash solution guarantees each agent gets ≥50% of their max possible CE utility, offering a tractable alternative to PPAD-hard CE computation.
- Established a tight bound showing every CE achieves ≥~0.69 of the max Nash welfare for general concave utilities, framing the trade-off between the two concepts.
Why It Matters
Provides a computationally efficient pathway to approximately fair resource allocations for complex economies where exact solutions are intractable.