基于博弈论的双边拍卖交易算法研究开题报告

1. 研究目的与意义（文献综述）

双边拍卖是一个买卖商品的过程，卖家给出价格，买家给出买价，卖家最后将商品卖给合适范围内出价最高的买家。明价递增是当今双边拍卖中最常见的特性。[1]买家依次公开出价，要求每一次出价必须高于之前的价格。[2]不过也有少数例外，在荷兰式拍卖里面，参与者从一个最高价开始，之后价格依次递减，直到有一个买价愿意接受这个价格，之后一次性成交。[2]最基本的双边交易模型需要一个买家和一个卖家，这种模型也可以延伸为一个供应链，比如农民将水果卖给水果超市，水果商在水果超市批量进购水果，水果商再将水果卖给消费者。[3]这样的模型可以进一步延伸为一个任意的无回路有向图。[4]

随着社会经济的发展，双边拍卖市场机制所涵盖的范围，已经不再像几百年前一样，仅仅限于一场拍卖一个特殊的物品。在传统股票，期货市场还有网络市场上，都能看到双边拍卖机制的存在。双边拍卖交易被广泛使用，主要是由于其多种经济和社会功能，表现在以下三点：一、发现商品价值。有许多商品按照传统计价方式很难发现其真正价值（如股票），通过拍卖，由竞价的方式为这些商品找到一个确定的价格。从某种意义上来说，拍卖是发现商品价格的一种重要途径。二、优化资源配置。拍卖过程中，最后成交的买家通常是具备最佳条件以及最需要拍卖品的人，这就使得被拍卖的商品适得其所。三、降低交易成本，提高交易效率，减少交易风险。由于双边拍卖公告的发布，关于拍卖物的信息能够完全公开地传递给所有竞买人，形成同一时间、同一地点众多竞买人参与拍卖的竞争。在这个过程中，信息发布的成本低廉，而且传播速度快，拍卖品能够直接面对买家，减少了中间不必要的流通环节，从而提高了交易效率。在这个交易过程中，信息完全公开，公平公正的竞争使得竞买人不受太多因素的约束，并且竞争风险小，款到即付，信用风险也小。

几十年来来，随着世界经济的发展，商品贸易量每日剧增，单凭人力来操作某些交易市场已经显得乏力，效率低下，且易出错误。依靠计算机来处理交易，成为了新的趋势，而采用计算机来处理交易的关键，就在于设计出一套成熟可靠且高效的交易算法，这就是研究算法的意义所在。

2. 研究的基本内容与方案

基本内容：

1）阅读文献，查阅资料，研究当下主流的双边拍卖交易算法，挑选其中符合研究方向的算法作为研究对象。

2）对所挑选的算法进行双边拍卖模型的建模，构建并分析其中交易者的纳什均衡报价算法。

3. 研究计划与安排

第一阶段（第1周—第3周）：查阅相关参考资料并且完成开题报告；翻译不少于5000字的英文资料并交予指导教师检查。

第二阶段（第4周—第9周）：了解所选取的双边交易拍卖算法的特点，根据博弈论理论对其进行合理的建模，建模中各个要素符合实际，之后针对该算法研究出计算交易者纳什均衡报价的具体方法。确保该方法可行并且高效。

第三阶段（第10周—第13周）：编程实现该算法，并且验证该程序的正确性与有效性。

4. 参考文献（12篇以上）

[1] Simon Parsons, Marek Marcinkiewicz,Jinzhong Niu and Steve Phelps.Everything you wanted to know about double auctions but were afraid to (bid or) ask,2006[2]Simon Parsons,Juan A.Rodriguez-Aguilar,Iiia and Mark Klein. Auctions and Bidding-A Guide for Computer Scientists,2011[3] Bing Shi,Enrico H.Gerding,Nicholas R.Jennings. An Equilibrium Analysis of Trading Across Multiple Double Auction Marketplaces using Fictitious Play, 2015[4]Zinovi Rabinovich,Victor Naroditskiy,Enrico H, Gerding, Nicholas R.Jennings. Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types, 2012[5]T.N, Cason and D.Friedman, Price formation in single call markets.Econometrica, March 1997[6]K.Chatterjee and W.Samuelson.Bargaining under incomplete information. Operations Research, 1983[7]D.Friedman. A simple testable model of double auction markets. Journal of Economic Behavior and Organization, 1991[8]V.Krishna, Auction Theory,2nd edition,Academic Press,2009[9]B.von Stengel,Equilibrium computation for two-player games in strategic and extensive form,in:Algorithmic Game Theory,Cambridge University Press,2007[10]D.Eberly,Solving Systems of Polynomial Equations,GeometricTools,2000[11]W,Rudin, Real and Complex Analysis,McGraw-Hill,1986[12]J.Hawkin,R.Holte,D.Szafron,Automated action abstraction of imperfect information extensive-form games,in:Proceedings of the Twenty-Fifth AAAI Conderence on Artificial Intelligence, 2011[13]S.Ganzfried,T.Sandhol,K.Waugh,Strategy purification and thresholding:Effective non-equilibrium approaches for playing large games,in:Proceedings of the International Conference on Automous Agents and Multiagent Systems,2012

[14]D.Eberly. Solving Systems of Polynomial Equations,GeometricTools.2000

[15]A.X.Jiang,K.Leyton-Brown,Bayesian action-graph games,in:Advances in Neural Information Processing Systems,vol.23,Curran Associates,Inc.,2010