Randomized Algorithms for Lexicographic Inference

• 成果类型: Article
• 署名作者: Kohli, Rajeev; Boughanmi, Khaled; Kohli, Vikram
• 署名单位: Columbia University; Northwestern University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1794
• 发表日期: 2019
• 页码: 357-375
• 关键词: models; CHOICE; REPRESENTATION; search; JUDGMENT

摘要

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.