
handle: 10722/152045
In this paper, we study the problem of online pricing for bundles of items. Given a seller with k types of items, m of each, a sequence of users {u 1 , u 2 , ...} arrives one by one. Each user is single-minded, i.e., each user is interested only in a particular bundle of items. The seller must set the price and assign some amount of bundles to each user upon his/her arrival. Bundles can be sold fractionally. Each u i has his/her value function v i (·) such that v i (x ) is the highest unit price u i is willing to pay for x bundles. The objective is to maximize the revenue of the seller by setting the price and amount of bundles for each user. In this paper, we first show that the lower bound of the competitive ratio for this problem is Ω(logh +logk ), where h is the highest unit price to be paid among all users. We then give a deterministic online algorithm, Pricing, whose competitive ratio is $O(\sqrt{k}\cdot\log h\log k)$ . When k =1 the lower and upper bounds asymptotically match the optimal result O (logh ).
Optimal results, Unit prices, Lower and upper bounds, Online pricing, Lower bounds, Value functions, Deterministic online algorithms, Competitive ratio
Optimal results, Unit prices, Lower and upper bounds, Online pricing, Lower bounds, Value functions, Deterministic online algorithms, Competitive ratio
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
