本文選題：算法機制設(shè)計　切入點：隨機算法　出處：《華東師范大學(xué)》2012年碩士論文

【摘要】：算法機制設(shè)計是計算楊理論科學(xué)和機制設(shè)計的交叉學(xué)科,是當(dāng)前國際上理論計算機領(lǐng)域里的研究熱點之一。算法機制設(shè)計的一個主要研究方向是在機制設(shè)計中引入計算復(fù)雜性理論,對于機制的復(fù)雜性進(jìn)行研究分析,判斷相應(yīng)機制的復(fù)雜度。然而很多機制從計算效率考慮是NP難的,這樣就迫使人們考慮利用近似算法中的各種技術(shù)去設(shè)計相應(yīng)的機制�？紤]到隨機算法是近似算法中重要的技術(shù)手段,那么,對隨機機制設(shè)計的研究和分析就具有很重要的理論意義和實際應(yīng)用價值。在本文中,我們首先給出了隨機機制設(shè)計的確定定義,然后給出了隨機誠實機制存在的的充分必要條件。根據(jù)該充分必要條件,我們給出了隨機算法直接轉(zhuǎn)化為隨機誠實機制的框架。在該框架下,我們考慮運用隨機取整(Random Rounding)技術(shù)的一類算法,我們表明這些算法均可以直接轉(zhuǎn)化為相應(yīng)的隨機誠實機制,并保持原有的近似比。 作為算法機制設(shè)計的一個重要應(yīng)用-拍賣設(shè)計在古羅馬時期早已出現(xiàn)。隨著互聯(lián)網(wǎng)技術(shù)的蓬勃發(fā)展,拍賣更是融入到了普通百姓的生活中。對于像Google, Baidu, Amazon等互聯(lián)網(wǎng)巨頭來說,拍賣設(shè)計更是其主要的收入來源。同時,拍賣機制的設(shè)計,特別是近幾年來興起的基于關(guān)鍵詞的網(wǎng)絡(luò)廣告位拍賣,也越來越受到學(xué)術(shù)界的重視。在本文的后半篇中,針對目前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.
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TP301.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 蘇俊霞;蔚承建;;基于粒子群優(yōu)化算法的自動機制設(shè)計[J];計算機工程與應(yīng)用;2007年04期

2 游文霞;王先甲;馮霞;文俊浩;;機制設(shè)計理論及其在計算機網(wǎng)絡(luò)協(xié)議設(shè)計中的應(yīng)用研究[J];計算機科學(xué);2007年03期

3 郭建立;吳智博;董劍;楊孝宗;劉宏偉;;基于機制設(shè)計理論的自組網(wǎng)節(jié)點合作協(xié)議[J];計算機學(xué)報;2009年03期

4 李澤平;盧顯良;向淑文;張運生;李林;聶曉文;;一種基于誠實機制的最優(yōu)負(fù)載分配方法[J];計算機應(yīng)用研究;2009年04期

5 侯乃聰;沈向洋;;投資網(wǎng)絡(luò)廣告關(guān)鍵詞的預(yù)算分配模型及其簡化算法[J];科技導(dǎo)報;2007年10期

6 樊曉香;;任務(wù)調(diào)度問題機制設(shè)計[J];計算機技術(shù)與發(fā)展;2008年07期

，

本文編號：1671395