License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2022.13
URN: urn:nbn:de:0030-drops-160998
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16099/
Go to the corresponding LIPIcs Volume Portal

Moreno, Bianca Marin ; Fricker, Christine ; Mohamed, Hanene ; Philippe, Amaury ; Trépanier, Martin

Mean Field Analysis of an Incentive Algorithm for a Closed Stochastic Network

pdf-format:
LIPIcs-AofA-2022-13.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{moreno_et_al:LIPIcs.AofA.2022.13,
  author =	{Moreno, Bianca Marin and Fricker, Christine and Mohamed, Hanene and Philippe, Amaury and Tr\'{e}panier, Martin},
  title =	{{Mean Field Analysis of an Incentive Algorithm for a Closed Stochastic Network}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16099},
  URN =		{urn:nbn:de:0030-drops-160998},
  doi =		{10.4230/LIPIcs.AofA.2022.13},
  annote =	{Keywords: Large scale analysis, mean-field, car-sharing, incentive algorithm, stochastic network, cluster, load balancing, closed Jackson networks, product-form distribution}
}

Keywords: Large scale analysis, mean-field, car-sharing, incentive algorithm, stochastic network, cluster, load balancing, closed Jackson networks, product-form distribution
Collection: 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)
Issue Date: 2022
Date of publication: 08.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI