Search

Environmental scientists frequently rely on time series of explanatory variables to explain their impact on an important response variable. However, sometimes, researchers are less interested in raw observations of an explanatory variable than in derived indices induced by episodes embedded in its time series. Often these episodes are intermittent, occur within a specific limited memory, persist for varying durations, at varying levels of intensity, and overlap important periods with respect to the response variable. We develop a generic, parametrised, family of weighted indices extracted from an environmental signal called IMPIT indices. To facilitate their construction and calibration, we developed a user friendly app in Shiny R referred to as IMPIT-a. We construct examples of IMPIT indices extracted from the Southern Oscillation Index and sea surface temperature signals. We illustrate their applications to two fished species in Queensland waters (i.e., snapper and saucer scallop) and wheat yield in New South Wales., Comment: 27 pages

Allometric settings of population dynamics models are appealing due to their parsimonious nature and broad utility when studying system level effects. Here, we parameterise the size-scaled Rosenzweig-MacArthur differential equations to eliminate prey-mass dependency, facilitating an in depth analytic study of the equations which incorporates scaling parameters’ contributions to coexistence. We define the functional response term to match empirical findings, and examine situations where metabolic theory derivations and observation diverge. The dynamical properties of the Rosenzweig-MacArthur system, encompassing the distribution of size-abundance equilibria, the scaling of period and amplitude of population cycling, and relationships between predator and prey abundances, are consistent with empirical observation. Our parameterisation is an accurate minimal model across 15+ orders of mass magnitude.

Allometric settings of population dynamics models are appealing due to their parsimonious nature and broad utility when studying system level effects. Here, we parameterise the size-scaled Rosenzweig-Macarthur ODEs to eliminate prey-mass dependency. We define the functional response term to match experiments, and examine situations where metabolic theory derivations and observation diverge. We produce dynamics consistent with observation. Our parameterisation of the Rosenzweig-Macarthur system is an accurate minimal model across 15+ orders of mass magnitude.

Cooperation is a ubiquitous and beneficial behavioural trait despite being prone to exploitation by free-riders. Hence, cooperative populations are prone to invasions by selfish individuals. However, a population consisting of only free-riders typically does not survive. Thus, cooperators and free-riders often coexist in some proportion. An evolutionary version of a Snowdrift Game proved its efficiency in analysing this phenomenon. However, what if the system has already reached its stable state but was perturbed due to a change in environmental conditions? Then, individuals may have to re-learn their effective strategies. To address this, we consider behavioural mistakes in strategic choice execution, which we refer to as incompetence. Parametrising the propensity to make such mistakes allows for a mathematical description of learning. We compare strategies based on their relative strategic advantage relying on both fitness and learning factors. When strategies are learned at distinct rates, allowing learning according to a prescribed order is optimal. Interestingly, the strategy with the lowest strategic advantage should be learnt first if we are to optimise fitness over the learning path. Then, the differences between strategies are balanced out in order to minimise the effect of behavioural uncertainty.

Environmental conditions shape entire communities by driving microbial interactions. These interactions then find their reflection in the evolutionary outcome of microbial competition. In static, homogeneous environments a robust, or evolutionary stable, outcome in microbial communities is reachable, if it exists. However, introducing heterogeneity and time-dependence in microbial ecology leads to stochastic evolutionary outcomes determined by specific environmental changes. We utilise evolutionary game theory to provide insight into phenotypic competition in dynamic environments. We capture these effects in a perturbed evolutionary game describing microbial interactions at a phenotypic level. We show that under regular periodic environmental fluctuations a stable state that preserves dominant phenotypes is reached. However, rapid environmental shifts, especially in a cyclic interactions, can lead to critical shifts in the evolutionary balance among phenotypes. Our analysis suggests that an understanding of the robustness of the systems current state is necessary to understand when system will shift to the new equilibrium. This can be done by understanding the systems overall margin of safety, that is, what level of perturbations it can take before its equilibrium changes. In particular, the extent to which an environmental shift affects the system’s behaviour.

We present a steady-state threshold risk analysis framework for exploited populations following the Beverton-Holt recurrence. The Beverton-Holt model is widely applied in the assessment of species biomass and fitted to experimental data to obtain a suitable range of parameter values. To account for the uncertainty in these parameter values, such as the growth rate, we analyze the probability of the steady-state harvested population falling below a critical threshold. More precisely, the Beverton-Holt equation with constant multiplicative survival, constant carrying capacity, and constant growth rate is considered. Under the assumption of a stochastic distributed proliferation rate, we analyze the risk of the steady-state population falling below a specified threshold, under constant harvest. We demonstrate a characteristic sensitivity property of that risk, that we refer to as "instability wedge," in the parameter space. We continue the study by assuming a 2-periodic carrying capacity, representing seasonal changes in the population's environment. Again, we demonstrate the risk sensitivity phenomenon. Although the growth rate was chosen to have a uniform distribution in presented examples, the framework extends to other probability distributions.

In this study, we define a hospital congestion episode as a situation where the number of new patients needing admission is greater than the number of available beds in the hospital, and investigate the likelihood that the current day’s midnight occupancy will exceed any specified threshold level. We demonstrate that this measure of risk exhibits a characteristic sensitivity phenomenon that we have named as hospital’s instability wedge. In particular, it is seen that frequently even small changes in the numbers of patients admitted or discharged can dramatically change the risk of exceeding the threshold, thereby changing the risk of subsequent congestion episodes. While this finding captures a salient difficulty of operating a modern public hospital, it also opens up an opportunity for monitoring and alleviating the above defined risk with only small changes in admission, discharge, and cancellation rates. A case study with recent patient journey data from Flinders Medical Centre in South Australia is presented. Refereed/Peer-reviewed

International audience; We consider a finite state, finite action, zero-sum stochastic games with data defining the game lying in the ordered field of real algebraic numbers. In both the discounted and the limiting average versions of these games, we prove that the value vector also lies in the same field of real algebraicnumbers. Our method supplies finite construction of univariate polynomials whose roots contain these value vectors. In the case where the data of the game are rational, the method also provides a way of checking whether the entries of the value vectors are also rational.

An instance of Hamiltonian cycle problem can be solved by converting it to an instance of Travelling salesman problem, assigning any choice of weights to edges of the underlying graph. In this note we demonstrate that, for difficult instances, choosing the edge weights to be the resistance distance between its two incident vertices is often a good choice. We also demonstrate that arguably stronger performance arises from using the inverse of the resistance distance. Examples are provided demonstrating benefits gained from these choices.

We address the question of whether it may be worthwhile to convert certain, now classical, NP-complete problems to one of a smaller number of kernel NP-complete problems. In particular, we show that Karp's classical set of 21 NP-complete problems contains a kernel subset of six problems with the property that each problem in the larger set can be converted to one of these six problems with only linear growth in problem size. This finding has potential applications in optimisation theory because the kernel subset includes 0-1 integer programming, job sequencing and undirected Hamiltonian cycle problems.

We present an algorithm to find the determinant and its first and second derivatives of a rank-one corrected generator matrix of a doubly stochastic Markov chain. The motivation arises from the fact that the global minimiser of this determinant solves the Hamiltonian cycle problem. It is essential for algorithms that find global minimisers to evaluate both first and second derivatives at every iteration. Potentially the computation of these derivatives could require an overwhelming amount of work since for the Hessian $N^2$ cofactors are required. We show how the doubly stochastic structure and the properties of the objective may be exploited to calculate all cofactors from a single LU decomposition.

We consider the long run average or ‘ergodic’ control of a discrete time Markov process with a probabilistic constraint in terms of a bound on the exit rate from a bounded subset of the state space. This is a natural counterpart of the more common probabilistic constraints in the finite horizon control problems. Using a recent characterization by Anantharam and the first author of risk-sensitive reward as the value of an average cost ergodic control problem, this problem is mapped to a constrained ergodic control problem that seeks to maximize an ergodic reward subject to a constraint on another ergodic reward. However, unlike the classical constrained ergodic reward/cost problems, this problem has some non-classical features due to a non-standard coupling between between the primary ergodic reward and the one that gets constrained. This renders the problem inaccessible to standard solution methodologies. A brief discussion of possible ways out is included.

We analyse a polyhedron which contains the convex hull of all Hamiltonian cycles of a given undirected connected cubic graph. Our constructed polyhedron is defined by polynomially-many linear constraints in polynomially-many continuous (relaxed) variables. Clearly, the emptiness of the constructed polyhedron implies that the graph is non-Hamiltonian. However, whenever a constructed polyhedron is non-empty, the result is inconclusive. Hence, the following natural question arises: if we assume that a non-empty polyhedron implies Hamiltonicity, how frequently is this diagnosis incorrect? We prove that, in the case of bridge graphs, the constructed polyhedron is always empty. We also demonstrate that some non-bridge non-Hamiltonian cubic graphs induce empty polyhedra as well. We compare our approach to the famous Dantzig-Fulkerson-Johnson relaxation of a TSP, and give empirical evidence which suggests that the latter is infeasible if and only if our constructed polyhedron is also empty. By considering special edge cut sets which are present in most cubic graphs, we describe a heuristic approach, built on our constructed polyhedron, for which incorrect diagnoses of non-Hamiltonian graphs as Hamiltonian appear to be very rare. In particular, for cubic graphs containing up to 18 vertices, only four out of 45,982 undirected connected cubic graphs were so misdiagnosed. By constrast, we demonstrate that an equivalent heuristic, when built on the Dantzig-Fulkerson-Johnson relaxation of a TSP, is mostly unsuccessful in identifying additional non-Hamiltonian graphs. These empirical results suggest that polynomial algorithms based on our constructed polyhedron may be able to correctly identify Hamiltonicity of a cubic graph in all but rare cases. HighlightsWe introduce new polyhedra that generally detect non-Hamiltonicity in cubic graphs.We prove that our approach is always successful for cubic bridge graphs.We propose a new heuristic based on special graph structures called crackers.Empirically we show that this heuristic is successful for nearly all cubic graphs.

We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian cycle problem (HCP) in an undirected graph of order \(n\). Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph’s edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly \(n\) snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic uses transformations inspired by \(k\)-opt algorithms such as the, now classical, Lin–Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in \(n^3\) major iterations.

A game of rock-paper-scissors is an interesting example of an interaction where none of the pure strategies strictly dominates all others, leading to a cyclic pattern. In this work, we consider an unstable version of rock-paper-scissors dynamics and allow individuals to make behavioural mistakes during the strategy execution. We show that such an assumption can break a cyclic relationship leading to a stable equilibrium emerging with only one strategy surviving. We consider two cases: completely random mistakes when individuals have no bias towards any strategy and a general form of mistakes. Then, we determine conditions for a strategy to dominate all other strategies. However, given that individuals who adopt a dominating strategy are still prone to behavioural mistakes in the observed behaviour, we may still observe extinct strategies. That is, behavioural mistakes in strategy execution stabilise evolutionary dynamics leading to an evolutionary stable and, potentially, mixed co-existence equilibrium., Author summary A game of rock-paper-scissors is more than just a children’s game. This type of interactions is often used to describe competition among animals or humans. A special feature of such an interaction is that none of the pure strategies dominates, resulting in a cyclic pattern. However, in wild communities such interactions are rarely observed by biologists. Our results suggest that this lack of cyclicity may stem from imperfectness of interacting individuals. In other words, we show analytically that heterogeneity in behavioural patterns may break a cyclic relationship and lead to a stable equilibrium in pure or mixed strategies.

In this paper we outline the design, development and application of a hospital patient flow management support tool – Hospital Event Simulation Model: Arrivals to Discharge (HESMAD). The model captures the patterns of patient flows within Flinders Medical Centre, a teaching hospital located in South Australia, through extensive exploitation of an existing hospital patient journey database (PJD). HESMAD employs mathematical and statistical modelling techniques, as well as the concept of modular design, to construct functions and processes that are embedded in a discrete event simulation system. The current structure of HESMAD reflects many iterations of refinements based on feedback from relevant industry experts. It places great emphasis on providing an engaging visualisation of the dynamics of events, and a convenient interface for domain experts: doctors, hospital managers and other health care professionals. An illustrative example of HESMAD’s wider applicability is presented.

We study a certain polytope arising from embedding the Hamiltonian cycle problem in a discounted Markov decision process. The Hamiltonian cycle problem can be reduced to finding particular extreme points of a certain polytope associated with the input graph. This polytope is a subset of the space of discounted occupational measures. We characterize the feasible bases of the polytope for a general input graph $G$, and determine the expected numbers of different types of feasible bases when the underlying graph is random. We utilize these results to demonstrate that augmenting certain additional constraints to reduce the polyhedral domain can eliminate a large number of feasible bases that do not correspond to Hamiltonian cycles. Finally, we develop a random walk algorithm on the feasible bases of the reduced polytope and present some numerical results. We conclude with a conjecture on the feasible bases of the reduced polytope., revised based on referees comments

We consider a simple model where an underlying environment alternates between a “good” and a “bad” state and is only observable when tapped. Considering this as a fishing resource management problem, optimizing fishing actions in the case of a small scale fisher (who does not affect the environment) requires balancing the rewards obtained and information gained from fishing. We consider policies of the form “back off if fish are not biting” and characterize the optimal “back off time” through a probabilistic regenerative analysis.

We study the embedding of the Hamiltonian Cycle problem, on a symmetric graph, in a discounted Markov decision process. The embedding allows us to explore the space of occupational measures corresponding to that decision process. In this paper we consider a convex combination of a Hamiltonian cycle and its reverse. We show that this convex combination traces out an interesting “H-curve” in the space of occupational measures. Since such an H-curve always exists in Hamiltonian graphs, its properties may help in differentiating between graphs possessing Hamiltonian cycles and those that do not. Our analysis relies on the fact that the resolvent-like matrix induced by our convex combination can be expanded in terms of finitely many powers of probability transition matrices corresponding to that Hamiltonian cycle. We derive closed form formulae for the coefficients of these powers which are reduced to expressions involving the classical Chebyshev polynomials of the second kind. For regular graphs, we also define a function that is the inner product of points on the H-curve with a suitably defined center of the space of occupational measures and show that, despite the nonlinearity of the inner-product, this function can be expressed as a linear function of auxiliary variables associated with our embedding. These results can be seen as stepping stones towards developing constraints on the space of occupational measures that may help characterize non-Hamiltonian graphs.

The adaptation process of a species to a new environment is a significant area of study in biology. As part of natural selection, adaptation is a mutation process which improves survival skills and reproductive functions of species. Here, we investigate this process by combining the idea of incompetence with evolutionary game theory. In the sense of evolution, incompetence and training can be interpreted as a special learning process. With focus on the social side of the problem, we analyze the influence of incompetence on behavior of species. We introduce an incompetence parameter into a learning function in a single-population game and analyze its effect on the outcome of the replicator dynamics. Incompetence can change the outcome of the game and its dynamics, indicating its significance within what are inherently imperfect natural systems., 17 pages, 3 figures

International audience; In this paper, we present some algebraic properties of a particular class of probability transition matrices, namely, Hamiltonian transition matrices. Each matrix P in this class corresponds to a Hamiltonian cycle in a given graph G on n nodes and to an irreducible, periodic, Markov chain. We show that a number of important matrices traditionally associated with Markov chains, namely, the stationary, fundamental, deviation and the hitting time matrix all have elegant expansions in the first n−1 powers of P , whose coefficients can be explicitly derived. We also consider the resolvent-like matrices associated with any given Hamiltonian cycle and its reverse cycle and prove an identity about the product of these matrices.

International audience; Linear programming formulations for the discounted and long-run average MDPs have evolved along separate trajectories. In 2006, E. Altman conjectured that the two linear programming formulations of discounted and long-run average MDPs are, most likely, a manifestation of general properties of singularly perturbed linear programs. In this note we demonstrate that this is, indeed, the case.

Given the results of Chap. 1 that every descendant may be constructed from a complete family of ancestor genes, we now investigate how the properties of the descendant correspond to the properties of those genes. In particular we consider the properties of Hamiltonicity, bipartiteness and planarity. In all three cases we prove that a descendant may only possess the property if all of its ancestor genes do. In the case of bipartiteness and planarity we also establish sufficient conditions. These results allow us to analyse the properties of a graph by considering its ancestor genes, or alternatively, to construct a graph with desired properties by choosing smaller genes with those properties. We follow each section with a discussion of famous results and conjectures relating to the graph properties, and how the results of this chapter relate to them.

In Chap. 1 we stated the result that every graph has a unique complete family of ancestor genes. The result is proved in detail in this chapter. The proof is lengthy and is therefore broken up into several intermediate steps. We first show that it is sufficient to prove the result for graphs with no parthenogenic objects. We then consider all possible methods of decomposing a graph into three components via the inverse operations and show that the components so obtained are always the same regardless of the inverse operations used. Next we prove that any complete family of ancestor genes for a graph has cardinality which is a fixed constant for that graph. We then proceed to prove that for any descendant without parthenogenic objects, it is possible to isolate at least two genes with single inverse breeding operations. Finally, we use each of these results to prove the uniqueness theorem.

The concept of games with incompetence has been introduced to better represent games where players may not be capable of executing strategies that they select. In particular this paper introduces incompetence into bimatrix games and investigates the properties of such games. The results obtained describe both the general dependence of "extreme Nash equilibrium payoffs" on incompetence and special behaviour arising in particular cases. The dependence of the payoffs can be complex and include non-linearities and transition points. Transition points occur when kernels change and may result in the number of "extreme Nash equilibria" changing. Understanding these changes allows the determination of the benefits of regimes that seek to decrease a player's incompetence. While the games we consider are normally static, in our context there is a hidden dynamics resulting from the fact that players will strive to improve their equilibrium payoffs by changing their incompetence levels. This might require training, in the case of games like tennis, or it might require the purchase of new equipment costing billions of dollars, in the case of military applications.

In this note the Hamiltonian cycle problem is mapped into an infinite horizon discounted cost constrained Markov decision problem. The occupation measure based linear polytope associated with this control problem defines a convex set which either strictly contains or is equal to another convex set, depending on whether the underlying graph has a Hamiltonian cycle or not. This allows us to distinguish Hamiltonian graphs from non-Hamiltonian graphs by comparing volumes of two convex sets.

In this note we study multivariate perturbations of algebraic equations. In general, it is not possible to represent the perturbed solution as a Puiseux-type power series in a connected neighborhood. For the case of two perturbation parameters we provide a sufficient condition that guarantees such a representation. Then, we extend this result to the case of more than two perturbation parameters. We motivate our study by the perturbation analysis of a weighted random walk on the Web Graph. In an instance of the latter the stationary distribution of the weighted random walk, the so-called Weighted PageRank, may depend on two (or more) perturbation parameters in a manner that illustrates our theoretical development.

Refereed/Peer-reviewed

In this paper, we propose a new hybrid algorithm for the Hamiltonian cycle problem by synthesizing the Cross Entropy method and Markov decision processes. In particular, this new algorithm assigns a random length to each arc and alters the Hamiltonian cycle problem to the travelling salesman problem. Thus, there is now a probability corresponding to each arc that denotes the probability of the event 'this arc is located on the shortest tour.' Those probabilities are then updated as in cross entropy method and used to set a suitable linear programming model. If the solution of the latter yields any tour, the graph is Hamiltonian. Numerical results reveal that when the size of graph is small, say less than 50 nodes, there is a high chance the algorithm will be terminated in its cross entropy component by simply generating a Hamiltonian cycle, randomly. However, for larger graphs, in most of the tests the algorithm terminated in its optimization component (by solving the proposed linear program). Refereed/Peer-reviewed

We exhibit a characteristic structure of the class of all regular graphs of degree d that stems from the spectra of their adjacency matrices. The structure has a fractal threadlike appearance. Points with coordinates given by the mean and variance of the exponentials of graph eigenvalues cluster around a line segment that we call a filar. Zooming-in reveals that this cluster splits into smaller segments (filars) labeled by the number of triangles in graphs. Further zooming-in shows that the smaller filars split into subfilars labelled by the number of quadrangles in graphs, etc. We call this fractal structure, discovered in a numerical experiment, a multifilar structure. We also provide a mathematical explanation of this phenomenon based on the Ihara-Selberg trace formula, and compute the coordinates and slopes of all filars in terms of Bessel functions of the first kind., Comment: 10 pages, 5 figures

We postulate that reasonable notions of sustainability must include a time-scale synchronization of both the processes of human development and those of the natural environment. We perform our analysis within a simple system of five differential equations where non-renewable and renewable resources are coupled with production capacities, abatement and human capital as functions of time. A 'sustainability screw' phenomenon is demonstrated describing a spiral like trajectory of three key variables-the non-renewable resources, the renewable resources and the production capital. This spiral may tend to an undesirable steady state, however, by adjusting a ratio of intensity parameters, time scales of production and natural recovery processes can be altered to produce more sustainable trajectories. Refereed/Peer-reviewed

We introduce the time-consistency concept that is inspired by the so-called “principle of optimality” of dynamic programming and demonstrate – via an example – that the conditional value-at-risk (CVaR) need not be time-consistent in a multi-stage case. Then, we give the formulation of the target-percentile risk measure which is time-consistent and hence more suitable in the multi-stage investment context. Finally, we also generalize the value-at-risk and CVaR to multi-stage risk measures based on the theory and structure of the target-percentile risk measure.

Environmental assessment is key to any environmental policy and is now among the highest priorities in socioeconomic development around the world. The present paper focuses on the application of multiple criteria decision making (MCDM) techniques to assessing the effectiveness of U S environmental policies for the reduction of toxic releases. The entropy concept is employed to assign suitable weights to the environmental indicators to reflect their relative importance in the assessment process.

We study singularly perturbed linear programs. These are linear programs whose constraints and objective coefficients depend on a small perturbation parameter, and furthermore the constraints become linearly dependent when the perturbation parameter goes to zero. Problems like that were studied by Jeroslow in 1970s. He proposed simplex-like method, which works over the field of rational functions. Here we develop an alternative asymptotic simplex method based on Laurent series expansions. This approach appears to be more computationally efficient. In addition, we point out several possible generalizations of our method and provide simple updating formulae for the perturbed solution.

Let P 0 be a stochastic matrix with no eigenvalue other than 1 on the unit circle and let P ( e )= P 0 + A ( e ) be an analytic perturbation which is still stochastic for small enough positive e . We determine the limit lim e↓0 1 N(e) ∑ l=1 N(e) P l (e), when N ( e )↑∞ at various rates.

We consider a direct conversion of the, classical, set splitting problem to the directed Hamiltonian cycle problem. A constructive procedure for such a conversion is given, and it is shown that the input size of the converted instance is a linear function of the input size of the original instance. A proof that the two instances are equivalent is given, and a procedure for identifying a solution to the original instance from a solution of the converted instance is also provided. We conclude with two examples of set splitting problem instances, one with solutions and one without, and display the corresponding instances of the directed Hamiltonian cycle problem, along with a solution in the first example.

A two-factor production model where one factor is characterized by a continuous state variable and corresponds to the fast mode via a controlled diffusion process, whereas the second factor is characterized by a discrete variable and corresponds to the slow mode via a controlled jump process.

The explosive growth in air traffic as well as the widespread adoption of Operations Research techniques in airline scheduling has given rise to tight flight schedules at major airports. An undesirable consequence of this is that a minor incident such as a delay in the arrival of a small number of flights can result in a chain reaction of events involving several flights and airports, causing disruption throughout the system. This paper reviews recent literature in the area of recovery from schedule disruptions. First we review how disturbances at a given airport could be handled, including the effects of runways and fixes. Then we study the papers on recovery from airline schedule perturbations, which involve adjustments in flight schedules, aircraft, and crew. The mathematical programming techniques used in ground holding are covered in some detail. We conclude the review with suggestions on how singular perturbation theory could play a role in analyzing disruptions to such highly sensitive schedules as those in the civil aviation industry.