Desirable Effort Fairness and Optimality Trade-offs in Strategic Learning

Chara Podimata; Ekaterina Fedorova; Valia Efthymiou

REVIEW 3 major objections 4 minor 2 cited by

This paper establishes closed-form upper bounds on how much accuracy or social welfare a principal sacrifices when constraining a strategic classifier to keep desirable-effort incentives fair across two agent groups.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 08:43 UTC pith:TW43Q2LV

load-bearing objection The model and the social-welfare bounds are genuinely new, but the accuracy-loss results are built on a false equivalence in Lemma A.2 and should not be trusted as written. the 3 major comments →

arxiv 2510.19098 v2 pith:TW43Q2LV submitted 2025-10-21 cs.GT cs.CY

Desirable Effort Fairness and Optimality Trade-offs in Strategic Learning

Valia Efthymiou , Ekaterina Fedorova , Chara Podimata This is my paper

classification cs.GT cs.CY MSC 91A6591A1068T01

keywords strategic learningdesirable effort fairnessoptimality lossStackelberg equilibriumcausal feature dependencepeer learningheterogeneous agentsfairness-constrained optimization

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper asks how much a decision-maker (principal) must sacrifice in accuracy or social welfare to make the incentives his scoring rule creates fair with respect to externally desirable feature changes. It models two groups of agents who best respond to a peer-learned estimate of the rule, pay group-specific quadratic costs, and alter features through a causal graph, while a stakeholder defines a desirability discrepancy function and a tolerance beta. The central result is a set of upper bounds on the principal's optimality loss in any beta-fair Stackelberg equilibrium, expressed directly in setting parameters such as C, A_g, Pi_g, Pi_D, w*, and beta, for convex discrepancy functions and for a class of nonconvex asymmetric functions via a convex ellipsoidal restriction. If these bounds hold, a principal can precompute the worst-case price of fairness and choose beta deliberately rather than by trial and error.

Core claim

For a principal who maximizes accuracy or social welfare and must keep a stakeholder-defined desirability-discrepancy function Delta(w) below a tolerance beta, the optimality loss in equilibrium is bounded by closed-form functions of the setting parameters. When Delta is convex and its beta-fair set is polyhedral or ellipsoidal, the loss bounds depend on quantities like the Hoffman constant, the smallest eigenvalue of the ellipsoid matrix Q, and the distance of the ground-truth rule from the fair set. When Delta is nonconvex, such as an asymmetric comparison that lets a privileged group receive more incentives, the paper restricts the feasible set to its ellipsoidal core, bounds the loss in

What carries the argument

The load-bearing object is the desirability-effort discrepancy function Delta(w) = Dist(Pi_D A_1^{-1} C^T Pi_1 w, Pi_D A_2^{-1} C^T Pi_2 w), which measures how differently the two groups' best-response efforts, weighted by stakeholder desirability scores, respond to the deployed rule w. The beta-fair feasible set W(beta; Delta) = {w : Delta(w) <= beta} is the mechanism connecting fairness to optimality: depending on the stakeholder's choice of Dist, W is a polyhedron (sum of absolute differences), an ellipsoid (sum of squared differences), or a nonconvex set with an ellipsoidal core (asymmetric squared norms). The proofs ride on the closed-form best response x_e = A_g^{-1} C^T Pi_g w, which

Load-bearing premise

The entire analysis assumes each agent knows the causal contribution matrix C, knows her cost matrix A_g, and recovers the principal's rule exactly as Pi_g w from peer data, so that her best-response effort is precisely A_g^{-1} C^T Pi_g w; if any of these is estimated or noisy, the desirability-effort vectors change and the paper's bounds no longer apply.

What would settle it

Take a two-group setting with known C, A_g, Pi_g, w*, and a discrepancy function satisfying Property 3.2; compute the paper's bound, then run the same beta-fair game with agents who observe only a noisy peer estimate (w_est = Pi_g w + epsilon) or a perturbed causal matrix C_hat. If the realized accuracy or welfare loss ever exceeds the bound at a tolerance beta within the stated range, the claimed guarantee is false.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

A principal who knows or can estimate C, A_g, Pi_g, Pi_D, and w* can compute an upper bound on how much accuracy or welfare he gives up at any chosen beta, turning fairness tolerance into a quantifiable budget.
For discrepancy functions like sum of absolute or squared differences, the fairness-constrained problem is a tractable convex program, and the bounds hold across whole classes of such functions rather than case by case.
For nonconvex asymmetric discrepancies, a principal can still deploy a tractable ellipsoidal restriction and bound both the equilibrium loss and the extra loss from convexification using the Lipschitz constant and the diameter of the fair space.
As beta grows, constrained optimal values approach the unconstrained optimum; the experiments show the recovery rate depends on how aligned group disparity is with the desirable features, not just on beta.
Accuracy loss is more sensitive than social-welfare loss to information disparity between groups, while cost disparity affects both objectives.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If agents' causal knowledge is imperfect, the paper's bounds are likely to understate real loss, since the entire chain from Delta(w) to the feasible region starts from the exact best response x_e = A_g^{-1} C^T Pi_g w; an immediate test is to replace C and Pi_g w with noisy estimates and measure how often the bounds are violated.
The same geometric machinery should extend to more than two groups if Delta is generalized to a maximum pairwise discrepancy, but the polyhedral and ellipsoidal properties and the constants in the bounds would need re-derivation.
The restriction-envelope analysis suggests a practical selection rule for beta: choose the smallest beta for which the difference between the envelope and restriction bounds is acceptable, since that difference upper-bounds the cost of tractability.
Because the stakeholder chooses Delta, the principal's optimality loss is partly a function of a political choice; a robust principal could hedge by considering a family of Delta functions and taking the worst-case bound across them.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

The model and the social-welfare bounds are genuinely new, but the accuracy-loss results are built on a false equivalence in Lemma A.2 and should not be trusted as written.

read the letter

Quick take: this paper has one genuinely new and useful modeling contribution, and one load-bearing mistake. The mistake is in Lemma A.2, and it undermines every accuracy-loss bound in Table 1.

What's genuinely new: the unified Stackelberg model with causal contribution matrix C, peer learning, two heterogeneous groups, desirability-weighted effort, and a fairness constraint on the discrepancy between groups' desirable effort. That combination hasn't been treated together before, and the paper is honest about the modeling assumptions. The social-welfare side is clean: Lemma A.3 correctly reduces SW to a linear objective in w, and the ellipsoid/polyhedron bounds for SW (Props A.2, A.4, A.9, A.11) are standard projection/KKT arguments that look sound. The section-5 experiments give an instructive illustration of how group splits aligned with desirable features produce larger accuracy loss under a fixed beta.

The soft spots are serious. Lemma A.2 claims accuracy is equivalent to -||w*-w||^2. That equivalence would be true if agents' modified features x' had identity second moment and no dependence on w. But x' = x + B_g w with B_g = C A_g^{-1} C^T Pi_g. So E[((w*-w)^T x')^2] = (w*-w)^T (I + B_g w w^T B_g^T + cross terms) (w*-w), which is not ||w*-w||^2. A simple one-dimensional example: C=A_g=Pi_g=1, x~N(0,1), w*=1 gives ACC(w) = -(1-w)^2(1+w^2). The proof's step from the quadratic form to the Euclidean norm is invalid. Since Props A.3, A.5, A.9, A.11 and the accuracy rows of Table 1 all invoke this lemma, those bounds do not follow from the presented arguments. This is not the acknowledged limitation about agents' knowledge of C; it is an internal algebraic error under the paper's own definitions.

Other smaller issues: the appendix has typos and garbled algebra (Table 1's symbols, parts of Prop A.2), the nonconvex class F in Definition 4.1 is defined ad hoc to be amenable to an ellipsoidal envelope, and the experiments lack error bars and code, with edge weights only described as 'sampled'. None of these are fatal on their own, but they add friction.

Bottom line: the paper is worth refereeing, not because the current accuracy claims hold, but because the model and the SW results are interesting and the accuracy error is identifiable and potentially fixable. I'd send it to review with a strong instruction to the authors to correct Lemma A.2 or drop the accuracy bounds. If the lemma can't be repaired, the paper becomes a much smaller contribution.

Referee Report

3 major / 4 minor

Summary. The paper studies a Stackelberg strategic-classification game in which a principal maximizes accuracy or social welfare subject to a 'desirability fairness' constraint on the discrepancy between two agent groups' incentivized effort, under causal feature dependencies, heterogeneous costs, and peer learning. It claims upper bounds on the principal's optimality loss as a function of the fairness tolerance beta, for convex discrepancy functions (Table 1) and for a class of nonconvex discrepancy functions via an ellipsoidal restriction (Section 4). Experiments on the ADULT dataset illustrate the trade-off. The central theoretical contribution is the collection of worst-case optimality-loss bounds in terms of the primitive parameters C, A_g, Pi_g, w*, and beta.

Significance. If the bounds were correct, the paper would provide a useful toolkit for a principal to reason about the price of fair desirable-effort incentives without committing to a single discrepancy function. The model is well motivated and the unified treatment of causality, heterogeneous costs, and peer learning is a worthwhile framing. However, the accuracy-side bounds rest on an algebraic equivalence (Lemma A.2) that is false under the paper's own definitions, and at least one social-welfare bound (Proposition A.2) is also incorrect. These are load-bearing errors: the headline accuracy-loss guarantees do not follow from the presented arguments. The empirical section, while interesting, cannot compensate for the invalid theory.

major comments (3)

[Appendix A.1.3, Lemma A.2] The claimed equivalence ACC(w;w*) = -||w*-w||^2 is algebraically false. With x' = x + C A_g^{-1} C^T Pi_g w = x + B_g w, the accuracy objective is -sum_g E[((w*-w)^T x + (w*-w)^T B_g w)^2]; even for E[x]=0 and E[xx^T]=I, the extra term ((w*-w)^T B_g w)^2 remains and is generally nonzero. Example: d=1, C=A_g=Pi_g=1, x~N(0,1), w*=1 gives ACC(w) = -(1-w)^2(1+w^2), not -(1-w)^2. Since Propositions A.3, A.5, A.9, A.11 and all accuracy rows of Table 1 invoke Lemma A.2 to reduce accuracy to Euclidean projection, the accuracy-side guarantees are unsupported. This is an internal error under the paper's own definitions, distinct from the acknowledged Section 6 limitation about agents' knowledge of C.
[Appendix A.2.1, Proposition A.2] The claimed constant upper bound sqrt(2) on social-welfare loss for any ellipsoidal beta-fair space (Property 3.2) is false. For d=1, take Q=2, beta=1 (so W(beta) subset B(1)) and let c = (C A_1^{-1} C^T Pi_1 + C A_2^{-1} C^T Pi_2)^T w* have norm 10. The unconstrained value is 10, while the constrained optimum is 10/sqrt(2) ~ 7.07, so the loss is ~2.93 > sqrt(2). The proof's 'generalized Pythagorean' step is dimensionally wrong (it writes ||w*_c - w*_u|| <= ||w*_c||^2 + ||w*_u||^2 - 2cos(...), omitting norms and the square root). The correct loss formula, given in Proposition A.4, is ||c|| - sqrt(beta)||c||_{Q^{-1}}, which is unbounded. Thus the SW bound in Table 1 (Property 3.2 row) is invalid.
[Definition 4.1 and Section 4] The nonconvex results apply only to the class F defined by Delta(w)=w^T Q w - f(w) with f nonnegative, L-Lipschitz, and beta <= lambda_d(Q). This is an ad hoc structural assumption, and the paper does not show that natural asymmetric discrepancy measures—beyond the one constructed in Example 4.1—fall into F. The abstract's claim of results for 'multiple broad classes of fairness measures' is therefore overstated. Given that the convex accuracy and SW bounds also fail as noted above, the theoretical contribution is not established even for the convex case.

minor comments (4)

[Table 1] The table is garbled: the row/column labels and entries are not legible in the text (e.g., 'Prop. 3.1 Prop. 3.2 Prop. 3.3 Accuracy SW' appears as a single line, and the mathematical expressions are misformatted). The reader cannot verify the advertised bounds.
[Appendix A.2.1, Examples A.1 and A.2] Example A.2 is internally inconsistent: it first states Pi_g = I_2, then sets Pi_1 := diag(1/2,1/2) and Pi_2 := diag(1,1). The displayed bound contains mismatched parentheses: '[(1/8-beta)^+ + (7/8-beta)^2]' is missing a square on the first term. These are presentation errors but hinder reproducibility.
[Proposition A.2 proof] The proof writes w*_c = Q^{-1} c / c^T Q c, which is inconsistent with Lemma A.4 (missing the sqrt(beta) and normalization by ||sqrt(Q^{-1})c||). This is likely a typo, but it obscures the argument and contributes to the incorrect bound.
[Section 2.1] The notation 'I...' is broken (likely a missing indicator-function definition). The Notation Table 2 is referenced but the table numbering is off (the first table is Table 1 in Section 3).

Circularity Check

0 steps flagged

No significant circularity: trade-off bounds follow from the stated model inputs; Lemma A.2's accuracy reduction is a correctness concern, not a circular one.

full rationale

The claimed derivation chain starts from the model inputs (C, A_g, Π_g, w*, β) and imported peer-learning best response x_e = A_g^{-1} C^T Π_g w (Prop. 2.1, from Lemma 3.1 of [7] and the causal-effort model of [16]). The optimality-loss bounds in Table 1 and Propositions A.1-A.5/A.9/A.11 are then obtained by Lipschitzness, convexity/ellipsoid geometry, and projection/Hoffman arguments; they introduce no fitted constants and do not rename the fairness constraint as a prediction. The self-citations [7] and [16] are load-bearing as model components, but they are external results with stated assumptions that do not include the trade-off bounds, so they do not make the derivation circular. I do flag Appendix A.1.3, Lemma A.2, where the accuracy objective is reduced to -||w*-w||^2 by jumping from the expected quadratic form in \hat{x} = x + C A_g^{-1} C^T Π_g w to <w*,w*> + <w,w> - 2<w*,w>; this step requires E[\hat{x}\hat{x}^T] = I and E[\hat{x}] = 0, which are not stated or implied by the model. That is an omitted algebraic step and a correctness risk for the accuracy-row bounds, but not a circular reduction, so it does not increase the circularity score.

Axiom & Free-Parameter Ledger

5 free parameters · 9 axioms · 2 invented entities

The theoretical bounds are parametric in the model inputs C, A_g, Pi_g, w*, beta, and Q, and are not fitted to data. The experimental section, however, introduces several hand-picked parameters: sampled causal edge weights, projection rank k=5, chosen cost matrices, chosen desirable features, and a fitted logistic-regression w*. These do not compromise the theory but are essential to reproducing the empirical tradeoff curves.

free parameters (5)

Causal graph edge weights = Not reported; sampled non-negative respecting the DAG
Appendix A.4.1. The contribution matrix C and therefore x_e, Delta(w), and every bound depend on these weights; no values or seeds are given.
Projection rank k for group subspaces = k = 5
Appendix A.4.1. The projectors Pi_1 and Pi_2 are built from the top-k right singular vectors; this hand-chosen rank changes the fairness constraint and all optimality-loss bounds.
Cost matrices A_1, A_2 = Main experiments: A_1 = I, A_2 = 2A_1
Appendix A.4.1. The cost disparity is a modeling choice, not estimated from data; it directly controls the SW objective and the fairness constraint.
Desirability matrix Pi_D = 1 on education, workclass, occupation; 0 elsewhere
Appendix A.4.1. Selected by the authors as “realistic to improve”; this choice determines which feature changes count as desirable and therefore shapes Delta(w).
Ground-truth rule w* = Logistic-regression coefficients on ADULT, projected to the unit ball
Appendix A.4.1. All accuracy-loss and social-welfare values are measured relative to this fitted w*; the fitted coefficients are not reported.

axioms (9)

standard math Contribution matrix C of a DAG is invertible (Lemma A.1)
Used to solve for the agent effort x_e and in kernel conditions for Examples 3.1/3.2.
standard math Hoffman bound on distance to a polyhedron (Hoffman 1952)
Used in Proposition A.3 to bound accuracy loss for polyhedral fair spaces.
standard math KKT conditions are necessary and sufficient for the convex optimization problems used (Slater’s condition)
Used in Lemma A.4 and Propositions A.2/A.4 to derive closed-form optima for ellipsoidal constraints.
domain assumption Agents’ peer-learning estimate is exactly w_est = Pi_g w (Lemma 3.1 of [7])
Proposition 2.1 imports this result to obtain the closed-form best response and all subsequent Delta(w) expressions.
domain assumption Agents know the causal graph C and their cost matrix A_g, and best-respond with quadratic costs
Section 2.3 and Proposition 2.1; the paper states this assumption is relaxed only in future work (Section 6).
domain assumption Principal knows w* (or can follow [7] up to a small unspecified error term)
Section 2.4 explicitly assumes known w* to simplify exposition; the unknown-w* extension is cited but not derived in this paper.
domain assumption Exactly two agent groups with linear subspaces and deployable policies restricted to the unit Euclidean ball B(1)
Section 2.2 and Eq. (3)-(4); all bounds are for this two-group, bounded-linear-policy setting.
ad hoc to paper Nonconvex fair spaces satisfy Definition 4.1: Delta(w) = w^T Q w - f(w) with f nonnegative, L-Lipschitz, and beta <= lambda_d(Q)
Section 4 introduces this class F specifically to make the convex-restriction bounds tractable; it is a modeling assumption, not a derived fact.
ad hoc to paper Assumptions A.1 and A.2: ker(Pi_1) ∩ ker(Pi_2) = ∅ and Pi_1 w ≠ Pi_2 w for all w ≠ 0
Required in Appendices A.2.2 and A.2.3 for Examples 3.1 and 3.2 to produce polyhedral/ellipsoidal fair spaces with non-empty kernel conditions.

invented entities (2)

Desirability score matrix Pi_D and feature-wise desirability scores des(i) no independent evidence
purpose: Encodes the external stakeholder’s preferences over which feature changes are desirable; enters Delta(w) as Pi_D x_e^(g)(w).
A modeling construct chosen by the stakeholder/designer; there is no empirical measurement procedure proposed for these scores.
Desirability discrepancy functions Delta(w) no independent evidence
purpose: Measures group disparity in desirable effort incentivized by a policy w; the principal’s fairness constraint is Delta(w) ≤ beta.
The paper treats Delta as stakeholder-supplied and studies broad classes of it; no ground-truth Delta is derived from data.

pith-pipeline@v1.3.0-alltime-deepseek · 33573 in / 13480 out tokens · 116908 ms · 2026-08-04T08:43:59.222275+00:00 · methodology

0 comments

read the original abstract

Strategic classification examines how decision rules interact with agents who strategically adapt their features. Most existing models focus on maximizing predictive performance, assuming agents best respond to the learned classifier. However, real decision-making systems are rarely optimized solely for accuracy: ethical, economic, and institutional considerations often make some feature changes more desirable than others. At the same time, principals may wish to incentivize these changes fairly across heterogeneous agents. While prior work has studied causal structure between features, notions of desirability, and information disparities in isolation, this work initiates a unified treatment of these components within a single framework. We frame the problem as a constrained optimization problem that captures the trade-offs between optimality, desirability, and fairness. We provide theoretical guarantees on the principal's optimality loss constrained to a particular desirability fairness tolerance for multiple broad classes of fairness measures. Finally, through experiments on real datasets, we show the explicit tradeoff between maximizing accuracy and fairness in desirability effort.

Figures

Figures reproduced from arXiv: 2510.19098 by Chara Podimata, Ekaterina Fedorova, Valia Efthymiou.

**Figure 1.** Figure 1: Examples of β-fair spaces in 2 dimensions that satisfy Properties 3.1 (feasible region polyhedral), 3.2 (β-fair space ellipsoidal), and/or 3.3 (feasible region ellipsoidal) Example 3.2 (Sum of squared differences). ∆(w) := P i∈[d] (ΠDx (1) e (w) − ΠDx (2) e (w))i) 2 In Example 3.1, the feasible region for the fairness constrained problem forms a polyhedron (i.e., Prop. 3.1). Likewise, in Example 3.2, the s… view at source ↗

**Figure 2.** Figure 2: A nonconvex β-fair space. ∆(w) := w⊤w − (.3 p |w1| + .3 p |w2|) and β = .3 4.1 β-fair SE Optimality Loss We can restrict any W(β; ∆) ∈ F to its core ellipsoid, E(β) = {w ∈ R d : w⊤Qw ≤ β}, inside the feasible region of the principal’s fairness constrained problem (Appendix A.3.1). Then using [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** Figure 3: Optimal value in various β-fair equilibria for ℓ1 fairness constraints. The desirable features are occupation, workclass, and education. into well and less educated groups, is consistently the most constrained, its curve starts at the lower point and improves most slowly. In this case, the desirable attributes (education, workclass, occupation) are very aligned with this group disparity, so the discrepancy… view at source ↗

**Figure 4.** Figure 4: Optimal values for varying β for different group splits under ℓ2-fairness constraint Interestingly, when we allow the cost matrices to be more complex than the unit (e.g random) then information disparities become more irrevelant. However, that’s not suprising considering the fact that the fairness-desirability function values equally the desirability matrix and the projection matrices of the groups. 43 [… view at source ↗

**Figure 5.** Figure 5: Optimal values for varying β for different group splits under non-uniform random cost matrices A1 = 2A2 and the ℓ1-fairness constraint 44 [PITH_FULL_IMAGE:figures/full_fig_p044_5.png] view at source ↗

discussion (0)

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Linear Strategic Classification with Endogenous Improvements
cs.LG 2026-05 unverdicted novelty 7.0

Formalizes improvement-aware strategic classification for linear classifiers under single-index models, proves the strategic-optimal classifier is a parallel shift of the Bayes boundary, and supplies PAC guarantees wi...
Linear Strategic Classification with Endogenous Improvements
cs.LG 2026-05 reject novelty 5.0

In a linear strategic-classification model where manipulation can genuinely improve outcomes, the optimal strategic classifier is a parallel shift of the Bayes boundary, and it is a provably better proxy for the impro...

Reference graph

Works this paper leans on

60 extracted references · 2 canonical work pages · cited by 1 Pith paper

[1]

The strategic perceptron

Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. InProceedings of the 22nd ACM Conference on Economics and Computation, EC ’21, page 6–25, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450385541. doi: 10.1145/3465456.3467629. URLhttps://doi.org/10.1145/3465456.3467629

arXiv 2021
[2]

Fundamental bounds on online strategic clas- sification

Saba Ahmadi, Avrim Blum, and Kunhe Yang. Fundamental bounds on online strategic clas- sification. InProceedings of the 24th ACM Conference on Economics and Computation, EC ’23, page 22–58, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701047. doi: 10.1145/3580507.3597818. URLhttps://doi.org/10.1145/3580507. 3597818

arXiv 2023
[3]

Could anticipating gaming incentivize improvement in (fair) strategic classification? In2024 IEEE 63rd Conference on Decision and Control (CDC), pages 6028–6035, 2024

Sura Alhanouti and Parinaz Naghizadeh. Could anticipating gaming incentivize improvement in (fair) strategic classification? In2024 IEEE 63rd Conference on Decision and Control (CDC), pages 6028–6035, 2024. doi: 10.1109/CDC56724.2024.10886604

arXiv 2024
[4]

Multiagent Evaluation Mechanisms.Proceedings of the AAAI Conference on Ar- 14 tificial Intelligence, 34(02):1774–1781, April 2020

Tal Alon, Magdalen Dobson, Ariel Procaccia, Inbal Talgam-Cohen, and Jamie Tucker- Foltz. Multiagent Evaluation Mechanisms.Proceedings of the AAAI Conference on Ar- 14 tificial Intelligence, 34(02):1774–1781, April 2020. doi: 10.1609/aaai.v34i02.5543. URL https://ojs.aaai.org/index.php/AAAI/article/view/5543

doi:10.1609/aaai.v34i02.5543 2020
[5]

The disparate effects of partial information in bayesian strategic learning, 2025

Srikanth Avasarala, Serena Wang, and Juba Ziani. The disparate effects of partial information in bayesian strategic learning, 2025. URLhttps://arxiv.org/abs/2506.00627

Pith/arXiv arXiv 2025
[6]

Gaming helps! learning from strategic interactions in natural dynamics

Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani. Gaming helps! learning from strategic interactions in natural dynamics. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, vol- ume 130 ofProceedings of Machine Learning Research, pages 1234–1242. PMLR, 13–15 Apr
[7]

Information discrepancy in strategic learning

Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani. Information discrepancy in strategic learning. 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 ofProceedings of Machine Learning Research, pages 1691–1715. PMLR,...

2022
[8]

The Role of Randomness and Noise in Strategic Clas- sification

Mark Braverman and Sumegha Garg. The Role of Randomness and Noise in Strategic Clas- sification. In Aaron Roth, editor,1st Symposium on Foundations of Responsible Computing (FORC 2020), volume 156 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:20, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. ISBN ...

work page doi:10.4230/lipics.forc.2020.9 2020
[9]

Who’s gaming the system? a causally-motivated approach for detecting strategic adaptation.Advances in Neural Information Processing Systems, 37:42311–42348, 2024

Trenton Chang, Lindsay Warrenburg, Sae-Hwan Park, Ravi Parikh, Maggie Makar, and Jenna Wiens. Who’s gaming the system? a causally-motivated approach for detecting strategic adaptation.Advances in Neural Information Processing Systems, 37:42311–42348, 2024

2024
[10]

Learning strategy-aware linear classifiers.Ad- vances in Neural Information Processing Systems, 33:15265–15276, 2020

Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers.Ad- vances in Neural Information Processing Systems, 33:15265–15276, 2020

2020
[11]

Silvia Chiappa and Thomas P. S. Gillam. Path-specific counterfactual fairness, 2018. URL https://arxiv.org/abs/1802.08139

Pith/arXiv arXiv 2018
[12]

Bayesian strategic classification

Lee Cohen, Saeed Sharifi-Malvajerdi, Kevin Stangl, Ali Vakilian, and Juba Ziani. Bayesian strategic classification. InProceedings of the 38th International Conference on Neural Informa- tion Processing Systems, NIPS ’24, Red Hook, NY, USA, 2025. Curran Associates Inc. ISBN 9798331314385

2025
[13]

Minimax group fairness in strate- gic classification

Emily Diana, Saeed Sharifi-Malvajerdi, and Ali Vakilian. Minimax group fairness in strate- gic classification. In2025 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 753–772, 2025. doi: 10.1109/SaTML64287.2025.00047

arXiv 2025
[14]

Strate- gic classification from revealed preferences

Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strate- gic classification from revealed preferences. InProceedings of the 2018 ACM Conference on Economics and Computation, pages 55–70, 2018

2018
[15]

The double-edged sword of behavioral responses in strategic classification: Theory and user studies

Raman Ebrahimi, Kristen Vaccaro, and Parinaz Naghizadeh. The double-edged sword of behavioral responses in strategic classification: Theory and user studies. InProceedings of the 2025 ACM Conference on Fairness, Accountability, and Transparency, F AccT ’25, 15 page 868–886, New York, NY, USA, 2025. Association for Computing Machinery. ISBN 9798400714825. ...

arXiv 2025
[16]

Incentivizing desirable effort profiles in strategic classification: The role of causality and uncertainty, 2025

Valia Efthymiou, Chara Podimata, Diptangshu Sen, and Juba Ziani. Incentivizing desirable effort profiles in strategic classification: The role of causality and uncertainty, 2025. URL https://arxiv.org/abs/2502.06749

Pith/arXiv arXiv 2025
[18]

Group-fair classification with strategic agents

Andrew Estornell, Sanmay Das, Yang Liu, and Yevgeniy Vorobeychik. Group-fair classification with strategic agents. InProceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, F AccT ’23, page 389–399, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701924. doi: 10.1145/3593013.3594006. URLhttps: //doi....

arXiv 2023
[19]

User altruism in recommendation systems.arXiv preprint arXiv:2506.04525, 2025

Ekaterina Fedorova, Madeline Kitch, and Chara Podimata. User altruism in recommendation systems.arXiv preprint arXiv:2506.04525, 2025

arXiv 2025
[20]

Strategic classification in the dark

Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen, and Nir Rosenfeld. Strategic classification in the dark. In Marina Meila and Tong Zhang, editors,Proceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 3672–3681. PMLR, 18–24 Jul 2021. URLhttps://proceedings.mlr.press/ v1...

2021
[21]

Equal- izing recourse across groups, 2019

Vivek Gupta, Pegah Nokhiz, Chitradeep Dutta Roy, and Suresh Venkatasubramanian. Equal- izing recourse across groups, 2019. URLhttps://arxiv.org/abs/1909.03166

Pith/arXiv arXiv 2019
[22]

Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z. Wang. Maximizing welfare with incentive-aware evaluation mechanisms. InProceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI’20, 2021. ISBN 9780999241165

2021
[23]

Papadimitriou, and Mary Wootters

Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, and Mary Wootters. Strategic classification.CoRR, abs/1506.06980, 2015. URLhttp://arxiv.org/abs/1506.06980

Pith/arXiv arXiv 2015
[24]

Stateful strategic regression

Keegan Harris, Hoda Heidari, and Zhiwei Steven Wu. Stateful strategic regression. InPro- ceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393

2021
[25]

Recommending to strategic users.arXiv preprint arXiv:2302.06559, 2023

Andreas Haupt, Dylan Hadfield-Menell, and Chara Podimata. Recommending to strategic users.arXiv preprint arXiv:2302.06559, 2023

Pith/arXiv arXiv 2023
[26]

Alan J. Hoffman. On approximate solutions of systems of linear inequalities.Journal of Research of the National Bureau of Standards, 49(4):263–265, 1952

1952
[27]

Causal strategic classification: a tale of two shifts

Guy Horowitz and Nir Rosenfeld. Causal strategic classification: a tale of two shifts. In 16 Proceedings of the 40th International Conference on Machine Learning, ICML’23. JMLR.org, 2023

2023
[29]

Algorithmic recourse: from counterfactual explanations to interventions

Amir-Hossein Karimi, Bernhard Sch¨ olkopf, and Isabel Valera. Algorithmic recourse: from counterfactual explanations to interventions. InProceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, F AccT ’21, page 353–362, New York, NY, USA,

2021
[30]

A survey of algorithmic recourse: Contrastive explanations and consequential recommendations.ACM Comput

Amir-Hossein Karimi, Gilles Barthe, Bernhard Sch¨ olkopf, and Isabel Valera. A survey of algorithmic recourse: Contrastive explanations and consequential recommendations.ACM Comput. Surv., 55(5), December 2022. ISSN 0360-0300. doi: 10.1145/3527848. URLhttps: //doi.org/10.1145/3527848

doi:10.1145/3527848 2022
[31]

ISBN 9781450383097

Association for Computing Machinery. ISBN 9781450383097. doi: 10.1145/3442188. 3445899. URLhttps://doi.org/10.1145/3442188.3445899

arXiv
[32]

Strategic classification is causal modeling in disguise

John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. InProceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020

2020
[33]

Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strate- gically? InProceedings of the 2019 ACM Conference on Economics and Computation, EC ’19, page 825–844, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367929. doi: 10.1145/3328526.3329584. URLhttps://doi.org/10.1145/3328526. 3329584

arXiv 2019
[34]

Fair inference on outcomes

Razieh Nabi and Ilya Shpitser. Fair inference on outcomes. InProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’18/IAAI’18/EAAI’18. AAAI Press, 2018. ISBN 978-1-57735-800-8

2018
[35]

Dragan, and Moritz Hardt

Smitha Milli, John Miller, Anca D. Dragan, and Moritz Hardt. The social cost of strategic classification. InProceedings of the Conference on Fairness, Accountability, and Transparency, F AT* ’19, page 230–239, New York, NY, USA, 2019. Association for Computing Machin- ery. ISBN 9781450361255. doi: 10.1145/3287560.3287576. URLhttps://doi.org/10.1145/ 32875...

arXiv 2019
[36]

Vera, and Luis F

Javier Pe˜ na, Juan C. Vera, and Luis F. Zuluaga. New characterizations of Hoffman con- stants for systems of linear constraints.Mathematical Programming, 187(1):79–109, May 17
[37]

Discrimination in- duced by algorithmic recourse objectives

Nicholas Perello, Cyrus Cousins, Yair Zick, and Przemyslaw Grabowicz. Discrimination in- duced by algorithmic recourse objectives. InProceedings of the 2025 ACM Conference on Fairness, Accountability, and Transparency, F AccT ’25, page 1653–1663, New York, NY, USA,

2025
[38]

One-shot strategic classification under unknown costs

Elan Rosenfeld and Nir Rosenfeld. One-shot strategic classification under unknown costs. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org, 2024

2024
[39]

Edelman, and Brian Axelrod

Yonadav Shavit, Benjamin L. Edelman, and Brian Axelrod. Causal strategic linear regres- sion. InProceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020

2020
[40]

doi: 10.1007/s10107-020-01473-6

ISSN 1436-4646. doi: 10.1007/s10107-020-01473-6. URLhttps://doi.org/10.1007/ s10107-020-01473-6

work page doi:10.1007/s10107-020-01473-6
[41]

Incentive-aware machine learning; robustness, fairness, improvement & causality.arXiv preprint arXiv:2505.05211, 2025

Chara Podimata. Incentive-aware machine learning; robustness, fairness, improvement & causality.arXiv preprint arXiv:2505.05211, 2025

Pith/arXiv arXiv 2025
[44]

Strategic classification with non-linear classifiers,

Benyamin Trachtenberg and Nir Rosenfeld. Strategic classification with non-linear classifiers,
[45]

URLhttps://arxiv.org/abs/2505.23443

arXiv
[46]

Decisions, counterfactual explanations and strategic behavior

Stratis Tsirtsis and Manuel Gomez-Rodriguez. Decisions, counterfactual explanations and strategic behavior. InProceedings of the 34th International Conference on Neural Information Processing Systems, NIPS ’20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546

2020
[49]

IfW(β)⊃ B(1) then the constrained optimum coincides with the unconstrained (it lies in the L2-ball), and the angle is zero
[50]

in particular :w ⋆ c = Q−1c c⊤Qc

IfW(β)⊂ B(1) then in the constrained optimization problem the ball constraint is not active and therefore by KKT we infer that the optimimum lies in the direction ofQ −1cand from Lemma A.4 we have the closed form solutions. in particular :w ⋆ c = Q−1c c⊤Qc . Now observe that cos(w⋆ u,w ⋆ c ) = cos(c, A−1c) = c⊤A−1c ∥c∥∥A−1c∥ >0 since we know thatA≻0 (by d...
[51]

Clearly, ifλ 1, λ2 >0* ,A=λ 1I+λ 2Qmust be invertible as the sum of two PD matrices is a PD matrix

If neither of the above is happening, then the KKT conditions tell us that 2λ1w⋆ c +2λ2Qw⋆ c =c whereλ 1, λ2 ≥0 are the Langrange multipliers. Clearly, ifλ 1, λ2 >0* ,A=λ 1I+λ 2Qmust be invertible as the sum of two PD matrices is a PD matrix. Hencew ⋆ c = 1 2 A−1cdoes not follow the direction of eithercorQ −1cbut a linear combination of those. In any case...
[52]

So it must be the case that for comple- mentary slackness,w ⊤Qw=β

w ∥w∥ = 2µQw 2.µ≥0 3.µ(w ⊤Qw−β) = 0 4.w ⊤Qw≤β First, notice thatµ >0, because otherwise,wmust be 0. So it must be the case that for comple- mentary slackness,w ⊤Qw=β. Then, from the first condition we have:Qw= w 2µ∥w∥ =λwwhere λ= 1 2µ∥w∥ . Thus we haveβ=w ⊤λw=λ∥w∥ 2 which means that∥w∥ 2 = q β λ . But now notice thatλis, by definition, an eigenvalue of of...
[53]

Π 1w̸= Π 2w∀w,w̸=0 then ker(ΠDA−1 g C⊤[Π1 −Π 2]) will be empty. Corollary A.3(Sufficient conditions for Example 3.1 to satisfy property 3.1 w/ no info asymme- try).Suppose that agents in our setting have the same information (i.e.Π 1 = Π 2 = Π g). Then, the fairness function described by Example 3.1 satisfies Property 3.1 ifker(Π g) =∅,A 2 ≻A 1 and β≤σ d(...
[54]

Π 1w̸= Π 2w∀w,w̸=0 then ker(ΠDA−1 g C⊤[Π1 −Π 2]) will be empty. 31 Corollary A.5(Sufficient conditions for Example 3.2 to satisfy property 3.2 w/ no info asymme- try).Suppose that agents in our setting have the same information (i.e.Π 1 = Π 2 = Π g). Then, the fairness function described by Example 3.2 satisfies Property 3.2 ifker(Π g) =∅,A 2 ≻A 1. Proof....
[55]

This will give us optimality loss bounds for theβ-fair SE as compared to the unconstrained SE

Construct an ellipsoidalrestriction,E(β), such thatE(β)⊆ B(1)∩ W(β; ∆). This will give us optimality loss bounds for theβ-fair SE as compared to the unconstrained SE
[56]

diameter

Construct an ellipsoidalenvelope,E( ˜β), such thatW(β; ∆)⊆ E( ˜β). This will give us opti- mality loss bounds for the convex restrictedβ-fair problem as compared to the nonconvex β-fair SE. A.3.1 Supplemental material for Section 4.1 First let’s construct the ellipsoidal restriction. We’ll use a nice lemma about when ellipsoids are inside the unit euclide...
[57]

Ifp= 0 we are done; otherwise divide by∥p∥ 2 to obtain∥p∥ 2 ≤ ∥w⋆∥2

By Cauchy–Schwarz, ∥p∥2 2 ≤ ⟨w⋆, p⟩ ≤ ∥w⋆∥2 ∥p∥2. Ifp= 0 we are done; otherwise divide by∥p∥ 2 to obtain∥p∥ 2 ≤ ∥w⋆∥2. Hence∥P S(w⋆)∥2 ≤ ∥w⋆∥2. Proposition A.11(Accuracy and social welfare loss from ellipsoidal restriction).IfW(β; ∆)∈ F. Then we have the following upper bounds on optimality loss between the nonconvex fairness constrained problem (Equation...
[58]

Ground-truth policy is not already in the restricted ellipsoid (i.e.,w ⋆ /∈ E(β))
[59]

Envelope ellipsoid is strictly inside the unit ball (i.e.,LD < λ d(Q)−β, see Lemma A.7)
[60]

Proof.We will just compare the bounds promised between the two propositions under conditions

Ground truth policy is strictly outside the ball envelope of the envelope ellipsoid (i.e.,∥w ⋆∥>q β+LD λd(Q) , see Lemma A.5) The principal gets a (strictly) tighter bound on restriction optimality loss using Proposition A.11 rather than Proposition A.9. Proof.We will just compare the bounds promised between the two propositions under conditions. CONDITIO...
[61]

We use uniform costsA 1 =A2 withA 1 =I
[62]

We use non-uniform costs withA 2 = 2A1 andA 1 =I
[63]

Their use is denoted in figure captions

We use non-uniformA 2 = 2A1 random cost matrices (A 1 is sampled at random). Their use is denoted in figure captions. Desirability .We chooseeducation,occupation, andworkclassasdesirable, since these attributes are realistic to improve and likely to have downstream, external effects outside of income. Thus, to external entities (e.g. government bodies) th...
[2020]

cancels itself out

URLhttps://arxiv.org/abs/2010.06529. 18 A Supplemental Material A.1 Supplemental material for Section 2 Table 2: Notation Table Symbol Meaning d dimension of features C Contribution matrix Ag groupgcost matrix Πg groupgprojection matrix ΠD diagonal desirability score matrix des(i) featureidesirability score g group Dg groupgdistribution of features Sg gro...

Pith/arXiv arXiv 2010
[2021]

URLhttps://proceedings.mlr.press/v130/bechavod21a.html
[2025]

ISBN 9798400714825

Association for Computing Machinery. ISBN 9798400714825. doi: 10.1145/3715275. 3732110. URLhttps://doi.org/10.1145/3715275.3732110

arXiv

[1] [1]

The strategic perceptron

Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. InProceedings of the 22nd ACM Conference on Economics and Computation, EC ’21, page 6–25, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450385541. doi: 10.1145/3465456.3467629. URLhttps://doi.org/10.1145/3465456.3467629

arXiv 2021

[2] [2]

Fundamental bounds on online strategic clas- sification

Saba Ahmadi, Avrim Blum, and Kunhe Yang. Fundamental bounds on online strategic clas- sification. InProceedings of the 24th ACM Conference on Economics and Computation, EC ’23, page 22–58, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701047. doi: 10.1145/3580507.3597818. URLhttps://doi.org/10.1145/3580507. 3597818

arXiv 2023

[3] [3]

Could anticipating gaming incentivize improvement in (fair) strategic classification? In2024 IEEE 63rd Conference on Decision and Control (CDC), pages 6028–6035, 2024

Sura Alhanouti and Parinaz Naghizadeh. Could anticipating gaming incentivize improvement in (fair) strategic classification? In2024 IEEE 63rd Conference on Decision and Control (CDC), pages 6028–6035, 2024. doi: 10.1109/CDC56724.2024.10886604

arXiv 2024

[4] [4]

Multiagent Evaluation Mechanisms.Proceedings of the AAAI Conference on Ar- 14 tificial Intelligence, 34(02):1774–1781, April 2020

Tal Alon, Magdalen Dobson, Ariel Procaccia, Inbal Talgam-Cohen, and Jamie Tucker- Foltz. Multiagent Evaluation Mechanisms.Proceedings of the AAAI Conference on Ar- 14 tificial Intelligence, 34(02):1774–1781, April 2020. doi: 10.1609/aaai.v34i02.5543. URL https://ojs.aaai.org/index.php/AAAI/article/view/5543

doi:10.1609/aaai.v34i02.5543 2020

[5] [5]

The disparate effects of partial information in bayesian strategic learning, 2025

Srikanth Avasarala, Serena Wang, and Juba Ziani. The disparate effects of partial information in bayesian strategic learning, 2025. URLhttps://arxiv.org/abs/2506.00627

Pith/arXiv arXiv 2025

[6] [6]

Gaming helps! learning from strategic interactions in natural dynamics

Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani. Gaming helps! learning from strategic interactions in natural dynamics. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, vol- ume 130 ofProceedings of Machine Learning Research, pages 1234–1242. PMLR, 13–15 Apr

[7] [7]

Information discrepancy in strategic learning

Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani. Information discrepancy in strategic learning. 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 ofProceedings of Machine Learning Research, pages 1691–1715. PMLR,...

2022

[8] [8]

The Role of Randomness and Noise in Strategic Clas- sification

Mark Braverman and Sumegha Garg. The Role of Randomness and Noise in Strategic Clas- sification. In Aaron Roth, editor,1st Symposium on Foundations of Responsible Computing (FORC 2020), volume 156 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:20, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. ISBN ...

work page doi:10.4230/lipics.forc.2020.9 2020

[9] [9]

Who’s gaming the system? a causally-motivated approach for detecting strategic adaptation.Advances in Neural Information Processing Systems, 37:42311–42348, 2024

Trenton Chang, Lindsay Warrenburg, Sae-Hwan Park, Ravi Parikh, Maggie Makar, and Jenna Wiens. Who’s gaming the system? a causally-motivated approach for detecting strategic adaptation.Advances in Neural Information Processing Systems, 37:42311–42348, 2024

2024

[10] [10]

Learning strategy-aware linear classifiers.Ad- vances in Neural Information Processing Systems, 33:15265–15276, 2020

Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers.Ad- vances in Neural Information Processing Systems, 33:15265–15276, 2020

2020

[11] [11]

Silvia Chiappa and Thomas P. S. Gillam. Path-specific counterfactual fairness, 2018. URL https://arxiv.org/abs/1802.08139

Pith/arXiv arXiv 2018

[12] [12]

Bayesian strategic classification

Lee Cohen, Saeed Sharifi-Malvajerdi, Kevin Stangl, Ali Vakilian, and Juba Ziani. Bayesian strategic classification. InProceedings of the 38th International Conference on Neural Informa- tion Processing Systems, NIPS ’24, Red Hook, NY, USA, 2025. Curran Associates Inc. ISBN 9798331314385

2025

[13] [13]

Minimax group fairness in strate- gic classification

Emily Diana, Saeed Sharifi-Malvajerdi, and Ali Vakilian. Minimax group fairness in strate- gic classification. In2025 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 753–772, 2025. doi: 10.1109/SaTML64287.2025.00047

arXiv 2025

[14] [14]

Strate- gic classification from revealed preferences

Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strate- gic classification from revealed preferences. InProceedings of the 2018 ACM Conference on Economics and Computation, pages 55–70, 2018

2018

[15] [15]

The double-edged sword of behavioral responses in strategic classification: Theory and user studies

Raman Ebrahimi, Kristen Vaccaro, and Parinaz Naghizadeh. The double-edged sword of behavioral responses in strategic classification: Theory and user studies. InProceedings of the 2025 ACM Conference on Fairness, Accountability, and Transparency, F AccT ’25, 15 page 868–886, New York, NY, USA, 2025. Association for Computing Machinery. ISBN 9798400714825. ...

arXiv 2025

[16] [16]

Incentivizing desirable effort profiles in strategic classification: The role of causality and uncertainty, 2025

Valia Efthymiou, Chara Podimata, Diptangshu Sen, and Juba Ziani. Incentivizing desirable effort profiles in strategic classification: The role of causality and uncertainty, 2025. URL https://arxiv.org/abs/2502.06749

Pith/arXiv arXiv 2025

[17] [18]

Group-fair classification with strategic agents

Andrew Estornell, Sanmay Das, Yang Liu, and Yevgeniy Vorobeychik. Group-fair classification with strategic agents. InProceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, F AccT ’23, page 389–399, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701924. doi: 10.1145/3593013.3594006. URLhttps: //doi....

arXiv 2023

[18] [19]

User altruism in recommendation systems.arXiv preprint arXiv:2506.04525, 2025

Ekaterina Fedorova, Madeline Kitch, and Chara Podimata. User altruism in recommendation systems.arXiv preprint arXiv:2506.04525, 2025

arXiv 2025

[19] [20]

Strategic classification in the dark

Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen, and Nir Rosenfeld. Strategic classification in the dark. In Marina Meila and Tong Zhang, editors,Proceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 3672–3681. PMLR, 18–24 Jul 2021. URLhttps://proceedings.mlr.press/ v1...

2021

[20] [21]

Equal- izing recourse across groups, 2019

Vivek Gupta, Pegah Nokhiz, Chitradeep Dutta Roy, and Suresh Venkatasubramanian. Equal- izing recourse across groups, 2019. URLhttps://arxiv.org/abs/1909.03166

Pith/arXiv arXiv 2019

[21] [22]

Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z. Wang. Maximizing welfare with incentive-aware evaluation mechanisms. InProceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI’20, 2021. ISBN 9780999241165

2021

[22] [23]

Papadimitriou, and Mary Wootters

Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, and Mary Wootters. Strategic classification.CoRR, abs/1506.06980, 2015. URLhttp://arxiv.org/abs/1506.06980

Pith/arXiv arXiv 2015

[23] [24]

Stateful strategic regression

Keegan Harris, Hoda Heidari, and Zhiwei Steven Wu. Stateful strategic regression. InPro- ceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393

2021

[24] [25]

Recommending to strategic users.arXiv preprint arXiv:2302.06559, 2023

Andreas Haupt, Dylan Hadfield-Menell, and Chara Podimata. Recommending to strategic users.arXiv preprint arXiv:2302.06559, 2023

Pith/arXiv arXiv 2023

[25] [26]

Alan J. Hoffman. On approximate solutions of systems of linear inequalities.Journal of Research of the National Bureau of Standards, 49(4):263–265, 1952

1952

[26] [27]

Causal strategic classification: a tale of two shifts

Guy Horowitz and Nir Rosenfeld. Causal strategic classification: a tale of two shifts. In 16 Proceedings of the 40th International Conference on Machine Learning, ICML’23. JMLR.org, 2023

2023

[27] [29]

Algorithmic recourse: from counterfactual explanations to interventions

Amir-Hossein Karimi, Bernhard Sch¨ olkopf, and Isabel Valera. Algorithmic recourse: from counterfactual explanations to interventions. InProceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, F AccT ’21, page 353–362, New York, NY, USA,

2021

[28] [30]

A survey of algorithmic recourse: Contrastive explanations and consequential recommendations.ACM Comput

Amir-Hossein Karimi, Gilles Barthe, Bernhard Sch¨ olkopf, and Isabel Valera. A survey of algorithmic recourse: Contrastive explanations and consequential recommendations.ACM Comput. Surv., 55(5), December 2022. ISSN 0360-0300. doi: 10.1145/3527848. URLhttps: //doi.org/10.1145/3527848

doi:10.1145/3527848 2022

[29] [31]

ISBN 9781450383097

Association for Computing Machinery. ISBN 9781450383097. doi: 10.1145/3442188. 3445899. URLhttps://doi.org/10.1145/3442188.3445899

arXiv

[30] [32]

Strategic classification is causal modeling in disguise

John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. InProceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020

2020

[31] [33]

Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strate- gically? InProceedings of the 2019 ACM Conference on Economics and Computation, EC ’19, page 825–844, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367929. doi: 10.1145/3328526.3329584. URLhttps://doi.org/10.1145/3328526. 3329584

arXiv 2019

[32] [34]

Fair inference on outcomes

Razieh Nabi and Ilya Shpitser. Fair inference on outcomes. InProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’18/IAAI’18/EAAI’18. AAAI Press, 2018. ISBN 978-1-57735-800-8

2018

[33] [35]

Dragan, and Moritz Hardt

Smitha Milli, John Miller, Anca D. Dragan, and Moritz Hardt. The social cost of strategic classification. InProceedings of the Conference on Fairness, Accountability, and Transparency, F AT* ’19, page 230–239, New York, NY, USA, 2019. Association for Computing Machin- ery. ISBN 9781450361255. doi: 10.1145/3287560.3287576. URLhttps://doi.org/10.1145/ 32875...

arXiv 2019

[34] [36]

Vera, and Luis F

Javier Pe˜ na, Juan C. Vera, and Luis F. Zuluaga. New characterizations of Hoffman con- stants for systems of linear constraints.Mathematical Programming, 187(1):79–109, May 17

[35] [37]

Discrimination in- duced by algorithmic recourse objectives

Nicholas Perello, Cyrus Cousins, Yair Zick, and Przemyslaw Grabowicz. Discrimination in- duced by algorithmic recourse objectives. InProceedings of the 2025 ACM Conference on Fairness, Accountability, and Transparency, F AccT ’25, page 1653–1663, New York, NY, USA,

2025

[36] [38]

One-shot strategic classification under unknown costs

Elan Rosenfeld and Nir Rosenfeld. One-shot strategic classification under unknown costs. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org, 2024

2024

[37] [39]

Edelman, and Brian Axelrod

Yonadav Shavit, Benjamin L. Edelman, and Brian Axelrod. Causal strategic linear regres- sion. InProceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020

2020

[38] [40]

doi: 10.1007/s10107-020-01473-6

ISSN 1436-4646. doi: 10.1007/s10107-020-01473-6. URLhttps://doi.org/10.1007/ s10107-020-01473-6

work page doi:10.1007/s10107-020-01473-6

[39] [41]

Incentive-aware machine learning; robustness, fairness, improvement & causality.arXiv preprint arXiv:2505.05211, 2025

Chara Podimata. Incentive-aware machine learning; robustness, fairness, improvement & causality.arXiv preprint arXiv:2505.05211, 2025

Pith/arXiv arXiv 2025

[40] [44]

Strategic classification with non-linear classifiers,

Benyamin Trachtenberg and Nir Rosenfeld. Strategic classification with non-linear classifiers,

[41] [45]

URLhttps://arxiv.org/abs/2505.23443

arXiv

[42] [46]

Decisions, counterfactual explanations and strategic behavior

Stratis Tsirtsis and Manuel Gomez-Rodriguez. Decisions, counterfactual explanations and strategic behavior. InProceedings of the 34th International Conference on Neural Information Processing Systems, NIPS ’20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546

2020

[43] [49]

IfW(β)⊃ B(1) then the constrained optimum coincides with the unconstrained (it lies in the L2-ball), and the angle is zero

[44] [50]

in particular :w ⋆ c = Q−1c c⊤Qc

IfW(β)⊂ B(1) then in the constrained optimization problem the ball constraint is not active and therefore by KKT we infer that the optimimum lies in the direction ofQ −1cand from Lemma A.4 we have the closed form solutions. in particular :w ⋆ c = Q−1c c⊤Qc . Now observe that cos(w⋆ u,w ⋆ c ) = cos(c, A−1c) = c⊤A−1c ∥c∥∥A−1c∥ >0 since we know thatA≻0 (by d...

[45] [51]

Clearly, ifλ 1, λ2 >0* ,A=λ 1I+λ 2Qmust be invertible as the sum of two PD matrices is a PD matrix

If neither of the above is happening, then the KKT conditions tell us that 2λ1w⋆ c +2λ2Qw⋆ c =c whereλ 1, λ2 ≥0 are the Langrange multipliers. Clearly, ifλ 1, λ2 >0* ,A=λ 1I+λ 2Qmust be invertible as the sum of two PD matrices is a PD matrix. Hencew ⋆ c = 1 2 A−1cdoes not follow the direction of eithercorQ −1cbut a linear combination of those. In any case...

[46] [52]

So it must be the case that for comple- mentary slackness,w ⊤Qw=β

w ∥w∥ = 2µQw 2.µ≥0 3.µ(w ⊤Qw−β) = 0 4.w ⊤Qw≤β First, notice thatµ >0, because otherwise,wmust be 0. So it must be the case that for comple- mentary slackness,w ⊤Qw=β. Then, from the first condition we have:Qw= w 2µ∥w∥ =λwwhere λ= 1 2µ∥w∥ . Thus we haveβ=w ⊤λw=λ∥w∥ 2 which means that∥w∥ 2 = q β λ . But now notice thatλis, by definition, an eigenvalue of of...

[47] [53]

Π 1w̸= Π 2w∀w,w̸=0 then ker(ΠDA−1 g C⊤[Π1 −Π 2]) will be empty. Corollary A.3(Sufficient conditions for Example 3.1 to satisfy property 3.1 w/ no info asymme- try).Suppose that agents in our setting have the same information (i.e.Π 1 = Π 2 = Π g). Then, the fairness function described by Example 3.1 satisfies Property 3.1 ifker(Π g) =∅,A 2 ≻A 1 and β≤σ d(...

[48] [54]

Π 1w̸= Π 2w∀w,w̸=0 then ker(ΠDA−1 g C⊤[Π1 −Π 2]) will be empty. 31 Corollary A.5(Sufficient conditions for Example 3.2 to satisfy property 3.2 w/ no info asymme- try).Suppose that agents in our setting have the same information (i.e.Π 1 = Π 2 = Π g). Then, the fairness function described by Example 3.2 satisfies Property 3.2 ifker(Π g) =∅,A 2 ≻A 1. Proof....

[49] [55]

This will give us optimality loss bounds for theβ-fair SE as compared to the unconstrained SE

Construct an ellipsoidalrestriction,E(β), such thatE(β)⊆ B(1)∩ W(β; ∆). This will give us optimality loss bounds for theβ-fair SE as compared to the unconstrained SE

[50] [56]

diameter

Construct an ellipsoidalenvelope,E( ˜β), such thatW(β; ∆)⊆ E( ˜β). This will give us opti- mality loss bounds for the convex restrictedβ-fair problem as compared to the nonconvex β-fair SE. A.3.1 Supplemental material for Section 4.1 First let’s construct the ellipsoidal restriction. We’ll use a nice lemma about when ellipsoids are inside the unit euclide...

[51] [57]

Ifp= 0 we are done; otherwise divide by∥p∥ 2 to obtain∥p∥ 2 ≤ ∥w⋆∥2

By Cauchy–Schwarz, ∥p∥2 2 ≤ ⟨w⋆, p⟩ ≤ ∥w⋆∥2 ∥p∥2. Ifp= 0 we are done; otherwise divide by∥p∥ 2 to obtain∥p∥ 2 ≤ ∥w⋆∥2. Hence∥P S(w⋆)∥2 ≤ ∥w⋆∥2. Proposition A.11(Accuracy and social welfare loss from ellipsoidal restriction).IfW(β; ∆)∈ F. Then we have the following upper bounds on optimality loss between the nonconvex fairness constrained problem (Equation...

[52] [58]

Ground-truth policy is not already in the restricted ellipsoid (i.e.,w ⋆ /∈ E(β))

[53] [59]

Envelope ellipsoid is strictly inside the unit ball (i.e.,LD < λ d(Q)−β, see Lemma A.7)

[54] [60]

Proof.We will just compare the bounds promised between the two propositions under conditions

Ground truth policy is strictly outside the ball envelope of the envelope ellipsoid (i.e.,∥w ⋆∥>q β+LD λd(Q) , see Lemma A.5) The principal gets a (strictly) tighter bound on restriction optimality loss using Proposition A.11 rather than Proposition A.9. Proof.We will just compare the bounds promised between the two propositions under conditions. CONDITIO...

[55] [61]

We use uniform costsA 1 =A2 withA 1 =I

[56] [62]

We use non-uniform costs withA 2 = 2A1 andA 1 =I

[57] [63]

Their use is denoted in figure captions

We use non-uniformA 2 = 2A1 random cost matrices (A 1 is sampled at random). Their use is denoted in figure captions. Desirability .We chooseeducation,occupation, andworkclassasdesirable, since these attributes are realistic to improve and likely to have downstream, external effects outside of income. Thus, to external entities (e.g. government bodies) th...

[58] [2020]

cancels itself out

URLhttps://arxiv.org/abs/2010.06529. 18 A Supplemental Material A.1 Supplemental material for Section 2 Table 2: Notation Table Symbol Meaning d dimension of features C Contribution matrix Ag groupgcost matrix Πg groupgprojection matrix ΠD diagonal desirability score matrix des(i) featureidesirability score g group Dg groupgdistribution of features Sg gro...

Pith/arXiv arXiv 2010

[59] [2021]

URLhttps://proceedings.mlr.press/v130/bechavod21a.html

[60] [2025]

ISBN 9798400714825

Association for Computing Machinery. ISBN 9798400714825. doi: 10.1145/3715275. 3732110. URLhttps://doi.org/10.1145/3715275.3732110

arXiv