Gotowa bibliografia na temat „Sponsored Search Auctions”

Recently there is an increase in smaller, domain-specific search engines that scour the deep web finding information that general-purpose engines are unable to discover. These search engines play a crucial role in the new generation of search paradigms where federated search engines (FSEs) integrate search results from heterogeneous sources. In this paper we pose, for the first time, the problem to design a revenue mechanism that ensures profits both to individual search engines and FSEs as a mechanism design problem. To this end, we extend the sponsored search auction models and we discuss possibility and impossibility results on the implementation of an incentive compatible mechanism. Specifically, we develop an execution-contingent VCG (where payments depend on the observed click behavior) that satisfies both individual rationality and weak budget balance in expectation.

To realize the specific results in the sponsored search auctions, most advertisers submit particular bid prices. The bidding behaviors with specific purposes are called as the strategic bidding. However, some strategic bidding behaviors will result in negative effects, such as the elimination of the equilibrium and the payment increase for some advertisers. The bidding behaviors with negative results are termed as the vindictive bidding. We survey four strategic bidding behaviors which include a rational bidding and three vindictive bidding strategies. In this paper, we study the relationship between the effects resulted by the vindictive bidding and the valuations of the vindictive advertisers. In our experiments, the search engine provider (SEP) is benefited by all vindictive bidding behaviors, and the increment of the SEP's revenue is proportional to the degree of the vindictiveness. Bidding vindictively without sacrificing the own utility improves the advertiser's utility with high probability. Moreover, we observe that the SEP's revenue is improved by the following situations. First, the vindictive advertiser with low valuation in the keywords with high market value results in more SEP's revenue than that in the keywords with low market value. The second case is to raise the bidding competition between advertisers.

Cette thèse regroupe trois essais en théorie des enchères. Le chapitre 1 introduit de ladélégation dans le mécanisme d’enchère GSP. Dans un jeu impliquant des transferts monétaires et unepolitique de rémunération mise en place par une agence, un équilibre collusif efficace est atteint.Nousproposons une caractérisation du profil d’enchères collusif implémentable dans un jeu de positions `a troisjoueurs et deux positions. Le chapitre 2 considère des ventes séquentielles d’un objet `a deux acheteurs: l’unconnaît son évaluation privée tandis que l’autre non. Les acheteurs ont une demande multi-unitaire et lesévaluations privées entre unit´es sont parfaitement corrélées. Un équilibre asymétrique existe dans lequelle joueur non-informé adopte une stratégie agressive tandis que le joueur informé joue de manière prudente.Le comportement du joueur non-informé est justifié par l’opportunité d’acquérir de l’informationgratuitement. Cette dynamique induit une décroissance des prix entre les ventes. Le chapitre 3, introduitun jeu de décision séquentielle dans la première enchère. Un équilibre séparateur existe dans lequel lejoueur informé est agressif lorsqu’il est le premier `a jouer impliquant une stratégie de non-participationde la part de son concurrent non-informé. A l’inverse, ce dernier adopte une attitude plus prudentelorsqu’il est le premier `a joueur. Un équilibre mélangeant dans lequel le joueur informé cache son informationprivée ne peut exister que si le joueur non-informé adopte une stratégie de non-participation
This thesis is a collection of three essays in theoretical auction analysis. Chapter 1 considersbid delegation in the GSP auction mechanism. In a game involving side-contracts and a compensationpolicy set by an agency, the first-best collusive outcome is achieved. We offer a characterization of the implementablebid profiles for the two-position game with three players. Chapter 2 considers the sequentialsale of an object to two buyers: one knows his private information and the other buyer does not. Buyershave a multi-unit demand and private valuations for each unit are perfectly correlated. An asymmetricequilibrium exists when the uninformed player adopts an aggressive bidding strategy. Conversely, hisinformed opponent behaves more conservatively by using bid shading. The bidding behaviour of theuninformed bidder is driven by the opportunity to learn his private valuation for free. This dynamic is atthe root of the decline in the equilibrium price across both sales. In chapter 3, information is observableduring the first-stage auction in a sequential-move game in which the first-mover bidder is observed byhis opponent. A separating equilibrium exists in which the informed bidder bids aggressively when he isthe first-mover which entails a non-participation strategy from his uninformed competitor. Conversely,the latter adopts a conservative behaviour when he is the first-mover. A pooling equilibrium in which theinformed bidder blurs his valuation can only exist if his uninformed opponent adopts a non-participatingstrategy

In online sponsored searches, the advertisers participate in a sequence of multi-keyword sponsored search auctions, and their bidding behaviour can be analysed as a non-cooperative stochastic differential game. Each advertiser has a two-dimensional cost and valuation state. The underlying cost dynamics are modelled by a Markovian deterministic process driven by an optimal feedback control based on an analysis of competitors' behaviour. The underlying valuation dynamics are modelled by a stationary stochastic process, which can be estimated from the users' behaviour by using statistical tools. Though the induced dynamic game is complex, we can simplify the analysis of the market using an approximation methodology known as mean-field games. The methodology assumes that advertisers optimise only with respect to the distribution of other advertisers' two-dimensional states. The problem can be broken down into two coupled PDEs, where an individual advertiser's optimal control paths are analysed by solving a Hamilton-Jacobi-Bellman equation, and the evolution of joint distribution of costs and valuations is characterised by a Fokker-Planck equation. Closed-form analytic solutions are not available, however, I apply numerical methods to compute both stationary and time-dependent distributions, as well as the optimal controls. The best response bidding strategies are then determined from the optimal controls by solving a mixed-integer nonlinear problem. I prove the existence and uniqueness of the stationary mean-field game equilibrium. It is also demonstrated that the mean-field game equilibrium is a reliable approximation of a rational advertiser's behaviour, in the sense that when the other advertisers use the mean-field game equilibrium in the finite stochastic differential game, the advertiser's best response is also to use the mean-field game equilibrium.

Orientador: Flávio Keidi Miyazawa
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-23T01:59:45Z (GMT). No. of bitstreams: 1 Pereira_ViniciusdeNovaesGuimaraes_M.pdf: 1343382 bytes, checksum: e44e4ecf8abf29e4b44af22979e1269b (MD5) Previous issue date: 2013
Resumo: Uma das fontes de receita mais lucrativas da internet são os anúncios para sites de busca. O crescimento deste mercado bilionário foi, em média, 20% ao ano nos últimos anos. Como o público alvo e variedade de anunciantes deste mercado são grandes e diversificados, um pequeno aumento da eficiência deste mecanismo representa um grande aumento de receita para os sites. Neste trabalho discutimos a evolução dos mecanismos usados neste mercado, identificando as razões destas mudanças. Avaliamos os mecanismos usados atualmente, modelando-o de formas diferentes e calculando o seu preço da anarquia
Abstract: Sponsored search auction is one of the most profitable sources of revenue on the internet. The growth of this market was, on average, 20% per year over the past years. Since the target audience and advertiser variety are big and diverse, a small increase in efficiency in this mechanism can bring a huge increase in the sites profits. In this work we discuss the evolution of the mechanisms used in this market, identifying the reasons of these changes. We evaluate the currently used mechanism, modeling in different ways and calculating the price of anarchy
Mestrado
Ciência da Computação
Mestre em Ciência da Computação

碩士
國立中正大學
資訊工程所
98
Generalized second price is not a dominant strategy in sponsored search auction, so advertisers may reduce the bids to improve their utilities, and that may reduce the search engine’s revenue. Thus, to improve the revenue of search engine, we impose two restrictions on the advertisers. First, the advertiser cannot bid the value which is less than the previous bid. Second, the advertiser is to bid the value which is no less than the previous bid plus the minimum increase price (MIP), if he wants to raise bid. To decide the sizes of the MIPs, we consider two strategies: fix strategy and adaptive strategy. The latter strategy has two policies: common MIP and respective MIP. Fix strategy fixes the size of the MIP throughout the MRSSA, and adaptive strategy adopts additive increase/ multiplicative decrease (AIMD) to modify the sizes of the MIPs. Common MIP is that the sizes of the ads’ MIPs are the same, and respective MIP is that each ad has his own MIP. Our simulation results of those strategies show that, first, search engine will obtain a lower revenue if we adopt the fix strategy and set a larger MIP. Second, the adaptive strategy resolves the low revenue problem of the fix strategy with large MIP, and slightly accelerates the advertisers’ bidding.

The on-line advertising market involving displaying of Ads against search results by a search engine is growing at a fast rate. A majority of the search engine companies sell their advertising space through auctions which are popularly called sponsored search auctions. In the face of fierce competition, each search engine company faces the threat of its advertisers switching to an alternative search engine in quest of better bang-per-buck. In order to retain customers, the search engine companies have introduced many utilities such as bid optimizer, ad slotting, and budget optimizer to promise enhanced bang-per-buck to the advertisers. The focus of this work is on the bid optimizer which is a software agent that automatically chooses bid values on behalf of the bidders. Bidders will provide a target budget to exhaust and a maximum bid value (willingness to pay). The bid optimizer aims to maximize the bang-per-buck by adjusting the bid amount based on the projected keyword traffic and remaining budget. In this thesis, we develop a novel bid optimizer based on Nash bargaining theory. The thesis is in two parts. In the first part, we address continuous bids while in the second part, we address discrete bids. Our formulation consists of a two person Nash bargaining model, where, the auctioneer is one player and a virtual aggregated agent representing all the n bidders is the other player. In the continuous bids case, the Nash bargaining formulation leads to a convex hull of the utility space of these two players. We show that this convex hull has exactly three corner points which can be computed in O(nlogn) time. Next, we show that the Nash bargaining solution, a point in this convex hull can be mapped to a bid profile of the bidders in O(n) time. Such a bid profile happens to be a local envy-free equilibrium of the underlying game that gets induced among the bidders due to the combined effect of auction rules and the bid optimizer. In the discrete bids case, we show that the Nash bargaining solution always lies on a certain edge of the convex hull such that one end point of the edge is the vector of maximum willingness to pay of all the bidders. We show that the other endpoint of this edge can be computed as a solution of a linear programming problem. We also map this solution to a bid profile of the bidders. For both continuous bids and discrete bids, we describe an algorithmic approach for implementing our idea. We also show experimentally that the proposed bid optimization algorithm, in conjunction with the generalized second price (GSP) auction as the underlying mechanism, outperforms the GSP when we take into account the realistic possibility of bidders dropping from the auction.

博士
國立中正大學
資訊工程研究所
102
In the current online advertising industry, the sponsored search auction (SSA) with the generalized second price (GSP) strategy is the most popular advertising application. The SSA combines Internet search with advertising service to recommend advertisements interested by the Internet users. To enhance the robustness of the SSA, we take into account the following issues: 1) the computation efficiency in determining winners as the advertisers have various valuations, 2) the outcome satisfaction between the SSA participants, and 3) the outcome fairness for advertisers with different bidding strategies. First, we apply the rank-by-bid principle to the English auction-based SSA to improve the computation time in determining winners. The proposed mechanism not only maintains the easy implementation of the English auction, but also provides the lower bound of revenue for the search engine provider (SEP). Next, we study the balance outcome that is accepted by the SEP and advertisers simultaneously. We investigate six factors to formulate the outcome satisfaction for the SEP and advertisers. Then, five similarity/distance measurement approaches are applied to estimate the way of realizing balance outcomes. In the end of this study, we measure the negative effects resulted from the vindictive bidding, and provide an auction mechanism to detect and correct vindictive bidding behaviors. From our theoretical analysis and simulation experiment, the proposed mechanisms provide efficient process for determining winners, balance outcomes accepted by the SEP and advertisers simultaneously, and fair and stable outcomes. This study is important in the implementation consideration since the proposed mechanisms take advantage of the properties applied in the real world environment.

Central to the explosive growth of the Internet has been the desire

of dispersed buyers and sellers to interact readily and in a manner

hitherto impossible. Underpinning these interactions, auction

pricing mechanisms have enabled Internet transactions in novel ways.

Despite this massive growth and new medium, empirical work in

marketing and economics on auction use in Internet contexts remains

relatively nascent. Accordingly, this dissertation investigates the

role of online auctions; it is composed of three essays.

The first essay, ``Online Auction Demand,'' investigates seller and

buyer interactions via online auction websites, such as eBay. Such

auction sites are among the earliest prominent transaction sites on

the Internet (eBay started in 1995, the same year Internet Explorer

was released) and helped pave the way for e-commerce. Hence, online

auction demand is the first topic considered in my dissertation. The

second essay, ``A Dynamic Model of Sponsored Search Advertising,''

investigates sponsored search advertising auctions, a novel approach

that allocates premium advertising space to advertisers at popular

websites, such as search engines. Because sponsored search

advertising targets buyers in active purchase states, such

advertising venues have grown very rapidly in recent years and have

become a highly topical research domain. These two essays form the

foundation of the empirical research in this dissertation. The third

essay, ``Sponsored Search Auctions: Research Opportunities in

Marketing,'' outlines areas of future inquiry that I intend to

pursue in my research.

Of note, the problems underpinning the two empirical essays exhibits

a common form, that of a two-sided network wherein two parties

interact on a common platform (Rochet and Tirole, 2006). Although

theoretical research on two-sided markets is abundant, this

dissertation focuses on their use in e-commerce and adopts an

empirical orientation. I assume an empirical orientation because I

seek to guide firm behavior with concrete policy recommendations and

offer new insights into the actual behavior of the agents who

interact in these contexts. Although the two empirical essays share

this common feature, they also exhibit notable differences,

including the nature of the auction mechanism itself, the

interactions between the agents, and the dynamic frame of the

problem, thus making the problems distinct. The following abstracts

for these two essays as well as the chapter that describes my future

research serve to summarize these contributions, commonalities and

differences.

Online Auction Demand

With $40B in annual gross merchandise volume, electronic auctions

comprise a substantial and growing sector of the retail economy. For

example, eBay alone generated a gross merchandise volume of $14.4B

during the fourth quarter of 2006. Concurrent with this growth has

been an attendant increase in empirical research on Internet

auctions. However, this literature focuses primarily on the bidder;

I extend this research to consider both seller and bidder behavior

in an integrated system within a two-sided network of the two

parties. This extension of the existing literature enables an

exploration of the implications of the auction house's marketing on

its revenues as well as the nature of bidder and seller interactions

on this platform. In the first essay, I use a unique data set of

Celtic coins online auctions. These data were obtained from an

anonymous firm and include complete bidding and listing histories.

In contrast, most existing research relies only on the observed

website bids. The complete bidding and listing histories provided by

the data afford additional information that illuminates the insights

into bidder and seller behavior such as bidder valuations and seller

costs.

Using these data from the ancient coins category, I estimate a

structural model that integrates both bidder and seller behavior.

Bidders choose coins and sellers list them to maximize their

respective profits. I then develop a Markov Chain Monte Carlo (MCMC)

estimation approach that enables me, via data augmentation, to infer

unobserved bidder and seller characteristics and to account for

heterogeneity in these characteristics. My findings indicate that:

i) bidder valuations are affected by item characteristics (e.g., the

attributes of the coin), seller (e.g. reputation), and auction

characteristics (e.g., the characteristics of the listing); ii)

bidder costs are affected by bidding behavior, such as the recency

of the last purchase and the number of concurrent auctions; and iii)

seller costs are affected by item characteristics and the number of

concurrent listings from the seller (because acquisition costs

evidence increasing marginal values).

Of special interest, the model enables me to compute fee

elasticities, even though no variation in historical fees exists in

these data. I compute fee elasticities by inferring the role of

seller costs in their historical listing decision and then imputing

how an increase in these costs (which arises from more fees) would

affect the seller's subsequent listing behavior. I find that these

implied commission elasticities exceed per-item fee elasticities

because commissions target high value sellers, and hence, commission

reductions enhance their listing likelihood. By targeting commission

reductions to high value sellers, auction house revenues can be

increased by 3.9%. Computing customer value, I find that attrition

of the largest seller would decrease fees paid to the auction house

by $97. Given that the seller paid $127 in fees, competition

offsets only 24% of the fees paid by the seller. In contrast,

competition largely in the form of other bidders offsets 81% of the

$26 loss from buyer attrition. In both events, the auction house

would overvalue its customers by neglecting the effects of

competition.

A Dynamic Model of Sponsored Search Advertising

Sponsored search advertising is ascendant. Jupiter Research reports

that expenditures rose 28% in 2007 to $8.9B and will continue to

rise at a 26% Compound Annual Growth Rate (CAGR), approaching half

the level of television advertising and making sponsored search

advertising one of the major advertising trends affecting the

marketing landscape. Although empirical studies of sponsored search

advertising are ascending, little research exists that explores how

the interactions of various agents (searchers,

advertisers, and the search engine) in keyword

markets affect searcher and advertiser behavior, welfare and search

engine profits. As in the first essay, sponsored search constitutes

a two-sided network. In this case, bidders (advertisers) and

searchers interact on a common platform, the search engine. The

bidder seeks to maximize profits, and the searcher seeks to maximize

utility.

The structural model I propose serves as a foundation to explore

these outcomes and, to my knowledge, is the first structural model

for keyword search. Not only does the model integrate the behavior

of advertisers and searchers, it also accounts for advertisers

competition in a dynamic setting. Prior theoretical research has

assumed a static orientation to the problem whereas prior empirical

research, although dynamic, has focused solely on estimating the

dynamic sales response to a single firm's keyword advertising

expenditures.

To estimate the proposed model, I have developed a two-step Bayesian

estimator for dynamic games. This approach does not rely on

asymptotics and also facilitates a more flexible model

specification.

I fit this model to a proprietary data set provided by an anonymous

search engine. These data include a complete history of consumer

search behavior from the site's web log files and a complete history

of advertiser bidding behavior across all advertisers. In addition,

the data include search engine information, such as keyword pricing

and website design.

With respect to advertisers, I find evidence of dynamic

bidding behavior. Advertiser valuation for clicks on their sponsored

links averages about $0.27. Given the typical $22 retail price of

the software products advertised on the considered search engine,

this figure implies a conversion rate (sales per click) of about

1.2%, well within common estimates of 1-2% (gamedaily.com). With

respect to consumers, I find that frequent clickers place a

greater emphasis on the position of the sponsored advertising link.

I further find that 10% of consumers perform 90% of the clicks.

I then conduct several policy simulations to illustrate the effects

of change in search engine policy. First, I find that the

search engine obtains revenue gains of nearly 1.4% by sharing

individual level information with advertisers and enabling them to

vary their bids by consumer segment. This strategy also improves

advertiser profits by 11% and consumer welfare by 2.9%. Second, I

find that a switch from a first to second price auction results in

truth telling (advertiser bids rise to advertiser valuations), which

is consistent with economic theory. However, the second price

auction has little impact on search engine profits. Third, consumer

search tools lead to a platform revenue increase of 3.7% and an

increase of consumer welfare of 5.6%. However, these tools, by

reducing advertising exposure, lower advertiser profits by 4.1%.

Sponsored Search Auctions: Research Opportunities in Marketing

In the final chapter, I systematically review the literature on

keyword search and propose several promising research directions.

The chapter is organized according to each agent in the search

process, i.e., searchers, advertisers and the search engine, and

reviews the key research issues for each. For each group, I outline

the decision process involved in keyword search. For searchers, this

process involves what to search, where to search, which results to

click, and when to exit the search. For advertisers, this process

involves where to bid, which word or words to bid on, how much to

bid, and how searchers and auction mechanisms moderate these

behaviors. The search engine faces choices on mechanism design,

website design, and how much information to share with its

advertisers and searchers. These choices have implications for

customer lifetime value and the nature of competition among

advertisers. Overall, I provide a number of potential areas of

future research that arise from the decision processes of these

various agents.

Foremost among these potential areas of future research are i) the

role of alternative consumer search strategies for information

acquisition and clicking behavior, ii) the effect of advertiser

placement alternatives on long-term profits, and iii) the measure of

customer lifetime value for search engines. Regarding the first

area, a consumer's search strategy (i.e., sequential search and

non-sequential search) affects which sponsored links are more likely

to be clicked. The search pattern of a consumer is likely to be

affected by the nature of the product (experience product vs. search

product), the design of the website, the dynamic orientation of the

consumer (e.g., myopic or forward-looking), and so on. This search

pattern will, in turn, affect advertisers payments, online traffic,

sales, as well as the search engine's revenue. With respect to the

second area, advertisers must ascertain the economic value of

advertising, conditioned on the slot in which it appears, before

making decisions such as which keywords to bid on and how much to

bid. This area of possible research suggests opportunities to

examine how advertising click-through and the number of impressions

differentially affect the value of appearing in a particular

sponsored slot on a webpage, and how this value is moderated by an

appearance in a non-sponsored slot (i.e., a slot in the organic

search results section). With respect to the third area of future

research, customer value is central to the profitability and

long-term growth of a search engine and affects how the firm should

allocate resources for customer acquisition and retention.

Organization

This dissertation is organized as follows. After this brief

introduction, the essay, ``Online Auction Demand,'' serves as a

basis that introduces some concepts of auctions as two-sided

markets. Next, the second essay, ``A Dynamic Model of Sponsored

Search Advertising,'' extends the first essay by considering a

richer context of bidder competition and consumer choice behavior.

Finally, the concluding chapter, which outlines my future research

interests, considers potential extensions that pertain especially to

sponsored search advertising.

Dissertation

Στην παρούσα διατριβή μελετάμε αγορές δημοπρασιών και εξετάζουμε διάφορες ιδιότητές τους καθώς και τον τρόπο που αυτές επηρεάζονται από τον τρόπο που συμπεριφέρονται και δρουν οι συμμετέχοντες. Η έννοια δημοπρασία αναφέρεται σε κάθε μηχανισμό, ή σύνολο κανόνων, που διέπει μια διαδικασία ανάθεσης αγαθών. Τέτοιοι μηχανισμοί είναι επιρρεπείς σε στρατηγικούς χειρισμούς (χειραγώγηση) από τους συμμετέχοντες, γεγονός που δικαιολογεί την έμφυτη δυσκολία στον σχεδιασμό τους. Σκοπός αυτής της εργασίας είναι η μελέτη σε θεωρητικό επίπεδο των ιδιοτήτων μηχανισμών δημοπρασίας έτσι ώστε να είμαστε σε θέση να προβλέψουμε, να εξηγήσουμε, ακόμα και να τροποποιήσουμε την απόδοσή τους στην πράξη. Εστιάζουμε την προσοχή μας σε δημοπρασίες χρηματοδοτούμενης αναζήτησης, οι οποίες αποτελούν την επικρατέστερη διαδικασία για την προβολή διαφημίσεων στο Διαδίκτυο. Υιοθετούμε παιγνιοθεωρητική προσέγγιση και υπολογίζουμε το Τίμημα της Αναρχίας για να φράξουμε την απώλεια αποδοτικότητας εξαιτίας της στρατηγικής συμπεριφοράς των παιχτών. Επίσης, αποδεικνύουμε εγγυήσεις εσόδων για να φράξουμε την απώλεια των εσόδων του μηχανισμού δημοπρασίας GSP (γενικευμένος μηχανισμός δεύτερης τιμής) σε αυτό το πλαίσιο. Για την ακρίβεια, ορίζουμε παραλλαγές του μηχανισμού δημοπρασίας GSP που δίνουν καλές εγγυήσεις εσόδων. Στη συνέχεια εξετάζουμε το πρόβλημα του σχεδιασμού της βέλτιστης δημοπρασίας ενός αντικειμένου. Αποδεικνύουμε ένα υπολογίσιμο φράγμα δυσκολίας στην προσέγγιση για την περίπτωση με τρεις παίχτες. Επίσης, αποδεικνύουμε ότι υπάρχει αξιοσημείωτη διαφορά ανάμεσα στα έσοδα που προκύπτουν από ντετερμινιστικούς φιλαλήθεις μηχανισμούς και πιθανοτικούς μηχανισμούς που είναι φιλαλήθεις κατά μέσο όρο.
In this dissertation we consider auction markets and examine their properties and how these are affected by the way the participants act. An auction may refer to any mechanism or set of rules governing a resource allocation process. Designing such a mechanism is not an easy task and this is partly due to their vulnerability to strategic manipulation by the participants. Our goal is to examine the theoretical properties of auction mechanisms in order to predict, explain, or even adjust their behavior in practice in terms of some desired features. We focus on sponsored search auctions, which constitute the leading procedure in Internet advertising. We adopt a game-theoretic approach and provide Price of Anarchy bounds in order to measure the efficiency loss due to the strategic behavior of the players. Moreover, we prove revenue guarantees to bound the suboptimality of GSP (generalized second price mechanism) in that respect. Ιn particular, we define variants of the GSP auction mechanism that yield good revenue guarantees. We also consider the problem of designing an optimal auction in the single-item setting. We prove a strong APX-hardness result that applies to the 3-player case. We furthermore give a separation result between the revenue of deterministic and randomized optimal auctions.

碩士
南華大學
資訊管理學系碩士班
99
Online advertising has been one of the few advertising platforms that have shown revenue growth fast over the past years. Especially, Search engines including Yahoo and Google utilize the Keyword Auction for ranking the advertisements displayed around the search results in the web page. In the early years of Keyword Auctions, the Generalized First Price (GFP) auction was used. Since all winners pay their bid in the first price, they have incentive to under-bid to reduce their payment. As a result, biding prices oscillate, and the outcome becomes quite unstable. To overcome the problem, the Generalized Second Price (GSP) auction was applied in the current search engine. This paper studied the auction strategy of Keyword Search for sponsors in order to find the relationship between the revenue of search engine and the speed of auction.

Game theory and mechanism design have emerged as an important tool to model, analyze,and solve decentralized design problems involving multiple agents that interact strategically in a rational and intelligent way. Some examples of these design problems include: auctions and markets in electronic commerce; network economics; dynamic pricing; routing protocols in wireless networks; resource allocation in computational grids; algorithms for selfish agents;etc. The motivation for this doctoral work springs from the high level of current interest indesigning innovative mechanisms for solving emerging game theoretic problems in the area of electronic commerce. In this thesis, we focus on three such problems and advance the current art in mechanism design while developing new, innovative mechanisms to solve the problems. The first problem we explore is the highly strategic problem of forming a high value E-business supply chain by choosing the best mix of supply chain partners. In our research, we formulate the supply chain formation problem as a mechanism design problem in a generic wayand show that the well known VCG (Vickrey-Clarke-Groves) mechanisms provide an apt frame-work for solving this problem. We provide a compelling example of a three stage automotive distribution network to illustrate the power and e±cacy of the proposed methodology. The second problem we model and solve is that of designing a revenue maximizing sponsored search auction. This is a problem that is faced by every Internet search engine, such as Google,MSN, and Yahoo!, whenever it receives a search query. In our research, we take a comprehensivelook at existing auction mechanisms for this problem. Our work leads to an innovative new auction mechanism, which we call OPT (optimal mechanism), that exhibits a superior level ofperformance. The proposed mechanism extends, in a non-trivial way, the well known Myersonoptimal auction to the specific setting of sponsored search auctions. The proposed mechanism maximizes the revenue to the search engine and also satisfies two crucial properties, Bayesian incentive compatibility and interim individual rationality. The third contribution is in respect of Stackelberg problems, which are game theoretic problems that involve hierarchical and sequential decision making. By focusing attention on an important subclass of these problems, namely the Single-Leader-Rest-Followers (SLRF) problems, we extend all relevant aspects of classical mechanism design theory to the case of SLRF problems. We derive many important results in respect of procurement auctions with reserve prices using the developed theory. The research carried out as part of this doctoral work, we believe, advances the current art in mechanism design while developing innovative mechanisms to solve those problems.