IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v45y2023i3d10.1007_s10878-023-01019-4.html
   My bibliography  Save this article

Group fairness in non-monotone submodular maximization

Author

Listed:
  • Jing Yuan

    (University of North Texas)

  • Shaojie Tang

    (University of Texas at Dallas)

Abstract

Maximizing a submodular function has a wide range of applications in machine learning and data mining. One such application is data summarization whose goal is to select a small set of representative and diverse data items from a large dataset. However, data items might have sensitive attributes such as race or gender, in this setting, it is important to design fairness-aware algorithms to mitigate potential algorithmic bias that may cause over- or under- representation of particular groups. Motivated by that, we propose and study the classic non-monotone submodular maximization problem subject to novel group fairness constraints. Our goal is to select a set of items that maximizes a non-monotone submodular function, while ensuring that the number of selected items from each group is proportionate to its size, to the extent specified by the decision maker. We develop the first constant-factor approximation algorithms for this problem. We also extend the basic model to incorporate an additional global size constraint on the total number of selected items.

Suggested Citation

  • Jing Yuan & Shaojie Tang, 2023. "Group fairness in non-monotone submodular maximization," Journal of Combinatorial Optimization, Springer, vol. 45(3), pages 1-15, April.
    • Handle: RePEc:spr:jcomop:v:45:y:2023:i:3:d:10.1007_s10878-023-01019-4
    DOI: 10.1007/s10878-023-01019-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-023-01019-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-023-01019-4?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Shaojie Tang & Jing Yuan, 2023. "Beyond submodularity: a unified framework of randomized set selection with group fairness constraints," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-22, May.
    2. Monroe, Burt L., 1995. "Fully Proportional Representation," American Political Science Review, Cambridge University Press, vol. 89(4), pages 925-940, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shaojie Tang & Jing Yuan, 2023. "Beyond submodularity: a unified framework of randomized set selection with group fairness constraints," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-22, May.
    2. Shaojie Tang & Jing Yuan, 2024. "Group Equality in Adaptive Submodular Maximization," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 359-376, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Markus Brill & Jean-François Laslier & Piotr Skowron, 2018. "Multiwinner approval rules as apportionment methods," Journal of Theoretical Politics, , vol. 30(3), pages 358-382, July.
    2. Haris Aziz & Markus Brill & Vincent Conitzer & Edith Elkind & Rupert Freeman & Toby Walsh, 2017. "Justified representation in approval-based committee voting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(2), pages 461-485, February.
    3. Munger, Michael C, 2000. "Five Questions: An Integrated Research Agenda for Public Choice," Public Choice, Springer, vol. 103(1-2), pages 1-12, April.
    4. Egor Ianovski, 2022. "Electing a committee with dominance constraints," Annals of Operations Research, Springer, vol. 318(2), pages 985-1000, November.
    5. Shaojie Tang & Jing Yuan, 2024. "Group Equality in Adaptive Submodular Maximization," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 359-376, March.
    6. Duddy, Conal, 2014. "Electing a representative committee by approval ballot: An impossibility result," Economics Letters, Elsevier, vol. 124(1), pages 14-16.
    7. Kamwa, Eric, 2017. "On stable rules for selecting committees," Journal of Mathematical Economics, Elsevier, vol. 70(C), pages 36-44.
    8. Adam Graham-Squire & Matthew I. Jones & David McCune, 2024. "New fairness criteria for truncated ballots in multi-winner ranked-choice elections," Papers 2408.03926, arXiv.org.
    9. Richard F. Potthoff & Steven J. Brams, 1998. "Proportional Representation," Journal of Theoretical Politics, , vol. 10(2), pages 147-178, April.
    10. Anna-Sophie Kurella & Salvatore Barbaro, 2024. "On the Polarization Premium for radical parties in PR electoral systems," Working Papers 2410, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    11. Dan Alger, 2006. "Voting by proxy," Public Choice, Springer, vol. 126(1), pages 1-26, January.
    12. Martin Lackner & Piotr Skowron, 2017. "Consistent Approval-Based Multi-Winner Rules," Papers 1704.02453, arXiv.org, revised Oct 2019.
    13. Piotr Faliszewski & Arkadii Slinko & Kolja Stahl & Nimrod Talmon, 2018. "Achieving fully proportional representation by clustering voters," Journal of Heuristics, Springer, vol. 24(5), pages 725-756, October.
    14. Wojciech Maciejewski & Wojciech Kordecki, 2017. "A method of assigning a global preference index," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 27(2), pages 59-75.
    15. Andreas Darmann & Janosch Döcker & Britta Dorn & Sebastian Schneckenburger, 2022. "Simplified group activity selection with group size constraints," International Journal of Game Theory, Springer;Game Theory Society, vol. 51(1), pages 169-212, March.
    16. Shaojie Tang & Jing Yuan, 2023. "Beyond submodularity: a unified framework of randomized set selection with group fairness constraints," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-22, May.
    17. Florian Brandl & Dominik Peters, 2019. "An axiomatic characterization of the Borda mean rule," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 52(4), pages 685-707, April.
    18. Subiza, Begoña & Peris, Josep E., 2014. "A Consensual Committee Using Approval Balloting," QM&ET Working Papers 14-5, University of Alicante, D. Quantitative Methods and Economic Theory.
    19. Dominik Peters & Lan Yu & Hau Chan & Edith Elkind, 2022. "Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results," Post-Print hal-03834509, HAL.
    20. Kamesh Munagala & Yiheng Shen & Kangning Wang & Zhiyi Wang, 2021. "Approximate Core for Committee Selection via Multilinear Extension and Market Clearing," Papers 2110.12499, arXiv.org.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:45:y:2023:i:3:d:10.1007_s10878-023-01019-4. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.