Randomized Algorithms for Lexicographic Inference

Rajeev Kohli (), Khaled Boughanmi () and Vikram Kohli ()
Additional contact information
Rajeev Kohli: Graduate School of Business, Columbia University, New York, New York 10027;
Khaled Boughanmi: Graduate School of Business, Columbia University, New York, New York 10027;
Vikram Kohli: McCormick School of Engineering, Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, Illinois 60208

Operations Research, 2019, vol. 67, issue 2, 357-375

Abstract: 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.

Keywords: lexicographic rules; noncompensatory choice; consumer search; discrete optimization; randomized algorithms; analysis of algorithms; maximum likelihood (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/opre.2018.1794 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:2:p:357-375

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().