Document Open Access Logo

Making Decisions Under Outcome Performativity

Authors Michael P. Kim, Juan C. Perdomo

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.79.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Michael P. Kim
  • Miller Institute, UC Berkeley,CA, USA
Juan C. Perdomo
  • Department of Computer Science, UC Berkeley, CA, USA

Funding

  • Kim, Michael P.: MPK is supported by the Miller Institute for Basic Research in Science and, in part, by the Simons Collaboration on Algorithmic Fairness.

Acknowledgements

The authors thank Parikshit Gopalan, Moritz Hardt, Celestine Mendler-Dunner, Omer Reingold, and Tijana Zrnic for helpful discussions throughout the development of the project.

Cite AsGet BibTex

Michael P. Kim and Juan C. Perdomo. Making Decisions Under Outcome Performativity. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 79:1-79:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.79

Abstract

Decision-makers often act in response to data-driven predictions, with the goal of achieving favorable outcomes. In such settings, predictions don’t passively forecast the future; instead, predictions actively shape the distribution of outcomes they are meant to predict. This performative prediction setting [Brown et al., 2022] raises new challenges for learning "optimal" decision rules. In particular, existing solution concepts do not address the apparent tension between the goals of forecasting outcomes accurately and steering individuals to achieve desirable outcomes. To contend with this concern, we introduce a new optimality concept - performative omniprediction - adapted from the supervised (non-performative) learning setting [Gopalan et al., 2022]. A performative omnipredictor is a single predictor that simultaneously encodes the optimal decision rule with respect to many possibly-competing objectives. Our main result demonstrates that efficient performative omnipredictors exist, under a natural restriction of performative prediction, which we call outcome performativity. On a technical level, our results follow by carefully generalizing the notion of outcome indistinguishability [Cynthia Dwork et al., 2021] to the outcome performative setting. From an appropriate notion of Performative OI, we recover many consequences known to hold in the supervised setting, such as omniprediction and universal adaptability [Kim et al., 2022].

Subject Classification

ACM Subject Classification
  • Theory of computation → Theory and algorithms for application domains
Keywords
  • performative prediction
  • outcome indistinguishability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Robert Balfanz and Vaughan Byrnes. Early warning indicators and intervention systems: State of the field. Handbook of student engagement interventions, pages 45-55, 2019. Google Scholar
  2. Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in a stateful world. In International Conference on Artificial Intelligence and Statistics, pages 6045-6061. PMLR, 2022. Google Scholar
  3. Joshua Cutler, Dmitriy Drusvyatskiy, and Zaid Harchaoui. Stochastic optimization under distributional drift. arXiv preprint, 2021. URL: http://arxiv.org/abs/2108.07356.
  4. Dmitriy Drusvyatskiy and Lin Xiao. Stochastic optimization with decision-dependent distributions. Mathematics of Operations Research, 2022. Google Scholar
  5. Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Outcome indistinguishability. In ACM Symposium on Theory of Computing (STOC'21), 2021. URL: http://arxiv.org/abs/2011.13426.
  6. Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Beyond bernoulli: Generating random outcomes that cannot be distinguished from nature. In International Conference on Algorithmic Learning Theory, pages 342-380. PMLR, 2022. Google Scholar
  7. Charles Elkan. The foundations of cost-sensitive learning. In International joint conference on artificial intelligence, volume 17, pages 973-978. Lawrence Erlbaum Associates Ltd, 2001. Google Scholar
  8. Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder. Loss minimization through the lens of outcome indistinguishability. Manuscript, 2022. Google Scholar
  9. Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors. In ITCS, 2022. Google Scholar
  10. Moritz Hardt, Meena Jagadeesan, and Celestine Mendler-Dünner. Performative power. arXiv preprint, 2022. URL: http://arxiv.org/abs/2203.17232.
  11. Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111-122, 2016. Google Scholar
  12. Ursula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning, pages 1939-1948. PMLR, 2018. Google Scholar
  13. Zachary Izzo, Lexing Ying, and James Zou. How to learn when data reacts to your model: performative gradient descent. In International Conference on Machine Learning, pages 4641-4650. PMLR, 2021. Google Scholar
  14. Zachary Izzo, James Zou, and Lexing Ying. How to learn when data gradually reacts to your model. In International Conference on Artificial Intelligence and Statistics, pages 3998-4035. PMLR, 2022. Google Scholar
  15. Meena Jagadeesan, Tijana Zrnic, and Celestine Mendler-Dünner. Regret minimization with performative feedback. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 9760-9785. PMLR, 17-23 July 2022. Google Scholar
  16. Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, and Rakesh Vohra. Moment multicalibration for uncertainty estimation. In Conference on Learning Theory, pages 2634-2678. PMLR, 2021. Google Scholar
  17. Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International Conference on Machine Learning, pages 2564-2572. PMLR, 2018. Google Scholar
  18. Michael P. Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 247-254, 2019. Google Scholar
  19. Michael P. Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold. Universal adaptability: Target-independent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 119(4):e2108097119, 2022. Google Scholar
  20. Michael P Kim and Juan C Perdomo. Making decisions under outcome performativity. arXiv preprint, 2022. URL: http://arxiv.org/abs/2210.01745.
  21. Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Fairness through computationally-bounded awareness. Advances in Neural Information Processing Systems, 31, 2018. Google Scholar
  22. Jon Kleinberg, Jens Ludwig, Sendhil Mullainathan, and Ziad Obermeyer. Prediction policy problems. American Economic Review, 105(5):491-95, 2015. Google Scholar
  23. Celestine Mendler-Dünner, Frances Ding, and Yixin Wang. Predicting from predictions. arXiv preprint, 2022. URL: http://arxiv.org/abs/2208.07331.
  24. Celestine Mendler-Dünner, Juan Perdomo, Tijana Zrnic, and Moritz Hardt. Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems, 33:4929-4939, 2020. Google Scholar
  25. John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In International Conference on Machine Learning, pages 6917-6926. PMLR, 2020. Google Scholar
  26. John P Miller, Juan C Perdomo, and Tijana Zrnic. Outside the echo chamber: Optimizing the performative risk. In International Conference on Machine Learning, pages 7710-7720. PMLR, 2021. Google Scholar
  27. Adhyyan Narang, Evan Faulkner, Dmitriy Drusvyatskiy, Maryam Fazel, and Lillian J Ratliff. Multiplayer performative prediction: Learning in decision-dependent games. arXiv preprint, 2022. URL: http://arxiv.org/abs/2201.03398.
  28. Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pages 7599-7609. PMLR, 2020. Google Scholar
  29. Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. Google Scholar
  30. US Department of Education. Issue brief: Early warning systems. Office of Planning, Evaluation and Policy Development, 2016. Available at URL: https://www2.ed.gov/rschstat/eval/high-school/early-warning-systems-brief.pdf.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact