Travel Reference
In-Depth Information
disconjunctive heuristic; lexicographic-by-features and lexicographic-by-aspects heuristic types.
The concept of greedoid analysis was fi rst proposed by Korte and Lovasz (1981) for proposing
the generalization of the matroid concept and referring to a class of optimization problems
which can be solved by greedy algorithms (Edmonds 1971). Greedy algorithms aim to solve a
combinatorial optimization problem piece by piece and to always select the piece with the most
benefi t. They are simple and very easy to implement but sometimes they might be shortsighted
since they simplify the decision process by always following the problem solving heuristic of
making the locally optimal choice at each stage.
The most common example to explain the greedy algorithm is 'Making the change'. If only
50 pence, 20 pence and 1 penny coins are available, the goal is to 'make a change' of 74 pence
with the minimum number of coins. In order to achieve this goal, the greedy algorithm is
applied so that each time the coin of the highest value, but less than the remaining change owed,
is selected until the whole process is fi nished. Therefore, one 50-pence coin, one 20-pence coin
and four 1-penny coins are selected to make the change. The algorithm, however, fails if the
available coins are 50 pence, 20 pence and 3 pence since after giving a 50-pence and a 20-pence
coin, the algorithm cannot use 3-pence coins for the remaining 4 pence change. But a human
would easily use one 50-pence coin and eight 3-pence coins to fulfi l the task. Greedy algorithms
can be used to mimic non-compensatory preference because sometimes people make decisions
just like the process presented by the greedy algorithm. Sometimes, people tend to select
the options with the most important attribute they regard and then keep selecting based on the
second important attribute and continue on until the fi nal option is selected. They will not go
back to review other information on other attributes which makes the decision process simple
and quick but in which the decision maker may miss some attractive options that did not meet
their requirement on the most important attribute but were very compelling on the other
important attributes.
In order to estimate this kind of non-compensatory (lexicographic) choice process for
consumers, the greedy algorithm was introduced and developed by Kohli and Jedidi (2007)
and Yee
et al
. (2007) independently. Kohli and Jedidi (2007) modifi ed a greedy algorithm to
infer lexicographic preference and two variants (conjunctive preference and lexicographic
preference by aspect) on purchase decisions of laptop computers. Because in reality there is
no perfect match between a certain type of preference function and the observed preference
rank order, the authors simply assigned the most fi t (statistically) preference model to each
individual. For the test of model goodness-of-fi t, the Kendall Tau value is used to indicate which
preference model has more powerful predictability. During the data collection, each laptop
is described by fi ve attributes with 13 aspects in total. After the fractional factorial design,
16 profi les are generated and presented to 69 MBA students using cards. The respondents
needed to rate each alternative according to their preference by a scale from 0-100. The
results showed two-thirds of the subjects in a study of consumer preference for laptops use
non-compensatory heuristics.
Yee
et al
. (2007) tested greedoid-based methods with applications to smartphones and
computers. They compared lexicographic preference by aspect (LBA) to two compensatory
benchmarks: hierarchical Bayes ranked logit (HBRL) and LINMAP. The greedy algorithm is
programmed in Java. A Fractional factorial design generated 32 full profi les and a web-based
questionnaire was conducted. The respondents were also students (339), they needed to rank the
alternatives either in a full rank manner or select the ones they would consider and then rank
these considered smartphones. The conjoint data set for computer choice was obtained from
a previous study, which was rating data on a ten-point scale for 16 full profi les. The fi ndings
suggested that the lexicographic models predict well.
