Urgency-aware Optimal Routing in Repeated Games through Artificial Currencies
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 agents. 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 agents in a system-optimal fashion, while accounting for their temporal preferences. We instantiate the framework in a parallel-network whereby agents 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 agents are charged when traveling on the first, fast arc, whilst they are rewarded when traveling on the second, slower arc. We assume the agents to be rational and model their choices through a game where each agent 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 agents' urgency. We complement our study through numerical simulations. Our results show that it is possible to achieve a system-optimal solution whilst reducing the agents' perceived discomfort by 14-20% when compared to a centralized optimal but urgency-unaware policy.
Code (0)
등록된 구현이 없습니다.
Tasks
ARCSimilar Papers 제목 키워드 기반
Urgency-aware Routing in Single Origin-destination Itineraries through Artificial Currencies
Within mobility systems, the presence of self-interested users can lead to aggregate routing patterns that are far from the societal optimum which could be achieved by centrally controlling the users' choices. In this pa…
ARCContextual Games: Multi-Agent Learning with Side Information
We formulate the novel class of contextual games, a type of repeated games driven by contextual information at each round. By means of kernel-based regularity assumptions, we model the correlation between different conte…
Dynamic Resource Allocation with Karma: An Experimental Study
A system of non-tradable credits that flow between individuals like karma, hence proposed under that name, is a mechanism for repeated resource allocation that comes with attractive efficiency and fairness properties, in…
FairnessNear-Optimal Online Egalitarian learning in General Sum Repeated Matrix Games
We study two-player general sum repeated finite games where the rewards of each player are generated from an unknown distribution. Our aim is to find the egalitarian bargaining solution (EBS) for the repeated game, which…
From Sampled Outcomes to Capability Distributions: Rethinking Supervision for LLM Routing
Existing LLM routing methods often construct supervision from a single sampled response for each query--model pair. Because LLM generation is stochastic, however, such an observation can be an unstable estimate of model …