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.

A combinatorial procurement auction for QoS-aware web services

Business processes and application functionality are becoming available as internal web services inside enterprise boundaries as well as becoming available as commercial web services from enterprise solution vendors and web services marketplaces. Typically there are multiple web service providers offering services capable of fulfilling a particular functionality, although with different Quality of Service (QoS). Dynamic creation of business processes requires composing an appropriate set of web services that best suit the current need. This paper presents a novel combinatorial auction approach to QoS aware dynamic web services composition. Such an approach would enable not only stand-alone web services but also composite web services to be a part of a business process. The combinatorial auction leads to an integer programming formulation for the web services composition problem. An important feature of the model is the incorporation of service level agreements. We describe a software tool QWESC for QoS-aware web services composition based on the proposed approach.

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.

An inexpensive all glass sealed stirrer

An inexpensive all glass sealed stirrer may be constructed using a surgical syringe of about 10-ml capacity.

An auction algorithm for procuring wireless channel in a heterogenous wireless network

In this paper, we develop a novel auction algorithm for procuring wireless channel by a wireless node in a heterogeneous wireless network. We assume that the service providers of the heterogeneous wireless network are selfish and non-cooperative in the sense that they are only interested in maximizing their own utilities. The wireless user needs to procure wireless channels to execute multiple tasks. To solve the problem of the wireless user, we propose a reverse optimal (REVOPT) auction and derive an expression for the expected payment by the wireless user. The proposed auction mechanism REVOPT satisfies important game theoretic properties such as Bayesian incentive compatibility and individual rationality.

Temperature dependence of hydrogen evolution reaction on nickel oxide electrode in sealed nickel/cadmium cells

The impedance of sealed nickel/cadmium cells around a cell e.m.f. of 0.0 V was measured at five different temperatures between � 10 and +30 °C. The results show that the behaviour is similar at all temperatures. Based on the experimental results, the relation between charge-transfer resistance (Rct) and temperature (T) has been established for the Volmer reaction. Further, the value of cathodic transfer coefficient (?) has been estimated.

Impedance peaks of sealed nickel/cadmium cells at low states-of-charge

The impedance of sealed nickel/cadmium cells is measured at low states-of-charge that correspond to a cell e.m.f. range of 0.0 to 1.3 V. The results show that the impedance exhibits a pronounced maximum between 0.3 and 0.45 V. It is concluded that the impedance maxima are due to physicochemical processes taking place at the nickel oxide electrode. The impedance of the nickel oxide electrode is dominated by three different phenomena: (i) a Ni(II)/Ni(III) reaction between 1.3 and 0.8 V; (ii) a double-layer impedance between 0.8 and 0.3 V; (iii) a hydrogen evolution reaction between 0.3 and 0.0 V.

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.

Analytical Evaluation of Squeeze Film Forces in a CMUT With Sealed Air-Filled Cavity

The presence of vacuum inside the cavity of a capacitive micromachined ultrasonic transducer (CMUT) causes the membrane of the device (which is the main vibrating structural component) to deflect towards the substrate, thereby causing a reduction in the effective gap height. This reduction causes a drastic decrease in the pull-in voltage of the device limiting the DC bias at which the device can be operated for maximum efficiency. In addition, this initial deflection of the membrane due to atmospheric pressure, causes significant stress stiffening of the the membrane, changing the natural frequency of the device significantly from the design value. To circumvent the deleterious effects of vacuum in the sealed cavity, we investigate the possibility of using sealed CMUT cavities with air inside at ambient pressure. In order to estimate the transducer loss due to the presence of air in the sealed cavity, we evaluate the resulting damping and determine the forces acting on the vibrating membrane resulting from the compression of the trapped air film. We take into account the flexure of the top vibrating membrane instead of assuming the motion to be parallel-plate like. Towards this end, we solve the linearized Reynolds equation using the appropriate boundary conditions and show that, for a sealed CMUT cavity, the presence of air does not cause any squeeze film damping.

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.

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.

Evidence of episodic brittle faulting in the cratonic part of the Peninsular India and its implications for seismic hazard in slow deforming regions

The region around Waclakkancheri, in the province of Kerala, India, which lies in the vicinity of Palghat-Cauvery ;hear zone (within the Precambrian crystalline terrain), has been a site of microseismic activity since 1989. Earlier studies had identified a prominent WNW-ESE structure overprinting on the E-W trending lineaments associated with Palghat-Cauvery shear zone. We have mapped this structure, located in a chamockite quarry near Desamangalam, Waclakkancheri, which we identify as a ca. 30 km-long south dipping reverse fault. This article presents the characteristics of this fault zone exposed on the exhumed crystalline basement and discusses its significance in understanding the earthquake potential of the region. This brittle deformation zone consists of fracture sets with small-scale displacement and slip planes with embedded fault gouges. The macroscopic as well as the microscopic studies of this fault zone indicate that it evolved through different episodes of faulting in the presence of fluids. The distinct zones within consolidated gouge and the cross cutting relationship of fractures indicate episodic fault activity. At least four faulting episodes can be recognized based on the sequential development of different structural elements in the fault rocks. The repeated ruptures are evident along this shear zone and the cyclic behavior of this fault consists of co-seismic ruptures alternating with inter-seismic periods, which is characterized by the sealed fractures and consolidated gouge. The fault zone shows a minimum accumulated dip/oblique slip of 2.1 m in the reverse direction with a possible characteristic slip of 52 cm (for each event). The ESR dating of fault gouge indicates that the deformation zone records a major event in the Middle Quaternary. The empirical relationships between fault length and slip show that this fault may generate events M >= 6. The above factors suggest that this fault may be characterized as potentially active. Our study offers some new pointers that can be used in other slow deforming cratonic hinterlands in exploring the discrete active faults.

Preparation, structure, microwave absorption and other properties of the 125K superconductor Tl2Ca2Ba2Cu3O10+δ*1

It is shown that Tl2Ca2Ba2Cu3O10+δ (2223), the n=3 member of the Tl2O2. Can�1Ba2CunO2n+2 family shows a Tc (zero-resistance) of 125K (onset 140K) only when it is prepared by the sealed tube ceramic method starting from the 1313 composition. The structure is orthorhombic (Image compared to 30� of 2122), but electron diffraction patterns show two possible orthorhombic structures. Lattice images show the expected local structure and also the presence of dislocations and intergrowths. Both 2223 and 2122 oxides absorb microwaves (9.1GHz) intensely in the superconducting state, with some hysteresis. XPS measurements show Cu mainly in the 1+ state, suggesting the important role of oxygen holes.