logo资料库

论文研究-网上双边拍卖机制设计及其实现.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.19M 资料格式：pdf 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    2 2 2 　2004 年 10 月 文章编号: 1000 6788 (2004) 10 0110 07 系统工程理论与实践 第 10 期　 网上双边拍卖机制设计及其实现 殷　红, 王先甲 (武汉大学系统工程研究所, 湖北 武汉 430072) 摘要: 　针对有多个买方和卖方参与的在线拍卖, 设计了一个双边拍卖机制, 此机制除了符合网络的特 点外, 还有如下优点: 允许参与人对多单位商品进行报价; 在时段末在线拍卖市场出清; 所有参与人都按 其对商品的真实估价进行报价; 卖方不会发生网上共谋 最后给出了此拍卖机制实现的具体数据结构和 系统框架 关键词: 　在线双边拍卖; 归一价格; 出清规则; 激励相容; 4 堆 中图分类号: 　C931; F08　　　　　　　　文献标识码: 　A 　　　 D esign of M echan ism fo r O n line Doub le A uction s: T heo ry and Im p lem en tation Y IN Hong, W AN G X ian jia (System s Engineering In stitu te, W uhan U n iversity,W uhan 430072, Ch ina) Abstract: 　T h is p ap er design s the m echan ism s fo r on line doub le auction s that adm it m u ltip le buyers and sellers to p articip ate in. Such auction m echan ism no t on ly acco rds w ith the characters of netw o rk bu t has som e m erits as fo llow s: adm itting b idding fo r the m u lti un it goods; clearing on line auction s; inducing tru thfu l revelation of values by buyers and sellers; sellers no co llu sion. T h is p ap er also gives efficien t algo rithm s and concrete system fram e fo r im p lem en tation. Key words: 　on line doub le auction s; clean ing ru le; in to heap incen tive com p atib le; 4 one p rice; tran slate 1　引言 随着 In ternet 的迅速发展, 人类许多的日常活动越来越趋于电子化, 网上拍卖作为一种重要的电子商 bay. com , O n sale. com , 中 国 的 雅 宝 (Yabuy. com ) , 酷 必 得 务活 动, 近 几 年 发 展 得 十 分 迅 速, 如 E 一方面, 网上拍卖不要求所有投标者 (Coo lB id. com ) 等拍卖网站都已经在消费品市场上占据了一席之地 共处一室同时投标, 使得拍卖的参与成本迅速降低, 同时其拍卖定价方式带有互联网鲜明的分布型和异步 性的特征, 因此网上拍卖比传统的市场拍卖更加灵活和方便; 另一方面, 在线拍卖机制也与现在网上十分 流行的固定价格机制有很大不同, 拍卖机制可以将买卖双方联系起来, 共同发现合理的价格, IBM 的研究 者认为, 在未来的 20 年内, 各种形式的拍卖机制将逐渐地代替现在的网上固定价格机制 如何设计一套与 互联网特性更相适应的网上拍卖机制, 是目前一个重要的研究课题 目前已经有一些关于网上拍卖的文献 B eam 1 等主要对现在网络上主流的英国式拍卖做了研究, 英 国式拍卖实际上是一种价格递增拍卖, 它有下面的缺点: 拍卖时间与最终的出售价成正比, 通信时间随最 终出售价的增加而成超线性的增加, 这正好与在线拍卖的实时性相冲突, 因此英国式拍卖机制并不太适合 网上拍卖 陈 2 等提出了一种逢低买入的网上拍卖机制, 在一定假设下, 逢低买入机制是弱激励相容的, 即 投标者让投标值等于他对物品的真实估价是投标者的弱占优战略, 不过逢低买入机制是建立在独立私有 收稿日期: 2003 资助项目: 国家自然科学基金 (60274048) 16 10 　　作者简介: 殷红 (1976- 先甲 (1957- ) , 男, 教授, 博士生导师, 研究方向包括博弈论、决策与对策理论等 ) , 女, 博士研究生, 主要从事博弈论和委托 代理理论的研究, Em ail: Am andayh@ 163. com ; 王 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    Λ 第 10 期 Λ 网上双边拍卖机制设计及其实现 111 估价模型和单拍卖人的基础上的, 它只适用于单边拍卖 Steven 3 等提出了一种双边拍卖的价格形成模 型, 通过观察以前的报价、成交价等历史数据, 来对当前的报价、投标价进行调整, 从而形成一个买卖双方 均满意的成交价格, 此方法是以最大化拍卖者的利润为目标, 假设买卖双方已经建立了足够的信任为基础 的, 但是他们并没有找到一种机制来保证这种买卖者之间的信任关系 B a 和W h in ston 4 等则研究了如何 建立一种网上诚信机制来保证拍卖双方之间的信任关系, 诚信机制需要有一个第三方来对不诚实的行为 进行监督并制定一些惩罚规则, 这虽然在一定程度上减少了网络欺骗, 但无疑增加了交易的时间和成本 W u rm an 等人 5 设计的拍卖机制比较适合网上双边拍卖, 它是将所有参与人的报价先进行由高到低的排 序, 然后基于第M + 1 价格来进行市场出清和交易, 这种机制只能保证对买方是激励相容的, 但不能保证 卖方一定真实地报价, 而且仅限于对单位商品的报价, 尤其对多个参与人报价相同的情况无法处理 本文针对有多个买方和卖方参与的网上在线拍卖, 设计出了一个更加符合网络特点的双边拍卖机制 此机制允许参与人对多单位商品进行报价,W u rm an 等人 5 提出可以将一个人对多单位商品的报价看成 是多个人对单位商品的报价来处理, 但是网上交易往往存在着交易成本, 所以不能简单地将他们等同起 来, 本文则采用了一种归一价格来将多单位商品报价转化为单位商品报价 本文设计的拍卖机制能够保证 另外, 此机制对所有参与人都是激励 网上拍卖实时出清, 对于达成交易的买卖双方可以随机地进行匹配 相容的 (即他们都按其真实的估价进行报价) , 并且卖方不会发生网上共谋 (即联合起来统一报高价) 最 后, 本文还给出了此拍卖机制具体的实现框架, 主要采用 4 堆数据结构来实现 2　网上双边拍卖 单边拍卖实现的是一种“一对多”的市场结构, 买卖双方总有一方具有资源的垄断优势, 而另一方具有 信息优势 与单边拍卖不同, 双边拍卖的市场结构是“多对多”, 即允许多个买方和卖方同时报价来交换某 种特定的商品, 买卖双方同时失去了各自在单边拍卖中的相对优势, 他们之间的关系变为一种供给和需求 的平等关系 网上双边拍卖不同于传统市场拍卖, 它有独特的运作方式: 在拍卖周期内, 首先由买方和卖方向网上 拍卖中心提交各自的报价和参加交易的商品数量信息, 然后由拍卖中心根据拍卖规则来匹配在线的买方 和卖方, 确定出清价格和成交的数量, 并规定交易费用和交割时间等 网上双边拍卖可以分为两种: 一种是 连续型双边拍卖 (CDA ) , 它即时匹配买卖双方以达成交易; 另一种是间隔型双边拍卖 (PDA ) , 即拍卖中心 在固定的时间间隔内, 收集买卖双方的报价信息, 确定匹配的买方和卖方, 以及他们的交易数量, 最后统一 价格进行交易 本文主要研究间隔型双边拍卖 网上交易较传统的市场交易实施起来要复杂, 为此拍卖中心需要采取向参与者收取一定服务费等方 式来保证交易的正确实施, 我们把此费用称为网上拍卖的交易成本, 它包括商品和货币的邮寄费用以及商 品质量的保证金等 在设计拍卖机制时, 我们需要作三个假设: 1) 网上拍卖采用的是密封价格拍卖的形式, 即每个参与人都根据自己对商品的估价进行独立地报 价; 2) 一个参与人在某一拍卖周期内只能有一个有效的报价, 即如果他想有一个新的报价, 必须用这个 新的报价替换旧的报价; 3) 在线拍卖的参与人都是风险规避的, 即如果有获利为负的可能, 他宁愿选择不参与 3　拍卖机制设计 3. 1　拍卖机制 假设在一个时段内有 l 个人参与网上对某种特定商品的在线拍卖, 其中有m 个人需要出售此类商品, 需要出售的商品总数为M , 另外 n = l - m 个人想购买此类商品, 此类商品的需求总量为N 每个参与人 均把自己希望交易的数量 K 和愿意交易的价格 b 提交给网上在线拍卖中心, 拍卖中心接受到的每个人的 信息是一个价格——数量对 ( b , K ) , 若商品数是正的, 表明此人是商品的买方, 那么负的商品数就代表 商品的卖方 为了便于处理, 拍卖中心需要将一个人对多单位商品的报价, 看成是多个有相同报价的人对 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    Λ Λ 系统工程理论与实践 2004 年 10 月 Λ 211 单位商品的报价 具体地, 是将卖方报价和买方报价合在一起进行从高到低的排序, 其中每个价格均按它 对应的商品数量重复排序, 由于考虑到交易成本, 所以在排序之前要先将买方的报价转化成归一价格 (详 见 3. 2) 假设按此方式进行排序后的报价集为: , b2, b2, …, b2 b1, b1, …, b1 , …, bi, bi, …, bi , …, bl, bl, …, bl . K 1 K 2 K i K l 表示报价为 bi 的参与者希望交易的商品数量 K i 其中每个人仅需要交易一单位的商品 虚拟成了有 L 个人参与的对单位商品报价的在线拍卖, 然后再按照如下的拍卖机制进行操作 的方便, 以下若无特别说明, 参与人都是指虚拟的对单位商品报价的参与人 这个报价集可以看成是L = M + N 个人的报价集合, 这样拍卖中心就将有 l 个人参与的对多单位商品报价的在线拍卖, 为了叙述 下面按照排在第M + 1 位置的价格来决定交易集, 交易集是指所有在该时段末能达成交易的卖方和 由此价格决定的交易集能保证市场出清 (详见 2. 3) , 因此我们将第M + 1 位置的价格称为出 买方的集合 清价, 下面定义出清规则 出清规则: 假设排在第M + 1 位置的价格为 bs , 那么 bs 就是所有报价中第 s 高的价格 当 bs 的报价者 是卖方时, 此时所有报价低于 bs 或与 bs 相同但排序在第M + 1 之后的卖方, 以及报价高于 bs 或与 bs 相同 但排序在第M + 1 之前的买方都进入交易集, 并且报价位于第M + 1 位置的参与者也进入交易集; 当 bs 的报价者是买方时, 交易集与上相同, 只不过报价位于第M + 1 位置的参与者不进入交易集 需要说明的 是, 报价相同的参与人之间的排序是随机的, 那么报价与 bs 相同的参与人是否能达成交易也是随机的, 但 报价为 bs 且能达成交易的人数是确定的, 此规则可以保证市场出清 拍卖周期结束时, 对所有匹配的商品还要规定它们的交易价格, 交易价格按如下的统一价格规则来计 算: 假设位于第M + 1 位置的参与人的报价为 bs , 如果此参与人是商品的卖方, 那么所有匹配的商品都统 一按 bs- 1 进行交易; 如果此参与人是商品的买方, 那么所有匹配的商品都统一按 bs 进行交易, 特殊情况 (第 M 与第M + 1 位置的报价相同) 按 bs+ 1 交易 3. 2　归一价格 由于网上拍卖的特点, 我们需要考虑交易成本, 每一对匹配的卖方和买方在交易时都需要支付交易成 本, 一般情况下匹配的双方一次交易 K 单位的商品比交易 K 次每次只交易一单位的商品所支付的成本要 高, 所以为了减少交易的成本, 我们应该给多商品报价者一定的价格优惠, 处理的方法就是将买者的报价 换算成归一价格 归一价格能够保证: 在报价相同时, 买者提交的商品需求数越多, 其归一价格越高, 达成 交易的可能性越大 1 > K N , 那么有 K , 假如买方 i 能够进入交易集, 那么他的净效用为W = K i (bi - b 归一价格的计算如下: 假设一次只交易一单位商品的交易成本是 1, 一次交易 K 单位商品的交易成 本是 假设买方 i 需要购买 K i 个单位的商品, 报价是 bi , 由统一价格规则决定的交 易价为 b 根据拍卖规则, 拍卖 中心要将他虚拟成 K i 个有相同报价只买一单位商品的买方, 假设虚拟后的报价为 b′ i , 那么买方 i 的净效 用为W ′= K i (b′ 否则, 若W > W ′, 那么多个单位商品 的买方可以联合起来, 通过报低价获利; 若W < W ′, 那么需要多单位商品的买方可以通过多次对一单位 商品进行报价每次报价相同的方式来获利, 因此只能是W = W ′, 即 K i (bi - b K i 1 , 这两种情况下的净效用应该相等 K i = K i (b′ 1, 化简后得: i - b ) - K i i - b ) - ) - K i ) - b′ i = bi + ( 1 - K i) K i i > bi i称为归一价格, 显然 b′ 　　我们把 b′ 易成交以减少交易成本, 在排序时我们需用买方的归一价格, 而非他的原始报价 方承担, 买方不承担交易成本, 因此我们不需要计算卖方的归一价格 了单位商品报价 3. 3　市场出清 在相同报价下, 为了使需求量高的买者比需求量低的买者更容 本文假设交易成本由卖 这样我们将多单位商品报价转化为 按照出清规则所决定的交易集可以保证在线交易市场出清, 也即交易集中买方和卖方达成交易的商 品数量相等 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    Λ Λ Λ 311 第 10 期 网上双边拍卖机制设计及其实现 定理 1　出清规则可以保证在线拍卖买方和卖方达成交易的商品数量相等 证明: 1) 假设排在第M + 1 位置的报价者是商品的卖方 么第M + 1 位置之前的卖方有M - 之前一共有 x + M - (y + 1) , 即 x = y + 1 M + 1 位置的报价者进入交易集, 此时交易集中有 x 个买方和 y + 1 个卖方, 市场出清 (y + 1) 个参与人, 从而M = x + M - 不防设第M + 1 位置之后的卖方有 y 个, 那 (y + 1) 个, 假设第M + 1 位置之前的买方有 x 个, 那么第M + 1 位置 由出清规则知第 2) 假设排在第M + 1 位置的报价者是商品的买方 + 1 位置之前的卖方有M - y , 即 x = y + M - 集, 此时交易集中有 x 个买方和 y 个卖方, 市场出清 y 个参与人, 从而M = x + M - 假如第M + 1 位置之后的卖方有 y 个, 那么第M y 个, 假设第M + 1 位置之前的买方有 x 个, 那么第M + 1 位置之前一共有 x 由出清规则知第M + 1 位置的报价者不进入交易 这种出清规则能保证所有报价低于 bs 的卖方, 以及报价高于 bs 的买方都进入交易集, 对于报价等于 bs 的参与人能否交易则是随机的, 但是在所有报价为 bs 的买方和卖方中能达成交易的人数是确定的, 并且当 第M + 1 位置的报价者是卖方时比是买方时多一个人交易 在这种出清规则下, 当我们把交易集还原成 实际的 l 个人的多单位商品报价时, 会发现报价为 bs 的参与人, 他的交易计划可能不能完全实现, 而只是 部分得到满足 3. 4　随机匹配成交 市场出清后, 交易中心要能够随机地匹配交易集, 这也是在线拍卖的实时性所要求的 统一的交易价, 由于存在交易成本, 和不同人交易其净利润可能不一样, 从而不能随机匹配 计算考虑交易成本下的交易价格, 以保证最后能够实时随机匹配 他们达成交易的商品数量为 K , 我们定义他们的实际交易价为 b″= b 此时如果按照 因此我们需要 对于任意一对匹配的买方和卖方, 假设 K = ( 1 - K ) , 称 1 - - ( K K K ) 为价格折扣 这样定义可以保证: 虽然卖方 j 与不同的买方交易时价格会不一样, 但不管与谁进行交易其净利润都 这是因为与更少的买方 这里, 对于交易成本 在交 因此, 只要是进入了交易集的 是一样的, 均为 K j (b 进行交易虽然节约了交易成本, 但是他的实际交易价要比与其他买方交易的价格低 我们需要做一个假定: 不管交易多少单位的商品, 节约的交易成本平摊到每单位商品上都是一样的 易成本由卖方承担的情况下, 买方不管与谁进行交易其净利润都是一样的 买方和卖方, 拍卖中心都可以将他们随机地匹配成交 1) , 其中 K j 表示卖方 j 的商品数量, bj 为其报价 bj - - 当 b 对应的报价者是买方 i 时, 此时有 b″= bi , 即买方 i 的实际交易价就是他的报价 所以对买方来 说, 当他需要的商品数量比较高时, 可以适当放低报价, 只要保证能够进入交易集, 这样当按实际交易价进 行交易时, 有可能实现他的低报价, 获得更多的净效用 因此, 这种机制鼓励买方多买, 买的越多, 其单位商 品的价格就越低, 从而在其单位商品上的获利就越大 3. 5　激励相容性分析 保证网络诚信是设计网上拍卖机制的一个重要问题, 我们设计出的拍卖机制是否适用, 关键在于当按 此拍卖机制进行运作时, 买卖双方是否能报出其对商品的真实估价, 也即以对商品的真实估价进行报价是 否是参与人的占优策略 如果一个拍卖机制能够激励买主和卖主通过真实报价来最大化他的效用, 我们就 称这个机制对买方 (或卖方) 是激励相容的 下面分析本文设计的拍卖机制的激励相容性 此时, 说真话是竞标者的占优策略 当M = m = 1 时, 本文的拍卖机制即是V ick rey 第二价格密封拍卖机制 V ick rey 6 证明了第二价格 此机制规定出价最高的投标者获得标的, 而他只需要支付第二高的 密封拍卖机制对竞标者是激励相容的 价格 因为一方面如果竞标者报出比对标的的估计更高的价格, 即使 他能够中标, 也有可能获得负的净效用; 另一方面如果竞标者报出比他对标的的估价更低的价格, 这不仅 不能够增加他的获利 (因为标的最终是按别人的报价而非他本人的报价来交易的) , 还减少了他赢得该标 的的概率, 因此竞标者只会按照他对标的的真实估价进行投标 定理 2 　在所有参与人都独立报价的情况下, 本文设计的拍卖机制对买方是激励相容的 证明　因为实际交易价等于统一价格减去价格折扣, 价格折扣与报价无关, 所以我们只需要关心统一 价格, 为简单起见, 以下证明只针对虚拟的单位商品报价 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    411 系统工程理论与实践 2004 年 10 月 1) 假设第M 与第M + 1 位置的报价不相同 另外, K s 为正 (负) 表示第M + 1 位置的报价者是买方 (卖方) 为 bs- 1 独立估价, b 是其报价, 由出清规则知 P (w in bs) P (K s > 0) + (v i - bs- 1) P (K s < 0) ] 如果第M + 1 位置的报价为 bs , 那么第M 位置的报价 假设 v i 表示买方 i 对单位商品的 b = bs) = 0 , 他的期望效用 V i为: V i = P (b > bs) [ (v i - 当 v i bs- 1时, 由 bs- 1 > bs可知 v i - bs- 1 和 v i - bs均非负, 此时买方总是希望最大化赢得商品的概率, 如果买方按其真实估计进行报价, 即 b = v i , 那么 P (b > bs) = 1 , 买方获得了最大的期望效用; 当 bs- 1 > bs 时, v i - bs- 1为负, v i - bs 非负, 因为拍卖参与者都是风险规避的, 也即当买方有可能获得负的效用 v i 时, 他宁愿选择不交易, 所以买方的最佳策略是让 b = v i , 此时有 P (b = bs) = 1, P (b > bs) = 0 , 买方获得 零效用; 如果 v i < bs, 那么 v i - bs- 1 和 v i - bs 均为负, 此时买方希望最小化赢得商品的概率, 只有当 b = v i 时, 赢得商品的概率最小 (为 0) 因此, 不管买方对商品的估计如何, 买方按其真实估计进行报价总是最优 的, 即真实报价是买方唯一的占优策略 2) 第M 与第M + 1 位置的报价相同, 此时 P (w in b = bs) > 0 , 买方 i 的期望效用为: V i = P (b > bs) P (K s > 0) + P (b = bs) P (w in b = bs) ] (v i - bs+ 1) + P (b > bs) P (K s < 0) ] (v i - bs- 1). bs- 1时, 由 bs- 1> bs 可知 v i- bs- 1和 v i- bs+ 1均非负, 此时买方总是希望最大化赢得商品的概率, 如果 当 v i 让 b= v i, 那么 P (b> bs) = 1, 买方获得了最大的期望效用; 当 bs- 1> v i bs+ 1时, v i- bs- 1为负且 v i- bs+ 1非负, 此时买方希望最大化获得 v i- bs+ 1的概率且最小化获得 v i- bs- 1的概率, 当买方按其真实估计进行报价时 可以达到这个目的, 因为当 b= v i时有 P (b> bs) = 0 和 P (b= bs) > 0, 买方获得严格正的效用; 当 v i< bs+ 1 时, v i- bs- 1和 v i- bs+ 1均为负, 若让 b= v i 可使得赢得商品的概率最小 (为 0) 因此, 不管买方对商品的估计 如何, 买方按其真实估计进行报价总是最优的 定理 3　在所有参与人都独立报价的情况下, 本文的拍卖机制对卖方是激励相容的 证明　这里仅对定理 2 中的第一种情况进行证明, 另一种情况类似可证 假设卖方 i 对单位商品的独立估价是 u i, 报价是 b , 由出清规则知 P (w in b = bs) = 1 , 则他的期望效 用U i为: U i = P (b < bs) + P (b = bs) P (K s > 0) (bs - u i) + P (K s < 0) (bs- 1 - u i) ] bs) 最大为 1; 当 bs < u i bs 时, bs- 1 - u i和 bs - u i 均非负, 此时卖方希望最大化赢得商品的概率, 若他按其真实估计进行报 当 u i 价即 b = u i时, 赢得商品的概率 P (b bs- 1 时, bs- 1 - u i非负、bs - u i 为负, 如果 卖方报价比其真实估计低, 那么一定有 P (b < bs) > 0 , 即卖方有严格正的可能性获得负的净利润, 而拍卖 参与者是风险规避的, 此时卖方宁愿没有赢得拍卖, 而只获得 0 保留收益, 若按真实估价进行报价可以保 证他获得 0 收益; 当 u i > bs- 1 时, bs- 1 - 因此, 不管卖方对商品的估计如何, 按其真实估计进行报价时总是最优的, 即真实报价是卖方唯一的占优策略 3. 6　网上共谋 u i 均为负, 若让 b = u i 则赢得商品的概率最小 u i 和 bs - 对于网上拍卖, 我们还需要探讨在本文的机制下, 买卖双方是否会进行网上共谋, 也就是说是否会出 在本文的机制下, 对于提交的商品数比较高的买 但对于卖方, 他需要承担交易成本并且实际交易价 现多个买方 (或卖方) 联合起来统一报低 (或高) 价的问题 方, 可以享受到优惠价格, 因此买方可能出现网上共谋 也是按对买方有利来设计的, 所以卖方不存在通过欺骗来获利的空间 定理 4　如果交易成本由卖方承担, 在统一价格机制下, 当按实际交易价 b″进行交易时, 卖方不会发 K ) 对称地, 如果交易成本由买方承担, 在统一价格机制下, 当按交易价 b″= b + ( 1 - K 生网上共谋 进行交易时, 买方不会发生网上共谋 4　算例 　　假设网上正在对某种商品进行拍卖, 现有 7 个在线的买方: A 、B 、C 、D 、E 、F 、G , 他们的报价依 次为: (8, 1)、(10, 1)、(13, 2)、(14, 1)、(16, 1)、(18, 2)、(20, 1) , 有 7 个在线的卖方: H 、P 、Q 、U 、V 、W 、X , 他们的报价依次为: (9, - 1)、(11, - 1)、(13, - 1)、(15, - 1)、(17, - 1)、(19, - 1) 、(21, - 1) , 其中 C © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    Ζ 第 10 期 网上双边拍卖机制设计及其实现 511 设单位商品的交易成本是 1, 两单位商品的交易成本是 1. 5, C 的归一价格为 13 + 和 F 均买两单位商品 13. 25 , F 的归一价格为 18. 25, 此时报价集为 {21, 20, 19, 18. 25, 18. 25, 17, 16, 15, 14, 13. 25, 13. 0. 25 25, 13, 11, 10, 9, 8} , 出清价为 15, 即 bs = 15 , M = 6 , 按照上面的出清规则, 此时买方交易集为 {16, 18. 25, 18. 25, 20} , 卖方交易集为 {9, 11, 13, 15} , 两交易集的商品数量相等, 最后买方 E 、F 、G 和卖方 H 、 这里我们假设交易成本由卖方承担, 则 F 的交易价为 15 - 0. 25 = 14. 75 , 从而 F 和 P 、Q 、U 赢得拍卖 H 、P、Q、U 中的任意两人匹配以 14. 75 成交, E 、G 和 H 、P 、Q 、U 中的另外两人以 15 成交 由于已经 考虑了交易成本, 卖方的利润是一样的 5　系统实现 目前对拍卖机制的研究只限于理论上, 很少讨论其实现 但对于网上在线拍卖, 设计的机制是否能实 现以及实现的效率问题是衡量此机制优劣的一个重要因素, 因此需要对本文提出的拍卖机制进行一些算 但是, 规则的合理性往往和操作的复杂性之间不能很好的统一, 这就要求我们在不 法设计和复杂性分析 违背规则的条件下设计一些好的算法来实现他们之间的统一 为此本文采用了 4 堆的数据结构, 能快速实 现前文提出的在线拍卖机制 5. 1　系统框架 根据前文设计的拍卖机制, 在线拍卖中心要依次完成以下操作: 1) 插入 删除: 当出现新的参与人报价时, 将其报价插入到数据结构中; 当参与人退出拍卖时, 删除其 对于买方参与人, 我们先计算其归一价格, 再 报价; 当参与人更改其报价时, 插入新的报价, 删除旧的报价 把归一价格看作单位商品的报价插入到数据结构中 2) 出清: 决定出清价, 并给出交易集 3) 交易: 随机匹配交易集中的买方和卖方, 确定其交易的商品数量, 计算其交易价, 并将所有的报价 删除, 准备下一轮拍卖 5. 2　4 堆方法 由于拍卖中心需要对报价进行排序, 所以可以直接用有序表的数据结构, 但是表的插入和删除速度较 慢, 这里采用 4 堆的数据结构来管理报价数据, 将不同的报价放到四个不同的堆中, 这四个堆分别是: 1) B in : 包含所有在当前交易集内的买方报价, 最低的报价在堆的最上面, 此堆的大小是 O (m in (M , N ) ) , M , N 是当前买方和卖方的数量; 2) B ou t: 包含所有不在当前交易集内的买方报价, 最高的报价在堆 的最上面, 此堆的大小是O (N ) ; 3) S in: 包含所有在当前交易集内的卖方报价, 最高的报价在堆的最上面, 此堆的大小是O (m in (M , N ) ) ; 4) S ou t : 包含所有不在当前交易集内的卖方报价, 最低的报价在堆的最上 面, 此堆的大小是O (N ) 仍以前面算例中的数据为例, 则四个堆之间的关系如图 1 所示 图 1　 四堆报价关系图 我们知道每个堆内部的数据结构都是一个完全二叉树, 完全二叉树具有自动排序的功能, 且插入、删 除十分快速方便 © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    2 为了保证设计的拍卖机制能够实现, 4 堆方法必须满足两个约束 一个约束是 B in 中的报价数量必须 与 S in中的完全相等, 这样才能保证交易集中需要交易的商品能够正好匹配; 另一个约束则是由每个堆的 顶节点数据来描述的, 令 bin, bou t, sin和 sou t分别是B in, B ou t, S in和 S ou t的顶节点, V a lue (n) 是节点 n 的值, 那 么下面的条件需要被满足: V a lue (sin) 3) V a lue (sou t) V a lue (bou t) ; (4) V a lue (bin) 1) V a lue (bin) V a lue (bout) ; 2) V a lue (sou t) V a lue (sin) . 5. 3　实现过程 611 系统工程理论与实践 2004 年 10 月 根据前面的系统框架, 利用 4 堆数据结构, 拍卖机制的具体实现如下: 1) 插入 当一个新的报价加入时, 必须决定此报价添加到哪个堆中, 以图 1 中的数据为例, 假设新加 入了一个卖方报价 snew = ＄13, 显然 snew 应该添加到 S in 中, 这是为了保证 S in和B in中的报价数量相等, 还必 须把B ou t的顶节点取出, 加到B in中去 一般情况下, 当一个新的卖方报价 snew 加入时, 有三种可能的操作: ①形成一个新的交易集, 将 B ou t 的 顶节点移到 B in; ②将 snew 加入到 S in中; ③将 snew 直接加入到 S out 中 当一个新的买方报价 bnew 加入时, 方法完全相似 2) 删除 删除某个节点前, 首先要找到此节点, 这在一个堆内是很快的 如果要删除的报价在 ou t 堆 中, 可以直接删除; 如果要删除的报价在 S in 或 B in中, 在删除此报价后, 我们还必须移动另一个 in 堆的顶 节点到它相应的 ou t 堆中, 以保证交易集能够匹配 3) 出清和交易 由于在拍卖过程中, 我们能保证交易集中买卖双方需要交易的商品数量始终相等, 所 = 按照前面的方法计算出相应的交易价, 然后 S in和 B in中的参与人随机地匹 按出清规则, 出清价即为 sin, bou t中的最大值: b 以只需依据每个堆的顶节点的报价就可得出出清价 m ax (V a lue (sin) , V a lue (bou t) ) 配成交 5. 4　系统复杂性分析 在系统实现过程中, 插入一个新报价所需 要的时间最多为 O (logL ) , L 为四个堆的总大 小, 在最坏情况下, 删除堆中任意节点所需要的 时间为 O (logL ) , 计算出清价所需要的时间为 O (m in (M , N ) ) , M , N 为需要交易的商品数 量 插入 删除 出清 表 1　系统复杂性对比表 采用的数据结构 4 堆 O (log L ) O (log L ) 有序表 O (L ) O (L ) O (m in (M , N ) ) O (m in (M , N ) ) 在同等条件下, 如果采用有序表的数据结 构, 插入一个新报价所需要的时间为 O (L ) , 删 除任意节点所需要的时间为O (L ) , 计算出清价所需要的时间为O (m in (M , N ) ) 详见表 1. 因此采用 4 堆的数据结构不仅能很好地实现拍卖机制, 其实现效率也比同类方法高 6　总结 网上拍卖作为一种重要的电子商务活动, 近几年发展得十分迅速, 因此对网上拍卖理论的研究成为了 本文设计了一个在线双边拍卖机制, 允许参与人对多单位商品进行报价, 更加符合网上拍 一个热点问题 卖的特点 文章还 给出了此拍卖机制具体的实现框架, 采用 4 堆数据结构可以方便地实现此拍卖机制, 还大大提高了系统的 效率 本文设计的拍卖机制能够保证在线拍卖市场出清, 并且对所有参与人都是激励相容的 因此本文在理论和实践上对网上拍卖都有一定的指导意义 参考文献: 1 　B eam C, Segev A , Shan th ikum ar J G. O p tim alD esign of In ternet based A uction s[R . F isger Cen ter fo r Info rm ation T echno logy &M anagem en t, H aas Schoo l of B u siness, U n iversity of Califo rn ia, B erkeley, W o rk ing Pap er 98- W P- (下转第 121 页) 1034. 1998. © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    2 第 10 期 费率结构对证券投资基金风险承担行为的影响研究 121 　　由于线性的费率结构比较常用也易于分析, 因此在本文中我们以一类线性的基金费率为对象, 研究了 我们的研究发现, 随着基金管理费率不对称程度的增加, 基金经理 费率结构对基金风险承担行为的影响 特别地, 当因基金的收益小于市场组合的收益而 所选择的投资组合也将更大程度地偏离基准即市场组合 对基金经理的处罚为 0, 即基金管理费率不对称程度最大时, 基金组合将完全偏离市场组合 同时我们还 发现, 基金经理风险规避系数越小、对基金经理因基金收益超过市场收益所得的奖励程度越小, 以及证券 A 相对市场组合的收益越大而波动越小, 则基金组合偏离市场组合的程度也将越大 我们的研究还表明, 基金组合偏离市场组合不一定导致基金收益的方差的增加, 这说明在以前一些实证研究文献中用基金收 益的方差来度量基金的风险不一定有效, 用基金组合偏离基准组合的程度来度量基金的风险更合适 参考文献: 1 　 Grinb latt M , T itm an S. A dverse risk incen tives and the design of p erfo rm ance based con tracts [J . M anagem en t Science, 1989, 35 (7) : 807- 822. 2 　Stark s L au ra T. Perfo rm ance incen tives fees: an agency theo retic app roach [J . Jou rnal of F inancial and Q uan titative A nalysis, 1987, 22 (1) : 17- 32. 3 　O u Yang H u i. O p tim al con tracts in a con tinuou s tim e delegated po rtfo lio m anagem en t p rob lem [J . T he R eview of F inancial Studies, 2003, 16 (1) : 173- 208. 4 　D as San jiv R , R angarajan K Sundaram. O n the regu lation of fee structu res in m u tual funds [ R . N ew Yo rk U n iversity, 1998. 5 　D iao X ifeng. A symm etric fund m anager com p en sation and equ ilib rium asset p ricing: T heo ry and evidence from Ch ina [R . U n iversity of B rith ish lo lum b ia, 2003. 6 　Cuoco Dom en ico, Ron Kan iel. Equ ilib rium p rices in the p resence of delegated po rtfo lio m anagem en t[R . U n iversity of T exas at A u stin, 2001. 7 　Chen H L , Pennacch i G. Does p rio r p erfo rm ance affect a m u tual fund’s cho ice of risk? T heo ry and fu rther em p irical evidence[R . U n iversity of Illino is, 2002. 8 　B row n Keith C, H arlow W V , L au ra T. Stark s. O f tou rnam en ts and tem p tation s: A n analysis of m anagerial incen tives in the m u tual fund indu stry[J. Jou rnal of F inance, 1996, 51 (1) : 85- 110. 9 　B u sse Jenn ifer. A no ther look at m u tual fund tou rnam en ts[J. Jou rnal of F inancial and Q uan titative A nalysis, 2001, 36 (1) : 53- 73. (上接第 116 页) 2 　Chen J , Chen X, Song X. B idder’s strategy under a k ind of on line auction group buying [J . Ch inese Jou rnal of M anagem en t Science, 2002, 5 (10) : 1- 7. 3 　Steven G, John D. P rice Fo rm ation in Doub le A uction s [R . Econom ics D ep artm en t of W ash ington U n iversity. , W o rk ing Pap er, Feb, 2003. 4 　B a S, W h in ston A B , Zhang H. B u ilding tru st in on line auction m arkets th rough an econom ic incen tive m echan ism [J. D ecision Suppo rt System s, 2003, 35 (3) : 273- 286. 5 　W u rm an P R , W alsh W E, W ellm an M P. F lex ib le doub le auction s fo r electron ic comm erce: T heo ry and im p lem en tation[J. D ecision Suppo rt System s, 1998, 24 (1) : 17- 27. 6 　V ick rey W. Coun ter sp ecu lation, auction s, and com p etitive sealed tenders[J . Jou rnal of F inance, 1961, 16 (1) : 8- 37. © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料