CS787: Advanced AlgorithmsTopic: Sponsored Search Auction Design Presenter(s): Nilay, Srikrishna, Taedong17.6.1 Introduction to Auction DesignThe Internet, which started of as a res earch project in 1960’s, today influences almost every aspectof our daily lives. This has increasingly led marketers to focus on online advertising. Search engineslike Google and Yahoo! source their revenues almost entirely from selling advertisement space. Inthis lecture we will study profit-maximization problems related to selling advertisement space onInternet web sites.The online advertisement market is highly dynamic in nature, with advertisers arriving and leavingall the time. Moreover, the numb er of hits received by a website changes over time, as does thevalue of an Internet user clicking on an advertisement. Clearly the selling price of an advertise-ment depends on the benefit derived by the advertisers from the display of their advertisements.In most cases, the web site owner does not have a good estimate of the value of this benefit, asthe advertisers needs often change with time. This is unlike classical optimization problems wherethe optimizer (the advertisement auctioneer in our case) knows the values of all the variables overwhich the optimization is to be carried out. This makes auctions the logical choice for sellingadvertisement space on web sites. The web site owners ask the advertisers themselves for theirvaluations of the benefit they will receive. The value reported by the advertiser is called her bid.However, the advertisers, be ing selfish agents, need not reveal their valuations truthfully if it is intheir self-interest to do so.The goal of the web site owner is to set up a selling mechanism that uses these reported val-ues to determine the price(s) to be offered to the advertisers, in such a way that maximizes profitwhen each agent bids according to her best interest. At the same time, the web site owner wouldlike to keep the process of finding the optimal bidding strategy simple in order to attract moreadvertisers to the online advertising market.17.6.2 Mathematical FrameworkMechanism design deals with the construction of mechanisms, or games which are designed toget the agents to behave in a certain way s o as to achieve some desired outcome. [2] provides aframework for algorithmic mechanism design.• A mechanism deals with a set of agents N and wishes to choose from a collection of outcomesO. Let n = |N | be the number of agents.• Each agent i is assumed to have a valuation function vi: O → R. Intuitively, the valua-1tion function describes agent i’s intrinsic preference for each outcome. An agent’s valuationfunction is known only to that agent.• T denotes the set of all possible valuation functions and v ∈ Tnis the vector of valuationfunctions of all agents.The mechanism works by asking each agent to report her valuation function and computing anoutcome and a set of payments based on the reported functions.• bidenotes the valuation function reported by agent i (also known as i’s bid), b ∈ Tndenotesthe vector of bids.• Pi: Tn→ R be the payment made by agent i, and P = (Pi)i∈Nbe the payment scheme.Thus, a mechanism M consists of a pair (O, P ), where O : Tn→ O is the output function and Pis the payment scheme.Each agent’s goal is to maximize her utility function, which is assumed to be of the formui(O, Pi) = vi(O) − PiSince the mechanism determines the outcome and the payments based on the bid vector b, we willabbreviate ui(O(b), Pi(b)) and vi(O(b)) to ui(b) and vi(b) respectively. Clearly, an agent’s utilitydepends not only on her valuation function, but also on the bid vector.• Let b−i= (b1, . . . , bi−1, ?, bi+1, . . . bn) denote the vector of bids with agent i’s bid hidden bya question mark. We will refer to this as the masked bid vector. We will write b as (b−i, bi).• Similarly, let v−idenote the vector of all other agents valuation functions, T−i= Tn−1bethe space of those vectors.A strategy Si: T → T is said to be a dominant strategy for agent i if ui(b−i, Si(vi)) ≥ ui(b−i, bi)for all b−i∈ T−iand bi, vi∈ T . In other words, agent i’s best strategy is to report her valuation asSi(vi) whenever her true valuation is vi. A mechanism is said to be a dominant strategy mechanismif every agent has a dominant strategy.Definition 17.6.2.1 (Truthful Mechanism) A truthful mechanism is a dominant strategy mech-anism in which truth-telling is a dominant strategy for every agent, i.e.ui(b−i, vi) ≥ ui(b−i, bi) ∀ b−i∈ T−iand bi, vi∈ TTheorem 17. 6.2. 2 (Bid-independence principle) If the mechanism (O,P) is truthful, andO(b−i, bi) = O(b−i, b0i), then Pi(b−i, bi) = Pi(b−i, b0i).2Proof: Suppose to the contrary, i.e. Pi(b−i, bi) > Pi(b−i, b0i), while O(b−i, bi) = O(b−i, b0i).When vi= biand all the other agents bid b−i, agent i is better off lying and bidding b0i, contra-dicting truthfulness.This principle asserts that in a truthful mechanism, the bid of an agent affects the payment madeby the agent only through its effect on the outcome of the mechanism.17.6.3 Truthfulness as a Means to Simplified BiddingAs mentioned e arlier, we would like to construct mechanisms for selling advertising space on Internetweb sites under which it is easy for the advertisers to determine their optimal bidding strategies.Unless an advertiser has a dominant s trategy, she would be forced to speculate (or hire someone tospeculate for her) on how the other advertisers are going to bid in order to determine her optimalstrategy. Thus, in order to get rid of speculation and keep the process of bidding simple, we wouldlike each advertiser to have a dominant strategy, i.e. we would like to use a dominant strategymechanism. The Revelation principle stated below allows us to restrict our attention to truthfulmechanisms without missing any possible combination of outcome and payment functions (whenwe view the outcome and payment as a function of valuation rather than bids).Theorem 17. 6.3. 1 (Revelation principle [5, 6]) Every dominant strategy mechanism can beconverted to a truthful mechanism without changing the outcome or the payments on vector ofvaluation functions of all agents.Proof: Given a dominant strategy mechanism M , construct a truthful m echanism M0thatsimulates each bidder’s dominant strategy in M. Let Sibe agent i’s dominant strategy underM. Then, M0produces the same outcome and payments on