Online pricing for multi-type of items

摘要: This paper studies the online pricing problem in which there is a sequence of users who want to buy items from one seller. The single seller has k types and each type limited copies. These are arriving by at different times single-minded. When arriving, user would announce her interested bundle non-increasing acceptable price function, specifies how much she willing pay for certain number bundles. Upon arrival user, needs determine immediately bundles be sold he charge her. His goal maximize sum money received users.When indivisible, we show that no deterministic algorithm could have competitive ratio better than O ( h ) where highest unit least some pay. Thus focus on randomized algorithms. We derive lower bound ? log + any solving this problem. Then give first R p -multi Δ -competitive, respectively maximum minimum copies can function growing slightly faster . known ahead time, decreased .When divisible fractionally, concentrate designing D -competitive. known, also study algorithms