基于互联网的统一价格多物品双向动态拍卖设计.doc

基于互联网的统一价格多物品双向动态拍卖设计*A uniform price multi-units double dynamic online auction design苗兰波1 2 唐加福1Miao Lanbo, Tang Jiafu1.东北大学信息科学与工程学院，辽宁，沈阳 110819Dept of Systems Engineering, College of Information Scence & EngineeringNortheastern University, Shenyang, 1108192.中国联合网络通信有限公司辽宁省分公司，辽宁，沈阳 110002China United Network Communications Corporation Liaoning Branch,110002【摘 要】 本文构造了一个统一价格的双向动态拍卖模型，证明了基于模型真实报价是买卖双方的占优拍卖策略，并且该策略也保证了拍卖的效率和均衡。该模型适用于具有多个买家和卖家并且每个卖家或卖家只能进行一件同质物品交易的集中式拍卖；基于本模型的竞标价等于保留价是卖方的占优拍卖策略，同时在交易者数量很大的时候竞标价等于其估价是买方的占优拍卖策略，并且集中式升价拍卖机制存在完美贝耶斯均衡。【关键词】 网上拍卖；机制设计；双向拍卖；拍卖策略【BSTRACT】 We construct a double dynamic auction model with uniform price and prove that it is the a dominant strategy for all traders to bid their true values. The model is suitable for a centralized auction with many traders (including many buyers and many sellers) and each trader has one homogeneous good for trading; it is a dominant strategy that sellers bid equals his reserve price, meanwhile it is a dominant strategy for each buyer that buyers bid equals his true value while the number of buyers becomes large, and the centralized double auction mechanism has a perfect Bayesian equilibrium.【KEY WORDS】 online auction；mechanism design；double auction；bid strategy1 引言网上拍卖作为一种重要的电子商务活动，通过互联网将买卖双方联系起来,充分利用了拍卖定价的多样性和互联网的分布性，使得交易便利性得到大幅提高并且参与成本得到全面降低，网上拍卖得以迅速发展。1995年，Onsale和eBay首当其冲开辟了网上拍卖的先河，如今网上拍卖逐渐普及，不但Yahoo、Amazon这类著名网站投身其中，就连索斯比这样的老牌拍卖行也加入了网上拍卖的队伍；我国的雅宝(Y)，酷必得(CoolB) 等拍卖网站也都已经在消费品市场上占据了一席之地。全球每年通过网上拍卖交易的金额都有上百亿，并以每月10%的速度不断增长。研究和设计适用于互联网特性的网上拍卖机制, 成为目前电子商务的重要课题。双向拍卖是买卖双方共同出价的一种拍卖机制，适合于多个卖方和买方的多物品拍卖；利用互联网的分布性和便利性的特点，众多供给和需求类似的买家和卖家能够得以聚集，因此产生了大量同质物品的网上双向竞拍的需求。追溯双向拍卖的研究的历史，Wilson1首先将双向拍卖拓展为独立私有价值的多买方和多卖方且每一参与者人最多只能交易一个单位的不可分物品的拍卖；Rustichini，Satterthwaite及 Williams2也基于私有价值环境对静态（一次性）双向拍卖进行研究，并证明参与者数量足够多时会达到有效的分配均衡；Perry 和Reny 3提出了在相关估价环境里（交易者类型是相关的），当交易者数量足够大时双向拍卖将以概率收敛到完全信息的市场均衡清算价格；Michael Peters和Sergei Severinov 45也提出了在相关估价环境里动态双向拍卖机制，通过买卖双方的供求来实现均衡。本文结合Roth 和Sotomayor 6的拍卖价格调整方式，利用Satterthwaite和Williams7的卖方均衡策略以及Michael Peters 和Sergei Severinov45的买方均衡策略的成果，并且基于卖方的私有估价和买方相关估价的假设，通过建立一定的规则构造了一个用于拍卖多个同质物品的统一价格的集中式双向动态拍卖模型，进而证明了真实报价是买卖双方的占优策略及基于这种策略的拍卖存在完美贝耶斯均衡。2 拍卖模型设计假设拍卖市场上有个买方个卖方，每个买方只有一个同质物品的动态购买需求，每个卖方只有一个同质的物品要拍卖；参与者的估价用表示，参与者的竞拍价用表示，其中为参与者的类型；一般情况下简写为，都简写为，则当时为买方估价为买方竞拍价，当时为卖方估价为卖方竞拍价；买方的估价是私有独立的，卖方的估价（或称保留价）是私有的但是相关；买卖双方的估价分布在内，其步长为。买卖双方的交易信息发送给交易中心，交易中心统一处理这些信息并确定交易的分配和价格，同时将相关信息发送给买卖双方。每一拍卖阶段的临时拍卖价称为拍卖标称价，表示为，这一信息及退出拍卖的买家信息是本拍卖机制对外公布的，买方根据这些进行竞拍。2.1基本概念及假设定义1 令为买方的估价向量，为卖方的估价向量（或保留价），那么我们将和从小到大排序后的第个估价值记为。从竞争的角度来说，就是在给定买方的估价和卖方的保留价后，市场供给和需求平衡时的最低市场出清价。定义2 我们称以拍卖价为起点，以为步长的任何两个相邻拍卖点为一个拍卖阶段，每个拍卖阶段可能是升价阶段也可能是卖家引入阶段（结束点除外）。本拍卖是卖方提供保留价的集中式双向拍卖，设立一个拍卖池、一个买方缓冲池和一个卖方缓冲池，统一由拍卖中心管理。拍卖中心通过下文的卖方引入规则、买方拍卖规则、拍卖升价规则和拍卖结束规则对整个拍卖过程进行管理和控制。拍卖池设定一个标称价，表示当前的拍卖阶段拍卖价。卖方竞标价（保留价）只有达到标称价的卖家才有机会进入拍卖池。令为所有卖方的集合。针对拍卖阶段，我们用代表当前已进入拍卖池中的所有卖方（保留价小于等于当前标称价）的集合，用代表该集合中当前阶段所有卖方数量；我们用代表当前未进入拍卖池且保留价等于标称价的所有卖方集合，用代表该集合中当前阶段所有卖方数量；用代表当前未进入拍卖池但其保留价大于标称价的所有卖方集合，用代表该集合中当前阶段所有卖方数量。拍卖开始时，所有买方都进入拍卖池中，所有卖方都进入卖方缓冲池中。随着标称价的上升会不断有卖方从中转入；根据供需平衡，卖方不断从转入拍卖池直至供需平衡，这时拍卖结束并确定交易价为。针对当前标称价，认可目前的标称价的买方会继续留在拍卖池中参与拍卖，对于不认可标称价的买方，拍卖中心将其放入买方缓冲池中。买方缓冲池中的买方不能参与下一阶段拍卖但保留本阶段的交易机会；一旦有新的买方进入买方缓冲池，买方缓冲池中的原有买方就会真正退出拍卖。因此针对当前标称价我们将买方分成三类，第一类为所有认可当前标称价的买家，我们用代表其集合，用代表该集合中当前拍卖阶段买方数量，该集合中的买方估价都大于等于当前标称价；第二类为认可上一阶段拍卖标称价但不认可本阶段当前拍卖标称价的买方，他们存在于买方缓冲池中，我们用代表这些买家的集合用代表该集合中当前阶段买方数量；第三类为不认可本阶段及上一阶段拍卖标称价的买方，他们已经退出拍卖，我们用代表他们的集合，用代表该集合中当前阶段买方数量。定义3 我们规定拍卖池中的卖方数量首次大于拍卖池中买方时拍卖结束，这一拍卖阶段称为最后拍卖阶段，其当前标称价为。规定阶段的拍卖标称价为整个拍卖的交易价，表示为。实际操作是这样的：首次到达时拍卖结束，交易价确定为；或者首次到达时拍卖结束，为保持概念的统一我们规定此阶段为阶段，交易价同样为。定义 4 参与者的收益是参与者的估价的函数，其中买方的收益等于买方估价减去拍卖交易价，卖方的收益等于拍卖交易价减去卖方估价。未获得交易机会的参与者的收益等于0。假设1 。 这是个估价单调性假设，要求拍卖参与者的估价依其类型严格递增。假设2 任给，如果，那么。该假设是一个单交叉条件的假设，要求针对所有参与者当上升或下降且其他参与者的类型不变时不等式严格成立。本假设说明参与者的类型对物品估价值大小的影响大于其它参与者类型对估价的影响。这保证了具有最高类型的参与者其估价也最高。假设3 买方的分布在内且买方数量足够多，保证每个点所在的拍卖阶段都存在至少一个买方。2.2拍卖规则设计首先对卖方提交的竞拍价（保留价）进行排序。所有卖方同时提交各自的物品的竞拍价（保留价），拍卖中心针对所有保留价按照递增顺序进行排序，其中最低保留价记为，最高保留价记为。排序后的卖方被放入卖方缓冲池中，拍卖中心公布卖方中最低的保留价(估价)，并将该保留价(估价)设置为最初拍卖标称价；然后买方同时对拍卖池的标称价进行竞拍。拍卖中心将所有买方放入拍卖池继续参与竞拍；如果买方不认可标称价就选择直接退出竞拍(没有进入买方缓冲池的环节，这点与中间阶段的拍卖不同)。以后每个拍卖阶段，拍卖中心都根据拍卖池中买方和卖方的数量关系，按照如下拍卖规则进行拍卖。2.2.1 卖方引入规则当拍卖标称价达到缓冲池的卖方的最低保留价时，拍卖中心就从卖方缓冲池的保留价排序列表中按照从小到大的顺序选择（如果有保留价相等的就从中随机选取）卖方进入拍卖池。（1）如果拍卖池中需求等于供给，既，那么就停止卖方引入，按照拍卖结束规则进行处理；（2）如果拍卖池中需求大于供给，既，那么就重复从缓冲池中引入保留价等于该拍卖标称价的卖方，直到该保留价下的所有卖方都被引入。然后拍卖中心根据拍卖升价规则进入买方升价阶段。2.2.2 买方拍卖规则根据当前拍卖标称价买方同时进行竞拍。针对拍卖池中的每个买方指定如下规则：（1）对于认可目前的标称价格的买方允许其继续参与竞拍；（2）对于不认可标称价的买方，拍卖中心首先将其放入买方缓冲池中并不允许再进入拍卖池中。同时，如果本阶段拍卖结束，那么原买方缓冲池的买方随机获得交易机会，否则原买方缓冲池的买方退出买方缓冲池进而退出拍卖。2.2.3 拍卖结束规则每进入一个新的拍卖阶段， 拍卖中心都要进行判断，针对拍卖阶段如果那么就按如下规则进行处理：（1）当时，说明状态的买卖双方数量相等（一个参与植对应一件物品），那么拍卖结束，拍卖池的买卖双方互相成交且交易价为本拍卖阶段的标称价；（2）当时，说明拍卖池中拍卖物品数量大于需求物品数量。此时拍卖结束，前一阶段的标称价成为交易价格并赋值给。拍卖池中的买方及从买方缓冲池中随机选取的个买方与拍卖池中的卖方进行交易。2.2.4 拍卖升价规则每进入一个新的拍卖阶段，如果，那么拍卖中心就判断标称价是否到达卖方缓冲池的最低保留价。（1）如果未达到缓冲池的最低保留价既，那么就将标称价提高一个单位步长，并针对这个标称价继续进行下一阶段每个价格点的买方竞拍；（2）如果达到缓冲池的最低保留价既，那么根据卖方引入规则引入卖方。3拍卖策略和均衡3.1 卖方拍卖策略我们称卖方选择保留价等于真实估价（真实成本）为卖方的对称策略。定理1 在卖方私有估价情况下，选择对称策略是每个卖方的占优策略。证明：在本拍卖模型中卖方只有一次报价机会且互相之间无接触，因此卖方具有私有价值环境。本定理与 satterthwaite（1989）中定理2.1中的情况一样，其证明过程详见参考文献7。 当然我们也可以换一种证明方式，并给出证明思路如下：将本定理的证明分成如下3部分：（1）假设除了卖方之外的所有参与者都遵守对称策略，当卖方的估价小于时，那么卖方的任何偏离策略都不会优于对称策略；（2）假设除了卖方之外的所有参与者都遵守对称策略，当卖方的保留价等于时，那么卖方的任何偏离策略都不会优于对称策略；（3）假设除了卖方之外的所有参与者都遵守对称策略，当卖方的估价大于时，那么卖方的任何偏离策略都不会优于对称策略。3.2买方拍卖策略及拍卖均衡基于卖方真实报价的前提下我们下面开始讨论买方的拍卖策略，并在以上基础上讨论整个拍卖均衡的存在性。定义5 每个参与拍卖的买方的对称拍卖策略定义如下：（1）如果该买方对物品的估价小于等于拍卖的标称价，那么该买方就选择退出拍卖；（2）否则，该买方选择接受当前拍卖的标称价，继续参与下一阶段的拍卖。引理1 如果所有的买方采用对称策略，那么拍卖的交易价等于阶段的标称价确定的交易价。证明：设阶段的标称价为，如果，根据的定义（定义3）可知此时, 所以必存在使得且根本没有交易机会；然而因为，所以他的估价一定大于等于当前标称价，既，根据买方拍卖规则，买方在本阶段不会选择退出，这与本阶段为 阶段矛盾。所以交易价必然大于等于标称价确定的交易价。设阶段的标称价为，如果，那么就存在一个非结束阶段的拍卖阶段，其标称价也等于。因为此时为非结束阶段，所以，根据买方策略一定存在下一阶段拍卖，导致标称价上升到。但是根据定义，达到阶段时供给刚刚大于需求，因此拍卖池中的每个买方都能获得交易机会并得到一份物品，如果不偏离对称策略，每个买方都不会继续竞拍，也就是说拍卖价不会超过。所以最后的标称价等于且交易价为。这样就证明了在所有买方遵守对称策略的情况下，买卖双方的交易价为，所有估价大于的买方和所有保留价（估价）小于的卖方进行交易。引理 2 当所有的参与者都遵守对称策略则从阶段必然通过升价到达阶段。证明：根据定义3中的定义可直接得到此引理的结论。定理1对称策略是买方的最优策略且基于此策略的拍卖博弈构成一个完美的贝耶斯均衡。证明：在我们的拍卖模型中，均衡策略包括一套进入和退出均衡路径的规则。虽然均衡路径比较简单，但是通过对称策略构成完美贝耶斯均衡的证明过程是却很复杂。我们的证明过程是这样的，依据引理1中给出的全部参与者都遵守对称策略情况下的拍卖结束阶段为参考点，针对任何一个买方单方偏离对称策略且假设除了之外的所有买方都遵守对称策略前提下，我们从如下三个方面对定理给与分析证明（单边方偏离策略我们用表示，拍卖池中相应的买方和卖方数量用和表示）：（1）如果， 那么买方的任何偏离策略都不会优于对称策略；（2）如果，那么买方的任何偏离策略都不会优于对称策略；（3）如果，那么买方的任何偏离策略都不会优于对称策略。（1）、（2）和（3）的证明我们分别进行，每方面又分成4种情况。（1）的证明：假设除了之外的所有买方都遵守对称策略且，如果遵守对称策略，那么他将获得交易机会，获得收益；如果买方偏离对称策略，那么我们需要考虑如下三种情况：情况. 买方偏离对称策略表现为买方虽然偏离对称策略，由于，所以在任何拍卖阶段不会影响拍卖池中买卖双方数量。根据买方拍卖规则，拍卖结束时买方仍将获得交易机会，交易价不变仍为，买方的收益等于采用对称策略时的收益，既。 情况. 买方偏离对称策略表现为如果阶段由于买方采用偏离策略并不改变阶段及以前阶段拍卖池中买卖双方的数量，所以根据买方拍卖规则，买方将获得交易机会，交易价仍然是。这种情况下买方的收益等于采用对称策略时的收益。如果阶段因为买方采用偏离策略，所以阶段时和都没有变化（以前阶段也没有变化）；根据引理2知从阶段必通过升价进入阶段，因为，所以买方进入买方缓冲池，导致拍卖池中买方数量减少一个，其中的卖方数量不变，那么阶段拍卖池中买卖双方大小关系不变，根据拍卖结束规则拍卖结束，交易价仍将为，买方将以的概率获得交易机会，因此该买方的期望收益小于。情况. 买方偏离对称策略，表现为如果阶段时由于买方采用偏离策略，并不影响阶段及之前阶段拍卖池中买方和卖方的数量，但会导致到达阶段时拍卖池中买方和卖方数量改变。如果此时，根据拍卖升价规则从阶段必通过升价进入阶段，结果，由于此阶段拍卖池中卖方数量不变，所以，根据拍卖结束规则拍卖提前一个阶段结束，交易价降为，买方以概率随机获得交易机会，期望收益为；如果此时，根据拍卖升价规则可知从阶段不会通过升价进入阶段，而是直接通过卖方引入进入阶段。由于该偏离策略不会影响阶段拍卖池中买卖双方的数量，根据拍卖结束规则本拍卖结束，交易价仍为，买方失去交易机会且收益为0。如果阶段由于买方采用偏离策略并不影响阶段及之前阶段拍卖池中买方和卖方的数量，但使得阶段拍卖池中买方数量减少一个而卖方数量不变，因此导致。如果，那么该偏离策略会导致，根据拍卖规则拍卖结束，买方将获得交易机会，交易价仍然是；如果，那么偏离策略会导致，根据引理2然后必会升价进入阶段，因此不会影响阶段拍卖池中买卖双方的数量关系，且交易价仍然是。买方将以的概率获得交易机会，该买方的期望收益小于；情况. 买方偏离对称策略，表现为买方采用偏离策略并不影响阶段之前拍卖池中买卖双方的数量关系，既对任何我们有，所以我们结合阶段、阶段对阶段进行分析。如果阶段时如果，那么买方的偏离策略会导致，根据拍卖结束规则和引理2，导致拍卖结束且交易价降到，同时买方失去了交易机会，收益为0；如果，那么买方的偏离策略不改变阶段拍卖池中买卖双方的数量关系既，根据拍卖规则无论是阶段还是阶段结束拍卖，买方都将失去了交易机会，收益为0。如果阶段由于买方采用偏离策略，使得到达阶段时拍卖池中买方数量减少一个，而卖方数量不变，导致，因此对交易价不产生影响，同时买方失去交易机会，收益为0。(2)和（3）的证明与（1）类似，这里就不再熬述。所以买方的任何偏离策略都不会优于对称策略，采用对称策略是买方的最优策略。综上可知：基于此策略的拍卖博弈构成一个完美的贝耶斯均衡。同时每个估价大于的买方都会与估价不大于的卖方进行交易，每个估价小于的卖方都会与估价小于的卖方进行交易。4 结语本文设计了一个适用于互联网的集中式同时升价双边拍卖机制，证明了基于本模型真实报价是买卖双方的最优拍卖策略，并且该策略也保证了拍卖的效率和均衡；通过理论设计及实现的描述，对网上双向拍卖理论研究和具体应用都具有一定的指导意义；另外本拍卖模型也可以进一步拓展为每个参与者可以交易多个物品的同制物品的双向拍卖。参考文献:1 Wilson, R. Incentive Efficiency of Double Auctions. Econometrica, 53, 1985. 11011115.2 Rustichini, A., M. A. Satterthwaite, and S. R. Williams. Convergence to Efficiency in a Simple Market with Incomplete Information. Econometrica, 62(5), 1994. 10411063.3 Perry, M., P.