随机算法机制设计与网络拍卖

发布时间：2018-03-27 11:49

本文选题：算法机制设计　切入点：随机算法　出处：《华东师范大学》2012年硕士论文

【摘要】：算法机制设计是计算杨理论科学和机制设计的交叉学科,是当前国际上理论计算机领域里的研究热点之一。算法机制设计的一个主要研究方向是在机制设计中引入计算复杂性理论,对于机制的复杂性进行研究分析,判断相应机制的复杂度。然而很多机制从计算效率考虑是NP难的,这样就迫使人们考虑利用近似算法中的各种技术去设计相应的机制。考虑到随机算法是近似算法中重要的技术手段,那么,对随机机制设计的研究和分析就具有很重要的理论意义和实际应用价值。在本文中,我们首先给出了随机机制设计的确定定义,然后给出了随机诚实机制存在的的充分必要条件。根据该充分必要条件,我们给出了随机算法直接转化为随机诚实机制的框架。在该框架下,我们考虑运用随机取整(Random Rounding)技术的一类算法,我们表明这些算法均可以直接转化为相应的随机诚实机制,并保持原有的近似比。作为算法机制设计的一个重要应用-拍卖设计在古罗马时期早已出现。随着互联网技术的蓬勃发展,拍卖更是融入到了普通百姓的生活中。对于像Google, Baidu, Amazon等互联网巨头来说,拍卖设计更是其主要的收入来源。同时,拍卖机制的设计,特别是近几年来兴起的基于关键词的网络广告位拍卖,也越来越受到学术界的重视。在本文的后半篇中,针对目前Google公司正在使用的广义二价(Generalized Second Price)拍卖机制,我们分析其纳什均衡(Nash equilibrium)与弱支配策略删除均衡(Weakly Dominant Elimination Equilibrium),表明该模型在两个竞拍者、两个广告位的情况下,其弱支配策略删除均衡集合为纳什均衡集合的一个子集,并且其弱支配策略删除均衡几乎均满足社会效用最大化(Social Efficiency)。
[Abstract]:Algorithmic mechanism design is an interdisciplinary discipline in computing Yang's theoretical science and mechanism design. At present, it is one of the research hotspots in the field of theoretical computer in the world. One of the main research directions of algorithm mechanism design is to introduce computational complexity theory into mechanism design, and to study and analyze the complexity of mechanism. Judging the complexity of the corresponding mechanism. However, many mechanisms are NP-hard in terms of computational efficiency. This forces people to consider using the various techniques in the approximate algorithm to design the corresponding mechanism. Considering that the stochastic algorithm is an important technical means in the approximate algorithm, then, The research and analysis of stochastic mechanism design have very important theoretical significance and practical application value. In this paper, we first give the definite definition of stochastic mechanism design. Then, a necessary and sufficient condition for the existence of stochastic honesty mechanism is given. According to the necessary and sufficient condition, we give the framework of transforming random algorithm directly into random honesty mechanism. We consider a class of algorithms using random rounding. we show that these algorithms can be transformed directly into the corresponding random honest mechanism and maintain the original approximate ratio. As an important application of algorithmic mechanism design, auction design appeared in ancient Rome. With the rapid development of Internet technology, auction has been integrated into the lives of ordinary people. For Internet giants such as Google, Baidu, Amazon and so on, Auction design is its main source of income. At the same time, the design of auction mechanism, especially the online ad auction based on keywords, has been paid more and more attention by the academic circles. In view of the generalized bivalent Second price) auction mechanism currently used by Google, we analyze its Nash equilibrium and weak dominance strategy to delete the equilibrium, Weakly Dominant Elimination equilibrium, which shows that this model is in the case of two bidders and two ad spots. Its weak domination strategy deletes the equilibrium set is a subset of the Nash equilibrium set, and its weak domination strategy delete equilibrium almost satisfies the social utility maximization and social efficiency.
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP301.6

【参考文献】