Discrete choice models are used to describe, explain, and predict choices made by people among a finite set of alternatives. However, standard discrete choice models come with an unrealistic assumption: that users are able to provide an unequivocal clear winner from any slate of alternatives. Often the user knows the winner but cannot report it, as when a UI does not allow a user to specify which of two movies they rated five stars is better. And often, among the myriad options available, the user is able to identify some good candidates, but finds it difficult to distinguish between the top contenders. In this paper, we study the problem of interacting with user choice data in which, sometimes, the user is unable to settle on a single compelling winner. To address this issue, we introduce an extension to the well-known random utility models (RUMs), which we call RUMs-with-Ties, where comparisons can result in a tie. We begin with an axiomatic formulation of Luce dating to the 1950s, and provide algorithms and matching lower bounds for operating on data with ties. We also provide a comprehensive comparison of RUMs versus RUMs-with-Ties from different angles. We present theoretical results indicating that simple ways of incorporating ties into existing approaches are unlikely to perform well. We also prove in our setting that the presence of additional items, even if lower in quality, allows an algorithm to learn the highest ranked element with far fewer trials. Finally, we provide experimental evaluations of different approaches to handling indistinguishable items in choice settings and demonstrate the advantages of direct modeling of ties via our approach.