CS Paper Radar

Fair Stable Matching: A Nash Social Welfare Approach

Parth Desai, Rasheed M, Ganesh Ghalme, Sujit Gujar

cs.GT cs.AI ·submitted 2026-09-02 09:26 UTC · v1

Abstract

While traditional stable matching algorithms, such as the Gale-Shapley algorithm, prioritize stability, they may fall short of achieving equitable outcomes among participants. We study the role of \emph{Nash social welfare} (NSW) as a fairness objective in the classic \emph{stable marriage problem}. We develop \texttt{SNSW-Alg} that finds a stable matching that maximizes Nash social welfare under rank-induced utilities in $\tilde{\mathcal{O}}(n^4)$ time, where $n$ is the number of men or women. We demonstrate that \texttt{SNSW-Alg} balances equity while preserving stability. We empirically evaluate our methods across diverse preference distributions, demonstrating significant gains in fairness without substantial losses in other key measures such as regret, egalitarian criterion, and sex equality. Our findings suggest that the stable matching produced by \texttt{SNSW-Alg} is statistically Pareto-undominated by stable matchings based on other fairness measures - regret, egalitarian, and sex equality. This study offers compelling insights for designing fair-stable matching.

Closest papers

Nearest neighbours by meaning across the whole index.

A $2.81^n$ upper bound on the number of stable matchings

cs.DS cs.DMmath.CO ·2026-11-04 ·Ebrahim Ghorbani, Matthias Mnich
theory similarity 0.67
Abstract

We study the maximum number ${\rm SM}(n)$ of stable matchings in an instance with $n$ men and $n$ women. Karlin, Oveis Gharan, and Weber (STOC 2018) proved the first single-exponential upper bound; their argument gives ${\rm SM}(n)\le 2^{17n}$ for sufficiently large $n$. Palmer and Pálvölgyi (FOCS 2021) improved this bound to $3.55^n+O(1)$. We prove that ${\rm SM}(n)<2.81^n$. This brings the exponential base closer to $2.28$, the base of the best known lower bound. More precisely, we bound the number of stable matchings in each instance in terms of each person's number of stable partners, where a stable partner is someone matched to that person in at least one stable matching. Our proof assigns each person a weight determined by this number and uses these weights to bound the number of stable matchings by induction.

0.23

Fairness and Non-wastefulness in Matching with Siblings and Initial Enrollments: Compatibility and Complexity

cs.GT ·2026-10-01 ·Haris Aziz, Gergely Csáji, Zhaohong Sun, Makoto Yokoo
similarity 0.66
Abstract

We study a two-sided matching problem between families and daycare centers in which a family may have multiple children with joint preferences, and some children may already be enrolled in daycare centers while seeking transfers. Our model combines and generalizes two well-studied matching frameworks: matching with couples and school choice with initial enrollments. The interaction between joint family preferences and initial enrollments creates fundamental challenges for the existence of desirable outcomes and the design of computationally efficient algorithms. Since stable matchings need not exist, we decompose stability into individual rationality, fairness, and non-wastefulness, and study the trade-off between fairness and non-wastefulness from two complementary directions. To preserve non-wastefulness, we first consider master-list-based approaches and show that they are insufficient in the presence of initial enrollments. We then introduce \emph{resettlement}, which protects displaced families by allowing them to return to their initial assignments, and develop a greedy improvement algorithm that establishes the existence of matchings satisfying non-wastefulness together with resettlement-based fairness. To preserve fairness, we first examine a generalized cutoff approach and then develop a fairness-preserving non-wasteful algorithm that guarantees fairness together with a relaxed notion of non-wastefulness. We further characterize the computational complexity of these solution concepts. While several fairness notions can be verified in polynomial time, deciding whether a non-wasteful matching satisfying them exists is NP-complete. Resettlement restores universal existence, but computing resettlement-based outcomes is PLS-hard, and verifying the stronger dominance-based fairness notion is coNP-complete.

0.18

A Matroid Generalization of Weighted Popular Matching: Characterization and Algorithm

cs.GT cs.DS ·2026-10-13 ·Yuni Iwamasa, Yusuke Kobayashi, Ryoga Mahara, Kenjiro Takazawa
similarity 0.64
Abstract

We study a problem that unifies two major generalizations of popular matchings in the one-sided preference model. In a bipartite graph in which each vertex, or applicant, on one side has preferences over the adjacent vertices, a matching is called popular if it does not lose a head-to-head election against any other matching. Since the seminal work of Abraham, Irving, Kavitha, and Mehlhorn, who gave the first polynomial-time algorithm for finding a popular matching, numerous generalizations of the popular matching problem have been investigated. Two prominent directions are weighted popular matchings, in which each applicant is assigned a voting weight, and popularity problems under matroid constraints. The former admits a polynomial-time algorithm due to Mestre, while the most general form of the latter is the popular common independent set problem, for which a polynomial-time algorithm is given by Kavitha, Makino, Schlotter, and Yokoi. In this paper, we introduce the weighted popular common independent set problem, which simultaneously generalizes weighted popular matchings and popular common independent sets. Our main result is the first polynomial-time algorithm for this problem. A key ingredient of the algorithm is a solution-independent characterization of weighted popular common independent sets, which we establish in this paper. As consequences of our algorithmic result, we obtain polynomial-time algorithms for several previously unresolved problems, including weighted popular matchings with matroid constraints and weighted popular branchings.

0.12

Computing Stable Matchings under Complementarities and Preference Misalignment

cs.GT ·2026-10-05 ·Tatsuya Iwase, Baharak Rastegari, Sebastian Stein, Enrico H. Gerding
similarity 0.63
Abstract

We study many-to-one, two-sided stable matching problems in which preferences are complementary and firms and workers may rank the same allocation differently. Here a coalition is a group of workers that can be jointly matched with a firm. With complementary preferences, a stable matching need not exist. We show that a stable matching exists for every instance when two conditions hold. The first requires each firm to have an anchor worker who is included in every feasible coalition that can be matched with that firm. The second is Transitive Alignment, which means there must be an overall ranking across different coalitions that is consistent with the workers' preferences. We propose CDAR (Combinatorial Deferred Acceptance with Reproposals), a Deferred Acceptance-style algorithm that permits reproposals, and prove its finite-time convergence and its output of a stable matching by constructing an $N$-digit potential function. Moreover, we show that, under strict preferences, the output of CDAR is Pareto optimal among stable matchings. The proposed framework naturally captures applications such as vehicle-route assignment for traffic safety and the misaligned interests of labor and management in wage negotiation.

0.17

From Preference to Reciprocity: Decentralized Matching with Empirically Grounded LLM-agent Based Modeling

cs.LG cs.AI ·2026-09-28 ·Wangxuan Fan, Xiaoyu Nie, Zhoutian Shi, Xiangcheng Meng, Shipei Zeng +3 more
similarity 0.62
Abstract

Bipartite matching is a fundamental problem in game theory and market design. Classical approaches such as Gale--Shapley assume complete preferences and centralized computation, whereas many real-world matching processes are decentralized, asynchronous, and shaped by sequential interaction under limited information. We propose a dynamic bipartite matching framework that combines large language model (LLM) agents with contextual bandits. In a simulated Chinese marriage market, economically grounded LLM agents evaluate locally encountered candidates, while agent-specific Logistic-UCB models learn reciprocal acceptance from realized proposal outcomes. The mechanism therefore separates two decisions---\emph{whom do I like?} and \emph{who is likely to like me back?}---without requiring ex ante market-wide preference rankings. We first validate LLM-induced mate preferences against the empirical conditional-logit reference across multiple LLM backbones. In the $50\times50$ matching experiment, Bandit-UCB achieves the highest mean mutual welfare (56.01 versus 54.87 for Gale--Shapley), a smaller gender rank gap than the classical baselines, and the fewest blocking pairs among the LLM-ABM policies. Learned acceptance models show economically interpretable gender-differentiated associations, while counterfactual setups reveal no systematic unilateral advantage from prior search knowledge. Overall, these results support the advantages of decentralized matching with LLM-based behavioral modeling and online learning under incomplete information for economic simulation and computational social science research.

0.26

A Weakly Group Strategy-Proof and Pareto-Stable Matching Mechanism with Two-Sided Indifferences under Gross Substitutes

cs.GT econ.TH ·2026-10-22 ·Yasushi Kawase, Ryosuke Sato
similarity 0.62
Abstract

We study finite many-to-one matching markets with indifferences on both sides and publicly known firm preferences over sets of workers. A standard approach breaks ties uniformly at random and runs deferred acceptance, which is strategy-proof for workers but may select a weakly stable matching that is Pareto dominated under the agents' original preferences. For the broad class of markets in which each firm's preferences admit a gross substitutes (GS) representation, we construct a deterministic generalized deferred acceptance mechanism that is weakly stable, Pareto efficient with respect to both sides, worker weakly group strategy-proof, and implementable in strongly polynomial time given value oracles for the GS representations. This domain includes nonresponsive firm preferences, such as additive scores under matroid constraints and assignment values. Our analysis bridges ordinal matching with indifferences and competitive equilibria under imperfectly transferable utility. Although the mechanism uses only ordinal comparisons, it returns a seller-optimal equilibrium matching of a tiered auxiliary market, and the equilibrium structure of this market yields the stability, efficiency, and incentive guarantees.

0.07

A Sub-$3^n$ Upper Bound on the Number of Stable Matchings

cs.DS cs.DMmath.CO ·2026-11-04 ·Ken-ichi Kawarabayashi, Hikaru Wada, Masataka Yoneda
theory similarity 0.62
Abstract · 56 pages, 12 figures

We study the problem of determining the maximum number of stable matchings. This classical counting problem was posed by Knuth and has been studied for five decades. We obtain a new $2.999^n$ upper bound on the number of stable matchings with $n$ men and $n$ women. This improves the best-known previous result by Palmer and Pálvölgyi. This result gets much closer to the well-known lower bound $\frac{2.28^n}{\text{poly}(n)}$. We refine their entropy-based framework by capturing broader structural relationships among stable matchings. To capture these relationships, we introduce new frameworks, including cones and supports. This establishes the $3.332^n$ bound. We also exploit relationships among local structures and use a charging argument to improve the bound to $2.999^n$.

0.28

Singleton-Attainability and Transparent Access in Matching

cs.GT econ.TH ·2026-09-23 ·Szilvia Pápai
similarity 0.60
Abstract · 68 pages, 3 tables. JEL Classification: C78, D47

Matching mechanisms differ in how much of an agent's preference ranking must be determined and reported to obtain a particular object. A mechanism is singleton-attainable (SA) if every object that an agent can obtain through some report can also be obtained by reporting only that object as acceptable. With an SA mechanism, once an attainable object has been identified, the agent need not rank or report any other object. Singleton-attainability identifies a distinct dimension in matching theory and market design: transparent access to attainable outcomes, separate from incentives, stability, welfare or equity. We establish general conditions for SA and derive its strategic implications. Top-lift invariance and truncation invariance together imply SA, while strategyproofness and stability each imply SA. By contrast, no Pareto improvement over a strategyproof, individually rational, and non-wasteful mechanism is SA. In particular, every Pareto improvement over Deferred Acceptance violates SA. We introduce report width, which measures how many acceptable objects may have to be reported to obtain an object. SA mechanisms have report width one. Report width is unbounded for a large class of efficient mechanisms that Pareto-improve Deferred Acceptance. Stable selection with report-induced priorities has width one when priorities are monotone and maximal width under reverse priority dominance. Rank-welfare maximization has width one when the outside-option rank is fixed and maximal width when it is report-dependent. These results reveal a structural divide, which we call the width dichotomy: across all mechanisms and families in our classification and all structural classes we study, report width is either one or unbounded.

0.21