Interpreting user actions to better understand their needs provides an important tool for improving information access services. In the context of organic Web search, considerable effort has been made to model user behavior and infer query intent, with the goal of improving the overall user experience. Much less work has been done in the area of sponsored search, i.e., with respect to the advertisement links (ads) displayed on search result pages by many commercial search engines. This thesis develops and evaluates new models and methods required to interpret user browsing and click behavior and understand query intent in this very different context. The concern of the initial part of the thesis is on extending the query categories for commercial search and on inferring query intent, with a focus on two major tasks: i) enriching queries with contextual information obtained from search result pages returned for these queries, and ii) developing relatively simple methods for the reliable labeling of training data via crowdsourcing. A central idea of this thesis work is to study the impact of contextual factors (including query intent, ad placement, and page structure) on user behavior. Later, this information is incorporated into probabilistic models to evaluate the quality of advertisement links within the context that they are displayed in their history of appearance. In order to account for these factors, a number of query and location biases are proposed and formulated into a group of browsing and click models. To explore user intent and behavior and to evaluate the performance of the proposed models and methods, logs of query and click information provided for research purposes are used. Overall, query intent is found to have substantial impact on predictions of user click behavior in sponsored search. Predictions are further improved by considering ads in the context of the other ads displayed on a result page. The parameters of the browsing and click models are learned using an expectation maximization technique applied to click signals recorded in the logs. The initial motivation of the user to browse the ad list and their browsing persistence are found to be related to query intent and browsing/click behavior. Accommodating these biases along with the location bias in user models appear as effective contextual signals, improving the performance of the existing models.

<p>Central to the explosive growth of the Internet has been the desire</p><p>of dispersed buyers and sellers to interact readily and in a manner</p><p>hitherto impossible. Underpinning these interactions, auction</p><p>pricing mechanisms have enabled Internet transactions in novel ways.</p><p>Despite this massive growth and new medium, empirical work in</p><p>marketing and economics on auction use in Internet contexts remains</p><p>relatively nascent. Accordingly, this dissertation investigates the</p><p>role of online auctions; it is composed of three essays.</p><p>The first essay, ``Online Auction Demand,'' investigates seller and</p><p>buyer interactions via online auction websites, such as eBay. Such</p><p>auction sites are among the earliest prominent transaction sites on</p><p>the Internet (eBay started in 1995, the same year Internet Explorer</p><p>was released) and helped pave the way for e-commerce. Hence, online</p><p>auction demand is the first topic considered in my dissertation. The</p><p>second essay, ``A Dynamic Model of Sponsored Search Advertising,''</p><p>investigates sponsored search advertising auctions, a novel approach</p><p>that allocates premium advertising space to advertisers at popular</p><p>websites, such as search engines. Because sponsored search</p><p>advertising targets buyers in active purchase states, such</p><p>advertising venues have grown very rapidly in recent years and have</p><p>become a highly topical research domain. These two essays form the</p><p>foundation of the empirical research in this dissertation. The third</p><p>essay, ``Sponsored Search Auctions: Research Opportunities in</p><p>Marketing,'' outlines areas of future inquiry that I intend to</p><p>pursue in my research.</p><p>Of note, the problems underpinning the two empirical essays exhibits</p><p>a common form, that of a two-sided network wherein two parties</p><p>interact on a common platform (Rochet and Tirole, 2006). Although</p><p>theoretical research on two-sided markets is abundant, this</p><p>dissertation focuses on their use in e-commerce and adopts an</p><p>empirical orientation. I assume an empirical orientation because I</p><p>seek to guide firm behavior with concrete policy recommendations and</p><p>offer new insights into the actual behavior of the agents who</p><p>interact in these contexts. Although the two empirical essays share</p><p>this common feature, they also exhibit notable differences,</p><p>including the nature of the auction mechanism itself, the</p><p>interactions between the agents, and the dynamic frame of the</p><p>problem, thus making the problems distinct. The following abstracts</p><p>for these two essays as well as the chapter that describes my future</p><p>research serve to summarize these contributions, commonalities and</p><p>differences.</p><p>Online Auction Demand</p><p>With $40B in annual gross merchandise volume, electronic auctions</p><p>comprise a substantial and growing sector of the retail economy. For</p><p>example, eBay alone generated a gross merchandise volume of $14.4B</p><p>during the fourth quarter of 2006. Concurrent with this growth has</p><p>been an attendant increase in empirical research on Internet</p><p>auctions. However, this literature focuses primarily on the bidder;</p><p>I extend this research to consider both seller and bidder behavior</p><p>in an integrated system within a two-sided network of the two</p><p>parties. This extension of the existing literature enables an</p><p>exploration of the implications of the auction house's marketing on</p><p>its revenues as well as the nature of bidder and seller interactions</p><p>on this platform. In the first essay, I use a unique data set of</p><p>Celtic coins online auctions. These data were obtained from an</p><p>anonymous firm and include complete bidding and listing histories.</p><p>In contrast, most existing research relies only on the observed</p><p>website bids. The complete bidding and listing histories provided by</p><p>the data afford additional information that illuminates the insights</p><p>into bidder and seller behavior such as bidder valuations and seller</p><p>costs.</p><p>Using these data from the ancient coins category, I estimate a</p><p>structural model that integrates both bidder and seller behavior.</p><p>Bidders choose coins and sellers list them to maximize their</p><p>respective profits. I then develop a Markov Chain Monte Carlo (MCMC)</p><p>estimation approach that enables me, via data augmentation, to infer</p><p>unobserved bidder and seller characteristics and to account for</p><p>heterogeneity in these characteristics. My findings indicate that:</p><p>i) bidder valuations are affected by item characteristics (e.g., the</p><p>attributes of the coin), seller (e.g. reputation), and auction</p><p>characteristics (e.g., the characteristics of the listing); ii)</p><p>bidder costs are affected by bidding behavior, such as the recency</p><p>of the last purchase and the number of concurrent auctions; and iii)</p><p>seller costs are affected by item characteristics and the number of</p><p>concurrent listings from the seller (because acquisition costs</p><p>evidence increasing marginal values).</p><p>Of special interest, the model enables me to compute fee</p><p>elasticities, even though no variation in historical fees exists in</p><p>these data. I compute fee elasticities by inferring the role of</p><p>seller costs in their historical listing decision and then imputing</p><p>how an increase in these costs (which arises from more fees) would</p><p>affect the seller's subsequent listing behavior. I find that these</p><p>implied commission elasticities exceed per-item fee elasticities</p><p>because commissions target high value sellers, and hence, commission</p><p>reductions enhance their listing likelihood. By targeting commission</p><p>reductions to high value sellers, auction house revenues can be</p><p>increased by 3.9%. Computing customer value, I find that attrition</p><p>of the largest seller would decrease fees paid to the auction house</p><p>by $97. Given that the seller paid $127 in fees, competition</p><p>offsets only 24% of the fees paid by the seller. In contrast,</p><p>competition largely in the form of other bidders offsets 81% of the</p><p>$26 loss from buyer attrition. In both events, the auction house</p><p>would overvalue its customers by neglecting the effects of</p><p>competition.</p><p>A Dynamic Model of Sponsored Search Advertising</p><p>Sponsored search advertising is ascendant. Jupiter Research reports</p><p>that expenditures rose 28% in 2007 to $8.9B and will continue to</p><p>rise at a 26% Compound Annual Growth Rate (CAGR), approaching half</p><p>the level of television advertising and making sponsored search</p><p>advertising one of the major advertising trends affecting the</p><p>marketing landscape. Although empirical studies of sponsored search</p><p>advertising are ascending, little research exists that explores how</p><p>the interactions of various agents (searchers,</p><p>advertisers, and the search engine) in keyword</p><p>markets affect searcher and advertiser behavior, welfare and search</p><p>engine profits. As in the first essay, sponsored search constitutes</p><p>a two-sided network. In this case, bidders (advertisers) and</p><p>searchers interact on a common platform, the search engine. The</p><p>bidder seeks to maximize profits, and the searcher seeks to maximize</p><p>utility.</p><p>The structural model I propose serves as a foundation to explore</p><p>these outcomes and, to my knowledge, is the first structural model</p><p>for keyword search. Not only does the model integrate the behavior</p><p>of advertisers and searchers, it also accounts for advertisers</p><p>competition in a dynamic setting. Prior theoretical research has</p><p>assumed a static orientation to the problem whereas prior empirical</p><p>research, although dynamic, has focused solely on estimating the</p><p>dynamic sales response to a single firm's keyword advertising</p><p>expenditures.</p><p>To estimate the proposed model, I have developed a two-step Bayesian</p><p>estimator for dynamic games. This approach does not rely on</p><p>asymptotics and also facilitates a more flexible model</p><p>specification.</p><p>I fit this model to a proprietary data set provided by an anonymous</p><p>search engine. These data include a complete history of consumer</p><p>search behavior from the site's web log files and a complete history</p><p>of advertiser bidding behavior across all advertisers. In addition,</p><p>the data include search engine information, such as keyword pricing</p><p>and website design.</p><p>With respect to advertisers, I find evidence of dynamic</p><p>bidding behavior. Advertiser valuation for clicks on their sponsored</p><p>links averages about $0.27. Given the typical $22 retail price of</p><p>the software products advertised on the considered search engine,</p><p>this figure implies a conversion rate (sales per click) of about</p><p>1.2%, well within common estimates of 1-2% (gamedaily.com). With</p><p>respect to consumers, I find that frequent clickers place a</p><p>greater emphasis on the position of the sponsored advertising link.</p><p>I further find that 10% of consumers perform 90% of the clicks.</p><p>I then conduct several policy simulations to illustrate the effects</p><p>of change in search engine policy. First, I find that the</p><p>search engine obtains revenue gains of nearly 1.4% by sharing</p><p>individual level information with advertisers and enabling them to</p><p>vary their bids by consumer segment. This strategy also improves</p><p>advertiser profits by 11% and consumer welfare by 2.9%. Second, I</p><p>find that a switch from a first to second price auction results in</p><p>truth telling (advertiser bids rise to advertiser valuations), which</p><p>is consistent with economic theory. However, the second price</p><p>auction has little impact on search engine profits. Third, consumer</p><p>search tools lead to a platform revenue increase of 3.7% and an</p><p>increase of consumer welfare of 5.6%. However, these tools, by</p><p>reducing advertising exposure, lower advertiser profits by 4.1%.</p><p>Sponsored Search Auctions: Research Opportunities in Marketing</p><p>In the final chapter, I systematically review the literature on</p><p>keyword search and propose several promising research directions.</p><p>The chapter is organized according to each agent in the search</p><p>process, i.e., searchers, advertisers and the search engine, and</p><p>reviews the key research issues for each. For each group, I outline</p><p>the decision process involved in keyword search. For searchers, this</p><p>process involves what to search, where to search, which results to</p><p>click, and when to exit the search. For advertisers, this process</p><p>involves where to bid, which word or words to bid on, how much to</p><p>bid, and how searchers and auction mechanisms moderate these</p><p>behaviors. The search engine faces choices on mechanism design,</p><p>website design, and how much information to share with its</p><p>advertisers and searchers. These choices have implications for</p><p>customer lifetime value and the nature of competition among</p><p>advertisers. Overall, I provide a number of potential areas of</p><p>future research that arise from the decision processes of these</p><p>various agents.</p><p>Foremost among these potential areas of future research are i) the</p><p>role of alternative consumer search strategies for information</p><p>acquisition and clicking behavior, ii) the effect of advertiser</p><p>placement alternatives on long-term profits, and iii) the measure of</p><p>customer lifetime value for search engines. Regarding the first</p><p>area, a consumer's search strategy (i.e., sequential search and</p><p>non-sequential search) affects which sponsored links are more likely</p><p>to be clicked. The search pattern of a consumer is likely to be</p><p>affected by the nature of the product (experience product vs. search</p><p>product), the design of the website, the dynamic orientation of the</p><p>consumer (e.g., myopic or forward-looking), and so on. This search</p><p>pattern will, in turn, affect advertisers payments, online traffic,</p><p>sales, as well as the search engine's revenue. With respect to the</p><p>second area, advertisers must ascertain the economic value of</p><p>advertising, conditioned on the slot in which it appears, before</p><p>making decisions such as which keywords to bid on and how much to</p><p>bid. This area of possible research suggests opportunities to</p><p>examine how advertising click-through and the number of impressions</p><p>differentially affect the value of appearing in a particular</p><p>sponsored slot on a webpage, and how this value is moderated by an</p><p>appearance in a non-sponsored slot (i.e., a slot in the organic</p><p>search results section). With respect to the third area of future</p><p>research, customer value is central to the profitability and</p><p>long-term growth of a search engine and affects how the firm should</p><p>allocate resources for customer acquisition and retention.</p><p>Organization</p><p>This dissertation is organized as follows. After this brief</p><p>introduction, the essay, ``Online Auction Demand,'' serves as a</p><p>basis that introduces some concepts of auctions as two-sided</p><p>markets. Next, the second essay, ``A Dynamic Model of Sponsored</p><p>Search Advertising,'' extends the first essay by considering a</p><p>richer context of bidder competition and consumer choice behavior.</p><p>Finally, the concluding chapter, which outlines my future research</p><p>interests, considers potential extensions that pertain especially to</p><p>sponsored search advertising.</p> / Dissertation

Interpreting user actions to better understand their needs provides an important tool for improving information access services. In the context of organic Web search, considerable effort has been made to model user behavior and infer query intent, with the goal of improving the overall user experience. Much less work has been done in the area of sponsored search, i.e., with respect to the advertisement links (ads) displayed on search result pages by many commercial search engines. This thesis develops and evaluates new models and methods required to interpret user browsing and click behavior and understand query intent in this very different context. The concern of the initial part of the thesis is on extending the query categories for commercial search and on inferring query intent, with a focus on two major tasks: i) enriching queries with contextual information obtained from search result pages returned for these queries, and ii) developing relatively simple methods for the reliable labeling of training data via crowdsourcing. A central idea of this thesis work is to study the impact of contextual factors (including query intent, ad placement, and page structure) on user behavior. Later, this information is incorporated into probabilistic models to evaluate the quality of advertisement links within the context that they are displayed in their history of appearance. In order to account for these factors, a number of query and location biases are proposed and formulated into a group of browsing and click models. To explore user intent and behavior and to evaluate the performance of the proposed models and methods, logs of query and click information provided for research purposes are used. Overall, query intent is found to have substantial impact on predictions of user click behavior in sponsored search. Predictions are further improved by considering ads in the context of the other ads displayed on a result page. The parameters of the browsing and click models are learned using an expectation maximization technique applied to click signals recorded in the logs. The initial motivation of the user to browse the ad list and their browsing persistence are found to be related to query intent and browsing/click behavior. Accommodating these biases along with the location bias in user models appear as effective contextual signals, improving the performance of the existing models.

Purpose: The purpose of this study is to understand millennials search behavior on mobile devices. Research Questions: How do millennials value organic and sponsored search results on mobile devices? What are the Web advertising variables that affect millennials attitudes towards sponsored search ads on mobile devices? Methodology: Data was collected from 103 Swedish millennials through an experiment and survey. Conclusion: The findings of this research supports the variables of entertainment and incentives to have a positive association with millennials attitudes towards mobile search ads while irritation, informativeness and credibility were only partially supported when testing independently with attitudes. An overall negative attitude could be seen toward sponsored links when participants motivated their action to click. Moreover, the results illustrated a higher attitude value towards mobile search ads to reflect an increased click behavior on sponsored search results.

The aim of this research was to find relationships between complimentary advertising strategies and sponsored search advertisement (SSA) in order to formulate a model to maximise return on investment achieved from online sponsored search advertisements. The results obtained from statistical analyses of SSA campaign data showed that complimentary online and offline advertisement campaigns have various different correlations to impressions, click-through rates, number of pages visited, time spent visiting a website, bounce rate of visitors to the website, cost-per-click and number of new registrations per keyword search from visitors gained through SSA campaigns. In particular, online display advertisements were found to have a slight positive correlation with new registrations made by customers gained through a simultaneously running SSA campaign. Offline radio adverts were found to have a positive correlation with impressions gained for SSA campaigns, whilst at the same time showing a negative correlation with the number of pages viewed by website visitors obtained through the SSA campaign. Some negative correlations to SSA campaign performance were also found, with the time visitors spent viewing the website decreasing, their bounce rate increasing and the cost-per-clicks for the keywords in the SSA campaign also increasing during periods when offline radio adverts were active. Offline television adverts were found to have a negative correlation with impressions gained for SSA campaigns, as well as the click-through rate for the keywords in these SSA campaigns. Offline television adverts did however also show a negative correlation with the cost-per-clicks for keywords in the SSA campaigns. Finally, a graphical model was developed to illustrate these correlations found between complimentary advertisement campaigns and SSA performance metrics. / Dissertation (MBA)--University of Pretoria, 2012. / Gordon Institute of Business Science (GIBS) / unrestricted

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.

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

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.

Στην παρούσα διατριβή μελετάμε αγορές δημοπρασιών και εξετάζουμε διάφορες ιδιότητές τους καθώς και τον τρόπο που αυτές επηρεάζονται από τον τρόπο που συμπεριφέρονται και δρουν οι συμμετέχοντες. Η έννοια δημοπρασία αναφέρεται σε κάθε μηχανισμό, ή σύνολο κανόνων, που διέπει μια διαδικασία ανάθεσης αγαθών. Τέτοιοι μηχανισμοί είναι επιρρεπείς σε στρατηγικούς χειρισμούς (χειραγώγηση) από τους συμμετέχοντες, γεγονός που δικαιολογεί την έμφυτη δυσκολία στον σχεδιασμό τους. Σκοπός αυτής της εργασίας είναι η μελέτη σε θεωρητικό επίπεδο των ιδιοτήτων μηχανισμών δημοπρασίας έτσι ώστε να είμαστε σε θέση να προβλέψουμε, να εξηγήσουμε, ακόμα και να τροποποιήσουμε την απόδοσή τους στην πράξη. Εστιάζουμε την προσοχή μας σε δημοπρασίες χρηματοδοτούμενης αναζήτησης, οι οποίες αποτελούν την επικρατέστερη διαδικασία για την προβολή διαφημίσεων στο Διαδίκτυο. Υιοθετούμε παιγνιοθεωρητική προσέγγιση και υπολογίζουμε το Τίμημα της Αναρχίας για να φράξουμε την απώλεια αποδοτικότητας εξαιτίας της στρατηγικής συμπεριφοράς των παιχτών. Επίσης, αποδεικνύουμε εγγυήσεις εσόδων για να φράξουμε την απώλεια των εσόδων του μηχανισμού δημοπρασίας 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.