Designing Algorithmic Delegates

As AI technologies improve, people are increasingly willing to delegate tasks to algorithmic agents. A human decision-maker decides whether to delegate to an AI agent based on features of the decision-making instance they are faced with; since humans typically lack full awareness of these features, they perform a kind of categorization by treating decision-making instances that agree in all their observable features as indistinguishable from one another. In this paper, we define the problem of designing the optimal algorithmic delegate in the presence of categorization, and reveal the fundamentally combinatorial nature of this problem. We show that finding the optimal delegate is computationally hard in general, but we find an efficient algorithm for a large family of settings.