The inference of a lexicographic rule from paired comparisons, ranking, or choice data is a discrete optimization problem that generalizes the linear ordering problem. We develop an approach to its solution using randomized algorithms. First, we show that maximizing the expected value of a randomized solution is equivalent to solving the lexicographic inference problem. As a result, the discrete problem is transformed into a continuous and unconstrained nonlinear program that can be solved, possibly only to a local optimum, using nonlinear optimization methods. Second, we show that a maximum likelihood procedure, which runs in polynomial time, can be used to implement the randomized algorithm. The maximum likelihood value determines a lower bound on the performance ratio of the randomized algorithm. We employ the proposed approach to infer lexicographic rules for individuals using data from a choice experiment for electronic tablets. These rules obtain substantially better fit and predictions than a previously described greedy algorithm, a local search algorithm, and a multinomial logit model.
Kohli, Rajeev, Khaled Boughanmi, and Vikram Kohli. "Randomized Algorithms for Lexicographic Inference." Operations Research 67, no. 2 (2019): 357-375.
Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.
Each topic is linked to an index of publications on that topic.