Modelling Discrete Choice Problems

Post-lunch, the final day of Web Science 2016 continues with a keynote by Andrew Tomkins, whose focus is on the dynamics of choice in online environments. He begins by highlighting R. Duncan Luce's work, including his Axiom of Choice, but also points out the subsequent work that has further extended the methods for analysing discrete choice. Today, the most powerful models are mathematically complex and computationally intractable, as well as requiring sophisticated external representations of dependence.

From this work it has become clear that the Axiom of Choice holds only under relatively select conditions. Contextual data is of great importance here, and additional approaches to modelling general behaviour of discrete choice are required. The Randomised Utility Model, for instance, assigns a random utility value to each available choice, and in an ideal world users would then select the item with maximum utility; but because of existing preferences real-world users will deviate from such choices.

The question then becomes what governs that deviation: which models best explain the actual, observable deviation patterns? Ultimately, what we are dealing with here are permutations of the list of available items, ranked by preference – but there are no good algorithms for effectively representing this at present.

But choice processes may follow a nested path: they may begin with a broad decision (Republican vs. Democrat) followed by a more narrow decision (Clinton vs. Sanders). A relatively weighting can be assigned to the options available at each decision point, resulting in a decision tree and an underlying likelihood value for each choice. The problem that arises here is that choices may not always factor neatly into nests – the tree structure is often based on the researcher's intuition –, and that the development of the trees becomes difficult when it needs to be done for a very large number of options, requiring algorithmic rather than manual tree construction.

One example of such a complex context is the selection of restaurants from Google Maps and similar platforms, and Andrew now introduces a dataset of some 15.5 million queries for 400,000 restaurants in North America. These occur mainly around lunch and dinner, and there is a willingness to travel a greater distance on the weekends. Factors to consider here are the distance to the restaurant, the number of closer restaurants, the quality of the restaurant, etc. This also introduces the idea of local restaurant density, which is related to the ranking and distance of local restaurants, and generates a score for each available restaurant. Finally, such scores can also take into account the type of restaurant as an additional factor.

Additional factors to consider are repeat consumption mixed with novelty – people may consume their favourites especially much, but may also mix in new experiences in order to avoid reducing their pleasure through overconsumption, and such reconsumption patterns are very difficult to model. Generally, the lifetimes of most consumption items are finite: the intervals between repeat consumption – e.g. of musical tracks – are growing more and more over time.

How may this be modelled? For a given series of consumption sessions, a novelty rating can be assigned to each item consumed; on this basis, the likelihood of the reconsumption of any given item can be computed. A further quality rating can also be introduced to distinguish between different types of consumption items. This also models the user's increasing boredom with and eventual abandonment of items.

Such discrete choice problems are extremely prevalent. Whether existing axioms apply needs empirical validation in each case; where they do, some very useful toolkits are widely available to model user behaviours. Where they don't, things get a great deal more difficult.