Randomized Algorithmic Mechanism Design And Online Auction

Algorithmic mechanism design is a cross disciplinary of theoretical computer sci-ence and mechanism design, and it is one of the hottest research spots in the field of theoretical computer science. One major research direction of algorithmic mechanism design is that we can bring the computational complexity theory into mechanism design to determine the complexity of the corresponding mechanisms. However, considering the computational efficiency, the complexity of many mechanisms is NP-hard, which forces us to focus on various approximation algorithms to design appropriate mechanisms, and randomized algorithms is the important technology in approximation algorithm, so it will be significant to research and analysis of the randomized mechanism design. In this paper, first, we give the definition of the random mechanism design, and then give the necessary and sufficient condition for the existence of the randomized truthful mechanisms. Ac-cording to the necessary and sufficient condition, We develop the framework of convert-ing the randomized algorithm directly into the randomized truthful mechanism. In this framework, we show that the algorithms applied by the random rounding technology can all be directly converted into truthful randomized mechanism and maintain the original approximation ratio.As one of the most direct application of algorithmic mechanism design-auction de-sign appeared in Ancient Rome times. As the Internet technology keeps on development, the auction has been integrated into the lives of ordinary people. For Internet giants like Google, Baidu, Amazon, The auction design is the main source of their income. At the same time, the auction design gets more and more attention from the academia, especially the keyword auction. In the latter half of chapter, we explore the Google's current Gen-eralized Second Price mechanism, and after analyzing the Nash equilibrium and Weakly Dominant Elimination Equilibrium under the simple Generalized Second Price model, we find that in the condition of the two agents, two slot, the GSP'Weakly Dominant Elim- ination Equilibrium is a subset of its Nash equilibrium and it almost satisfies the Social Efficiency.