A Budged-Balanced Tolling Scheme for Efficient Equilibria under Heterogeneous Preferences

Abstract

Multiagent reinforcement learning has shown its potential for tackling real world problems, like traffic.We consider the toll-based route choice problem, in which self-interested drivers (agents) need to repeatedly choose (commuting) routes that minimise the travel costs between their origins to their destinations.One of the major challenges here is to deal with agents' selfishness when competing for a common resource, as they tend to converge to a substantially far from optimum equilibrium.In the case of traffic, this translates into higher congestion levels.Along the years, the use of tolls has been advocated as a means to tackle this issue.However, existing approaches typically assume that (i) drivers have homogeneous preferences, and that (ii) collected tolls are kept for the traffic authority.In this paper, we propose the Generalised Toll-based Q-learning algorithm (GTQ-learning), a multiagent reinforcement learning algorithm capable of realigning the agents' heterogeneous preferences with respect to travel time and monetary expenses.Firstly, we introduce the toll-based route choice problem with preferences and side payments.Building upon such a problem, GTQ-learning works by neutralising agents' preferences, thus ensuring that congestion levels are minimised regardless of agents' selfishness levels.Furthermore, GTQ-learning achieves δ -approximated budget balance by redistributing a fraction δ of the collected tolls and keeping the rest for maintaining the roads.We perform a theoretical analysis of GTQ-learning, showing that it leads agents to a system-efficient equilibrium, and provide supporting empirical results, evidencing that GTQ-learning minimises congestion on realistic road networks.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 4 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.