research-article

Meritocratic Fairness for Infinite and Contextual Bandits

Authors:

Matthew Joseph,

Michael Kearns,

Jamie Morgenstern,

Aaron RothAuthors Info & Claims

AIES '18: Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society

Pages 158 - 163

https://doi.org/10.1145/3278721.3278764

Published: 27 December 2018 Publication History

Abstract

We study fairness in linear bandit problems. Starting from the notion of meritocratic fairness introduced in~\citeJKMR16, we carry out a more refined analysis of a more general problem, achieving better performance guarantees with fewer modelling assumptions on the number and structure of available choices as well as the number selected. We also analyze the previously-unstudied question of fairness in infinite linear bandit problems, obtaining instance-dependent regret upper bounds as well as lower bounds demonstrating that this instance-dependence is necessary. The result is a framework for meritocratic fairness in an online linear setting that is substantially more powerful, general, and realistic than the current state of the art.

References

[1]

Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. 2011. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems. 2312--2320.

Digital Library

[2]

Naoki Abe, Alan W Biermann, and Philip M Long. 2003. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, Vol. 37, 4 (2003), 263--293.

Digital Library

[3]

Venkatachalam Anantharam, Pravin Varaiya, and Jean Walrand. 1987. Asymptotically Efficient Allocation Rules for the Multiarmed Bandit Problem with Multiple Plays -- Part I: I.I.D. Rewards. IEEE Trans. Automat. Control, Vol. AC-32, Nov (1987), 968--976.

[4]

Peter Auer. 2002. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, Vol. 3, Nov (2002), 397--422.

Digital Library

[5]

Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. 2017. Fairness in Criminal Justice Risk Assessments: The State of the Art. arXiv preprint arXiv:1703.09207 (2017).

[6]

Alexandra Chouldechova. 2017. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. arXiv preprint arXiv:1703.00056 (2017).

[7]

Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. 2017. Algorithmic decision making and the cost of fairness. arXiv preprint arXiv:1701.08230 (2017).

Digital Library

[8]

Varsha Dani, Thomas P Hayes, and Sham M Kakade. 2008. Stochastic Linear Optimization under Bandit Feedback. In COLT. 355--366.

[9]

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012. Fairness through awareness. In Proceedings of ITCS 2012. ACM, 214--226.

Digital Library

[10]

Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. 2005. Online convex optimization in the bandit setting: gradient descent without a gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 385--394.

Digital Library

[11]

Sorelle A. Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. 2016. On the (im)possibility of fairness. In arXiv, Vol. abs/1609.07236. http://arxiv.org/abs/1609.07236

[12]

Moritz Hardt, Eric Price, and Nathan Srebro. 2016. Equality of Opportunity in Supervised Learning. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5--10, 2016, Barcelona, Spain, Vol. abs/1610.02413. http://arxiv.org/abs/1610.02413

Digital Library

[13]

Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. 2016a. Fairness in learning: Classic and contextual bandits. In Advances in Neural Information Processing Systems. 325--333.

Digital Library

[14]

Matthew Joseph, Michael J. Kearns, Jamie Morgenstern, Seth Neel, and Aaron Roth. 2016b. Fair Algorithms for Infinite and Contextual Bandits. CoRR, Vol. abs/1610.09559 (2016). http://arxiv.org/abs/1610.09559

[15]

J. Kleinberg, S. Mullainathan, and M. Raghavan. 2017. Inherent Trade-Offs in the Fair Determination of Risk Scores. In ITCS .

[16]

Blake Woodworth, Suriya Gunasekar, Mesrob I Ohannessian, and Nathan Srebro. 2017. Learning Non-Discriminatory Predictors. arXiv preprint arXiv:1702.06081 (2017).

[17]

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi. 2017. Fairness Beyond Disparate Treatment and Disparate Impact: Learning Classification without Disparate Mistreatment. In Proceedings of World Wide Web Conference .

Digital Library

Cited By

Chang PFishman LNeel SSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Feature importance disparities for data bias investigationsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692309(6170-6201)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692309
Bechavod YSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Monotone individual fairnessProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692200(3266-3283)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692200
Caton SHaas C(2024)Fairness in Machine Learning: A SurveyACM Computing Surveys10.1145/361686556:7(1-38)Online publication date: 9-Apr-2024
https://dl.acm.org/doi/10.1145/3616865
Show More Cited By

Index Terms

Meritocratic Fairness for Infinite and Contextual Bandits
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory

Recommendations

Fairness and Privacy Guarantees in Federated Contextual Bandits
AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

This paper studies the contextual multi-armed bandit problem with fairness and privacy guarantees in a federated setting. It proposes a collaborative algorithm, Fed-FairX-LinUCB, that achieves sub-linear fairness regret and can be adapted to ensure ...
Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits
AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems

Existing approaches to fairness in stochastic multi-armed bandits (MAB) primarily focus on exposure guarantee to individual arms. When arms are naturally grouped by certain attribute(s), we propose Bi-Level Fairness, which considers two levels of ...
Airtime Fairness for IEEE 802.11 Multirate Networks

Under a multi rate network scenario, the IEEE 802.11 DCF MAC fails to provide air-time fairness for all competing stations since the protocol is designed for ensuring max-min throughput fairness and the maximum achievable throughput by any station gets ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

AIES '18: Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society

December 2018

406 pages

ISBN:9781450360128

DOI:10.1145/3278721

Program Chairs:
Jason Furman
Harvard University, USA
,
Gary Marchant
Arizona State University, USA
,
Huw Price
Cambridge University, UK
,
Francesca Rossi
IBM Research, USA & University of Padova, Italy

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 December 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

AIES '18

Sponsor:

SIGAI

AIES '18: AAAI/ACM Conference on AI, Ethics, and Society

February 2 - 3, 2018

LA, New Orleans, USA

Acceptance Rates

AIES '18 Paper Acceptance Rate 61 of 162 submissions, 38%;

Overall Acceptance Rate 61 of 162 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
250
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)3

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chang PFishman LNeel SSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Feature importance disparities for data bias investigationsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692309(6170-6201)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692309
Bechavod YSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Monotone individual fairnessProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692200(3266-3283)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692200
Caton SHaas C(2024)Fairness in Machine Learning: A SurveyACM Computing Surveys10.1145/361686556:7(1-38)Online publication date: 9-Apr-2024
https://dl.acm.org/doi/10.1145/3616865
Puranik BGuldogan OMadhow UPedarsani R(2024)Long-Term Fairness in Sequential Multi-Agent Selection With Positive ReinforcementIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2024.34160785(424-441)Online publication date: 2024
https://doi.org/10.1109/JSAIT.2024.3416078
Wei WMa XWang JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Fair adaptive experimentsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666962(19157-19169)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666962
Bechavod YRoth AKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Individually fair learning with one-sided feedbackProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618490(1954-1977)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618490
Hort MChen ZZhang JHarman MSarro F(2023)Bias Mitigation for Machine Learning Classifiers: A Comprehensive SurveyACM Journal on Responsible Computing10.1145/36313261:2(1-52)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1145/3631326
Dash AChakraborty AGhosh SMukherjee AGummadi K(2023)FaiRIR: Mitigating Exposure Bias From Related Item Recommendations in Two-Sided PlatformsIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.316465510:3(1301-1313)Online publication date: Jun-2023
https://doi.org/10.1109/TCSS.2022.3164655
Grazzi RAkhavan AFalk JCella LPontil MKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Group meritocratic fairness in linear contextual banditsProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602041(24392-24404)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602041
Puranik BMadhow UPedarsani RConitzer VTasioulas JScheutz MCalo RMara MZimmermann A(2022)A Dynamic Decision-Making Framework Promoting Long-Term FairnessProceedings of the 2022 AAAI/ACM Conference on AI, Ethics, and Society10.1145/3514094.3534127(547-556)Online publication date: 26-Jul-2022
https://dl.acm.org/doi/10.1145/3514094.3534127
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents