As data-driven predictive models are increasingly used to inform decisions,
it has been argued that decision makers should provide explanations that help
individuals understand what would have to change for these decisions to be
beneficial ones. However, there has been little discussion on the possibility
that individuals may use the above counterfactual explanations to invest effort
strategically and maximize their chances of receiving a beneficial decision. In
this paper, our goal is to find policies and counterfactual explanations that
are optimal in terms of utility in such a strategic setting. We first show
that, given a pre-defined policy, the problem of finding the optimal set of
counterfactual explanations is NP-hard. Then, we show that the corresponding
objective is nondecreasing and satisfies submodularity and this allows a
standard greedy algorithm to enjoy approximation guarantees. In addition, we
further show that the problem of jointly finding both the optimal policy and
set of counterfactual explanations reduces to maximizing a non-monotone
submodular function. As a result, we can use a recent randomized algorithm to
solve the problem, which also offers approximation guarantees. Finally, we
demonstrate that, by incorporating a matroid constraint into the problem
formulation, we can increase the diversity of the optimal set of counterfactual
explanations and incentivize individuals across the whole spectrum of the
population to self improve. Experiments on synthetic and real lending and
credit card data illustrate our theoretical findings and show that the
counterfactual explanations and decision policies found by our algorithms
achieve higher utility than several competitive baselines.

本文旨在在战略环境下寻找最优的政策和对策解释，包括 NP 难的问题，非降性和子模性，用标准贪心算法获得近似保证。最后，我们表明通过将拟阵约束加入问题的制定中，我们可以提高对策解释的最优集合的多样性，并激励整个人口谱上的个体自我改进。