Dynamic bidding strategies in search-based advertising

Search-based advertising allows the advertisers to run special campaigns targeted to different groups of potential consumers at low costs. Google, Yahoo and Microsoft advertising programs allow the advertisers to bid for an ad position on the result page of a user’s query when the user searches for a keyword that the advertiser relates to its products or services. The expected revenue generated by the ad depends on the ad position, and the ad positions of the advertisers are concurrently determined after an instantaneous auction based on the bids of the advertisers. The advertisers are charged only when their ads are clicked by the users. To avoid excessive ad expenditures due to sudden surges in the keyword-search activities, each advertiser reserves a fixed finite daily budget, and the ads are not shown in the remainder of the day when the budget is depleted. Arrival times of keyword-search instances, ad positions, ad selections, and sales generated by the ads are random. Therefore, an advertiser faces a dynamic stochastic total net revenue optimization problem subject to a strict budget constraint. Here we formulate and solve this problem using dynamic programming. We show that there is always an optimal dynamic bidding policy. We describe an iterative numerical approximation algorithm that uniformly converges to the optimal solution at an exponential rate of the number of iterations. We illustrate the algorithm on numerical examples. Because dynamic programing calculations of the optimal bidding policies are computationally demanding, we also propose both static and dynamic alternative bidding policies. We numerically compare the performances of optimal and alternative bidding policies by systematically changing each input parameter. The relative percentage total net revenue losses of the alternative bidding policies increases with the budget loading, but were never more than 3.5 % of maximum expected total net revenue. The best alternative to the optimal bidding policy turned out to be a static greedy bidding policy. Finally, statistical estimation of the model parameters is visited.     

Optimal keyword bidding in search-based advertising with target exposure levels

Search-based advertising has become very popular since it provides advertisers the ability to attract potential customers with measurable returns. In this type of advertising, advertisers bid on keywords to have an impact on their ad’s placement, which in turn affects the response from potential customers. An advertiser must choose the right keywords and then bid correctly for each keyword in order to maximize the expected revenue or attain a certain level of exposure while keeping the daily costs in mind. In response to increasing need for analytical models that provide a guidance to advertisers, we construct and examine deterministic optimization models that minimize total expected advertising costs while satisfying a desired level of exposure. We investigate the relationship between our problem and the well-known continuous non-linear knapsack problem, and then solve the problem optimally by utilizing Karush–Kuhn–Tucker conditions. We present practical managerial insights based on the analysis of both a real-life data from a retailer and a hypothetical data.     

组合拍卖在门户网站广告机会分配中的应用

目前门户网站的广告机会销售主要通过价格协商的方式,这种方式不仅导致大量的中间交易成本而且分配结果常常无法达到最优.针对该情形,本文结合门户网站广告机会的特点,建立了广告机会分配的组合拍卖模型.该模型能让广告主自由的表达广告机会之间的无差异及互补效用.通过将该模型的特例转化为一般背包问题,文中证明了该问题求解的NP难特性.因此本文针对标的本身的结构提出了四种启发式信息及两种求解器:二元蚁群算法及贪婪算法.最后通过数值实验给出了在不同情况下,不同启发信息的性能并表明了在任何情况下二元蚁群算法比贪婪算法的寻优性更强.     

A mathematical model for personalized advertisement in virtual reality environments

We consider a personalized advertisement assignment problem faced by the manager of a virtual reality environment. In this online environment, users log in/out, and they spend time in different virtual locations while they are online. Every time a user visits a new virtual location, the site manager can show the ad of an advertiser. At the end of a fixed time horizon, the manager collects revenues from all of the advertisers, and the total revenue depends on the number of ads of different advertisers she displays to different users. In this setup, the objective of the manager is to find an optimal dynamic ad display policy in order to maximize her expected revenue. In the current paper, we formulate this problem as a continuous time stochastic optimization problem in which the actions of users are represented with two-state Markov processes and the manager makes display decisions at the transition times of these processes. To our best knowledge, no formal stochastic model and rigorous analysis has been given for this practical problem. Such a model and its analysis are the major contributions of this paper along with an optimal solution.     

A generic auction algorithm for the minimum cost network flow problem

In this paper we broadly generalize the assignment auction algorithm to solve linear minimum cost network flow problems. We introduce a generic algorithm, which contains as special cases a number of known algorithms, including the -relaxation method, and the auction algorithm for assignment and for transportation problems. The generic algorithm can serve as a broadly useful framework for the development and the complexity analysis of specialized auction algorithms that exploit the structure of particular network problems. Using this framework, we develop and analyze two new algorithms, an algorithm for general minimum cost flow problems, called network auction, and an algorithm for thek node-disjoint shortest path problem.     

关键词广告支付模式的研究

关键词广告是主要用于搜索引擎的一种广告销售机制.所谓关键词既指搜索用户在搜索框内输入的检索词,也指机器程序从用户浏览的网页内容中抓取的词.广告主的广告依据关键词触发而展现在相应网页上.对搜索引擎来说,选择广告的支付模式是销售机制的核心命题.在互联网发展的实践中出现了许多支付模式,比如按展现付费(Pay-Per-Impression),接点击付费(Pay-Per-Click),按呼叫付费(Pay-Per-Call)和按销量付费(Pay-Per-Sale)等.如果实现这些支付模式的条件都具备,那么哪一种付费方式对搜索引擎是最有利的?试图回答这个问题.主要结论是对搜索引擎来讲,按点击付费是最优或近似最优的支付模式.     

Rang moyen de familles de courbes elliptiques et lois de Sato-Tate

The goal of this note is to give some complements to an article of Fouvery and Pomykala: by anad-hoc method, they bound on average the rank of elliptic curves over in polynomial families:y ²=x ³=a(t)x+b(t) whent varies in under some generic conditions on the polynomials (over a(t),b(t). Here, by a more systematic treatment, we are able to relax most of these conditions, keeping only the natural one (the family is not geometricaly trivial). However, this result, specialized to the case treated by Fouvry and Pomykala, yields a better bound; our method depends on the distribution of the number of points in families of elliptic curves over finite fields (known as the vertical Sato-Tate law), which itself depends on the work of Deligne on the Weil conjectures.

     

Rate of Convergence Analysis of Discretization and Smoothing Algorithms for Semiinfinite Minimax Problems

Discretization algorithms for semiinfinite minimax problems replace the original problem, containing an infinite number of functions, by an approximation involving a finite number, and then solve the resulting approximate problem. The approximation gives rise to a discretization error, and suboptimal solution of the approximate problem gives rise to an optimization error. Accounting for both discretization and optimization errors, we determine the rate of convergence of discretization algorithms, as a computing budget tends to infinity. We find that the rate of convergence depends on the class of optimization algorithms used to solve the approximate problem as well as the policy for selecting discretization level and number of optimization iterations. We construct optimal policies that achieve the best possible rate of convergence and find that, under certain circumstances, the better rate is obtained by inexpensive gradient methods.     

Telecom service provider portal: Revenue sharing and outsourcing

Early mobile phones only provided voice transmission, for a fee. They have now evolved into voice and online data portals for providing additional services through 3rd party vendors. These service providers (vendors) are given access to a customer base “owned” by the mobile phone companies, for a fee. Typically customers make two payments: to the mobile phone company for phone services and to the 3rd party vendors for specific services bought from them. Variations to the above business model may involve outsourcing the online portal and/or acquiring customers from other independent portals. For these scenarios, we study how the fees for phone service and customer access are established and how they may relate to the prices of vendor services, and which services should be located on the portal - all in a game-theoretic context. Our results prove that it is possible to reorganize revenue flows through an invoicing process that may benefit the mobile network operator more than the other parties. In addition, we establish optimality in terms of the number of vendors on the portal, and determine a rank-ordering of vendors for their inclusion into the portal.     

The effect of information on the quality of decisions

We study the effect of additional information on the quality of decisions. We define the extreme case of complete information about probabilities as our reference scenario. There, decision makers (DMs) can use expected utility theory to evaluate the best alternative. Starting from the worst case—where DMs have no information at all about probabilities—we find a method of constantly increasing the information by systematically limiting the ranges of the probabilities. In our simulation-based study, we measure the effects of the constant increase in information by using different forms of relative volumes. We define these as the relative volumes of the gradually narrowing areas which lead to the same (or a similar) decision as with the probability in the reference scenario. Thus, the relative volumes account for the quality of information. Combining the quantity and quality of information, we find decreasing returns to scale on information, or in other words, the costs of gathering additional information increase with the level of information. Moreover, we show that more available alternatives influence the decision process negatively. Finally, we analyze the quality of decisions in processes where more states of nature are considered. We find that this degree of complexity in the decision process also has a negative influence on the quality of decisions.     

Optimal consumption and arbitrage in incomplete,finite state security markets

We study a consistent treatment for both the multi-period portfolio selection problem and the option attainability problem by a dual approach. We assume that time is discrete, the horizon is finite, the sample space is finite and the number of securities is less than that of the possible securities price transitions, i.e. an incomplete security market. The investor is prohibited from investing stocks more than given linear investment amount constraints at any time and he maximizes an expected additive utility function for the consumption process. First we give a set of budget feasibility conditions so that a consumption process is attainable by an admissible portfolio process. To establish this relation, we used an algorithmic approach which has a close connection with the linear programming duality. Then we prove the unique existence of a primal optimal solution from the budget feasibility conditions. Finally, we formulate a dual control problem and establish the duality between primal and dual control problems.We are grateful to the editor, Hiroshi Konno, and two anonymous referees for their valuable comments and constructive suggestions on this research. We are responsible for the remaining errors. The first author is supported in part by the fund endowed to the Research Association for Financial Engineering by Toyo Trust Bank Co. and Mito Shoken Co.     

On approximation of the best case optimal value in interval linear programming

Interval linear programming addresses problems with uncertain coefficients and the only information that we have is that the true values lie somewhere in the prescribed intervals. For the inequality constraint problem, computing the worst case scenario and the corresponding optimal value is an easy task, but the best case optimal value calculation is known to be NP-hard. In this paper, we discuss lower and upper bound approximation for the best case optimal value, and propose suitable methods for both of them. We also propose a not apriori exponential algorithm for computing the best case optimal value. The presented techniques are tested by randomly generated data, and also applied in a simple data classification problem.     

Infinitesimal adjunction and polar curves

The polar curves of foliations having a curve C of separatrices generalize the classical polar curves associated to hamiltonian foliations of C. As in the classical theory, the equisingularity type ℘() of a generic polar curve depends on the analytical type of , and hence of C. In this paper we find the equisingularity types ε(C) of C, that we call kind singularities, such that ℘() is completely determined by ε(C) for Zariski-general foliations . Our proofs are mainly based on the adjunction properties of the polar curves. The foliation-like framework is necessary, otherwise we do not get the right concept of general foliation in Zariski sense and, as we show by examples, the hamiltonian case can be out of the set of general foliations. The author was partially supported by the research projects MTM2007-66262 (Ministerio de Educación y Ciencia), MTM2006-15338-C02-02 (Ministerio de Educación y Ciencia),VA059A07 (Junta de Castilla y León) and PGIDITI06PXIB377128PR (Xunta de Galicia).     

The newsvendor’s optimal incentive contracts for multiple advertisers

We consider a newsvendor who earns a revenue from the sales of her product to end users as well as from multiple advertisers paying to obtain access to those end users. We study the optimal decisions of a price-taking and a price-setting newsvendor when the advertisers have private information about their willingness to pay. We focus on the impact of the number of advertisers on the newsvendor’s optimal decisions. We find that regardless of the number of advertisers, the newsvendor may exclude advertisers with a low willingness to pay and distort the price and inventory from their system-efficient levels to screen the advertisers. Moreover, the newsvendor’s decision to exclude an advertiser is based exclusively on that advertiser’s characteristics, and the newsvendor’s optimal decision thus reveals independence among the advertisers. Nonetheless, the profits of the newsvendor and the advertisers also display network effects as both increase in the number of advertisers. Finally, our numerical results show that the newsvendor prefers an equivalent single advertiser to multiple advertisers due to the pooling effect.     

Stability analysis and optimal control of a hand-foot-mouth disease (HFMD) model

In this paper, we propose a system of ordinary differential equations to model the hand-foot-mouth disease (HFMD). We derive the expression of the basic reproduction number . When , the system only has the disease free equilibrium, which is globally asymptotically stable; otherwise, the system is persistent. By sensitivity analysis, we identify the control parameters. Then we formulate an optimal control problem to find the optimal control strategy. These results are applied to the spread of HFMD in Mainland China. The basic reproduction number tells us that it is outbreak in China.     

Régularisation et $ \bar \partial_b $ homotopie sur les variétés CR

We give a regularization and ‐homotopy formula on CR generic manifolds. As a consequence we obtain some isomorphism theorems between cohomological groups. This work generalizes Chirka results given on complex manifolds.     

Generic properties of the complementarity problem

Givenf: R ₊ ⁿ R ⁿ , the complementarity problem is to find a solution tox 0,f(x) 0, and x, f(x) = 0. Under the condition thatf is continuously differentiable, we prove that for a generic set of such anf, the problem has a discrete solution set. Also, under a set of generic nondegeneracy conditions and a condition that implies existence, we prove that the problem has an odd number of solutions.This work was partially supported by N.S.F. Grants GP-8007 and 010185.     

The stochastic goodwill problem

Stochastic control problems related to optimal advertising under uncertainty are considered. In particular, we determine the optimal strategies for the problem of maximizing the utility of goodwill at launch time and minimizing the disutility of a stream of advertising costs that extends until the launch time for some classes of stochastic perturbations of the classical Nerlove–Arrow dynamics. We also consider some generalizations such as problems with constrained budget and with discretionary launching.     

Excess of locally D-optimal designs and homothetic transformations

The paper is devoted to the study of homothety’s influence on the number of optimal design support points under fixed values of a regression model’s parameters. The Ayen–Peters two-dimensional nonlinear in parameters model used in analytical chemistry is considered. It is shown that the number of optimal design support points must be greater than or equal to the number of parameters depending on certain conditions. The optimal designs with the minimal number of support points are constructed explicitly. Some numerical methods for constructing designs with greater number of points (we suggest to call them excess designs) are used.     

Identification of the Optimal Active Set in a Noninterior Continuation Method for LCP

This paper concerns about the possibility of identifying the active set in a noninterior continuation method for solving the standard linear complementarity problem based on the algorithm and theory presented by Burke and Xu (J. Optim. Theory Appl. 112 (2002) 53). It is shown that under the assumptions of P-matrix and nondegeneracy, the algorithm requires at most Olog(₀₀/)) iterations to find the optimal active set, where ₀ is the width of the neighborhood which depends on the initial point, ₀> 0 is the initial smoothing parameter, is a positive number which depends on the problem and the initial point, and is a small positive number which depends only on the problem.