Abstract
Traditional approaches to ranking in web search follow the paradigm of rank-by-score: a learned function gives each query-URL combination an absolute score and URLs are ranked according to this score. This paradigm ensures that if the score of one URL is better than another then one will always be ranked higher than the other. Scoring contradicts prior work in behavioral economics that showed that users' preferences between two items depend not only on the items but also on the presented alternatives. Thus, for the same query, users' preference between items A and B depends on the presence/absence of item C. We propose a new model of ranking, the Random Shopper Model, that allows and explains such behavior. In this model, each feature is viewed as a Markov chain over the items to be ranked, and the goal is to find a weighting of the features that best reflects their importance. We show that our model can be learned under the empirical risk minimization framework, and give an efficient learning algorithm. Experiments on commerce search logs demonstrate that our algorithm outperforms scoring-based approaches including regression and listwise ranking.
Introduction: The Challenge of Context-Dependent Preferences
In classical ranking theory, models often assume the "Independence of Irrelevant Alternatives" (IIA). Under this assumption, if a consumer prefers a $20 paper shredder (Product A) over a $50 one (Product B), the introduction of a $95 "decoy" shredder (Product C) should not alter that preference.
However, behavioral economics and real-world commerce search logs reveal a more complex reality. The presence of a high-priced alternative can make a mid-range option appear more attractive—a phenomenon known as a preference flip. Traditional "rank-by-score" models, which assign fixed values to (query, item) pairs, are mathematically incapable of capturing these context-dependent shifts. If A is scored higher than B, it will always be ranked higher, regardless of the other items on the page. To address this, we propose a model that ranks items in context.
The Random Shopper Model (RSM)
The Random Shopper Model (RSM) departs from static scoring by viewing each product feature (e.g., price, brand, rating) as a Markov chain or "topology" over the set of items to be ranked.
In this framework, each product is represented as a node in a graph. An edge from product $u$ to $v$ represents the probability that a user will transition their interest from $u$ to $v$ based on a specific feature. For instance, in a "lower price" topology, the transition probability toward cheaper items would be higher.
A hypothetical shopper performs a random walk across this graph. At each step, they select a feature based on its learned "importance weight" and follow an edge in that feature's corresponding Markov chain. The final ranking is determined by the stationary distribution of this random walk; products where the shopper spends the most time are considered the most relevant.
Learning the model involves finding optimal weights for these Markov chains. We utilize an iterative gradient-ascent-style algorithm to minimize the difference between the model's predicted stationary distribution and observed user click-through rates (CTR).
Experimental Evaluation
We evaluated RSM using real-world data from a major commerce search engine, focusing on "high-consideration" categories like TVs and digital cameras where users frequently compare attributes.
To rigorously test the model's ability to handle context, we developed a specialized "preference flip" benchmark. This dataset consists of product pairs (A, B) where user preferences were observed to flip depending on the presence of a third item. We compared RSM against two standard rank-by-score baselines: Least Squares (LS) regression and Listwise Ranking (LR).
Key Results and Insights
Our analysis confirmed that preference flips are a significant factor in commerce search, occurring in approximately 25% of queries.
Because context-oblivious models cannot resolve the contradictions inherent in preference flips, they are mathematically capped at 50% accuracy on our specialized benchmark. In contrast, RSM achieved approximately 58% accuracy, representing a statistically significant improvement ($p < 10^{-5}$).
Beyond accuracy, the model offers several advantages:
- Emergent Context: By deriving rankings from a random walk across the entire result set, an item's value is inextricably linked to its neighbors.
- Efficiency: Despite its complexity, the RSM algorithm is computationally efficient. Training took approximately 14 seconds on our dataset, and ranking required only 0.02ms per query, making it suitable for production environments.
Limitations and Future Work
While RSM provides a powerful framework for context-aware ranking, several areas for future research remain:
- Proxy Metrics: The current model uses CTR as a proxy for preference. Future iterations could incorporate purchase data to better reflect genuine consumer intent.
- Topology Design: We currently use a simple rank-based method to convert numeric features into Markov chains. Optimizing these encodings remains an open question.
- Query-Specific Weights: The model currently learns global weights. Integrating query intent (e.g., distinguishing between a user seeking "budget" vs. "professional" gear) could further refine the importance of specific feature topologies.
Summary updated