We study revenue optimization learning algorithms for repeated posted-price auctions where a seller interacts with a single strategic buyer that holds a fixed private valuation for a good and seeks to maximize his cumulative discounted surplus. For this setting, first, we propose a novel algorithm that never decreases offered prices and has a tight strategic regret bound in @math under some mild assumptions on the buyer surplus discounting. This result closes the open research question on the existence of a no-regret horizon-independent weakly consistent pricing. The proposed algorithm is inspired by our observation that a double decrease of offered prices in a weakly consistent algorithm is enough to cause a linear regret. This motivates us to construct a novel transformation that maps a right-consistent algorithm to a weakly consistent one that never decreases offered prices. Second, we outperform the previously known strategic regret upper bound of the algorithm PRRFES, where the improvement is achieved by means of a finer constant factor @math of the principal term @math in this upper bound. Finally, we generalize results on strategic regret previously known for geometric discounting of the buyer's surplus to discounting of other types, namely: the optimality of the pricing PRRFES to the case of geometrically concave decreasing discounting; and linear lower bound on the strategic regret of a wide range of horizon-independent weakly consistent algorithms to the case of arbitrary discounts.
Displaying sponsored ads alongside the search results is a key monetization strategy for search engine companies. Since users are more likely to click ads that are relevant to their query, it is crucial for search engine to deliver the right ads for the query and the order in which they are displayed. There are several works investigating on how to learn a ranking function to maximize the number of ad clicks. In this paper, we address a new revenue optimization problem and aim to answer the question: how to construct a ranking model that can deliver high quality ads to the user as well as maximize search engine revenue? We introduce two novel methods from di fferent machine learning perspectives, and both of them take the revenue component into careful considerations. The algorithms are built upon the click-through log data with real ad clicks and impressions. The extensively experimental results verify the proposed algorithm that can produce more revenue than other methods as well as avoid losing relevance accuracy. To provide deep insight into the importance of each feature to search engine revenue, we extract twelve basic features from four categories. The experimental study provides a feature ranking list according to the revenue benefit of each feature. Sponsored search is an important monetization channel for search engines, in which an auction mechanism is used to select the ads shown to users and determine the prices charged from advertisers. There have been several pieces of work in the literature that investigate how to design an auction mechanism in order to optimize the revenue of the search engine. However, due to some unrealistic assumptions used, the practical values of these studies are not very clear. In this paper, we propose a novel game-theoretic machine learning approach, which naturally combines machine learning and game theory, and learns the auction mechanism using a bilevel optimization framework. In particular, we first learn a Markov model from historical data to describe how advertisers change their bids in response to an auction mechanism, and then for any given auction mechanism, we use the learnt model to predict its corresponding future bid sequences. Next we learn the auction mechanism through empirical revenue maximization on the predicted bid sequences. We show that the empirical revenue will converge when the prediction period approaches infinity, and a Genetic Programming algorithm can effectively optimize this empirical revenue. Our experiments indicate that the proposed approach is able to produce a much more effective auction mechanism than several baselines. This paper develops a general approach, rooted in statistical learning theory, to learning an approximately revenue-maximizing auction from data. We introduce t-level auctions to interpolate between simple auctions, such as welfare maximization with reserve prices, and optimal auctions, thereby balancing the competing demands of expressivity and simplicity. We prove that such auctions have small representation error, in the sense that for every product distribution F over bidders’ valuations, there exists a t-level auction with small t and expected revenue close to optimal. We show that the set of t-level auctions has modest pseudo-dimension (for polynomial t) and therefore leads to small learning error. One consequence of our results is that, in arbitrary single-parameter settings, one can learn a mechanism with expected revenue arbitrarily close to optimal from a polynomial number of samples. E-commerce web-sites such as Ebay as well as advertising exchanges (AdX) such as DoubleClick's, RightMedia, or AdECN work as intermediaries who sell items (e.g. page-views) on behalf of a seller (e.g. a publisher) to buyers on the opposite side of the market (e.g., advertisers). These platforms often use fixed-percentage sharing schemes, according to which (i) the platform runs an auction amongst buyers, and (ii) gives the seller a constant-fraction (e.g., 80 ) of the auction proceeds. In these settings, the platform faces asymmetric information regarding both the valuations of buyers for the item (as in a standard auction environment) as well as about the seller's opportunity cost of selling the item. Moreover, platforms often face intense competition from similar market places, and such competition is likely to favor auction rules that secure high payoffs to sellers. In such an environment, what selling mechanism should platforms employ? Our goal in this paper is to study optimal mechanism design in settings plagued by competition and two-sided asymmetric information, and identify conditions under which the current practice of employing constant cuts is indeed optimal. In particular, we first show that for a large class of competition games, platforms behave in equilibrium as if they maximize a a convex combination of seller's payoffs and platform's revenue, with weight α on the seller's payoffs (which is proxy for the intensity of competition in the market). We generalize the analysis of Myerson and Satterthwaite (1983), and derive the optimal direct-revelation mechanism for each α. As expected, the optimal mechanism applies a reserve price which is decreasing in α. Next, we present an indirect implementation based on sharing schemes". We show that constant cuts are optimal if and only if the opportunity cost of the seller has a power-form distribution, and derive a simple formula for computing the optimal constant cut as a function of the sellers' distribution of opportunity costs, and the market competition proxy α. Finally, for completeness, we study the case of a seller's optimal auction with a fixed profit for the platform, and derive the optimal direct and indirect implementations in this setting. This paper considers the problem faced by a seller who has a single object to sell to one of several possible buyers, when the seller has imperfect information about how much the buyers might be willing to pay for the object. The seller's problem is to design an auction game which has a Nash equilibrium giving him the highest possible expected utility. Optimal auctions are derived in this paper for a wide class of auction design problems. Abstract Most search engines use the weighted Generalized Second Price (wGSP) auction to sell keyword-based text ads, generating billions of dollars of advertising revenue every year. Designing and implementing near-optimal reserve prices for these wGSP auctions are naturally important problems for both academia and industry. In this paper, we show how to calculate and implement the near-optimal reserve price of the wGSP mechanism in realistic settings. Unlike reserve prices in standard single-item auctions, optimal reserve prices in wGSP auctions are discriminatory, different even for advertisers bidding on the same keyword. The optimal reserve price results can be extended to support CPA CPC CPM 1 hybrid auctions. Our simulations indicate that setting a proper reserve price will transfer some bidder utility (payoff) to auctioneer utility, resulting in higher revenue for the search engine. We describe a practical methodology to implement optimal reserve prices in production systems.  The Generalized Second Price (GSP) auction is the primary auction used for selling sponsored search advertisements. In this paper we consider the revenue of this auction at equilibrium. We prove that if agent values are drawn from identical regular distributions, then the GSP auction paired with an appropriate reserve price generates a constant fraction (1 6th) of the optimal revenue. In the full-information game, we show that at any Nash equilibrium of the GSP auction obtains at least half of the revenue of the VCG mechanism excluding the payment of a single participant. This bound holds also with any reserve price, and is tight. Finally, we consider the tradeoff between maximizing revenue and social welfare. We introduce a natural convexity assumption on the click-through rates and show that it implies that the revenue-maximizing equilibrium of GSP in the full information model will necessarily be envy-free. In particular, it is always possible to maximize revenue and social welfare simultaneously when click-through rates are convex. Without this convexity assumption, however, we demonstrate that revenue may be maximized at a non-envy-free equilibrium that generates a socially inefficient allocation. Second-price auctions with reserve play a critical role for modern search engine and popular online sites since the revenue of these companies often directly de- pends on the outcome of such auctions. The choice of the reserve price is the main mechanism through which the auction revenue can be influenced in these electronic markets. We cast the problem of selecting the reserve price to optimize revenue as a learning problem and present a full theoretical analysis dealing with the complex properties of the corresponding loss function. We further give novel algorithms for solving this problem and report the results of several experiments in both synthetic and real data demonstrating their effectiveness. We present an extensive analysis of the key problem of learning optimal reserve prices for generalized second price auctions. We describe two algorithms for this task: one based on density estimation, and a novel algorithm benefiting from solid theoretical guarantees and with a very favorable running-time complexity of @math , where @math is the sample size and @math the number of slots. Our theoretical guarantees are more favorable than those previously presented in the literature. Additionally, we show that even if bidders do not play at an equilibrium, our second algorithm is still well defined and minimizes a quantity of interest. To our knowledge, this is the first attempt to apply learning algorithms to the problem of reserve price optimization in GSP auctions. Finally, we present the first convergence analysis of empirical equilibrium bidding functions to the unique symmetric Bayesian-Nash equilibrium of a GSP. Online advertising is an essential part of the Internet and the main source of revenue for many web-centric firms such as search engines, social networks, and online publishers. A key component of online advertising is the auction mechanism which selects and prices the set of winning ads. This work is inspired by one of the biggest practical drawbacks of the widely popular Vickrey-Clarke-Groves (VCG) mechanism, which is the unique incentive-compatible mechanism that maximizes social welfare. It is known that VCG lacks a desired property of revenue monotonicity - a natural notion which states that the revenue of a mechanism shouldn't go down as the number of bidders increase or if the bidders increase their bids. Most firms which depend on online advertising revenue have a large sales team to attract more bidders on their inventory as the general belief is that more bidders will increase competition, and hence revenue. However, the lack of revenue monotonicity of VCG conflicts with this general belief and can be strategically confusing for the firm's business. In this work, we seek incentive-compatible mechanisms that are revenue-monotone. This natural property comes at the expense of social welfare - one can show that it is not possible to get incentive-compatibility, 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 further study revenue-monotonicity for two important online advertising scenarios. First one is the text vs image ad auction where in an ad slot, one can either show a single image ad or a few text ads. Second one is the video-pod auction where we have a video advertising slot of k seconds which can be filled with multiple video ads. For the image-text auction, we give a mechanism that satisfy both RM and IC and achieve PoRM of ∑i=1k 1 i ≈ ln k. We also show that the PoRM of our mechanism is the best possible by proving a matching lower bound of ∑i=1k 1 i on the PoRM of any deterministic mechanism under some mild assumptions. For the video-pod auction, we give a mechanism that achieves a PoRM of (⌊ log k ⌋ + 1) ⋅ (2 + ln k). Many online companies sell advertisement space in second-price auctions with reserve. In this paper, we develop a probabilistic method to learn a profitable strategy to set the reserve price. We use historical auction data with features to fit a predictor of the best reserve price. This problem is delicate - the structure of the auction is such that a reserve price set too high is much worse than a reserve price set too low. To address this we develop objective variables, a new framework for combining probabilistic modeling with optimal decision-making. Objective variables are "hallucinated observations" that transform the revenue maximization task into a regularized maximum likelihood estimation problem, which we solve with an EM algorithm. This framework enables a variety of prediction mechanisms to set the reserve price. As examples, we study objective variable methods with regression, kernelized regression, and neural networks on simulated and real data. Our methods outperform previous approaches both in terms of scalability and profit. 