Robust Strategic Classification under Decision-Dependent Cost Uncertainty

• URL: http://arxiv.org/abs/2606.30136v1
• Date: Mon, 29 Jun 2026 11:15:11 GMT
• Title: Robust Strategic Classification under Decision-Dependent Cost Uncertainty
• Abstract summary: Humans have been found to game'' algorithmic decision systems by altering their input data (at a cost to them) in order to favorably change the algorithmic outcomes they receive (at a cost to the algorithm)<n>This paper proposes and analyzes a two-stage robust optimization framework with a decision-dependent uncertainty set to capture such dependencies.<n>We highlight that awareness of policy-dependent costs not only reduces uncertainty, but also better curtails gaming of the algorithmic system over time.
• Score: 3.1351527202068445
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Humans facing algorithmic decision systems have been found to ``game'' them by altering their input data (at a cost to them) in order to favorably change the algorithmic outcomes they receive (at a cost to the algorithm). The growing literature on strategic classification seeks to develop robust machine learning algorithms that account for, and reduce, unwanted strategic behavior. A limitation of these existing works is that they assume the cost of strategic behavior to be fixed and independent of the classifier's decision. In practice, however, manipulation costs evolve and depend on past algorithmic decisions: today's decisions influence tomorrow's costs. This paper proposes and analyzes a two-stage robust optimization framework with a decision-dependent uncertainty set to capture such dependencies. We highlight that awareness of policy-dependent costs not only reduces uncertainty, but also better curtails gaming of the algorithmic system over time.

Related papers

• Strategic Feature Selection [62.74494413516484]
  We study strategic classification through feature selection and its interaction with ridge regularization.<n>We provide a fine-grained characterization of the performance of a feature subset under optimal regularization.<n>Motivated by this characterization, we develop a practical algorithm for jointly choosing the feature set and the level of ridge regularization.
  arXiv  Detail & Related papers  (2026-06-17T09:47:15Z)
• Scalable Decision Focused Learning via Online Trainable Surrogates [9.624413875440233]
  We propose an acceleration method based on replacing costly loss function evaluations with an efficient surrogate.<n>Unlike previously defined surrogates, our approach relies on unbiased estimators reducing the risk of spurious local optima.<n>In our results, the method reduces costly inner solver calls, with a solution quality comparable to other state-of-the-art techniques.
  arXiv  Detail & Related papers  (2025-12-03T15:09:21Z)
• Collective dynamics of strategic classification [49.14942990735098]
  We apply evolutionary game theory to the problem of feedback loops between collectives of users and institutions.<n>We show that increased detection capabilities reduce social costs and could lead to users' improvement.<n>The speed at which the institutions re-adapt to the user's population plays a role in the final outcome.
  arXiv  Detail & Related papers  (2025-08-12T20:57:17Z)
• On strategies for risk management and decision making under uncertainty shared across multiple fields [55.2480439325792]
  The paper finds more than 110 examples of such strategies and this approach to risk is termed RDOT: Risk-reducing Design and Operations Toolkit.<n>RDOT strategies fall into six broad categories: structural, reactive, formal, adversarial, multi-stage and positive.<n>Overall, RDOT represents an overlooked class of versatile responses to uncertainty.
  arXiv  Detail & Related papers  (2023-09-06T16:14:32Z)
• Influence of the algorithm's reliability and transparency in the user's decision-making process [0.0]
  We conduct an online empirical study with 61 participants to find out how the change in transparency and reliability of an algorithm could impact users' decision-making process. The results indicate that people show at least moderate confidence in the decisions of the algorithm even when the reliability is bad.
  arXiv  Detail & Related papers  (2023-07-13T03:13:49Z)
• On solving decision and risk management problems subject to uncertainty [91.3755431537592]
  Uncertainty is a pervasive challenge in decision and risk management. This paper develops a systematic understanding of such strategies, determine their range of application, and develop a framework to better employ them.
  arXiv  Detail & Related papers  (2023-01-18T19:16:23Z)
• Algorithmic Decision-Making Safeguarded by Human Knowledge [8.482569811904028]
  We study the augmentation of algorithmic decisions with human knowledge. We show that when the algorithmic decision is optimal with large data, the non-data-driven human guardrail usually provides no benefit. In these cases, even with sufficient data, the augmentation from human knowledge can still improve the performance of the algorithmic decision.
  arXiv  Detail & Related papers  (2022-11-20T17:13:32Z)
• Early and Revocable Time Series Classification [0.028675177318965035]
  This paper introduces a new problem called early and revocabletimeseries classification. We propose anew cost-based framework and derive two new approaches from it. The ability of revok-ing decisions significantly improves performance over the irrevocable regime.
  arXiv  Detail & Related papers  (2021-09-21T16:09:11Z)
• Modularity in Reinforcement Learning via Algorithmic Independence in Credit Assignment [79.5678820246642]
  We show that certain action-value methods are more sample efficient than policy-gradient methods on transfer problems that require only sparse changes to a sequence of previously optimal decisions. We generalize the recently proposed societal decision-making framework as a more granular formalism than the Markov decision process.
  arXiv  Detail & Related papers  (2021-06-28T21:29:13Z)
• Algorithmic Challenges in Ensuring Fairness at the Time of Decision [6.228560624452748]
  Algorithmic decision-making in societal contexts can be framed as optimization under bandit feedback. Recent lawsuits accuse companies that deploy algorithmic pricing practices of price gouging. We introduce the well-studied fairness notion of envy-freeness within the context of convex optimization.
  arXiv  Detail & Related papers  (2021-03-16T19:06:28Z)
• Non-stationary Online Learning with Memory and Non-stochastic Control [71.14503310914799]
  We study the problem of Online Convex Optimization (OCO) with memory, which allows loss functions to depend on past decisions. In this paper, we introduce dynamic policy regret as the performance measure to design algorithms robust to non-stationary environments. We propose a novel algorithm for OCO with memory that provably enjoys an optimal dynamic policy regret in terms of time horizon, non-stationarity measure, and memory length.
  arXiv  Detail & Related papers  (2021-02-07T09:45:15Z)
• Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
  Off-policy policy optimization is a challenging problem in reinforcement learning. Off-policy algorithms are memory-efficient and capable of learning from off-policy samples.
  arXiv  Detail & Related papers  (2020-09-14T16:22:46Z)

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.