In machine learning contests such as the Large Scale Visual Recognition Challenge [1] and the KDD Cup [2], contestants can submit candidate solutions and receive from an oracle (typically the organizers of the competition) the accuracy of their guesses compared to (a subset of) the ground-truth labels. A commonly used accuracy metric for binary classification tasks is the Area Under the Receiver Operating Characteristics Curve (AUC), which is equivalent to the probability of correct response in a 2-Alternative Forced Choice (2AFC) task [3] in which the classifier must distinguish one positively labeled example from one negatively labeled example. In this paper we illustrate how knowledge of the 2AFC score c of a set of guesses constrains the set of possible labelings that the dataset can have. We then show that the worst-case number of possible binary labelings of n examples corresponding to any particular 2AFC score c w.r.t. some candidate solution is O(2). 1 Computing the 2AFC Score Let y1, . . . , yn represent the ground-truth binary labels of a dataset of n examples and let ŷ1, . . . , ŷn represent the contestant’s real-valued guesses for the labels. To simplify our analysis in this paper, we assume that there are no ties, i.e., each ŷi is unique. In this case, the 2AFC score for the real-valued guesses w.r.t. the true binary labels can be computed as: