  People affected by machine learning model decisions may benefit greatly from
access to recourses, i.e. suggestions about what features they could change to
receive a more favorable decision from the model. Current approaches try to
optimize for the cost incurred by users when adopting a recourse, but they
assume that all users share the same cost function. This is an unrealistic
assumption because users might have diverse preferences about their willingness
to change certain features. In this work, we introduce a new method for
identifying recourse sets for users which does not assume that users'
preferences are known in advance. We propose an objective function, Expected
Minimum Cost (EMC), based on two key ideas: (1) when presenting a set of
options to a user, there only needs to be one low-cost solution that the user
could adopt; (2) when we do not know the user's true cost function, we can
approximately optimize for user satisfaction by first sampling plausible cost
functions from a distribution, then finding a recourse set that achieves a good
cost for these samples. We optimize EMC with a novel discrete optimization
algorithm, Cost Optimized Local Search (COLS), which is guaranteed to improve
the recourse set quality over iterations. Experimental evaluation on popular
real-world datasets with simulated users demonstrates that our method satisfies
up to 25.89 percentage points more users compared to strong baseline methods,
while, the human evaluation shows that our recourses are preferred more than
twice as often as the strongest baseline recourses. Finally, using standard
fairness metrics we show that our method can provide more fair solutions across
demographic groups than baselines. We provide our source code at:
https://github.com/prateeky2806/EMC-COLS-recourse
