SØREN ASMUSSEN (Aarhus University)

Lévy Processes with Two-Sided Reflection

The talk is based on joint work with Lars Nørvang andersen, Peter Glynn and Mats Pihlsgåard.

BURAK BÜKE (University of Edinburgh)

Stabilizing Policies for Probabilistic Matching Systems

In this work, we introduce a novel queueing model where two types of users (customers and suppliers) arrive at a system and, instead of waiting to access a resource, the arriving users wait in the system to be  matched with a potential candidate from the other queue. This new model is useful for analyzing the behavior of web portals which match the people who provide a specific service (suppliers) with the people who demand the service (customers), such as employment portals, matrimonial and dating sites, rental portals, and multipurpose web portals (e.g. Craigslist.org and Gumtree.com). As an example, in an employment portal, the employees (suppliers) arrive at the portal at random times and upon arrival they scan the job postings available on the website. If they can find a potential match among these postings, they get hired and leave the system. If they cannot find a match, they post their resume on the website and wait until an arriving employer (customer) hires them. Employers also behave in a similar manner. 

We assume that users arrive at a probabilistic matching system according to independent Poisson processes. Each given customer can match with a specific supplier with probability $q$ independent of other customers and suppliers. Once a customer (supplier) arrives if there is at least one match for the supplier (customer), s/he chooses one arbitrarily and leaves the system immediately. If there are no matching suppliers (customers), s/he subscribes to the system and waits to be picked by an arriving supplier (customer). We prove that if a probabilistic matching system system is not controlled, it is unstable (non-ergodic). We suggest three admission control policies to stabilize probabilistic matching systems under different assumptions. The key factor differentiating this novel model from the literature is the matching probability $q$. Hence, we analyze the performances of the proposed policies, especially focusing on how the matching probability affects different measures. We also outline how the analysis of probabilistic matching system differs from the conventional queueing systems, and introduce some open problems related to these systems.

The talk is based on joint work with Hanyi Chen and Miklos Rasonyi.

ANA BUŠIĆ (INRIA/ENS)

Stability in dynamic bipartite matching models

Matching models arise in many applications, such as healthcare, transportation, and energy. We consider a bipartite matching queueing model, where customers and servers play symmetrical roles. Time is discrete and at each time step, one customer and one server arrive in the system. Also, at each time step, pairs of matched customer and server, if they exist, depart from the system. Authorized matchings between customer/server classes are given by a fixed bipartite graph. A matching policy is chosen, which decides how to match when there are several possibilities. Customers/servers that cannot be matched are stored in a buffer. The evolution of the model can be described by a discrete time Markov chain. We study its stability under various admissible matching policies including: ML (Match the Longest), MS (Match the Shortest), FIFO (match the oldest), priorities. There exist natural necessary conditions for stability (independent of the matching policy) defining the maximal possible stability region. For some bipartite graphs, we prove that the stability region is indeed maximal for any admissible matching policy. For the ML policy, we prove that the stability region is maximal for any bipartite graph. For the MS and priority policies, we exhibit a bipartite graph with a non-maximal stability region.

MOEZ DRAIEF (Imperial College London)

Distances in Weighted Random Graphs

In this talk, I will present recent results analysing the impact of edge weights on dis-

tances in sparse random graphs. We interpret these weights as delays, and take them

as i.i.d exponential random variables. We analyze the weighted flooding time defined as

the minimum time needed to reach all nodes from one uniformly chosen node, and the

weighted diameter corresponding to the largest distance between any pair of vertices.

Under some regularity conditions on the degree sequence of the random graph, we derive

exact asymtotic behaviours for these quantities as the size of the graph tends to infinity.

This is a joint work with H. Amini (EPFL) and M. Lelarge (ENS-INRIA)

Joint work with J. Abernethy (U. Mich.), K. Amin and M. Kearns (U. Penn.)

SERGEY FOSS (Heriot-Watt University)

On Erickson's Characterization Theorem for a Random Walk When the Mean Does Not Exist

A celebrated 40-year-old result by K.B.Erickson [1] provides necessary and sufficient conditions for the average S_n/n either to tend to plus or minus infinity or to oscillate. I will present another proof of it, which is structured, relatively short, and is based  on the Kingman's subadditive ergodic theorem.

[1] K.B. Erickson, The strong law of large numbers when the mean is undefined, Trans.Amer. Math. Soc., 185 (1973), 371-381.

[2] D.E. Denisov and S.G.Foss. On transience conditions for Markov chains and random walks. Siberian Math. J., 44 (2003), 53-68.

AYALVADI GANESH (University of Bristol)

Queues, Tolls and Welfare

We consider a number of parallel queues serving customers belonging to distinct classes. The classes differ in their aversion to delay. We consider the problem of assigning customers to queues so as to maximise a measure of social welfare. Restricting attention to Markovian routing policies, we establish certain structural properties of the optimal routing matrix.

Next, we assume that each queue charges an entry toll to customers, who then route themselves selfishly to minimise their total cost, composed of the toll and the expected delay. The customers have no information about queue occupancies, and so again to have use Markovian decision rules. Again, we characterise structural properties of the Wardrop equilibrium for this congestion game. Finally, we show how tolls can be set so as to ensure that the Wardrop equilibrium coincides with the social optimum, and relate these optimal tolls to Pigouvian taxes.

DAVID HODGE (University of Nottingham)

Restless Bandits: A Background and Applications in Dynamic Resource Allocation

I will give an quick overview of the history of restless bandit theory and talk some applications to queues, stock control and machine maintenance . I will discuss some problems where bandit "indices" can yield excellent scalable heuristics for high dimensional resource allocation problems. I will also discuss some work on asymptotic optimality with a view to highlighting the many areas where the result could be of use.

LUKAS SZPRUCH (University of Edinburgh)

Multilevel Monte Carlo Simulations

In this talk I introduce the concept of multilevel Monte Carlo (MLMC) estimator for multidimensional SDEs driven by Brownian motion. Giles has shown that if we combine a numerical approximation with strong order of convergence $O(\D t)$ with MLMC we can reduce the computational complexity to estimate expected values of functionals of SDE solutions with a root-mean-square error of $\eps$ from $O(\eps^{-3})$ to $O(\eps^{-2})$. However, in general, to obtain a rate of strong convergence higher than $O(\D t^{1/2})$ requires simulation, or approximation, of Lévy areas. Recently, Giles and Szpruch constructed antithetic multilevel estimator, that allows to avoid the simulation of Lévy areas and still achieves an $O(\D t^2)$ variance for smooth payoffs and almost an

$O(\D t^{3/2})$ variance for piecewise smooth payoffs, even though there is only

$O(\D t^{1/2})$ strong convergence. This results in an $O(\eps^{-2})$ complexity for       estimating the value of European and Asian put and call options.

GIDEON WEISS (University of Haifa)

FCFS Infinite Bipartite Matching and Applications

The following model was introduced to respond to a problem posed by Kaplan in the 80’s: There are two random infinite sequences of items, each con- sisting of several types, with a bipartite compatibility graph between types, and these are matched on a FCFS basis. After several attempts we now have some understanding of this model, with a beautiful reversibility result. Product form expressions then allow calculation of many performance measures, including the matching rates sought by Kaplan. The model is then applied to get approximations for some related highly intractable queueing models.

Joint work with Ivo Adan, Marko Boon, Ana Busic and Jean Mairesse.

ILZE ZIEDINS (University of Auckland)

Queueing Networks with Self-Optimising State-Dependent Routing

It is well-known that adding extra capacity to queues in networks where individuals choose their own route can sometimes severely degrade performance, rather than improving it.  We will discuss examples of queueing networks where this is the case under probabilistic routing, but where under state-dependent routing the worst case performance is no longer seen.  This raises the more general question of whether giving arrivals more information about the state of the network is helpful or harmful.  The models we will discuss have some relevance for traffic networks, where individuals choose their own route and/or mode of transport and, increasingly, have at least some information available about the instantaneous state of the network when making their decisions.