When people choose routes minimizing their individual delay, the aggregate congestion can be much higher compared to that experienced by a centrally-imposed routing. Yet centralized routing is incompatible with the presence of self-interested users. How can we reconcile the two? In this paper we address this question within a repeated game framework and propose a fair incentive mechanism based on artificial currencies that routes selfish users in a system-optimal fashion, while accounting for their temporal preferences. We instantiate the framework in a parallel-network whereby users commute repeatedly (e.g., daily) from a common start node to the end node. Thereafter, we focus on the specific two-arcs case whereby, based on an artificial currency, the users are charged when traveling on the first, fast arc, whilst they are rewarded when traveling on the second, slower arc. We assume the users to be rational and model their choices through a game where each user aims at minimizing a combination of today's discomfort, weighted by their urgency, and the average discomfort encountered for the rest of the period (e.g., a week). We show that, if prices of artificial currencies are judiciously chosen, the routing pattern converges to a system-optimal solution, while accommodating the users’ urgency. We complement our study through numerical simulations. Our results show that it is possible to achieve a system-optimal solution whilst significantly reducing the users’ perceived discomfort when compared to a centralized optimal but urgency-unaware policy.

Urgency-aware optimal routing in repeated games through artificial currencies

Agazzi A.;
2021

Abstract

When people choose routes minimizing their individual delay, the aggregate congestion can be much higher compared to that experienced by a centrally-imposed routing. Yet centralized routing is incompatible with the presence of self-interested users. How can we reconcile the two? In this paper we address this question within a repeated game framework and propose a fair incentive mechanism based on artificial currencies that routes selfish users in a system-optimal fashion, while accounting for their temporal preferences. We instantiate the framework in a parallel-network whereby users commute repeatedly (e.g., daily) from a common start node to the end node. Thereafter, we focus on the specific two-arcs case whereby, based on an artificial currency, the users are charged when traveling on the first, fast arc, whilst they are rewarded when traveling on the second, slower arc. We assume the users to be rational and model their choices through a game where each user aims at minimizing a combination of today's discomfort, weighted by their urgency, and the average discomfort encountered for the rest of the period (e.g., a week). We show that, if prices of artificial currencies are judiciously chosen, the routing pattern converges to a system-optimal solution, while accommodating the users’ urgency. We complement our study through numerical simulations. Our results show that it is possible to achieve a system-optimal solution whilst significantly reducing the users’ perceived discomfort when compared to a centralized optimal but urgency-unaware policy.
Salazar, M.; Paccagnan, D.; Agazzi, A.; Heemels, W. P. M. H. M.
File in questo prodotto:
File Dimensione Formato  
2011.11595 (2).pdf

accesso aperto

Descrizione: Articolo pubblicato
Tipologia: Documento in Pre-print
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 739.93 kB
Formato Adobe PDF
739.93 kB Adobe PDF Visualizza/Apri
1-s2.0-S0947358021000832-main.pdf

accesso aperto

Tipologia: Versione finale editoriale
Licenza: Creative commons
Dimensione 1.8 MB
Formato Adobe PDF
1.8 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1135375
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact