Stochastic optimization on social networks with application to service pricing

In this paper we develop a combined simulation and optimization approach for solving difficult decision problems on complex dynamic networks. For a specific reference problem we consider a telecommunication service provider who offers a telecommunication service to a market with network effects. More particularly, the service consumption of an individual user depends on both idiosyncratic characteristics and the popularity of this service among the customer’s immediate neighborhood. Both the social network and the individual user preferences are largely heterogeneous and changing over time. In addition the service provider’s decisions are made in absence of perfect knowledge about user preferences. The service provider pursues the strategy of stimulating the demand by offering differentiated prices to the customers. For finding the optimal pricing we apply a stochastic quasi-gradient algorithm that is integrated with a simulation model that drives the evolution of the network and user preferences over time. We show that exploiting the social network structure and implementing differentiated pricing can substantially increase the revenues of a service provider operating on a social network. More generally, we show that stochastic gradient methods represent a powerful methodology for the optimization of decisions in social networks.     

A Network Optimization Model for Budget Planning in Multi-Objective Hierarchical Systems

This paper presents a planning/budgeting scheme for hierarchical systems. A multi-objective network optimization model for multilayer budget allocation is suggested. The network presents the hierarchical structure of the system. The budget allocations are the flows in the network. Each component in the system (arc in the network) has lower and upper bounds. The model maximizes the additive utility function of the system, expressed as a weighted summation over the preferences of the system's components in the various levels. The preferences are evaluated by using a multigoal approach, utilizing the Analytical Hierarchy Process (AHP). Finally, the model is conceptually compared with other known budgeting procedures and models, such as ZBB, PBBS and cost benefit analyses.     

Network production-location problems under price uncertainty

The scope of the network plant location problem is extended in three significant ways: (i) The ‘design’ of the facility, including consideration of input substitution and the level of output, is combined with the location decision; (ii) input and output prices are treated as random variables, and (iii) the risk preferences of the decision maker are considered explicitly in the decision making process. Node optimality properties are developed for several model variations. An elimination-by-bound solution algorithm is presented along with suggested upper and lower bounds and methods of simplification. Under certain conditions, the optimal input ratios and plant locations are shown to be invariant with some parametric changes. The potential for influencing the location decisions of firms, depending upon the characteristics of their risk preferences, production functions, and the demand functions for their input, through manipulation of the risk they face, is illustrated.     

Representing and Learning Distributions with the Aid of a Neural Network

This paper describes a method by which a neural network learns to fit a distribution to sample data. The neural network may be used to replace the input distributions required in a simulation or mathematical model and it allows random variates to be generated for subsequent use in the model. Results are given for several data sets which indicate the method is robust and can represent different families of continuous distributions. The neural network is a three-layer feed-forward network of size (1-3-3-1). This paper suggests that the method is an alternative approach to the problem of selection of suitable continuous distributions and random variate generation techniques for use in simulation and mathematical models.     

On the probability of a rational outcome for generalized social welfare functions on three alternatives

In Kalai (2002) [10], Kalai investigated the probability of a rational outcome for a generalized social welfare function (GSWF) on three alternatives, when the individual preferences are uniform and independent. In this paper we generalize Kalai's results to a broader class of distributions of the individual preferences, and obtain new lower bounds on the probability of a rational outcome in several classes of GSWFs. In particular, we show that if the GSWF is monotone and balanced and the distribution of the preferences is uniform, then the probability of a rational outcome is at least 3/4, proving a conjecture raised by Kalai. The tools used in the paper are analytic: the Fourier-Walsh expansion of Boolean functions on the discrete cube, properties of the Bonamie-Beckner noise operator, and the FKG inequality.     

Properties of voting with veto power

The article investigates a game-theoretical model with veto power in application to the election of the chairman of the board in a corporation. Alternative voting rules are considered, the most interesting being open voting in a specified order. Conditions are determined when voter 1 can ensure the election of his candidate. A complete solution is obtained for three voters, both in the case of strict preferences and in the case when the preferences of voters 2 and 3 are incompletely defined (contain an uncertainty). The latter case is particularly relevant because it arises for several decision-making rules and is an inseparable part of the real-life election process, when the voters represent several interest groups.     

Structure and emergence in a nested logit model with social and spatial interactions

Suppose you have the possibility to choose to adopt one of a number of different behaviors or to choose to buy one of a number of different products, and suppose your choice is influenced by your individual perception of the average choices made by others. Economists Brock and Durlauf (in Am. Econ. Rev. 92(2):298, 2002; The Economy as an Evolving Complex System III. Oxford University Press, New York, 2006) have derived seminal theoretical results for the equilibrium behavior of the multinomial discrete choice model with social interactions, assuming homogeneous decision-makers, global interactions and laws of large of numbers. The research presented in this paper extends Brock and Durlauf’s model to allow for unobserved preference heterogeneity between choice alternatives by studying the nested logit model. Next, by drawing on the computational possibilities permitted through social simulation of multi-agent systems (MAS), this paper relaxes the assumption of global interactions and considers instead local interactions within several hypothesized social and spatial network structures. Additional heterogeneity is thus hereby induced by the influence on a given decision-maker’s choice by the particular network connections he or she has and the particular perceived percentages, for example, of the agent’s neighbors or socio-economic peers making each choice. Discrete choice estimation results controlling these heterogeneous individual preferences are embedded in a multi-agent based simulation model in order to observe the evolution of choice behavior over time with socio-dynamic feedback due to the network effects. The MAS approach also gives us an additional advantage in the possibility to test size effects, and thus relax the assumption of large numbers, as well as test the effect of different initial conditions. Finally an extra benefit is gained via the MAS approach in that we are not confined to study only the equilibrium behavior, and have the possibility here to observe the time-varying trajectories of the choice behavior. This is important since smaller network sizes are revealed to be associated with higher volatility of the choice behavior in this model, and consequently stochastic cycling between equilibria. Averaged over time, the emergent behavior in such case yields a quite different picture than the theoretical results predicted by Brock and Durlauf. Furthermore being able to observe the emergent behavior allows us to see the subtle role of the unobserved heterogeneity in the nested logit model in breaking the symmetry of the multinomial logit model. We can see the temporal patterns by which theoretically predicted dominant equilibria emerge or not according to different social and spatial network scenarios. With an eye towards application in the context of transportation mode choice, we conclude highlighting limitations of our present study and recommendations for future work.     

Timetabling optimization of a mixed double- and single-tracked railway network

The paper deals with the timetabling problem of a mixed multiple- and single-tracked railway network. Out of all the solutions minimizing the maximum relative travel time, the one minimizing the sum of the relative travel times is selected. User preferences are taken into account in the optimization problems, that is, the desired departure times of travellers are used instead of artificially planned departure times. To find the global optimum of the optimization problem, an algorithm based on the bisection rule is used to provide sharp upper bounds of the objective function together with one trick that allows us to drastically reduce the number of binary variables to be evaluated by considering only those which really matter. These two strategies together permit the memory requirements and the computation time to be reduced, the latter exponentially with the number of trains (several orders of magnitude for existing networks), when compared with other methods. Several examples of applications are presented to illustrate the possibilities and excellences of the proposed method. The model is applied to the case of the existing Madrid–Sevilla high-speed line (double track), together with several extensions to Toledo, Valencia, Albacete, and Málaga, which are contemplated in the future plans of the high-speed train Spanish network. The results show that the computation time is reduced drastically, and that in some corridors single-tracked lines would suffice instead of double-tracked lines.     

Bounding Distributions for Stochastic Logic Networks

A stochastic logic network is defined as a connected set of logic and time delay elements. Each of the latter elements has an associated probability distribution describing the nature of that element's delay. When used, for example, in project planning and scheduling, combinations of logic and time delay elements in such networks may represent conditions for the starting of project activities which are themselves represented by time delay elements. It is at present not known how to calculate the probability distributions for the events in such a network. This paper shows how to obtain upper and lower bounds for these probability distributions. The method is not a simulation technique; rather, it is a straightforward computational scheme derived from elementary probability theory. An example is given where the method is applied to a stochastic project scheduling network in which alternative ways exist for carrying out one of the jobs in the network.     

The clustering coefficient and the diameter of small-world networks

The small-world network, proposed by Watts and Strogatz, has been extensively studied for the past over ten years. In this paper, a generalized small-world network is proposed, which extends several small-world network models. Furthermore, some properties of a special type of generalized small-world network with given expectation of edge numbers have been investigated, such as the degree distribution and the isoperimetric number. These results are used to present a lower and an upper bounds for the clustering coefficient and the diameter of the given edge number expectation generalized small-world network, respectively. In other words, we prove mathematically that the given edge number expectation generalized small-world network possesses large clustering coefficient and small diameter.     

Reduction of overestimation in interval arithmetic simulation of biological wastewater treatment processes

A novel interval arithmetic simulation approach is introduced in order to evaluate the performance of biological wastewater treatment processes. Such processes are typically modeled as dynamical systems where the reaction kinetics appears as additive nonlinearity in state. In the calculation of guaranteed bounds of state variables uncertain parameters and uncertain initial conditions are considered. The recursive evaluation of such systems of nonlinear state equations yields overestimation of the state variables that is accumulating over the simulation time. To cope with this wrapping effect, innovative splitting and merging criteria based on a recursive uncertain linear transformation of the state variables are discussed. Additionally, re-approximation strategies for regions in the state space calculated by interval arithmetic techniques using disjoint subintervals improve the simulation quality significantly if these regions are described by several overlapping subintervals. This simulation approach is used to find a practical compromise between computational effort and simulation quality. It is pointed out how these splitting and merging algorithms can be combined with other methods that aim at the reduction of overestimation by applying consistency techniques. Simulation results are presented for a simplified reduced-order model of the reduction of organic matter in the activated sludge process of biological wastewater treatment.     

Interval articulation of superiority and precise elicitation of priorities

This paper develops an approach to obtaining precise (point) estimates of priorities of objects, in particular, coefficients of importance of criteria. It is assumed that the judgements regarding the preference superiority of one object over another are given in the forms of intervals, that is by indicating the lower and upper bounds. The suggested approach is suitable both in the case of consistent and inconsistent preferences. In the former case, the available intervals are processed by contracting them to the maximum degree, in the latter, by extending them to the minimum degree. The degrees of contraction or extension are regarded as the indexes of indeterminacy or inconsistency of preferences, and treated as multiple objective functions. A method of transformation of such a multicriterial problem to a sequence of several linear programming problems is suggested.     

Using a Neural Network to Enhance the Decision Making Quality of a Visual Interactive Simulation Model

The use of a neural network to represent the results of a simulation model is described. The neural network is implemented as an interaction within a visual interactive simulation model. All results obtained from the simulation are offered to the neural network. After a suitable period of training the quality of results obtained from the network matches those obtained by running the original simulation model. An example which embeds a neural network as an interaction within a visual interactive simulation model is described. The example shows how the combined system may enhance the decision making quality of a visual interactive simulation model.     

A system for priority routing and capacity assignment in packet switched networks

A model and its associated solution procedure for the problem of concurrent flow and capacity assignment in a packet switched network are presented. The distinguishing feature of the model lies in the fact that a user defined priority level is associated with each message in the network. Different service requirements and message characteristics are associated with each message class. An algorithm that generates good feasible solutions to the model, together with tight lower bounds on the value of the objective function, is developed. Results of numerical experiments using several network topologies are reported.     

An upper bound for the competitive location and capacity choice problem with multiple demand scenarios

A new mathematical model is considered related to competitive location problems where two competing parties, the Leader and the Follower, successively open their facilities and try to win customers. In the model, we consider a situation of several alternative demand scenarios which differ by the composition of customers and their preferences.We assume that the costs of opening a facility depend on its capacity; therefore, the Leader, making decisions on the placement of facilities, must determine their capacities taking into account all possible demand scenarios and the response of the Follower. For the bilevel model suggested, a problem of finding an optimistic optimal solution is formulated. We show that this problem can be represented as a problem of maximizing a pseudo- Boolean function with the number of variables equal to the number of possible locations of the Leader’s facilities.We propose a novel systemof estimating the subsets that allows us to supplement the estimating problems, used to calculate the upper bounds for the constructed pseudo-Boolean function, with additional constraints which improve the upper bounds.     

Dynamic simultaneous fare proration for large-scale network revenue management

Network revenue management is concerned with managing demand for products that require inventory from one or several resources by controlling product availability and/or prices in order to maximize expected revenues subject to the available resource capacities. One can tackle this problem by decomposing it into resource-level subproblems that can be solved efficiently, for example by dynamic programming. We propose a new dynamic fare proration method specifically having large-scale applications in mind. It decomposes the network problem by fare proration and solves the resource-level dynamic programs simultaneously using simple, endogenously obtained dynamic marginal capacity value estimates to update fare prorations over time. An extensive numerical simulation study demonstrates that the method results in tightened upper bounds on the optimal expected revenue, and that the obtained policies are very effective with regard to achieved revenues and required runtime.     

网络结构、采纳者偏好与创新扩散:基于采纳者决策过程的创新扩散系统动力学模型仿真分析

在对采纳者决策过程分析的基础上,将网络结构和采纳者偏好作为核心参数,构建基于采纳者决策过程的创新扩散系统动力学模型。对模型进行仿真发现,在采纳者趋同化偏好条件下,网络平均度、网络重连概率与采纳者偏好强度的变动趋势与创新扩散效率的变动趋势相同,而在采纳者差异化偏好条件下则与创新扩散效率变动趋势相反。网络平均路径长度对创新扩散的影响方向与采纳者偏好特征无关,提高网络平均路径长度会始终降低创新扩散的效率。采纳者的趋同化偏好能够放大创新扩散对网络结构变量与采纳者偏好强度变量的敏感程度,采纳者差异化偏好则会缩小创新扩散对网络结构变量与采纳者偏好强度变量的敏感程度。研究结果对于制定创新推广策略具有一定的指导意义。     

Locality and bounding-box quality of two-dimensional space-filling curves

Space-filling curves can be used to organise points in the plane into bounding-box hierarchies (such as R-trees). We develop measures of the bounding-box quality of space-filling curves that express how effective different space-filling curves are for this purpose. We give general lower bounds on the bounding-box quality measures and on locality according to Gotsman and Lindenbaum for a large class of space-filling curves. We describe a generic algorithm to approximate these and similar quality measures for any given curve. Using our algorithm we find good approximations of the locality and the bounding-box quality of several known and new space-filling curves. Surprisingly, some curves with relatively bad locality by Gotsman and Lindenbaum's measure, have good bounding-box quality, while the curve with the best-known locality has relatively bad bounding-box quality.     

Approximate valuation of average options

This paper concerns the valuation of average options of European type where an investor has the right to buy the average of an asset price process over some time interval, as the terminal price, at a prespecified exercise price. A discrete model is first constructed and a recurrence formula is derived for the exact price of the discrete average call option. For the continuous average call option price, we derive some approximations and theoretical upper and lower bounds. These approximations are shown to be very accurate for at-the-money and in-the-money cases compared to the simulation results. The theoretical bounds can be used to provide useful information in pricing average options.     

Spatial classification

The aim of a spatial classification is to position the units on a spatial network and to give simultaneously a set of structured classes of these units “compatible” with the network. We introduce the basic needed definitions: compatibility between a classification structure and a tessellation, (m,k)-networks as a case of tessellation, convex, maximal and connected subsets in such networks, spatial pyramids and spatial hierarchies. As like Robinsonian dissimilarities induced by indexed pyramids generalize ultrametrics induced by indexed hierarchies we show that a new kind of dissimilarity called “Yadidean” induced by spatial pyramids generalize Robinsonian dissimilarities. We focus on spatial pyramids where each class is a convex for a grid, and we show that there are several one-to-one correspondences with different kinds of Yadidean dissimilarities. These new results produce also, as a special case, several one-to-one correspondences between spatial hierarchies (resp. standard indexed pyramids) and Yadidean ultrametrics (resp. Robinsonian) dissimilarities. Qualities of spatial pyramids and their supremum under a given dissimilarity are considered. We give a constructive algorithm for convex spatial pyramids illustrated by an example. We show finally by a simple example that spatial pyramids on symbolic data can produce a geometrical representation of conceptual lattices of “symbolic objects”.