In this paper we consider the dynamic assortment selection problem under an uncapacitated multinomial-logit (MNL) model. By carefully analyzing a revenue potential function, we show that a trisection based algorithm achieves an item-independent regret bound of @math , which matches information theoretical lower bounds up to iterated logarithmic terms. Our proof technique draws tools from the unimodal convex bandit literature as well as adaptive confidence parameters in minimax multi-armed bandit problems.
The work @cite_4 is closely related to our paper, which analyzes the same revenue potential function and proposes a golden ratio search algorithm based on the unimodal property of the potential function. However, only using the unimodal property leads a regret bound involving @math @cite_4 , which is not @math -independent. Moreover, the golden ratio search algorithm imposes a strong separability assumption'' (see Proposition 8 in @cite_4 ), which assumes a constant gap between the expected revenues of any pair of candidate assortments, which may fail when the number of items @math is large. In this work we relax the gap assumption and also remove the additional @math dependency by a more refined analysis of properties of the revenue potential function.
@cite_4
2000931246 2951767300 1964207488 1495768673
Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253 We study the revenue maximization problem of a seller with n heterogeneous items for sale to a single buyer whose valuation function for sets of items is unknown and drawn from some distribution D. We show that if D is a distribution over subadditive valuations with independent items, then the better of pricing each item separately or pricing only the grand bundle achieves a constant-factor approximation to the revenue of the optimal mechanism. This includes buyers who are k-demand, additive up to a matroid constraint, or additive up to constraints of any downwards-closed set system (and whose values for the individual items are sampled independently), as well as buyers who are fractionally subadditive with item multipliers drawn independently. Our proof makes use of the core-tail decomposition framework developed in prior work showing similar results for the significantly simpler class of additive buyers [LY13, BILW14]. In the second part of the paper, we develop a connection between approximately optimal simple mechanisms and approximate revenue monotonicity with respect to buyers' valuations. Revenue non-monotonicity is the phenomenon that sometimes strictly increasing buyers' values for every set can strictly decrease the revenue of the optimal mechanism [HR12]. Using our main result, we derive a bound on how bad this degradation can be (and dub such a bound a proof of approximate revenue monotonicity); we further show that better bounds on approximate monotonicity imply a better analysis of our simple mechanisms. We investigate nonparametric multiproduct pricing problems, in which we want to find revenue maximizing prices for products @math based on a set of customer samples @math . We mostly focus on the unit-demand case, in which products constitute strict substitutes and each customer aims to purchase a single product. In this setting a customer sample consists of a number of nonzero values for different products and possibly an additional product ranking. Once prices are fixed, each customer chooses to buy one of the products she can afford based on some predefined selection rule. We distinguish between the min-buying, max-buying, and rank-buying models. Some of our results also extend to single-minded pricing, in which case products are strict complements and every customer seeks to buy a single set of products, which she purchases if the sum of prices is below her valuation for that set. For the min-buying model we show that the revenue maximization problem is not approximable within factor @math for some constant @math , unless @math , thereby almost closing the gap between the known algorithmic results and previous lower bounds. We also prove inapproximability within @math , @math being an upper bound on the number of nonzero values per customer, and @math under slightly stronger assumptions and provide matching upper bounds. Surprisingly, these hardness results hold even if a price ladder constraint, i.e., a predefined order on the prices of all products, is given. Without the price ladder constraint we obtain similar hardness results for the special case of uniform valuations, i.e., the case that every customer has identical values for all the products she is interested in, assuming specific hardness of the balanced bipartite independent set problem in constant degree graphs or hardness of refuting random 3CNF formulas. Introducing a slightly more general problem definition in which customers are given as an explicit probability distribution, we obtain inapproximability within @math assuming @math . These results apply to single-minded pricing as well. For the max-buying model a polynomial-time approximation scheme exists if a price ladder is given. We give a matching lower bound by proving strong NP-hardness. Assuming limited product supply, we analyze a generic local search algorithm and prove that it is 2-approximate. Finally, we discuss implications for the rank-buying model. 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.