Group-buying ads seeking a minimum number of customers before the deal expiry are increasingly used by the daily-deal providers. Unlike the traditional web ads, the advertiser's profits for group-buying ads depends on the time to expiry and additional customers needed to satisfy the minimum group size. Since both these quantities are time-dependent, optimal bid amounts to maximize profits change with every impression. Consequently, traditional static bidding strategies are far from optimal. Instead, bid values need to be optimized in real-time to maximize expected bidder profits. This online optimization of deal profits is made possible by the advent of ad exchanges offering real-time (spot) bidding. To this end, we propose a real-time bidding strategy for group-buying deals based on the online optimization of bid values. We derive the expected bidder profit of deals as a function of the bid amounts, and dynamically vary bids to maximize profits. Further, to satisfy time constraints of the online bidding, we present methods of minimizing computation timings. Subsequently, we derive the real time ad selection, admissibility, and real time bidding of the traditional ads as the special cases of the proposed method. We evaluate the proposed bidding, selection and admission strategies on a multi-million click stream of 935 ads. The proposed real-time bidding, selection and admissibility show significant profit increases over the existing strategies. Further the experiments illustrate the robustness of the bidding and acceptable computation timings.
Display advertising has traditionally been sold via guaranteed contracts --- a guaranteed contract is a deal between a publisher and an advertiser to allocate a certain number of impressions over a certain period, for a pre-specified price per impression. However, as spot markets for display ads, such as the RightMedia Exchange, have grown in prominence, the selection of advertisements to show on a given page is increasingly being chosen based on price, using an auction. As the number of participants in the exchange grows, the price of an impressions becomes a signal of its value. This correlation between price and value means that a seller implementing the contract through bidding should offer the contract buyer a range of prices, and not just the cheapest impressions necessary to fulfill its demand. Implementing a contract using a range of prices, is akin to creating a mutual fund of advertising impressions, and requires randomized bidding. We characterize what allocations can be implemented with randomized bidding, namely those where the desired share obtained at each price is a non-increasing function of price. In addition, we provide a full characterization of when a set of campaigns are compatible and how to implement them with randomized bidding strategies. We present the design of a banner advertising auction which is considerably more expressive than current designs. We describe a general model of expressive ad contract bidding and an allocation model that can be executed in real time through the assignment of fractions of relevant ad channels to specific advertiser contracts. The uncertainty in channel supply and demand is addresscd by the formulation of a stochastic combinatorial optimization problem for channel allocation that is rerun periodically. We solve this in two different ways: fast deterministic optimization with respect to expectations; and a novel online sample-based stochastic optimization method-- that can be applied to continuous decision spaces--which exploits the deterministic optimization as a black box. Experiments demonstrate the importance of expressive bidding and the value of stochastic optimization. Motivated by the allocation problem facing publishers in display advertising we formulate the online assignment with forecast problem, a version of the online allocation problem where the algorithm has access to random samples from the future set of arriving vertices. We provide a solution that allows us to serve Internet users in an online manner that is provably nearly optimal. Our technique applies to the forecast version of a large class of online assignment problems, such as online bipartite matching, allocation, and budgeted bidders, in which we wish to minimize the value of some convex objective function subject to a set of linear supply and demand constraints. Our solution utilizes a particular subspace of the dual space, allowing us to describe the optimal primal solution implicitly in space proportional to the demand side of the input graph. More importantly, it allows us to prove that representing the primal solution using such a compact allocation plan yields a robust online algorithm which makes near-optimal online decisions. Furthermore, unlike the primal solution, we show that the compact allocation plan produced by considering only a sampled version of the original problem generalizes to produce a near optimal solution on the full problem instance.