Ultra valuations

Understand

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.