We study the envy free pricing problem faced by a seller who wishes to maximize revenue by setting prices for bundles of items. If there is an unlimited supply of items and agents are single minded then we show that finding the revenue maximizing envy free allocation pricing can be solved in polynomial time by reducing it to an instance of weighted independent set on a perfect graph. We define an allocation pricing as if no agent wishes to replace her allocation with the union of the allocations of some set of other agents and her price with the sum of their prices. We show that it is -hard to decide if a given allocation pricing is multi envy free. We also show that revenue maximization multi envy free allocation pricing is hard. Furthermore, we give efficient algorithms and hardness results for various variants of the highway problem.
Much of the work on envy free revenue maximization is on item pricing rather than on subset pricing. @cite_13 give an @math -approximation for the general single minded problem, where @math is the number of items and @math is the number of agents. This result was extended by @cite_4 to an @math -approximation for arbitrary valuations and unlimited supply using single fixed pricing which is basically pricing all bundles with the same price. @cite_6 show that the general item pricing problem with unlimited availability of items is hard to approximate within a (semi-)logarithmic factor.
@cite_13 @cite_6 @cite_4
2010996873 2031502124
We consider the problem of pricing n items to maximize revenue when faced with a series of unknown buyers with complex preferences, and show that a simple pricing scheme achieves surprisingly strong guarantees. We show that in the unlimited supply setting, a random single price achieves expected revenue within a logarithmic factor of the total social welfare for customers with general valuation functions, which may not even necessarily be monotone. This generalizes work of Guruswami et. al [18], who show a logarithmic factor for only the special cases of single-minded and unit-demand customers. In the limited supply setting, we show that for subadditive valuations, a random single price achieves revenue within a factor of 2O(√(log n loglog n) of the total social welfare, i.e., the optimal revenue the seller could hope to extract even if the seller could price each bundle differently for every buyer. This is the best approximation known for any item pricing scheme for subadditive (or even submodular) valuations, even using multiple prices. We complement this result with a lower bound showing a sequence of subadditive (in fact, XOS) buyers for which any single price has approximation ratio 2Ω(log1 4 n), thus showing that single price schemes cannot achieve a polylogarithmic ratio. This lower bound demonstrates a clear distinction between revenue maximization and social welfare maximization in this setting, for which [12,10] show that a fixed price achieves a logarithmic approximation in the case of XOS [12], and more generally subadditive [10], customers. We also consider the multi-unit case examined by [1111] in the context of social welfare, and show that so long as no buyer requires more than a 1 -- e fraction of the items, a random single price now does in fact achieve revenue within an O(log n) factor of the maximum social welfare. We present approximation and online algorithms for a number of problems of pricing items for sale so as to maximize seller's revenue in an unlimited supply setting. Our first result is an O(k)-approximation algorithm for pricing items to single-minded bidders who each want at most k items. This improves over recent independent work of Briest and Krysta [5] who achieve an O(k2) bound. For the case k = 2, where we obtain a 4-approximation, this can be viewed as the following graph vertex pricing problem: given a (multi) graph G with valuations we on the edges, find prices pi ≥ 0 for the vertices to maximize Σ (pi + pj). e=(i,j):we ≥ pi + pj.We also improve the approximation of [11] from O(log m + log n) to O(log n), where m is the number of bidders and n is the number of items, for the "highway problem" in which all desired subsets are intervals on a line.Our approximation algorithms can be fed into the generic reduction of [2] to yield an incentive-compatible auction with nearly the same performance guarantees so long as the number of bidders is sufficiently large. In addition, we show how our algorithms can be combined with results of Blum and Hartline [3], [4], and Kalai and Vempala [13] to achieve good performance in the online setting, where customers arrive one at a time and each must be presented a set of item prices based only on knowledge of the customers seen so far. 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. We consider the item pricing problem for revenue maximization, where a single seller with multiple distinct items caters to multiple buyers with unknown subadditive valuation functions who arrive in a sequence. The seller sets the prices on individual items, and we design randomized pricing strategies to maximize expected revenue. We consider dynamic uniform strategies, which can change the price upon the arrival of each buyer but the price on all unsold items is the same at all times, and static nonuniform strategies, which can assign different prices to different items but can never change it after setting it initially. We design pricing strategies that guarantee poly-logarithmic (in number of items) approximation to maximum possible social welfare, which is an upper bound on revenue. We also show that any static uniform pricing strategy cannot yield such approximation, thus highlighting a large gap between the powers of dynamic and static pricing. Finally, our pricing strategies imply poly-logarithmic ...