DPDI动态拍卖机制的研究与算法实现

发布时间：2018-07-07 15:42

本文选题：动态拍卖 + 机制设计　；参考：《华东师范大学》2012年硕士论文

【摘要】：拍卖是一种通用的研究许多社会经济领域问题的重要手段和工具,为理性个体代理间资源分配以及决策制定等问题提供了一个通用的实现框架。随着计算机技术的飞速发展和Internet的出现,与动态因素紧密结合的动态拍卖也被越来越多的学者以及研究机构所关注。在线广告拍卖问题关注如何将动态产生的用户搜索关注点有效地分配给数量不断变化的在线广告商。网上订票系统需要处理随机出现的买家与时间敏感的票务之间的关系。远程教育系统具有使用教育资源可动态回收与远程使用者申请随机的特性,同时需要争取实现系统服务实现整体福利最优。由此可见动态拍卖的应用场景极其广泛并具有实际意义,成为了拍卖问题研究中的热点。传统研究多关注于静态环境下拍卖理论的研究。尽管静态拍卖理论以及机制设计在解决一系列广泛多样的问题领域已经取得了相当成功的研究成果,然而由于动态环境的特殊性质,对于静态拍卖问题的研究往往不能直接转化应用到动态环境中。因此对于动态拍卖的研究既需要参考经典静态拍卖的机制设计,同时也应结合动态因素进行分析。动态拍卖所涉及的动态包括两类：动态数量(Dynamic Population),表示参加拍卖的竞拍者数量随时间发生变化的动态性；动态信息(Dynamic Information),表示参加拍卖的竞拍者私有信息随时间发生变化的动态性。目前国内外的研究分别针对这两个方面进行展开,并进一步细化分析在特定方面特定场景下的机制设计。本文不单独考虑两个动态因素中的某一个因素,而是结合动态拍卖的两个动态因素——竞拍者数量动态以及竞拍者信息动态来考虑机制设计。由于动态拍卖过程具有马尔科夫性,因此结合马尔科夫过程对该动态拍卖进行形式化描述,并在此基础上定义拍卖要素的表达式。其次,维克瑞-克拉克-格罗夫斯(Vickrey-Clarke-Groves,后文将简称为VCG)机制作为经典的符合激励兼容性的静态拍卖机制具有借鉴意义,本文将在DPDI (Dynamic PopulationDynamic Information)动态拍卖模型的基础上,将静态VCG机制与动态拍卖的动态属性相结合,设计具有激励兼容性且最大化预期社会福利的DPDI动态拍卖机制,并对其激励兼容性进行属性验证。最后,在机制实现方面,针对差异化的DPDI动态拍卖场景实现DPDI动态拍卖算法,并且对KPrice算法进行改进使其能够适应DPDI动态拍卖场景,并结合示例给出具体的操作说明。针对这两种算法进行试验模拟仿真,并结合动态拍卖中的关键指标对实验结果进行分析,总结归纳算法实现的效果以及应用特性。。本文对竞拍者数量动态且信息动态的动态拍卖场景进行了研究,构造出更具有通用性的DPDI动态拍卖模型,使得对动态拍卖机制的研究更为全面；针对两个动态属性,设计DPDI动态拍卖机制,实现动态拍卖的有效实施,使得竞拍者与拍卖者均能满足自身需求,维持动态拍卖系统的稳定均衡；最后对动态拍卖场景的模拟仿真以及实验数据分析,为拍卖系统的优化提供了调整的方向。
[Abstract]:Auction is an important means and tool to study many social and economic problems. It provides a general framework for the allocation of resources and decision making between rational individual agents. With the rapid development of computer technology and the emergence of Internet, dynamic auction with dynamic factors is becoming more and more important. The issue of online advertising auction is focused on how to effectively allocate the dynamic user search concerns to the changing number of online advertisers. The online booking system needs to deal with the relationship between random buyers and time sensitive ticketing. The distance education system has the use of education. It can be seen that the application scene of dynamic auction is very extensive and has practical significance, so it has become a hot spot in the study of auction.
Traditional research pays much attention to the study of auction theory in static environment. Although static auction theory and mechanism design have achieved considerable success in solving a series of wide variety of problems, the research on static auction can not be directly applied to the research of static auction because of the special nature of the dynamic environment. Therefore, for dynamic auction research, it is necessary to refer to the classical static auction mechanism design, and at the same time, we should combine dynamic factors to analyze.
Dynamic auction involves the dynamics of two categories: the dynamic quantity (Dynamic Population), which indicates the dynamics of the number of bidders participating in the auction with time; the dynamic information (Dynamic Information) indicates the dynamics of the changes in the private information of the bidders participating in the auction with time. The two aspect is to expand and further analyze the mechanism design under specific circumstances and specific scenarios.
This paper does not consider one of the two dynamic factors separately, but combines the two dynamic factors of the dynamic auction - the dynamic of the bidder and the dynamic of the bidder's information. Because the dynamic auction process has Markoff, the dynamic auction is formally described in combination with the Marco's process. On this basis, the expression of the auction elements is defined. Secondly, the mechanism of Vickrey-Clarke-Groves (Vickrey-Clarke-Groves, VCG) is the classic static auction mechanism that meets the incentive compatibility. This paper will be based on the basis of the DPDI (Dynamic PopulationDynamic Information) dynamic auction model. The static VCG mechanism is combined with dynamic properties of dynamic auction to design a DPDI dynamic auction mechanism with incentive compatibility and maximize the expected social welfare, and verify its incentive compatibility. Finally, in the implementation of the mechanism, the dynamic auction algorithm of DPDI is implemented for the differential DPDI dynamic auction scene, and KPri The CE algorithm can be improved to adapt to the DPDI dynamic auction scene, and give specific operation instructions in combination with the example. The experiment simulation is carried out for the two algorithms, and the experimental results are analyzed with the key indexes in the dynamic auction, and the effect and the application characteristics of the algorithm are summarized.
This paper studies the dynamic auction scene of the dynamic and dynamic auction of the bidder, and constructs a more universal DPDI dynamic auction model, which makes the study of the dynamic auction mechanism more comprehensive. Aiming at two dynamic properties, the dynamic auction mechanism of DPDI is designed to realize the effective implementation of the dynamic auction, so that the bidder and the auction will be auctioned. All of them can meet their own needs and maintain the stable equilibrium of the dynamic auction system. Finally, the simulation of the dynamic auction scene and the analysis of the experimental data provide an adjustment direction for the optimization of the auction system.
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP301.6;F713.359;F224

【参考文献】