We consider two variants of a pricing problem under the nested logit model. In the first variant, the set of products offered to customers is fixed, and we want to determine the prices of the products. In the second variant, we jointly determine the set of offered products and their corresponding prices. In both variants, the price of each product has to be chosen within given upper and lower bounds specific to the product, each customer chooses among the offered products according to the nested logit model, and the objective is to maximize the expected revenue from each customer. We give approximation methods for both variants. For any ρ > 0, our approximation methods obtain a solution with an expected revenue deviating from the optimal expected revenue by no more than a factor of 1 + ρ. To obtain such a solution, our approximation methods solve a linear program whose size grows at rate 1/ρ. In addition to our approximation methods, we develop a linear program that we can use to obtain an upper bound on the optimal expected revenue. In our computational experiments, we compare the expected revenues from the solutions obtained by our approximation methods with the upper bounds on the optimal expected revenues and show that we can obtain high-quality solutions quite fast.

In this paper, we study a class of stochastic optimization problems, where although the objective functions may not be convex, they satisfy a generalization of convexity called the sequentially convex property. We focus on a setting where the distribution of the underlying uncertainty is unknown and the manager must make a decision in real time based on historical data. Because sequentially convex functions are not necessarily convex, they pose difficulties in applying standard adaptive methods for convex optimization. We propose a nonparametric algorithm based on a gradient descent method and show that the T-season average expected cost differs from the minimum cost by at most [Formula: see text]. Our analysis is based on a careful quantification of the bias that is inherent in gradient estimation because of the adaptive nature of the problem. We demonstrate the usefulness of the concept of sequential convexity by applying it to three canonical problems in inventory control, capacity allocation, and the lifetime buy decision, under the assumption that the manager does not know the demand distributions and has access only to historical sales (censored demand) data.

Motivated by the availability of real-time data on customer characteristics, we consider the problem of personalizing the assortment of products to each arriving customer. For an arriving customer of type z, the company must decide, in real-time, on the assortment of products to offer. Given the offered assortment, the customers make choices on which products to buy, if any, according to a general choice model that is specific to each customer type. Our goal is to develop a revenue-maximizing policy that determines the assortment to offer to each arriving customer, taking into account the customer type and the current inventories.

Increases in online search activities have spurred the growth of search-based advertising services offered by search engines. These services enable companies to promote their products to consumers based on their search queries. In most search-based advertising services, a company sets a daily budget, selects a set of keywords, determines a bid price for each keyword, and designates an ad associated with each selected keyword. When a consumer searches for one of the selected keywords, search engines then display the ads associated with the highest bids for that keyword on the search result page. A company whose ad is displayed pays the search engine only when the consumer clicks on the ad. If the company's spending has exceeded its daily budget, however, its ads will not be displayed. With millions of available keywords and a highly uncertain clickthru rate associated with the ad for each keyword, identifying the most profitable set of keywords given the daily budget constraint becomes challenging for companies wishing to promote their goods and services via search-based advertising. Motivated by these challenges, we formulate a model of keyword selection in search-based advertising services. We develop an algorithm that adaptively identifies the set of keywords to bid on based on historical performance. The algorithm prioritizes keywords based on a prefix ordering-- sorting of keywords in a descending order of profit-tocost ratio (or "bang-per-buck"). We show that the average expected profit generated by the algorithm converges to near-optimal profits. Furthermore, the convergence rate is independent of the number of keywords and scales gracefully with the problem's parameters. Extensive numerical simulations show that our algorithm outperforms existing methods, increasing profits by about 7%.

Market research has shown that consumers exhibit a variety of different purchasing behaviors; specifically, some tend to purchase products earlier than other consumers. Identifying such early buyers can help personalize marketing strategies, potentially improving their effectiveness. In this paper, we present a non-parametric approach to the problem of identifying early buyers from purchase data. Our formulation takes as inputs the detailed purchase information of each consumer, with which we construct a weighted directed graph whose nodes correspond to consumers and whose edges correspond to purchases consumers have in common; the edge weights indicate how frequently consumers purchase products earlier than other consumers.Identifying early buyers corresponds to the problem of finding a subset of nodes in the graph with maximum difference between the weights of the outgoing and incoming edges. This problem is a variation of the maximum cut problem in a directed graph. We provide an approximation algorithm based on semidefinite programming (SDP) relaxations pioneered by Goemans and Williamson, and analyze its performance. We apply the algorithm to real purchase data from Amazon.com, providing new insights into consumer behaviors.

In this paper, we use the rollout method for policy improvement to an- alyze a version of Klondike solitaire. This version, sometimes called thoughtful solitaire, has all cards revealed to the player, but then follows the usual Klondike rules. A strategy that we establish, using iterated roll- outs, wins about twice as many games on average as an expert human player does. 1 Introduction Though proposed more than fifty years ago [1, 7], the effectiveness of the policy improve- ment algorithm remains a mystery. For discounted or average reward Markov decision problems with n states and two possible actions per state, the tightest known worst-case upper bound in terms of n on the number of iterations taken to find an optimal policy is O(2n/n) [9]. This is also the tightest known upper bound for deterministic Markov de- cision problems. It is surprising, however, that there are no known examples of Markov decision problems with two possible actions per state for which more than n + 2 iterations are required. A more intriguing fact is that even for problems with a large number of states say, in the millions an optimal policy is often delivered after only half a dozen or so iterations. In problems where n is enormous say, a googol this may appear to be a moot point because each iteration requires (n) compute time. In particular, a policy is represented by a table with one action per state and each iteration improves the policy by updating each entry of this table. In such large problems, one might resort to a suboptimal heuris- tic policy, taking the form of an algorithm that accepts a state as input and generates an action as output. An interesting recent development in dynamic programming is the roll- out method. Pioneered by Tesauro and Galperin [13, 2], the rollout method leverages the policy improvement concept to amplify the performance of any given heuristic. Unlike the conventional policy improvement algorithm, which computes an optimal policy off-line so that it may later be used in decision-making, the rollout method performs its computations on-line at the time when a decision is to be made. When making a decision, rather than applying the heuristic policy directly, the rollout method computes an action that would result from an iteration of policy improvement applied to the heuristic policy. This does not require (n) compute time since only one entry of the table is computed. The way in which actions are generated by the rollout method may be considered an al- ternative heuristic that improves on the original. One might consider applying the rollout method to this new heuristic. Another heuristic would result, again with improved perfor- mance. Iterated a sufficient number of times, this process would lead to an optimal policy. However, iterating is usually not an option. Computational requirements grow exponen- tially in the number of iterations, and the first iteration, which improves on the original heuristic, is already computationally intensive. For this reason, prior applications of the rollout method have involved only one iteration [3, 4, 5, 6, 8, 11, 12, 13]. For example, in the interesting study of Backgammon by Tesauro and Galperin [13], moves were generated in five to ten seconds by the rollout method running on configurations of sixteen to thirty- two nodes in a network of IBM SP1 and SP2 parallel-RISC supercomputers with parallel speedup efficiencies of 90%. A second iteration of the rollout method would have been infeasible requiring about six orders of magnitude more time per move. In this paper, we apply the rollout method to a version of solitaire, modeled as a deter- ministic Markov decision problem with over 52! states. Determinism drastically reduces computational requirements, making it possible to consider iterated rollouts1. With five iterations, a game, implemented in Java, takes about one hour and forty-five minutes on average on a SUN Blade 2000 machine with two 900MHz CPUs, and the probability of winning exceeds that of a human expert by about a factor of two. Our study represents an important contribution both to the study of the rollout method and to the study of solitaire.

Motivated by its success in decoding turbo codes, we provide an analysis of the belief propagation algorithm on the turbo decoding graph with Gaussian densities. In this context, we are able to show that, under certain conditions, the algorithm converges and that-somewhat surprisingly-though the density generated by belief propagation may differ significantly from the desired posterior density, the means of these two densities coincide. Since computation of posterior distributions is tractable when densities are Gaussian, use of belief propagation in such a setting may appear unwarranted. Indeed, our primary motivation for studying belief propagation in this context stems from a desire to enhance our understanding of the algorithm's dynamics in a non-Gaussian setting, and to gain insights into its excellent performance in turbo codes. Nevertheless, even when the densities are Gaussian, belief propagation may sometimes provide a more efficient alternative to traditional inference methods.