英文摘要 | Online keyword advertising was inspired by search engine companies, and it is now widely applied in almost all online services. The advantages (e.g., mass audience, targeted, and measurable) of this advertising form have made it currently the most prevailing and effective online marketing instrument. It has attracted a large number of advertisers and is the major revenue source of the service providers. The prices of the keyword advertisements are determined by auction, which makes it different from the traditional posted price or negotiating transactions. The designing of this kind of auction mechanisms is a great success of the game theory and auction theory in the era of the Internet. However, the particular characteristics of this market, such as large number of participants, dynamic and repeated adjustments, and complex bidding behaviors, have generated new challenges for researchers in both academia and industry. From the point of view of game theory, the research of keyword advertising includes the following major directions: equilibrium analysis of auction mechanism, bidding strategy planning, auction mechanism designing and optimization, advertising budget allocation, etc. In this thesis, we perform analyses on all of the above challenges, and make the following researches and contributions: (1) To compute all equilibria of the generalized second-price (GSP) mechanism. We define an equivalence relation, ``same-slot'', on the space of all equilibria of the GSP mechanism, then partition the space into finite many equivalence classes. With the help this partition, we can find all equilibria of the GSP mechanism. We prove that each of this class is a convex polyhedron, the intersection of two classes is either empty or with zero measure, and the intersection of three or even more classes is definitely empty. (2) To further refine the obtained equilibria and plan bidding strategy for advertisers. We propose three refinement concepts: Weakly Stable Nash Equilibrium (WSNE), Stable Nash Equilibrium (STNE), and Risk-free Symmetrical Nash Equilibrium (RfSNE). STNE and RfSNE can be efficiently computed, thus can be used as bidding strategy. RfSNE strategy does not include over-bidding, as a result, can be safely employed to avoid malicious bids from the rivals. (3) We extend the GSP mechanism to more general linear mechanism and obtain the sufficient and necessary conditions of the existence of Nash and symmetrical Nash equilibrium of a li... |
修改评论