LIPIcs.AofA.2022.13.pdf
- Filesize: 0.75 MB
- 17 pages
Document
Mean Field Analysis of an Incentive Algorithm for a Closed Stochastic Network
Authors
-
Part of:
Volume:
33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-06-08
File
Document Identifiers
Acknowledgements
The authors would like to thank Communauto for funding and allowing to do this study. They also thank the Natural Science and Engineering Research Council of Canada (NSERC) for funding.
Cite AsGet BibTex
Bianca Marin Moreno, Christine Fricker, Hanene Mohamed, Amaury Philippe, and Martin Trépanier. Mean Field Analysis of an Incentive Algorithm for a Closed Stochastic Network. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.AofA.2022.13
https://doi.org/10.4230/LIPIcs.AofA.2022.13
Abstract
The paper deals with a load-balancing algorithm for a closed stochastic network with two zones with different demands. The algorithm is motivated by an incentive algorithm for redistribution of cars in a large-scale car-sharing system. The service area is divided into two zones. When cars stay too long in the low-demand zone, users are encouraged to pick them up and return them in the high-demand zone. The zones are divided in cells called stations. The cars are the network customers. The mean-field limit solution of an ODE gives the large scale distribution of the station state in both clusters for this incentive policy in a discrete Markovian framework. An equilibrium point of this ODE is characterized via the invariant measure of a random walk in the quarter-plane. The proportion of empty and saturated stations measures how the system is balanced. Numerical experiments illustrate the impact of the incentive policy. Our study shows that the incentive policy helps when the high-demand zone observes a lack of cars but a saturation must be prevented especially when the high-demand zone is small.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Queueing theory
- Mathematics of computing → Markov processes
- Mathematics of computing → Stochastic processes
Keywords
- Large scale analysis
- mean-field
- car-sharing
- incentive algorithm
- stochastic network
- cluster
- load balancing
- closed Jackson networks
- product-form distribution
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
A. Economou and D. Fakinos. Product form stationary distributions for queueing networks with blocking and rerouting. Queueing Systems Theory Appl., 30:251-260, 1998.
-
Stewart N. Ethier and Thomas G. Kurtz. Markov processes. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York, 1986. Characterization and convergence.
-
G. Fayolle, R. Iasnogorodski, and V. Malyshev. Random Walks in the Quarter Plane: Algebraic Methods, Boundary Value Problems, Applications to Queueing Systems and Analytic Combinatorics. Springer, 2003.
-
G. Fayolle and J.-M. Lasgouttes. Asymptotics and scalings for large product-form networks via the central limit theorem. Markov Process. Related Fields, 2:317-348, 1996.
-
C. Fricker and N. Gast. Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity. Euro journal on transportation and logistics, 5(3):261-291, 2016.
-
C. Fricker, N. Gast, and H. Mohamed. Mean field analysis for inhomogeneous bike sharing systems. Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), 2012.
-
C. Fricker, H. Mohamed, T. Popescu, and M. Trépanier. Stochastic modelling of free-floating car-sharing systems. CIRRELT, 2021.
-
C. Fricker and D. Tibi. Equivalence of ensembles for large vehicle-sharing models. The Annals of Applied Probability, 27(2):883-916, 2017.
-
N. Gast and B. Gaujal. A mean field model of work stealing in large-scale systems. ACM SIGMETRICS Performance Evaluation Review, 38(1):13-24, 2010.
-
Nicolas Gast. Expected values estimated via mean-field approximation are 1/n-accurate. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(1):1-26, 2017.
-
Nicolas Gast and Benny Van Houdt. A refined mean field approximation. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1-28, 2017.
-
D. K. George and C. H. Xia. Asymptotic analysis of closed queueing networks and its implications to achievable service levels. SIGMETRICS Performance Evaluation Review, 38:3-5, 2010.
-
W. J. Gordon and G. F. Newell. Closed queueing systems with exponential servers. Operations Research, 15(2):254-265, 1967.
-
James R. Jackson. Jobshop-like queueing systems. Management Science, 10(1):131-142, 1963.
-
F.P. Kelly. Loss networks. Annals of Applied Probability, 1(3):319-378, 1991.
-
Arpan Mukhopadhyay, Ravi R Mazumdar, and Rahul Roy. Binary opinion dynamics with biased agents and agents with different degrees of stubbornness. In 2016 28th International Teletraffic Congress (ITC 28), volume 1, pages 261-269. IEEE, 2016.
-
Philippe Robert. Stochastic Networks and Queues. Applications of Mathematics: Stochastic Modelling and Applied Probability. Springer, 2003.