We introduce leave-one-out unfairness, which characterizes how likely amodel's prediction for an individual will change due to the inclusion orremoval of a single other person in the model's training data. Leave-one-outunfairness appeals to the idea that fair decisions are not arbitrary: theyshould not be based on the chance event of any one person's inclusion in thetraining data. Leave-one-out unfairness is closely related to algorithmicstability, but it focuses on the consistency of an individual point'sprediction outcome over unit changes to the training data, rather than theerror of the model in aggregate. Beyond formalizing leave-one-out unfairness,we characterize the extent to which deep models behave leave-one-out unfairlyon real data, including in cases where the generalization error is small.Further, we demonstrate that adversarial training and randomized smoothingtechniques have opposite effects on leave-one-out fairness, which sheds lighton the relationships between robustness, memorization, individual fairness, andleave-one-out fairness in deep models. Finally, we discuss salient practicalapplications that may be negatively affected by leave-one-out unfairness.