  When subjected to automated decision-making, decision subjects may
strategically modify their observable features in ways they believe will
maximize their chances of receiving a favorable decision. In many practical
situations, the underlying assessment rule is deliberately kept secret to avoid
gaming and maintain competitive advantage. The resulting opacity forces the
decision subjects to rely on incomplete information when making strategic
feature modifications. We capture such settings as a game of Bayesian
persuasion, in which the decision maker offers a form of recourse to the
decision subject by providing them with an action recommendation (or signal) to
incentivize them to modify their features in desirable ways. We show that when
using persuasion, the decision maker and decision subject are never worse off
in expectation, while the decision maker can be significantly better off. While
the decision maker's problem of finding the optimal Bayesian
incentive-compatible (BIC) signaling policy takes the form of optimization over
infinitely-many variables, we show that this optimization can be cast as a
linear program over finitely-many regions of the space of possible assessment
rules. While this reformulation simplifies the problem dramatically, solving
the linear program requires reasoning about exponentially-many variables, even
in relatively simple cases. Motivated by this observation, we provide a
polynomial-time approximation scheme that recovers a near-optimal signaling
policy. Finally, our numerical simulations on semi-synthetic data empirically
demonstrate the benefits of using persuasion in the algorithmic recourse
setting.
