In this paper, we focus on recourse for the setting of dynamic sequential allocations with limited resources, in which agents are competing against each other. In particular, we assume the decision maker is using a threshold policy and demonstrate the problem of recourse invalidation under the use case of college admissions. We then provide a first attempt to generate a valid threshold recourse that takes into account the feedback efect of recourse implementation.
This problem was addressed via an empirical simulation study [
In this paper, we present a setting of a dynamic allocation problem based on the college admission use-case. We provide an algorithm for generating all possible valid recourse values. Finally, we show that the current recourse properties may not be suficient to select the recourse which benefits users the most. There is a need to specify the recourse objective.
Let us consider the use case of college admissions. At each time step , a population of candidates apply for available seats. Each candidate has a 1-dimensional feature that represents their value to the decision maker (DM, university in this case) if admitted. The available resource quantity (number of seats) is . The DM uses a threshold allocation policy and sets a threshold such that at most candidates are admitted. A candidate is admitted if > . The overall utility of the allocation to the DM, , is the sum of features of all admitted applicants.
The population of candidates is composed of two groups: • New candidates . A set of candidates who are applying for the first time. We assume that the features of the new population arriving are the same at each round, e.g. {1 = 0.9, 2 = 0.7, . . . = 0.5}.1 For simplicity, we assume the candidates are sorted such that 1 has the highest value and has the lowest value. • Reapplying candidates . A set of candidates who were rejected in the previous round and attempt to be admitted in the current round. For the first round, this set is empty. Again, we assume the candidates are sorted such that 1 has the highest value and has the lowest value. The size of this set may change from round to round.
After setting the admission threshold , the DM provides the rejected candidates − = { ∈ | ≤ } a recourse ˆ. In this setting, all candidates are provided with the same recourse, which is the feature value they should have in the next round in order to be admitted. The rejected candidates from group cannot reapply (we allow only a second chance).
We consider the decision making process of the users regarding recourse implementation. All individuals share the same cost function : R × R → R. We assume the candidates choose whether to implement the recourse based on their expected utility. For this example, we set , the gain or reward given to each individual, to 1 if admitted (+ = 1) and 0 if rejected (− = 0). Given that the recourse is valid (acceptance is guaranteed upon implementation of
the recourse), the candidate will choose to implement the recourse only if 1 − (, ˆ) > 1≥ ^, i.e., the expected utility from implementing the recourse is higher than that of not implementing the recourse. The set of reapplying candidates after implementing the recourse is denoted .
Our goal is to provide a valid recourse, i.e. ˆ > +1. For this condition to hold, the total number of candidates above the value ˆ should be at most . We demonstrate the problem of invalid recourse using the following example. We consider an allocation problem at = 0 with resources = 2, cost function (, ˆ) = 2 · | ˆ − |, new candidates = {1 = 0.8, 2 = 0.7, 3 = 0.5, 4 = 0.4, 5 = 0.3, 6 = 0.1} and no current reapplying candidates = {}. The admission threshold is 0 = 0.6, i.e., the admitted set is 0+ = {1 = 0.8, 2 = 0.7}.
After setting the threshold, we would like to provide a recourse for the set of rejected candidates − = {−1 = 0.5, −2 = 0.4, −3 = 0.3, −4 = 0.1}. As mentioned above, we assume that the set of new candidates is identical at each time step. Let us consider the possible recourse value 0.75. The costs of implementing this recourse for the rejected candidates are {(−1 , 0.75) = 0.5, (−2 , 0.75) = 0.7, (−3 , 0.75) = 0.9, (−4 , 0.75) = 1.3}. Thus, three out of the four rejected candidates will choose to implement the recourse, as their cost is lower then the reward of being admitted (1). Yet, there are only two available slots ( = 2), so the recourse will not be valid. The threshold would be at least 0.75 and none of the candidates implementing the recourse would be admitted.
If we assume the feature space is unbounded, a naive valid recourse always exists - setting the recourse to a high enough value such that no individual chooses to implement it. In case of a bounded feature space, there may not be a valid recourse, e.g., when too many individuals would choose to implement a recourse of the maximal feature value.
In some cases, several values could be used as a valid recourse. Following our example, we can identify two ranges of recourse values. A recourse in the range [0.9, 1) would result in only one candidate implementing the recourse, −1 . The costs in the range [(−1 , 0.9) = 0.8, (−1 , 1) = 1) provide the candidate with a positive gain, while the costs for the other candidates would result in a non-positive utility, e.g., (−2 , 0.9) = 1. Therefore, the rest of the rejected candidates will not implement the recourse. Similarly, a recourse in the range (0.8, 0.9) would cause exactly two candidates to implement the recourse (−1 , −2 ). Each option is represented by a range and not by a single value. Clearly, the minimal value in this range would benefit the individuals implementing the recourse, as their cost would be minimised. We wish to provide a recourse of minimal cost, so we can always choose the minimal value as recourse.
Algorithm 1 generates all minimal valid recourse values. First, for each individual of the top + 1 rejected candidates, we find , the minimal recourse value for which the candidate will
Require: new candidates (of the next round, sorted in descending order), rejected candidates − (sorted in descending order) with |− | = , cost function , resource amount , > 0, feature upper bound , gain to the individual if accepted + ◁ Find the minimal recourse value for which the individual will choose not to implement the recourse. for from 1 to ( + 1, ) do
ifnd such that (− , ) = + end for ← {}
◁ A possible recourse value to allow the top candidates to reapply. This value guarantees that the rest of the reapplying candidates will choose not to implement the recourse (too costly), and that all individuals implementing the recourse will be admitted. for from 1 to (, − 1) do
ˆ ← ( +1, − +1 + ) ◁ The recourse is added only if it is not too costly for the individual with the lowest feature among the top reapplying candidates (hence not too costly for all top ), and the recourse does not exceed the feature upper bound.
if ˆ < and ˆ ≤ then
Add ˆ to end if end for
◁ The case of providing a recourse that allows all rejected candidates to reapply (if the number of available seats is at least the number of rejected candidates). if ≤ then
ˆ ← − +1 + ◁ There is no need to check whether the recourse is too costly for the rest of the rejected candidates.
if ˆ < and ˆ ≤ then
Add ˆ to end if end if return choose to not implement the recourse. Second, for each number of reapplying candidates from 1 to , we set the minimal recourse value ˆ to ( +1, − +1 + ]), > 0. This recourse is guaranteed to admit at most reapplying candidates, because this recourse is too costly for the rest of the rejected candidates. In addition, all reapplying candidates implementing this recourse are guaranteed to be allocated with the resource (their new feature value is larger than that of the -th new candidate). We then check two conditions: 1) The recourse is not too costly for all top rejected individuals. That is, the recourse value ˆ must be lower than .2 2) In 2Note that as the feature increases, the cost decreases. Therefore, it is suficient to verify this condition for the candidate with the lowest feature in the top rejected candidates. Utility-maximising recourse Given several values of a minimal valid recourse, there is a need to determine which value is preferred. Following our example, we are left with two options for a recourse: ˆ1 = 0.9, ˆ2 = 0.8 + for some > 0 (here, = 0.01). The decision of which specific value to choose depends on the objective. We consider two viewpoints: 1. The DM’s objective. Maximising the sum of features of admitted individuals ( ). 2. The objective of the reapplying population. Maximising the sum of individual rewards (to the individuals) for the set of the reapplying population ( ).
From the utilities for the DM and the reapplying candidates in table 1, we can observe that the DM would prefer to provide the recourse ˆ1 = 0.9 while the reapplying candidates would prefer the recourse ˆ2 = 0.81. Hence, for recourse generation for dynamic allocation problems, it is not suficient to specify that the recourse should be valid and minimal, there should also be a recourse objective in order to select one value from a set of possible recourse values.
The problem of recourse invalidation due to recourse implementation was only recently discussed in the literature. To the best of our knowledge, this is the first attempt to provide a valid feedback-aware recourse in dynamic settings. Using an example, we show that this problem could have several solutions, or not at all. In order to select one solution, new recourse desiderata should be in place, to prevent misuse of recourse by the decision makers.
The setting described in this paper has several limitations that can be relaxed in future work. For example, a more realistic setting could include applicants sampled from a population distribution. In addition, we only consider a threshold recourse, but the DM could also provide a diferent recourse to each individual. Moreover, we consider validity in a binary way, but in practice, most methods provide a recourse that is valid with high probability. When the recourse is not guaranteed to be valid, the estimation of expected utility for the users would change, and consequently the recourse should take that into consideration. Lastly, we do not consider the utility for new candidates, and the impact of intentionally providing a costly recourse to some individuals. Hence, some additional fairness notions for recourse may be required.
This work was supported by the Research Council of Norway under project number 302203.