{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:10:46Z","timestamp":1755839446002},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:p>\n            Given\n            <jats:italic>m<\/jats:italic>\n            users (voters), where each user casts her preference for a single item (candidate) over\n            <jats:italic>n<\/jats:italic>\n            items (candidates) as a ballot, the preference aggregation problem returns\n            <jats:italic>k<\/jats:italic>\n            items (candidates) that have the\n            <jats:italic>k<\/jats:italic>\n            highest number of preferences (votes). Our work studies this problem considering\n            <jats:italic>complex fairness constraints<\/jats:italic>\n            that have to be satisfied via proportionate representations of different values of the group protected attribute(s) in the top-\n            <jats:italic>k<\/jats:italic>\n            results. Precisely, we study\n            <jats:italic>the margin finding problem under single ballot substitutions<\/jats:italic>\n            , where a single substitution amounts to removing a vote from candidate\n            <jats:italic>i<\/jats:italic>\n            and assigning it to candidate\n            <jats:italic>j<\/jats:italic>\n            and the goal is to\n            <jats:italic>minimize the number of single ballot substitutions needed to guarantee that the top-k results satisfy the fairness constraints.<\/jats:italic>\n            We study several variants of this problem considering how top-\n            <jats:italic>k<\/jats:italic>\n            fairness constraints are defined, (i) MFBinaryS and MFMultiS are defined when the fairness (proportionate representation) is defined over a single, binary or multivalued, protected attribute, respectively; (ii) MF-Multi2 is studied when top-\n            <jats:italic>k<\/jats:italic>\n            fairness is defined over two different protected attributes; (iii) MFMulti3+ investigates the margin finding problem, considering 3 or more protected attributes. We study these problems theoretically, and present a suite of algorithms with provable guarantees. We conduct rigorous large scale experiments involving multiple real world datasets by appropriately adapting multiple state-of-the-art solutions to demonstrate the effectiveness and scalability of our proposed methods.\n          <\/jats:p>","DOI":"10.14778\/3565816.3565832","type":"journal-article","created":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T00:35:16Z","timestamp":1669250116000},"page":"317-329","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Satisfying complex top-\n            <i>k<\/i>\n            fairness constraints by preference substitutions"],"prefix":"10.14778","volume":"16","author":[{"given":"Md. Mouinul","family":"Islam","sequence":"first","affiliation":[{"name":"NJIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dong","family":"Wei","sequence":"additional","affiliation":[{"name":"NJIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[{"name":"NJIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Senjuti Basu","family":"Roy","sequence":"additional","affiliation":[{"name":"NJIT"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,11,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113610.3113926"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687713"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300079"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00183045"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940883"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00149-X"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. 361--372","author":"Roy Senjuti Basu","year":"2011","unstructured":"Senjuti Basu Roy and Kaushik Chakrabarti . 2011 . Location-aware type ahead search on spatial databases: semantics and efficiency . In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. 361--372 . Senjuti Basu Roy and Kaushik Chakrabarti. 2011. Location-aware type ahead search on spatial databases: semantics and efficiency. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. 361--372."},{"key":"e_1_2_1_8_1","volume-title":"The existence of social welfare functions. Econometrica: Journal of the Econometric Society","author":"Blau Julian H","year":"1957","unstructured":"Julian H Blau . 1957. The existence of social welfare functions. Econometrica: Journal of the Econometric Society ( 1957 ), 302--313. Julian H Blau. 1957. The existence of social welfare functions. Econometrica: Journal of the Econometric Society (1957), 302--313."},{"key":"e_1_2_1_9_1","volume-title":"Towards computing victory margins in STV elections. arXiv preprint arXiv:1703.03511","author":"Blom Michelle","year":"2017","unstructured":"Michelle Blom , Peter J Stuckey , and Vanessa J Teague . 2017. Towards computing victory margins in STV elections. arXiv preprint arXiv:1703.03511 ( 2017 ). Michelle Blom, Peter J Stuckey, and Vanessa J Teague. 2017. Towards computing victory margins in STV elections. arXiv preprint arXiv:1703.03511 (2017)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.2307\/1955105"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00007172"},{"key":"e_1_2_1_12_1","volume-title":"Impossibility theorems in the Arrovian framework. Handbook of social choice and welfare 1","author":"Campbell Donald E","year":"2002","unstructured":"Donald E Campbell and Jerry S Kelly . 2002. Impossibility theorems in the Arrovian framework. Handbook of social choice and welfare 1 ( 2002 ), 35--94. Donald E Campbell and Jerry S Kelly. 2002. Impossibility theorems in the Arrovian framework. Handbook of social choice and welfare 1 (2002), 35--94."},{"key":"e_1_2_1_13_1","volume-title":"Estimating the Margin of Victory for Instant-Runoff Voting. In 2011 Electronic Voting Technology Workshop\/Workshop on Trustworthy Elections (EVT\/WOTE 11)","author":"Cary David","year":"2011","unstructured":"David Cary . 2011 . Estimating the Margin of Victory for Instant-Runoff Voting. In 2011 Electronic Voting Technology Workshop\/Workshop on Trustworthy Elections (EVT\/WOTE 11) . David Cary. 2011. Estimating the Margin of Victory for Instant-Runoff Voting. In 2011 Electronic Voting Technology Workshop\/Workshop on Trustworthy Elections (EVT\/WOTE 11)."},{"key":"e_1_2_1_14_1","volume-title":"Multiwinner voting with fairness constraints. arXiv preprint arXiv:1710.10057","author":"Celis L Elisa","year":"2017","unstructured":"L Elisa Celis , Lingxiao Huang , and Nisheeth K Vishnoi . 2017. Multiwinner voting with fairness constraints. arXiv preprint arXiv:1710.10057 ( 2017 ). L Elisa Celis, Lingxiao Huang, and Nisheeth K Vishnoi. 2017. Multiwinner voting with fairness constraints. arXiv preprint arXiv:1710.10057 (2017)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.01.003"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.04.008"},{"key":"e_1_2_1_17_1","volume-title":"Essay on the Application of Analysis to the Probability of Majority Decisions","author":"de Condorcet Marquis","unstructured":"Marquis de Condorcet . 1785. Essay on the Application of Analysis to the Probability of Majority Decisions . Paris : Imprimerie Royale ( 1785). Marquis de Condorcet. 1785. Essay on the Application of Analysis to the Probability of Majority Decisions. Paris: Imprimerie Royale (1785)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05119-2_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372165"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-011-0603-9"},{"key":"e_1_2_1_21_1","volume-title":"Designing electoral institutions: STV systems and their consequences. Political studies 44, 1","author":"Farrell David M","year":"1996","unstructured":"David M Farrell , Malcolm Mackerras , and Ian McAllister . 1996. Designing electoral institutions: STV systems and their consequences. Political studies 44, 1 ( 1996 ), 24--43. David M Farrell, Malcolm Mackerras, and Ian McAllister. 1996. Designing electoral institutions: STV systems and their consequences. Political studies 44, 1 (1996), 24--43."},{"key":"e_1_2_1_22_1","volume-title":"Fair algorithms for selecting citizens' assemblies. Nature 596, 7873","author":"Flanigan Bailey","year":"2021","unstructured":"Bailey Flanigan , Paul G\u00f6lz , Anupam Gupta , Brett Hennig , and Ariel D Procaccia . 2021. Fair algorithms for selecting citizens' assemblies. Nature 596, 7873 ( 2021 ), 548--552. Bailey Flanigan, Paul G\u00f6lz, Anupam Gupta, Brett Hennig, and Ariel D Procaccia. 2021. Fair algorithms for selecting citizens' assemblies. Nature 596, 7873 (2021), 548--552."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-003-0306-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467349"},{"key":"e_1_2_1_25_1","volume-title":"Computers and intractability","author":"Garey Michael R","unstructured":"Michael R Garey and David S Johnson . 1979. Computers and intractability . Vol. 174 . freeman San Francisco . Michael R Garey and David S Johnson. 1979. Computers and intractability. Vol. 174. freeman San Francisco."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330691"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442188.3445936"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3287560.3287592"},{"key":"e_1_2_1_29_1","first-page":"577","article-title":"Mathematics without numbers","volume":"88","author":"Kemeny John G","year":"1959","unstructured":"John G Kemeny . 1959 . Mathematics without numbers . Daedalus 88 , 4 (1959), 577 -- 591 . John G Kemeny. 1959. Mathematics without numbers. Daedalus 88, 4 (1959), 577--591.","journal-title":"Daedalus"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.33.1.38"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043932.2043956"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407855"},{"key":"e_1_2_1_33_1","volume-title":"Electoral systems","author":"Laslier Jean-Fran\u00e7ois","unstructured":"Jean-Fran\u00e7ois Laslier . 2012. And the loser is... plurality voting . In Electoral systems . Springer , 327--351. Jean-Fran\u00e7ois Laslier. 2012. And the loser is... plurality voting. In Electoral systems. Springer, 327--351."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2886521.2886613"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v24i1.7624"},{"key":"e_1_2_1_36_1","volume-title":"A comparison of efficiency of multicandidate electoral systems. American Journal of Political Science","author":"Samuel Merrill III.","year":"1984","unstructured":"Samuel Merrill III. 1984. A comparison of efficiency of multicandidate electoral systems. American Journal of Political Science ( 1984 ), 23--48. Samuel Merrill III. 1984. A comparison of efficiency of multicandidate electoral systems. American Journal of Political Science (1984), 23--48."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2307\/2981392"},{"key":"e_1_2_1_38_1","first-page":"30","article-title":"Aggregating preferences cannot be fair","volume":"2","author":"Rossi Francesca","year":"2005","unstructured":"Francesca Rossi , Kristen Brent Venable , and Toby Walsh . 2005 . Aggregating preferences cannot be fair . Intelligenza Artificiale 2 , 1 (2005), 30 -- 38 . Francesca Rossi, Kristen Brent Venable, and Toby Walsh. 2005. Aggregating preferences cannot be fair. Intelligenza Artificiale 2, 1 (2005), 30--38.","journal-title":"Intelligenza Artificiale"},{"key":"e_1_2_1_39_1","volume-title":"2014 IEEE 30th international conference on data engineering. IEEE, 412--423","author":"Roy Senjuti Basu","year":"2014","unstructured":"Senjuti Basu Roy , Saravanan Thirumuruganathan , Sihem Amer-Yahia , Gautam Das , and Cong Yu . 2014 . Exploiting group recommendation functions for flexible preferences . In 2014 IEEE 30th international conference on data engineering. IEEE, 412--423 . Senjuti Basu Roy, Saravanan Thirumuruganathan, Sihem Amer-Yahia, Gautam Das, and Cong Yu. 2014. Exploiting group recommendation functions for flexible preferences. In 2014 IEEE 30th international conference on data engineering. IEEE, 412--423."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1515\/spp-2012-0003"},{"key":"e_1_2_1_41_1","volume-title":"Social choice theory. Handbook of mathematical economics 3","author":"Sen Amartya","year":"1986","unstructured":"Amartya Sen . 1986. Social choice theory. Handbook of mathematical economics 3 ( 1986 ), 1073--1181. Amartya Sen. 1986. Social choice theory. Handbook of mathematical economics 3 (1986), 1073--1181."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the EDBT Conference.","author":"Stoyanovich Julia","year":"2018","unstructured":"Julia Stoyanovich , Ke Yang , and HV Jagadish . 2018 . Online set selection with fairness and diversity constraints . In Proceedings of the EDBT Conference. Julia Stoyanovich, Ke Yang, and HV Jagadish. 2018. Online set selection with fairness and diversity constraints. In Proceedings of the EDBT Conference."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1257\/jep.9.1.27"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517865"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229086"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2921558.2921559"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3565816.3565832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:36:33Z","timestamp":1672220193000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3565816.3565832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["10.14778\/3565816.3565832"],"URL":"https:\/\/doi.org\/10.14778\/3565816.3565832","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,10]]},"assertion":[{"value":"2022-11-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}