Source-linked AI summary
Convex Program Duality, Fisher Markets, and Nash Social Welfare
Richard Cole, Nikhil R. Devanur, Vasilis Gkatzelis, Kamal Jain, Tung Mai, Vijay V. Vazirani, Sadra Yazdanbod
TL;DR
The paper addresses how to analyze Nash social welfare maximization and generalized Fisher markets through tractable convex programs. It uses convex-programming duality to connect established market formulations, construct new programs, and characterize equilibria. The resulting NSW relaxation has a bounded gap, while the generalized markets admit rational equilibria and polynomial-time computation.
Problem
Existing NSW formulations include a natural relaxation with an unbounded integrality gap, while generalized Fisher-market programs lack a unified conventional analysis.
Method
The paper uses convex-programming duality, Fenchel conjugates, and added market constraints to derive programs for NSW and generalized Fisher markets.
Results
The new NSW program exactly captures the optimum integrally and has a relaxation with gap at most 2.89; Fisher-market extensions admit rational equilibria.
Takeaways & Limitations
The duality framework unifies Eisenberg–Gale and Shmyrev formulations and supports convex equilibrium programs for spending- and utility-restricted markets.
Takeaways & Limitations
A convex program for the combined spending- and utility-restricted linear market remains an open question.
Abstract
from arXiv · showhide
We study Fisher markets and the problem of maximizing the Nash social welfare (NSW), and show several closely related new results. In particular, we obtain: -- A new integer program for the NSW maximization problem whose fractional relaxation has a bounded integrality gap. In contrast, the natural integer program has an unbounded integrality gap. -- An improved, and tight, factor 2 analysis of the algorithm of [7]; in turn showing that the integrality gap of the above relaxation is at most 2. The approximation factor shown by [7] was $2e^{1/e} \approx 2.89$. -- A lower bound of $e^{1/e}\approx 1.44$ on the integrality gap of this relaxation. -- New convex programs for natural generalizations of linear Fisher markets and proofs that these markets admit rational equilibria. These results were obtained by establishing connections between previously known disparate results, and they help uncover their mathematical underpinnings. We show a formal connection between the convex programs of Eisenberg and Gale and that of Shmyrev, namely that their duals are equivalent up to a change of variables. Both programs capture equilibria of linear Fisher markets. By adding suitable constraints to Shmyrev's program, we obtain a convex program that captures equilibria of the spending-restricted market model defined by [7] in the context of the NSW maximization problem. Further, adding certain integral constraints to this program we get the integer program for the NSW mentioned above. The basic tool we use is convex programming duality. In the special case of convex programs with linear constraints (but convex objectives), we show a particularly simple way of obtaining dual programs, putting it almost at par with linear program duality. This simple way of finding duals has been used subsequently for many other applications.
1 Introduction
The paper develops a unified convex-programming view of Nash social welfare and generalized Fisher markets, addressing limitations of existing formulations and analyses.
- NSW maximization: The natural NSW integer program relaxes to the Eisenberg–Gale program, but its integrality gap is unbounded.This rules out a straightforward fractional-allocation-and-rounding approach based on that formulation.
- NSW maximization: The paper introduces a new integer program that exactly computes the optimal NSW allocation and whose relaxation computes the spending-restricted equilibrium.Its objective also equals the upper bound used in the prior approximation algorithm.
- NSW maximization: The new relaxation has integrality gap at most 2.89 and a lower bound of e^{1/e} ≈ 1.44.The supplied passage states the upper-bound result and lower-bound family, though the latter is truncated in the excerpt.
- Fisher markets: The paper formally connects the Eisenberg–Gale and Shmyrev programs by showing that their duals coincide up to a variable change.Adding suitable constraints to Shmyrev’s program yields a program capturing spending-restricted equilibria.
- Fisher markets: Convex programs for spending-restricted and utility-restricted markets establish equilibrium existence, rationality, and polynomial-time computability via the ellipsoid algorithm.The models impose seller earning bounds or buyer utility bounds, respectively.
- Convex duality: The paper derives a simple dual-construction method for convex programs with convex objectives and linear constraints.The method is designed to be nearly as simple as linear-program duality.
2 Preliminaries
This section defines Fisher markets, their spending- and utility-restricted variants, Nash social welfare, and the equilibrium objects used throughout the paper.
- Fisher markets: Fisher markets contain divisible goods, budgeted buyers, prices, allocations, and utility-maximizing demand subject to budgets.The standard model assumes one unit of each good and specifies market-clearing conditions for positively priced goods.
- Utility models: Linear utilities are additive over goods, while quasi-linear, Leontief, and CES utilities provide other utility-function classes.The paper assumes linear utilities in its main body unless stated otherwise.
- Restricted markets: The spending-restricted model caps each seller’s earnings, allowing the seller to withdraw unsold supply after reaching the cap.Buyers still spend their money and obtain optimal bundles in equilibrium.
- Restricted markets: The utility-restricted model caps each buyer’s utility, allowing the buyer to retain unspent money after reaching the cap.Goods with positive prices must be fully sold in equilibrium.
- Market representations: The spending graph connects each agent to exactly the items on which that agent spends positive money.This bipartite graph represents the support of a spending vector.
- Nash social welfare: NSW maximization allocates indivisible items to maximize the geometric mean of agents’ utilities.For linear valuations, Cole and Gkatzelis previously gave a 2e^{1/e} ≈ 2.89-factor approximation.
3 Convex programming duality
The paper presents a shortcut for deriving duals of convex programs with linear constraints, using Fenchel conjugates and generalized complementary slackness.
- Fenchel conjugates: The Fenchel conjugate is defined as f*(μ) := sup_x{μ^T x − f(x)} and is central to the duality framework.The discussion assumes strict convexity and differentiability for the main applications.
- Fenchel conjugates: Complementary pairs satisfy either the conjugate equality or the corresponding gradient relations between f and f*.These relations connect primal and dual variables through ∇f(x)=μ and ∇f*(μ)=x.
- Dual construction: Lagrangian duality transforms convex programs with convex or concave objectives and linear constraints into another convex program.The section seeks a shortcut replacing a usually lengthy calculation.
- Duality guarantees: The resulting program pairs satisfy weak duality, while strict primal feasibility yields strong duality and generalized complementary slackness.The stated conditions include infeasibility corresponding to an unbounded dual and equality of optima under strict feasibility.
- Dual construction: Compared with linear-program duality, each nonlinear primal variable contributes an auxiliary dual variable and a Fenchel-conjugate term.The dual also modifies the corresponding constraint by including the auxiliary variable.
- Dual forms: The framework includes versions for primal variables with non-negativity constraints and for minimization programs.These forms are presented as paired convex programs and their duals.
4 Convex programs for Fisher markets
Convex duality links major Fisher-market programs and extends equilibrium computation to quasi-linear, spending-restricted, and utility-restricted settings.
- Linear Fisher markets: The dual variables of the relevant convex programs are equilibrium prices for linear Fisher markets.This gives a direct optimization-based characterization of market equilibria.
- Linear Fisher markets: Eliminating β_i yields an unconstrained convex minimization over prices involving Σ_i B_i log(min_j {p_j/v_ij}).Its subgradient corresponds to market excess supply, linking gradient descent with tâtonnement price updates.
- Linear Fisher markets: A logarithmic variable change produces an equivalent convex program and its dual.The transformation uses q_j = log p_j and γ_i = −log β_i.
- Program connections: The Eisenberg–Gale and Shmyrev programs have the same dual up to a change of variables.Removing a constant objective term from the dual yields Shmyrev’s program.
- Quasi-linear utilities: Dual pairs also capture equilibria for Fisher markets with quasi-linear utilities.The formulation accommodates buyers who may prefer leaving their budgets partly unspent when prices exceed values.
- Market extensions: The paper develops convex programs, existence, uniqueness, and rationality results for spending-restricted and utility-restricted markets.The extensions include spending-constraint utilities and linear, Leontief, and CES utility-restricted markets.
5 A new program for the Nash social welfare problem
The paper introduces a spending-restricted integer program whose integral solutions represent NSW allocations, while its fractional relaxation computes the spending-restricted equilibrium and matches the prior upper bound. This program avoids the natural formulation’s unbounded integrality gap and has an integrality gap bounded between e^{1/e} and 2e^{1/e}.
- Motivation: The natural NSW formulation has an unbounded integrality gap, so rounding its Eisenberg–Gale relaxation cannot yield a bounded approximation.The natural formulation becomes the polynomially solvable Eisenberg–Gale program after relaxing integrality, but the resulting gap is unbounded.
- Gap bounds: The relaxation has integrality gap at least e^{1/e} ≈ 1.44 and at most 2e^{1/e} ≈ 2.89.The lower bound follows from an instance whose fractional objective approaches V^f while every integral allocation has NSW (1−f)^{1−f}·(1−f+V)^f, with f=(e−1)/e.
- The SR program: The new SR integer program uses variables q_j and b_ij, with b_ij ∈ {0,q_j}, so each integral solution corresponds to an allocation of indivisible items.Item j is allocated to agent i exactly when b_ij = q_j.
- The SR program: The optimal SR program solution corresponds to an NSW-maximizing allocation, and its objective value equals the optimal NSW.This establishes the program as an exact integer formulation rather than merely an approximation model.
- The fractional relaxation: The fractional SR relaxation computes the spending-restricted equilibrium, with b_ij recording buyer spending, q_j recording total spending, and prices recovered from dual variables.Unlike the natural formulation, the spending constraint involves only primal variables q_j.
- The fractional relaxation: The fractional relaxation’s objective equals SR-UB, the prior upper bound used for the NSW approximation algorithm.The equality holds after the valuation scaling described in the program’s analysis.
6 A Tight Analysis of the Spending-Restricted Rounding Algorithm
The SRR algorithm rounds a spending-restricted equilibrium, and a tighter analysis establishes an exact approximation factor of 2. The proof uses structural properties of matching-trees and improves the earlier 2e^(1/e) ≈ 2.89 bound.
- Algorithm: The SRR algorithm first computes a spending-restricted equilibrium before rounding through the spending graph.Its listed steps select tree roots, assign leaf-items, and assign items with q_j ≤ 1/2.
- Tight approximation guarantee: 2 replaces the earlier 2e^(1/e) ≈ 2.89 approximation bound.The improved analysis is explicitly described as better than the prior analysis.
- Proof structure: Pruning multi-agent spending-graph nodes by retaining each item’s largest-spending child produces matching-trees that are forests.The proof analyzes these trees to characterize the rounding outcome.
- Proof structure: The worst-case analysis shows that unmatched value is distributed across remaining agents rather than concentrated in only a few agents.This observation supports the bound for the naive matching and therefore for SRR, whose allocation is at least as good.
- Tight approximation guarantee: 2 is the SRR algorithm’s exact approximation factor.The paper proves both an upper bound of 2 and a matching lower bound.
7 Discussion
The discussion identifies open extensions of the NSW problem and develops convex-duality connections across Fisher-market programs. It also presents duality as a simple route to equilibrium programs for generalized markets.
- Open problems: A convex program for the common linear-utility generalization with both buyer utility bounds and seller earning bounds remains open.This combines the utility-restricted and spending-restricted models.
- Open problems: A constant-factor approximation for non-symmetric NSW remains an open problem.The paper studies the symmetric case, where agents have equal budgets or clout.
- Open problems: Submodular and more generally subadditive utilities are identified as important generalizations of NSW.The paper specifically says the submodular case deserves more attention.
- Convex-program connections: The duals of the Eisenberg–Gale and Shmyrev programs are equivalent up to a change of variables.Both programs capture equilibria of linear Fisher markets.
- Convex-program connections: Convex duality yields programs for generalized Fisher markets even when a direct Eisenberg–Gale formulation is unclear.The discussion covers Leontief, network-flow, transaction-cost, and other generalized markets.
Alternate proof of Gibbs’ inequality
The alternate proof minimizes a transformed dual expression by eliminating auxiliary variables. The resulting minimum equals the logarithm of the relevant aggregate valuation and is also attained in the primal.
- Dual minimization: The dual proof fixes α_i and minimizes over μ_ij subject to α_i ≥ log v_ij − μ_ij.The minimizing choice is μ_ij = log v_ij − α_i.
- Dual minimization: The minimized objective is obtained by setting the derivative with respect to α_i to zero.This reduces the optimization to a closed-form minimum.
- Result: The minimum value is α_i + 1 = log(∑_{j∈S_i} v_ij), and the same value is attained in the primal.The primal attains it by setting b_ij = v_ij.
B Convex Program, Existence and Uniqueness for the SR equilibrium
The f-SR convex program captures spending-restricted equilibria through spending variables and dual prices. The section establishes equilibrium existence conditions, uniqueness of the spending vector, and non-uniqueness of prices.
- Program interpretation: The f-SR program includes seller earning-limit constraints ensuring that spending on good j does not exceed c_j.The variables q_j record total spending on each good.
- Program interpretation: The f-SR program computes SR equilibria, with b_ij representing buyer spending and q_j representing total spending on good j.Prices are recovered from optimal dual variables.
- Equilibrium conditions: The KKT conditions imply that buyers spend only on maximum bang-per-buck goods at the recovered prices.The same conditions also enforce that each buyer spends the full budget and that seller earnings equal min(p_j, c_j).
- Existence: An SR equilibrium price exists if and only if the stated feasibility condition holds.For linear utilities, the proof reduces existence to feasibility of the f-SR convex program.
- Uniqueness: The spending vector q is unique, although SR equilibrium prices need not be unique.With one buyer and one seller, every price greater than 1 can be an SR equilibrium price.
B.1 Rationality of the SR equilibrium
The paper proves that spending-restricted equilibria admit rational prices when an equilibrium exists and all market parameters are rational. The proof represents equilibrium conditions within a suitable polyhedron and selects a rational vertex.
- A rational equilibrium exists if an equilibrium exists and all specified market parameters are rational.
- Equilibrium prices, spending, and inverse MBB values lie in a polyhedron determined by spending relationships and binding seller limits.
- A nonempty polyhedron has a rational vertex because its defining coefficients are rational, yielding a rational equilibrium price.
C SR equilibrium with Spending Constraint Utilities
This section extends spending-restricted markets to spending-constraint utility functions and characterizes them through convex programs. The resulting equilibria have structured spending behavior, existence conditions, unique spending vectors, and rational equilibria under rational parameters.
- Market model: Spending-constraint utilities describe each buyer’s utility rate for a good as a function of money spent, with linear Fisher markets as a special case.
- Convex program: The spending-restricted convex program P2 captures equilibrium prices for spending-constraint utility functions.
- Equilibrium characterization: At equilibrium, buyers spend first on higher-rate segments, follow best spending strategies, and sellers earn the minimum of their cap and total spending.
- Existence and uniqueness: An equilibrium exists exactly when the corresponding convex program is feasible, and the spending vector is unique.
- Rationality: For rational parameters, spending-restricted markets with spending-constraint utilities admit rational equilibria.
- Utility-restricted markets: Convex programs P3, P4, and P5 capture utility-restricted equilibria for linear, Leontief, and CES utility functions, respectively.
D.5 Existence and Uniqueness of UR equilibrium
For utility-restricted markets, an equilibrium price always exists under linear, Leontief, and CES utilities, while equilibrium utilities are unique even when prices need not be.
- Price non-uniqueness: Equilibrium prices need not be unique; with one buyer and one seller, every price in [1, 2] can be an equilibrium price.
- Existence: Equilibrium prices always exist in utility-restricted markets with linear, Leontief, and CES utility functions.
- Uniqueness: Equilibrium utilities are unique because every equilibrium corresponds to maximizing a strictly concave weighted log-utility objective.
E Proofs of Theorem 1 and Lemma 10 (Approximation Factor Bounds)
The approximation analysis studies SRR allocations on pruned spending-graph trees and establishes a factor-2 bound, alongside an instance showing that the factor is tight in the limit.
- Matching-tree construction: The algorithm prunes the spending graph into matching-trees by retaining, for each item, the edge to the agent spending the most on it.
- Approximation analysis: Each matching-tree contains an agent receiving value at least 1/(2k) during the algorithm’s earlier allocation steps.
- Approximation analysis: If one agent in a k-agent tree receives value below 1/2, every other agent in that tree receives at least 1/2.
- Product bound: Lemma 25 bounds the number of agents with value at least 1 in a minimum-product allocation, supporting the product comparison used in the proof.
- Product bound: Lemma 26 proves the SRR allocation’s product bound for every matching-tree, using separate cases for agents above and below value 1/2.
- Tightness: A constructed instance makes the ratio between the NSW of the algorithm’s outcome and a better allocation converge to 2 as κ grows.