As Internet advertisements (also called "ads") revenue growth is being driven further than ever before, one challenge facing publishers, such as Google and Amazon, is to quickly select and place a group of ads in an ad space for each online user with the objective of maximizing the expected revenue. This is especially challenging in the context of mobile advertising due to the smaller screen size of mobile devices and longer user session. We notice that most existing models do not allow the publisher to place the same ad in multiple positions. However, it has been reported that people must see an advertisement at least several times before they will acquire enough interest to consider buying the product or service advertised. To capture this repetition effect we largely generalize the previous model by allowing the publisher to repeat the same ads multiple times. We also notice that many existing models assume that a user will leave the ad session permanently after clicking an ad. Our framework allows a more realistic but complicated user behavior by allowing a user to return to the previous ad session. Our model is able to capture many factors that may affect the click probability of an ad such as the intrinsic quality of the ad, the position of the ad, and all ads that have been previously displayed. We also extend our work to adaptive setting where publishers can dynamically adjust their ad display according to user's feedback. We develop effective algorithms with guarantees of finding either optimal or approximate solutions.

This study develops a data-driven approach to solve constrained optimization problems in which the decision maker does not have an analytic form for the objective function but knows what decision variables affect the function. The approach makes direct use of the available data, rather than first using the data to estimate the objective function and then solving the problem as a traditional optimization problem. The difficulty in first estimating the unknown objective function is that the decision maker needs to have sufficient knowledge of its properties that are necessary to guide the estimation process. Thus, our approach is appropriate for situations where such structural knowledge is absent, either because the domain is very complex or because the knowledge is deliberately hidden by a partner firm that has a vested interest in the outcome of the decision. Our approach comes with a worst-case performance guarantee that improves with the characteristics (size, pervasiveness) of the available data. We illustrate our technique on a traffic-stream mixing problem encountered by a supply side Internet advertising network that wishes to optimize the click revenue earned from ads. A head-to-head comparison (with the existing method used) on real data shows a significant increase (≥10%, on average) in the revenue. We also demonstrate the value of our approach under more general conditions. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0818 .

Input distortion is a common problem faced by expert systems, particularly those deployed with a Web interface. In this study, we develop novel methods to distinguish liars from truth-tellers, and redesign rule-based expert systems to address such a problem. The four proposed methods are termed split tree (ST), consolidated tree (CT), value-based split tree (VST), and value-based consolidated tree (VCT), respectively. Among them, ST and CT aim to increase an expert system’s accuracy of recommendations, and VST and VCT attempt to reduce the misclassification cost resulting from incorrect recommendations. We observe that ST and VST are less efficient than CT and VCT in that ST and VST always require selected attribute values to be verified, whereas CT and VCT do not require value verification under certain input scenarios. We conduct experiments to compare the performances of the four proposed methods and two existing methods, i.e., the traditional true tree (TT) method that ignores input distortion and the knowledge modification (KM) method proposed in prior research. The results show that CT and ST consistently rank first and second, respectively, in maximizing the recommendation accuracy, and VCT and VST always lead to the lowest and second lowest misclassification cost. Therefore, CT and VCT should be the methods of choice in dealing with users’ lying behaviors. Furthermore, we find that KM is outperformed by not only the four proposed methods, but sometimes even by the TT method. This result further confirms the advantage necessity of differentiating liars from truth-tellers when both types of users exist in the population. A supplemental video can be found at https://doi.org/10.1287/ijoc.2016.0728 .

Access control mechanisms in software systems administer user privileges by granting users permission to perform certain operations while denying unauthorized access to others. Such mechanisms are essential to ensure that important business functions in an organization are conducted securely and smoothly. Currently, the dominant access control approach in most major software systems is role-based access control. In this approach, permissions are first assigned to roles, and users acquire permissions by becoming members of certain roles. However, given the dynamic nature of organizations, a fixed set of roles usually cannot meet the demands that users (existing or new) have to conduct business. The typical response to this problem is to myopically create new roles to meet immediate demand that cannot be satisfied by an existing set of roles. This ad hoc creation of roles invariably leads to a proliferation in the number of roles with the accompanying administrative overhead. Based on discussions with practitioners, we propose a role refinement scheme that reconstructs a system of roles to reduce the cost of role management. We first show that the role-refinement problem is strongly NP-hard and then provide two polynomial-time approximation algorithms (a greedy algorithm and a randomized rounding algorithm) and establish their performance guarantees. Finally, numerical experiments—based on a real data set from a firm's enterprise resource planning system—are conducted to demonstrate the applicability and performance of our refinement scheme.

The explosive growth in the variety and size of social networks has focused attention on searching these networks for useful structures. Like the Internet or the telephone network, the ability to efficiently search large social networks will play an important role in the extent of their use by individuals and organizations alike. However, unlike these domains, search on social networks is likely to involve measures that require a set of individuals to collectively satisfy some skill requirement or be tightly related to each other via some underlying social property of interest. The aim of this paper is to highlight—and demonstrate via specific examples—the need for algorithmic results for some fundamental set-based notions on which search in social networks is expected to be prevalent. To this end, we argue that the concepts of an influential set and a central set that highlight, respectively, the specific role and the specific location of a set are likely to be useful in practice. We formulate two specific search problems: the elite group problem (EGP) and the portal problem (PP), that represent these two concepts and provide a variety of algorithmic results. We first demonstrate the relevance of EGP and PP across a variety of social networks reported in the literature. For simple networks (e.g., structured trees and bipartite graphs, cycles, paths), we show that an optimal solution to both EGP and PP is easy to obtain. Next, we show that EGP is polynomially solvable on a general graph, whereas PP is strongly NP-hard. Motivated by practical considerations, we also discuss (i) a size-constrained variant of EGP together with its penalty-based relaxation and (ii) the solution of PP on balanced and full d-trees and general trees.

The need to consolidate the information contained in heterogeneous data sources has been widely documented in recent years. In order to accomplish this goal, an organization must resolve several types of heterogeneity problems, especially the entity heterogeneity problem that arises when the same real-world entity type is represented using different identifiers in different data sources. Statistical record linkage techniques could be used for resolving this problem. However, the use of such techniques for online record linkage could pose a tremendous communication bottleneck in a distributed environment (where entity heterogeneity problems are often encountered). In order to resolve this issue, we develop a matching tree, similar to a decision tree, and use it to propose techniques that reduce the communication overhead significantly, while providing matching decisions that are guaranteed to be the same as those obtained using the conventional linkage technique. These techniques have been implemented, and experiments with real-world and synthetic databases show significant reduction in communication overhead.

The increasing popularity of the World Wide Web has made it an attractive medium for advertisers. As more advertisers place Internet advertisements (hereafter also called "ads"), it has become important for Web site owners to maximize revenue through the optimal selection and placement of these ads. Unlike most previous research, we consider a hybrid pricing model, where the price advertisers pay is a function of 1) the number of exposures of the ad and 2) the number of clicks on the ad. The problem is finding an ad schedule to maximize the Web site revenue under a hybrid pricing model. We formulate two versions of the problem - static and dynamic - and propose a variety of efficient solution techniques that provide near-optimal solutions. In the dynamic version, the schedule of ads is changed based on individual user click behavior. We show by using a theoretical proof under special circumstances and an experimental demonstration under general conditions that a schedule that adapts to the user click behavior consistently outperforms one that does not. We also demonstrate that to benefit from observing the user click behavior, the associated probability parameter need not be estimated accurately. For both of these versions, we examine the sensitivity of the revenue with respect to the model parameters.

Browser and proxy-server caching are effective and relatively inexpensive methods of improving Web performance. Most existing research considers caching to occur independently at the browser and the proxy server. When the browser and the proxy-server cache independently, documents may get duplicated across the two levels. This paper analyzes the impact of document duplication on the performance of several browser-proxy caching policies. We first derive an exact expression and an accurate approximation for the delay under a joint browser-proxy caching policy in which no duplication is permitted. This policy is compared to a base or benchmark policy in which caching occurs independently at the two levels, and hence, duplication of documents is freely permitted. We next propose a more general caching policy in which a controlled amount of duplication is permitted. This policy is analyzed and an exact expression and an approximate expression for performance are derived. Finally, a simulation study is performed to confirm the accuracy of the theoretical results and extend these results for situations that are difficult to analyze mathematically.

The explosive growth in online shopping has provided online retailers impressive opportunities to extend revenue and profit. However, retailers may lose considerable online business from slow response times at electronic shopping sites. Although increasing server capacity may improve response time, the resources needed to do so are clearly not free. In this study, we propose a scheme that can improve a server's performance with no more than its current capacity. This scheme is based on priority processing, where the priority assigned to a customer depends on the potential revenue that is likely to be generated from the customer. The results for single-period analysis show that the benefit from priority processing increases as the server becomes more heavily utilized. We have also modeled a multiperiod version of the problem, where the demand in a period depends on the quality of service (QoS) that buyers receive in the previous period. In the multiperiod problem, both the server capacity and the processing policy in each period are determined optimally. Here, it may be optimal for the retailer to sacrifice profit and increase QoS in initial periods in order to increase demand (and revenue) in later periods. Thus, the processing policy of the server evolves from an emphasis on QoS in initial periods, to one on profit in subsequent periods.

The importance of software maintenance in managing the life-cycle costs of a system cannot be overemphasized. Beyond a point, however, it is better to replace a system rather than maintain it. We derive model and operating policy that reduces the sum of maintenance and replacement costs in the useful life of a software system. The main goal is to compare uniform (occurring at fixed time intervals) versus flexible (occurring at varying, planned time intervals) polices for maintenance and replacement. The model draws from the empirical works of earlier researchers to consider 1) inclusion of user requests for maintenance, 2) scale economies in software maintenance, 3) efficiencies derived from replacing old software technology with new software technology, and 4) the impact of software reuse on replacement and maintenance. Results from our model show that the traditional practice of maintaining or replacing a software system at uniform time intervals may not be optimal. We also find that an increase in software reuse leads to more frequent replacement, but the number of maintenance activities is not significantly impacted.

We derive bounds on the probability of a goal node given a set of acquired input nodes. The bounds apply to decomposable networks; a class of Bayesian networks encompassing causal trees and causal polytrees. The difficulty of computing the bounds depends on the characteristics of the decomposable network. For directly connected networks with binary goal nodes, tight bounds can be computed in polynomial time. For other kinds of decomposable networks, the derivation of the bounds requires solving an integer program with a nonlinear objective function, a computationally intractable problem in the worst case. We provide a relaxation technique that computes looser bounds in polynomial time for more complex decomposable networks. We briefly describe an application of the probability bounds to a record linkage problem.

In constructing a software system, extended periods of coding without adequate coordination (such as system integration and testing) can result in considerable fault correction effort. On the other hand, too much coordination can also prove counterproductive by disrupting the smooth flow of development work. The goal, therefore, is to find an optimal level of coordination so as to minimize system construction effort while adhering to functionality and schedule constraints. Previous research, however, has not considered dynamic project factors such as system growth, system stability and team learning when addressing the above coordination problem. Dynamic factors are important because they could lead to differences in the intensity (frequency) of coordination needed at different stages of system construction. Unlike existing studies, we propose a dynamic coordination policy that places coordination activities at optimal (and often nonuniform) intervals during the construction of a system. Our analysis shows that, if a system stabilizes slowly, more intense coordination should occur early in the project. Also, if the team's knowledge of the system improves with time (i.e. learning effects are present), more intense coordination should occur both near the beginning and near the end of the project. Our analysis also shows that, by encouraging more frequent coordination, superior development tools could facilitate team learning. Finally, the application of the coordination model to data from a NASA software project demonstrates that optimally coordinating a project could significantly reduce the system construction cost.

We study the presence of economic bias in the training data used to develop inductive expert systems. Such bias arises when an expert considers economic factors in decision making. We find that the presence of economic bias is particularly harmful when there is an economic misalignment between the expert and the user of the induced expert system. Such misalignment is referred to as differential bias. The most significant contribution of this study is a training data debiasing procedure that uses a genetic algorithm to reconstruct training data that is relatively free of economic bias. We conduct a series of simulation experiments that show: the economic performance of accuracy and value seeking algorithms is statistically the same when the training data has economic bias; both accuracy and value seeking algorithms suffer in the presence of differential bias; the proposed debiasing procedure significantly combats differential bias; and the debiasing procedure is quite robust with respect to estimation errors in its input parameters.

We study the sequential information acquisition problem for rule-based expert systems as follows: find the information acquisition strategy that minimizes the expected cost to operate the system while maintaining the same output decisions. This problem arises for rule-based expert systems when the cost or time to collect inputs is significant and the inputs are not known until the system operates. We develop several “optimistic” heuristics to generate information acquisition strategies and study their properties. The heuristics provide choices concerning precision (i.e., how optimistic) versus computational effort. The heuristics are embedded into an informed search algorithm (based on AO*) that produces an optimal strategy and a greedy search algorithm. The search strategies are designed for situations in which rules can overlap and the cost of collecting an input may depend on the set of inputs previously collected. We study the properties of these approaches and simulate their performance on a variety of synthetic expert systems. Our results indicate that the heuristics are very precise, leading to near optimal results for greedy search and moderate search effort for optimal search.

Sequential decision models are an important element of expert system optimization when the cost or time to collect inputs is significant and inputs are not known until the system operates. Many expert systems in business, engineering, and medicine have benefited from sequential decision technology. In this survey, we unify the disparate literature on sequential decision models to improve comprehensibility and accessibility. We separate formulation of sequential decision models from solution techniques. For model formulation, we classify sequential decision models by objective (cost minimization versus value maximization) knowledge source (rules, data, belief network, etc.), and optimized form (decision tree, path, input order). A wide variety of sequential decision models are discussed in this taxonomy. For solution techniques, we demonstrate how search methods and heuristics are influenced by economic objective, knowledge source, and optimized form. We discuss open research problems to stimulate additional research and development.