Multi‐level hierarchic Markov processes as a framework for herd management support

A general problem in relation to application of Markov decision processes to real world problems is the curse of dimensionality, since the size of the state space grows to prohibitive levels when information on all relevant traits of the system being modeled are included. In herd management, we face a hierarchy of decisions made at different levels with different time horizons, and the decisions made at different levels are mutually dependent. Furthermore, decisions have to be made without certainty about the future state of the system. These aspects contribute even further to the dimensionality problem. A new notion of a multilevel hierarchic Markov process specially designed to solve dynamic decision problems involving decisions with varying time horizon has been presented. The method contributes significantly to circumvent the curse of dimensionality, and it provides a framework for general herd management support instead of very specialized models only concerned with a single decision as, for instance, replacement. The applicational perspectives of the technique are illustrated by potential examples relating to the management of a sow herd and a dairy herd.     

Hierarchical optimization: An introduction

Decision problems involving multiple agents invariably lead to conflict and gaming. In recent years, multi-agent systems have been analyzed using approaches that explicitly assign to each agent a unique objective function and set of decision variables; the system is defined by a set of common constraints that affect all agents. The decisions made by each agent in these approaches affect the decisions made by the others and their objectives. When strategies are selected simultaneously, in a noncooperative manner, solutions are defined as equilibrium points [13,51] so that at optimality no player can do better by unilaterally altering his choice. There are other types of noncooperative decision problems, though, where there is a hierarchical ordering of the agents, and one set has the authority to strongly influence the preferences of the other agents. Such situations are analyzed using a concept known as a Stackelberg strategy [13, 14,46]. The hierarchical optimization problem [11, 16, 23] conceptually extends the open-loop Stackelberg model toK players. In this paper, we provide a brief introduction and survey of recent work in the literature, and summarize the contributions of this volume. It should be noted that the survey is not meant to be exhaustive, but rather to place recent papers in context.     

Top-Down Fuzzy Decision Making with Partial Preference Information

This paper proposes a multi-stage decision procedure to cope with a hierarchical multiple objective decision environment in which the upper-level DM only provides partial preference information and the lower-level DM is fuzzy about the tradeoff questions such that to achieve substantially more than or equal to some values is delivered to maximize the objectives. Therefore, the procedure consists of two levels, a upper-level and a lower-level. The main idea is that after the upper-level provides partial preference information to the lower-level as a guideline of decision, the lower-level DM determines a satisfactory solution from the reduced non-dominated set in the framework of multi-objective fuzzy programs.     

A multilevel programming approach to decentralized (or hierarchical) resource allocation systems

In many decision processes there is a hierarchy of decision-makers and decisions are taken at different levels in this hierarchy. In business (and many other practical activities) decision making has changed over the last decades. From a single person (the boss!) and a single criterion (e.g. profit), decision environments have developed increasingly to become multi-person and multi-criteria and even multi-level (or hierarchical) situations. In organization with hierarchical decision systems, the sequential and preemptive nature of the decision process makes the problem of selecting an optimum strategy and action very different from the usual operations research methods. Therefore, a multilevel programming approach is considered in modeling such problems. In particular a three-level mathematical programming model has been proposed for an optimal resource allocation problem in Ethiopian universities. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A new decision support framework for managing foot-and-mouth disease epidemics

Animal disease epidemics such as the foot-and-mouth disease (FMD) pose recurrent threat to countries with intensive livestock production. Efficient FMD control is crucial in limiting the damage of FMD epidemics and securing food production. Decision making in FMD control involves a hierarchy of decisions made at strategic, tactical, and operational levels. These decisions are interdependent and have to be made under uncertainty about future development of the epidemic. Addressing this decision problem, this paper presents a new decision-support framework based on multi-level hierarchic Markov processes (MLHMP). The MLHMP model simultaneously optimizes decisions at strategic, tactical, and operational levels, using Bayesian forecasting methods to model uncertainty and learning about the epidemic. As illustrated by the example, the framework is especially useful in contingency planning for future FMD epidemics.     

An optimal algorithm for search of extrema of a bimodal function

This paper describes and analyzes an algorithm which computes an interval of length t in which a minimizer (or a maximizer) of a periodical bimodal function h is located using a minimal number of evaluations of the function h. A dynamic programming approach is used in order to demonstrate the optimality of the algorithm.     

Selection of a correlated equilibrium in Markov stopping games

This paper deals with an extension of the concept of correlated strategies to Markov stopping games. The Nash equilibrium approach to solving nonzero-sum stopping games may give multiple solutions. An arbitrator can suggest to each player the decision to be applied at each stage based on a joint distribution over the players’ decisions according to some optimality criterion. This is a form of equilibrium selection. Examples of correlated equilibria in nonzero-sum games related to the best choice problem are given. Several concepts of criteria for selecting a correlated equilibrium are used.     

Optimizing pig marketing decisions under price fluctuations

In the manufacturing of fattening pigs, pig marketing refers to a sequence of culling decisions until the production unit is empty. The profit of a production unit is highly dependent on the price of pork, the cost of feeding and the cost of buying piglets. Price fluctuations in the market consequently influence the profit, and the optimal marketing decisions may change under different price conditions. Most studies have considered pig marketing under constant price conditions. However, because price fluctuations have an influence on profit and optimal marketing decisions it is relevant to consider pig marketing under price fluctuations. In this paper we formulate a hierarchical Markov decision process with two levels which model sequential marketing decisions under price fluctuations in a pig pen. The state of the system is based on information about pork, piglet and feed prices. Moreover, the information is updated using a Bayesian approach and embedded into the hierarchical Markov decision process. The optimal policy is analyzed under different patterns of price fluctuations. We also assess the value of including price information into the model.

     

Competition-reachability of a graph

The reachability r(D) of a directed graph D is the number of ordered pairs of distinct vertices (x,y) with a directed path from x to y. Consider a game associated with a graph G=(V,E) involving two players (maximizer and minimizer) who alternately select edges and orient them. The maximizer attempts to maximize the reachability, while the minimizer attempts to minimize the reachability, of the resulting digraph. If both players play optimally, then the reachability is fixed. Parameters that assign a value to each graph in this manner are called competitive parameters. We determine the competitive-reachability for special classes of graphs and discuss which graphs achieve the minimum and maximum possible values of competitive-reachability.     

Multi-Level Strategic Evaluation of Hospital Plans and Decisions

Strategic decision making in hospitals involves the assessment of linkages between decisions that are typically made in a hierarchical fashion. In hospitals, as in most large organizations, overall system performance is a function of how well the critical decisions are integrated. This paper focuses on the multi-level nature of the decisions and policies that typically need to be evaluated in hospital planning, highlighting that both optimization and simulation approaches may be required. An application involving a large general purpose urban hospital is used to illustrate the interdependency between the levels in the planning hierarchy. An optimization model is formulated to deal with facility layout and capacity allocation while a simulation model is proposed to capture the complexities of hospital operations. The linkages and information feedback between the models are shown to be critical in the design of a system that performs well and facilitates strategic hospital planning.     

Nonlinear Markov Operators,Discrete Heat Flow,and Harmonic Maps Between Singular Spaces

We develop a theory of harmonic maps f:MN between singular spaces M and N. The target will be a complete metric space (N,d) of nonpositive curvature in the sense of A. D. Alexandrov. The domain will be a measurable space (M,) with a given Markov kernel p(x,dy) on it. Given a measurable map f:MN, we define a new map Pf:MN in the following way: for each xM, the point Pf(x)N is the barycenter of the probability measure p(x,f ^–1(dy)) on N. The map f is called harmonic on DM if Pf=f on D. Our theory is a nonlinear generalization of the theory of Markov kernels and Markov chains on M. It allows to construct harmonic maps by an explicit nonlinear Markov chain algorithm (which under suitable conditions converges exponentially fast). Many smoothing and contraction properties of the linear Markov operator P _M,R carry over to the nonlinear Markov operator P=P _M,N . For instance, if the underlying Markov kernel has the strong Lipschitz Feller property then all harmonic maps will be Lipschitz continuous.     

Convex bodies with extremal volumes having prescribed brightness in finitely many directions

We consider the class of convex bodies in ⁿ with prescribed projection (n – 1)-volumes along finitely many fixed directions. We prove that in such a class there exists a unique body (up to translation) with maximumn-volume. The maximizer is a centrally symmetric polytope and the normal vectors to its facets depend only on the assigned directions.Conditions for the existence of bodies with minimumn-volume in the class defined above are given. Each minimizer is a polytope, and an upper bound for the number of its facets is established.Work partially supported by Istituto di Analisi Globale e Applicazioni, CNR, Firenze.     

Markov decision processes with multidimensional action spaces

We study controlled Markov processes where multiple decisions need to be made for each state. We present conditions on the cost structure and the state transition mechanism of the process under which optimal decisions are restricted to a subset of the decision space. As a result, the numerical computation of the optimal policy may be significantly expedited.     

The polynomial hierarchy and a simple model for competitive analysis

The multi-level linear programs of Candler, Norton and Townsley are a simple class of sequenced-move games, in which players are restricted in their moves only by common linear constraints, and each seeks to optimize a fixed linear criterion function in his/her own continuous variables and those of other players. All data of the game and earlier moves are known to a player when he/she is to move. The one-player case is just linear programming.We show that questions concerning only the value of these games exhibit complexity which goes up all levels of the polynomial hierarchy and appears to increase with the number of players.For three players, the games allow reduction of the ₂ and ₂ levels of the hierarchy. These levels essentially include computations done with branch-and-bound, in which one is given an oracle which can instantaneously solve NP-complete problems (e.g., integer linear programs). More generally, games with (p + 1) players allow reductions of _p and _p in the hierarchy.An easy corollary of these results is that value questions for two-player (bi-level) games of this type is NP-hard.The author's work has been supported by the Alexander von Humboldt Foundation and the Institut fur Okonometrie und Operations Research of the University of Bonn, Federal Republic of Germany; grant ECS8001763 of the National Science Foundation, USA; and a grant from the Georgia Tech Foundation.     

A genetic filtering problem ∗

Members of a population of fixed size N can be in any one of n states. In discrete time the individuals jump from one state to another, independently of each other, and with probabilities described by a homogeneous Markov chain. At each time a sample of size M is withdrawn, (with replacement). Based on these observations, and using the techniques of Hidden Markov Models, recursive estimates for the distribution of the population are obtained     

On level sets of marginal functions

The investigation of level sets of marginal functions is motivated by several aspects of standard and generalized semi-infinite programming. The feasible- set M of such a prob­lem is easily seen to be a level set of the marginal function corresponding to the lower level problem. In the present paper we study the local structure of M at feasible bound­ary points in the generic case. A codimension formula shows that there is a wide range of these generic situations, but that the number of active indices is always bounded by the state space dimension. We restrict our attention to two special subcases

In the first case, where the number of active indices is maximalM is shown to be locally diffeomorphic to the non-negative orthant. This situation is well-known from finite and also from standard semi-infinite programming. However, in the second case a generic situation arises which is typical for generalized semi-infinite programming. Here, the active index set is a singleton, and M can exhibit a re-entrant corner or even local non-closedness, depending on whether the Mangasarian-Fromovitz constraint qualifica­tion holds at the active index. If an objective function is minimized over M then in the setting of the second case a local minimizer cannot occur     

Unifying temporal and organizational scales in multiscale decision-making

In enterprise systems, making decisions is a complex task for agents at all levels of the organizational hierarchy. To calculate an optimal course of action, an agent has to include uncertainties and the anticipated decisions of other agents, recognizing that they also engage in a stochastic, game-theoretic reasoning process. Furthermore, higher-level agents seek to align the interests of their subordinates by providing incentives. Incentive-giving and receiving agents need to include the effect of the incentive on their payoffs in the optimal strategy calculations. In this paper, we present a multiscale decision-making model that accounts for uncertainties and organizational interdependencies over time. Multiscale decision-making combines stochastic games with hierarchical Markov decision processes to model and solve multi-organizational-scale and multi-time-scale problems. This is the first model that unifies the organizational and temporal scales and can solve a 3-agent, 3-period problem. Solutions can be derived as analytic equations with low computational effort. We apply the model to a service enterprise challenge that illustrates the applicability and relevance of the model. This paper makes an important contribution to the foundation of multiscale decision theory and represents a key step towards solving the general X-agent, T-period problem.     

On a duel with time lag and equal accuracy functions

This paper deals with a duel with time lag that has the following structure: Each of two players I and II has a gun with one bullet and he can fire his bullet at any time in [0, 1], aiming at this opponent. The gun of player I is silent and the gun of player II is noisy with time lagt (i.e., if player II fires at timex, then player I knows it at timex+t). They both have equal accuracy functions. Furthermore, if player I hits player II without being hit himself before, the payoff is +1; if player I is hit by player II without hitting player II before, the payoff is –1; if they hit each other at the same time or both survive, the payoff is 0.This paper gives the optimal strategy for each player, the game value, and some examples.     

Age Process, Workload Process, Sojourn Times, and Waiting Times in a Discrete Time SM[K]/PH[K]/1/FCFS Queue

In this paper, we study a discrete time queueing system with multiple types of customers and a first-come-first-served (FCFS) service discipline. Customers arrive according to a semi-Markov arrival process and the service times of individual customers have PH-distributions. A GI/M/1 type Markov chain for a generalized age process of batches of customers is introduced. The steady state distribution of the GI/M/1 type Markov chain is found explicitly and, consequently, the steady state distributions of the age of the batch in service, the total workload in the system, waiting times, and sojourn times of different batches and different types of customers are obtained. We show that the generalized age process and a generalized total workload process have the same steady state distribution. We prove that the waiting times and sojourn times have PH-distributions and find matrix representations of those PH-distributions. When the arrival process is a Markov arrival process with marked transitions, we construct a QBD process for the age process and the total workload process. The steady state distributions of the waiting times and the sojourn times, both at the batch level and the customer level, are obtained from the steady state distribution of the QBD process. A number of numerical examples are presented to gain insight into the waiting processes of different types of customers.AMS subject classification: 60K25, 60J10This revised version was published online in June 2005 with corrected coverdate     

A markov-modulated M/M/1 queue with group arrivals

We study anM/M/1 group arrival queue in which the arrival rate, service time distributions and the size of each group arrival depend on the state of an underlying finite-state Markov chain. Using Laplace transforms and matrix analysis, we derive the results for the queue length process, its limit distribution and the departure process. In some special cases, explicit results are obtained which are analogous to known classic results.