Name
Abstract | ||
|---|---|---|
Given a seller with $$k$$ types of items, $$m$$ of each, a sequence of users $$\{u_1, u_2,\ldots \}$$ 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 $$u_i$$ has his/her value function $$v_i(\cdot )$$ 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 a lower bound of the competitive ratio for this problem is $$\Omega (\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(\sqrt{k}\cdot \log h\log k)$$. When $$k=1$$ the lower and upper bounds asymptotically match the optimal result $$O(\log h)$$. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s10898-013-0043-4 | J. Global Optimization |
Keywords | Field | DocType |
Online algorithms,Pricing,Competitive ratio | Online algorithm,Mathematical optimization,Upper and lower bounds,Unit price,Bellman equation,Omega,Bundle,Mathematics,Competitive analysis | Journal |
Volume | Issue | ISSN |
58 | 2 | 0925-5001 |
Citations | PageRank | References |
2 | 0.40 | 20 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yong Zhang | 1 | 68 | 10.51 |
| Francis Y. L. Chin | 2 | 2173 | 377.15 |
| Hing-Fung Ting | 3 | 76 | 11.69 |