  We are witnessing an increasing use of data-driven predictive models to
inform decisions. As decisions have implications for individuals and society,
there is increasing pressure on decision makers to be transparent about their
decision policies. At the same time, individuals may use knowledge, gained by
transparency, to invest effort strategically in order to maximize their chances
of receiving a beneficial decision. Our goal is to find decision policies that
are optimal in terms of utility in such a strategic setting. To this end, we
first characterize how strategic investment of effort by individuals leads to a
change in the feature distribution. Using this characterization, we first show
that, in general, we cannot expect to find optimal decision policies in
polynomial time and there are cases in which deterministic policies are
suboptimal. Then, we demonstrate that, if the cost individuals pay to change
their features satisfies a natural monotonicity assumption, we can narrow down
the search for the optimal policy to a particular family of decision policies
with a set of desirable properties, which allow for a highly effective
polynomial time heuristic search algorithm using dynamic programming. Finally,
under no assumptions on the cost individuals pay to change their features, we
develop an iterative search algorithm that is guaranteed to find locally
optimal decision policies also in polynomial time. Experiments on synthetic and
real credit card data illustrate our theoretical findings and show that the
decision policies found by our algorithms achieve higher utility than those
that do not account for strategic behavior.
