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 Modified Dubins Method for Optimal Path Planning of a Miniature Air Vehicle Converging to a Straight Line Path

This paper presents a Dubins model based strategy to determine the optimal path of a Miniature Air Vehicle (MAV), constrained by a bounded turning rate, that would enable it to fly along a given straight line, starting from an arbitrary initial position and orientation. The method is then extended to meet the same objective in the presence of wind which has a magnitude comparable to the speed of the MAV. We use a modification of the Dubins' path method to obtain the complete optimal solution to this problem in all its generality.

Determination of optimal trajectory under design constraints for a satellite launch vehicle

An optimal pitch steering programme of a solid-fuel satellite launch vehicle to maximize either (1) the injection velocity at a given altitude, or (2) the size of circular orbit, for a given payload is presented. The two-dimensional model includes the rotation of atmosphere with the Earth, the vehicle's lift and drag, variation of thrust with time and altitude, inverse-square gravitational field, and the specified initial vertical take-off. The inequality constraints on the aerodynamic load, control force, and turning rates are also imposed. Using the properties of the central force motion the terminal constraint conditions at coast apogee are transferred to the penultimate stage burnout. Such a transformation converts a time-free problem into a time-fixed one, reduces the number of terminal constraints, improves accuracy, besides demanding less computer memory and time. The adjoint equations are developed in a compact matrix form. The problem is solved on an IBM 360/44 computer using a steepest ascent algorithm. An illustrative analysis of a typical launch vehicle establishes the speed of convergence, and accuracy and applicability of the algorithm.

Optimal iterative schemes for computing the Moore-Penrose matrix inverse

Among the iterative schemes for computing the Moore — Penrose inverse of a woll-conditioned matrix, only those which have an order of convergence three or two are computationally efficient. A Fortran programme for these schemes is provided.

Influence of adhesive non-linearities on the performance and optimal length of adhesive bonded joints

An analytical study for the static strength of adhesive lap joints is presented. The earlier solutions of Volkersen [i], DeBruyne[2] and others were limited to linear adhesives. The influence of adhesive non-linearity was first considered by Grimes' et al[3] and Dickson et al [4]. Recently Hart-Smith[5] successfully introduced elastic-plastic behaviour of the adhesive. In the present study the problem is formulated for general non-linear adhesive behaviour and an efficient numerical algorithm is written for the solution. Bilinear and trilinear models for the nonlinearity yield closed form analytical solutions.

A model for determining the optimal project life span and concession period of BOT projects

The concession agreement is the core feature of BOT projects, with the concession period being the most essential feature in determining the time span of the various rights, obligations and responsibilities of the government and concessionaire. Concession period design is therefore crucial for financial viability and determining the benefit/cost allocation between the host government and the concessionaire. However, while the concession period and project life span are essentially interdependent, most methods to date consider their determination as contiguous events that are determined exogenously. Moreover, these methods seldom consider the, often uncertain, social benefits and costs involved that are critical in defining, pricing and distributing benefits and costs between the various parties and evaluating potentially distributable cash flows. In this paper, we present the results of the first stage of a research project aimed at determining the optimal build-operate-transfer (BOT) project life span and concession period endogenously and interdependently by maximizing the combined benefits of stakeholders. Based on the estimation of the economic and social development involved, a negotiation space of the concession period interval is obtained, with its lower boundary creating the desired financial return for the private investors and its upper boundary ensuring the economic feasibility of the host government as well as the maximized welfare within the project life. The outcome of the new quantitative model is considered as a suitable basis for future field trials prior to implementation. The structure and details of the model are provided in the paper with Hong Kong tunnel project as a case study to demonstrate its detailed application. The basic contributions of the paper to the theory of construction procurement are that the project life span and concession period are determined jointly and the social benefits taken into account in the examination of project financial benefits. In practical terms, the model goes beyond the current practice of linear-process thinking and should enable engineering consultants to provide project information more rationally and accurately to BOT project bidders and increase the government's prospects of successfully entering into a contract with a concessionaire. This is expected to generate more negotiation space for the government and concessionaire in determining the major socioeconomic features of individual BOT contracts when negotiating the concession period. As a result, the use of the model should increase the total benefit to both parties.

Trajectory sensitivity modification in optimal linear systems

A new procedure for reducing trajectory sensitivity for the optimal linear regulator is described. The design is achieved without increase in the order of optimization and without the feedback of trajectory sensitivity. The procedure is also used in the input signal design problem for linear system identification by interpreting it as increasing trajectory sensitivity with respect to parameters to be estimated.

Causes and consequences of variation in nestling immune function

Defence against pathogens is a vital need of all living organisms that has led to the evolution of complex immune mechanisms. However, although immunocompetence the ability to resist pathogens and control infection has in recent decades become a focus for research in evolutionary ecology, the variation in immune function observed in natural populations is relatively little understood. This thesis examines sources of this variation (environmental, genetic and maternal effects) during the nestling stage and its fitness consequences in wild populations of passerines: the blue tit (Cyanistes caeruleus) and the collared flycatcher (Ficedula albicollis). A developing organism may face a dilemma as to whether to allocate limited resources to growth or to immune defences. The optimal level of investment in immunity is shaped inherently by specific requirements of the environment. If the probability of contracting infection is low, maintaining high growth rates even at the expense of immune function may be advantageous for nestlings, as body mass is usually a good predictor of post-fledging survival. In experiments with blue tits and haematophagous hen fleas (Ceratophyllus gallinae) using two methods, methionine supplementation (to manipulate nestlings resource allocation to cellular immune function) and food supplementation (to increase resource availability), I confirmed that there is a trade-off between growth and immunity and that the abundance of ectoparasites is an environmental factor affecting allocation of resources to immune function. A cross-fostering experiment also revealed that environmental heterogeneity in terms of abundance of ectoparasites may contribute to maintaining additive genetic variation in immunity and other traits. Animal model analysis of extensive data collected from the population of collared flycatchers on Gotland (Sweden) allowed examination of the narrow-sense heritability of PHA-response the most commonly used index of cellular immunocompetence in avian studies. PHA-response is not heritable in this population, but is subject to a non-heritable origin (presumably maternal) effect. However, experimental manipulation of yolk androgen levels indicates that the mechanism of the maternal effect in PHA-response is not in ovo deposition of androgens. The relationship between PHA-response and recruitment was studied for over 1300 collared flycatcher nestlings. Multivariate selection analysis shows that it is body mass, not PHA-response, that is under direct selection. PHA-response appears to be related to recruitment because of its positive relationship with body mass. These results imply that either PHA-response fails to capture the immune mechanisms that are relevant for defence against pathogens encountered by fledglings or that the selection pressure from parasites is not as strong as commonly assumed.

A closed-form optimal tuning of mass dampers for one degree-of-freedom systems under rotating unbalance forcing

This paper is focused on the study of a vibrating system forced by a rotating unbalance and coupled to a tuned mass damper (TMD). The analysis of the dynamic response of the entire system is used to define the parameters of such device in order to achieve optimal damping properties. The inertial forcing due to the rotating unbalance depends quadratically on the forcing frequency and it leads to optimal tuning parameters that differ from classical values obtained for pure harmonic forcing. Analytical results demonstrate that frequency and damping ratios, as a function of the mass parameter, should be higher than classical optimal parameters. The analytical study is carried out for the undamped primary system, and numerically investigated for the damped primary system. We show that, for practical applications, proper TMD tuning allows to achieve a reduction in the steady-state response of about 20% with respect to the response achieved with a classically tuned damper. Copyright © 2015 by ASME.

Optimal foreign aid and tariffs

This paper investigates the optimal choice of foreign aid when trade policies are decided in a non-cooperative fashion. Three alternative scenarios, depending on the timing of the actions and on whether aid is tied, are analyzed. It is shown that, in the case where aid is decided before tariffs, untied aid can lead to the reduction of the recipient's optimal trade tax. When the donor can tie the aid to a reduction in the recipient's tariff, the optimal aid level is always positive and the world can always achieve a Pareto-efficient equilibrium.

Scattering theory and the discrete linear optimal control problem

This paper deals with the interpretation of the discrete-time optimal control problem as a scattering process in a discrete medium. We treat the discrete optimal linear regulator, constrained end-point and servo and tracking problems, providing a unified approach to these problems. This approach results in an easy derivation of the desired results as well as several new ones.

Shape effect on optimal geometric conditions in surface aeration systems

The performance of surface aeration systems, among other key design variables, depends upon the geometric parameters of the aeration tank. Efficient performance and scale up or scale down of the experimental results of an aeration ystem requires optimal geometric conditions. Optimal conditions refer to the conditions of maximum oxygen transfer rate, which assists in scaling up or down the system for ommercial utilization. The present work investigates the effect of an aeration tank's shape (unbaffled circular, baffled circular and unbaffled square) on oxygen transfer. Present results demonstrate that there is no effect of shape on the optimal geometric conditions for rotor position and rotor dimensions. This experimentation shows that circular tanks (baffled or unbaffled) do not have optimal geometric conditions for liquid transfer, whereas the square cross-section tank shows a unique geometric shape to optimize oxygen transfer.

Delay Optimal Scheduling in a Two-Hop Vehicular Relay Network

We study a scheduling problem in a wireless network where vehicles are used as store-and-forward relays, a situation that might arise, for example, in practical rural communication networks. A fixed source node wants to transfer a file to a fixed destination node, located beyond its communication range. In the absence of any infrastructure connecting the two nodes, we consider the possibility of communication using vehicles passing by. Vehicles arrive at the source node at renewal instants and are known to travel towards the destination node with average speed v sampled from a given probability distribution. Th source node communicates data packets (or fragments) of the file to the destination node using these vehicles as relays. We assume that the vehicles communicate with the source node and the destination node only, and hence, every packet communication involves two hops. In this setup, we study the source node's sequential decision problem of transferring packets of the file to vehicles as they pass by, with the objective of minimizing delay in the network. We study both the finite file size case and the infinite file size case. In the finite file size case, we aim to minimize the expected file transfer delay, i.e. expected value of the maximum of the packet sojourn times. In the infinite file size case, we study the average packet delay minimization problem as well as the optimal tradeoff achievable between the average queueing delay at the source node buffer and the average transit delay in the relay vehicle.

An optimal dynamic inversion-based neuro-adaptive approach for treatment of chronic myelogenous leukemia

Combining the advanced techniques of optimal dynamic inversion and model-following neuro-adaptive control design, an innovative technique is presented to design an automatic drug administration strategy for effective treatment of chronic myelogenous leukemia (CML). A recently developed nonlinear mathematical model for cell dynamics is used to design the controller (medication dosage). First, a nominal controller is designed based on the principle of optimal dynamic inversion. This controller can treat the nominal model patients (patients who can be described by the mathematical model used here with the nominal parameter values) effectively. However, since the system parameters for a realistic model patient can be different from that of the nominal model patients, simulation studies for such patients indicate that the nominal controller is either inefficient or, worse, ineffective; i.e. the trajectory of the number of cancer cells either shows non-satisfactory transient behavior or it grows in an unstable manner. Hence, to make the drug dosage history more realistic and patient-specific, a model-following neuro-adaptive controller is augmented to the nominal controller. In this adaptive approach, a neural network trained online facilitates a new adaptive controller. The training process of the neural network is based on Lyapunov stability theory, which guarantees both stability of the cancer cell dynamics as well as boundedness of the network weights. From simulation studies, this adaptive control design approach is found to be very effective to treat the CML disease for realistic patients. Sufficient generality is retained in the mathematical developments so that the technique can be applied to other similar nonlinear control design problems as well.