Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
50,278 characters · 11 sections · 45 citation commands
\twocolumn[
\aistatstitle{When the Universe is Too Big: Bounding Consideration Probabilities for Plackett--Luce Rankings}
\aistatsauthor{ Ben Aoki-Sherwood \And Catherine Bregou \And David Liben-Nowell }
\aistatsaddress{University of Colorado Boulder \And Carleton College \And Carleton College }
\aistatsauthor{Kiran Tomlinson \And Thomas Zeng}
\aistatsaddress{Microsoft Research \And University of Wisconsin--Madison}] \runningauthor{Aoki-Sherwood, Bregou, Liben-Nowell, Tomlinson, Zeng}
Among the wide-ranging topics studied in the behavioral sciences, predicting and explaining human choices is a central challenge across a range of disciplines. (Why that entr\'{e}e at that caf\'{e} with that person, of all the restaurants you can think of, of all your potential dates, of all the dishes on the menu?) Settings where individuals select an item from a collection of available alternatives are well studied in the literature on discrete choice train2009discrete, with applications ranging from marketing chintagunta2011structural and voting thurner2000empirical to transportation policy horne2005improving and recommender systems danaf2019online. A closely related line of work studies rankings alvo2014statistical, rather than single choices, often modeling a ranking as a sequence of discrete choices (selecting the top-ranked item, then the second, etc.). The Plackett--Luce ranking model plackett1975analysis,luce1959individual exemplifies the link between discrete choice and ranking, positing that items at each of $k$ positions are selected in turn according to a logit choice model mcfadden1973conditional. Due to its convex negative log-likelihood and easily interpretable parameters, the Plackett--Luce model has seen substantial use in the machine learning literature seshadri2020learning,zhao2016learning,zhao2019learning,nguyen2023efficient,saha2020pac.
However, as Plackett--Luce models are applied to datasets of increasing size, it becomes implausible that individuals are able to weigh all of their options against each other. This issue has been largely ignored in the ranking setting, but has been discussed at length in the discrete choice literature. For instance, in keeping with the framework of bounded rationality simon1957models, a prominent line of work in discrete choice suggests that selection is a two-stage process, where individuals first narrow their options to a small consideration set from which their final selection is made hauser1990evaluation,shocker1991consideration. These so-called “consider then choose” models have shown considerable promise in their explanatory power roberts1991development,bacsar2004parameterized and help address the issue of large item universes. But they suffer from a major issue: consideration sets are almost always unobserved (except in carefully controlled experimental settings) and cannot in general be identified from observed choice data jagabathula2023demand,nierop10:_retriev_unobs_consid_sets_househ_panel_data. However, if it were possible to derive meaningful information about consideration probabilities from rankings, this would be very valuable: for instance, in recommender systems, we can think of the core goal as identifying items with high utility but low consideration probability. These are the types of items that users would not discover naturally but still enjoy.
\paragraph{The present work.} In this paper, we define the natural consider-then-rank model obtained by augmenting top-$k$ Plackett--Luce with the independent-consideration rule manzini2014stochastic, in which each item advances to the ranking stage randomly and independently with an unknown item-specific consideration probability. We term this model Plackett--Luce with consideration (PL+C). One might hope that richer observations---a ranking of $k$ items rather than just a single choice---would make it feasible to identify consideration probabilities, at least for large $k$. Unfortunately, our first result is negative: regardless of $k$, there are infinite families of consideration probabilities that generate the same distribution of observed data. However, we show that it is possible to derive meaningful bounds on consideration probabilities, despite their non-identifiability. In addition to observations of rankings, some (but not all) of our bounds draw on two types of information for learning about consideration probabilities: (1) known item utilities and (2) a lower bound on expected consideration set size. (Later, we discuss settings where such information is indeed available.) First, we derive relative bounds on the consideration probabilities of different items, of the form “if item $i$ has consideration probability $p_i$, then $j$'s consideration probability is greater than $f(p_i)$.” The intuition is that if $i$ has higher utility then $j$, then we would expect to see $i$ ranked highly more often than $j$---but if instead $j$ outperforms $i$, then consideration must be the culprit, and $j$'s consideration probability must be higher than $i$'s. Quantitatively, the $j$-vs.-$i$ gap in the frequency of being ranked highly tells us how much more often $j$ is considered than $i$. To make this bound more useful, we show how to infer that $i$ has higher utility than $j$ despite confounding from consideration, which invalidates standard Plackett--Luce inference.
These relative bounds provide useful information, but, absent additional anchor points, they still admit a large range of possible consideration probabilities. Motivated by this limitation, we then seek absolute upper and lower bounds on consideration probabilities. For lower bounds, na\"{i}vely, we might hope that the fraction of observed rankings in which item $i$ appears would be a lower bound on $i$'s consideration probability. However, this idea fails in our setting, as we assume that we only observe rankings of exactly $k$ items, and that any instance where fewer than $k$ items were considered is discarded before we observe it (or, equivalently, a consideration set is resampled). However, we are able to rescue this approach if we can assume a mild bound on expected consideration set size, since we can then upper bound the probability that a sample was discarded. Next, we turn to upper bounds on items' consideration probabilities. Our absolute upper bounds use exogenous knowledge of item utilities, which we learn in our data from survey questions with explicit consideration sets. Thus, if an item $i$ is ranked first less often than we would expect given its utility, then it must not be considered very often relative to the other items. Using a pessimistic upper bound of 1 for other items' consideration probabilities can then yield a nontrivial upper bound on $i$'s consideration probability. To wrap up our theoretical contributions, we provide algorithms to combine our absolute and relative bounds by propagating over a directed acyclic graph induced by our relative bounds.
Finally, we demonstrate how our methods can reveal meaningful information about consideration probabilities on real data. In a psychology experiment about perceptions of U.S.\ history putnam2018collective, participants completed several tasks related to their view of the historical importance of particular U.S.\ states, such as naming the three states they believe contributed most to U.S.\ history. They were also provided with a random set of 10 states and asked to rate their percentage contribution to U.S. history. (We convert the numerical scores to rankings.) These two settings, Top-3 and Random-10, provide us both observations from fixed consideration sets (Random-10) and from unknown consideration sets (Top-3). We can thus estimate utilities in the absence of consideration from the Random-10 data and then estimate consideration from the Top-3 data, using our bounds. Our results on this data align with expectations about state history: original colonies Massachusetts and Virginia were the states with the highest range of possible consideration probabilities ($0.59$ to $1.00$), while Missouri, an anecdotally often-forgotten state fotgottenstates, had the lowest upper bound on consideration probability ($0.11$).
There are several approaches to adding consideration to choice models. The one closest to our work adds a consideration stage to random utility models ben1995discrete,roberts1991development,nierop10:_retriev_unobs_consid_sets_househ_panel_data,bacsar2004parameterized, following the formulation of manski1977structure. Another line of work uses a different choice model, assuming choosers have a strict preference ordering over items and deterministically pick the highest ranked item they consider manzini2014stochastic,cattaneo2020random. An extension of this model allows the preference orderings to be stochastic jagabathula2023demand. There are also a variety of approaches for modeling the consideration stage, including feature-based constraints ben1995discrete, rational utility-maximization roberts1991development, and the independent consideration model we use manzini2014stochastic.
The issue of non-identifiability likewise has a number of proposed solutions. In the most straightforward approach, experimenters directly ask item availability questions to choosers (e.g., “is item $i$ available?” or “did you consider item $i$?”) roberts1991development,ben1995discrete,suh2009role, which is especially useful when trying to estimate constraint-based consideration models. A similar approach in online shopping settings uses data about which items customers view to directly infer consideration sets gu2012identifying,moe2006empirical. Another strategy leans on knowing when a default “outside option” (i.e., making no selection) was selected and assuming that it is only chosen when no items are considered manzini2014stochastic,jagabathula2023demand. Yet another approach supposes we have observations of choices over time as item features vary and uses the idea that demand for highly considered items will respond more to changes in features abaluck2021consumers. Finally, several papers make assumptions about the parametric form of consideration probabilities as a function of chooser and item features and estimate those parameters from choice data nierop10:_retriev_unobs_consid_sets_househ_panel_data,bacsar2004parameterized, although this approach makes inference computationally challenging.
While consideration sets have been extensively explored in single-choice setting, they have received limited attention in the ranking literature; to our knowledge, our work is the first to recover information about consideration probabilities under Plackett--Luce. palma2017improving discusses the idea of consideration sets in relation to rankings, but only uses them to identify a relevant prefix of rankings in survey data (items ranked above the outside option are treated as the implied consideration set). fok2012rank mention the idea of applying consideration sets to rankings, but do not pursue this direction as they focus on survey settings where respondents are forced to rank all available items. We note that the Plackett--Luce model is sometimes referred to as the “rank-ordered logit” in the econometrics literature beggs1981assessing,hausman1987specifying, while “Plackett--Luce” is more common in computer science (for length-2 rankings, a.k.a.\ pairwise comparisons, the model is also called “Bradley--Terry” bradley1952rank). Much of the existing computational work on the Plackett--Luce model has focused on utility inference guiver2009bayesian,maystre2015fast,zhao2016learning,liu2019learning.
In a ranking setting, we have a universe of items $\mathcal U = \{1, \dots, n\}$ and observe a collection of length-$k$ rankings of the form $r = \tup{r_1, \dots, r_k}$, where $k \le n$ is fixed and each $r_i \in \mathcal U$ is distinct.
The Plackett--Luce model plackett1975analysis,luce1959individual posits that each item $i$ has a utility $u_i \in \mathbb{R}$ and that rankings are formed by a sequence of choices with the probability of selecting $i \in \mathcal{U}$ proportional to $\exp(u_i)$, first choosing a top-ranked item, then a second-ranked item (distinct from the first), etc. We assume these $k$ choices are made from only a subset of items, a consideration set $C\subseteq \mathcal U$ where $|C| \ge k$. The probability of observing ranking $r$ under a Plackett--Luce (PL) model with consideration set $C$ is
if $\set{r_1, \ldots, r_k} \subseteq C$; otherwise, ${\textstyle \Pr_{\textup{\textsc{\scriptsize PL}}}}(r \mid C) = 0$.
As our model of consideration, we assume each item $i$ has a positive consideration probability $p_i \in (0, 1]$ and that items are considered independently, conditioned on the constraint ${|C| \ge k}$. (We do not observe any cases where fewer than $k$ items are considered---either such instances are thrown out before we observe them, or the chooser considers a new set.) Thus, the probability of considering a set $C$ with $|C| \ge k$ is
where $z_{k, p} = \sum_{C \subseteq \mathcal U, |C| \ge k} \left(\prod_{i \in C} p_i\right) \prod_{j \in \mathcal{U}\setminus C} (1-p_j)$ normalizes the probabilities given the condition $|C| \ge k$. For any set $C$ with $|C| < k$, we define ${\textstyle \Pr_{\textup{\textsc{\scriptsize C}}}}(C) = 0$.
Combining (ref) yields our full model of rankings, Plackett--Luce with consideration (PL+C), in which we sum over all possible consideration sets, weighted by their probabilities, and apply Plackett--Luce:
Finally, we introduce some additional notation. Let $\mathcal R$ be the set of length-$k$ rankings over $\mathcal U$ and let $\mathcal R_{i\le \ell}\subset \mathcal R$ be the set of rankings that contain $i$ in any of the top $\ell$ positions. For a set of rankings $R$, let ${\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(R) = \sum_{r \in R} {\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(r)$, and likewise for ${\textstyle \Pr_{\textup{\textsc{\scriptsize PL}}}}(R\mid C)$.
We begin with an impossibility result: even with complete information about ${\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(r)$ for every ranking $r$---and even with complete knowledge of the utilities $u_1, \ldots, u_n$ for all items---we cannot infer the consideration probabilities $p_1, \ldots, p_n$ due to non-uniqueness. See (ref) for all omitted proofs.
(ref) says that we cannot hope to compute exact consideration probabilities. Nevertheless, we will show that, in certain circumstances, we can conclude something about the relative values of two items' consideration probabilities. To do this, we will first need the following lemma about the probability of observing items in the top $\ell$ positions under Plackett--Luce.
Additionally, if both $i$ and $j$ are considered, it is easy to show that $i$ (the higher utility item) is more likely to be highly ranked than $j$. Thus, if both are equally likely to be considered, we would expect to see $i$ appearing more often in high rank positions than $j$. If, to the contrary, we observe that $j$ is chosen more frequently than $i$, then it must be the case that $j$ is considered more often. That is: if we know the utilities of items, then we can use flips in top-$\ell$ ranking rates to identify which items are considered more frequently than others. We formalize this intuition in the following theorem.
We defer the proof of (ref), as this result is effectively subsumed by a more powerful theorem that also gives us information about the relative sizes of $p_i$ and $p_j$:
The proof isolates rankings that contain $i$ and not $j$ (and vice versa) and uses a bijection between those rankings and their associated consideration sets in conjunction with (ref) to establish the claim. Intuitively, the terms $p_i(1-p_j)$ and $p_j(1-p_i)$ come from considering $i$ and not $j$ or $j$ and not $i$, which we then cross-divide to group like variables. Taking $c=1$, (ref) implies (ref), since $x/(1-x)$ is a monotonically increasing function of $x$ for $x \in [0, 1)$. Additionally, the smaller $c$ is (i.e., the more we see $j$ ranked higher than $i$, despite its lower utility), the larger the gap between $p_i$ and $p_j$ must be. We can rearrange (ref) to be either an upper bound on $p_i$ in terms of $p_j$ or a lower bound on $p_j$ in terms of $p_i$:
Our relative bounds appear to require exogenous knowledge of utilities, but we only need to know that $u_i > u_j$, not exact values. This can be inferred from rankings: if we only consider rankings in which both $i$ and $j$ appear (so we know both were considered), then whichever is ranked higher more often has higher utility, given enough observations. Formally:
We note that this approach to identifying relative utilities is prone to sampling noise for rare items.
Suppose that we observe a set of rankings generated by a PL+C model, where the underlying consideration probabilities $p_1, \ldots, p_n$ are unknown. Even if we have a priori knowledge of the underlying utilities $u_1, \ldots, u_n$, (ref) says that we cannot compute the values of $p_1, \ldots, p_n$. But we might hope that (ref) (or the more powerful (ref)) would allow us to leverage the empirical data into knowledge about their relative consideration probabilities: that theorem might allow us to propagate a lower bound on $p_i$ into a lower bound on $p_j$. But for this kind of implication to be meaningful, we need a nontrivial starting point---that is, some way to infer that $p_i$ is bounded away from zero, say $p_i > \eps$.
How might we get started? While it is tempting to think that item $i$'s rate of occurrence in the observed length-$k$ rankings would lower bound $p_i$, the fact that we condition our samples on $|C| \ge k$ means that this relationship may not hold. For example, if each of $n = 5$ items has an identical consideration probability $p > 0$ and identical utility, then each of those five items occurs as the top choice with probability $0.2$, by symmetry---but that is true for any value of $p > 0$, whether $p \ge 0.2$ or $p = 0.01$. So $p_i \ge {\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(\mathcal R_{i \le k})$ may not hold. However, if we make some relatively mild assumptions about the expected consideration set size, then we can use item occurrence rates and a Chernoff bound to get a lower bound on their consideration probability. From a practical perspective, we note that measuring mean consideration set size is a common task in consumer research hauser1990evaluation.
Given this bound on the cases where $|C| < k$, we can correct our earlier hopeful argument.
Algorithmically, we can use (ref) to get initial lower bounds on consideration probabilities, and then (ref)---in particular, in the lower bound form (ref)---to propagate them to yield lower bounds on other items' consideration probabilities. Define a directed graph $G = \tup{V, E}$ with $V = \mathcal U$ and an edge $\tup{i, j}$ for each $i, j \in \mathcal U$ such that $u_i > u_j$ and ${\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(\mathcal R_{i \le \ell}) < {\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(\mathcal R_{j \le \ell})$ for some $\ell$. Each edge $\tup{i, j}$ represents a pair of items where (ref) gives the lower bound (ref) for $p_j$ as a function of $p_i$. Because utilities strictly decrease along every edge, and thus along every path, the graph $G$ is acyclic. We can therefore topologically sort $G$ and use this ordering to propagate lower bounds on consideration probabilities. This procedure is formalized in (ref).
In the proof, we show that ${\forall i \in \mathcal U : b_i \le p_i}$ is an invariant throughout the execution of the algorithm. The initial values of $b_i$ set in Line (ref) satisfy the condition by (ref); all updates to values of $b_i$ in Line (ref) maintain this property by (ref), the lower-bound form of (ref).
We now turn to upper bounds on consideration probabilities, in the same spirit as for lower bounds in (ref). We will again be able to use (ref) to tighten our initial upper bounds. However, upper bounding consideration probabilities turns out to be a bit trickier, so we will have to build some more technical infrastructure.
Our approach to inferring an upper bound on $p_i$ is based on the intuition that increasing the consideration probability of a different item $j$ only makes $i$ less likely to be chosen; increasing the competition for $i$ (by making $j$ more likely to be an additional competitor) can only hurt $i$'s chances. We can then use this idea to bound $i$'s winning chances against a hypothetical scenario where all other consideration probabilities are 1, in which case the consideration mechanism is easy to analyze. But, surprisingly, that intuition about increasing $j$'s consideration probability turns out to be false (but not by too much). As a result, our lemma statements will need to be a bit more technical. (For example, suppose that $\mathcal U = \set{1, 2, 3}$ with $u_1 = u_2 = +\infty$ and $u_3 = -\infty$. Let $k = 2$, and let $p_1 = 1$ and $p_2 = 0.02$. Item 3 never wins, but its presence affects the relative strengths of items 1 and 2. If $p_3 = 0$, then the only consideration set that we ever observe is $\set{1, 2}$, and so item 2 wins 50% of the time. But if $p_3$ is increased to $1$, then 98% of the observed consideration sets are $\set{1, 3}$; the chance that item 2 wins drops from 50% to 1%.) It turns out that the issue that arises here is specifically about cases in which the consideration set is of size exactly $k$. Fortunately, it is rare that a length-$k$ ranking emerges from a consideration set of size exactly equal to $k$ (under our ongoing mild assumptions about $\sum_i p_i$):
We use this bound on the probability that $|C| = k$ to bound the amount by which $i$'s chances of winning increases when $j$'s consideration probability decreases.
The idea behind the proof is to group consideration sets containing $i$ into pairs where one contains $j$ and the other does not. Increasing $j$'s consideration probability makes it more likely we observe the consideration set with $j$, which then makes it less likely we see $i$ ranked first. However, this pairing fails if the first set in the pair has size $k$, since then its partner without $j$ is infeasible. (ref) allows us to bound the error introduced by these failed pairings. On the other hand, if $k+1$ consideration probabilities are 1, then we never see the problematic size-$k$ consideration sets.
Finally, using (ref), we can upper bound $p_i$ by comparing how often $i$ is ranked first under the PL+C model to how often we would expect it to be ranked first if all other consideration probabilities were 1, which is easy to compute as a function of $p_i$.
Just as we did with lower bounds, we can use (ref) to find initial upper bounds on every $p_i$ and then use (ref) to tighten these bounds, this time using the upper bound formulation (ref). The algorithm is identical in structure to the lower-bounding procedure; see (ref) for pseudocode and a proof of correctness.
To illustrate how our theoretical machinery can be used to infer consideration behavior, we analyze an existing dataset in which $\mathop{\approx} 2900$ American participants in a psychology experiment were asked to compare contributions of the 50 U.S. states to U.S. history putnam2018collective. The data\footnote{Made available by putnam2018collective at \url{https://osf.io/tnjqs/} under a CC-BY 4.0 license.} include their responses to numerical questions (the Random-10 question: estimate the percentage of state $X$'s contribution to U.S. history, for each state $X$ in a set of ten randomly selected states) and ranking questions (the Top-3 question: identify, in order, the three states that contributed the most to U.S. history). For Random-10, we convert the numerical ratings into rankings by sorting. Since the set of states being considered is fixed by the Random-10 question itself, we model these rankings using Plackett--Luce without consideration (PL). However, the Top-3 question forces participants to construct their responses without a reference list of candidates, instead having to recall the names of the states that they will list brown1976recall; indeed, participants are unlikely to have considered all 50 states, making the Top-3 setting well suited to PL+C.
According to (ref), we cannot hope to learn consideration probabilities for the 50 U.S. states. However, (ref) (and its upper-bound analog; see (ref) in (ref)) enables us to at least infer bounds on these consideration probabilities given estimates of top-$\ell$ appearance rates ${\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(\mathcal R_{i \le \ell})$, utilities $u_i$, and a lower bound on expected consideration set size $\alpha k$. Because the Top-3 and Random-10 data feature rankings over the same universe of items (the states), if we model these responses with PL+C and PL, respectively, then it is natural to assume that the underlying utilities are the same between the two questions. Working from this assumption, we fit\footnote{We used Rprop riedmiller1993direct on the full dataset with initial learning rate 0.05 and $L_2$ regularization strength $10^{-6}$, stopping when the squared gradient magnitude fell below $10^{-8}$. Since the PL model has a convex negative log likelihood, any well-tuned or robust optimizer would be expected to converge to a global optimum. While we used a train-test split for initial exploration, the results presented here are from the model fit to the entire dataset, as we do not have meaningful test metrics to evaluate. Given our assumptions, our bounds provably hold. Training takes less than a second on a 2018 MacBook Pro. Our code is available at \url{https://github.com/aoki-sherwoodb/bounding-consideration-probs}.} a PL model (implemented in PyTorch paszke2019pytorch) to the Random-10 data, learning the utility $u_i$ for each state and taking these to be the utilities under the full PL+C model for Top-3. For each state $i$, we then calculate the empirical estimates of ${\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(\mathcal R_{i \le \ell})$ for $\ell = 1, 2, 3$: the proportion of the Top-3 rankings in which state $i$ appears in the first $\ell$ positions. Finally, we take $\alpha = 5$, assuming that participants on average consider at least $15$ states when ranking their top $3$.
Recall that (ref) (and, similarly, (ref)) relies on pairs of states whose utilities and top-$\ell$ ranking rates are flipped.\footnote{To identify these flips, we use utilities learned from Random-10 data rather than (ref), avoiding high sampling error on states that rarely appear in the Top-3.} There are many such flips in this data, highlighting the importance of consideration in the Top-3 question. We visualize these flips in (ref) (left), which shows the directed acyclic graph $G$ constructed in (ref). (For clarity, we display the transitive reduction aho1972transitive of $G$.) For each edge $\tup{i, j}$ in this graph, we know that state $i$ has a lower consideration probability than state $j$, despite having higher utility. For instance, we find that Massachusetts has higher consideration probability than Virginia, which in turn has higher consideration probability than New York and Pennsylvania.
We also compute upper bounds on consideration probabilities using (ref), with the same utilities $u_i$, values of $\alpha$ and $k$, and top-1 ranking probabilities ${\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(\mathcal R_{i = 1})$ (again, using empirical estimates). Combining our lower and upper bounds yields feasible intervals on consideration probabilities for each state, which we display in (ref) (right). Our upper bounds reveal that, if our assumptions are valid, most states are considered less than 30--40% of the time. Additionally, the bounds on consideration probabilities align with theories about why certain states were highly rated in the data putnam2018collective. Of the eight states with the highest lower bound, five are states drawn from the thirteen original colonies and commonly associated with the American Revolution (Massachusetts, Virginia, New York, Pennsylvania, and Delaware), two are the largest U.S.\ states by population (California and Texas), and the last, Washington, was hypothesized by putnam2018collective to be confused by participants with the U.S.\ capital city Washington, D.C.\ and may also be easy to recall in the context of historical judgements due to its namesake.
We formalized a natural model of ranking with consideration, adding independent consideration to Plackett--Luce. Despite showing that consideration probabilities are not identified in general, we derived relative and absolute bounds that allow us to learn about possible ranges of consideration probabilities from observed ranking data. Our data application demonstrates how these bounds can be used in practice to gain insight into consideration behavior. In addition to providing behavioral insights, approximately recovering consideration probabilities has exciting possible applications in recommender systems, which could be tailored to suggest items that have high utility but low consideration probability.
The astute reader will notice that our bounds use exact top-$\ell$ ranking probabilities and utilities, but that empirical estimates from observed rankings are necessarily noisy (and may reverse whether $u_i > u_j$ or $u_i < u_j$). Luckily, there are some easy fixes. For (ref), we can use upper and lower confidence intervals on top-$\ell$ ranking rates to compute a range of possible values of $c$ (and, in particular, a high-probability guarantee under sampling error). To handle uncertainty in utility estimates, we can use confidence intervals to find only statistically significant utility-consideration flips.
There remains much to explore regarding the PL+C model, and ranking with consideration sets more generally. While PL+C is clearly at least as powerful as Plackett--Luce, how much expressive power is gained by adding consideration? What kinds of distributions over rankings can and cannot be expressed by a PL+C model? Another natural extension of the Plackett--Luce model allows violations of the independence of irrelevant alternatives (IIA) assumption built into Plackett--Luce, such as the contextual repeated selection (CRS) model seshadri2020learning. How does the expressive power of CRS compare to PL+C? Does PL+C allow (apparent) IIA violations due to the consideration stage? (We expect so; the three-item example in (ref) is reminiscent of non-IIA behavior.)
Another interesting question concerns computing PL+C probabilities efficiently. If we know utilities and consideration probabilities, the direct approach to computing ${\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(r)$ using (ref) involves a sum over exponentially many consideration sets. Is it possible to exactly compute PL+C probabilities in polynomial time, or is it provably hard? We have derived two efficient approximation algorithms, but not a hardness proof or exact efficient algorithm. The first algorithm samples sufficiently many consideration sets and computes an empirical estimate of ${\textstyle \Pr_{\textup{\textsc{\scriptsize PL+C}}}}(r)$, while the second groups together consideration sets with similar total utilities (with “similarity” defined by a tolerance $\epsilon$), computes their total consideration probabilities, and approximates their total utilities. Details of the algorithms are in (ref); we leave further exploration of this problem to future work.
The PL+C model also admits several natural extensions, such as incorporating different models of the consideration stage or allowing rankings of varied length. The latter direction may even simplify some of the consideration probability bounds, as some of the difficulty in our top-$k$ setting arises because of the conditioning that $|C| \ge k$ (but this conditioning is often needed given the ubiquity of top-$k$ data).
Portions of this work were carried out while all authors were at Carleton College and while K.T. was at Cornell University. Thanks to Aadi Akyianu, David Chu, Katrina Li, Adam Putnam, Sophie Quinn, Morgan Ross, Laura Soter, and Jeremy Yamashiro for helpful discussions. Comments are welcome.