Rank aggregation systems collect ordinal preferences from individuals to produce a global ranking that represents the social preference. Rank-breaking is a common practice to reduce the computational complexity of learning the global ranking. The individual preferences are broken into pairwise comparisons and applied to efficient algorithms tailored for independent paired comparisons. However, due to the ignored dependencies in the data, naive rank-breaking approaches can result in inconsistent estimates. The key idea to produce accurate and consistent estimates is to treat the pairwise comparisons unequally, depending on the topology of the collected data. In this paper, we provide the optimal rank-breaking estimator, which not only achieves consistency but also achieves the best error bound. This allows us to characterize the fundamental tradeoff between accuracy and complexity. Further, the analysis identifies how the accuracy depends on the spectral gap of a corresponding comparison graph.
In an orthogonal direction, new discrete choice models with sparse structures has been proposed recently in @cite_18 and optimization algorithms for revenue management has been proposed @cite_6 . In a similar direction, new discrete choice models based on Markov chains has been introduced in @cite_2 , and corresponding revenue management algorithms has been studied in @cite_51 . However, typically these models are analyzed in the asymptotic regime with infinite samples, with the exception of @cite_53 . A non-parametric choice models for pairwise comparisons also have been studied in @cite_50 @cite_34 . This provides an interesting opportunities to studying learning to rank for these new choice models.
@cite_18 @cite_53 @cite_6 @cite_50 @cite_2 @cite_34 @cite_51
2737040173 2098763115 1495768673 2962739555
We consider revenue management problems when customers choose among the offered products according to the Markov chain choice model. In this choice model, a customer arrives into the system to purchase a particular product. If this product is available for purchase, then the customer purchases it. Otherwise, the customer transitions to another product or to the no purchase option, until she reaches an available product or the no purchase option. We consider three classes of problems. First, we study assortment problems, where the goal is to find a set of products to offer to maximize the expected revenue obtained from each customer. We give a linear program to obtain the optimal solution. Second, we study single resource revenue management problems, where the goal is to adjust the set of offered products over a selling horizon when the sale of each product consumes the resource. We show how the optimal set of products to offer changes with the remaining resource inventory. Third, we study network revenue ... 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. This paper was accepted by Yossi Aviv, operations management. In this paper, we introduce a novel approach for reducing the k-item n-bidder auction with additive valuation to k-item 1-bidder auctions. This approach, called the Best-Guess reduction, can be applied to address several central questions in optimal revenue auction theory such as the relative strength of simple versus complex mechanisms, the power of randomization, and Bayesian versus dominant-strategy implementations. First, when the items have independent valuation distributions, we present a deterministic mechanism called Deterministic Best-Guess that yields at least a constant fraction of the optimal revenue by any randomized mechanism. This also gives the first simple mechanism that achieves constant fraction optimal revenue for such multi-buyer multi-item auctions. Second, if all the nk valuation random variables are independent, the optimal revenue achievable in dominant strategy incentive compatibility (DSIC) is shown to be at least a constant fraction of that achievable in Bayesian incentive compatibility (BIC). Third, when all the nk values are identically distributed according to a common one-dimensional distribution F, the optimal revenue is shown to be expressible in the closed form Θ(k(r + ∫0mr(1 − F(x)n)dx)) where r = supx≥0 x(1 − F(x)n) and m = lk nr; this revenue is achievable by a simple mechanism called 2nd-Price Bundling. All our results apply to arbitrary distributions, regular or irregular. In this work we derive fundamental limits for many linear and non-linear sparse signal processing models including group testing, quantized compressive sensing, multivariate regression and observations with missing features. In general, sparse signal processing problems can be characterized in terms of the following Markovian property. We are given a set of N variables X1, X2, ..., XN, and there is an unknown subset of variables S ⊂ 1, 2, ..., N that are relevant for predicting outcomes outputs Y. In other words, when Y is conditioned on Xn nϵS it is conditionally independent of the other variables, Xn n∉S. Our goal is to identify the set S from samples of the variables X and the associated outcomes Y. We characterize this problem as a version of the noisy channel coding problem. Using asymptotic information theoretic analyses, we establish mutual information formulas that provide sufficient and necessary conditions on the number of samples required to successfully recover the salient variables. These mutual information expressions unify conditions for both linear and non-linear observations. We then compute sample complexity bounds for the aforementioned models, based on the mutual information expressions.