Mistake, Manipulation and Margin Guarantees in Online Strategic Classification

• URL: http://arxiv.org/abs/2403.18176v1
• Date: Wed, 27 Mar 2024 01:05:45 GMT
• Title: Mistake, Manipulation and Margin Guarantees in Online Strategic Classification
• Authors: Lingqing Shen, Nam Ho-Nguyen, Khanh-Hung Giang-Tran, Fatma Kılınç-Karzan,
• Abstract summary: We consider an online strategic classification problem where each arriving agent can manipulate their true feature vector to obtain a positive predicted label. We prove convergence, finite mistake and finite manipulation guarantees for a variety of agent cost structures. Our numerical study on real and synthetic data demonstrates that the new algorithms outperform previous ones in terms of margin, number of manipulation and number of mistakes.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider an online strategic classification problem where each arriving agent can manipulate their true feature vector to obtain a positive predicted label, while incurring a cost that depends on the amount of manipulation. The learner seeks to predict the agent's true label given access to only the manipulated features. After the learner releases their prediction, the agent's true label is revealed. Previous algorithms such as the strategic perceptron guarantee finitely many mistakes under a margin assumption on agents' true feature vectors. However, these are not guaranteed to encourage agents to be truthful. Promoting truthfulness is intimately linked to obtaining adequate margin on the predictions, thus we provide two new algorithms aimed at recovering the maximum margin classifier in the presence of strategic agent behavior. We prove convergence, finite mistake and finite manipulation guarantees for a variety of agent cost structures. We also provide generalized versions of the strategic perceptron with mistake guarantees for different costs. Our numerical study on real and synthetic data demonstrates that the new algorithms outperform previous ones in terms of margin, number of manipulation and number of mistakes.

Related papers

• Strategic Classification With Externalities [11.36782598786846]
  We propose a new variant of the strategic classification problem. Motivated by real-world applications, our model crucially allows the manipulation of one agent to affect another. We show that under certain assumptions, the pure Nash Equilibrium of this agent manipulation game is unique and can be efficiently computed.
  arXiv  Detail & Related papers  (2024-10-10T15:28:04Z)
• Multi-Agent Imitation Learning: Value is Easy, Regret is Hard [52.31989962031179]
  We study a multi-agent imitation learning (MAIL) problem where we take the perspective of a learner attempting to coordinate a group of agents. Most prior work in MAIL essentially reduces the problem to matching the behavior of the expert within the support of the demonstrations. While doing so is sufficient to drive the value gap between the learner and the expert to zero under the assumption that agents are non-strategic, it does not guarantee to deviations by strategic agents.
  arXiv  Detail & Related papers  (2024-06-06T16:18:20Z)
• Learnability Gaps of Strategic Classification [68.726857356532]
  We focus on addressing a fundamental question: the learnability gaps between strategic classification and standard learning. We provide nearly tight sample complexity and regret bounds, offering significant improvements over prior results. Notably, our algorithm in this setting is of independent interest and can be applied to other problems such as multi-label learning.
  arXiv  Detail & Related papers  (2024-02-29T16:09:19Z)
• Fundamental Bounds on Online Strategic Classification [13.442155854812528]
  We show that no deterministic algorithm can achieve a mistake bound $o(Delta)$ in the strategic setting. We also extend this to the agnostic setting and obtain an algorithm with a $Delta$ multiplicative regret. We design randomized algorithms that achieve sublinear regret bounds against both oblivious and adaptive adversaries.
  arXiv  Detail & Related papers  (2023-02-23T22:39:43Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  We consider a distributed reinforcement learning setting where multiple agents explore the environment and communicate their experiences through a central server. $alpha$-fraction of agents are adversarial and can report arbitrary fake information. We seek to identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents.
  arXiv  Detail & Related papers  (2022-06-01T00:44:53Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  Real-world machine learning deployments are characterized by mismatches between the source (training) and target (test) distributions. In this work, we investigate methods for predicting the target domain accuracy using only labeled source data and unlabeled target data. We propose Average Thresholded Confidence (ATC), a practical method that learns a threshold on the model's confidence, predicting accuracy as the fraction of unlabeled examples.
  arXiv  Detail & Related papers  (2022-01-11T23:01:12Z)
• Distribution-free uncertainty quantification for classification under label shift [105.27463615756733]
  We focus on uncertainty quantification (UQ) for classification problems via two avenues. We first argue that label shift hurts UQ, by showing degradation in coverage and calibration. We examine these techniques theoretically in a distribution-free framework and demonstrate their excellent practical performance.
  arXiv  Detail & Related papers  (2021-03-04T20:51:03Z)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  We study the problem of decision-making in the setting of a scarcity of shared resources when the preferences of agents are unknown a priori. Our approach is based on the representation of preferences in a reproducing kernel Hilbert space. We derive optimal strategies that maximize agents' expected payoffs.
  arXiv  Detail & Related papers  (2020-10-29T03:08:22Z)
• The Strategic Perceptron [11.078814063722803]
  In presence of strategic agents that desire to be classified as positive, the Perceptron algorithm may not be able to observe the true position of agents. We show examples with the predictor oscillating between two solutions forever, making an unbounded number of mistakes. Our main contribution is providing a modified Perceptron-style algorithm which makes a bounded number of mistakes in presence of strategic agents.
  arXiv  Detail & Related papers  (2020-08-04T17:20:24Z)
• No-Regret and Incentive-Compatible Online Learning [29.267666165169324]
  We study online learning settings in which experts act strategically to maximize their influence on the learning algorithm's predictions. We want the learning algorithm to be no-regret with respect to the best fixed expert in hindsight. We provide algorithms that achieve no regret and incentive compatibility for experts for both the full and partial information settings.
  arXiv  Detail & Related papers  (2020-02-20T16:21:34Z)
• Bounded Incentives in Manipulating the Probabilistic Serial Rule [8.309903898123526]
  Probabilistic Serial is not incentive-compatible. A substantial utility gain through strategic behaviors would trigger self-interested agents to manipulate the mechanism. We show that the incentive ratio of the mechanism is $frac32$.
  arXiv  Detail & Related papers  (2020-01-28T23:53:37Z)

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.