We study the convergence of Markov decision processes, composed a large number objects, to optimization problems on ordinary differential equations. show that optimal reward such process, which satisfies Bellman equation, converges solution continuous Hamilton-Jacobi-Bellman (HJB) equation based mean field approximation process. give bounds difference rewards and an algorithm for deriving approximating process from HJB illustrate method three examples pertaining, respectively, investment...

In this paper we investigate the properties of multimodular functions. doing so give elementary proofs for already established by Hajek and generalize some his results. particular, extend relation between convexity multimodularity to convex subsets ℤ m . We also obtain general optimization results average costs related a sequence functions rather than single function. Under context, show that expected cost problem is optimized using regular sequences. finally illustrate usefulness theory in...

Recent mobile equipment (as well as the norm IEEE 802.21) offers possibility for users to switch from one technology another (vertical handover). This allows flexibility in resource assignments and, consequently, increases potential throughput allocated each user. In this paper, we design a fully distributed algorithm based on trial and error mechanisms that exploits benefits of vertical handover by finding fair efficient assignment schemes. On hand, mobiles gradually update fraction data...

In this paper, we consider a generic model of computational grids, seen as several clusters homogeneous processors. such systems, key issue when designing efficient job allocation policies is to balance the workload over different resources.

Starting from a heuristic learning scheme for strategic N-person games, we derive new class of continuous-time dynamics consisting replicator-like drift adjusted by penalty term that renders the boundary game’s strategy space repelling. These penalty-regulated are equivalent to players keeping an exponentially discounted aggregate their ongoing payoffs and then using smooth best response pick action based on these performance scores. Owing this inherent duality, proposed satisfy variant folk...

The objective pursued in this paper is two-fold. first part addresses the following combinatorial problem: it possible to construct an infinite sequence over n letters where each letter distributed as “evenly” and appears with a given rate? second of use construction framework optimal routing queuing networks. We show under rather general assumptions that deterministic stochastic event graphs such sequence.

In this paper, we consider a generic model of computational grids, seen as several clusters homogeneous processors. such systems, key issue when designing efficient job allocation policies is to balance the workload over different resources. We present Markovian for performance evaluation policy, namely work stealing (idle processors steal from others) in large-scale heterogeneous systems. Using mean field theory, show that size system grows, it converges deterministic ordinary differential...

To efficiently manage serverless computing platforms, a key aspect is the auto-scaling of services, i.e., set computational resources allocated to service adapts over time as function traffic demand. The objective find compromise between user-perceived performance and energy consumption. In this paper, we consider \emph{scale-per-request} pattern investigate how many instances (or servers) should be spawned each an \emph{unfortunate} job arrives, that finds all servers busy upon its arrival....

In average reward Markov decision processes, state-of-the-art algorithms for regret minimization follow a well-established framework: They are model-based, optimistic and episodic. First, they maintain confidence region from which policies computed using well-known subroutine called Extended Value Iteration (EVI). Second, these used over time windows episodes, each ended by the Doubling Trick (DT) rule or variant thereof. this work, without modifying EVI, we show that there is significant...

We analyze a mean field game model of SIR dynamics (Susceptible, Infected, and Recovered) where players choose when to vaccinate. show that this admits unique equilibrium (MFE) consists in vaccinating at maximal rate until given time then not vaccinating. The vaccination strategy minimizes the total cost has same structure as MFE. prove period MFE is always smaller than one minimizing cost. This implies that, encourage optimal behavior, should be subsidized. Finally, we provide numerical...

This article presents a theoretical modeling of small but basic scenario that shows great inequity in medium access between nodes using the IEEE 802.11 DCF mode. In this configuration, two terminals evolve independently and are almost never synchronized, which results serious performance issue for third emitter between. The compared to simulation discussion on different loss causes follows.

We consider mean field games with discrete state spaces (called in the following) and we analyze these continuous time, over finite as well infinite time horizons. prove existence of a equilibrium assuming continuity cost drift. These conditions are more general than existing papers studying space games. Besides, also study convergence equilibria N -player to our four settings. On one hand, define class strategies which any sequence converges weakly when number players goes infinity. other...

The Controller Area Network (CAN) protocol possesses fault confinement mechanisms aimed at differentiating between short disturbances caused by electromagnetic interference (EMI) and permanent failures due to hardware dysfunctioning. In this paper, we derive a Markovian analysis of these which enables one assess the risk reaching two degraded modes-busoff error-passive-defined CAN. We identify several problems with existing mechanisms, major being that busoff state is reached too easily....

short-paper Mean field limit of non-smooth systems and differential inclusions Share on Authors: Nicolas Gast Grenoble University LIG, Montbonnot, France FranceView Profile , Bruno Gaujal INRIA Authors Info & Claims ACM SIGMETRICS Performance Evaluation ReviewVolume 38Issue 2September 2010 pp 30–32https://doi.org/10.1145/1870178.1870189Online:15 October 2010Publication History 20citation114DownloadsMetricsTotal Citations20Total Downloads114Last 12 Months4Last 6 weeks0 Get Citation AlertsNew...

In this paper, we give evolution equations for free-choice Petri nets which generalize the [max, +]-algebraic setting already known event graphs. These can be seen as a coupling of two linear systems, (min, +)-linear system and quasi-(+, x)-linear one. This leads to new methods algorithms to: 1) in untimed case, check liveness several other basic logical properties; 2) timed establish various conservation monotonicity 3) stochastic stability, i.e., fact that marking remains bounded...

Perfect simulation, or coupling from the past, is an efficient technique for sampling steady state of monotone discrete time Markov chains. Indeed, one only needs to consider two trajectories corresponding minimal and maximal in system. We show here that even non-monotone system