Modeling, Computation and Optimization

The following sections are included:

• Foreword

• Preface

• Acknowledgments

• Contents

We consider jamming in wireless networks in the framework of zero-sum games with linearized Shannon capacity utility function. The base station has to distribute the power fairly among the users in the presence of a jammer. The jammer in turn tries to distribute its power among the channels to produce as much harm as possible. This game can also be viewed as a minimax problem against the nature. We show that the game has the unique equilibrium and investigate its properties and also we developed an efficient algorithm which allows to find the optimal strategies in finite number of steps.

We study a one-way flow connections model of unilateral network formation. We prove the existence of Nash networks for games where the corresponding payoff functions allow for heterogeneity among the profits that agents gain by the network. Furthermore, we show by a counterexample that, when link costs are heterogeneous, Nash networks do not always exist.

We model and analyze strategic interaction over time in a duopolistic market. Each period the firms independently and simultaneously choose whether to advertise or not. Advertising increases the own immediate sales, but may also cause an externality, e.g., increase or decrease the immediate sales of the other firm ceteris paribus.

There exists also an effect of past advertisement efforts on current sales. The ‘market potential’ of each firm is determined by its own but also by its opponent's past efforts. A higher effort of either firm leads to an increase of the market potential, however the impact of the own past efforts is always stronger than the impact of the opponent's past efforts. How much of the market potential materializes as immediate sales, then depends on the current advertisement decisions.

We determine feasible rewards and (subgame perfect) equilibria for the limiting average reward criterion using methods inspired by the repeated-games literature. Uniqueness of equilibrium is by no means guaranteed, but Pareto efficiency may serve very well as a refinement criterion for wide ranges of the advertisement costs.

Unaware of the developments in each other's areas, researchers in the disciplines of Economics and Reliability Theory have been working independently. The objective of this paper is to point out some interesting relationships that exist between some of the notions in these two areas. In particular, we will discuss notions of NBUE (New Better Than Used in Expectation) order, HNBUE order, TTT (Total Time on Test) order from Reliability Theory and those of Lorenz Order, Excess Wealth Order from Economics. Some new results obtained recently about these stochastic orders will also be presented.

In the framework of cooperative games, we introduce the notions of semi-null players and semi-dummy players in order to provide a new axiomatization for the Shapley value. A semi-null player is powerful as a singleton, but powerless by joining another nonempty coalition. According to the axiomatic approach to solutions, semi-null players receive the egalitarian payoff. It is shown that the Shapley value is the unique solution verifying semi-null player property, symmetry, efficiency, and linearity. Shapley's original proof technique is essentially adapted in that the basis of unanimity games is replaced by the basis of the so-called complementary unanimity games being the main representatives of the class of 1-concave games.

This chapter proposes a class of weak additivity concepts for an operator on the set of real valued functions on a finite state space Ω. Let ɛ ⊆ 2^Ω be a set of subsets of Ω. Two functions x and y on Ω are ɛ-coextrema if, for each E ∈ ɛ, the set of minimizers of x restricted on E and that of y have a common element, and the set of maximizers of x restricted on E and that of y have a common element as well. An operator I on the set of functions on Ω is ɛ-coextrema additive if I(x + y) = I(x) + I(y) whenever x and y are ɛ-coextrema. So an additive operator is ɛ-coextrema additive, and an ɛ-coextrema additive operator is comonotonic additive. The main result characterizes homogeneous ɛ-coextrema additive operators.

In this chapter we are looking critically at our capitalist market system, or at least at the models we might use to predict market behaviour and make market decisions, and wondering what happened to the main player — the consumer — in the system. Indeed, the consumer, in most models is marginalized or dehumanized if considered at all. A revisit to both the logic and the ideals of capitalism of Adam Smith and others is undertaken. Creatively reengineering the market system is the task addressed. This requires an understanding of what constitutes a creative process.

Two kinds of applications of game theory were outlined in [Aumann (2008)]. In one we get insight into an interactive situation and, in the other, game theory tells us what to do. Aumann calls the second kind of applications, game engineering. Organisational systems gurus, Russell Ackoff and Sheldon Rovin explain how to outsmart bureaucracies in their celebrated work ‘Beating the System’ [Ackoff and Rovin (2005)]. What is common between game engineering and beating the system is creativity. We apply this understanding to games played in the market place. This leads us to consider thought experiments, social dialogues, and models that stipulate the rightful place for the consumers as main players.

Advertising plays a very important role in drawing consumer attention to new-products and in encouraging early adoptions. The problem of drawing optimal advertising plans for innovations have therefore has received a lot of attention from marketing managers and researchers. But there is need for further research on problems pertaining to new-products that are part of technological generations. This chapter deals with the determination of optimal advertising expenditure for two-generation consumer durables. The model considers intergenerational diffusion effect and also introduces a framework for modeling innovation diffusion for two competing generations.

In this chapter we employ a nonconvex separation theorem to scalarize the vector minimization problem subject to the constraint given in the form of set inclusion. A new Lagrange function is formulated for the scalarized problem. Saddle point criteria is developed which ensure the existence of the Lagrange multipliers. We also discuss the Lagrange duality.

In this chapter we define the concept of approximate optimal solutions for semi infinite programming problems. The KKT type necessary optimality conditions, characterizing approximate optimal solutions, are derived using the exact penalty function approach. Finally we provide the bound on the penalty parameter in terms of dual variables so as to obtain an almost approximate solution for the primal semi infinite programming problem.

We consider a one supplier - multiple retailers system over a finite planning horizon. Retailers have external demands for a single product and their inventories are controlled by the supplier based on order-up-to level inventory policy. The problem is to determine the time and the quantity of product to order for the supplier, the retailers to be visited in any period, the quantity of product to be delivered in these visits and the vehicle routes for deliveries so as to minimize system-wide inventory and routing costs. We present a Lagrangian relaxation based solution procedure and implement the procedure on test instances. Computational study shows that fairly good solutions are found in reasonable time.

In this chapter, we consider the probability and severity of ruin for a renewal class of risk process in which the claim inter occurrence times is Generalized Exponential. We have obtained closed form expression for the distribution of the deficit at ruin. We illustrate the application of this result with several examples.

This chapter presents the feasible proportional allocation rule to discourage free riding for a special class of free riding problems. Some theoretical and practical properties of the rule are discussed. Applications to the management of the Baltic Sea cod fishery and the Norwegian spring-spawning herring fishery are presented.

In this chapter we study a differential game, for the extraction activity of a renewable good, in which players are overlapping generations. The framework of overlapping generations allows us to consider intragenerational (players in the same generation) and intergenerational (players in different generations) game equilibria. We consider the case in which players, even if identical, face competition in an asymmetric way. Since we consider overlapping generations, players have asynchronous time horizons, in contrast with a number of studies in intertemporal exploitation of resources in which players have identical time horizons. We conclude by considering the case in which players compete in a leader-follower way. We introduce a Stackelberg differential game with asynchronous time horizons and non fixed role structure. The overlapping generations' framework results in the presence of two different behaviours, the myopic and the non-myopic behaviour. We present a possible solution for the myopic case.

Optimal Communication Spanning Tree Problem (OCSTP) is formulated as a mixed integer programming problem and Benders' Partitioning approach is applied for solving it. It is shown that after fixing the values of integer variables for defining a given tree, the dual of the resulting problem is very easy to solve. This dual solution is used to generate a cut for the Benders' master problem. Rather than solving the master problem directly as an integer program, we use the stan-dard local search algorithm to obtain an approximate solution. The algorithm proposed by us evaluates the Benders' objective function at each neighboring tree, and moves to the neighbor that minimizes this objective function. A cut for the master problem is generated from the new solution and added to the master problem. In order to achieve faster convergence, some constrains are imposed on the search. We present computational results on randomly generated 100-node problems, and compare the standard local search with Benders' search. The results show that starting from randomly selected initial trees, average solution quality produced by Benders' search is significantly better than that produced by standard local search.

An analogue of Sperner's lemma with multiple, unrestricted labels is proved. It extends a result due to Hochberg, McDiarmid and Saks obtained in the context of determining the bandwidth of the triangulated triangle.

Support Vector Machines (SVMs) suffer from the problem of large memory requirements and CPU time when trained in batch mode on large data sets. Therefore incremental techniques have been developed to facilitate batch SVM learning. In this chapter we propose a new incremental technique called Incremental Twin Support Vector Machines for training in batch mode. This technique is based on a newly developed classifier, called Twin Support Vector Machines (TWSVM) classifier. The TWSVM classifier determines two non-parallel planes by solving two related support vector machines-type problems, each of which is smaller than in a conventional Incremental SVM. Numerical implementation on several benchmark datasets has shown that the Incremental Twin SVM is not only fast, but also has good generalization.

Portfolio diversification (i.e., possessing shares of many companies at the same time for reducing risks) is considered to be an important task in the investor's community to reduce the risk of a portfolio without not necessarily reducing the returns. This chapter will present a classification study of different categories of companies on the basis of their various financial attributes using a quadratic optimization based classifier namely Support Vector Machine (SVM). We have also used this model for sector wise classification of the company. To validate the performance, we compared the results with the ratings for companies provided by ICICI direct, a well known trading website in Indian stock market. The comparison shows that the model generated by SVM is efficient and the results obtained using this technique are quite impressive.

We deal with a generalized proximal point algorithm for a sequence of m-accretive operators in Banach spaces. We investigate the condition of coefficients more deeply, and obtain weak convergence of an iterative scheme with a weaker coefficient condition.

Modeling using a complementarity framework arises naturally for games, economics, engineering and management decision making problems. This chapter presents a survey on complementarity models in non-cooperative games and certain classes of structured stochastic game problems. This framework is implemented as a linear complementarity, vertical block linear complementarity and extended linear complementarity problem.