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.

Multi-agent search using?sensors with heterogeneous capabilities

In this thesis we address the problem of multi-agent search. We formulate two deploy and search strategies based on optimal deployment of agents in search space so as to maximize the search effectiveness in a single step. We show that a variation of centroidal Voronoi configuration is the optimal deployment. When the agents have sensors with different capabilities, the problem will be heterogeneous in nature. We introduce a new concept namely, generalized Voronoi partition in order to formulate and solve the heterogeneous multi-agent search problem. We address a few theoretical issues such as optimality of deployment, convergence and spatial distributedness of the control law and the search strategies. Simulation experiments are carried out to compare performances of the proposed strategies with a few simple search strategies.

Spin Probe Signature of Freezing in Water Slow Cooling Experiment: Our Observation is Global or Local?

First systematic spin probe ESR study of water freezing has been conducted using TEMPOL and TEMPO as the probes. The spin probe signature of the water freezing has been described in terms of the collapse of narrow triplet spectrum into a single broad line. This spin probe signature of freezing has been observed at an anomalously low temperature when a milimoler solution of TEMPOL is slowly cooled from room temperature. A systematic observation has revealed a spin probe concentration dependence of these freezing and respective melting points. These results can be explained in terms of localization of spin probe and liquid water,most probably in the interstices of ice grains, in an ice matrix. The lowering of spin probe freezing point, along with the secondary evidences, like spin probe concentration dependence of peak-to-peak width in frozen limit signal, indicates a possible size dependence of these localizations/entrapments with spin probe concentration. A weak concentration dependence of spin probe assisted freezing and melting points, which has been observed for TEMPO in comparison to TEMPOL, indicates different natures of interactions with water of these two probes. This view is also supported by the relaxation behavior of the two probes.

Search on a Hypercubic Lattice using Quantum Random Walk

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d=2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [ A. Patel and M. A. Rahaman Phys. Rev. A 82 032330 (2010)] provides an O(√NlnN) algorithm, which is not optimal. The scaling behavior can be improved to O(√NlnN) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78 012310 (2008). We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.

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.

Multi-agent Search using Voronoi partitions

This paper addresses the problem of multiagent search in an unknown environment. The agents are autonomous in nature and are equipped with necessary sensors to carry out the search operation. The uncertainty, or lack of information about the search area is known a priori as a probability density function. The agents are deployed in an optimal way so as to maximize the one step uncertainty reduction. The agents continue to deploy themselves and reduce uncertainty till the uncertainty density is reduced over the search space below a minimum acceptable level. It has been shown, using LaSalle’s invariance principle, that a distributed control law which moves each of the agents towards the centroid of its Voronoi partition, modified by the sensor range leads to single step optimal deployment. This principle is now used to devise search trajectories for the agents. The simulations were carried out in 2D space with saturation on speeds of the agents. The results show that the control strategy per step indeed moves the agents to the respective centroid and the algorithm reduces the uncertainty distribution to the required level within a few steps.

Self Assessment-Based Decision Making for Multiagent Cooperative Search

This paper addresses a search problem with multiple limited capability search agents in a partially connected dynamical networked environment under different information structures. A self assessment-based decision-making scheme for multiple agents is proposed that uses a modified negotiation scheme with low communication overheads. The scheme has attractive features of fast decision-making and scalability to large number of agents without increasing the complexity of the algorithm. Two models of the self assessment schemes are developed to study the effect of increase in information exchange during decision-making. Some analytical results on the maximum number of self assessment cycles, effect of increasing communication range, completeness of the algorithm, lower bound and upper bound on the search time are also obtained. The performance of the various self assessment schemes in terms of total uncertainty reduction in the search region, using different information structures is studied. It is shown that the communication requirement for self assessment scheme is almost half of the negotiation schemes and its performance is close to the optimal solution. Comparisons with different sequential search schemes are also carried out. Note to Practitioners-In the futuristic military and civilian applications such as search and rescue, surveillance, patrol, oil spill, etc., a swarm of UAVs can be deployed to carry out the mission for information collection. These UAVs have limited sensor and communication ranges. In order to enhance the performance of the mission and to complete the mission quickly, cooperation between UAVs is important. Designing cooperative search strategies for multiple UAVs with these constraints is a difficult task. Apart from this, another requirement in the hostile territory is to minimize communication while making decisions. This adds further complexity to the decision-making algorithms. In this paper, a self-assessment-based decision-making scheme, for multiple UAVs performing a search mission, is proposed. The agents make their decisions based on the information acquired through their sensors and by cooperation with neighbors. The complexity of the decision-making scheme is very low. It can arrive at decisions fast with low communication overheads, while accommodating various information structures used for increasing the fidelity of the uncertainty maps. Theoretical results proving completeness of the algorithm and the lower and upper bounds on the search time are also provided.

Optimal association of mobile wireless devices with a WLAN-3G access network

In this paper, we consider the problem of association of wireless stations (STAs) with an access network served by a wireless local area network (WLAN) and a 3G cellular network. There is a set of WLAN Access Points (APs) and a set of 3G Base Stations (BSs) and a number of STAs each of which needs to be associated with one of the APs or one of the BSs. We concentrate on downlink bulk elastic transfers. Each association provides each ST with a certain transfer rate. We evaluate an association on the basis of the sum log utility of the transfer rates and seek the utility maximizing association. We also obtain the optimal time scheduling of service from a 3G BS to the associated STAs. We propose a fast iterative heuristic algorithm to compute an association. Numerical results show that our algorithm converges in a few steps yielding an association that is within 1% (in objective value) of the optimal (obtained through exhaustive search); in most cases the algorithm yields an optimal solution.

Quantum Algorithms with Fixed Points: The Case of Database Search

The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of $\frac{\pi}{3}$. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using $q$ oracle queries, these variations reduce the probability of finding a non-target state from $\epsilon$ to $\epsilon^{2q+1}$, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.

Anomalous X-ray scattering study of local structures in the superionic conducting glass (AgBr)0.4 (Ag2O)0.3 (GeO2)0.3

The local structural information in the near-neighbor region of superionic conducting glass (AgBr)0.4(Ag2O)0.3(GeO2)0.3 has been estimated from the anomalous X-ray scattering (AXS) measurements using Ge and Br K absorption edges. The possible atomic arrangements in the near-neighbor region of this glass were obtained by coupling the results with the least-squares variational method so as to reproduce two differential intensity profiles for Ge and Br as well as the ordinary scattering profile. The coordination number of oxygen around Ge is found to be 3.6 at a distance of 0.176 nm, suggesting the GeO4 tetrahedral unit as the probable structural entity in this glass. Moreover, the coordination number of Ag around Br is estimated as 6.3 at a distance of 0.284 nm, suggesting an arrangement similar to that in crystalline AgBr.

Relation between Local Structure and Glass Forming Ability of Liquid Alloys

An attempt has been made to describe the glass forming ability (GFA) of liquid alloys, using the concepts of the short range order (SRO) and middle range order (MRO) characterizing the liquid structure.A new approach to obtain good GFA of liquid alloys is based on the following four main factors: (1) formation of new SRO and competitive correlation with two or more kinds of SROs for crystallization, (2) stabilization of dense random packing by interaction between different types of SRO, (3) formation of stable cluster (SC) or middle range order (MRO) by harmonious coupling of SROs, and (4) difference between SRO characterizing the liquid structure and the near-neighbor environment in the corresponding equilibrium crystalline phases. The atomic volume mismatch estimated from the cube of the atomic radius was found to be a close relation with the minimum solute concentration for glass formation. This empirical guideline enables us to provide the optimum solute concentration for good GFA in some ternary alloys. Model structures, denoted by Bernal type and the Chemical Order type, were again tested in the novel description for the glass structure as a function of solute concentration. We illustrated the related energetics of the completion between crystal embryo and different types of SRO. Recent systematic measurements also provide that thermal diffusivity of alloys in the liquid state may be a good indicator of their GFA.

Reactive interdiffusion: deviation from local equilibrium in the Fe-NiTiO3 couple

Deviation from local equilibrium between Fe–Ni alloy and (Fe,Ni)TiO3 solid solution in the reaction–diffusion zone of the Fe–NiTiO3 couple at 1273 K is evaluated by comparing the measured compositions in the zone with experimentally determined equilibrium tie-lines. The deviation is quantified by computing the Gibbs energy change for the reaction, Fe + NiTiO3 → FeTiO3 + Ni, from measured compositions in the zone and activity data available in the literature. Except near the extremities of the zone, the computed Gibbs energy change is constant, 8.2 kJ mol−1 higher than the standard Gibbs energy change for the reaction.