Maximizing Nash Social Welfare under Two-Sided Preferences

Pallavi Jain, Rohit VaishAAAI 2024 · DOI

Abstract

Nash Social Welfare (NSW) is a prominent fairness metric that balances utilitarian and egalitarian objectives by maximizing the geometric mean of agent utilities. While extensively studied in one-sided resource allocation, its application to two-sided matching markets—where both sides (e.g., workers and firms) have preferences—remains relatively unexplored. This paper addresses this gap, demonstrating that two-sided preferences significantly increase computational complexity. We prove that maximizing NSW is NP-hard even in highly restricted settings, such as when firms have a capacity of two and valuations are ternary. To navigate this complexity, we provide a comprehensive suite of approximation algorithms and parameterized solutions, identifying specific "tractable islands" where exact solutions are possible.

Introduction

In traditional matching theory, such as the Gale-Shapley framework, the primary focus is on stability. However, stable matchings can be inherently unfair, often heavily favoring one side of the market. To introduce fairness, researchers turn to Nash Social Welfare (NSW). NSW is the geometric mean of all agents' utilities, offering a middle ground between maximizing total utility and supporting the least-advantaged agent.

Unlike one-sided settings where items are passive, two-sided markets involve agents on both sides with distinct valuations. For instance, in a labor market, workers have preferences over firms, and firms have additive valuations for the workers they employ. This interdependence creates a complex optimization landscape where a matching favorable to a firm might be detrimental to its workers.

The Complexity of Two-Sided Preferences

The transition from one-sided to two-sided preferences introduces a "complexity cliff." While the problem is solvable in polynomial time if each firm hires only one worker, it becomes NP-hard as soon as a firm's capacity reaches two. This holds true even with very simple valuations (e.g., {0, 1, 2}).

Figure 1: Comparison of matchings under different preference structures. A matching optimal for one side may be suboptimal when considering two-sided preferences.

A key insight is the divergence between one-sided and two-sided optimality. As shown in Figure 1, a matching that maximizes welfare from the firms' perspective alone (left) can be arbitrarily suboptimal when worker preferences are factored in (right), potentially leading to zero welfare if any agent's utility drops to zero.

Methodological Framework

The authors utilize several theoretical tools to map the problem's complexity:

  • Hardness Reductions: By reducing the "Rainbow Perfect Matching" problem to the NSW matching problem, they establish NP-hardness for general cases.
  • Submodular Optimization: The logarithm of the Nash product is shown to be a submodular function. This allows the application of greedy algorithms from fair division literature to achieve approximation guarantees.
  • Fixed-Parameter Tractability (FPT): For markets with a small number of workers ($m$), the authors developed an exact DP algorithm running in $O^*(3^m)$ time.
  • Polynomial Multiplication: This technique is used to design faster approximation schemes by representing matching configurations as algebraic terms.
Figure 5: A complex bipartite graph construction used in the hardness reduction from Rainbow Perfect Matching to the NSW matching problem.

Key Results and Tractable Islands

The research provides a detailed "complexity map" of the problem space:

  • General Hardness: Maximizing NSW is NP-hard even with ternary valuations and a firm capacity of 2.
  • Approximation Guarantees: A $1/\sqrt{opt}$-approximation algorithm is provided for general instances with positive valuations.
  • Tractable Cases: The problem becomes polynomial-time solvable under symmetric binary valuations, where a worker $w$ values firm $f$ if and only if $f$ values $w$, with values restricted to {0, 1}.

Conclusion and Future Directions

This work bridges the gap between matching theory and fair division. While it establishes a $1/\sqrt{opt}$ approximation, the existence of a constant-factor approximation for the general two-sided case remains an open question. Future research should also explore the axiomatic foundations of two-sided NSW, such as "Envy-Freeness up to one item," and investigate the feasibility of matchings that are simultaneously Nash-optimal and stable.

Summary updated

BibTeX
@inproceedings{jain2024maximizing,
  author = {Pallavi Jain and Rohit Vaish},
  title = {{Maximizing Nash Social Welfare under Two-Sided Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28839},
}
Figure