Realistic/intuitive example where a nonadditive loss function is preferred over additive ones This thread asks, Are loss functions necessarily additive in observations? As of now, one answer is in the negative. However, I am not aware of any practical examples of nonadditive loss functions that are intuitively justifiable in real-world problems. Therefore, I am asking for a realistic/intuitive example where a nonadditive loss function is preferred over additive ones. 
To distinguish between 


*

*loss functions used as objective functions in estimation and their additivity w.r.t. to the training data


and 


*

*loss functions used for evaluating predictions and their additivity w.r.t. to the test data, 


the focus of this question is on the latter (assessing point predictions vs. actual realizations, for example).
 A: One example that comes to mind is the area under the ROC curve (AUC). For binary classification problems where the model outputs a continuous score (e.g. logistic regression or SVMs), AUC gives the probability that the model will score a randomly selected 'positive' instance higher than a randomly selected 'negative' instance.
For evaluating prediction performance, AUC plays the same role as other metrics/loss functions (e.g. misclassification rate, log loss, etc). Namely, it maps predicted scores and true labels to a real number that summarizes performance. And, it can be used as the basis for decision rules; in particular, as an objective function for model selection. Higher AUC is more desirable, so AUC is actually a utility function rather than a loss function. But, this distinction is minor, as one can simply multiply AUC by negative one to obtain the loss incurred by choosing a particular model.
Unlike misclassification rate, log loss, etc., AUC is non-additive (in the sense defined in the question). That is, if $y_i$ and $s_i$ are the true label and predicted score for the $i$th test case and $g$ is an arbitrary function, AUC can't be expressed in the form $\sum_{i=1}^n g(y_i, s_i)$. Rather, AUC is calculated by integrating the estimated ROC curve, which consists of the true positive rate vs. false positive rate as the classification threshold is varied. The integral is typically calculated using the trapezoid rule between points on the ROC curve. Although this involves a sum over trapezoids, AUC is non-additive because the area of each trapezoid depends non-additively on the predicted score and true labels of multiple test cases. For details, see section 7 and algorithm 2 in Fawcett (2006).
Bradley (1997), Huang and Ling (2005), and others have argued for the use of AUC over accuracy (which is additive). Although AUC has found wide use (e.g. ~247k google scholar results for +auc +classification), there are arguments against it as well; e.g. see Lobo et al. (2008).
References


*

*Fawcett, T. (2006). An introduction to ROC analysis. Pattern recognition letters, 27(8), 861-874.

*Bradley, A. P. (1997). The use of the area under the ROC curve in the evaluation of machine learning algorithms. Pattern recognition, 30(7), 1145-1159.

*Huang, J., & Ling, C. X. (2005). Using AUC and accuracy in evaluating learning algorithms. IEEE Transactions on knowledge and Data Engineering, 17(3), 299-310.

*Lobo, J. M., Jimenez‐Valverde, A., & Real, R. (2008). AUC: a misleading measure of the performance of predictive distribution models. Global ecology and Biogeography, 17(2), 145-151.
A: A sensible choice of loss could be the negative of utility. Within the framework of maximization of expected utility (MEU), we would have additive loss, since we would use average (over the set of test cases) negative loss as an estimate of expected utility. On the other hand, we could have nonadditive loss if we abandon MEU. E.g. if we are trying to maximize the utility of the worst outcome, we could choose the negative maximum (over the set of test cases) loss as an estimate of our target. A key observation here is that the maximum is not an additive function.
