Online advertising is an essential part of Internet and the main source of revenue for lots of web-centric companies such as search engines, news websites, Internet social networks, and other types of publishers. Online advertising happens in different settings and includes many challenges and constraints. A key component in each setting is the mechanism which selects and prices the set of winning ads. In this thesis, we consider the mechanism related issues arises in online advertising and propose candidate solutions with a special focus on the revenue aspect.

Generalized Second Price (GSP) auction (the current mechanism of choice in online advertising) has appealing properties when ads are simple (text based and identical in size). But GSP does not generalize to richer ad settings, whereas truthful mechanisms, such as VCG do. Hence there are incentives for search platforms to migrate to truthful mechanisms, but a straight switch from GSP to VCG either requires all bidders instantly bid truthfully or incurs significant revenue loss. We propose a transitional mechanism which encourages advertisers to update their bids to their valuations, while mitigating revenue loss\footnote{It is the candidate mechanism to make the transition from GSP to VCG in Microsoft's Bing.}. The mechanism is equivalent to GSP when nobody has updated her bid, is equivalent to VCG when everybody has updated, and it has the same allocation and payments of the original GSP if bids were in the minimum symmetric Nash equilibrium. In settings where both GSP ads and truthful ads exist, it is easier to propose a payment function than an allocation function. We give a general framework for these settings to characterize payment functions which guarantee incentive compatibility of truthful ads, by requiring that the payment functions satisfy two properties.

Next, we discuss about revenue monotonicity (revenue should go up as the number of bidders increases) of truthful mechanisms in online advertising. This natural property comes at

the expense of social welfare - one can show that it is not possible to get truthfulness , revenue monotonicity, and optimal social welfare simultaneously. In light of this, we introduce the notion of Price of Revenue Monotonicity (\porm) to capture the loss in social welfare of a revenue monotone mechanism. We design truthful and revenue monotone mechanisms for important online advertising auctions with small \porm{} and prove a matching lower bound.

Finally, we study how to measure revenue of mechanisms in the prior free settings. One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high values for the goods and a {\em competitive} outcome would have generated a significant revenue. A competitive outcome is one for which it is impossible for the seller and a subset of buyers to `block' the auction by defecting and negotiating an outcome with higher payoffs for themselves. This corresponds to the well-known concept of {\em core} in cooperative game theory where designing {\em core-selecting auctions} is well studied \cite{AM02,AM06,DM08,DC12}. While these auctions are known for having good revenue properties, they lack incentive-compatibility property desired for online advertising. Towards this, we define a notion of {\em core-competitive} auctions. We say that an incentive-compatible auction is $\alpha$-core-competitive if its revenue is at least $1/\alpha$ fraction of the minimum revenue of a core-outcome. We study designing core-competitive mechanisms for a famous online advertising scenario.