多需求鱼池定价问题(英文)

On Multi-demand Knapsack Pricing

本文考虑了多需求下的鱼池定价问题.假设有m个鱼池可供投放鱼类种群,n个顾客需要使用鱼池,每个顾客有多个鱼类种群需要投放到至多m个鱼池中去.鱼池所有者根据顾客的需求和报价进行重新定价和最终分配,在满足部分顾客的全部需求下最大化其收益.文中考虑了两种定价机制-单一定价和按比例定价.并结合背包算法,在按比例定价情形下设计了具有对数竞争比的算法,最大化鱼池所有者的收益.

We study the pricing of multi-demand knapsack problem to maximize the seller/supplier＇s revenue. There are n customers which wish to place items in the knapsack, each of them has a valuation for buying the corresponding spaces of the knapsack. The knapsack supplier decides the price and the corresponding allocation to customers. Assume that the pricing strategy must be envy-free, that is： the customers who succeed in getting space by paying the given price are most satisfied about the allocation. We design the competitive algorithms over the sum of customers＇ valuation, by composing the technique of packing algorithm.