Online Pricing for Multi-type of Items

摘要

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 Ω(log h + log k), 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( k~(1/2)· log h log k). When k = 1 the lower and upper bounds asymptotically match the optimal result O (log h).