Details

Autor(en) / Beteiligte

• Kohli, Rajeev
• Boughanmi, Khaled
• Kohli, Vikram

Titel

Randomized Algorithms for Lexicographic Inference

Ist Teil von

• Operations research, 2019-03, Vol.67 (2), p.357-375, Article opre.2018.1794

Ort / Verlag

Linthicum: INFORMS

Erscheinungsjahr

2019

Quelle

美国运筹学和管理学研究协会期刊（NSTL购买）

Beschreibungen/Notizen

• Consumers generally do not know about, much less evaluate, the hundreds or thousands of product variations available to them in a category. In many situations, including online shopping, they use product features to sequentially screen the set of available alternatives. In “Randomized algorithms for lexicographic inference,” R. Kohli, K. Boughanmi, and V. Kohli describe a method for inferring lexicographic rules from ranking, choice, or paired comparison data. They show that the inference problem is computationally hard (it generalizes the linear ordering problem) and propose a randomized algorithm that explicitly uses statistical distributions, the parameters of which are obtained by maximizing a likelihood function. The expected value of the solution obtained by the randomized algorithm is a function of the likelihood value and has a nontrivial lower bound. In an empirical test, the algorithm found screening rules that predicted consumer preferences substantially better than several competing methods. 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.