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.

An iterative auction mechanism for combinatorial exchanges

Combinatorial exchanges are double sided marketplaces with multiple sellers and multiple buyers trading with the help of combinatorial bids. The allocation and other associated problems in such exchanges are known to be among the hardest to solve among all economic mechanisms. In this paper, we develop computationally efficient iterative auction mechanisms for solving combinatorial exchanges. Our mechanisms satisfy Individual-rationality (IR) and budget-nonnegativity (BN) properties. We also show that our method is bounded and convergent. Our numerical experiments show that our algorithm produces good quality solutions and is computationally efficient.

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.

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.

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.

A Global Constraint On Relative Rotation To Avoid Lumped Compliant Mechanisms In Topology Optimization

Some of the well known formulations for topology optimization of compliant mechanisms could lead to lumped compliant mechanisms. In lumped compliance, most of the elastic deformation in a mechanism occurs at few points, while rest of the mechanism remains more or less rigid. Such points are referred to as point-flexures. It has been noted in literature that high relative rotation is associated with point-flexures. In literature we also find a formulation of local constraint on relative rotations to avoid lumped compliance. However it is well known that a global constraint is easier to handle than a local constraint, by a numerical optimization algorithm. The current work presents a way of putting global constraint on relative rotations. This constraint is also simpler to implement since it uses linearized rotation at the center of finite-elements, to compute relative rotations. I show the results obtained by using this constraint oil the following benchmark problems - displacement inverter and gripper.

A comparative study of the energetics, structures, and mechanisms of the HCN H HNC and LiCN <-> LiNC isomerizations

The potential energy surfaces of the HCN<->HNC and LiCN<->LiNC isomerization processes were determined by ab initio theory using fully optimized triple-zeta double polarization types of basis sets. Both the MP2 corrections and the QCISD level of calculations were performed to correct for the electron correlation. Results show that electron correlation has a considerable influence on the energetics and structures. Analysis of the intramolecular bond rearrangement processes reveals that, in both cases, H (or Li+) migrates in an almost elliptic path in the plane of the molecule. In HCN<->HNC, the migrating hydrogen interacts with the in-plane pi,pi* orbitals of CN, leading to a decrease in the C-N bond order. In LiCN<->LiNC, Li+ does not interact with the corresponding pi,pi* orbitals of CN.

Reactivity of Cationic Terminal Borylene Complexes: Novel Mechanisms for Insertion and Metathesis Chemistry Involving Strongly Lewis Acidic Ligand Systems

The reactions of terminal borylene complexes of the type [CpFe(CO)(2)(BNR2)](+) (R = `Pr, Cy) with heteroallenes have been investigated by quantum-chemical methods, in an attempt to explain the experimentally observed product distributions. Reaction with dicyclohexylcarbodiimide (CyNCNCy) gives a bis-insertion product, in which 1 equiv of carbodiimide is assimilated into each of the Fe=B and B=N double bonds to form a spirocyclic boronium system. In contrast, isocyanates (R'NCO, R' = Ph, 2,6-wXy1, CY; XYl = C6H3Me2) react to give isonitrile complexes of the type [CpFe(CO)(2)(CNR')]+, via a net oxygen abstraction (or formal metathesis) process. Both carbodiimide and socyanate substrates are shown to prefer initial attack at the Fe=B bond rather than the B=N bond of the borylene complex. Further mechanistic studies reveal that the carbodiimide reaction ultimately leads to the bis-insertion compounds [CpFe(CO)(2)C(NCy)(2)B(NCY)(2)CNR2](+), rather than to the isonitrile system [CpFe(CO)(2)(CNCy)](+), on the basis of both thermodynamic (product stability) and kinetic considerations (barrier heights). The mechanism of the initial carbodiimide insertion process is unusual in that it involves coordination of the substrate at the (borylene) ligand followed by migration of the metal fragment, rather than a more conventional process: i.e., coordination of the unsaturated substrate at the metal followed by ligand migration. In the case of isocyanate substrates, metathesis products are competitive with those from the insertion pathway. Direct, single-step metathesis reactivity to give products containing a coordinated isonitrile ligand (i.e. [CpFe(CO)(2)(CNR')](+)) is facile if initial coordination of the isocyanate at boron occurs via the oxygen donor (which is kinetically favored); insertion chemistry is feasible when the isocyanate attacks initially via the nitrogen atom. However, even in the latter case, further reaction of the monoinsertion product so formed with excess isocyanate offers a number of facile (low energetic barrier) routes which also generate ['CpFe(CO)(2)(CNR')](+), rather than the bis-insertion product [CpFe(CO)(2)C(NR')(O)B(NR')(O)CNR2](+) (i.e., the direct analogue of the observed products in the carbodiimide reaction).

Deformation mechanisms during large strain deformation of nanocrystalline nickel

In this letter, a conclusive evidence of the operation of planar slip along with grain boundary mediated mechanisms has been reported during large strain deformation of nanocrystalline nickel. Dislocation annihilation mechanism such as mechanical recovery has been found to play an important role during the course of deformation. The evidences rely on x-ray based techniques, such as dislocation density determination and crystallographic texture measurement as well as microstructural observation by electron microscopy. The characteristic texture evolution in this case is an indication of normal slip mediated plasticity in nanocrystalline nickel.

Some mechanisms of excitation of a railway wheel

Railway wheel vibrations are caused by a number of mechanisms. Two of these are considered: (a) gravitational load reaction acting on different points of the wheel rim, as the wheel rolls on, and (b) random fluctuating forces generated at the contact patch by roughness on the mating surfaces of the wheel and rail. The wheel is idealized as a thin ring, and the analysis is limited to a single wheel rolling on a rail. It is shown that the first mechanism results in a stationary pattern of vibration, which would not radiate any sound. The acceleration caused by roughness-excited forces is much higher at higher frequencies, but is of the same order as that caused by load reaction at lower frequencies. The computed acceleration level (and hence the radiated SPL) caused by roughness is comparable with the observed values, and is seen to increase by about 10 dB for a doubling of the wagon speed. The driving point impedance of the periodic rail-sleeper system at the contact patch, which is used in the analysis, is derived in a companion paper.

Velocity and acceleration analysis of complex mechanisms by graphical iteration

A simple graphical method is presented for velocity and acceleration analysis of complex mechanisms possessing low or high degree of complexity. The method is iterative in character and generally yields the solution within a few iterations. Several examples have been worked out to illustrate the method.

Mechanisms of transmembrane cation transport studied by nuclear magnetic resonance spectroscopy

Several molecules like ionophores, vitamins, ion-binding cyclic peptides, acidic phospholipids, surfactants are known to expose the inner side of vesicles, to the externally added cations. Whereas ionophores and certain other systems bring about these changes by a selective transport (influx) of the cation by specialized mechanisms known as the carrier and channel mechanism, other systems cause lysis and vesicle fusion. These systems have been successfully studied using1H,31 P and13C nuclear magnetic resonance spectroscopy after the demonstration, fifteen years ago, of the ability of paramagnetic lanthanide ions to distinguish the inside of the vesicle from the outside. The results of these ’nuclear magnetic resonance kinetics’ experiments are reviewed.

Contributions to organic synthesis and reaction mechanisms

Development of new methods, leading to the first stereo-specific total synthesis of a steroid,viz equilenin, and of estrone and their derivatives and of several important synthones, useful for the preparation of physiologically active steroids, and the first conversion of an equilenane to estrane have been described. An account of the achievement of original syntheses of testosterone and its isomers and derivatives and degradation products, urinary steroids, terpenes and their important degradation products has been given. Mechanisms of Dieckmann cyclization, a novel dehydrogenation-addition reaction involving abietic acid and tetrachloro-o-benzoquinone, a rearrangement involving a substitution of cyclopentanone-2-carboxylic ester have been elucidated. An abnormaluv absorption exhibited by saturated 1,2-dicyano esters has been rationalized. Divergences in theord data of testosterone and 19-nortesto-sterone from their isomers have been explained by x-ray crystallographic studies of 8-isotestosterone, 8-iso-10-isotestosterone and 8-iso-10-iso-19-nortestosterone. A tentative explanation for the difference in their physiological activities has been suggested.

Mechanisms of molecular doping of graphene: A first-principles study

Doping graphene with electron donating or accepting molecules is an interesting approach to introduce carriers into it, analogous to electrochemical doping accomplished in graphene when used in a field-effect transistor. Here, we use first-principles density-functional theory to determine changes in the electronic-structure and vibrational properties of graphene that arise from the adsorption of aromatic molecules such as aniline and nitrobenzene. Identifying the roles of various mechanisms of chemical interaction between graphene and a molecule, we bring out the contrast between electrochemical and molecular doping of graphene. Our estimates of various contributions to shifts in the Raman-active modes of graphene with molecular doping are fundamental to the possible use of Raman spectroscopy in (a) characterization of the nature and concentration of carriers in graphene with molecular doping, and (b) graphene-based chemical sensors.