Fair Secretaries with Unfair Predictions

• URL: http://arxiv.org/abs/2411.09854v1
• Date: Fri, 15 Nov 2024 00:23:59 GMT
• Title: Fair Secretaries with Unfair Predictions
• Authors: Eric Balkanski, Will Ma, Andreas Maggiori,
• Abstract summary: We show that an algorithm can have zero probability of accepting the best candidate, which we deem unfair, despite promising to accept a candidate whose expected value is at least $maxOmega (1), 1 - O(epsilon)$ times the optimal value, where $epsilon$ is the prediction error. Our algorithm and analysis are based on a new "pegging" idea that diverges from existing works and simplifies/unifies some of their results.
• Score: 12.756552522270198
• License:
• Abstract: Algorithms with predictions is a recent framework for decision-making under uncertainty that leverages the power of machine-learned predictions without making any assumption about their quality. The goal in this framework is for algorithms to achieve an improved performance when the predictions are accurate while maintaining acceptable guarantees when the predictions are erroneous. A serious concern with algorithms that use predictions is that these predictions can be biased and, as a result, cause the algorithm to make decisions that are deemed unfair. We show that this concern manifests itself in the classical secretary problem in the learning-augmented setting -- the state-of-the-art algorithm can have zero probability of accepting the best candidate, which we deem unfair, despite promising to accept a candidate whose expected value is at least $\max\{\Omega (1) , 1 - O(\epsilon)\}$ times the optimal value, where $\epsilon$ is the prediction error. We show how to preserve this promise while also guaranteeing to accept the best candidate with probability $\Omega(1)$. Our algorithm and analysis are based on a new "pegging" idea that diverges from existing works and simplifies/unifies some of their results. Finally, we extend to the $k$-secretary problem and complement our theoretical analysis with experiments.

Related papers

• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  We introduce the notion of a margin complement, which measures how much a prediction score $S$ changes due to a thresholding operation. We show that under suitable causal assumptions, the influences of $X$ on the prediction score $S$ are equal to the influences of $X$ on the true outcome $Y$.
  arXiv  Detail & Related papers  (2024-05-24T11:22:19Z)
• Non-clairvoyant Scheduling with Partial Predictions [17.387787159892287]
  We present a learning-augmented algorithm satisfying the robustness, consistency, and smoothness criteria. We also present a novel tradeoff between consistency and smoothness inherent in the scenario with a restricted number of predictions.
  arXiv  Detail & Related papers  (2024-05-02T05:29:22Z)
• PAC Prediction Sets Under Label Shift [52.30074177997787]
  Prediction sets capture uncertainty by predicting sets of labels rather than individual labels. We propose a novel algorithm for constructing prediction sets with PAC guarantees in the label shift setting. We evaluate our approach on five datasets.
  arXiv  Detail & Related papers  (2023-10-19T17:57:57Z)
• Zero-Regret Performative Prediction Under Inequality Constraints [5.513958040574729]
  This paper studies performative prediction under inequality constraints. We develop a robust primal-dual framework that requires only approximate up to a certain accuracy. We then propose an adaptive primal-dual algorithm for location families.
  arXiv  Detail & Related papers  (2023-09-22T04:54:26Z)
• Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
  We study learning-augmented algorithms for sorting and hypergraph orientation under uncertainty. Our algorithms provide improved performance guarantees for accurate predictions while maintaining worst-case guarantees that are best possible without predictions.
  arXiv  Detail & Related papers  (2023-05-16T07:52:08Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of $T$ days (or times) The goal is to make a prediction with the minimum cost, specifically compared to the best expert in the set. We show a space lower bound of $widetildeOmegaleft(fracnMRTright)$ for any deterministic algorithm that achieves regret $R$ when the best expert makes $M$ mistakes.
  arXiv  Detail & Related papers  (2023-03-03T04:39:53Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  We study the use of multiple predictors for a number of fundamental problems, including matching, load balancing, and non-clairvoyant scheduling. For each of these problems we introduce new algorithms that take advantage of multiple predictors, and prove bounds on the resulting performance.
  arXiv  Detail & Related papers  (2022-10-22T12:58:07Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
  arXiv  Detail & Related papers  (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)
• Online Multivalid Learning: Means, Moments, and Prediction Intervals [16.75129633574157]
  We present a technique for providing contextual predictions that are "multivalid" in various senses. The resulting estimates correctly predict various statistics of the labels $y$ not just marginally. Because our algorithms handle adversarially chosen examples, they can equally well be used to predict statistics of the residuals of arbitrary point prediction methods.
  arXiv  Detail & Related papers  (2021-01-05T19:08:11Z)
• Malicious Experts versus the multiplicative weights algorithm in online prediction [85.62472761361107]
  We consider a prediction problem with two experts and a forecaster. We assume that one of the experts is honest and makes correct prediction with probability $mu$ at each round. The other one is malicious, who knows true outcomes at each round and makes predictions in order to maximize the loss of the forecaster.
  arXiv  Detail & Related papers  (2020-03-18T20:12:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.