  This paper proposes an original exchange property of valuations.This property
is shown to be equivalent to a property described by Dress and Terhalle in the
context of discrete optimization and matroids and shown there to characterize
the valuations for which the demand oracle can be implemented by a greedy
algorithm. The same exchange property is also equivalent to a property
described independently by Reijnierse, van Gellekom and Potters and by Lehmann,
Lehmann and Nisan and shown there to be satisfied by substitutes valuations. It
studies the family of valuations that satisfy this exchange property, the ultra
valuations. Any substitutes valuation is an ultra valuation, but ultra
valuations may exhibit complementarities. Any symmetric valuation is an ultra
valuation. Substitutes valuations are exactly the submodular ultra valuations.
Ultra valuations define ultrametrics on the set of items. The maximum of an
ultra valuation on $n$ items can be found in $O(n^2)$ steps. Finding an
efficient allocation among ultra valuations is NP-hard.
