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

DOI10.1007/S00453-019-00550-3MaRDI QIDQ2415359zbMATH OpenOpenAlexWikidataFDO

Authors Hugo Gilbert, Olivier Spanjaard

Publication date 21 May 2019

Published in Algorithmica (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

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)