The random utility model is one of the most fundamental models in discrete choice analysis in economics. Although Falmagne (1978) obtained an axiomatization of the random utility model, his characterization requires strong observability of choices, i.e., the frequencies of choices must be observed from all subsets of the set of alternatives. Little is known, however, about the axiomatization when the frequencies on some choice sets are not observable. In fact, the problem of obtaining a tight characterization appears to be out of reach in most cases in view of a related NP-hard problem. We consider the following incomplete dataset. Let X be a finite set of alternatives. Let X* ⊆ X bea set of unobservable alternatives. Let D ⊆ 2X be the set of choice sets. We assume that the choice frequency ρ(D, x) is unobservable (i.e., not defined) if and only if x ∈ X* or D ∉ D. Let M* ≡ {(D,x)|x ∈ D ∈ 2X and [x ∈ X* or D ∉ D]} be the set of all pairs (D,x) such that ρ(D, x) is not observable. To state our theorem, for any ρ and (D, x) ∈ M ≡ {(D, x) ∈ D × X | x ∈ D}, define a Block-Marschak polynomial by K(ρ, D, x) = ΣE:E⊇D(−1)|E\D|ρ(E,x).