The property in some random utility models that the distribution of ac
hieved utility is invariant across alternatives (the invariance proper
ty) is noteworthy as it applies to the multinomial logit model as well
as to its generalization: the generalized extreme-value (GEV) models.
GEV models constitute the most versatile tool yet known for dealing w
ith discrete choice situations with a structure of similarity-that is,
statistical dependence-among alternatives. The invariance property is
obviously violated in practice for heterogeneous populations. Therefo
re it has been argued that invariance constitutes a major problem for
GEV models. In contrast these authors argue that invariance is a usefu
l theoretical concept precisely by bringing out heterogeneity. Further
, multiple segment GEV models are a suitable tool for dealing with het
erogeneity-both theoretically and pragmatically. The class of random u
tility models possessing the invariance property was characterized by
Robertson and Strauss; called the RS class here. However, their proof
was not complete. An alternative representation of the RS class is sug
gested based on the notion of additive homogeneity. This new represent
ation enables the authors to prove the RS characterization theorem and
to simplify and systematize the proofs of many other results on RS-an
d specifically GEV-models. Also, in the new representation, the charac
terization is naturally stated in terms of the choice probabilities, a
nd of the probability distribution of maximum utility. Assuming that t
he distribution of actual choices is observable, the choice probabilit
ies are particularly empirically meaningful. This motivates a study of
the conditions for a choice probability structure to be RS representa
ble. For the binary choice case conditions that are both necessary and
sufficient are given.