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

基于互联网的统一价格多物品双向动态拍卖设计*Auniformpricemulti-unitsdoubledynamiconlineauctiondesign苗兰波12唐加福1MiaoLanbo,TangJiafu1.东北大学信息科学与工程学院，辽宁，沈阳110819DeptofSystemsEngineering,CollegeofInformationScence&EngineeringNortheasternUniversity,Shenyang,1108192.中国联合网络通信有限公司辽宁省分公司，辽宁，沈阳110002ChinaUnitedNetworkCommunicationsCorporationLiaoningBranch,110002【摘要】本文构造了一个统一价格的双向动态拍卖模型，证明了基于模型真实报价是买卖双方的占优拍卖策略，并且该策略也保证了拍卖的效率和均衡。该模型适用于具有多个买家和卖家并且每个卖家或卖家只能进行一件同质物品交易的集中式拍卖；基于本模型的竞标价等于保留价是卖方的占优拍卖策略，同时在交易者数量很大的时候竞标价等于其估价是买方的占优拍卖策略，并且集中式升价拍卖机制存在完美贝耶斯均衡。【关键词】网上拍卖；机制设计；双向拍卖；拍卖策略【BSTRACT】Weconstructadoubledynamicauctionmodelwithuniformpriceandprovethatitistheadominantstrategyforalltraderstobidtheirtruevalues.Themodelissuitableforacentralizedauctionwithmanytraders(includingmanybuyersandmanysellers)andeachtraderhasonehomogeneousgoodfortrading;itisadominantstrategythatseller’sbidequalshisreserveprice,meanwhileitisadominantstrategyforeachbuyerthatbuyer’sbidequalshistruevaluewhilethenumberofbuyersbecomeslarge,andthecentralizeddoubleauctionmechanismhasaperfectBayesianequilibrium.【KEYWORDS】onlineauction；mechanismdesign；doubleauction；bidstrategy1引言网上拍卖作为一种重要的电子商务活动，通过互联网将买卖双方联系起来,充分利用了拍卖定价的多样性和互联网的分布性，使得交易便利性得到大幅提高并且参与成本得到全面降低，网上拍卖得以迅速发展。1995年，Onsale和eBay首当其冲开辟了网上拍卖的先河，如今网上拍卖逐渐普及，不但Yahoo、Amazon这类著名网站投身其中，就连索斯比这样的老牌拍卖行也加入了网上拍卖的队伍；我国的雅宝(Yabuy.com)，酷必得(CoolBid.com)等拍卖网站也都已经在消费品市场上占据了一席之地。全球每年通过网上拍卖交易的金额都有上百亿，并以每月10%的速度不断增长。研究和设计适用于互联网特性的网上拍卖机制,成为目前电子商务的重要课题。双向拍卖是买卖双方共同出价的一种拍卖机制，适合于多个卖方和买方的多物品拍卖；利用互联网的分布性和便利性的特点，众多供给和需求类似的买家和卖家能够得以聚集，因此产生了大量同质物品的网上双向竞拍的需求。追溯双向拍卖的研究的历史，Wilson[1]首先将双向拍卖拓展为独立私有价值的多买方和多卖方且每一参与者人最多只能交易一个单位的不可分物品的拍卖；Rustichini，Satterthwaite及Williams[2]也基于私有价值环境对静态（一次性）双向拍卖进行研究，并证明参与者数量足够多时会达到有效的分配均衡；Perry和Reny[3]提出了在相关估价环境里（交易者类型是相关的），当交易者数量足够大时双向拍卖将以概率收敛到完全信息的市场均衡清算价格；MichaelPeters和SergeiSeverinov[4][5]也提出了在相关估价环境里动态双向拍卖机制，通过买卖双方的供求来实现均衡。本文结合Roth和Sotomayor[6]的拍卖价格调整方式，利用Satterthwaite和Williams[7]的卖方均衡策略以及MichaelPeters和SergeiSeverinov[4][5]的买方均衡策略的成果，并且基于卖方的私有估价和买方相关估价的假设，通过建立一定的规则构造了一个用于拍卖多个同质物品的统一价格的集中式双向动态拍卖模型，进而证明了真实报价是买卖双方的占优策略及基于这种策略的拍卖存在完美贝耶斯均衡。2拍卖模型设计假设拍卖市场上有m个买方n个卖方，每个买方只有一个同质物品的动态购买需求，每个卖方只有一个同质的物品要拍卖；参与者的估价用()iv表示，参与者的竞拍价用()ib表示，其中为参与者的类型；一般情况下()iv简写为iv，()ib都简写为ib，则当1,...,im时iv为买方*基金项目：国家自然科学基金资助项目(NSFC70721001和70625001)估价ib为买方竞拍价，当1,...,imn时iv为卖方估价ib为卖方竞拍价；买方的估价是私有独立的，卖方的估价（或称保留价）是私有的但是相关；买卖双方的估价分布在{,,2,...,}Dppdpdp内，其步长为0d。买卖双方的交易信息发送给交易中心，交易中心统一处理这些信息并确定交易的分配和价格，同时将相关信息发送给买卖双方。每一拍卖阶段t的临时拍卖价称为拍卖标称价，表示为tp，这一信息及退出拍卖的买家信息是本拍卖机制对外公布的，买方根据这些进行竞拍。2.1基本概念及假设定义1令1{,...}bmVvv为买方的估价向量，1{,...}smnVvv为卖方的估价向量（或保留价），那么我们将bV和sV从小到大排序后的第m个估价值记为mv。从竞争的角度来说，mv就是在给定买方的估价和卖方的保留价后，市场供给和需求平衡时的最低市场出清价。定义2我们称以拍卖价p为起点，以0d为步长的任何两个相邻拍卖点为一个拍卖阶段，每个拍卖阶段可能是升价阶段也可能是卖家引入阶段（结束点除外）。本拍卖是卖方提供保留价的集中式双向拍卖，设立一个拍卖池、一个买方缓冲池和一个卖方缓冲池，统一由拍卖中心管理。拍卖中心通过下文的卖方引入规则、买方拍卖规则、拍卖升价规则和拍卖结束规则对整个拍卖过程进行管理和控制。拍卖池设定一个标称价，表示当前的拍卖阶段拍卖价。卖方竞标价（保留价）只有达到标称价的卖家才有机会进入拍卖池。令S为所有卖方的集合。针对拍卖阶段t，我们用pS代表当前已进入拍卖池中的所有卖方（保留价小于等于当前标称价）的集合，用()psQt代表该集合中当前阶段所有卖方数量；我们用eS代表当前未进入拍卖池且保留价等于标称价的所有卖方集合，用()esQt代表该集合中当前阶段所有卖方数量；用hS代表当前未进入拍卖池但其保留价大于标称价的所有卖方集合，用()hsQt代表该集合中当前阶段所有卖方数量。拍卖开始时，所有买方都进入拍卖池中，所有卖方都进入卖方缓冲池中。随着标称价的上升会不断有卖方从hS中转入eS；根据供需平衡，卖方不断从eS转入拍卖池直至供需平衡，这时拍卖结束并确定交易价为mv。针对当前标称价，认可目前的标称价的买方会继续留在拍卖池中参与拍卖，对于不认可标称价的买方，拍卖中心将其放入买方缓冲池中。买方缓冲池中的买方不能参与下一阶段拍卖但保留本阶段的交易机会；一旦有新的买方进入买方缓冲池，买方缓冲池中的原有买方就会真正退出拍卖。因此针对当前标称价我们将买方分成三类，第一类为所有认可当前标称价的买家，我们用pB代表其集合，用()pbQt代表该集合中当前拍卖阶段买方数量，该集合中的买方估价都大于等于当前标称价；第二类为认可上一阶段拍卖标称价但不认可本阶段当前拍卖标称价的买方，他们存在于买方缓冲池中，我们用pdB代表这些买家的集合用()pdbQt代表该集合中当前阶段买方数量；第三类为不认可本阶段及上一阶段拍卖标称价的买方，他们已经退出拍卖，我们用dB代表他们的集合，用()dbQt代表该集合中当前阶段买方数量。定义3我们规定拍卖池中的卖方数量首次大于拍卖池中买方时拍卖结束，这一拍卖阶段称为最后拍卖阶段tT，其当前标称价为Tp。规定1T阶段的拍卖标称价为整个拍卖的交易价，表示为mTvpd。实际操作是这样的：首次到达ppsbQQ时拍卖结束，交易价确定为mTvpd；或者首次到达ppsbQQ时拍卖结束，为保持概念的统一我们规定此阶段为1T阶段，交易价同样为mTvpd。定义4参与者的收益是参与者的估价v的函数，其中买方的收益等于买方估价iv减去拍卖交易价mv，卖方的收益等于拍卖交易价mv减去卖方估价iv。未获得交易机会的参与者的收益等于0。假设1()/()0iiv。这是个估价单调性假设，要求拍卖参与者的估价iv依其类型i严格递增。假设2任给ij，如果()()ijvv，那么()/()()/()iiijvv。该假设是一个单交叉条件的假设，要求针对所有参与者当i上升或j下降且其他参与者的类型不变时不等式严格成立。本假设说明参与者i的类型i对物品估价iv值大小的影响大于其它参与者类型j对估价iv的影响。这保证了具有最高类型的参与者其估价也最高。假设3买方的分布在{,,2,...,}Dppdpdp内且买方数量足够多，保证每个点所在的拍卖阶段都存在至少一个买方。2.2拍卖规则设计首先对卖方提交的竞拍价（保留价）进行排序。所有卖方同时提交各自的物品的竞拍价（保留价），拍卖中心针对所有保留价按照递增顺序进行排序，其中最低保留价记为p，最高保留价记为p。排序后的卖方被放入卖方缓冲池中，拍卖中心公布卖方中最低的保留价(估价)p，并将该保留价(估价)设置为最初拍卖标称价；然后买方同时对拍卖池的标称价进行竞拍。拍卖中心将所有买方放入拍卖池继续参与竞拍；如果买方不认可标称价就选择直接退出竞拍(没有进入买方缓冲池的环节，这点与中间阶段的拍卖不同)。以后每个拍卖阶段，拍卖中心都根据拍卖池中买方和卖方的数量关系，按照如下拍卖规则进行拍卖。2.2.1卖方引入规则当拍卖标称价达到缓冲池的卖方的最低保留价时，拍卖中心就从卖方缓冲池的保留价排序列表中按照从小到大的顺序选择（如果有保留价相等的就从中随机选取）卖方进入拍卖池。（1）如果拍卖池中需求等于供给，既()()ppbsQtQt，那么就停止卖方引入，按照拍卖结束规则进行处理；（2）如果拍卖池中需求大于供给，既()()ppbsQtQt，那么就重复从缓冲池中引入保留价等于该拍卖标称价的卖方，直到该保留价下的所有卖方都被引入。然后拍卖中心根据拍卖升价规则进入买方升价阶段。2.2.2买方拍卖规则根据当前拍卖标称价买方同时进行竞拍。针对拍卖池中的每个买方指定如下规则：（1）对于认可目前的标称价格的买方允许其继续参与竞拍；（2）对于不认可标称价的买方，拍卖中心首先将其放入买方缓冲池中并不允许再进入拍卖池中。同时，如果本阶段拍卖结束，那么原买方缓冲池的买方随机获得交易机会，否则原买方缓冲池的买方退出买方缓冲池进而退出拍卖。2.2.3拍卖结束规则每进入一个新的拍卖阶段，拍卖中心都要进行判断，针对拍卖阶段t如果()()ppsbQtQt那么就按如下规则进行处理：（1）当()()ppsbQtQt时，说明p状态的买卖双方数量相等（一个参与植对应一件物品），那么拍卖结束，拍卖池的买卖双方互相成交且交易价为本拍卖阶段的标称价；（2）当()()ppsbQtQt时，说明拍卖池中拍卖物品数量大于需求物品数量。此时拍卖结束，前一阶段的标称价成为交易价格并赋值给mv。拍卖池中的买方及从买方缓冲池中随机选取的()