Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case

DOI10.1007/S00453-019-00550-3zbMATH Open1425.91345arXiv1809.08453OpenAlexW2890099492WikidataQ128436885 ScholiaQ128436885MaRDI QIDQ2415359FDOQ2415359

Authors: Hugo Gilbert, Olivier Spanjaard 

Publication date: 21 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Abstract: This paper deals with fairness in stable marriage problems. The idea studied here is to achieve fairness thanks to a Generalized Gini Index (GGI), a well-known criterion in inequality measurement, that includes both the egalitarian and utilitarian criteria as special cases. We show that determining a stable marriage optimizing a GGI criterion of agents' disutilities is an NP-hard problem. We then provide a polynomial time 2-approximation algorithm in the general case, as well as an exact algorithm which is polynomial time in the case of a constant number of non-zero weights parametrizing the GGI criterion.

Full work available at URL: https://arxiv.org/abs/1809.08453

Recommendations

• Approximation Algorithms for the Sex-Equal Stable Marriage Problem
• Approximation algorithms for the sex-equal stable marriage problem
• scientific article; zbMATH DE number 2086256
• Complexity of the sex-equal stable marriage problem
• Sex-equal stable matchings: complexity and exact algorithms

zbMATH Keywords

fairnesscomplexitystable marriage problemgeneralized Gini index

Mathematics Subject Classification ID

Statistical methods; economic indices and measures (91B82) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Matching models (91B68)

Cites Work

• On ordered weighted averaging aggregation operators in multicriteria decisionmaking
• Understanding the generalized median stable matchings
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage
• Title not available (Why is that?)
• Title not available (Why is that?)
• College Admissions and the Stability of Marriage
• Generalized Gini inequality indices
• On solving linear programs with the ordered weighted averaging objective.
• The Minimum Satisfiability Problem
• The geometry of fractional stable matchings and its applications
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• Linear programming brings marital bliss
• On the complexity of achieving proportional representation
• OWA-based extensions of the Chamberlin-Courant rule
• Combinatorial optimization problems with uncertain costs and the OWA criterion
• Network flow and 2-satisfiability
• Sex-equal stable matchings: complexity and exact algorithms
• Complexity of the sex-equal stable marriage problem
• The fair OWA one-to-one assignment problem: NP-hardness and polynomial time special cases
• Fairness and rank-weighted utilitarianism in resource allocation
• Random matching under priorities: stability and no envy concepts

Cited In (1)

• The fair OWA one-to-one assignment problem: NP-hardness and polynomial time special cases

This page was built for publication: Optimizing a generalized Gini index in stable marriage problems: NP-hardness, approximation and a polynomial time special case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2415359)