A Nash Bargaining Approach to Retention Enhancing Bid Optimization in Sponsored Search Auctions with Discrete Bids

Bid optimization is now becoming quite popular in sponsored search auctions on the Web. Given a keyword and the maximum willingness to pay of each advertiser interested in the keyword, the bid optimizer generates a profile of bids for the advertisers with the objective of maximizing customer retention without compromising the revenue of the search engine. In this paper, we present a bid optimization algorithm that is based on a Nash bargaining model where the first player is the search engine and the second player is a virtual agent representing all the bidders. We make the realistic assumption that each bidder specifies a maximum willingness to pay values and a discrete, finite set of bid values. We show that the Nash bargaining solution for this problem always lies on a certain edge of the convex hull such that one end point of the edge is the vector of maximum willingness to pay of all the bidders. We show that the other endpoint of this edge can be computed as a solution of a linear programming problem. We also show how the solution can be transformed to a bid profile of the advertisers.

An Optimal Mechanism for Sponsored Search Auctions on the Web and Comparison With Other Mechanisms

In this paper, we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we describe two well-known mechanisms for sponsored search auction-Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call optimal (OPT) mechanism. The OPT mechanism maximizes the search engine's expected revenue, while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT. We compute and compare the expected revenue earned by the search engine under the three mechanisms when the advertisers are symmetric and some special conditions are satisfied. We also compare the three mechanisms in terms of incentive compatibility, individual rationality, and computational complexity. Note to Practitioners-The advertiser-supported web site is one of the successful business models in the emerging web landscape. When an Internet user enters a keyword (i.e., a search phrase) into a search engine, the user gets back a page with results, containing the links most relevant to the query and also sponsored links, (also called paid advertisement links). When a sponsored link is clicked, the user is directed to the corresponding advertiser's web page. The advertiser pays the search engine in some appropriate manner for sending the user to its web page. Against every search performed by any user on any keyword, the search engine faces the problem of matching a set of advertisers to the sponsored slots. In addition, the search engine also needs to decide on a price to be charged to each advertiser. Due to increasing demands for Internet advertising space, most search engines currently use auction mechanisms for this purpose. These are called sponsored search auctions. A significant percentage of the revenue of Internet giants such as Google, Yahoo!, MSN, etc., comes from sponsored search auctions. In this paper, we study two auction mechanisms, GSP and VCG, which are quite popular in the sponsored auction context, and pursue the objective of designing a mechanism that is superior to these two mechanisms. In particular, we propose a new mechanism which we call the OPT mechanism. This mechanism maximizes the search engine's expected revenue subject to achieving Bayesian incentive compatibility and individual rationality. Bayesian incentive compatibility guarantees that it is optimal for each advertiser to bid his/her true value provided that all other agents also bid their respective true values. Individual rationality ensures that the agents participate voluntarily in the auction since they are assured of gaining a non-negative payoff by doing so.

Design of an optimal auction for sponsored search auctions

In this paper we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we design a novel auction which we call the OPT (optimal) auction. The OPT mechanism maximizes the search engine's expected revenue while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We show that the OPT mechanism is superior to two of the most commonly used mechanisms for sponsored search namely (1) GSP (Generalized Second Price) and (2) VCG (Vickrey-Clarke-Groves). We then show an important revenue equivalence result that the expected revenue earned by the search engine is the same for all the three mechanisms provided the advertisers are symmetric and the number of sponsored slots is strictly less than the number of advertisers.

Optimal auctions for multi-unit procurement with volume discount bids

Our attention, is focused on designing an optimal procurement mechanism which a buyer can use for procuring multiple units of a homogeneous item based on bids submitted by autonomous, rational, and intelligent suppliers. We design elegant optimal procurement mechanisms for two different situations. In the first situation, each supplier specifies the maximum quantity that can be supplied together with a per unit price. For this situation, we design an optimal mechanism S-OPT (Optimal with Simple bids). In the more generalized case, each supplier specifies discounts based on the volume of supply. In this case, we design an optimal mechanism VD-OPT (Optimal with Volume Discount, bids). The VD-OPT mechanism uses the S-OPT mechanism as a building block. The proposed mechanisms minimize the cost to the buyer, satisfying at the same time, (a) Bayesian, incentive compatibility and (b) interim individual rationality.

Multi-Armed Bandit Mechanisms for Multi-Slot Sponsored Searth Auctions

In pay-per click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their ads. This auction is typically conducted for a number of rounds (say T). There are click probabilities mu_ij associated with agent-slot pairs. The search engine's goal is to maximize social welfare, for example, the sum of values of the advertisers. The search engine does not know the true value of an advertiser for a click to her ad and also does not know the click probabilities mu_ij s. A key problem for the search engine therefore is to learn these during the T rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced and would be referred to as multi-armed-bandit (MAB) mechanisms. When m = 1,characterizations for truthful MAB mechanisms are available in the literature and it has been shown that the regret for such mechanisms will be O(T^{2/3}). In this paper, we seek to derive a characterization in the realistic but nontrivial general case when m > 1 and obtain several interesting results.

Bidding Dynamics of Rational Advertisers in Sponsored Search Auctions on the Web

In this paper, we address a key problem faced by advertisers in sponsored search auctions on the web: how much to bid, given the bids of the other advertisers, so as to maximize individual payoffs? Assuming the generalized second price auction as the auction mechanism, we formulate this problem in the framework of an infinite horizon alternative-move game of advertiser bidding behavior. For a sponsored search auction involving two advertisers, we characterize all the pure strategy and mixed strategy Nash equilibria. We also prove that the bid prices will lead to a Nash equilibrium, if the advertisers follow a myopic best response bidding strategy. Following this, we investigate the bidding behavior of the advertisers if they use Q-learning. We discover empirically an interesting trend that the Q-values converge even if both the advertisers learn simultaneously.

Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions

In pay-per-click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their advertisements (ads for short). A sponsored search auction for a keyword is typically conducted for a number of rounds (say T). There are click probabilities mu(ij) associated with each agent slot pair (agent i and slot j). The search engine would like to maximize the social welfare of the advertisers, that is, the sum of values of the advertisers for the keyword. However, the search engine does not know the true values advertisers have for a click to their respective advertisements and also does not know the click probabilities. A key problem for the search engine therefore is to learn these click probabilities during the initial rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced. These mechanisms, due to their connection to the multi-armed bandit problem, are aptly referred to as multi-armed bandit (MAB) mechanisms. When m = 1, exact characterizations for truthful MAB mechanisms are available in the literature. Recent work has focused on the more realistic but non-trivial general case when m > 1 and a few promising results have started appearing. In this article, we consider this general case when m > 1 and prove several interesting results. Our contributions include: (1) When, mu(ij)s are unconstrained, we prove that any truthful mechanism must satisfy strong pointwise monotonicity and show that the regret will be Theta T7) for such mechanisms. (2) When the clicks on the ads follow a certain click precedence property, we show that weak pointwise monotonicity is necessary for MAB mechanisms to be truthful. (3) If the search engine has a certain coarse pre-estimate of mu(ij) values and wishes to update them during the course of the T rounds, we show that weak pointwise monotonicity and type-I separatedness are necessary while weak pointwise monotonicity and type-II separatedness are sufficient conditions for the MAB mechanisms to be truthful. (4) If the click probabilities are separable into agent-specific and slot-specific terms, we provide a characterization of MAB mechanisms that are truthful in expectation.

Properties Of Castor Oil Impregnated All-Polypropylene And Polypropylene-Paper Capacitors

In view of its non-toxicity, and good dielectric properties, castor oil, a polar liquid dielectric of vegetable origin is suggested as a possible alternative to PCB's for capacitor applications. In this paper the dielectric properties (including partial discharge behavior), of all-polypropylene and paper-polypropylene capacitors with castor oil as impregnant, are reported. The paper also contains results of life studies conducted under accelerated electrical and thermal stresses when they are occurring both individually and combined. The data obtained have been statistically analyzed and approximate life of the system calculated bylinear extrapolation.

Analysis Of The Dielectric Behavior Of Castor Oil Impregnated All-Paper Capacitors

Several new liquids impregnants for capacitors have been suggested as possible alternatives to PCB'S which are being replaced in view of their harmful effects.The application of castor oil, a vegetable product, has been studied in the authors laboratary with the same obejective.

Future switching technology: bacterial protein-based programmable all-optical switch for integrated optics applications?

We report on the bacterial protein-based all-optical switches which operate at low laser power, high speed and fulfil most of the requirements to be an ideal all-optical switch without any moving parts involved. This consists of conventional optical waveguides coated with bacteriorhodopsin films at switching locations. The principle of operation of the switch is based on the light-induced refractive index change of bacteriorhodopsin. This approach opens the possibility of realizing proteinbased all-optical switches for communication network, integrated optics and optical computers.

Stereochemical studies on cyclic peptides: Detailed energy minimization studies on hydrogen bonded all-trans cyclic pentapeptide backbones

Conformational studies have been carried out on hydrogenbonded all-trans cyclic pentapeptide backbone. Application of a combination of grid search and energy minimization on this system has resulted in obtaining 23 minimum energy conformations, which are characterized by unique patterns of hydrogen bonding comprising of β- and γ-turns. A study of the minimum energy conformationsvis-a-vis non-planar deviation of the peptide units reveals that non-planarity is an inherent feature in many cases. A study on conformational clustering of minimum energy conformations shows that the minimum energy conformations fall into 6 distinct conformational families. Preliminary comparison with available X-ray structures of cyclic pentapeptide indicates that only some of the minimum energy conformations have formed crystal structures. The set of minimum energy conformations worked out in the present study can form a consolidated database of prototypes for hydrogen bonded backbone and be useful for modelling cyclic pentapeptides both synthetic and bioactive in nature.

Dark matter dominance at all radii in the superthin galaxy UGC 7321

We model the shape and density profile of the dark matter halo of the low surface brightness, superthin galaxy UGC 7321, using the observed rotation curve and the H i scale height data as simultaneous constraints. We treat the galaxy as a gravitationally coupled system of stars and gas, responding to the gravitational potential of the dark matter halo. An isothermal halo of spherical shape with a core density in the range of View the MathML source and a core radius between 2.5 and 2.9 kpc, gives the best fit to the observations for a range of realistic gas parameters assumed. We find that the best-fit core radius is only slightly higher than the stellar disc scale length (2.1 kpc), unlike the case of the high surface brightness galaxies where the halo core radius is typically 3–4 times the disc scale length of the stars. Thus our model shows that the dark matter halo dominates the dynamics of the low surface brightness, superthin galaxy UGC 7321 at all radii, including the inner parts of the galaxy.

Effect of residual stresses and metallographic stability on the over all performance of integral diaphragm material

The integral diaphragm pressure transducer consists of a diaphragm machined from precipitation hardened martensitic (APX4) steel. Its performance is quite significant as it depends upon various factors such as mechanical properties including induced residual stress levels, metallurgical and physical parameters due to different stages of processing involved. Hence, the measurement and analysis of residual stress becomes very important from the point of in-service assessment of a component. In the present work, the stress measurements have been done using the X-ray diffraction (XRD) technique, which is a non-destructive test (NDT). This method is more reliable and widely used compared to the other NDT techniques. The metallurgical aspects have been studied by adopting the conventional metallographic practices including examination of microstructure using light microscope. The dimensional measurements have been carried out using dimensional gauge. The results of the present investigation reveals that the diaphragm material after undergoing series of realization processes has yielded good amount of retained austenite in it. Also, the presence of higher compressive stresses induced in the transducer results in non-linearity, zero shift and dimensional instability. The problem of higher retained austenite content and higher compressive stress have been overcome by adopting a new realization process involving machining and cold and hot stabilization soak which has brought down the retained austenite content to about 5–6% and acceptable level of compressive stress in the range −100 to −150 MPa with fine tempered martensitic phase structure and good dimensional stability. The new realization process seems to be quite effective in terms of controlling retained austenite content, residual stress, metallurgical phase as well as dimensional stability and this may result in minimum zero shift of the diaphragm system.

Stabilization of an All-Metal Antiaromatic Molecule (Al4Li4) Using BH and C as Caps

It has been reported by Pati et al. (J. Am. Chem. Soc. 2005, 127, 3496) that coordination with a transition metal can stabilize the “antiaromatic”, all-metal compound Al4Li4. Here, we report that it can also be stabilized by capping with a main group element like C and its isoelectronic species BH. Our calculations of binding energy, nuclear independent chemical shift, energy decomposition analysis, and molecular orbital analysis support the capping-induced stability, reduction of bond length alternation, and increase of aromaticity of these BH/C-capped Al4Li4 systems. The interaction between px and py orbitals of BH/C and the HOMO and LUMO of Al4Li4 is responsible for the stabilization. Our calculations suggest that capping can introduce fluxionality at room temperature.