  Progress in machine learning and artificial intelligence has spurred the
widespread adoption of automated decision systems (ADS). An extensive
literature explores what conditions must be met for these systems' decisions to
be fair. However, questions of legitimacy -- why those in control of ADS are
entitled to make such decisions -- have received comparatively little
attention. This paper shows that when such questions are raised theorists often
incorrectly conflate legitimacy with either public acceptance or other
substantive values such as fairness, accuracy, expertise or efficiency. In
search of better theories, we conduct a critical analysis of the philosophical
literature on the legitimacy of the state, focusing on consent, public reason,
and democratic authorisation. This analysis reveals that the prevailing
understanding of legitimacy in analytical political philosophy is also
ill-suited to the task of establishing whether and when ADS are legitimate. The
paper thus clarifies expectations for theories of ADS legitimacy and charts a
path for a future research programme on the topic.
