Social cost guarantees in smart route guidance

Paolo Serafino, Carmine Ventre, Long Tran-Thanh, Jie Zhang, Bo An, Nick Jennings

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding


We model and study the problem of assigning traffic in an urban road network infrastructure. In our model, each driver submits their intended destination and is assigned a route to follow that minimizes the social cost (i.e., travel distance of all the drivers). We assume drivers are strategic and try to manipulate the system (i.e., misreport their intended destination and/or deviate from the assigned route) if they can reduce their travel distance by doing so. Such strategic behavior is highly undesirable as it can lead to an overall suboptimal traffic assignment and cause congestion. To alleviate this problem, we develop moneyless mechanisms that are resilient to manipulation by the agents and offer provable approximation guarantees on the social cost obtained by the solution. We then empirically test the mechanisms studied in the paper, showing that they can be effectively used in practice in order to compute manipulation resistant traffic allocations.
Original languageEnglish
Title of host publicationPRICAI 2019: Trends in Artificial Intelligence. PRICAI 2019
EditorsA. Nayak, A. Sharma
PublisherSpringer, Cham; Fondazione C.I.M.E., Florence
Number of pages14
ISBN (Print)978-3-030-29910-1
Publication statusPublished - 30 Aug 2019

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Bibliographical note

The 16th Pacific Rim International Conference on Artificial Intelligence , PRICAI 2019 ; Conference date: 26-08-2019 Through 30-08-2019


Dive into the research topics of 'Social cost guarantees in smart route guidance'. Together they form a unique fingerprint.

Cite this