Given a seller with <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$k$$</EquationSource> </InlineEquation> types of items, <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$m$$</EquationSource> </InlineEquation> of each, a sequence of users <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$\{u_1, u_2,\ldots \}$$</EquationSource> </InlineEquation> arrive 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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$u_i$$</EquationSource> </InlineEquation> has his/her value function <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$v_i(\cdot )$$</EquationSource> </InlineEquation> such that <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$$v_i(x)$$</EquationSource> </InlineEquation> is the highest unit price <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$$u_i$$</EquationSource> </InlineEquation> is willing to pay for <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$$x$$</EquationSource> </InlineEquation> 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 a lower bound of the competitive ratio for this problem is <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$$\Omega (\log h+\log k)$$</EquationSource> </InlineEquation>, where <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$$h$$</EquationSource> </InlineEquation> is the highest unit price to be paid among all users. We then give a deterministic online algorithm, Pricing, whose competitive ratio is <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$$O(\sqrt{k}\cdot \log h\log k)$$</EquationSource> </InlineEquation>. When <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$$k=1$$</EquationSource> </InlineEquation> the lower and upper bounds asymptotically match the optimal result <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$$O(\log h)$$</EquationSource> </InlineEquation>. Copyright Springer Science+Business Media New York 2014
