Optimizing a Generalized Gini Index in Stable Marriage Problems: NP-Hardness, Approximation and a Polynomial Time Special Case View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-02-08

AUTHORS

Hugo Gilbert, Olivier Spanjaard

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. More... »

PAGES

1-29

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-019-00550-3

DOI

http://dx.doi.org/10.1007/s00453-019-00550-3

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1112025330


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Gran Sasso Science Institute", 
          "id": "https://www.grid.ac/institutes/grid.466750.6", 
          "name": [
            "Gran Sasso Science Institute, 67100, L\u2019Aquila, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gilbert", 
        "givenName": "Hugo", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "French National Centre for Scientific Research", 
          "id": "https://www.grid.ac/institutes/grid.4444.0", 
          "name": [
            "Laboratoire d\u2019Informatique de Paris 6, LIP6, CNRS, Sorbonne Universit\u00e9, 75005, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Spanjaard", 
        "givenName": "Olivier", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01240738", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001136524", 
          "https://doi.org/10.1007/bf01240738"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf03167200", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009603935", 
          "https://doi.org/10.1007/bf03167200"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf03167200", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009603935", 
          "https://doi.org/10.1007/bf03167200"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0165-4896(81)90018-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012639305"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2014.11.013", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019582803"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-012-9672-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023636971", 
          "https://doi.org/10.1007/s00453-012-9672-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-23114-3_29", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025701357", 
          "https://doi.org/10.1007/978-3-319-23114-3_29"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(02)00399-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025946021"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(02)00399-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025946021"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(89)90041-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027976540"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(89)90041-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027976540"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-009-9307-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035594515", 
          "https://doi.org/10.1007/s00453-009-9307-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-009-9307-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035594515", 
          "https://doi.org/10.1007/s00453-009-9307-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-009-9307-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035594515", 
          "https://doi.org/10.1007/s00453-009-9307-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-23114-3_31", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042313458", 
          "https://doi.org/10.1007/978-3-319-23114-3_31"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00355-007-0235-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042423374", 
          "https://doi.org/10.1007/s00355-007-0235-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00355-007-0235-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042423374", 
          "https://doi.org/10.1007/s00355-007-0235-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/362619.362631", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043822363"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/28869.28871", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053415670"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/21.87068", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061122429"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/91.388176", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061247734"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0215048", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841910"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0216010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841956"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0895480191220836", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062882836"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/moor.23.4.874", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064724167"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/acprof:oso/9780198566076.001.0001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098761640"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/8591", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098875524"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/00029890.1962.11989827", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1101512498"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-018-0434-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1101844891", 
          "https://doi.org/10.1007/s00453-018-0434-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-018-0434-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1101844891", 
          "https://doi.org/10.1007/s00453-018-0434-5"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-02-08", 
    "datePublishedReg": "2019-02-08", 
    "description": "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\u2019 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.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-019-00550-3", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }
    ], 
    "name": "Optimizing a Generalized Gini Index in Stable Marriage Problems: NP-Hardness, Approximation and a Polynomial Time Special Case", 
    "pagination": "1-29", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "dbf46a1392d8d059699a94675aa822bec5696b4681f9088c1c7e9290b62f8623"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-019-00550-3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1112025330"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-019-00550-3", 
      "https://app.dimensions.ai/details/publication/pub.1112025330"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T09:03", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000332_0000000332/records_121950_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00453-019-00550-3"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-019-00550-3'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-019-00550-3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-019-00550-3'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-019-00550-3'


 

This table displays all metadata directly associated to this object as RDF triples.

140 TRIPLES      21 PREDICATES      47 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-019-00550-3 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N6bbd9e8401e4435895526a64f33a801a
4 schema:citation sg:pub.10.1007/978-3-319-23114-3_29
5 sg:pub.10.1007/978-3-319-23114-3_31
6 sg:pub.10.1007/bf01240738
7 sg:pub.10.1007/bf03167200
8 sg:pub.10.1007/s00355-007-0235-2
9 sg:pub.10.1007/s00453-009-9307-2
10 sg:pub.10.1007/s00453-012-9672-0
11 sg:pub.10.1007/s00453-018-0434-5
12 https://doi.org/10.1016/0165-4896(81)90018-4
13 https://doi.org/10.1016/0167-6377(89)90041-2
14 https://doi.org/10.1016/j.tcs.2014.11.013
15 https://doi.org/10.1016/s0377-2217(02)00399-5
16 https://doi.org/10.1080/00029890.1962.11989827
17 https://doi.org/10.1093/acprof:oso/9780198566076.001.0001
18 https://doi.org/10.1109/21.87068
19 https://doi.org/10.1109/91.388176
20 https://doi.org/10.1137/0215048
21 https://doi.org/10.1137/0216010
22 https://doi.org/10.1137/s0895480191220836
23 https://doi.org/10.1142/8591
24 https://doi.org/10.1145/28869.28871
25 https://doi.org/10.1145/362619.362631
26 https://doi.org/10.1287/moor.23.4.874
27 schema:datePublished 2019-02-08
28 schema:datePublishedReg 2019-02-08
29 schema:description 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.
30 schema:genre research_article
31 schema:inLanguage en
32 schema:isAccessibleForFree false
33 schema:isPartOf sg:journal.1047644
34 schema:name Optimizing a Generalized Gini Index in Stable Marriage Problems: NP-Hardness, Approximation and a Polynomial Time Special Case
35 schema:pagination 1-29
36 schema:productId Na1fd9fb8d3f84c3baaca4812f7f970f0
37 Naffe6849ae7141a8ad4b8146f115ecc6
38 Ndbcb9ad38d104383ab9b8a40ac924546
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112025330
40 https://doi.org/10.1007/s00453-019-00550-3
41 schema:sdDatePublished 2019-04-11T09:03
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N6a90b6d7212d4348809926bd913422eb
44 schema:url https://link.springer.com/10.1007%2Fs00453-019-00550-3
45 sgo:license sg:explorer/license/
46 sgo:sdDataset articles
47 rdf:type schema:ScholarlyArticle
48 N198339cdcda74a219a80144c934eff3a rdf:first Naa9f054da3dd400da9ed2ecb096bb961
49 rdf:rest rdf:nil
50 N6a90b6d7212d4348809926bd913422eb schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N6bbd9e8401e4435895526a64f33a801a rdf:first Na2c5c1835a8e4ed09cb746ba8d2b74f6
53 rdf:rest N198339cdcda74a219a80144c934eff3a
54 Na1fd9fb8d3f84c3baaca4812f7f970f0 schema:name dimensions_id
55 schema:value pub.1112025330
56 rdf:type schema:PropertyValue
57 Na2c5c1835a8e4ed09cb746ba8d2b74f6 schema:affiliation https://www.grid.ac/institutes/grid.466750.6
58 schema:familyName Gilbert
59 schema:givenName Hugo
60 rdf:type schema:Person
61 Naa9f054da3dd400da9ed2ecb096bb961 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
62 schema:familyName Spanjaard
63 schema:givenName Olivier
64 rdf:type schema:Person
65 Naffe6849ae7141a8ad4b8146f115ecc6 schema:name doi
66 schema:value 10.1007/s00453-019-00550-3
67 rdf:type schema:PropertyValue
68 Ndbcb9ad38d104383ab9b8a40ac924546 schema:name readcube_id
69 schema:value dbf46a1392d8d059699a94675aa822bec5696b4681f9088c1c7e9290b62f8623
70 rdf:type schema:PropertyValue
71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
72 schema:name Information and Computing Sciences
73 rdf:type schema:DefinedTerm
74 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
75 schema:name Computation Theory and Mathematics
76 rdf:type schema:DefinedTerm
77 sg:journal.1047644 schema:issn 0178-4617
78 1432-0541
79 schema:name Algorithmica
80 rdf:type schema:Periodical
81 sg:pub.10.1007/978-3-319-23114-3_29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025701357
82 https://doi.org/10.1007/978-3-319-23114-3_29
83 rdf:type schema:CreativeWork
84 sg:pub.10.1007/978-3-319-23114-3_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042313458
85 https://doi.org/10.1007/978-3-319-23114-3_31
86 rdf:type schema:CreativeWork
87 sg:pub.10.1007/bf01240738 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001136524
88 https://doi.org/10.1007/bf01240738
89 rdf:type schema:CreativeWork
90 sg:pub.10.1007/bf03167200 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009603935
91 https://doi.org/10.1007/bf03167200
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/s00355-007-0235-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042423374
94 https://doi.org/10.1007/s00355-007-0235-2
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/s00453-009-9307-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035594515
97 https://doi.org/10.1007/s00453-009-9307-2
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/s00453-012-9672-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023636971
100 https://doi.org/10.1007/s00453-012-9672-0
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/s00453-018-0434-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101844891
103 https://doi.org/10.1007/s00453-018-0434-5
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/0165-4896(81)90018-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012639305
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/0167-6377(89)90041-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027976540
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/j.tcs.2014.11.013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019582803
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/s0377-2217(02)00399-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025946021
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1080/00029890.1962.11989827 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101512498
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1093/acprof:oso/9780198566076.001.0001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098761640
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1109/21.87068 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061122429
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1109/91.388176 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061247734
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1137/0215048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841910
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1137/0216010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841956
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1137/s0895480191220836 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882836
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1142/8591 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098875524
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1145/28869.28871 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053415670
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1145/362619.362631 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043822363
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1287/moor.23.4.874 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064724167
134 rdf:type schema:CreativeWork
135 https://www.grid.ac/institutes/grid.4444.0 schema:alternateName French National Centre for Scientific Research
136 schema:name Laboratoire d’Informatique de Paris 6, LIP6, CNRS, Sorbonne Université, 75005, Paris, France
137 rdf:type schema:Organization
138 https://www.grid.ac/institutes/grid.466750.6 schema:alternateName Gran Sasso Science Institute
139 schema:name Gran Sasso Science Institute, 67100, L’Aquila, Italy
140 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...