We study approximation algorithms for revenue maximization based on static item pricing, where a seller chooses prices for various goods in the market, and then the buyers purchase utility-maximizing bundles at these given prices. We formulate two somewhat general techniques for designing good pricing algorithms for this setting: Price Doubling and Item Halving. Using these techniques, we unify many of the existing results in the item pricing literature under a common framework, as well as provide several new item pricing algorithms for approximating both revenue and social welfare. More specifically, for a variety of settings with item pricing, we show that it is possible to deterministically obtain a log-approximation for revenue and a constant-approximation for social welfare simultaneously: thus one need not sacrifice revenue if the goal is to still have decent welfare guarantees. In addition, we provide a new black-box reduction from revenue to welfare based on item pricing, which immediately gives us new revenue-approximation algorithms (e.g., for gross substitutes valuations). The main technical contribution of this paper is a @math -approximation algorithm for revenue maximization based on the Item Halving technique, for settings where buyers have XoS valuations, where @math is the number of goods and @math is the average supply. Surprisingly, ours is the first known item pricing algorithm with polylogarithmic approximations for such general classes of valuations, and partially resolves an important open question from the algorithmic pricing literature about the existence of item pricing algorithms with logarithmic factors for general valuations. We also use the Item Halving framework to form envy-free item pricing mechanisms for the popular setting of multi-unit markets, providing a log-approximation to revenue in this case.
Clearly, the current paper is closely associated with the growing body of work on item pricing and more general envy-free schemes @cite_2 @cite_13 @cite_1 for social welfare and revenue maximization. Item pricing for maximizing only welfare has traditionally been a sought after area of research owing to its ties to Walrasian equilibrium; since our focus is primarily on revenue, we refer the reader to @cite_25 @cite_8 @cite_7 for more recent algorithmic perspectives on the subject. On the other hand, the problem of item pricing for revenue maximization has recently gained traction in computer science with respect to both sequential and simultaneous mechanisms. A steady stream of research has yielded near-optimal approximation algorithms for a variety of settings including but not limited to unit demand @cite_29 @cite_5 @cite_3 , single minded @cite_12 @cite_33 @cite_6 , graph minded @cite_23 , multi-unit markets @cite_2 @cite_13 , and unlimited supply settings @cite_26 @cite_29 . One of the main contributions of this paper is a general framework that captures many of the above results, and provides a recipe for converting them into bicriteria approximations.
@cite_26 @cite_33 @cite_7 @cite_8 @cite_29 @cite_1 @cite_3 @cite_6 @cite_23 @cite_2 @cite_5 @cite_13 @cite_25 @cite_12
1656659859 2062453462 1964207488 2292671995 2040618534 1526218779
We study prior-free revenue maximization for a seller with unlimited supply of n item types facing m myopic buyers present for k < log n days. We show that a certain randomized schedule of posted prices has an approximation factor of O(log m+log n k). This algorithm relies on buyer valuations having hereditary maximizers, a novel natural property satisfied for example by gross substitutes valuations. We obtain a matching lower bound with multi-unit valuations. In light of existing results [2], k days can thus improve the approximation by a Θ(k) factor. We also provide a posted price schedule with the same factor for positive affine allocative externalities, despite an increase in the optimal revenue. We deal with the problem of finding profit-maximizing prices for a finite number of distinct goods, assuming that of each good an unlimited number of copies is available, or that goods can be reproduced at no cost (e.g., digital goods). Consumers specify subsets of the goods and the maximum prices they are willing to pay. In the considered single-minded case every consumer is interested in precisely one such subset. If the goods are the edges of a graph and consumers are requesting to purchase paths in this graph, then we can think of the problem as pricing computer network connections or transportation links.We start by showing weak NP-hardness of the very restricted case in which the requested subsets are nested, i.e., contained inside each other or non-intersecting, thereby resolving the previously open question whether the problem remains NP-hard when the underlying graph is simply a line. Using a reduction inspired by this result we present an approximation preserving reduction that proves APX-hardness even for very sparse instances defined on general graphs, where the number of requests per edge is bounded by a constant B and no path is longer than some constant l. On the algorithmic side we first present an O(log l + log B)-approximation algorithm that (almost) matches the previously best known approximation guarantee in the general case, but is especially well suited for sparse problem instances. Using a new upper bounding technique we then give an O(l2)-approximation, which is the first algorithm for the general problem with an approximation ratio that does not depend on B. 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 the highway problem, we are given an @math -edge path graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is to choose weights so as to maximize the profit. A lot of research has been devoted to this apparently simple problem. The highway problem was shown to be strongly @math -hard only recently [K. M. , in Proceedings of the International Symposium on Algorithmic Game Theory (SAGT), 2009, pp. 275--286]. The best-known approximation is @math [I. Gamzu and D. Segev, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 582--593], which improves on the previous best @math approximation [M.-F. Balcan and A. Blum, in Proceedings of the ACM Conference on Electronic Commerce,... We study envy-free (EF) mechanisms for multi-unit auctions with budgeted agents that approximately maximize revenue. In an EF auction, prices are set so that every bidder receives a bundle that maximizes her utility amongst all bundles; We show that the problem of revenue-maximizing EF auctions is NP-hard, even for the case of identical items and additive valuations (up to the budget). The main result of our paper is a novel EF auction that runs in polynomial time and provides a approximation of 1 2 with respect to the revenue-maximizing EF auction. A slight variant of our mechanism will produce an allocation and pricing that is more restrictive (so called item pricing) and gives a 1 2 approximation to the optimal revenue within this more restrictive class. Novel compositions for use as cell growth-promoting materials are made by the following novel process involving the steps of: (a) slowly contacting serum or plasma with sufficient chilled perchloric acid to reach a 0.1 to 0.25 final molar concentration of said perchloric acid in said serum or plasma, (b) at a temperature of -1 DEG C. to 15 DEG C., (c) under intensive mixing which is continued until a homogeneous suspension is obtained, (d) separating the resultant precipitate, which contains the growth-promoting substances, from the supernatant, (e) eluting said growth-promoting substances from said precipitate by first resuspending said precipitate in an aqueous alkaline or salt solution, and thereafter, (f) adjusting the pH to solubilize the growth-promoting substances from the insoluble proteins, (g) separating the supernatant, which contains the growth-promoting substances, from the insoluble, undesired precipitate, (h) exchanging the solvent in the supernatant for a physiological solution, and (i) sterilizing the resultant growth-promoting material.