Publications

Choice-based demand models serve as building blocks for making demand predictions, which are key inputs to critical operational decisions, such as what prices to charge for different products or which subset of products to offer to the customers. Traditionally, parametric choice models (such as the multinomial logit model) have been employed for tractability reasons, but with the increasing ability of firms to collect large volumes of sales transaction and product availability data, nonparametric choice models have been gaining in popularity. We review recent advances in nonparametric estimation of two versatile choice model families.

We describe an efficient estimation method for large-scale tree logit models, using a novel change-of-variables transformation that allows us to express the negative log-likelihood as a strictly convex function in the leaf node parameters and a difference of strictly convex functions in the non-leaf node parameters. Exploiting this representation, we design a fast iterative method that computes a sequence of parameter estimates using simple closed-form updates. Our algorithm relies only on first-order information (function and gradients values), but unlike other first-order methods, it does not require any step size tuning or costly projection steps. The sequence of parameter estimates yields increasing likelihood values, and we establish sublinear convergence to a stationary point of the maximum likelihood problem. Numerical results on both synthetic and real data show that our algorithm outperforms state-of-the-art optimization methods, especially for large-scale tree logit models with thousands of nodes.

We report experimental and quasi-experimental evidence from a "sharing economy" marketplace that transitioned from decentralized to centralized pricing. Centralized pricing increased the utilization of providers' assets, resulting in higher revenues but also higher transaction costs. Providers who were barred from accessing the price system made non-price adjustments, including reducing the availability of their assets, canceling booked transactions, and exiting the market. Providers who retained partial pricing control reacted substantially less but experienced similar revenue increases. We highlight the challenges of implementing centralized pricing and assessing its welfare effects show that partial control can mitigate these challenges, allowing providers to express their private and heterogeneous preferences while maintaining the benefits of centralization.

We propose a back-to-back procedure for running personalized promotions in retail operations contexts, from the construction of a nonparametric choice model where customer preferences are represented by directed acyclic graphs (DAGs) to the design of such promotions. The source data includes a history of purchases tagged by customer id, and product availability and promotion data for a category of products. In each customer DAG nodes represent products and directed edges represent the relative preference order between two products. Upon arrival to the store, a customer samples a full ranking of products within the category consistent with her DAG, and purchases the most preferred option among the available ones. We describe the DAG construction process and explain how to mount a parametric, multinomial logit model (MNL) over it. We provide new bounds for the likelihood of a DAG and show how to conduct the MNL estimation. We test our model to predict purchases at the individual level on real retail data and verify that it outperforms state-of-the-art benchmarks. Finally, we illustrate how to use it to run personalized promotions. Our framework leads to significant revenue gains over the sample data that make it an attractive candidate to be tested in practice.

To estimate customer demand, choice models rely both on what the individuals do and do not purchase. A customer may not purchase a product because it was not offered, but also because it was not considered. To account for this behavior, existing literature has proposed the so-called consider-then-choose (CTC) models, which posit that customers sample a consideration set and then choose the most preferred product from the intersection of the offer set and the consideration set. CTC models have been studied quite extensively in the marketing literature. More recently, they have gained popularity within the Operations Management literature to make assortment and pricing decisions. Despite their richness, CTC models are difficult to estimate in practice because firms do not observe customers' consideration sets. Therefore, the common assumption in operations has been that customers consider everything on offer, so the offer set is the same as the consideration set. This raises the following question: when firms only collect transaction data, do CTC models offer any predictive advantage over the classic choice models? More precisely, under what conditions do CTC models outperform (if ever) classic choice models in terms of prediction accuracy?

In this work, we study a general class of CTC models. We propose techniques to estimate these models efficiently from sales transaction data. We then compare their performance against the classic approach. We find that CTC models outperform standard choice models when there is noise in the offer set information and the noise is asymmetric across the training and test offer sets, but otherwise offer no particular predictive advantage over the classic approach. We demonstrate the benefits of using the CTC models in real-world retail and online platform settings. In particular, we show that CTC models calibrated on transaction data are better at long-term and warehouse level sales forecasts. We also find that offer sets are difficult to accurately define in online platform settings because customers usually only consider a small subset of all the available listings in the platform. In fact, CTC models significantly outperform standard choice models in online platform settings.

Assortment optimization is an important problem arising in many applications, including retailing and online advertising. The goal in such problems is to determine a revenue-/profit-maximizing subset of products to offer from a large universe of products when customers exhibit stochastic substitution behavior. We consider a mixture of Mallows model for demand, which can be viewed as a “smoothed” generalization of sparse, rank-based choice models, designed to overcome some of their key limitations. In spite of these advantages, the Mallows distribution has an exponential support size and does not admit a closed-form expression for choice probabilities. We first conduct a case study using a publicly available data set involving real-world preferences on sushi types to show that Mallows-based smoothing significantly improves both the prediction accuracy and the decision quality on this data set. We then present an efficient procedure to compute the choice probabilities for any assortment under the mixture of Mallows model. Sur- prisingly, this finding allows us to formulate a compact mixed integer program (MIP) that leads to a practical approach for solving the assortment-optimization problem under a mixture of Mallows model. To complement this MIP formulation, we exploit additional structural properties of the underlying distribution to propose several polynomial-time approximation schemes (PTAS), taking the form of a quasi-PTAS in the most general setting, which can be strengthened to a PTAS or a fully PTAS under stronger assumptions. These are the first algorithmic approaches with provably near-optimal performance guarantees for the assortment-optimization problem under the Mallows or the mixture of Mallows model in such generality.

Mixture models are versatile tools that are used extensively in many fields, including operations, marketing, and econometrics. The main challenge in estimating mixture models is that the mixing distribution is often unknown, and imposing a priori parametric assumptions can lead to model misspecification issues. In this paper, we propose a new methodology for non- parametric estimation of the mixing distribution of a mixture of logit models. We formulate the likelihood-based estimation problem as a constrained convex program and apply the conditional gradient (also known as Frank–Wolfe) algorithm to solve this convex program. We show that our method iteratively generates the support of the mixing distribution and the mixing proportions. Theoretically, we establish the sublinear convergence rate of our estimator and characterize the structure of the recovered mixing distribution. Empirically, we test our approach on real- world datasets. We show that it outperforms the standard expectation-maximization (EM) benchmark on speed (16 times faster), in-sample fit (up to 24% reduction in the log-likelihood loss), and predictive (average 28% reduction in standard error metrics) and decision ac- curacies (extracts around 23% more revenue). On synthetic data, we show that our estimator is robust to different ground-truth mixing distributions and can also account for endogeneity.

Probability distributions over rankings are crucial for the modeling and design of a wide-range of practical systems. In this work, we pursue a nonparametric approach that seeks to learn a distribution over rankings (aka the ranking model) that is consistent with the observed data and has the sparsest possible support (i.e., the smallest number of rankings with non-zero probability mass). We focus on first-order marginal data, which comprise information on the probability that item i is ranked at position j, for all possible item and position pairs. The observed data may be noisy. Finding the sparsest approximation requires brute force search in the worst case. To address this issue, we restrict our search to, what we dub, the signature family, and show that the sparsest model within the signature family can be found computationally efficiently compared to the brute force approach. We then establish that the signature family provides good approximations to popular ranking model classes, such as the multinomial logit and the exponential family classes, with support size that is small relative to the dimension of the observed data. We test our methods on two datasets: the ranked election dataset from the American Psychological Association (APA) and the preference ordering data on 10 different sushi varieties.

We report on a randomized trial conducted during a market design transition on a sharing economy platform, where providers who formerly set rental prices for their assets were randomly assigned to groups with varying levels of pricing control. Even when faced with the prospect of significantly higher revenues, providers retaliate against the centralization of pricing by exiting the platform, reducing asset availability and cancelling transactions. Allowing providers to retain partial control lowers retaliation substantially even though providers do not frequently utilize this additional flexibility. We discuss information asymmetry, divergent incentives, and psychological contract violation as alternative explanations for our results.

Customer preferences may not be rational, so we focus on quantifying the limit of rationality (LoR) in choice modeling applications. We define LoR as the cost of approximating the observed choice fractions from a collection of offer sets with those from the best-fitting probability distribution over rankings. Computing LoR is intractable in the worst case. To deal with this challenge, we introduce two new concepts, rational separation and choice graph, through which we reduce the problem to solving a dynamic program on the choice graph and express the computational complexity in terms of the structural properties of the graph. By exploiting the graph structure, we provide practical methods to compute LoR efficiently for a large class of applications. We apply our methods to real- world grocery sales data and identify product categories for which going beyond rational choice models is necessary to obtain an acceptable performance.

Despite the growth of online retail, the majority of products are still sold offline, and the “touch-and-feel” aspect of physically examining a product before purchase remains important to many consumers. In this paper, we demonstrate that large discrepancies can exist between how consumers evaluate products when examining them “live” versus based on online descriptions, even for a relatively familiar product (messenger bags) and for utilitarian features. Therefore, the use of online evaluations in market research may result in inaccurate predictions and potentially suboptimal decisions by the firm. Because eliciting preferences by conducting large-scale offline market research is costly, we propose fusing data from a large online study with data from a smaller set of participants who complete both an online and an offline study. We demonstrate our approach using conjoint studies on two sets of participants. The group who completed both online and offline studies allows us to calibrate the relationship between online and offline partworths. To obtain reliable parameter estimates, we propose two statistical methods: a hierarchical Bayesian approach and a k-nearest-neighbors approach. We demonstrate that the proposed approach achieves better out-of-sample predictive performance on individual choices (up to 25% improvement), as well as aggregate market shares (up to 33% improvement).

We consider the problem of segmenting a large population of customers into non-overlapping groups with similar preferences, using diverse preference observations such as purchases, ratings, clicks, and so forth, over subsets of items. We focus on the setting where the universe of items is large (ranging from thousands to millions) and unstructured (lacking well-defined attributes) and each customer provides observations for only a few items. These data characteristics limit the applicability of existing techniques in marketing and machine learning. To overcome these limitations, we propose a model-based embedding technique, which takes the customer observations and a probabilistic model class generating the observations as inputs, and outputs an embedding (a low-dimensional vector representation in Euclidean space) for each customer. We then cluster the embeddings to obtain the segments. Theoretically, we derive precise necessary and sufficient conditions that guarantee asymptotic recovery of the true segments under a standard latent class setup. Empirically, we demonstrate the speed and performance of our method in two real-world case studies: (a) up to 84% improvement in accuracy of new movie recommendations on the MovieLens data set and (b) up to 8% improvement in the performance of similar product recommendations algorithm on an offline data set at eBay. We show that our method outperforms standard latent class, empirical Bayesian, and demographic-based techniques.

Firms are increasingly selling through both offline and online channels, allowing customers to experience the touch and feel of product attributes before purchasing those products. Consequently, the selection of products offered offline affects the demand in both channels. We address how firms should select an optimal offline assortment to maximize profits across both channels; we call this the showcase decision problem. We incorporate the impact of physical evaluation on preferences into the consumer demand model. Under this model, we show that the decision problem is NP-hard. Analytically, we derive optimal results for special cases and near-optimal approximations for general cases. Empirically, we use conjoint analysis to identify changes in consumer preferences resulting from physically evaluating products. For this application, we demonstrate gains in expected revenue of up to 40% due to accounting for the impact of offline assortment on the online sales.

In retail operations, customer choices may be affected by stockout and promotion events. Given panel data with the transaction history of customers, and product availability and promotion data, our goal is to predict future individual purchases. We use a general nonparametric framework in which we represent customers by partial orders of preferences. In each store visit, each customer samples a full preference list of the products consistent with her partial order, forms a consideration set, and then chooses to purchase the most preferred product among the considered ones. Our approach involves: (a) defining behavioral models to build consideration sets as subsets of the products on offer, (b) proposing a clustering algorithm for determining customer segments, and (c) deriving marginal distributions for partial preferences under the multinomial logit model. Numerical experiments on real-world panel data show that our approach allows more accurate, fine-grained predictions for individual purchase behavior compared to state-of-the-art alternative methods.

We consider the problem of "hyper-localizing" product assortments at a fashion retailer — that is, customizing the offerings to the particular preferences of customers visiting the store, so that customers can easily find the products that fit their tastes and purchase more. To make this decision, the firm must accurately predict the demand for each style at each store — a challenging task because of large variety and the small number of purchases per customer. To address this challenge, we propose: (a) a nonparametric choice modeling technique that uses purchase transactions tagged by customer IDs to build distributions over preference lists of products that are personalized to each customer and (b) an optimization framework that uses the predictions from our choice models to optimally allocate merchandise to different stores subject to inventory and dollar budget constraints. We implemented our methods at a large US fashion retailer with about $3B in annual revenue and approximately 300 stores. In a controlled experiment, our methods resulted in additional 7% revenue growth (approx. $200M profit impact) over the current method. We present the implementation details and the specific challenges (both technical and managerial) posed for assortment planning by fashion retail and the ways we addressed them.

We study the problem of identifying unreliable and adversarial workers in crowdsourcing systems where workers (or users) provide labels for tasks (or items). Most existing studies assume that worker responses follow specic probabilistic models; however, recent evidence shows the presence of workers adopting non-random or even malicious strategies. To account for such workers, we suppose that workers comprise a mixture of honest and adversarial workers. Honest workers may be reliable or unreliable, and they provide labels according to an unknown but explicit probabilistic model. Adversaries adopt labeling strategies different from those of honest workers, whether probabilistic or not. We propose two reputation algorithms to identify unreliable honest workers and adversarial workers from only their responses. Our algorithms assume that honest workers are in the majority, and they classify workers with outlier label patterns as adversaries. Theoretically, we show that our algorithms successfully identify unreliable honest workers, workers adopting deterministic strategies, and worst-case sophisticated adversaries who can adopt arbitrary labeling strategies to degrade the accuracy of the inferred task labels. Empirically, we show that ltering out outliers using our algorithms can signicantly improve the accuracy of several state-of-the-art label aggregation algorithms in real-world crowdsourcing datasets.

The selection of products and prices offered by a firm significantly impacts its profits. Existing approaches do not provide flexible models that capture the joint effect of assortment and price. We propose a nonparametric framework in which each customer is represented by a particular price threshold and a particular preference list over the alternatives. The customers follow a two-stage choice process; they consider the set of products with prices less than the threshold and choose the most preferred product from the set considered. We develop a tractable nonparametric expectation maximization (EM) algorithm to fit the model to the aggregate transaction data and design an efficient algorithm to determine the profit-maximizing combination of offer set and price. We also identify classes of pricing structures of increasing complexity, which determine the computational complexity of the estimation and decision problems. Our pricing structures are naturally expressed as business constraints, allowing a manager to trade off pricing flexibility with computational burden.

Lack of quality textbooks and good educational resources is a well- known problem in developing regions. In this paper, we describe the design of CollectiveTeach, a web platform that aims to integrate rich educational content into an inquiry-based framework, viz. the 5E learning model, for generating web-annotated lesson plans for school and college teachers in developing countries. Given the wealth of educational resources on the Web, CollectiveTeach helps teachers to author new lesson plans through a simple web interface allowing them to easily search, select, order and collect educational content relevant to the topics they wish to teach. This paper describes our experiences building two versions of the CollectiveTeach platform. The initial platform was tested via a user study with a cohort of 19 teachers in Ghana and the learnings of this user study were incorporated in a second, improved version of CollectiveTeach; the current prototype of CollectiveTeach was evaluated using human experts for computer science subjects covered in standard undergraduate curriculum.

We consider the assortment optimization problem when customer preferences follow a mixture of Mallows distributions. The assortment optimization problem focuses on determining the revenue/profit maximizing subset of products from a large universe of products; it is an important decision that is commonly faced by retailers in determining what to offer their customers. There are two key challenges: (a) the Mallows distribution lacks a closed-form expression (and requires summing an exponential number of terms) to compute the choice probability and, hence, the expected revenue/profit per customer; and (b) finding the best subset may require an exhaustive search. Our key contributions are an efficiently computable closed-form expression for the choice probability under the Mallows model and a compact mixed integer linear program (MIP) formulation for the assortment problem.

Many socio-economic indicators are sensitive to real-world events. Proper characterization of the events can help to identify the relevant events that drive fluctuations in these indicators. In this paper, we propose a novel generative model of real-world events and em- ploy it to extract events from a large corpus of news articles. We introduce the notion of an event class, which is an abstract grouping of similarly themed events. These event classes are manifested in news articles in the form of event triggers which are specific words that describe the actions or incidents reported in any article. We use the extracted events to predict fluctuations in different socio- economic indicators. Specifically, we focus on food prices and predict the price of 12 different crops based on real-world events that potentially influence food price volatility, such as transport strikes, festivals etc. Our experiments demonstrate that incorporating event information in the prediction tasks reduces the root mean square error (RMSE) of prediction by 22% compared to the standard ARIMA model. We also predict sudden increases in the food prices (i.e. spikes) using events as features, and achieve an average 5-10% increase in accuracy compared to baseline models, including an LDA topic-model based predictive model.

A system and method for providing a personalized recommendation from a series of partial preferences is presented. A preference distribution of a population including a plurality of weighted ranked lists is identified. A revealed preference of a user is compared to the plurality of ranked lists. An affinity weight between the user and each of the plurality of ranked lists is assigned, and a weighted average of each of the affinity weights is taken.

A system and method for determining a rank aggregation from a series of partial preferences is presented. A distribution is learned over preferences from partial preferences with sparse support. A computer receives a plurality of partial preferences selected from two or more preference lists. Weights are assigned to each of said plurality of partial preferences, resulting in multiple ranked lists.

A set of queries, such as a search log, is divided into commercial queries and non-commercial queries. A first set of query communities is determined from the non-commercial queries and a second set is determined from the commercial queries. The query communities are correlated based on the users who submitted the queries and instances where a query from the first set of query communities was followed by a query from the second set to generate a mapping between the first set of query communities and the second set. Later, a non-commercial query is received from a user, and the mapping is used to predict one or more commercial queries that the user is likely to submit in the future based on the non-commercial query. One or more of the commercial queries are presented to the user according to the mapping with search results responsive to the non-commercial query.

In this paper, we study the problem of aggregating noisy labels from crowd workers to infer the underlying true labels of binary tasks. Unlike most prior work which has examined this problem under the random worker paradigm, we consider a much broader class of adversarial workers with no specific assumptions on their labeling strategy. Our key contribution is the design of a computationally efficient reputation algorithm to identify and filter out these adversarial workers in crowd-sourcing systems. Our algorithm uses the concept of optimal semi-matchings in conjunction with worker penalties based on label disagreements, to assign a reputation score for every worker. We provide strong theoretical guarantees for deterministic adversarial strategies as well as the extreme case of sophisticated adversaries where we analyze the worst-case behavior of our algorithm. Finally, we show that our reputation algorithm can significantly improve the accuracy of existing label aggregation algorithms in real-world crowdsourcing datasets.

We consider the key operational problem of optimizing the mix of offered products to maximize revenues when product prices are exogenously set and product demand follows a general discrete choice model. The key challenge in making this decision is the computational difficulty of finding the best subset, which often requires exhaustive search. Existing approaches address the challenge by either deriving efficient algorithms for specific parametric structures or studying the performance of general-purpose heuristics. The former approach results in algorithms that lack portability to other structures; whereas the latter approach has resulted in algorithms with poor performance. We study a portable and easy-to-implement local search heuristic. We show that it efficiently finds the global optimum for the multinomial logit (MNL) model and derive performance guarantees for general choice structures. Empirically, it is better than prevailing heuristics when no efficient algorithms exist, and it is within 0.02% of optimality otherwise.

Choice models today are ubiquitous across a range of applications in operations and marketing. Real-world implementations of many of these models face the formidable stumbling block of simply identifying the “right” model of choice to use. Because models of choice are inherently high-dimensional objects, the typical approach to dealing with this problem is positing, a priori, a parametric model that one believes adequately captures choice behavior. This approach can be substantially suboptimal in scenarios where one cares about using the choice model learned to make fine-grained predictions; one must contend with the risks of mis-specification and overfitting/underfitting. Thus motivated, we visit the following problem: For a “generic” model of consumer choice (namely, distributions over preference lists) and a limited amount of data on how consumers actually make decisions (such as marginal information about these distributions), how may one predict revenues from offering a particular assortment of choices? An outcome of our investigation is a nonparametric approach in which the data automatically select the right choice model for revenue predictions. The approach is practical. Using a data set consisting of automobile sales transaction data from a major U.S. automaker, our method demonstrates a 20% improvement in prediction accuracy over state-of-the-art benchmark models; this improvement can translate into a 10% increase in revenues from optimizing the offer set. We also address a number of theoretical issues, among them a qualitative examination of the choice models implicitly learned by the approach. We believe that this paper takes a step toward “automating” the crucial task of choice model selection.

We consider the problem of recovering a function over the space of permutations (or, the symmetric group) over n $n$ elements from given partial information; the partial information we consider is related to the group theoretic Fourier Transform of the function. This problem naturally arises in several settings such as ranked elections, multi-object tracking, ranking systems, and recommendation systems. Inspired by the work of Donoho and Stark in the context of discrete-time functions, we focus on non-negative functions with a sparse support (support size << domain size). Our recovery method is based on finding the sparsest solution (through $\ell_0$ 􏰹􏰽optimization) that is consistent with the available information. As the main result, we derive sufficient conditions for functions that can be recovered exactly from partial information through 􏰹􏰽$\ell_0$ optimization. Under a natural random model for the generation of functions, we quantify the recoverability conditions by deriving bounds on the sparsity (support size) for which the function satisfies the sufficient conditions with a high probability as $n \to \infty$􏰼. 􏰹􏰽 $\ell_0$ optimization is computationally hard. Therefore, the popular compressive sensing literature considers solving the convex relaxation, $\ell_1$ optimization, to find the sparsest solution. However, we show that 􏰹􏰼 optimization fails to recover a function (even with constant sparsity) generated using the random model with a high probability as $n \to \infty$􏰼. In order to overcome this problem, we propose a novel iterative algorithm for the recovery of functions that satisfy the sufficient conditions. Finally, using an Information Theoretic framework, we study necessary conditions for exact recovery to be possible.

With the recent explosion of choices available to us in every walk of our life, capturing the choice behavior exhibited by individuals has become increasingly important to many businesses. At the core, capturing choice behavior boils down to being able to predict the probability of choosing a particular alternative from an offer set, given historical choice data about an individual or a group of "similar" individuals. For such predictions, one uses what is called a choice model, which models each choice occasion as follows: given an offer set, a preference list over alternatives is sampled according to a certain distribution, and the individual chooses the most preferred alternative according to the sampled preference list. Most existing literature, which dates back to at least the 1920s, considers parametric approaches to choice modeling. The goal of this thesis is to deviate from the existing approaches to propose a nonparametric approach to modeling choice. Apart from the usual advantages, the primary strength of a nonparametric model is its ability to scale with the data - certainly crucial to applications of our interest where choice behavior is highly dynamic. Given this, the main contribution of the thesis is to operationalize the nonparametric approach and demonstrate its success in several important applications. Specifically, we consider two broad setups: (1) solving decision problems using choice models, and (2) learning the choice models. In both setups, data available corresponds to marginal information about the underlying distribution over rankings. So the problems essentially boil down to designing the 'right' criterion to pick a model from one of the (several) distributions that are consistent with the available marginal information. First, we consider a central decision problem in operations management (OM): find an assortment of products that maximizes the revenues subject to a capacity constraint on the size of the assortment. Solving this problem requires two components: (a) predicting revenues for assortments and (b) searching over all subsets of a certain size for the optimal assortment. In order to predict revenues for an assortment, of all models consistent with the data, we use the choice model that results in the 'worst-case' revenue. We derive theoretical guarantees for the predictions, and show that the accuracy of predictions is good for the cases when the choice data comes from several different parametric models. Finally, by applying our approach to real-world sales transaction data from a major US automaker, we demonstrate an improvement in accuracy of around 20% over state-of-the-art parametric approaches. Once we have revenue predictions, we consider the problem of finding the optimal assortment. It has been shown that this problem is provably hard for most of the important families of parametric of choice models, except the multinomial logit (MNL) model. In addition, most of the approximation schemes proposed in the literature are tailored to a specific parametric structure. We deviate from this and propose a general algorithm to find the optimal assortment assuming access to only a subroutine that gives revenue predictions; this means that the algorithm can be applied with any choice model. We prove that when the underlying choice model is the MNL model, our algorithm can find the optimal assortment efficiently. Next, we consider the problem of learning the underlying distribution from the given marginal information. For that, of all the models consistent with the data, we propose to select the sparsest or simplest model, where we measure sparsity as the support size of the distribution. Finding the sparsest distribution is hard in general, so we restrict our search to what we call the 'signature family' to obtain an algorithm that is computationally efficient compared to the brute-force approach. We show that the price one pays for restricting the search to the signature family is minimal by establishing that for a large class of models, there exists a "sparse enough" model in the signature family that fits the given marginal information well. We demonstrate the efficacy of learning sparse models on the well-known American Psychological Association (APA) dataset by showing that our sparse approximation manages to capture useful structural properties of the underlying model. Finally, our results suggest that signature condition can be considered an alternative to the recently popularized Restricted Null Space condition for efficient recovery of sparse models.

We consider the problem of designing a fair scheduling algorithm for discrete-time constrained queuing networks. Each queue has dedicated exogenous packet arrivals. There are constraints on which queues can be served simultaneously. This model effectively describes important special instances like network switches, interference in wireless networks, bandwidth sharing for congestion control and traffic scheduling in road roundabouts. Fair scheduling is required because it provides isolation to different traffic flows; isolation makes the system more robust and enables providing quality of service. Existing work on fairness for constrained networks concentrates on flow based fairness. As a main result, we describe a notion of packet based fairness by establishing an analogy with the ranked election problem: packets are voters, schedules are candidates, and each packet ranks the schedules based on its priorities. We then obtain a scheduling algorithm that achieves the described notion of fairness by drawing upon the seminal work of Goodman and Markowitz (1952). This yields the familiar Maximum Weight (MW) style algorithm. As another important result, we prove that the algorithm obtained is throughput optimal. There is no reason a priori why this should be true, and the proof requires nontraditional methods.

Recommendation engines today suggest one product to another, e.g., an accessory to a product. However, intent to buy often precedes a user’s appearance in a commerce vertical: someone interested in buying a skateboard may have earlier searched for {varial heelflip}, a trick performed on a skateboard. This paper considers how a search engine can provide early warning of commercial intent. The naive algorithm of counting how often an interest precedes a commercial query is not sufficient due to the number of related ways of expressing an interest. Thus, methods are needed for finding sets of queries where all pairs are related, what we call a query community, and this is the technical contribution of the paper. We describe a random model by which we obtain relationships between search queries and then prove general conditions under which we can reconstruct query communities. We propose two complementary approaches for inferring recommendations that utilize query communities in order to magnify the recommendation signal beyond what an individual query can provide. An extensive series of experiments on real search logs shows that the query communities found by our algorithm are more interesting and unexpected than a baseline of clustering the query-click graph. Also, whereas existing query suggestion algorithms are not designed for making commercial recommendations, we show that our algorithms do succeed in forecasting commercial intent. Query communities increase both the quantity and quality of recommendations.

The interest is in recovering distribution over the space of permutations over n elements given partial information. Non-trivial sufficient conditions for this question were introduced by Jagabathula and Shah (2008). This note states an unresolved question (see Conjecture 3.1) pertaining necessary conditions.

We visit the following fundamental problem: For a ‘generic’ model of consumer choice (namely, distributions over preference lists) and a limited amount of data on how consumers actually make decisions (such as marginal preference information), how may one predict revenues from offering a particular assortment of choices? This problem is central to areas within operations research, marketing and econometrics. We present a framework to answer such questions and design a number of tractable algorithms (from a data and computational standpoint) for the same.

We consider the problem of exact recovery of a function, defined on the space of permutations (or, the symmetric group) over n elements, from a given partial set of its Fourier series coefficients; we focus on non-negative functions. As the main result, we derive sufficient conditions not only in terms of the structural properties of the functions, but also in terms of a bound on the sparsity of the functions that can be recovered. We also propose an algorithm for recovery and prove that it finds the function with the sparsest support, which could be obtained through $\ell_0$ optimization. We also show that $\ell_1$ optimization, however, fails to recover the function.

Motivated by applications like elections, web-page ranking, revenue maximization etc., we consider the question of inferring popular rankings using constrained data. More specifically, we consider the problem of inferring a probability distribution over the group of permutations using its first order marginals. We first prove that it is not possible to recover more than O(n) permutations over n elements with the given information. We then provide a simple and novel algorithm that can recover up to O(n) permutations under a natural stochastic model; in this sense, the algorithm is optimal. In certain applications, the interest is in recovering only the most popular (or mode) ranking. As a second result, we provide an algorithm based on the Fourier Transform over the symmetric group to recover the mode under a natural majority condition; the algorithm turns out to be a maximum weight matching on an appropriately defined weighted bipartite graph. The questions considered are also thematically related to Fourier Transforms over the symmetric group and the currently popular topic of compressed sensing.

We consider the problem of designing scheduling schemes for networks with arbitrary topology and scheduling constraints. We address the optimality of scheduling schemes for packet networks in terms of throughput, delay and fairness. Specifically, we design two scheduling schemes. The first one achieves simultaneous throughput and delay optimization. The second scheme provides fairness. We design a scheduling scheme that guarantees a per-flow average delay bound of O(# of hops), with a constant factor loss of throughput. We derive the constants for a network operating under primary interference constraints. Our scheme guarantees an average delay bound of $1-\rho_j$ , where $d_j$ is the number of hops and $\rho_j$ is the effective loading along flow j. This delay guarantee comes at a factor 5 loss of throughput. We also provide a counter-example to prove the essential optimality of our result. For the fair scheduling scheme, we define a packet-based notion of fairness by establishing a novel analogy with the ranked election problem. The election scheme of Goodman and Markowitz (1952) yields a maximum weight style scheduling algorithm. We then prove the throughput optimality of the scheme for a single-hop network. Standard methods for proving the stability of queuing systems fail us and hence we introduce a non-standard proof technique with potential wider applications.

We consider the problem of designing an online scheduling scheme for a multi-hop wireless packet network with arbitrary topology and operating under arbitrary scheduling constraints. The objective is to design a scheme that achieves high throughput and low delay simultaneously. We propose a scheduling scheme that, for networks operating under primary interference constraints, guarantees a per-flow end-to-end packet delay bound of $5d_j/(1−\rho_j)$, at a factor 5 loss of throughput, where $d_j$ is the path length (number of hops) of flow j and $\rho_j$ is the effective loading along the route of flow j. Clearly, $d_j$ is a universal lower bound on end-to-end packet delay for flow j. Thus, our result is essentially optimal. To the best of our knowledge, our result is the first one to show that it is possible to achieve a per-flow end-to-end delay bound of O(# of hops) in a constrained network. Designing such a scheme comprises two related subproblems: Global Scheduling and Local Scheduling. Global Scheduling involves determining the set of links that will be simultaneously active, without violating the scheduling constraints. While local scheduling involves determining the packets that will be transferred across active edges. We de- sign a local scheduling scheme by adapting the Preemptive Last-In-First-Out (PL) scheme, applied for quasi-reversible continuous time networks, to an unconstrained discrete-time network. A global scheduling scheme will be obtained by using stable marriage algorithms to emulate the unconstrained network with the constrained wireless network. Our scheme can be easily extended to a network operating under general scheduling constraints, such as secondary interference constraints, with the same delay bound and a loss of throughput that depends on scheduling constraints through an intriguing “sub-graph covering” property.

In this paper, we consider the problem of designing a scheduling algorithm for input queued switches, that is both fair as well as throughput optimal. Most of the existing literature on input-queued switch fairness criteria concentrates on flow-based fairness. Since a large fraction of network traffic is about “short-flows”, there is a need for packet-based fairness criterion. The significant body of literature developed over the past two decades for packet-based scheduling algorithms is primarily concerned with throughput and delay, but not fairness. One of the reasons for such a state of affairs is the lack of a proper definition for packet-based fairness. The difficulty in defining fair stems from the fact that any reasonable notion of fairness must combine the well-known notion of fairness for a single-queue with the scheduling constraint of an input queued switch in an appropriate manner. As one of the main results of this paper, we define a notion of packet-based fair scheduling by identifying it as the selection of a winner in the following ranked election: packets are voters; schedules are candidates and each packet ranks different schedules based on their priorities. Drawing upon the seminal work of Goodman and Markowitz (1952) on ranked elections, we obtain a unique characterization of the fair schedule. Another important contribution of this paper is proving that the thus obtained fair scheduling algorithm is throughput optimal. There is no a priori reason why this should be true, and we introduce some non-standard proof techniques to prove the result. Our results suggest a framework for defining fair scheduling algorithm for a constrained packet network; a non- standard method to prove throughput stability for algorithms, such as ours, that are not based on queue-sizes.

We consider the point-to-point link scheduling problem in Spatial Time Division Multiple Access (STDMA) wireless ad hoc networks, motivate the use of spatial reuse as performance metric and provide an explicit characterization of spatial reuse. We assume uniform transmission power at all nodes and propose an algorithm based on a graph model of the network as well as Signal to Interference and Noise Ratio (SINR) computations. Our algorithm achieves higher spatial reuse than existing algorithms, without compromising on computational complexity.