[WP-019] A Note on Ordinally Concave Functions

Author

Satoru Fujishige, Fuhito Kojima, Koji Yokote

Abstract

The notion of ordinal concavity of utility functions has recently been considered by Hafalir, Kojima, Yenmez, and Yokote in economics while there exist earlier related works in discrete optimization and operations research. In the present note we consider functions satisfying ordinal concavity and introduce a weaker notion of ordinal weak-concavity as well. We also investigate useful behaviors of ordinally (weak-)concave functions and related choice correspondences, show a characterization of ordinally weak-concave functions, and give an efficient algorithm for maximizing ordinally concave functions. We further examine a duality in ordinally (weak-)concave functions and introduce the lexicographic composition of ordinally weak-concave functions.

PDF