带有预算的单商品在线定价问题研究

，

(浙江理工大学理学院，杭州 310018)

0 引 言

随着企业商品销售信息化的发展，各种新颖的销售模式层出不穷，这对企业通过商品销售实现收益最大化的目标提出了挑战。衡量一个企业创造价值的标准是商品销售额的增加。从而企业收益最大化是市场经济发展的一个主要目标。商品销售不仅是市场经济中最基础的一环，而且是企业实现收益最大化的关键因素，更是通过市场竞争来实现资源配置的一种机制。商品销售过程涉及到商品的供求、竞争、定价等因素，尤其是定价因素的应用场景非常广泛。因此商品定价问题在经济学中具有非常重要的地位，近些年来许多学者研究了该问题，着重研究了定价问题中用户的行为模式[1-5]。商品定价问题模型在优化领域中可分为两类，即具有完整市场信息的模型和具有不完整市场信息的模型，前者主要刻画分析不同的用户行为模式，后者主要考虑在未来信息缺失的情况下设计优化算法等。

离线定价问题可以看作组合拍卖问题[2，4，6-7]，并且组合拍卖问题的研究方向有两个：一是组合拍卖的用户行为是无嫉妒型的，即给了一个定价，在这个价格下没有任何一个用户愿意和其他用户交换商品；二是这个组合拍卖是激励相容，即每个理性的投标者对于拍卖品的出标都是真实的[2-4]。

然而不论离线还是在线情形，目标是最优化卖方的收入，必定会有一个限制性因素——用户的预算[15-18]。Dobzinski等[19]对带有预算的商品拍卖问题提出了一个新的性能标准——流动福利，即知道所有信息的卖方能够从一个特例中抽取到的最大收入，同时也给出了一个竞争比为2的近似算法。Lu等[16]研究了在简单拍卖环境中，可以对多个带有预算的代理中分配一个单位的可分商品定价问题，并在预算可知的特殊情形下，设计了一个竞争比约为1.618的近似算法。这些都是带有预算的商品定价(拍卖)离线问题。

但对于带有预算的商品在线定价(拍卖)问题研究是很少，最新的是Eden等[20]研究带有预算的商品在线定价问题，这里的用户是带有一个到达时间和一个离开时间。本文受文献[20]的启发，从在线的角度来研究带预算的商品定价问题，与文献[20]不同之处在于本文的用户到达是overlist，是在文献[14]的基础上对用户多加一个限制性因素—预算，使其更具有一般性，更符合实际生活。本文对该情形利用价格分层的方法给出了近似算法，和预算的分类讨论来分析竞争比以及算法竞争比的大小。

1 符号定义

本文引入以下符号。

m：卖方拥有的商品数量；

Vi(x)：用户Ui对x个商品愿意支付的单价，即用户对x个商品的出价；

hi：用户Ui对x商品的最高出价，hi=maxVi(x)；

Lj：2j2价格层的价格，j=0，1，…；

|Qi|：2i2价格层的商品数量；

xi：2i2价格层能够使用的商品数量；

B：用户购买商品的预算；

ALG：表示通过定价算法卖方得到的总收入;

OPT：表示离线最优时卖方得到的总收入;

OPT1：表示买家的定价不超过2k2时，在离线最优情形卖方得到的收入;

OPT2：表示买家的定价超过2k2时，在离线最优情形卖方得到的收入。

2 问题描述

3 定价算法

算法A1：定价

a)yj表示买家Ui在出价为2j2时愿意购买的商品最大数量且满足yj≤m。

c) 如果xk≠0，这里xk表示2k2价格层可用的最大商品数量，然后设置单价pi=2k2。

d) 给买家Ui分配的商品数量mi=min{xk，yk}，

e) 修改可用商品的数量。

g) 设置单价pi=2k′2，

h) 给买家Ui分配的商品数量mi=min{xk′，yk′}，

i) 修改可用商品的数量，

j) 算法结束。

算法A2：修改商品数量

当pi=2k2和mi=min{xk，yk}时，

a) 如果mi=xk时，

b) 当0

d) 对于j=l+1到k时，

e)xj=xk-yk，

f) 算法结束。

4 算法分析

采用分层的思想根据用户的出价将价格进行分层处理：如果2j2≤p<2(j+1)2则p∈Lj，j=0，1，…。Lj中价格对应商品数量|Qj|，当j≥0，有|Qj|=2-j-1m。在定价算法中如果在2i2的价格层中所有商品都分配给了某些买家，卖家能够用低层中剩余商品数量去满足出价为2i2的买家。当使用低层的剩余商品数量时必须按照严格递减的顺序即首先使用的是Qi-1层，然后是Qi-2层，……，等。

引理1a) 在Qi价格层的商品的价格至少为2i2。

b) 用户的出价不少于2(i+1)2的能用的商品数量至少是2-i-1m。

证明:

a) 因为高价格层可以使用低价格层的商品，Qi价格层的商品价格为2i2。所以大于Qi的价格层要使用Qi层的商品，这时Qi层的商品价格是大于2i2，故a)得证。

b) 当出价等于2i2时能够使用的最大商品数量是xi=(1-2-i-1)m，而商品的总量是m，所以当用户的出价不少于2(i+1)2的能用的商品数量至少是m-xi=2-i-1m，故b)得证。

从上面的算法中可知如果xi=0则称价格层2i2是满状态。用算法处理好这个用户后，记k=max{j|xj=0}。即所有的202到2k2是满状态的但值2j2(j>k)不是满状态的，即当j>k+1，xj>0。

5 主要结果

定理定价算法的竞争比是

该定理将通过引理2-5证明。

证明:

综上所述引理2得证。

证明:

(1)

而此时在线情况由于价格层从202到2k2是满状态的。从引理1易知用户单价不超过卖家获得的总收入至少为

(2)

故引理3得证。

引理4对于每个2p2≤2k2的价格层，用在线定价算法在这里最多有一个用户被分配的数量为xp

证明:

从定价算法中可知当买家设置单价为2p2，这个价格层中保留的商品数量是大于0。如果xp

证明:证明此引理考虑以下两种情形：

2p2·2-p-1m≥2p2·2-p-1yp≥2l2·2-p-1yl=

2(l+1)2·2-2l-1·2-p-1yl≥p′m′·2-2l-1·2-p-1。

显然，这个用户在价格层为2p2的离线最优收入与定价算法的总收入的竞争比最多为

再由引理4可以知，在每个价格层为2p2≤2k2商品最多被计算2次。一次是用户需求是全部满足，一次是用户需求是部分满足。故将OPT2更细致的分成两个部分OPT21和OPT22。OPT21为通过此算法用户需求全部满足时，卖家所获得离线最优收入，OPT22为通过此算法用户需求部分满足，卖家所获得离线最优收入。

从而引理5成立。

因为当B>m时把OPT划分为OPT1和OPT2两种情况，所以在取竞争比时应当选两者中较大的情形，再根据引理2可知定理得证。

6 结 论

参考文献：

[1] Abraham I， Babaioff M， Dughmi S， et al. Combinatorial auctions with restricted complements[C]// ACM Conference on Electronic Commerce. ACM，2012:3-16．

[2] Bartal Y， Gonen R， Nisan N. Incentive compatible multi unit combinatorial auctions[C]// Conference on Theoretical Aspects of Rationality and Knowledge. ACM，2003:72-87．

[3] Dobzinski S， Nisan N， Schapira M. Truthful randomized mechanisms for combinatorial auctions[C]// Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of computing. New York: ACM New York，2006:644-652．

[4] Lavi R， Nisan N. Competitive analysis of incentive compatible on-line auctions[C]// Proceedings of the 2nd ACM Conference on Electronic commerce. New York: ACM New York，2000:233-241．

[5] Lehmann B， Lehmann B D， Nisan N. Combinatorial auctions with decreasing marginal utilities[J]. Games & Economic Behavior，2002，55(2):270-296．

[6] Fiat A， Wingarten A. Envy， multi envy， and revenue maximization[C]// International Workshop on Internet and Network Economics. Springer-Verlag，2009:498-504．

[7] Im S， Lu P， Wang Y. Envy-free pricing with general supply constraints[C]// International Conference on Internet and Network Economics. Springer-Verlag，2010:483-491．

[8] Blum A， Hartline J D. Near-optimal online auctions[C]// Sixteenth ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics，2005:1156-1163．

[9] Babaioff M， Dughmi S， Kleinberg R， et al. Dynamic pricing with limited supply[J]. ACM Transactions on Economics and Computation，2011，3(1):1-26．

[10] El-Yaniv R. Competitive solutions for online financial problems[J]. ACM Computing Surveys，1998，30(1):28-69．

[11] El-Yaniv R， Fiat A， Karp R M， et al. Optimal search and one-way trading online algorithms[J]. Algorithmica，2001，30(1):101-139．

[12] Zhang W M， Zhang E， Zheng F F. Online( J， K )-search problem and its competitive analysis[J]. Theoretical Computer Science.2015，593(C):139-145．

[13] Zhang W M， Xu Y F， Dong Y， et al. Online algorithms for the multiple time series search problem[J]. Computers & Operations Research，2012，39(5):929-938．

[14] Zhang Y， Chin F Y L， Ting H F. Competitive algorithms for online pricing[C]// International Conference on Computing and Combinatorics. Springer-Verlag，2011:391-401．

[15] Briest P. Uniform budgets and the envy-free pricing problem[C]// International Colloquium on Automata， Languages and Programming. Springer-Verlag，2008:808-819．

[16] Lu P， Xiao T. Improved efficiency guarantees in auctions with budgets[C]// Sixteenth ACM Conference on Electronic commerce. ACM，2015:397-413．

[17] Devanur N R， Ha B Q， Hartline J D. Prior-free auctions for budgeted agents[C]// Fourteenth ACM Conference on Electronic Commerce.ACM，2013:287-304．

[18] Fiat A， Leonardi S， Saia J， et al. Single valued combinatorial auctions with budgets[C]// ACM Conference on Electronic Commerce. ACM，2011:223-232．

[19] Dobzinski S， Leme R P. Efficiency guarantees in auctions with budgets[C]// International Colloquium on Automata, Languages, and Programming. Springer Berlin Heidelberg，2014:392-404．

[20] Eden A， Feldma M， Vardi A. Online random sampling for budgeted settings[C]//International Symposium on Algorithmic Game Theory. Springer，2017:29-40．