用户名: 密码: 验证码:
组合拍卖中竞胜标自动确定问题研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
组合拍卖,是允许竞标者将多个异质商品组合起来进行捆绑竞价的多物品拍卖方式。由于组合拍卖能给予竞标者极大的自由,能够激发竞标者的参与热情,并能有效地提高资源配置效率,同时增加拍卖收益和社会效益,所以,随着互联网的发展、商品交易的多样化,组合拍卖越来越引起人们的兴趣,成为网上拍卖理论和应用研究的热点问题之一。
     组合拍卖虽然具有很强的优势,但同时它也提出了大量的问题和挑战。其中,组合拍卖区别于非组合拍卖的一个明显特征就是组合拍卖中的计算复杂性,即组合拍卖的竞胜标确定问题。竞胜标求解已经被证明是一个NPC问题,其计算复杂性与拍卖效率之间的矛盾一直是影响组合拍卖广泛应用的主要障碍。障碍在实际问题中,可以被克服、降低或者避免。虽然克服不可避免的计算困难是很重要的能力,但是,若能利用组合拍卖问题的内在特性,采用合适的方法,依托组合拍卖的优势去降低或者避免其中的计算困难,则是最佳方法,也是有效解决WDP,促进组合拍卖在实际中广泛应用的至关重要问题之一。
     为了找到解决WDP的有效方法及全面了解WDP的研究现状,本文以“ISIWeb of Knowledge”为平台,以“winner determination problem”为关键词进行了文献搜索,对找出的删选后的101篇文献的全部摘要和部分正文进行了阅读分析,发现学者们虽然都认识到组合拍卖中实际商品的组合空间要比理论上的小得多,但是在WDP算法研究上,大多都是基于理论上如何战胜WDP的计算复杂性,而不是采用一些技巧,真正从商品实际可能出现的组合空间出发,从组合拍卖设计的优势出发,降低或者避免WDP的计算障碍。这种基于理论的要求,从各种角度包括人为限定投标空间或标的结构,对WDP进行求解的方法,由于和实际问题有不可近似性,所以影响了该理论在实际中的应用。但是这些也证明了,如果能根据组合拍卖实际问题特性,采用合适的方法,是一定可以有效解决WDP的。
     所以本文以降低或者避免WDP计算复杂性,进行定性与定量相结合的角度出发,以自动求解WDP为目的,定性分析商品的实际特征,采用可拓学中的物元模型,对商品的基本组合特征进行形式化表示,然后以投标语言表达其内在逻辑关系为基础,建立WDP的量化模型。接着,应用量性融合的NP难问题的可构造技术——有穷损害优先法构造WDP的求解过程,试图为WDP的解决寻找一个新的突破口,提供一个新的求解思路。
     首先,本文通过可拓理论,对商品及竞标人、投标行为等进行了定性分析和描述,并构建了相应的物元模型,真正表达出商品间的协同价值和竞标人偏好。根据物元模型对商品特性的描述,以具有协同价值的属性为依据,通过关联函数,构造了商品间实际可能发生的组合空间。
     其次,基于LGB投标语言,将定性分析得到的商品描述的物理模型转换为相应的逻辑模型,便于对WDP的定量分析及应用计算机进行存储与检索,以实现对WDP的自动求解。由于不同的投标结构对WDP算法的复杂度有很大影响,而树形结构已经被证明,在限定标的组合情况下,可以在多项式时间内求得最优解。因此针对上述的商品组合情况,构建其树形拓扑结构图及相应的搜索过程。
     接着,应用定性与定量方法相结合的有穷损害优先法,研究WDP的不可解度,并构造了其相对可计算性,使其可以在小于等于s步的计算时间内发现一个可计算集,在这个集合中找到每一个满足要求的有效商品组合,直至最终所找到的商品组合能够尽可能地使目标函数最大化为止。然后,本文采用了斯坦福大学开发的组合拍卖模拟测试数据平台,进行了实验验证,结果表明本文的算法是有效的。
     最后,为了更好地说明本文的思想与算法的可行性,采用了哈尔滨工业大学的一个科研项目数据,生产实际中组合拍卖的应用——医药采购招标的案例进行了分析,将依据本文方法的求解结果与实际已经发生的结果进行了比较,结果表明,二者的最终结果——获胜供应商及商品组合标的在很大程度相吻合,说明本文的思想虽然还需要进一步研究改进,但却可以在实际中有效应用,并且是能够促进组合拍卖在实践中广泛应用的有效途径之一。
Combinatorial auction is a multi-item auction which allows bidders to combine heterogeneous goods together to bid. Combinatorial auction gives much freedom to bidders and stimulates much enthusiasm.What's more,combinatorial auction can effectively improve the efficiency of resource allocation and increase the auction revenue and social benefits.With the development of the Internet and the diversification of commodity trading, combinatorial auction attracts more interest.In a word, combinatorial auction become a hot topic in online auction theory and application research.
     Through combinatorial auction has a strong advantage, it also brings a number of problems and challenges. At present, the mechanism design, bidding language and the winner determination problem (WDP) are three main issues involved in combination auctions. Mechanism design problem is the core of combinatorial auction, but by finding the optimal algorithm for winner determination problem concerns the practicality and feasibility of mechanism chosen. So winner determination problem is one of the key issues of mechanism design. Now solving winner determination problem has proven to be an NPC problem. The conflict between calculation efficiency and the auction complexity has been a major obstacle in wide application of combinatorial auction. The expression of the bidding language is premise of solution to winner determination problem and directly related to the complexity of the algorithm.So effective solution to WDP is a critical problem to promote combinatorial auction widely used in practice.
     To find an effective way to solve the WDP and comprehensive understanding of current situation, I chose ISI Web of Knowledge as platform and winner determination problem as keywords. After the election, I find101articles to analysis all abstracts and partial text. Through reading, I have a lot of thoughts. Scholars have recognized that actual commodity space is much smaller than the theoretical in combinatorial auctions, but in the WDP algorithm research, did not really arise from a combination of real commodity space. Based on theory, they solve WDP from various angles, including man-made limit space or the tender structure. These limitations cannot approximate the actual problems, so impact applications of theory in practice. But these also proved that, if the problem can be based on the actual characteristics, limiting the combinations of goods can certainly an effective solution to WDP.
     Solving WDP must be closely related with the actual problems,so I began with actual features of goods,combined qualitative and quantitative analysis methods, to try to find a new breakthrough to WDP and provide a new way of thinking.
     Firstly, I make the qualitative analysis and description on the goods, bidders and bidding behavior using extension theory and construct the corresponding element model. On this basis,these can really express synergistic value between goods and bidder's interests. According to description of element model based on product features and synergistic value to the property, through the correlation function, I construct combinational space that may occur between goods.
     Secondly,based on LGB, Physical model of goods description using qualitative analysis will change into the corresponding logical model so that we can make quantitative analysis of the WDP and solve this using computers. Because the different structure of the tender can influce greatly complexity of the WDP algorithm and the tree structure has been proven that it can be obtained in polynomial time, we can construct the tree topology and the corresponding search process.
     Thirdly, I study the degree of WDP unsolvable by using qualitative and quantitative methods combined with poor injury priority method. At the same time, I construct their relative computability so that it can find a computable set in less than or equal to s step time. I need find each effective product collection that meet the requirements, untill finally find the mix of goods that can maximize the objective function as much as possible.
     Last, in order to illustrate the feasibility of the idea and algorithm well, I have verified using the actual production of the case-bidding medical data. At the same time, I will compare the solution based on the results of this method with actual results. The results showed that the final outcome of the two-winning combination of suppliers and goods subject, to a large extent,match. This idea can be effectively applied in practice, can promote the combination of auction to be one of effective ways that widely used in practice although this idea needs to be improved further.
引文
[1]Aleksandar Peke'c, Michael H. Rothkopf. Combinatorial Auction Designs[J]. Management Science.2003,49(11):1485-1503.
    [2]Sven de Vries, Rakesh V. Vohra. Combinatorial Auctions:A Survey[J]. Informs Journal on Computing,2003,15(3):284-309.
    [3]王宏.组合拍卖的理论与实践:一个文献综述.产业经济评论[J],2009,3(1):111-146.
    [4]Rothkopf M H, Aleksandar Pekec, Ronald M. Harstard. Computationally Manageable Combinational Auctions[J]. Management Science,1998,44(8):1131-1147.
    [5]Peter Cramton,Yoav Shoham, Richard Steinberg. Combinatorial Auctions[C]. The MIT Press,2006:297-342.
    [6]T. Sandholm, S. Suri. Bob. Improved Winner Determination in Combinatorial Auctions and Generalizations[J]. Artificial Intelligence,2003,(7):33-58.
    [7]T. Sandholm. Approaches to Winner Determination in Combinatorial Auctions[J]. Decision Support Systems,2000,28(1-2):165-176.
    [8]Sandholm, T. Algorithm for Optimal Winner Determination in Combinatorial Auctions[J]. Artificial Intelligence,2002,135:1-54.
    [9]Dries R. Goossens, Rudolf Muller, Frits C. R. Spieksma. Algorithms for Recognizing Economic Properties in Matrix Bid Combinatorial Auctions[J], Informs Journal on Computing,2010,22(3).
    [10]Peter Cramton, Yoav Shoham, Richard Steinberg. An Overview of Combinatorial Auctions[J]. Acm Sigecom Exchanges,2007,10(7):1-12.
    [11]Jawad Abrache, Teodor Gabriel Crainic, Michel Gendreau, Monia Rekik, Combinatorial Auctions[J]. Ann Opereration Research,2007,153:131-164.
    [12]Craig Boutilier, Solving Concisely Expressed Combinatorial Auction Problems[J], The National Conference on Artificial,2002.
    [13]Nisan, N. Bidding and Allocation in Combinatorial Auctions[C]. In Proceedings of the2nd ACM Conference on Electronic Commerce,2004:1-12.
    [14]Minneapolis, MN. Nisan, N. The Communication Complexity of Combinatorial Auctions. Draft, Institute of Computer Science, The Hebrew University of Jerusalem,2001. Available at:http://www. cs.huji. ac.il/-noam/mkts. html.
    [15]Ma Z, Kwon RH, Lee CG. A Stochastic Programming Winner Determination Model for Truckload Procurement under Shipment Uncertainty. Transportation Research Part E-logistics and Transportation Review,2010,46(1):49-60.
    [16]Robert W. Day,S. Raghavan. Matrix Bidding in Combinatorial Auctions. Operations and Information Management,2009.
    [17]Choi HL, Brunet L, How JP. Consensus-Based Decentralized Auctions for Robust Task Allocation. IEEE Transactions on Robotics,2009,25(4):912-926.
    [18]Wang GF, Tian JX. Studies on the Winner-determination Model in Combinatorial Tendering and Bidding of Construction Project. Proceedings of2008International Conference on Construction&Real Estate Management,2008,(1-2):57-60.
    [19]Chevaleyre Y, Endriss U, Estivie S, et al. Multiagent Resource Allocation in K-additive Domains:Preference Presentation Reand Complexity. Annals of Operations Research,2008,163(1):49-62.
    [20]Lim A, Rodrigues B, Xu Z. Transportation Procurement with Seasonally Varying Shipper Demand and Volume Guarantees. Operations Research,2008,56(3):758-771.
    [21]Martin DJ, Gehrke J, Halpern JY. Toward Expressive and Scalable Sponsored Search Auctions.2008IEEE24th International Conference on Data Engineering, Vols1-3:Proceedings of The International Conference on Data Engineering (SERIES),2008:237-246.
    [22]Vig L, Adams JA. Market-based Multi-robot Coalition Formation. Distributed Autonomous Robotic Systems,2006,(7):227-236.
    [23]Kumar V, Kumar S, Tiwari MK, et al. Auction-based Approach to Resolve the Scheduling Problem in the Steel Making Process[J]. International Journal of Production Research,2006,44(8):1503-1522.
    [24]Narahari Y, Dayama P. Combinatorial Auctions for Electronic Business, sadhana-academy Proceedings in Engineering Sciences,2005,30:179-211.
    [25]Rafael Epstein, Lysette Henrquez. A Combinatorial Auction Improves School Meals in Chile:A Case of OR in Developing Countries[J]. International Transactions in Operational Research,2004,(3):593-612.
    [26]Srivinas, Tiwari MK, Allada V. Solving The Machine-loading Problem in a Flexible Manufacturing System using A Combinatorial Auction-based Approach[J]. International Journal of Production Research,2004,42(9):1879-1893.
    [27]Hsu MC, Chang PHM, Wang YM, et al. Multi-agent Travel Planning Through Coalition and Negotiation In An Auction. Intelligent Agents and Multi-agent Systems:Lecture Notes in Artificial Intelligence.2003,2891:62-73.
    [28]Bichler M, Pikovsky A, Setzer T. An Analysis of Design Problems in Combinatorial Procurement Auctions. Business&Information Systems Engineering,2009,1(1):111-117.
    [29]Dulluri S, Raghavan NRS. Allocation of Advertising Space by A Web Service Provider using Combinatorial Auctions. Sadhana-academy Proceedings in Engineering Sciences,2005,30:213-230.
    [30]Milano M, Guerri A. Bid Evaluation in Combinatorial Auctions: Optimization and Learning. Software-practice&Experience,2009,39(13):1127-1155.
    [31]Hsieh FS, Tsai SM. Hsieh FS, Tsai SM. Combinatorial Reverse Auction Based on Lagrangian Relaxation.2008IEEE Asia-pacific Services Computing Conference, Vols1-3, Proceeding,2008:329-334.
    [32]Gottlob G, Greco G. On The Complexity of Combinatorial Auctions: Structured Item Graphs and Hypertree Decompositions [C]. EC'07: Proceedings of The Eighth Annual Conference on Electronic Commerce,2007:152-161.
    [33]Chakrabarty D, Goel G. On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and Gap. Proceedings of The49th Annual IEEE Symposium on Foundations of Computer Science:Annual IEEE Symposium on Foundations of Computer Science,2008:687-696.
    [34]Sui X, Leung HF. An Adaptive Bidding Strategy in Multi-Round Combinatorial Auctions for Resource Allocation.20th IEEE International Conference on Tools With Artificial Intelligence, Proceedings Proceedings-International Conference on Tools with Artificial Intelligence,2008,(2):423-430.
    [35]Mu'alem A, Nisan N. Truthful Approximation Mechanisms for Restricted Combinatorial Auctions[J]. Games and Economic Behavior,2008,64(2):612-631.
    [36]Cheng CB. Solving A Sealed-bid Reverse Auction Problem by Multiple-criterion Decision-making Methods. Computers&Mathematics with Applications,2008,56(12):3261-3274.
    [37]Fiala P, Flusserova L. Modeling of Combinatorial Auctions in Network Economy. Proceedings of the23rd International Conference on Mathematical Methods in Economics2005,2005:87-92.
    [38]Giovannucci A, Rodriguez-Aguilar JA, Reyes A, et al. Enacting Agent-based Services for Automated Procurement[J]. Engineering Applications of Artificial Intelligence,2008,21(2):183-199.
    [39]Day RW, Raghavan S. A Combinatorial Procurement Auction Featuring Bundle Price Revelation without Free-riding[J]. Decision Support Systems,2008,44(3):621-640.
    [40]Dramitinos M, Stamoulis GD, Courcoubetis C. An Auction Mechanism for Allocating the Bandwidth of Networks to Their Users[J]. Computer Networks,2007,51(18):4979-4996.
    [41]Drexl A, Jornsten K. Reflections about Pseudo-dual Prices in Combinatorial Auctions[J]. Journal of the Operational Research Society,2007,58(12):1652-1659.
    [42]Abrache J, Crainic TG, Gendreau M, et al. Combinatorial Auctions. Annals of Operations Research,2007,153(1):131-164.
    [43]Mishra D, Veeramani D. Vickrey-Dutch Procurement Auction for Multiple Items[J]. European Journal of Operational Research,2007,180(2):617-629.
    [44]Fu LF, Feng YQ, Wu G. Mechanism Designing of Multi-unit Combinatorial Online Double Auction. Proceedings of the2006International Conference on Management Science&Engineering (13th),2006,1-3:130-134.
    [45]Shu J, Varaiya P. Smart Pay Access Control Via Incentive Alignment. IEEE Journal on Selected Areas in Communications,2006,24(5):1051-1060.
    [46]Giovannucci A, Rodriguez-Aguilar JA, Cerquides J. Multi-unit Combinatorial Reverse Auctions with Transformability Relationships Among Goods. Internet and Network Economics, Proceedings:Lecture Notes in Computer Science,2005,3828:858-867.
    [47]Conitzer V, Derryberry J, Sandholm T. Combinatorial Auctions with Structured Item Graphs. Proceeding of The Nineteenth National Conference on Artificial Intelligence and The Sixteenth Conference on Innovative Applications of Artificial Intelligence,2004:212-218.
    [48]Rao AR, Cecchi G, Peck C, et al. A Model of the Formation of a Self-organized Cortical Representation of Color. Human Vision and Electronic Imaging X:Proceedings of The Society of Photo-optical Instrumentation Engineers (SPIE).2005,5666:17-26.
    [49]Carlsson P, Andersson A. A Flexible Model for Tree-structured Multi-commodity Markets. CEC2005:Seventh IEEE International Conference on E-Commerce Technology, Proceedings,2005:50-57.
    [50]Xia M, Stallaert J, Whinston AB. Solving the Combinatorial Double Auction Problem[J]. European Journal of Operational Research,2005,163(1):239-251.
    [51]Rodriguez-Aguilar JA, Reyes-Moro A, Giovanucci A, et al. Negotiation Support in Highly-constrained Trading Scenarios. Current Topics in Artificial Intelligence:Lecture Notes in Computer Science,2003,3040:425-434.
    [52]Guerri A, Milano M. CP-IP Techniques for The Bid Evaluation in Combinatorial Auctions. Principles and Practice of Constraint Programming -cp2003, Proceedings:Lecture Notes in Computer Science,2003,2833:863-867.
    [53]Hu SL, Shi CY. The Computational Complexity of Dynamic Programming Algorithm for Combinatorial Auctions.2002International Conference on Machine Learning and Cybernetics, Proceedings,2002,1-4:266-268.
    [54]Boutilier C.Solving Concisely Expressed Combinatorial Auction problems. Eighteenth National Conference on Artificial Intelligence (AAAI-02)/Fourteenth Innovative Applications of Artificial Intelligence Conference (IAAI-02), Proceedings,2002:359-366.
    [55]Conen W, Sandholm T. Partial-revelation VCG Mechanism for Combinatorial Auctions. Eighteenth National Conference on Artificial Intelligence (AAAI-02)/Fourteenth Innovative Applications of Artificial Intelligence Conference (IAAI-02), Proceedings,2002:367-372.
    [56]Lee J, Lee SG, Lee S. A Framework of Winner Determination Algorithms for Internet Auctions. Web and Communication Technologies and Internet-related Social Issues-hsi2003:Lecture Notes in Computer Science,2003,2713:415-424.
    [57]Davenport AJ, Kalagnanam JR. Price Negotiations for Procurement of Direct Inputs. Mathematics of The Internet-E-Auction and Markets:Ima Volumes in Mathematics and Its Applications,2002,127:27-43.
    [58]Collins J, Gini M. An Integer Programming Formulation of the Bid Evaluation Problem for Coordinated Tasks. Mathematics of The Internet-E-auction and Markets:Ima Volumes in Mathematics and Its Applications,2002,127:59-74.
    [59]Jones JL, Koehler GJ. Combinatorial Auctions using Rule-based Bids[J]. Decision Support Systems,2002,34(1):59-74.
    [60]Sandholm T. Approaches to Winner Determination in Combinatorial Auctions[J]. Decision Support Systems,2000,28(1-2):165-176.
    [61]Bai JC, Ming Z. Heuristic and Algorithm for Mixed Multi-Unit Combinatorial Auctions. Proceedings of The11th Joint Conference on Information Sciences,2008:U217-U222.
    [62]Leyton-Brown K, Nudelman E, Shoham Y. Empirical Hardness Models: Methodology and a Case Study on Combinatorial Auctions. Journal of The Acm,2009,56(4).
    [63]Byde A, Kelly T, Zhou YH, et al. Efficiently Generating k-Best Solutions to Procurement Auctions. Algorithmic Aspects in Information and Management, Proceedings,2009,5564:68-84.
    [64]Chen L, Chen XY, Hu SL, et al. Hybrid Algorithm for Winner Determination Problem in Combinatorial Auctions.2008International Conference on Computational Intelligence and Security, Vols1AND2, Proceedings,2008,(1-2):645-649
    [65]Boughaci D, Benhamou B, Drias H. A Memetic Algorithm for the Optimal Winner Determination Problem. Soft Computing,2009,13(8-9):905-917.
    [66]Escudero LF, Landete M, Marin A. A Branch-and-cut Algorithm for The Winner Determination Problem[J]. Decision Support Systems,2009,46(3):649-659.
    [67]Zhang JQ, Avasarala V, Sanderson AC, et al. Differential Evolution for Discrete Optimization:An Experimental Study on Combinatorial Auction Problems.2008IEEE Congress on Evolutionary Computation:IEEE Congress on Evolutionary Computation,2008,1-8:2794-2800
    [68]Goossens DR, Spieksma FCR. Exact Algorithms for The Matrix Bid Auction[J]. Computers&Operations Research,2009,36(4):1090-1109.
    [69]Fukuta N, Ito T. Performance Analysis about Parallel Greedy Approximation on Combinatorial Auctions. Intelligent Agents and Multi-agent Systems, Proceedings:Lecture Notes in Artificial Intelligence,2008,5357:173-184.
    [70]Flusserova L, Fiala P. Winner Determination Problem. Proceedings of The25th International Conference on Mathematical Methods in Economics2007,2007:84-89.
    [71]Yang S, Segre AM, Codenotti B. An Optimal Multiprocessor Combinatorial Auction Solver[J]. Computers&Operations Research,2009,36(1):149-166.
    [72]Ozer AH, Ozturan C. A Model and Heuristic Algorithms for Multi-unit Nondiscriminatory Combinatorial Auction[J]. Computers&Operations Research,2009,36(1):196-208.
    [73]Singh RJ, Sen AK. Exploring Local Search in Winner Determination Problem[J]. Information Technology&Management,2008,9(2):105-119.
    [74]Tagashira S, Mito M, Fujita S. Towards Generic Solver of Combinatorial Optimization Problems with Autonomous Agents in P2P Networks. High-performance Computing:Lecture Notes in Computer Science,2008,4759:152-163.
    [75]Gong JW, Qi JY, Xiong GM, et al. A GA Based Combinatorial Auction Algorithm for Multi-robot Cooperative Hunting. CIS:2007International Conference on Computational Intelligence and Security, Proceedings,2007:137-141.
    [76]Zhang L, Zhang RS. The Winner Determination Approach of Combinatorial Auctions Based on Double Layer Orthogonal Multi-agent Genetic Algorithm. Iciea2007:IEEE Conference on Industrial Electronics and Applications,2007,1-4:2382-2386.
    [77]Avasarala V, Polavarapu H, Mullen T. An Approximate Algorithm for Resource Allocation using Combinatorial Auctions.2006IEEE/WIC/ACM International Conference on Intelligent Agent Technology, Proceedings,2006:571-578.
    [78]Gan RW, Guo QS, Chang HY, et al. Ant Colony Optimization for Winner Determination in Combinatorial Auctions. ICNC2007:Third International Conference on Natural Computation, Proceedings,2007,(4):441-445.
    [79]Gagliolo M, Schmidhuber J. Learning Dynamic Algorithm Portfolios. Annals of Mathematics and Artificial Intelligence,2006,47(3-4):295-328.
    [80]Gallo C. A Data Set Generation Algorithm in Combinatorial Auctions. Eurocon2005:The International Conference on Computer as a Tool, Proceedings,2005,1-2:744-747.
    [81]Narumanchi MV, Vidal JM. Algorithms for Distributed Winner Determination in Combinatorial Auctions. Agent-mediated Electronic Commerce:Designing Trading Agents and Mechanisms:Lecture Notes in Artificial Intelligence,2006,3937:43-56.
    [82]Kameshwaran S, Benyoucef L. Branch on Price:A Fast Winner Determination Algorithm for Discount Auctions. Algorithmic Aspects in Information and Management, Proceedings:Lecture Notes in Computer Science,2006,4041:375-386.
    [83]Jin MZ, Wu SD, Erkoc M. Multiple Unit Auctions with Economies and Diseconomies of Scale. European Journal of Operational Research,2006,174(2):816-834.
    [84]Tagashira S, Mito M, Fujita S. A Generic Solver Based on Functional Parallelism for Solving Combinatorial Optimization Problems[J]. Ieice Transactions on Information and Systems,2006,E89D(6),1940-1947.
    [85]Lim A, Tang JQ. A Lagrangian Heuristic for Winner Determination Problem in Combinatorial Auctions. AI2005:Advances in Artificial Intelligence:Lecture Notes in artificial Intelligence,2005,3809:736-745.
    [86]Giovannucci A, Rodriguez-Aguilar JA, Cerquides J, et al. Ibundler:An Agent-based Decision Support Service for Combinatorial negotiations. Proceeding of The Nineteenth National Conference on Artificial Intelligence and The Sixteenth Conference on Innovative Applications of Artificial Intelligence,2004:1012-1013.
    [87]Aknine S. Iterated Algorithm for The Optimal Winner Determination in Combined Negotiations. ECAI2004:16th European Conference on Artificial Intelligence, Proceedings:Frontiers in Artificial Intelligence and Applications,2004,110:949-950.
    [88]Bai JC, Chang HY, Yi Y. A Partheno-genetic Algorithm for Optimal Winner Determination in Combinatorial Auctions. Proceedings of The2004International Conference on Machine Learning and Cybernetics,2004,1-7:553-557.
    [89]Bai H, Zhang ZL. A Winner Determination Algorithm for Multi-unit Combinatorial Auctions with Reserve Prices. Proceedings of The2005International Conference on Active Media Technology (AMT2005),2005:239-243.
    [90]Jones JL, Koehler GJ. A Heuristic for Winner Determination in Rule-based Combinatorial Auctions. Informs Journal on Computing,2005,17(4):475-489.
    [91]Bai JC, Chang HY, Yi Y. An Immune Partheno-genetic Algorithm for Winner Determination in Combinatorial Auctions. Advances in Natural Computation, Pt3, Proceedings:Lecture Notes in Computer Science,2005,3612:74-85.
    [92]Koutroumbas K. Comax:A Cooperative Method for Determining The Position of The Maxima. Neural Processing Letters,2005,22(2):205-221.
    [93]Sandholm T, Suri S, Gilpin A, et al. CABOB:A fast, Optimal Algorithm for Winner Determination in Combinatorial Auctions. Management Science,2005,51(3):374-390.
    [94]Gunluk O, Ladanyi L, de Vries S. A Branch-and-price Algorithm and New Test Problems for Spectrum Auctions. Management Science,2005,51(3):391-406.
    [95]Xu JY. Dynamic Airborne Fire Control System Measurement Data Modeling. Proceedings of The Third International Symposium on Instrumentation Science and Technology,2004,(1):466-469.
    [96]Mito M, Fujita S. On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions. Journal of Heuristics,2004,10(5):507-523.
    [97]Mito M, Fujita S. On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions. IEEE/WIC International Conference on Intelligent Agent Technology, Proceedings,2003:25-31.
    [98]Chen PY, Wang DW. A Fitting-first Heuristics Embedded Chaotic Search for Winner Determination in Combinatorial Auctions. Proceedings of2003International Conference on Management Science&Engineering,2003, MI:471-474.
    [99]Sandholm T. Algorithm for Optimal Winner Determination in Combinatorial Auctions[J]. Artificial Intelligence,2002,135(1-2):1-54.
    [100]Hoos HH, Boutilier C. Solving Combinatorial Auctions Using Stochastic Local Search. Seventeenth National Conference on Artificial Intelligence (AAAI-2001)/Twelfth Innovative Applications of Artificial Intelligence Conference (IAAI-2000),2000:22-29.
    [101]Easwaran AM, Pitt J. An Agent Service Brokering Algorithm for Winner Determination in Combinatorial Auctions. ECAI2000:14th European Conference on Artificial Intelligence, Proceedings:Frontiers in Artificial Intelligence and Applications,2000,54:286-290.
    [102]Drexl A, Jornsten K, Knof D. Non-linear Anonymous Pricing Combinatorial Auctions[J]. European Journal of Operational Research,2009,199(1):296-302.
    [103]Hsieh FS, Hua CC. Decision Support for Combinatorial Reverse Auction with Multiple Buyers and Sellers. Opportunities and Challenges for Next-generation Applied Intelligence,2009,214:105-110.
    [104]Wang C, Ghenniwa HH, Shen WM. Constraint-Based Winner Determination for Auction-Based Scheduling. IEEE Transactions on Systems Man and Cybernetics Part A-systems and Humans,2009,39(3):609-618.
    [105]Juda AI, Parkes DC. An Options-based Solution to The Sequential Auction Problem[J]. Artificial Intelligence,2009,173(7-8):876-899.
    [106]Khanpour S, Movaghar A. Design and Implementation of Optimal Winner Determination Algorithm in Combinatorial e-Auctions. Proceedings of World Academy of Science, Engineering and Technology:Proceedings of World Academy of Science Engineering and Technology,2006,14:286-289.
    [107]Goossens D. Exact Methods for Combinatorial Auctions.4OR-A Quarterly Journal of Operations Research,2007,5(4):335-338.
    [108]Sandholm T. Expressive Commerce and Its Application to Sourcing:How We Conducted$35Billion of Generalized Combinatorial Auctions, ai Magazine,2007,28(3):45-58.
    [109]Demir GK, Gini M. Winner Determination for Combinatorial Auctions for Tasks with Time and Precedence Constraints. Journal of Intelligent&Fuzzy Systems,2007,18(3):267-280.
    [110]Lehmann B, Lehmann D, Nisan N. Combinatorial Auctions with Decreasing Marginal Utilities. Games and Economic Behavior,2006,55(2):270-296.
    [111]Kelly T. Generalized Knapsack Solvers for Multi-unit Combinatorial Auctions:Analysis and Application to Computational Resource Allocation. Agent-mediated Electronic Commerce Vi-theories for and Engineering of Distributed Mechanisms and Systems:Lecture Notes in Artificial Intelligence,2005,3435:73-86.
    [112]Andersson A, Holmstrom J, Willman M. An Auction Mechanism for Polynomial-time Execution with Combinatorial Constraints. CEC2005: Seventh IEEE International Conference on E-Commerce Technology, Proceedings,2005:17-24.
    [113]Bleischwitz Y, Kliewer G. Accelerating Vickrey Payment Computation in Combinatorial Auctions for An Airline Alliance. Experimental and Efficient Algorithms, Proceedings:Lecture Notes in Computer Science,2005,3503:228-239.
    [114]Jian C, He H. Research on a Range of Procurement Combinational Auction's WDP Algorithm. Management Sciences and Global Strategies in The21st Century,2004,1-2:1081-1084.
    [115]Andersson A, Tenhunen M, Ygge F. Integer Programming for Combinatorial Auction Winner Determination. Fourth International Conference on Multiagent Systems, Proceedings,2000:39-46.
    [116]Lewis DJ, Allen S. Structure Determination of The Ag-Cu-Sn Ternary Eutectic. Advanced Materials&Processes,2001,159(2):42-43.
    [117]Kothari, Anshul, Tuomas Sandholm and Subhash Suri, Solving Combinatorial Exchanges:Optimality Via A Few Partial Bids[C], in Proceedings of the ACM Conference on Electronic Commerce (ACM-EC),2003:236-237.
    [118]C. Boutilier and H. H. Hoos. Bidding Languages for Combinatorial Auctions [J]. In Seventeenth International Joint Conference on Artificial Intelligence,2001,(1).
    [119]H. H. Hoos and C. Boutlier. Solving Combinatorial Auctions using Stochastic Local Search. In Proceedings of the7th National Conference on Artificial Intelligence,2000.
    [120]黄河,徐鸿雁,陈剑.多因素采购组合拍卖获胜者确定问题研究.系统工程理论与实践,2008,(7):27-33.
    [121]陈剑,黄河.基于树型结构的在线逆向组合拍卖模型.系统工程理论与实践,2004,(8):310-315.
    [122]陈李钢.电子商务下的组合拍卖机制设计与模型优化研究.哈尔滨工业大学博士论文,2006.
    [123]陈培友,汪定伟.组合拍卖竞胜标确定问题的混沌搜索算法.管理科学学报,2003,6(5):25-29.
    [124]陈培友,汪定伟.用遗传算法求解组合拍卖竞胜标.东北大学学报(自然科学版),2003,124(1):7-10.
    [125]陈培友,汪定伟.用改进遗传算法求解组合拍卖竞胜标.东北大学学报(自然科学版),2004,125(4):349-354.
    [126]白鉴聪,常会友,衣杨.获胜者确定问题的建模与启发式算法[J].计算机研究与发展,2005,42(11):1856-1861.
    [127]Georg Gottlob, Gianluigi Greco. On The Complexity of Combinatorial Auctions:Structured Item Graphs and Hypertree Decompositions.
    [128]Vincent Conitzer, Jonathan Derryberry, Tuomas Sandholm. Combinatorial Auctions with Structured Item Graphs. Game Theory&Economic Models,2004:212-218.
    [129]Parkes DC, Rabin MO, Thorpe C. Cryptographic Combinatorial Clock-Proxy Auctions. Financial Cryptography and Data Security:Lecture Notes in Computer Science,2009,5628:305-324.
    [130]黄文奇,许如初.近世计算理论导引——NP难度问题的背景、前景及其求解算法研究[M].科学出版社,2004:71-78.
    [131]杨东屏,李昂生.可计算理论[M].科学出版社,1999,118-142.
    [132]蔡文,杨春燕.可拓学基础理论研究的新进展[J].中国工程科学,2003,(2):80-87.
    [133]蔡文.可拓论及其应用[J].科学通报,1999,44(7):673-681.
    [134]周乐欣.拍卖理论在物流交易中的应用研究[D].武汉大学,2010.
    [135]秦琴.组合拍卖赢者决定问题及其应用研究[D].湖南师范大学,2010.
    [136]贺志涛.多维网上拍卖优化机制与决策模型研究[D].哈尔滨工业大学,2009.
    [137]李翠娟.运输服务采购多属性组合拍卖策略研究[D].西南交通大学,2007.
    [138]郑珉楠.基于互联网模式的组合拍卖模型与算法研究[D].东华大学,2009.
    [139]薛晓斌.混合型多属性组合拍卖研究[D].厦门大学,2009.
    [140]李莹.组合拍卖的非合作博弈分析[D].大连理工大学,2005.
    [141]孙晓明.量子信息论与计算经济学中若干算法与复杂性问题研究,2005.
    [142]柴玉梅,岳昌应,王黎明.基于线性结构的逆向组合拍卖算法研究[J].计算机工程与设计,2010,31(2).
    [143]孙叶萌.计算网格中货物市场模型和拍卖模型的比较[D].吉林大学,2005.
    [144]黄河,陈剑.组合拍卖与议价谈判机制设计研究[J].管理科学学报,2010,13(2).
    [145]贾欣鑫,罗亮,郭丽峰,何尚录.求解组合拍卖问题的一种贪婪算法[J].温州大学学报,2009,30(3).
    [146]金星,石纯一.一种边际效用递减组合拍卖的胜者决定算法[J].计算机研究与发展,2006,43(7):1142-1148.
    [147]王飞,许肖豪,张静,陈凯.GHP时隙分配问题的组合拍卖竞胜标模型与算法[J].系统工程,2010,28(2).
    [148]甘荣伟,郭清顺,常会友,衣杨.获胜者确定问题的启发规则与改进蚁群算法[J].小型微型计算机系统,2008,(8).
    [149]黄河,陈剑,徐鸿雁.组合采购拍卖的多因素投标机制设计研究[J].中国软科学,2008,(7).
    [150]刘宝平,黄杰.基于拍卖理论的装备招标采购定价模型研究[J].武汉理工大学学报,2009,31(3).
    [151]傅丽芳,冯玉强.基于关联规则分析的组合拍卖竞胜标决定算法[J].系统管理学报,2008,17(5).
    [152]王勇,张龙勇,胡有勇.基于树形结构的物流作业反向组合拍卖[J].科技进步与对策,2009,26(23).
    [153]蒋健,闫继宏,臧希喆,赵杰.基于组合拍卖的多机器人任务死锁解决方法[J].计算机工程与应用,2008,44(4).
    [154]黄河,陈剑.采购组合拍卖投标均衡策略研究[J].系统工程理论与实践,2007,(10).
    [155]黄河,但斌,徐鸿雁.基于树形机构的采购组合拍卖获胜概率计算方法研究[J].数学的实践与认识,2008,38(1).
    [156]Beall,S.The Role of Reverse Auetions in Strategic Soureing[Z].Center for Advaneed Purchasing Studies,2003:18-30.
    [157]Hevner et al.Design Science in Information Systems Research. Mis Quarterly,2004,(3):75-105.
    [158]Leyton-brown, K., Pearson, M., Shoham, Y. Towards a Universal Test Suite for Combinatorial Auction Algorithms. ACM EC,2000. http://www. cs. ubc.ca/-kevinlb/CATS/.
    [159]Meritxell Vinyals, Andrea Giovannucc,etc.A Test Suite for The Evaluation of Mixed Multi-unit Combinatorial Auctions. Journal of Algorithms: Algorithms in Cognition, Informatics and Logic63,2008:130-150.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700