Optimizing the application order under precedent-based decision-making

We study the decision problem of a Proposer who has a set of applications to submit for approval to an Authority and can choose an order of submission. The Proposer's utility depends on the Authority's rulings. The Authority has to be consistent with its past decisions, which we model using the nearest-neighbor criterion. If the Proposer's utility increases with the set of approved applications, then any greedy strategy is optimal for her: She should submit any application that, given the current history, would be approved. However, if her utility increases with some approvals but decreases with others, the Proposer's problem becomes significantly more complex. In the single-dimensional case, an optimal strategy can be computed in polynomial time. In the general case, however, finding an optimal strategy is NP-hard. Thus, even in the absence of uncertainty or strategic behavior on the part of the Authority, evaluating the impact of current submissions on future outcomes can be computationally intractable.